المحاضرة الخامسة هياكل متقطعة

Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems
Rules of inference
Rules of inference:
• Allow us to infer new True statements from existing True
statements
• Represent logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rule of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example;
• Modus Ponens, or the Law of Detachment
• Rule of inference p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
False False True
False
True
True
True True
True
False False
True
p q p ? q
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
Rules of inference: logically valid inference patterns
Example:
• Modus Ponens, or the Law of Detachment
• Rules of inference
p
p ? q
? q
• Given p is true and the implication p ? q is true then q is true.
• Tautology Form: (p ? (p ? q)) ? q
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Addition
p ? (p ? q) p_____
? p ?q
• Example: It is below freezing now. Therefore, it is below
freezing or raining snow.
• Simplification
(p ? q) ?p p ?q
? p
• Example: It is below freezing and snowing. Therefore it is
below freezing.
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Modus Tollens (modus ponens for the contrapositive)
[ ¬q ? (p ? q)] ? ¬p ¬q
p ?q
? ¬p
• Hypothetical Syllogism
[(p ? q) ? (q ? r)] ? (p ? r) p ? q
q ? r
? p ? r
• Disjunctive Syllogism
[(p ? q) ? ¬p] ?q p ? q
¬p___
? q
11
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• Logical equivalences (discussed earlier)
A <=> B
A ? B is a tautology
Example: De Morgan Law
¬( p ? q ) <=> ¬p ? ¬q
¬( p ? q ) ? ¬p ? ¬q is a tautology
CS 441 Discrete mathematics for CS M. Hauskrecht
Rules of inference
• A valid argument is one built using the rules of inference from
premises (hypotheses). When all premises are true the argument
should lead us to the correct conclusion.
• (p1 ? p2 ? p3 ?… ?pn ) ? q
• How to use the rules of inference?
12
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Assume the following statements (hypotheses):
• It is not sunny this afternoon and it is colder than yesterday.
• We will go swimming only if it is sunny.
• If we do not go swimming then we will take a canoe trip.
• If we take a canoe trip, then we will be home by sunset.
Show that all these lead to a conclusion:
• We will be home by sunset.
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) ?
• We want to show: t
13
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
• Approach:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation: “We will go swimming only if it is sunny”.
• Ambiguity: r ? p or p ? r ?
• Sunny is a must before we go swimming
• Thus, if we indeed go swimming it must be sunny,
therefore r ? p
CS 441 Discrete mathematics for CS M. Hauskrecht
Applying rules of inference
Text:
(1) It is not sunny this afternoon and it is colder than yesterday.
(2) We will go swimming only if it is sunny.
(3) If we do not go swimming then we will take a canoe trip.
(4) If we take a canoe trip, then we will be home by sunset.
Propositions:
• p = It is sunny this afternoon, q = it is colder than yesterday,
r = We will go swimming , s= we will take a canoe trip
• t= We will be home by sunset
Translation:
• Assumptions: (1) ¬ p ? q, (2) r ? p, (3) ¬ r ? s, (4) s? t
• We want to show: t
14
CS 441 Discrete mathematics for CS M. Hauskrecht
Proofs using rules of inference
Translations:
• Assumptions: ¬ p ? q, r ? p, ¬ r ? s, s? t
• We want to show: t
Proof:
• 1. ¬ p ? q Hypothesis
• 2. ¬ p Simplification
• 3. r ? p Hypothesis
• 4. ¬ r Modus tollens (step 2 and 3)
• 5. ¬ r ? s Hypothesis
• 6. s Modus ponens (steps 4 and 5)
• 7. s? t Hypothesis
• 8. t Modus ponens (steps 6 and 7)
• end of proof
CS 441 Discrete mathematics for CS M. Hauskrecht
Informal proofs
Proving theorems in practice:
• The steps of the proofs are not expressed in any formal language
as e.g. propositional logic
• Steps are argued less formally using English, mathematical
formulas and so on
• One must always watch the consistency of the argument made,
logic and its rules can often help us to decide the soundness of the
argument if it is in question
• We use (informal) proofs to illustrate different methods of
proving theorems

proving theorems