1/27/2014
Quick Questions?
What is the negation of Some students in your class use e-mail?
Some students in your class do not use e-mail. All students in your class use e-mail. All students in your class do not use e-mail.
Quick Questions?
What is the negation of Some friendly people are not angry?
Some friendly people are angry. Some unfriendly people are angry. All friendly people are angry. All unfriendly people are angry. All friendly people are not angry.
1/27/2014
Chapter 1, Part III: Proofs
Summary
Valid Arguments and Rules of Inference Proof Methods Proof Strategies
1/27/2014
Section 1.6
Example of Valid Arguments
We have the two premises: (Let P(x), Q(x), and R(x) be the propositional functions x is a lion, x is fierce, and x drinks coffee, respectively.) All lions are fierce. x (P(x) Q(x)) Some lions do not drink coffee. x (P(x) R(x))
And the conclusion:
Some fierce creatures do not drink coffee.
x (Q(x) R(x)) How do we get the conclusion from the premises?
1/27/2014
Example of Valid Arguments
We have the two premises:
If you have a current password, then you can log onto the network. (pq) You have a current password. (proposition p)
And the conclusion:
You can log onto the network. (proposition q)
How do we get the conclusion from the premises?
The Argument
We can express the premises (above the line) and the conclusion (below the line) in propositional logic as an argument:
We will see shortly that this is a valid argument.
1/27/2014
Valid Arguments
The rules of inference are the essential building block in the construction of valid arguments. We will show how to construct valid arguments in two stages; first for propositional logic and then for predicate logic.
1. 2.
Propositional Logic
Inference Rules
Predicate Logic
Inference rules for propositional logic plus additional inference rules to handle variables and quantifiers.
Arguments in Propositional Logic
An argument in propositional logic is a sequence of propositions. All but the final proposition are called premises. The last statement is the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true.
1/27/2014
Arguments in Propositional Logic
An argument form in propositional logic is a sequence of compound propositions involving propositional variables. An argument form is valid no matter which particular propositions are substituted for the propositional variables in its premises, the conclusion is true if the premises are all true.
Arguments in Propositional Logic
The argument form with premises p1 ,p2, ,pn and conclusion q is valid, when (p1 p2 pn ) q is a tautology. The key to showing that an argument in propositional logic is valid is to show that its argument form is valid. Inference rules are relatively simple argument forms that will be used to construct more complex argument forms.
1/27/2014
Rules of Inference for Propositional Logic: Modus Ponens
Corresponding Tautology: (p (p q)) q
Example: Let p be It is snowing. Let q be I will study discrete math. If it is snowing, then I will study discrete math. It is snowing. Therefore , I will study discrete math.
Modus Tollens
Corresponding Tautology: (p(p q))q
Example: Let p be it is snowing. Let q be I will study discrete math. If it is snowing, then I will study discrete math. I will not study discrete math. Therefore , it is not snowing.
1/27/2014
Hypothetical Syllogism
Corresponding Tautology: ((p q) (qr))(p r)
Example: Let p be it snows. Let q be I will study discrete math. Let r be I will get an A. If it snows, then I will study discrete math. If I study discrete math, I will get an A. Therefore , If it snows, I will get an A.
Disjunctive Syllogism
Corresponding Tautology: (p(p q))q
Example: Let p be I will study discrete math. Let q be I will study English literature. I will study discrete math or I will study English literature. I will not study discrete math. Therefore , I will study English literature.
1/27/2014
Addition
Corresponding Tautology: p (p q)
Example: Let p be I will study discrete math. Let q be I will visit Las Vegas. I will study discrete math. Therefore, I will study discrete math or I will visit Las Vegas.
Simplification
Corresponding Tautology: (pq) p
Example: Let p be I will study discrete math. Let q be I will study English literature. I will study discrete math and English literature Therefore, I will study discrete math.
1/27/2014
Conjunction
Corresponding Tautology: ((p) (q)) (p q)
Example: Let p be I will study discrete math. Let q be I will study English literature.
I will study discrete math. I will study English literature. Therefore, I will study discrete math and I will study English literature.
Resolution
Resolution plays an important role in AI and is used in Prolog.
Corresponding Tautology: ((p r ) (p q)) (q r)
Example: Let p be I am taking CSCI 1301. Let q be I am taking CSCI 2610. Let r be I am taking CSCI 1302. I am not taking CSCI 1301 or I am taking CSCI 1302. I am taking CSCI 1301 or I am taking CSCI 2610. Therefore, I am taking CSCI 1302 or I am taking CSCI 2610.
10
1/27/2014
Using Rules of Inference to Build Valid Arguments
A valid argument is a sequence of statements. Each statement is either a premise or follows from previous statements by rules of inference. The last statement is called conclusion. A valid argument takes the following form: S1 S2
. . .
Sn
Fallacies
Mistakes in proof by applying contingencies instead of tautologies are fallacies. Affirming the conclusion (Common Mistake)
If it is Sunday afternoon, then I go to the movies I go to the movies It is Sunday afternoon Its Saturday Night!!
22
11
1/27/2014
Fallacies
Denying the hypothesis
If an animal flies then the animal is a bird The animal does not fly The animal is not a bird Its a penguin!!
23
Valid Arguments
Example 1: From the single proposition Show that q is a conclusion. Solution:
12
