Transcript Introduction

Logic and Proofs
Foundations
Outlines
• Propositional logic
– Propositions and logical operators
– Propositional equivalence
• Predicate logic
– Predicates and quantifiers
– Rules of Inference
• Basic Proofs
Jul-15
Logic and Proofs
2
Propositional Logic
• Proposition
• Truth values
• Examples
Jul-15
Logic and Proofs
3
Propositions
• A proposition is a statement which is either
true or false.
• Examples of propositions
– The sun rises in the east.
– Our king is 80 years old.
• Examples of non-propositions
– What is your name?
– Pour some water into the cup.
Jul-15
Logic and Proofs
4
Truth Values
• TRUE, T, or 1
• FALSE, F, or 0
• A proposition can be:
– TRUE
– FALSE
• A proposition cannot be:
– both TRUE and FALSE
– neither TRUE nor FALSE
Jul-15
Logic and Proofs
5
Logical (or Boolean) Operators
• Unary operators
– Negation (not), denoted by ¬.
• Binary operators
– Conjunction (and), denoted by &, , .
– Disjunction (or), denoted by +, .
– Implication (if-then), denoted by .
– Equivlence (iff), denoted by .
Jul-15
Logic and Proofs
6
Truth Tables
• Given propositional variables, we can create a logical
expression from the propositional variables and
logical operators.
Jul-15
P
T
Q
T
¬Q
F
P&Q
T
P+Q
T
PQ
T
PQ
T
T
F
T
F
T
F
F
F
T
F
F
T
T
F
F
F
T
F
F
T
T
Logic and Proofs
7
Negation
• Let P be the proposition:
– I am speaking English.
• The negation of P, denoted by ¬P, is the
proposition:
– I am not speaking English.
– It is not the case that I am speaking English.
Jul-15
Logic and Proofs
8
Conjuction
• AND
• Let P be the proposition I am writing in English.
• Let Q be the proposition I am speaking English.
• The conjunction of P and Q, denoted by P&Q
or PQ, is the proposition:
– I am writing in English and speaking English.
Jul-15
Logic and Proofs
9
Disjunction
• OR
• Let P be the proposition I am speaking Thai.
• Let Q be the proposition I am speaking English.
• The disjunction of P and Q, denoted by P+Q
or PQ, is the proposition:
– I am speaking English or Thai.
Jul-15
Logic and Proofs
10
Implication
• IF-THEN
• Let P be the proposition I am writing in English.
• Let Q be the proposition I am speaking English.
• PQ (if P then Q, P implies Q, Q only if P,
Q whenever P, P is a sufficient condition of Q,
Q is a necessary condition of Q):
– If I am writing in English, I am speaking English.
– I am speaking English whenever I am writing in
English.
Jul-15
Logic and Proofs
11
Terminology
• Given the proposition PQ.
• P is called a premise, hypothesis or
antecedent.
• Q is called a conclusion or consequence.
• QP is the CONVERSE of PQ.
• ¬Q  ¬P is the CONTRAPOSITIVE of PQ.
Jul-15
Logic and Proofs
12
Examples
• R: Raining tomorrow is a sufficient condition
for my not going to town.
• Assign propositional variables to component
propositions
– P: It will rain tomorrow
Q: I will not go to town
• Symbolize the assertion R: PQ
• Symbolize the converse QP
• Convert the symbols back into words
Jul-15
– If I don’t go to town then it will rain tomorrow.
– Raining tomorrow is a necessary condition for my
not going to town. Logic and Proofs
13
Biconditional
• IF AND ONLY IF, IFF
• Let P be the proposition I am writing in English.
• Let Q be the proposition I am speaking English.
• The conjunction of P and Q, denoted by
PQ, is the proposition:
– I am writing in English if and only if I am speaking
English.
Jul-15
Logic and Proofs
14
Exclusive OR
• Either … or …
• Let P be the proposition I am speaking Thai.
• Let Q be the proposition I am speaking English.
• The exclusive-or of P and Q, denoted by
PQ, is the proposition:
– I am speaking either Thai or English.
Jul-15
Logic and Proofs
15
Terminology
• Tautology = proposition which is always true.
– Classic Example: P¬P
• Contradiction = proposition which is always false.
– Classic Example: P¬P
• A contingency is a proposition which neither a
tautology nor a contradiction.
– Example: (PQ)¬R
• Two propositions P and Q are logically equivalent if
PQ is a tautology.
– We write PQ
• Example: (PQ)(QP)(PQ)
Jul-15
Logic and Proofs
16
Propositional Equivalence
Identity
• P T P
• P F P
Domination
• P T T
• P F F
Idempotency
• P P P
• P P P
De Morgan’s
• (P Q) P Q
• (P Q) P Q
Jul-15
Double negation
• (P)) P
Commutativity
• P Q QP
• P Q QP
Associativity
• (P Q)R P(QR)
• (P Q) R P (QR)
Distributivity
• P (QR) (P Q)(P R)
• P (QR) (P Q)(P R)
Logic and Proofs
17
Propositional Equivalence
Implication
• PQP Q
Absurdity
• ( PQ) (PQ) P
Tautology
• P PT
Contradiction
• P PF
Equivalence
• P T P
• P F P
• (PQ) (QP) (PQ)
Contrapositive
• (PQ)(QP)
Jul-15
Absorption
• P (P Q)P
• P (P Q)P
Exportation
• (P Q)R P(QR)
Logic and Proofs
18
Canonical or Normal Forms
• Literals
– Propositions or negation of propositions
• Disjunctive normal form
– Disjunction of conjunctions of literals
– (PQ ¬R)(¬PQ¬RS) (QR)(¬S)
• Conjunctive normal form
– Conjunction of disjunctions of literals
– (PQ¬R)(¬PQ¬RS)(QR)(¬S)
Jul-15
Logic and Proofs
19
Disjunctive Normal Form (DNF)
Finding DNF
• Complete the truth
table
• Find minterms for rows
with values 1
– Minterms = conjunctions
(and) of literals.
P
Q
R
Z
0
0
0
1 PQR
0
0
1
0
0
1
0
1 P QR
0
1
1
0
1
0
0
0
1
1
PQ R
0
1
P QR
1
0
• Or all minterms
1 0
(PQR) 
1 1
(P QR) 
1 1
( PQ  R) 
( P  QR) Logic and Proofs
Jul-15
20
Conjunctive Normal Form (CNF)
• Negation of DNF can be easily written in CNF
 ((PQR)  (P QR)  ( PQ  R)  ( P  QR))
= (PQR)(P QR)( PQ  R)  ( P QR)
= (P  Q  R)  (P  Q  R) (P  Q  R)  (P  Q  R)
• Finding CNF
– if you negate a DNF and use De Morgan’s Laws.
Jul-15
Logic and Proofs
21
Predicate Logic
Predicates
• Predicates or propositional functions
– propositions which contain variables
– generalization of propositions
• Predicates become propositions when
– every variable is bound by assigning it a value
from the Universe of Discourse U or
– quantifying every variable.
Jul-15
Logic and Proofs
23
Example
Let U = Z, the integers = {. . . -2, -1, 0 , 1, 2, 3, . . .}
• P(x): x>0 is a predicate.
– P(x) has no truth value until the variable x is bound.
– P(-3) and P(0) are false, and P(3) is true.
• The collection of integers for which P(x) is true are
the positive integers.
• P(y) P(0) is not a proposition because y has not
been bound.
• P(3)P(0) is a proposition which is true.
Jul-15
Logic and Proofs
24
Example
Let R be the three-variable predicate.
• R(x, y, z): x + y = z
Find the truth value of
– R(2, -1, 5)
– R(3, 4, 7)
– R(x, 3, z)
Jul-15
Logic and Proofs
25
Quantifiers
Existential quantifier
• P(x) is true for some x in the
universe of discourse.
• $xP(x) reads :
Universal quantifier
• P(x) is true for all x in the
universe of discourse.
• "xP(x) reads
– ‘For all x, P(x)’,
– ‘For every x, P(x)’
–
–
–
–
• U={1,2,3}
• "xP(x) P(1)P(2) P(3)
‘There is an x such that P(x),’
‘For some x, P(x)’,
‘For at least one x, P(x)’,
‘I can find an x such that P(x).’
• U={1,2,3}
• $xP(x) P(1)P(2) P(3)
• The variable x is bound by
the universal quantifier
producing a proposition.
Jul-15
Logic and Proofs
26
Unique existential quantifier
P(x) is true for one and • A predicate is not a
proposition until all
only one x in the
variables have been bound
universe of
either by quantification or
discourse.
assignment of a value.
• $!xP(x) reads
– ‘There is a unique x
such that P(x),’
– ‘There is one and only
one x such that P(x),’
– ‘One can find only one
x such that P(x).’
• .
Jul-15
Logic and Proofs
27
Some Equivalences
Involving the negation operator
• "xP(x) $xP(x)
• $x P(x) "xP(x)
Jul-15
Logic and Proofs
28
Some Terminologies
Valid
• An assertion involving predicates is valid if it
is true for every universe of discourse.
Satisfiable/Unsatisfiable
• An assertion involving predicates is satisfiable
if there is a universe and an interpretation for
which the assertion is true. Else it is
unsatisfiable.
Jul-15
Logic and Proofs
29
Properties of Quantifiers
• Distributivity
– "x [P(x)Q(x)]  "xP(x)  "x Q(x)
– "x [P(x)Q(x)]  "xP(x)  "xQ(x)
– "x [P(x)Q(x)]  "xP(x)  "x Q(x) is false.
• (why?)
Jul-15
Logic and Proofs
30
Properties of Quantifiers
• Commutativity
– "x "y P(x,y)  "y "x P(x,y)
– $x $y P(x,y)  $y $x P(x,y)
– $x "y P(x,y)  "y $x P(x,y) is false.
Jul-15
Logic and Proofs
31
Basic Proof
Proving a Theorem
Definition:
• A theorem is a valid logical assertion which
can be proves using
– Other theorems or lemmas
– Axioms
– Inference rules.
• Lemma = pre-theorem
• Corollary = post-theorem
Jul-15
Logic and Proofs
33
Inference Rules
• H1  H2  …  Hn  C , where
– H1, H2, …,Hn are hypotheses, and
– C is the conclusion.
• Symbolic form
H1
H2
…
Hn
C
Jul-15
Logic and Proofs
34
Inference Rules
• Modus ponens
P
PQ
Q
• Addition
P
PQ
• Simplication
PQ
P
• Conjunction
P
Q
PQ
Jul-15
• Modus Tollens
¬Q
PQ
P
• Hypothetical syllogism
PQ
QR
PR
• Disjunctive syllogism
PQ
¬P
Q
• Resolution
PQ
¬P  R
QR
Logic and Proofs
35
Example
F:
A:
M:
P:
Horses fly.
Cows eat artichokes.
The mosquito is the national bird.
Peanut butter tastes good on hot
dogs
Hypotheses
1. (F A)M
2. M P
3. P
Conclusion
A
Jul-15
Assertion
1.(F A)M
2.M P
3.(F A)P
4.P
5.(F A)
6.F A
7.A F
8.A
Logic and Proofs
Reasons
Hypothesis 1.
Hypothesis 2.
steps 1 and 2 and
hypothetical syll.
Hypothesis 3.
steps 3 and 4 and
modus tollens
step 5 and DeMorgan
step 6 and
commutativity of 'and'
step 7 and
simplification
Q. E. D.
36
Using Resolution in Prolog
• Prolog is a programming language.
• A statement in Prolog is an if-then rule.
• Running a prolog program = Asking if
something is true.
Jul-15
Logic and Proofs
37
Resolution: Example
PQR
(P  ¬Q  ¬R) R (Q  ¬S  ¬R) R
(P  ¬Q  ¬R)
(Q  ¬S)
QSR
S
(P  ¬Q)
(Q  ¬S  ¬R)
Q
S.
R.
P
Question: P?
Jul-15
Logic and Proofs
38
Inference Rules for Quantifiers
• Universal instantiation
"x P(x)
 P(c)
• Existential instantiation
$x P(x)
 P(c) for some element c
• Universal generalization
P(c) for an arbitrary c
 "x P(x)
• Existential generalization
P(c) for some element c
 $x P(x)
Jul-15
Logic and Proofs
39
Methods of Proof
• We wish to establish the truth of the 'theorem'
PQ
• P may be a conjunction of other hypotheses.
• PQ is a conjecture until a proof is produced.
Jul-15
Logic and Proofs
40
Trivial proof
• If we know Q is true then PQ is true.
Example:
• If it's raining today then the void set is a subset of
every set.
• The assertion is trivially true independent of
the truth of P.
Jul-15
Logic and Proofs
41
Vacuous proof
• If we know one of the hypotheses in P is false then
PQ is vacuously true.
Example:
• If I am both rich and poor then hurricane Fran was a
mild breeze.
• This is of the form
(P P)Q
• and the hypotheses form a contradiction.
• Hence Q follows from the hypotheses vacuously.
Jul-15
Logic and Proofs
42
Direct proof
• Assumes the hypotheses are true.
• Use the rules of inference, axioms and any
logical equivalences to establish the truth of
the conclusion.
Jul-15
Logic and Proofs
43
Example: Direct proof
Theorem: If 6x + 9y = 101, then x or y is not an
integer.
Proof: (Direct)
Let x and y be real numbers such that 6x + 9y = 101.
Then, 3(2x + 3y) = 101.
But 101/3 is not an integer.
2x or 3y is not an integer.
Therefore, x or y must not be an integer.
Q.E.D.
Jul-15
Logic and Proofs
44
Indirect proof
This is a direct proof of the contrapositive:
• Assume the conclusion of PQ is false (Q
is true)
• Use the rules of inference, axioms and any
logical equivalences to establish the premise
P is false.
– To show that a conjunction of hypotheses is false
is suffices to show just one of the hypotheses is
false.
Jul-15
Logic and Proofs
45
Example: Indirect proof
Definition: A perfect number is one which is the sum of all its
divisors except itself.
Example: 6 is perfect since 1 + 2 + 3 = 6. So is 28.
Theorem:
A perfect number is not a prime.
(If p is a perfect number, then p is a prime.)
Proof: (Indirect).
Let p be a prime number.
Then, 1 and p are only two divisors of p.
Hence the sum of the divisors less than p is 1 which is not
equal to p.
Hence p cannot be perfect.
Q. E. D.
Jul-15
Logic and Proofs
46
Proof by contradiction
reductio ad absurdum
• To prove Q, assume Q is false.
• Derive a contradiction, usually PP which
establishes Q  F.
• The contrapositive of this assertion is T  Q
from which it follows that Q must be true.
Jul-15
Logic and Proofs
47
Example: Proof by contradiction
Theorem: There is no largest prime number.
(Note that there are no formal hypotheses here.)
We assume the conclusion 'there is no largest prime number' is
false.
There is a largest prime number. Call it p.
Hence, the set of all primes lie between 1 and p.
Form the product of these primes:
r = 2•3•5•7•11•....•p.
But r + 1 is a prime larger than p. (Why?)
This contradicts the assumption that there is a largest prime.
Q.E.D.
Jul-15
Logic and Proofs
48
Proof by contradiction
reductio ad absurdum
Formal proof
P: there is no largest prime.
Q: p is the largest prime.
Assume P is true.
Then (for some p) Q is true.
So is P  Q.
We construct a prime > p.
So Q  Q.
By hypothetical syllogism, we get P  Q .
From two applications of modus ponens we conclude that Q
is true and Q is true so by conjunction QQ or a
contradiction is true.
Hence the assumption must be false and the theorem is true.
Jul-15
Logic and Proofs
49
Proof by Cases
• Break the premise of PQ into an equivalent disjunction
of the form P1 P2...Pn .
• Then use the tautology
[(P1 Q) (P2 Q) ...(Pn Q)] [(P1 P2 ... Pn )Q]
• Each of the implications Pi Q is a case.
• You must:
– convince the reader that the cases are inclusive, i.e., they
exhaust all possibilities
– establish all implications
Jul-15
Logic and Proofs
50
Proof by Cases
Let be the operation 'max' on
the set of integers:
Theorem: (Associativity)
For all a, b, c
(ab)c = a(bc).
Proof:
Let a, b, c be any arbitrary
integers.
Then one of the following cases
must hold:
1. a b c
2. a c b
3. b a c
4. b c a
5. c a b
6. c b a
Jul-15
Case 1: (ab)c=ac=a, and a(bc)=ab=a.
Hence, (ab)c = a(bc).
Case 2: (ab)c=ac=a, and a(bc)=ac=a.
Hence, (ab)c = a(bc).
Case 3: (ab)c=bc=b, and a(bc)=ab=b.
Hence, (ab)c = a(bc).
Case 4: (ab)c=bc=b, and a(bc)=ab=b.
Hence, (ab)c = a(bc).
Case 5: (ab)c=ac=c, and a(bc)=ac=c.
Hence, (ab)c = a(bc).
Case 6: (ab)c=bc=c, and a(bc)=ac=c.
Hence, (ab)c = a(bc).
Q. E. D.
Logic and Proofs
51