Transcript Document

Formal Logic
Mathematical Structures
for Computer Science
Chapter 1
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Formal
Predicate Logic




Similar to propositional logic for solving arguments, build from
quantifiers, predicates and logical connectives.
A valid argument for predicate logic need not be a tautology.
The meaning and the structure of the quantifiers and predicates
determines the interpretation and the validity of the arguments
Basic approach to prove arguments:



Strip of quantifiers
Manipulate the unquantified wffs
Reinsert the quantifiers
Four new inference rules
Two rules to strip the qualifiers

Section 1.4
Two rules to reinsert the qualifiers
Note to remember: P(x) could be (y) (z) Q(x,y,z)
Predicate Logic
1
Inference Rules
From
Can Derive
Name /
Abbreviation
Restrictions on Use
(x)P(x)
P(t) where t is a
variable or constant
symbol
Universal
Instantiation- ui
If t is a variable, it must
not fall within the scope
of a quantifier for t
(x)P(x)
P(t) where t is a
variable or constant
symbol not previously
used in a proof
sequence
Existential
Instantiation- ei
Must be the first rule
used that introduces t
P(x)
(x)P(x)
Universal
Generalization- ug
P(x) has not been
deduced from any
hypotheses in which x is
a free variable nor has
P(x) been deduced by ei
from any wff in which x
is a free variable
P(x) or P(a)
(x)P(x)
Existential
Generalization- eg
To go from P(a) to
(x)P(x), x must not
appear in P(a)
Section 1.4
Predicate Logic
2
Examples: Proofs using Predicate Logic

Prove the following argument:






The argument is (x)[P(x)  Q(x)] Λ P(a)  Q(a)
The proof sequence is as follows:
1.
2.
3.
4.
Section 1.4
All flowers are plants. Sunflower is a flower. Therefore,
sunflower is a plant.
P(x) is “ x is a plant”
a is a constant symbol (Sunflower)
Q(x) is “x is a flower”
(x)[P(x)  Q(x)]
P(a)
P(a)  Q(a)
Q(a)
hyp
hyp
1, ui
2, 3, mp
Predicate Logic
3
Examples: Proofs using Predicate Logic


Prove the argument (x)[P(x)  Q(x)] Λ [Q(y)]  [P(y)]
Proof sequence:
1.
2.
3.
4.


hyp
hyp
1, ui
2, 3, mt
Prove the argument (x)P(x)  (x)P(x)
Proof sequence:
1.
2.
3.
Section 1.4
(x)[P(x)  Q(x)]
[Q(y)]
P(y)  Q(y)
[P(y)]
(x)P(x)
P(x)
(x)P(x)
hyp
1, ui
2, eg
Predicate Logic
4
Examples: Proofs using Predicate Logic


Prove the argument (x)[P(x)  Q(x)] Λ (x)P(x)  (x)Q(x)
Proof sequence:
1.
2.
3.
4.
5.
6.

Section 1.4
(x)[P(x)  Q(x)]
hyp
(x)P(x)
hyp
P(x)  Q(x)
1, ui
P(x)
2, ui : no restriction on ui about reusing a name
Q(x)
3, 4, mp
(x)Q(x)
5, ug
Note: step 6 is legitimate since x is not a free variable in any
hypothesis nor was ei used before
Predicate Logic
5
Examples: Proofs using Predicate Logic


Prove the argument
(x)[P(x) Λ Q(x)]  (x)P(x) Λ (x)Q(x)
Proof sequence:
1.
2.
3.
4.
5.
6.
7.
Section 1.4
(x)[P(x) Λ Q(x)]
P(x) Λ Q(x)
P(x)
Q(x)
(x)P(x)
(x)Q(x)
(x)P(x) Λ (x)Q(x)
hyp
1, ui
2, sim
2, sim
3, ug
4, ug
5, 6, con
Predicate Logic
6
Examples: Proofs using Predicate Logic



Prove the argument
(y)[P(x)  Q(x,y)]  [P(x)  (y)Q(x,y)]
Using the deduction method, we can derive
(y)[P(x)  Q(x,y)] Λ P(x)  (y)Q(x,y)
Proof sequence:
1.
2.
3.
4.
5.
Section 1.4
(y)[P(x)  Q(x,y)]
P(x)
P(x)  Q(x,y)
Q(x,y)
(y)Q(x,y)
hyp
hyp
1, ui
2, 3, mp
4, ug
Predicate Logic
7
Temporary hypotheses



A temporary hypothesis can be inserted into a proof sequence.
If T is inserted as a temporary hypothesis and eventually W is
deduced from T and other hypotheses, then the wff T  W has
been deduced from other hypotheses and can be reinserted into
the proof sequence
Prove the argument
[P(x)  (y)Q(x,y)]  (y)[P(x)  Q(x,y)]
Proof sequence:
1.
2.
3.
4.
5.
6.
Section 1.4
P(x)  (y)Q(x,y)hyp
P(x)
(y)Q(x,y)
Q(x,y)
P(x)  Q(x,y)
(y)[P(x)  Q(x,y)]
temporary hypothesis
1, 2, mp
3, ui
temp. hyp discharged
5, ug
Predicate Logic
8
More Examples

Prove the sequence [(x)A(x)]  (x)[A(x)]


Proof sequence for [(x)A(x)]  (x)[A(x)]
1.
2.
3.
4.
5.
6.

[(x)A(x)]
A(x)
(x)A(x)
A(x)  (x)A(x)
[A(x)]
(x)[A(x)]
hyp
temp. hyp
2, eg
temp. hyp discharged
1, 4, mt
5, ug
Proof sequence for (x)[A(x)]  [(x)A(x)]
1.
2.
3.
4.
5.
6.
7.
8.
Section 1.4
To prove equivalence, implication in each direction should be proved
(x)[A(x)]
(x)A(x)
A(a)
[A(a)]
[(x)[A(x)]]
(x)A(x)  [(x)[A(x)]]
[((x)[A(x)])]
[(x)A(x)]
hyp
temp. hyp
2, ei
1, ui
3, 4, inc
temp. discharged
1, dn
6, 7, mt
Predicate Logic
9
Proving Verbal arguments

Every crocodile is bigger than every alligator. Sam is a crocodile. But
there is a snake, and Sam isn’t bigger than that snake. Therefore,
something is not an alligator.


Use C(x): x is a crocodile; A(x): x is an alligator, B(x,y): x is bigger than y,
s is a constant (Sam), S(x): x is a Snake
Hence prove argument
(x) (y)[C(x) Λ A(y)  B(x,y)] Λ C(s) Λ (x)(S(x) Λ [B(s,x)])  (x)[A(x)]
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Section 1.4
(x) (y)[C(x) Λ A(x)  B(x,y)]
C(s)
(x)(S(x) Λ [B(s,x)])
(y)[C(s) Λ A(y)  B(s,y)]
S(a) Λ [B(s,a)])
C(s) Λ A(a)  B(s,a)
[B(s,a)]
[C(s) Λ A(a)]
[C(s)] V [A(a)]
[[C(s)]]
[A(a)]
(x)[A(x)]
Predicate Logic
hyp
hyp
hyp
1, ui
3, ei
4, ui
5, sim
6, 7, mt
9, De Morgan
2, dn
9, 10, ds
11, eg
10
Class Exercise

Prove the argument
(x)[(B(x) V C(x))  A(x)]  (x)[B(x)  A(x)]
Proof sequence:
1.
2.
3.
4.
5.
6.
7.
Section 1.4
(x)[(B(x) V C(x))  A(x)]
(B(x) V C(x))  A(x)
B(x)
B(x) V C(x)
A(x)
B(x)  A(x)
(x)[B(x)  A(x)]
hyp
1, ui
temp. hyp
3, add
2, 4, mp
temp. hyp discharged
6, ug
Predicate Logic
11
Class exercise


Every ambassador speaks only to diplomats, and some ambassadors speak
to someone. Therefore, there is a diplomat.
Use A(x): x is an ambassador; S(x,y): x speaks to y; D(x): x is a diplomat
Prove the argument
(x) (y)[(A(x) Λ S(x,y))  D(y)] Λ (x)(y)(A(x) Λ S(x,y))  (x)D(x)
Proof Sequence:
1.
(x) (y)[(A(x) Λ S(x,y))  D(y)]
2.
(x)(y)(A(x) Λ S(x,y))
3.
(y)((A(a) Λ S(a,y))  D(y))
4.
(y)(A(a) Λ S(a,y))
5.
A(a) Λ S(a,b)
6.
(A(a) Λ S(a,b))  D(b)
7.
D(b)
8.
(x)D(x)
Section 1.4
Predicate Logic
hyp
hyp
1, ui
2, ei
4, ei
3, ui
5, 6, mp
7, eg
12