Basics of Discrete Structures and Discrete Logic

A presentation regarding basics of discrete logic.

1. Spring 2003 CMSC 203 - Discrete Structures 1
Let’s get started with...Let’s get started with...
LogicLogic!!

2. Spring 2003 CMSC 203 - Discrete Structures 2
LogicLogic
•Crucial for mathematical reasoningCrucial for mathematical reasoning
•Important for program designImportant for program design
•Used for designing electronic circuitryUsed for designing electronic circuitry
•(Propositional )Logic is a system based on (Propositional )Logic is a system based on
propositionspropositions..
•A proposition is a (declarative) statement that is A proposition is a (declarative) statement that is
either either truetrue or or falsefalse (not both). (not both).
•We say that the We say that the truth valuetruth value of a proposition is of a proposition is
either true (either true (TT) or false () or false (FF).).
•Corresponds to Corresponds to 11 and and 00 in digital circuits in digital circuits

3. Spring 2003 CMSC 203 - Discrete Structures 3
The Statement/Proposition GameThe Statement/Proposition Game
““Elephants are bigger than mice.”Elephants are bigger than mice.”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?yesyes
What is the truth value What is the truth value
of the proposition?of the proposition? truetrue

4. Spring 2003 CMSC 203 - Discrete Structures 4
The Statement/Proposition GameThe Statement/Proposition Game
““520 < 111”520 < 111”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?yesyes
What is the truth value What is the truth value
of the proposition?of the proposition? falsefalse

5. Spring 2003 CMSC 203 - Discrete Structures 5
The Statement/Proposition GameThe Statement/Proposition Game
““y > 5”y > 5”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?nono
Its truth value depends on the value of y, Its truth value depends on the value of y,
but this value is not specified.but this value is not specified.
We call this type of statement a We call this type of statement a
propositional functionpropositional function or or open sentenceopen sentence..

6. Spring 2003 CMSC 203 - Discrete Structures 6
The Statement/Proposition GameThe Statement/Proposition Game
““Today is January 27 and 99 < 5.”Today is January 27 and 99 < 5.”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?yesyes
What is the truth value What is the truth value
of the proposition?of the proposition? falsefalse

7. Spring 2003 CMSC 203 - Discrete Structures 7
The Statement/Proposition GameThe Statement/Proposition Game
““Please do not fall asleep.”Please do not fall asleep.”
Is this a statement?Is this a statement? nono
Is this a proposition?Is this a proposition?nono
Only statements can be propositions.Only statements can be propositions.
It’s a request.It’s a request.

8. Spring 2003 CMSC 203 - Discrete Structures 8
The Statement/Proposition GameThe Statement/Proposition Game
““If the moon is made of cheese,If the moon is made of cheese,
then I will be rich.”then I will be rich.”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?yesyes
What is the truth value What is the truth value
of the proposition?of the proposition? probably trueprobably true

9. Spring 2003 CMSC 203 - Discrete Structures 9
The Statement/Proposition GameThe Statement/Proposition Game
““x < y if and only if y > x.”x < y if and only if y > x.”
Is this a statement?Is this a statement? yesyes
Is this a proposition?Is this a proposition?yesyes
What is the truth value What is the truth value
of the proposition?of the proposition? truetrue
… … because its truth value because its truth value
does not depend on does not depend on
specific values of x and y.specific values of x and y.

10. Spring 2003 CMSC 203 - Discrete Structures 10
Combining PropositionsCombining Propositions
As we have seen in the previous examples, As we have seen in the previous examples,
one or more propositions can be combined one or more propositions can be combined
to form a single to form a single compound propositioncompound proposition..
We formalize this by denoting propositions We formalize this by denoting propositions
with letters such as with letters such as p, q, r, s,p, q, r, s, and and
introducing several introducing several logical operators or logical operators or
logical connectiveslogical connectives. .

11. Spring 2003 CMSC 203 - Discrete Structures 11
Logical Operators (Connectives)Logical Operators (Connectives)
We will examine the following logical operators:We will examine the following logical operators:
• Negation Negation (NOT, (NOT, ))
• Conjunction Conjunction (AND, (AND, ))
• Disjunction Disjunction (OR, (OR, ))
• Exclusive-or Exclusive-or (XOR, (XOR,  ))
• Implication Implication (if – then, (if – then,  ))
• Biconditional Biconditional (if and only if, (if and only if,  ))
Truth tables can be used to show how these Truth tables can be used to show how these
operators can combine propositions to compound operators can combine propositions to compound
propositions.propositions.

12. Spring 2003 CMSC 203 - Discrete Structures 12
Negation (NOT)Negation (NOT)
Unary Operator, Symbol: Unary Operator, Symbol: 
PP  PP
true (T)true (T)false (F)false (F)
false (F)false (F)true (T)true (T)

13. Spring 2003 CMSC 203 - Discrete Structures 13
Conjunction (AND)Conjunction (AND)
Binary Operator, Symbol: Binary Operator, Symbol: 
PP QQ PP Q Q
TT TT TT
TT FF FF
FF TT FF
FF FF FF

14. Spring 2003 CMSC 203 - Discrete Structures 14
Disjunction (OR)Disjunction (OR)
Binary Operator, Symbol: Binary Operator, Symbol: 
PP QQ P P  QQ
TT TT TT
TT FF TT
FF TT TT
FF FF FF

15. Spring 2003 CMSC 203 - Discrete Structures 15
Exclusive Or (XOR)Exclusive Or (XOR)
Binary Operator, Symbol: Binary Operator, Symbol: 
PP QQ PPQQ
TT TT FF
TT FF TT
FF TT TT
FF FF FF

16. Spring 2003 CMSC 203 - Discrete Structures 16
Implication (if - then)Implication (if - then)
Binary Operator, Symbol: Binary Operator, Symbol: 
PP QQ PPQQ
TT TT TT
TT FF FF
FF TT TT
FF FF TT

17. Spring 2003 CMSC 203 - Discrete Structures 17
Biconditional (if and only if)Biconditional (if and only if)
Binary Operator, Symbol: Binary Operator, Symbol: 
PP QQ PPQQ
TT TT TT
TT FF FF
FF TT FF
FF FF TT

18. Spring 2003 CMSC 203 - Discrete Structures 18
Statements and OperatorsStatements and Operators
Statements and operators can be combined in any Statements and operators can be combined in any
way to form new statements.way to form new statements.
PP QQ PPQQ ((P)P)((Q)Q)
TT TT FF FF FF
TT FF FF TT TT
FF TT TT FF TT
FF FF TT TT TT

19. Spring 2003 CMSC 203 - Discrete Structures 19
Statements and OperationsStatements and Operations
Statements and operators can be combined in any Statements and operators can be combined in any
way to form new statements.way to form new statements.
PP QQPPQQ(P(PQ)Q)((P)P)((Q)Q)
TT TT TT FF FF
TT FF FF TT TT
FF TT FF TT TT
FF FF FF TT TT

20. Spring 2003 CMSC 203 - Discrete Structures 20
ExercisesExercises
•To take discrete mathematics, you must have To take discrete mathematics, you must have
taken calculus or a course in computer science.taken calculus or a course in computer science.
•When you buy a new car from Acme Motor When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2% Company, you get $2000 back in cash or a 2%
car loan.car loan.
•School is closed if more than 2 feet of snow School is closed if more than 2 feet of snow
falls or if the wind chill is below -100.falls or if the wind chill is below -100.

21. Spring 2003 CMSC 203 - Discrete Structures 21
ExercisesExercises
–P: take discrete mathematicsP: take discrete mathematics
–Q: take calculusQ: take calculus
–R: take a course in computer scienceR: take a course in computer science
•P P  Q Q  R R
•Problem with proposition RProblem with proposition R
–What if I want to represent “take CMSC201”?What if I want to represent “take CMSC201”?
•To take discrete mathematics, you must have To take discrete mathematics, you must have
taken calculus or a course in computer science.taken calculus or a course in computer science.

22. Spring 2003 CMSC 203 - Discrete Structures 22
ExercisesExercises
–P: buy a car from Acme Motor CompanyP: buy a car from Acme Motor Company
–Q: get $2000 cash backQ: get $2000 cash back
–R: get a 2% car loanR: get a 2% car loan
•P P  Q Q  R R
•Why use XOR here? – example of Why use XOR here? – example of ambiguity of ambiguity of
natural languagesnatural languages
•When you buy a new car from Acme Motor When you buy a new car from Acme Motor
Company, you get $2000 back in cash or a 2% Company, you get $2000 back in cash or a 2%
car loan.car loan.

23. Spring 2003 CMSC 203 - Discrete Structures 23
ExercisesExercises
–P: School is closed P: School is closed
–Q: 2 feet of snow fallsQ: 2 feet of snow falls
–R: wind chill is below -100R: wind chill is below -100
•Q Q  R R  P P
•Precedence among operators:Precedence among operators:
, , , , , , , , 
•School is closed if more than 2 feet of snow School is closed if more than 2 feet of snow
falls or if the wind chill is below -100.falls or if the wind chill is below -100.

24. Spring 2003 CMSC 203 - Discrete Structures 24
Equivalent StatementsEquivalent Statements
PP QQ (P(PQ)Q)((P)P)((Q)Q)(P(PQ)Q)((P)P)((Q)Q)
TT TT FF FF TT
TT FF TT TT TT
FF TT TT TT TT
FF FF TT TT TT
The statements The statements (P(PQ) and (Q) and (P) P)  ( (Q) are Q) are logically equivalentlogically equivalent, since they have the , since they have the
same truth table, or put it in another way, same truth table, or put it in another way, (P(PQ) Q) ((P) P)  ( (Q) is always true.Q) is always true.

25. Spring 2003 CMSC 203 - Discrete Structures 25
Tautologies and ContradictionsTautologies and Contradictions
A tautology is a statement that is always true.A tautology is a statement that is always true.
Examples: Examples:
–RR((R)R)
(P(PQ) Q)  ((P)P)(( Q)Q)
A contradiction is a statement that is always false.A contradiction is a statement that is always false.
Examples: Examples:
–RR((R)R)
(((P (P  Q) Q)  ((P) P)  ( (Q))Q))
The negation of any tautology is a contradiction, and The negation of any tautology is a contradiction, and
the negation of any contradiction is a tautology.the negation of any contradiction is a tautology.

26. Spring 2003 CMSC 203 - Discrete Structures 26
EquivalenceEquivalence
Definition: two propositional statements Definition: two propositional statements
S1 and S2 are said to be (logically) S1 and S2 are said to be (logically)
equivalent, denoted S1 equivalent, denoted S1  S2 if S2 if
–They have the same truth table, orThey have the same truth table, or
–S1 S1  S2 is a tautologyS2 is a tautology
Equivalence can be established byEquivalence can be established by
–Constructing truth tablesConstructing truth tables
–Using equivalence laws (Table 5 in Section 1.2)Using equivalence laws (Table 5 in Section 1.2)

27. Spring 2003 CMSC 203 - Discrete Structures 27
EquivalenceEquivalence
Equivalence lawsEquivalence laws
–Identity laws, Identity laws, P P  T T  P, P,
–Domination laws, Domination laws, P P  F F  F, F,
–Idempotent laws, Idempotent laws, P P  P P  P, P,
–Double negation law, Double negation law,  (( P P) )  P P
–Commutative laws, Commutative laws, P P  Q Q  Q Q  P, P,
–Associative laws, Associative laws, P P  (Q (Q  R) R) ( (P P  Q) Q)  R R,,
–Distributive laws, Distributive laws, P P  (Q (Q  R) R) ( (P P  Q) Q)  (P (P  R) R),,
–De Morgan’s laws, De Morgan’s laws,  (P(PQ) Q)  (( P) P)  ( ( Q)Q)
–Law with implicationLaw with implication P P  Q Q   P P  Q Q

28. Spring 2003 CMSC 203 - Discrete Structures 28
ExercisesExercises
•Show that Show that P P  Q Q   P P  Q Q: by truth table : by truth table
•Show that Show that (P (P  Q) Q)  (P (P  R) R)  P P  (Q (Q  R) R): by : by
equivalence laws (q20, p27):equivalence laws (q20, p27):
–Law with implication on both sidesLaw with implication on both sides
–Distribution law on LHSDistribution law on LHS

29. Spring 2003 CMSC 203 - Discrete Structures 29
Summary, Sections 1.1, 1.2Summary, Sections 1.1, 1.2
•PropositionProposition
–Statement, Truth value, Statement, Truth value,
–Proposition, Propositional symbol, Open propositionProposition, Propositional symbol, Open proposition
•Operators Operators
–Define by truth tablesDefine by truth tables
–Composite propositionsComposite propositions
–Tautology and contradictionTautology and contradiction
•Equivalence of propositional statementsEquivalence of propositional statements
–Definition Definition
–Proving equivalence (by truth table or equivalence Proving equivalence (by truth table or equivalence
laws)laws)

30. Spring 2003 CMSC 203 - Discrete Structures 30
Propositional Functions & PredicatesPropositional Functions & Predicates
Propositional function (open sentence):Propositional function (open sentence):
statement involving one or more variables,statement involving one or more variables,
e.g.: x-3 > 5.e.g.: x-3 > 5.
Let us call this propositional function P(x), where Let us call this propositional function P(x), where
P is the P is the predicatepredicate and x is the and x is the variablevariable..
What is the truth value of P(2) ?What is the truth value of P(2) ?falsefalse
What is the truth value of P(8) ?What is the truth value of P(8) ?
What is the truth value of P(9) ?What is the truth value of P(9) ?
falsefalse
truetrue
When a variable is given a value, it is said to be When a variable is given a value, it is said to be
instantiatedinstantiated
Truth value depends on value of variableTruth value depends on value of variable

31. Spring 2003 CMSC 203 - Discrete Structures 31
Propositional FunctionsPropositional Functions
Let us consider the propositional function Let us consider the propositional function
Q(x, y, z) defined as: Q(x, y, z) defined as:
x + y = z.x + y = z.
Here, Q is the Here, Q is the predicatepredicate and x, y, and z are the and x, y, and z are the
variablesvariables..
What is the truth value of Q(2, 3, 5) ?What is the truth value of Q(2, 3, 5) ?truetrue
What is the truth value of Q(0, 1, 2) ?What is the truth value of Q(0, 1, 2) ?
What is the truth value of Q(9, -9, 0) ?What is the truth value of Q(9, -9, 0) ?
falsefalse
truetrue
A propositional function (predicate) becomes a A propositional function (predicate) becomes a
proposition when proposition when allall its variables are its variables are instantiatedinstantiated..

32. Spring 2003 CMSC 203 - Discrete Structures 32
Propositional FunctionsPropositional Functions
Other examples of propositional functions Other examples of propositional functions
Person(x), Person(x), which is true if x is a personwhich is true if x is a person
Person(Socrates) = T Person(Socrates) = T
CSCourse(x),CSCourse(x), which is true if x is a which is true if x is a
computer science coursecomputer science course
CSCourse(CMSC201) = TCSCourse(CMSC201) = T
Person(dolly-the-sheep) = FPerson(dolly-the-sheep) = F
CSCourse(MATH155) = FCSCourse(MATH155) = F
How do we sayHow do we say
All humans are mortalAll humans are mortal
One CS courseOne CS course

33. Spring 2003 CMSC 203 - Discrete Structures 33
Universal QuantificationUniversal Quantification
Let P(x) be a predicate (propositional function).Let P(x) be a predicate (propositional function).
Universally quantified sentenceUniversally quantified sentence::
For all x in the For all x in the universe of discourseuniverse of discourse P(x) is true. P(x) is true.
Using the universal quantifier Using the universal quantifier ::
x P(x) x P(x) “for all x P(x)” or “for every x P(x)”“for all x P(x)” or “for every x P(x)”
(Note: (Note: x P(x) is either true or false, so it is a x P(x) is either true or false, so it is a
proposition, not a propositional function.)proposition, not a propositional function.)

34. Spring 2003 CMSC 203 - Discrete Structures 34
Universal QuantificationUniversal Quantification
Example: Let the universe of discourse be all peopleExample: Let the universe of discourse be all people
S(x): x is a UMBC student.S(x): x is a UMBC student.
G(x): x is a genius.G(x): x is a genius.
What does What does x (S(x) x (S(x)  G(x)) G(x)) mean ? mean ?
““If x is a UMBC student, then x is a genius.” orIf x is a UMBC student, then x is a genius.” or
““All UMBC students are geniuses.”All UMBC students are geniuses.”
If the universe of discourse is all UMBC students, If the universe of discourse is all UMBC students,
then the same statement can be written asthen the same statement can be written as
x G(x)x G(x)

35. Spring 2003 CMSC 203 - Discrete Structures 35
Existential QuantificationExistential Quantification
Existentially quantified sentenceExistentially quantified sentence::
There exists an x in the universe of discourse There exists an x in the universe of discourse
for which P(x) is true.for which P(x) is true.
Using the existential quantifier Using the existential quantifier ::
x P(x) x P(x) “There is an x such that P(x).”“There is an x such that P(x).”
“ “There is at least one x such that P(x).”There is at least one x such that P(x).”
(Note: (Note: x P(x) is either true or false, so it is a x P(x) is either true or false, so it is a
proposition, but no propositional function.)proposition, but no propositional function.)

36. Spring 2003 CMSC 203 - Discrete Structures 36
Existential QuantificationExistential Quantification
Example: Example:
P(x): x is a UMBC professor.P(x): x is a UMBC professor.
G(x): x is a genius.G(x): x is a genius.
What does What does x (P(x) x (P(x)  G(x)) G(x)) mean ? mean ?
““There is an x such that x is a UMBC professor There is an x such that x is a UMBC professor
and x is a genius.”and x is a genius.”
oror
““At least one UMBC professor is a genius.”At least one UMBC professor is a genius.”

37. Spring 2003 CMSC 203 - Discrete Structures 37
QuantificationQuantification
Another example:Another example:
Let the universe of discourse be the real numbers.Let the universe of discourse be the real numbers.
What does What does xxy (x + y = 320)y (x + y = 320) mean ? mean ?
““For every x there exists a y so that x + y = 320.”For every x there exists a y so that x + y = 320.”
Is it true?Is it true?
Is it true for the natural numbers?Is it true for the natural numbers?
yesyes
nono

38. Spring 2003 CMSC 203 - Discrete Structures 38
Disproof by CounterexampleDisproof by Counterexample
A counterexample to A counterexample to x P(x) is an object c so x P(x) is an object c so
that P(c) is false. that P(c) is false.
Statements such as Statements such as x (P(x) x (P(x)  Q(x)) can be Q(x)) can be
disproved by simply providing a counterexample.disproved by simply providing a counterexample.
Statement: “All birds can fly.”Statement: “All birds can fly.”
Disproved by counterexample: Penguin.Disproved by counterexample: Penguin.

39. Spring 2003 CMSC 203 - Discrete Structures 39
NegationNegation
((x P(x)) is logically equivalent to x P(x)) is logically equivalent to x (x (P(x)).P(x)).
((x P(x)) is logically equivalent to x P(x)) is logically equivalent to x (x (P(x)).P(x)).
See Table 2 in Section 1.3.See Table 2 in Section 1.3.
This is de Morgan’s law for quantifiersThis is de Morgan’s law for quantifiers

40. Spring 2003 CMSC 203 - Discrete Structures 40
NegationNegation
ExamplesExamples
Not all roses are redNot all roses are red
x (Rose(x)x (Rose(x)  Red(x) Red(x)))
x (Rose(x)x (Rose(x)  Red(x)Red(x)))
Nobody is perfectNobody is perfect
x (Person(x)x (Person(x)  Perfect(x) Perfect(x)))
x (Person(x)x (Person(x)  Perfect(x)Perfect(x)))

41. Spring 2003 CMSC 203 - Discrete Structures 41
Nested QuantifierNested Quantifier
A predicate can have more than one variables.A predicate can have more than one variables.
–S(x, y, z): z is the sum of x and yS(x, y, z): z is the sum of x and y
–F(x, y): x and y are friendsF(x, y): x and y are friends
We can quantify individual variables in different We can quantify individual variables in different
waysways
x, y, z (S(x, y, z) x, y, z (S(x, y, z)  (x <= z (x <= z  y <= z)) y <= z))
x x y y z (F(x, y) z (F(x, y)  F(x, z) F(x, z)  (y != z) (y != z)  F(y, z)F(y, z)

42. Spring 2003 CMSC 203 - Discrete Structures 42
Nested QuantifierNested Quantifier
Exercise: translate the following English Exercise: translate the following English
sentence into logical expressionsentence into logical expression
““There is a rational number in between every There is a rational number in between every
pair of distinct rational numbers”pair of distinct rational numbers”
Use predicate Use predicate Q(x)Q(x), which is true when x , which is true when x
is a rational numberis a rational number
x,y (x,y (QQ(x) (x)  QQ (y) (y)  (x < y) (x < y) 
u (Q(u) u (Q(u)  (x < u) (x < u)  (u < y))) (u < y)))

43. Spring 2003 CMSC 203 - Discrete Structures 43
Summary, Sections 1.3, 1.4Summary, Sections 1.3, 1.4
•Propositional functions (predicates)Propositional functions (predicates)
•Universal and existential quantifiers, and Universal and existential quantifiers, and
the duality of the twothe duality of the two
•When predicates become propositionsWhen predicates become propositions
–All of its variables are instantiatedAll of its variables are instantiated
–All of its variables are quantifiedAll of its variables are quantified
•Nested quantifiersNested quantifiers
–Quantifiers with negationQuantifiers with negation
•Logical expressions formed by predicates, Logical expressions formed by predicates,
operators, and quantifiersoperators, and quantifiers

44. Spring 2003 CMSC 203 - Discrete Structures 44
Let’s proceed to…Let’s proceed to…
Mathematical Mathematical
ReasoningReasoning

45. Spring 2003 CMSC 203 - Discrete Structures 45
Mathematical ReasoningMathematical Reasoning
We need We need mathematical reasoningmathematical reasoning to to
• determine whether a mathematical argument is determine whether a mathematical argument is
correct or incorrect and correct or incorrect and
• construct mathematical arguments.construct mathematical arguments.
Mathematical reasoning is not only important for Mathematical reasoning is not only important for
conducting conducting proofsproofs and and program verificationprogram verification, but , but
also for also for artificial intelligenceartificial intelligence systems (drawing systems (drawing
logical inferences from knowledge and facts).logical inferences from knowledge and facts).
We focus on We focus on deductivedeductive proofs proofs

46. Spring 2003 CMSC 203 - Discrete Structures 46
TerminologyTerminology
An An axiomaxiom is a basic assumption about mathematical is a basic assumption about mathematical
structure that needs no proof.structure that needs no proof.
-Things known to be true (facts or proven theorems)Things known to be true (facts or proven theorems)
-Things believed to be true but cannot be provedThings believed to be true but cannot be proved
We can use a We can use a proofproof to demonstrate that a to demonstrate that a
particular statement is true. A proof consists of a particular statement is true. A proof consists of a
sequence of statements that form an argument.sequence of statements that form an argument.
The steps that connect the statements in such a The steps that connect the statements in such a
sequence are the sequence are the rules of inferencerules of inference..
Cases of incorrect reasoning are called Cases of incorrect reasoning are called fallaciesfallacies..

47. Spring 2003 CMSC 203 - Discrete Structures 47
TerminologyTerminology
A A theoremtheorem is a statement that can be shown to be is a statement that can be shown to be
true.true.
A A lemmalemma is a simple theorem used as an is a simple theorem used as an
intermediate result in the proof of another intermediate result in the proof of another
theorem.theorem.
A A corollarycorollary is a proposition that follows directly is a proposition that follows directly
from a theorem that has been proved.from a theorem that has been proved.
A A conjectureconjecture is a statement whose truth value is is a statement whose truth value is
unknown. Once it is proven, it becomes a theorem.unknown. Once it is proven, it becomes a theorem.

48. Spring 2003 CMSC 203 - Discrete Structures 48
ProofsProofs
A A theoremtheorem often has two parts often has two parts
-Conditions (premises, hypotheses)Conditions (premises, hypotheses)
-conclusionconclusion
A A correct (deductive) proofcorrect (deductive) proof is to establish that is to establish that
-If the conditions are true then the conclusion is trueIf the conditions are true then the conclusion is true
-I.e., Conditions I.e., Conditions  conclusion is a conclusion is a tautologytautology
Often there are missing pieces between conditions Often there are missing pieces between conditions
and conclusion. Fill it by an and conclusion. Fill it by an argumentargument
-Using conditions and axiomsUsing conditions and axioms
-Statements in the argument connected by proper Statements in the argument connected by proper
rules of inferencerules of inference

49. Spring 2003 CMSC 203 - Discrete Structures 49
Rules of InferenceRules of Inference
Rules of inferenceRules of inference provide the justification of provide the justification of
the steps used in a proof.the steps used in a proof.
One important rule is called One important rule is called modus ponensmodus ponens or the or the
law of detachmentlaw of detachment. It is based on the tautology . It is based on the tautology
(p (p  (p (p  q)) q))  q. We write it in the following way: q. We write it in the following way:
pp
p p  q q
________
 qq
The two The two hypotheseshypotheses p and p p and p  q are q are
written in a column, and the written in a column, and the conclusionconclusion
below a bar, where below a bar, where  means “therefore”. means “therefore”.

50. Spring 2003 CMSC 203 - Discrete Structures 50
Rules of InferenceRules of Inference
The general form of a rule of inference is:The general form of a rule of inference is:
pp
11
pp
22
..
..
..
pp
nn
________
 qq
The rule states that if pThe rule states that if p
11 andand p p
22 andand … …
andand p p
nn are all true, then q is true as well. are all true, then q is true as well.
Each rule is an established tautology ofEach rule is an established tautology of
pp
11  p p
22  … …  p p
nn  q q
These rules of inference can be used in These rules of inference can be used in
any mathematical argument and do not any mathematical argument and do not
require any proof.require any proof.

51. Spring 2003 CMSC 203 - Discrete Structures 51
Rules of InferenceRules of Inference
pp
__________
 ppqq
AdditionAddition
ppqq
__________
 pp
SimplificationSimplification
pp
qq
__________
 ppqq
ConjunctionConjunction
qq
p p  q q
__________
  pp
Modus Modus
tollenstollens
p p  q q
q q  r r
__________
 pp r r
Hypothetical Hypothetical
syllogismsyllogism
((chainingchaining))
ppqq
pp
__________
 q q
Disjunctive Disjunctive
syllogismsyllogism
((resolutionresolution))

52. Spring 2003 CMSC 203 - Discrete Structures 52
ArgumentsArguments
Just like a rule of inference, an Just like a rule of inference, an argument argument consists consists
of one or more hypotheses (or premises) and a of one or more hypotheses (or premises) and a
conclusion. conclusion.
We say that an argument isWe say that an argument is valid valid, if whenever all , if whenever all
its hypotheses are true, its conclusion is also true.its hypotheses are true, its conclusion is also true.
However, if any hypothesis is false, even a valid However, if any hypothesis is false, even a valid
argument can lead to an incorrect conclusion. argument can lead to an incorrect conclusion.
Proof: show that Proof: show that hypotheses hypotheses  conclusion conclusion is true is true
using rules of inferenceusing rules of inference

53. Spring 2003 CMSC 203 - Discrete Structures 53
ArgumentsArguments
Example:Example:
““If 101 is divisible by 3, then 101If 101 is divisible by 3, then 101
22
is divisible by 9. is divisible by 9.
101 is divisible by 3. Consequently, 101101 is divisible by 3. Consequently, 101
22
is divisible is divisible
by 9.”by 9.”
Although the argument is Although the argument is validvalid, its conclusion is , its conclusion is
incorrectincorrect, because one of the hypotheses is false , because one of the hypotheses is false
(“101 is divisible by 3.”).(“101 is divisible by 3.”).
If in the above argument we replace 101 with 102, If in the above argument we replace 101 with 102,
we could correctly conclude that 102we could correctly conclude that 102
22
is divisible is divisible
by 9.by 9.

54. Spring 2003 CMSC 203 - Discrete Structures 54
ArgumentsArguments
Which rule of inference was used in the last Which rule of inference was used in the last
argument?argument?
p: “101 is divisible by 3.”p: “101 is divisible by 3.”
q: “101q: “101
22
is divisible by 9.” is divisible by 9.”
pp
p p  q q
__________
 qq
Modus Modus
ponensponens
Unfortunately, one of the hypotheses (p) is false.Unfortunately, one of the hypotheses (p) is false.
Therefore, the conclusion q is incorrect.Therefore, the conclusion q is incorrect.

55. Spring 2003 CMSC 203 - Discrete Structures 55
ArgumentsArguments
Another example:Another example:
““If it rains today, then we will not have a barbeque If it rains today, then we will not have a barbeque
today. If we do not have a barbeque today, then today. If we do not have a barbeque today, then
we will have a barbeque tomorrow.we will have a barbeque tomorrow.
Therefore, if it rains today, then we will have a Therefore, if it rains today, then we will have a
barbeque tomorrow.”barbeque tomorrow.”
This is a This is a validvalid argument: If its hypotheses are argument: If its hypotheses are
true, then its conclusion is also true.true, then its conclusion is also true.

56. Spring 2003 CMSC 203 - Discrete Structures 56
ArgumentsArguments
Let us formalize the previous argument:Let us formalize the previous argument:
p: “It is raining today.”p: “It is raining today.”
q: “We will not have a barbecue today.”q: “We will not have a barbecue today.”
r: “We will have a barbecue tomorrow.”r: “We will have a barbecue tomorrow.”
So the argument is of the following form:So the argument is of the following form:
p p  q q
q q  r r
____________
 P P  r r
Hypothetical Hypothetical
syllogismsyllogism

57. Spring 2003 CMSC 203 - Discrete Structures 57
ArgumentsArguments
Another example:Another example:
Gary is either intelligent or a good actor.Gary is either intelligent or a good actor.
If Gary is intelligent, then he can count If Gary is intelligent, then he can count
from 1 to 10.from 1 to 10.
Gary can only count from 1 to 3.Gary can only count from 1 to 3.
Therefore, Gary is a good actor.Therefore, Gary is a good actor.
i: “Gary is intelligent.”i: “Gary is intelligent.”
a: “Gary is a good actor.”a: “Gary is a good actor.”
c: “Gary can count from 1 to 10.”c: “Gary can count from 1 to 10.”

58. Spring 2003 CMSC 203 - Discrete Structures 58
ArgumentsArguments
i: “Gary is intelligent.”i: “Gary is intelligent.”
a: “Gary is a good actor.”a: “Gary is a good actor.”
c: “Gary can count from 1 to 10.”c: “Gary can count from 1 to 10.”
Step 1:Step 1:  c c HypothesisHypothesis
Step 2:Step 2: i i  c c HypothesisHypothesis
Step 3:Step 3:  i i Modus tollens Steps 1 & 2Modus tollens Steps 1 & 2
Step 4:Step 4: a a  i i HypothesisHypothesis
Step 5:Step 5: a a Disjunctive SyllogismDisjunctive Syllogism
Steps 3 & 4Steps 3 & 4
Conclusion: Conclusion: aa (“Gary is a good actor.”) (“Gary is a good actor.”)

59. Spring 2003 CMSC 203 - Discrete Structures 59
ArgumentsArguments
Yet another example:Yet another example:
If you listen to me, you will pass CS 320.If you listen to me, you will pass CS 320.
You passed CS 320.You passed CS 320.
Therefore, you have listened to me.Therefore, you have listened to me.
Is this argument valid?Is this argument valid?
NoNo, it assumes ((p , it assumes ((p  q) q) q) q)  p. p.
This statement is not a tautology. It is This statement is not a tautology. It is falsefalse if p is if p is
false and q is true.false and q is true.

60. Spring 2003 CMSC 203 - Discrete Structures 60
Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements
x P(x)x P(x)
____________________
 P(c) if cP(c) if cUU
Universal Universal
instantiationinstantiation
P(c) for an arbitrary cP(c) for an arbitrary cUU
______________________________________
 x P(x)x P(x)
Universal Universal
generalizationgeneralization
x P(x)x P(x)
____________________________________________
 P(c) for some element cP(c) for some element cUU
Existential Existential
instantiationinstantiation
P(c) for some element cP(c) for some element cUU
________________________________________
 x P(x) x P(x)
Existential Existential
generalizationgeneralization

61. Spring 2003 CMSC 203 - Discrete Structures 61
Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements
Example:Example:
Every UMB student is a genius. Every UMB student is a genius.
George is a UMB student.George is a UMB student.
Therefore, George is a genius.Therefore, George is a genius.
U(x): “x is a UMB student.”U(x): “x is a UMB student.”
G(x): “x is a genius.”G(x): “x is a genius.”

62. Spring 2003 CMSC 203 - Discrete Structures 62
Rules of Inference for Quantified StatementsRules of Inference for Quantified Statements
The following steps are used in the argument:The following steps are used in the argument:
Step 1:Step 1: x (U(x) x (U(x)  G(x)) G(x)) HypothesisHypothesis
Step 2:Step 2: U(George) U(George)  G(George) G(George)Univ. instantiation Univ. instantiation
using Step 1using Step 1
x P(x)x P(x)
____________________
 P(c) if cP(c) if cUU
Universal Universal
instantiationinstantiation
Step 3:Step 3: U(George) U(George) HypothesisHypothesis
Step 4:Step 4: G(George) G(George) Modus ponensModus ponens
using Steps 2 & 3using Steps 2 & 3

63. Spring 2003 CMSC 203 - Discrete Structures 63
Proving TheoremsProving Theorems
Direct proof:Direct proof:
An implication p An implication p  q can be proved by showing that q can be proved by showing that
if p is true, then q is also true.if p is true, then q is also true.
Example:Example: Give a direct proof of the theorem Give a direct proof of the theorem
“If n is odd, then n“If n is odd, then n
22
is odd.” is odd.”
Idea:Idea: Assume that the hypothesis of this Assume that the hypothesis of this
implication is true (n is odd). Then use rules of implication is true (n is odd). Then use rules of
inference and known theorems of math to show inference and known theorems of math to show
that q must also be true (nthat q must also be true (n
22
is odd). is odd).

64. Spring 2003 CMSC 203 - Discrete Structures 64
Proving TheoremsProving Theorems
n is odd.n is odd.
Then n = 2k + 1, where k is an integer.Then n = 2k + 1, where k is an integer.
Consequently, nConsequently, n
22
= (2k + 1) = (2k + 1)
22
..
= 4k= 4k
22
+ 4k + 1 + 4k + 1
= 2(2k= 2(2k
22
+ 2k) + 1 + 2k) + 1
Since nSince n
22
can be written in this form, it is odd. can be written in this form, it is odd.

65. Spring 2003 CMSC 203 - Discrete Structures 65
Proving TheoremsProving Theorems
Indirect proof:Indirect proof:
An implication p An implication p  q is equivalent to its q is equivalent to its contra-contra-
positivepositive q q  p. Therefore, we can prove p p. Therefore, we can prove p  q q
by showing that whenever q is false, then p is also by showing that whenever q is false, then p is also
false.false.
Example:Example: Give an indirect proof of the theorem Give an indirect proof of the theorem
“If 3n + 2 is odd, then n is odd.”“If 3n + 2 is odd, then n is odd.”
Idea:Idea: Assume that the conclusion of this Assume that the conclusion of this
implication is false (n is even). Then use rules of implication is false (n is even). Then use rules of
inference and known theorems to show that p inference and known theorems to show that p
must also be false (3n + 2 is even).must also be false (3n + 2 is even).

66. Spring 2003 CMSC 203 - Discrete Structures 66
Proving TheoremsProving Theorems
n is even.n is even.
Then n = 2k, where k is an integer.Then n = 2k, where k is an integer.
It follows that 3n + 2 = 3(2k) + 2 It follows that 3n + 2 = 3(2k) + 2
= 6k + 2= 6k + 2
= 2(3k + 1)= 2(3k + 1)
Therefore, 3n + 2 is even.Therefore, 3n + 2 is even.
We have shown that the contrapositive of the We have shown that the contrapositive of the
implication is true, so the implication itself is also implication is true, so the implication itself is also
true true (If 3n + 2 is odd, then n is odd).(If 3n + 2 is odd, then n is odd).

67. Spring 2003 CMSC 203 - Discrete Structures 67
Proving TheoremsProving Theorems
Indirect Proof is a special case of Indirect Proof is a special case of proof by proof by
contradictioncontradiction
Suppose n is even (Suppose n is even (negation of the conclusionnegation of the conclusion).).
Then n = 2k, where k is an integer.Then n = 2k, where k is an integer.
It follows that 3n + 2 = 3(2k) + 2 It follows that 3n + 2 = 3(2k) + 2
= 6k + 2= 6k + 2
= 2(3k + 1)= 2(3k + 1)
Therefore, 3n + 2 is even.Therefore, 3n + 2 is even.
However, this is a However, this is a contradictioncontradiction since 3n + 2 is given since 3n + 2 is given
to be odd, so the conclusion (n is odd) holds.to be odd, so the conclusion (n is odd) holds.

68. Spring 2003 CMSC 203 - Discrete Structures 68
Another Example on ProofAnother Example on Proof
Anyone performs well is either intelligent or a Anyone performs well is either intelligent or a
good actor.good actor.
If someone is intelligent, then he/she can count If someone is intelligent, then he/she can count
from 1 to 10.from 1 to 10.
Gary performs well.Gary performs well.
Gary can only count from 1 to 3.Gary can only count from 1 to 3.
Therefore, not everyone is both intelligent and a Therefore, not everyone is both intelligent and a
good actorgood actor
P(x): x performs wellP(x): x performs well
I(x): x is intelligentI(x): x is intelligent
A(x): x is a good actorA(x): x is a good actor
C(x): x can count from 1 to 10C(x): x can count from 1 to 10

69. Spring 2003 CMSC 203 - Discrete Structures 69
Another Example on ProofAnother Example on Proof
Hypotheses:Hypotheses:
1.1.Anyone performs well is either intelligent or a good Anyone performs well is either intelligent or a good
actor.actor.
x (P(x) x (P(x)  I(x) I(x)  A(x)) A(x))
2.2.If someone is intelligent, then he/she can count If someone is intelligent, then he/she can count
from 1 to 10.from 1 to 10.
x (I(x) x (I(x)  C C(x) )(x) )
3.3.Gary performs well.Gary performs well.
P(G)P(G)
4.4.Gary can only count from 1 to 3.Gary can only count from 1 to 3.
C(G)C(G)
Conclusion: not everyone is both intelligent and a good Conclusion: not everyone is both intelligent and a good
actoractor
x(I(x) x(I(x)  A(x)) A(x))

70. Spring 2003 CMSC 203 - Discrete Structures 70
Another Example on ProofAnother Example on Proof
Direct proof:Direct proof:
Step 1:Step 1: x (P(x) x (P(x)  I(x) I(x)  A(x)) A(x)) HypothesisHypothesis
Step 2:Step 2: P(G) P(G)  I(G) I(G)  A(G) A(G) Univ. Inst. Step 1Univ. Inst. Step 1
Step 3:Step 3: P(G) P(G) HypothesisHypothesis
Step 4:Step 4: I(G) I(G)  A(G) A(G) Modus ponens Steps 2 & 3Modus ponens Steps 2 & 3
Step 5:Step 5: x (I(x) x (I(x)  C(x)) C(x)) HypothesisHypothesis
Step 6:Step 6: I(G) I(G)  C(G) C(G) Univ. inst. Step5Univ. inst. Step5
Step 7:Step 7: C(G) C(G) HypothesisHypothesis
Step 8:Step 8: I(G) I(G) Modus tollens Steps 6 & 7Modus tollens Steps 6 & 7
Step 9:Step 9: I(G) I(G)  A(G) A(G) Addition Step 8Addition Step 8
Step 10:Step 10: (I(G) (I(G)  A(G)) A(G))Equivalence Step 9Equivalence Step 9
Step 11:Step 11: xx(I(x) (I(x)  A(x)) A(x))Exist. general. Step 10Exist. general. Step 10
Step 12:Step 12: x (I(x) x (I(x)  A(x)) A(x)) Equivalence Step 11Equivalence Step 11
Conclusion: Conclusion: x (I(x) x (I(x)  A(x)) A(x)), not everyone is both intelligent and , not everyone is both intelligent and
a good actor.a good actor.

71. Spring 2003 CMSC 203 - Discrete Structures 71
Summary, Section 1.5Summary, Section 1.5
•Terminology (axiom, theorem, conjecture, Terminology (axiom, theorem, conjecture,
argument, etc.)argument, etc.)
•Rules of inference (Tables 1 and 2)Rules of inference (Tables 1 and 2)
•Valid argument (hypotheses and conclusion)Valid argument (hypotheses and conclusion)
•Construction of valid argument using rules of Construction of valid argument using rules of
inferenceinference
–For each rule used, write down and the statements For each rule used, write down and the statements
involved in the proofinvolved in the proof
•Direct and indirect proofsDirect and indirect proofs
–Other proof methods (e.g., induction, pigeon hole) Other proof methods (e.g., induction, pigeon hole)
will be introduced in later chapterswill be introduced in later chapters