Transcript Survey of Mathematical Ideas Math 100 Chapter3

Survey of Mathematical Ideas
Math 100
Chapter 3, Logic
John Rosson
Thursday February 15, 2007
The Lady and the Tiger
1
2
p - Lady in room 1
q - Tiger in room 1
r - Lady in room 2
s - Tiger in room 2
Given information:
ps
(pr)  (qs)
Argument: If the first sign were true, both p and
s would have to be true. This would mean that
both disjunctions in the second sign would have
to be true and so the sign would be true. But this
contradicts the first piece of information, so the
first sign has to be false. Since they do not share
a room the lady has to be in 2 ( r ) and the tiger in
1 (q).
• One sign is true the
other false
•The lady and tiger do
not share a room
Introduction to Logic
1.
2.
3.
4.
5.
Statements and Quantifiers
Truth Tables and Equivalent Statements
The Conditional
More on the Conditional
(3.6) Analyzing Arguments using Truth
Tables
The Conditional
Recall the truth table for the conditional statement.
Conditional
p
q
pq
T
T
T
T
F
F
F
T
T
F
F
T
The conditional
statement is false
only when the first
statement, called
the antecedent, is
true and the second
statement, called
the consequent, is
false.
A conditional statement is always true when the
antecedent is false and always true when the
consequent is true.
Calculating Truth Tables
Calculating truth tables involving the conditional is not difficult. All we have
to remember is that the conditional is false only when the antecedent is
true and the consequent is false.
p
T
T
F
F
q
T
F
T
F
( p  q) 
( p  q)
F T T T
F T T F
T F T T
T F F F
q

F
T
F
T

F
T
F
T
q
T
F
T
F
Calculating Truth Tables
Notice that the conditional statement p  q
is equivalent to the statement ~pq.
p
T
T
F
F
q
T
F
T
F
p
T
T
F
F

T
F
T
T
q
T
F
T
F
~
F
F
T
T
p
T
T
F
F

T
F
T
T
q
T
F
T
F
Since the conditional
can be interpreted as
implication, this
equivalence can be
interpreted as
follows. The claim
that “p implies q” has
the same logical
meaning as “either p
is false or q is true”.
For example, let p be the statement that “the number n is evenly divisible by 4”
and let q be the statement that “ the number n is evenly divisible by 2”. Now, p
implies q since any number divisible by 4 is divisible by 2. It is also valid to say
that either a number is not divisible by 4 or it is divisible by 2.
This equivalence also means that any statement containing a conditional () may be logically
replaced by one using only “not” (~) and “or” ().
Calculating Truth Tables
Notice that the the negation of the conditional ~( p q)
is equivalent to the statement p  ~q.
p
T
T
F
F
q
T
F
T
F
~
F
T
F
F
(p
T
T
F
F

T
F
T
T
q)
T
F
T
F
p
T
T
F
F

F
T
F
F
~
F
T
F
T
q
T
F
T
F
Since the
conditional can
be interpreted as
implication, this
equivalence can
be interpreted as
follows. The
claim that “p does
not imply q” has
the same logical
meaning as “p is
true and q is
false”.
For example, let p be the statement that “the number n is evenly divisible by 2”
and let q be the statement that “ the number n is evenly divisible by 4”. Now, p
does not imply q since the number 6 is divisible by 2 ( so p is true) and 6 is not
divisible by 4 (so q is false).
Calculating Truth Tables
This says that: if p
implies q and p is
true then q has to be
true also.
We also get the following tautology.
p
T
T
F
F
q
T
F
T
F
((p  q)  p)  q
((p  q)  p) 
T T T T T T
T F F F T T
F T T F F T
F T F F F T
q
T
F
T
F
Most of
mathematics and
much of Artificial
Intelligence (AI) is
founded on this
tautology.
Recall:
All men are mortal.
Socrates is a man.
Socrates is mortal.
Assumptions.
Rule of logic.
Modus ponens
Conclusion.
But where do the rules of logic
come from?
The argument would go like this: “All men are mortal” can be express as “For all x,
if x is a man then x is mortal”. Specializing (another logical rule) x to Socrates, we
have “If Socrates is a man then Socrates is mortal”. The first line becomes
“Socrates is a man”  “Socrates is mortal” . So this tautology is the basis of the
logical rule modus ponens.
Conditional
The conditional statement is the basic form of deductive reasoning. It
has a direction, from antecedent to consequent. Since it is so important,
the conditional has many synonyms.
Synonyms for pq.
If p, then q.
p is a sufficient condition for q.
If p, q.
q is a necessary condition for p.
p implies q.
All p’s are q’s.
p only if q.
q if p.
Relative Forms
Direct
Converse
p
q
pq
p
q
qp
T
T
T
T
T
T
T
F
F
T
F
T
F
T
T
F
T
F
F
F
T
F
F
T
Inverse
Contrapositive
p
q
~p  ~q
p
q
~q  ~p
T
T
T
T
T
T
T
F
T
T
F
F
F
T
F
F
T
T
F
F
T
F
F
T
Note that this is not the negation of the direct
statement.
Note that the
direct and
contrapositive
statements are
equivalent as are
the converse and
the inverse.
Relative Forms
Let p be the statement “you build it” and let q be the statement
“they will come”.
Direct Statement: p  q, “If you build it, then they will come.”
Converse : q  p, “If they do come, then you did build it.”
Inverse : ~p  ~q, “If you do not build it, then they will not come.”
Contrapositive: ~q  ~p, “If they do not come, then you did not build it.”
Biconditional
Consider the truth table for the conjunction of a conditional with its converse.
p
q
(p  q)

(q  p)
T
T
T
T
T
T
F
F
F
T
F
T
T
F
F
F
F
T
T
T
Biconditional
p
q
pq
T
T
T
T
F
F
F
T
F
F
F
T
This statement claims that it is
true both that p implies q and
conversely that q implies p.
This relationship between p and
q is important enough to get its
own symbol called the
biconditional (conditional in
both directions).
In words, p  q means “p is true if and only if q is
true.” The statement p  q is true precisely when
p and q have the same truth values. If p and q
are equivalent statements then p  q is a
tautology.
Biconditional
Consider the following example.
p q ~ (p  q)  (p  ~ q)
T
T
F
F
T
F
T
F
F
T
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
F
T
This statement is a tautology because the two terms of the
biconditional are equivalent (have the same true table).
It is true that “a natural number is even if and only if it is divisible by 2.”
It is false that “a natural number is even if and only if it is divisible by 4.”
Assignments 3.5, 3.6, 4.1, 4.2, 4.3
Read Section 3.5, 3.6
Due February 20
Exercises p. 145
1-23 odd, 27,29,47
Test 1 over Chapters 1, 2, 3
Thursday, February 22
Read 4.1, 4.2, 4.3
Due February 27
Exercises p. 176
1-4, 5,11,19, 23, 35, 47