Transcript PPT

Valid AND Invalid Arguments
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
2.3
[email protected]
1
Argument
An argument is a sequence of propositions (statements ), and propositional
forms.
All statements but the final one are called assumptions or hypothesis.
The final statement is called the conclusion.
An argument is valid if: whenever all the assumptions are true, then the
conclusion is true.
The conclusion is said to be inferred, entails or deduced from the truth
of the premises
If today is Wednesday, then yesterday is Tuesday.
Today is Wednesday.
Yesterday is Tuesday.
Introduction to Abstract Mathematics
2
Entailment



A collection of statements P1,…,Pn (premises) entails statement Q
(conclusion) if and only if:
– Whenever all premises hold the conclusion holds
– For every interpretation I that makes all Pj hold (true), I also
makes Q hold (true)
Notations for valid arguments: P1,…,Pn
Q or
P1,…,Pn ├ Q
Example
Premises:
P1 = “If Socrates is human then Socrates is mortal”
P2 = “Socrates is human”
Conclusion:
Q = “Socrates is mortal”
Introduction to Abstract Mathematics
3
Valid Argument Forms
Modus Ponens
To sat that an argument form is valid if no matter what particular
propositions are substituted for the propositional variables in its
promises
if the resulting promises are true
p and p 
then
then
the conclusion is also true
q
q
If you are a fish, then you drink water.
You drink water.
You are a fish.
p
q
T
q
T
p→q
T
T
T
F
F
F
F
T
T
T
F
F
T
F
Modus ponens is Latin meaning “method of affirming”.
Introduction to Abstract Mathematics
4
Modus Tollens
P  Q, ~ Q ├ ~ P
If p then q.
~q
~p
p
q
p→q
~q
~p
If you are a fish, then you drink water.
You are not a fish.
You do not drink water.
Modus tollens is Latin meaning "method of denying”.
Introduction to Abstract Mathematics
5
Equivalence
A student is trying to prove that propositions P, Q, and R are all true.
She proceeds as follows.
First, she proves three facts:
• P implies Q
• Q implies R
• R implies P.
Then she concludes,
``Thus P, Q, and R are all true.''
Proposed argument:
( P  Q), (Q  R), ( R  P)
P Q R
Introduction to Abstract Mathematics
Is it valid?
6
Valid Argument?
Conclusion true whenever all assumptions are true.
assumptions
conclusion
To prove an argument is not valid, we just need to find a counterexample.
Introduction to Abstract Mathematics
7
Exercises
Introduction to Abstract Mathematics
8
More Exercises
Introduction to Abstract Mathematics
9
Contradiction
If you can show that the assumption that the statement p is false leads
logically to a contradiction, then you can conclude that p is true.
You are working as a clerk.
If you have won Mark 6, then you would not work as a clerk.
You have not won Mark 6.
Introduction to Abstract Mathematics
10
Propositional Logic


Method #1:
– Go through all possible interpretations and check the definition
of valid argument
Method #2:
– Use derivation rules to get from the premises to the conclusion
in a logically sound way
 “derive the conclusions from premises”
Introduction to Abstract Mathematics
11
Method #1


Section 1.3 in the text proves many arguments/inference rules using
truth tables
Suppose the argument is:
P1,…,PN therefore Q
Create a truth table for formula
F=(P1 & … & PN  Q)
Check if F is a tautology
Introduction to Abstract Mathematics
12
But Why?


Formula A entails formula B iff
(A  B) is a tautology
In general:
– premises P1,…,PN entail Q
Iff
formula F=(P1 & … & PN  Q) is a tautology
Introduction to Abstract Mathematics
P1
P2
.
.
.
PN
Q
13
Examples
PvQvR
~R
PvQvR
~R
PvQ
Q
valid/invalid?
(example 1.3.1 in the book, p. 30)
Introduction to Abstract Mathematics
14
Examples

PQ
Q
entails
P

valid/invalid?



Introduction to Abstract Mathematics
15
Example
PvQ
~P  ~Q
PQ


valid/invalid?
Any argument with a contradiction in its premises is
valid by default…
Introduction to Abstract Mathematics
16
Method #2 : Derivations

To prove that an argument is valid:
– Begin with the premises
– Use valid/sound inference rules
– Arrive at the conclusion
Introduction to Abstract Mathematics
17
Inference Rules


(Logic Rules)
But what are these “inference rules”?
They are simply…
- valid arguments!
Example:
– XY
– XYZW
– therefore
– ZW
by modus ponens
Introduction to Abstract Mathematics
18
Example









(X  Y  Z  W)  K
XY
therefore
ZW
How?
(X  Y  Z  W)  K
XYZW
by conjunctive simplification
XY
ZW
by modus ponens
Introduction to Abstract Mathematics
19
Derivations

The chain of inference rules that starts with the
premises and ends with the conclusion is called a
derivation:
– The conclusion is derived from the premises
Such a derivation makes a proof of argument’s validity
Introduction to Abstract Mathematics
20
Example









(X  Y  Z  W)  K
XY
therefore
ZW
derivation
How?
(X  Y  Z  W)  K
XYZW
by conjunctive simplification
XY
ZW
by modus ponens
Introduction to Abstract Mathematics
21
Definition
Let H1, H2, … Hk and Q be propositional expressions. A propositional
expression Q is sad to be logical consequence of H1, H2, … Hk if Q
is true whenever all H1, H2, … Hk are evaluated to be true.
This relationship is expressed symbolically by writing
H1, H2, … Hk
Q . Or
H1, H2, … Hk ├ Q
This is, what is called rule of inference or valid argument. It is
normally read as
H1, H2, …, and Hk yield Q
H1, H2, …, and Hk entails Q .
Introduction to Abstract Mathematics
22
Example:
The following truth table shows P, P  Q ├ Q since it proves
that (P  (P  Q))  Q is a tautology
P
PQ
Q
P ( P  Q)
(P  (P  Q))  Q
T
T
T
T
T
T
F
F
F
T
F
T
T
F
T
F
F
T
F
T
Introduction to Abstract Mathematics
23
Not a valid arguments
If for some propositional forms H1, H2, … Hk and Q we have all
H1, H2, … Hk are evaluated to be true and Q false, then we say that Q
does not logically follow from H1, H2, … Hk . We will use the following notation
to indicate that by
H1, H2, … Hk ├? Q
(we call this invalid argument).
Example: Show that Q, P  Q ├? P (is not valid argument).
P Q
T
T
T
F
F
T
F
F
Introduction to Abstract Mathematics
P  Q Q ( P  Q) (P  (P  Q))  P
T
T
T
F
F
T
T
T
F
T
F
T
24
Theorem (LR): Let P, Q, R, and S be propositional expressions then the
followings are valid arguments (rules of logic or inference rules )
1. P  Q, P├ Q
Modus Ponens [MP]
2. PQ ,  Q ├  P
Modus Tolens [MT]
3. (P  Q)  (R  S), P  R ├ Q  S
Constructive Dilemma [CD]
4. P  Q ├ P
Simplification [Simp]
5. P├ P  Q or Q ├ P  Q
Addition (Generalization) [Add]
6. P, Q ├ P  Q
Conjunction [Conj]
7. P  Q ,  P ├ Q
or P  Q ,  Q ├ P
Disjunctive Syllogism [DS](Ellimination)
8. (P  Q)  ( R  S),  Q  S ├  P   R
Destructive Dilemma [DD]
9. P  Q, Q  R├ P  R
Transitivity [Tr]
Introduction to Abstract Mathematics
25
Definition of proof
A proof of Q from H1, H2, … Hk is finite sequence of propositional forms
Q 1, Q 2, … Qn
such that Qn is same as Q and every Qj is either one of Hi, (i = 1, 2, … , k)
or it follows from the proceedings by the logic rules.
Note: In these proofs we will follow the following formats:
We begin with by listing all the hypotheses (marked as Hyp), then the
sequence of propositional forms followed by the reason (short description of
rules) that allowed that proposition to be included in proof in the same line
and end with the conclusion. To make referencing easier we will number
the lines and use abbreviated names of logic rules specified in the Theorem
(RL1).
Introduction to Abstract Mathematics
26
Example:
Prove
(P  Q)  (Q  R), P ├ Q
Proof:
1. (P  Q)  (Q  R)
2. P
3. P  Q
4. Q  R
5. Q
Introduction to Abstract Mathematics
Hyp
Hyp
3 Add
3, 1 MP
4 S .
END
27
Example: (P  Q), P  (R  S),  Q ├ (R  S)
Proof:
1.
2.
3.
4.
5.
(P  Q)
P  (R  S)
 Q
 P
(R  S)
Hyp
Hyp
Hyp
1,3 MT
2,4 DS
END
Introduction to Abstract Mathematics
28
Second Type of Logic rules (Rules of Replacement)



Recall that if two propositional expressions P and Q are logically
equivalent P  Q if they have same truth tables.
Now suppose P  Q and P appears in a propositional expression
R. If in R some of the appearances of P is replaced by Q then
the new resulting propositional expression R’ is logically
equivalent to R.
To make proof writing more flexible we will extend rules of logic
by adding some simple rules of replacement listed in the
following theorem.
Introduction to Abstract Mathematics
29
Theorem RR ( See theorem 1.1.1) (replacement rules)
Commutative Law [Com]
P  Q  Q  P ,
P  Q  Q  P
3. Distributive Law [Dist]
P  (Q  R)  (P  Q)  (P  R)
P  (Q  R)  (P  Q)  (P  R)
5. DeMorgan Law [DeM]
~ ( P  Q)  (~ P  ~ Q )
~ ( P  Q)  (~ P  ~ Q )
7. Implication Law [Impl]
(P  Q)  (~ P  Q)
1.
9. Exportation [Exp]
(P  Q)  R  P (Q  R)
11. P  t  P and P  c  c
2. Associative Law [Assoc]
(P  Q )  R  P  (Q  R)
(P  Q )  R  P  (Q  R)
4. Contrapositive Law [Contr]
(P  Q)  (~ Q  P)
6. Double Negation [DN]
~ ~ (P)  P
8. Equivalence Law [Equiv]
P  Q  ( P  Q)  (Q  P)
P  Q  (P  Q)  (~ Q  ~ P)
10. Tautology (Identity) [ Taut]
P  P  P or P  P  P
12 P  t  t and P  c  P
t-tautolagy and c-contradiction
Introduction to Abstract Mathematics
30
Eample: Prove (P  Q), (R  Q)├ (P  R)  Q
Proof:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
P  Q
R  Q
 P  Q
 R  Q
( P  Q)  ( R  Q)
(Q   P)  (Q   R)
Q  ( P   R)
Q   (P  R)
 (P  R)  Q
(P  R)  Q
Introduction to Abstract Mathematics
Hyp
Hyp
1 Impl
2 Impl
3,4 Conj
5 Com
6 Dist
7 DeM
8 Com
9 Impl
END
31
Practice problems
1.
2.
3.
4.
Study the Sections 2.3 from your textbook.
Be sure that you understand all the examples discussed in
class and in textbook.
Only after you complete the proof of the Theorem LR
from the notes
Do the following problems from the textbook:
Exercise 2.3, # 2, 3, 7, 8, 15, 26, 36, 43, 44, 46, 51.
Introduction to Abstract Mathematics
32