Propositional Logic
Class notes
Proof Techniques
Document also available in PDF, Postscript, DVI, Text, LaTeX, LyX.
Chapter 1 Predicate Logic (sections 1.3, 1.4)
1.1 Introduction
Exemple 1
``Every man has a brain; Socrate is a man; therefore Socrate has
a brain.''
Is propositional logic expressive enough for this sentence ?
What is missing ?
1.1.1 Quantifiers, Predicates, Validity
Exemple 2
``Every man has a brain''
``For all man, this man has a brain''
New features: constants / variables / quantifier / predicates
Définition 1
Quantifiers:

For all
 For every
 There exists
 For at least one
 For each
 For any
 For some
Universal quantifier
: (for all x)
Existential quantifier
: (there exists
x)
Always place the quantifiers inside ( ).
1.1.2 Predicates:
Définition 2
Predicate: a statement that describes a property of a variable
Exemple 3
P(x) : x has a brain
``For all man, this man has a brain''
Translates into (for allx ) P(x)
As in propositional logic, we can build well formed formulas
from predicates and logic connectives.
Exemple 4
(for allx ) B(x)> R(x)': if x is blue, then x is not red.
1.1.3 Domain of interpretation:
If x is a car, the sentence above (for allx ) P(x) is false.
The truth of the sentence depends on where you take x from!
Définition 3
Domain of interpretation:
The collection of objects from which x may be selected
Exemple 5
(for allx ) (x>0)
DOI: all integers
DOI: all integers > 10
DOI: all humans
Exemple 6
For any thing, if it's a man then it has a brain
P(x): x is a man
Q(x): x has a brain
(for allx ) P(x)> Q(x)
Exercice 1
Write a formula for the following sentence:
``There exists a man which is called Socrate''
1.1.4 NAry predicates:
Définition 4
Binary predicate: predicate which takes two variables
NAry predicate : predicate which takes several variables

P(x,y)=x>y (DOI: integers)
 P(Q,B): Q is the author of the book B (DOI: all authors /
books)
 Everyone has exactly one best friend:
B(X,Y): Y is the best friend of X
(for allx ) (there existsy ) B(X,Y)/\[ (for all Z) B(X,Z)>(Z=Y) ]
For any person X, there exists a person Y, such that:

Y is the best friend of X
 For any person Z, if Z is the best friend of X, then Z
is actually Y.
1.1.5 Truth value
Can we define the Truth table of a wff ?
Problem 1
The domain of interpretation may be infinite.
To assess the truth value, we need to know:

What is the domain of interpretation.
 What property of elements of the DOI does P(x) represent.
 An assignment for each constant.
Définition 5
This is called an interpretation.
Exemple 7
[, Exercise 1 p. 41]
What is the truth value of the following wffs for this interpretation:
DOI: integers; O(x): x is odd; L(x): x<10; G(x): x>9

(there existsx ) O(x)
There exists an odd number
 (for allx ) [L(x)> O(x)]
For any integer x, if x is strictly lower than 10, then x is odd;
Any integer strictly lower than 10 is odd;
 (there existsx ) [L(x)/\ G(x)]
There exists an integer x such that x is strictly lower than 10 and
x is strictly larger than 9
 (for allx ) [L(x)\/ G(x)]
For any integer, either x is strictly lower than 10 or x is strictly
bigger that 9
Exercice 2
[, Exercise 3 p. 41]
Are the following wffs true for this interpretation:
DOI: states of the US.
Q(x,y): x is north of y; P(x): x starts with the letter
M; a is "Mississippi".

(for allx ) P(x)
 (for allx ) (for ally ) (for allz ) [ (Q(x,y)/\ Q(y,z)) > Q(x,z) ]
 (there existsy ) (there existsx ) Q(x,y)
 (for allx ) (there existsy ) [P(y)/\ Q(x,y)]
For any state x, there exists a state y such that y starts
with M and x is north of y.
 (there existsy ) Q(a,y)
Exercice 3
Translate the following sentences into wffs, with:
DOI: world; D(x): x is a day; S(x): x is sunny; R(x): x is
rainy;
M is "Monday"; T is "Tuesday".

All days are sunny:
 Some days are not rainy:
 Every day that is sunny is not rainy:
 Some days are sunny and rainy:
 No day is both sunny and rainy:
 It is always a sunny day only if it is a rainy day:
 No day is sunny:
 Monday was sunny; therefore every day will be sunny:
 It rained both Monday and Tuesday:
 If some day is rainy, then every day will be sunny:
1.1.6 Dummy variables / free variables:
Définition 6
A dummy variable is a variable which is linked to a quantifier.
The name of the variable is irrelevant.
Same thing as a local variable in a program.
Exemple 8
(there existsx ) Q(x) is the same wff as (there existsz ) Q(z)
(there existsx ) (for ally ) Q(x,y) is the same wff as (there existsz ) (for allt ) Q(z,t) or (there existsy ) (for allx ) Q(y,x)
Définition 7
A variable is free if it is not linked to a quantifier.
Same thing as a global variable in a program.
Résumé 2
Where are we?

We can build all the wff of predicate logic.
 Given a wff P, and an interpretation, we can decide the truth value
of P.
Définition 8
Argument: P_{1}/\ P_{2}/\···/\ P_{k} > Q

In propositional logic, an argument is valid if it's a tautology.
I.e. if it's true whatever truth value are assigned to each basic
proposition.
 In predicate logic, an argument is valid if it's intrinsically
true.
I.e. if it's true for ANY interpretation.
Exercice 4
[, Exercise 16 p. 35]
Give interpretations to prove that the following wffs are not valid:

(there existsx ) A(x)/\(there existsx ) B(x) > (there existsx ) [ A(x)/\ B(x) ]
 (for allx ) (there existsy ) P(x,y) > (there existsx ) (for ally ) P(x,y)
 (for allx ) [P(x)> Q(x)] > (for allx ) [P(x)\/ Q(x)]
 (for allx ) [ A(x)' ] <> [(for allx ) A(x) ]'
1.2 Predicate logic
There is an infinity of interpretations, so there is no algorithm
to check the validity of a predicate.
We will have to use REASON:

Reuse the rules from propositional logic
 Accept a few basic new rules as intuitively valid
 Use formal logic with those rules to prove arguments
1.2.1 Universal instantiation:
Exemple 9
We want to be able to prove the following argument:
Every human is mortal; Socrate is a man; Therefore Socrate is mortal.
H(x): x is a human; M(x): x is a mortal; s: Socrate
(for allx ) [H(x) > M(x)]/\ H(s) > M(s)
Définition 9
Rule of universal instantiation (ui):
From: (for allx ) P(x)
Can derive: P(s)
Note: s can be any constant.
We decide that this rule is valid, because it is intuitively
valid.
Proof sequence for: (for allx ) [H(x)> M(x)]/\ H(s) > M(s)

1. 
(for allx ) [H(x)> M(x)] 
(hyp) 
2. 
H(s) 
(hyp) 
3. 
H(s)> M(s) 
(ui 1) 
4. 
M(s) 
(mp 2, 3) 

Exercice 5
Prove (for allx ) [ P(x)> R(x) ]/\[ R(y)' ] > [ P(y)' ]
1.2.2 Universal generalization:
Exemple 10
``Every human is a living being. Every living being is mortal.Therefore
every human is mortal.''
H(x): is a human
L(x): is a living being
M(x) is mortal
(for allx ) [H(x)> L(x)] /\ (for allx ) [L(x)> M(x)] > (for allx ) [H(x)> M(x)]
This is clearly something we want to be able to prove, but we cannot
use hypothetical syllogism directly!
Définition 10
Rule of universal generalization (ug)
From: P(s)
Can derive: (for allx ) P(x)
s must be an arbitrary element of the domain.
Exemple 11
(for allx ) [H(x)> L(x)] /\ (for allx ) [L(x)> M(x)] > (for allx ) [H(x)> M(x)]

1. 
(for allx ) H(x)> L(x) 
(hyp) 
2. 
(for allx ) L(x)> M(x) 
(hyp) 
3. 
H(s)> M(s) 
(ui 1) 
4. 
L(s)> M(s) 
(ui 2) 
5. 
H(s)> M(s) 
(hs 3,4) 
6. 
(for allx ) [H(x)> M(x)] 
(ug 5) 

Exemple 12
s: Socrate; H(x): x is a man; M(x): x is mortal:

1. 
M(s) 
(hyp) 
2. 
H(s)'\/ M(s) 
(add 1) 
3. 
H(s)> M(s) 
(imp 2) 
4. 
(for allx ) [H(x)> M(x)] 
(ug 3) 

Socrate is a mortal, therefore every man is a mortal.
This proof sequence is incorrect: you cannot apply ug at step 4.
Indeed s is Socrate, and not an arbitrary element of the domain.
Exercice 6
Prove the following arguments:

(for allx ) [P(x)/\ Q(x)] > (for allx ) P(x)/\(for allx ) Q(x)
 (for allx ) P(x)/\(for allx ) Q(x) > (for allx ) (P(x)/\ Q(x))
 (for allx ) [P(x)/\(for ally ) Q(x,y)] > (for allx ) (for ally ) Q(x,y)
1.2.3 Existential instantiation:
Exemple 13
DOI: contents of the fridge.
There exists a fruit; therefore, I can take a fruit.
F(x): x is a fruit
(there existsx ) F(x) > F(s)
Définition 11
Rule of existential instantiation (ei):
From: (there existsx ) P(x)
Can derive: P(s)
s must be a newly created variable
Exemple 14
(for allx ) [P(x)> Q(x)] /\(there existsy ) P(y) > Q(s)

1. 
(for allx ) [P(x)> Q(x)] 
(hyp) 
2. 
(there existsy ) P(y) 
(hyp) 
3. 
P(s) 
(ei 2) 
4. 
P(s)> Q(s) 
(ui 1) 
5. 
Q(s) 
(mp 3,4) 

1.2.4 Existential generalization:
Exemple 15
DOI: contents of the fridge
I see a fruit, therefore there exists a fruit.
F(s) > (there existsx ) F(x)
Définition 12
Rule of existential generalization (eg)
From: F(s)
Can derive:(there existsx ) F(x)
Exemple 16
(for allx ) [P(x)> Q(x)] /\ (there existsy ) P(y) > (there existsy ) Q(y)

1. 
(for allx ) [P(x)> Q(x)] 
(hyp) 
2. 
(there existsy ) P(y) 
(hyp) 
3. 
P(s) 
(ei 2) 
4. 
P(s)> Q(s) 
(ui 1) 
5. 
Q(s) 
(mp 3,4) 
6. 
(there existsy ) Q(y) 
(eg 5) 

Exemple 17
(there existsx ) P(x)/\(there existsx ) Q(x) > (there existsx ) [P(x)/\ Q(x)]

1. 
(there existsx ) P(x) 
(hyp) 
2. 
(there existsx ) Q(x) 
(hyp) 
3. 
P(s) 
(ei 1) 
4. 
Q(s) 
(ei 2) 
5. 
P(s)/\ Q(s) 
(add 3,4) 
6. 
(there existsx ) [P(x)/\ Q(x)] 
(eg 5) 

We have seen that the previous argument is incorrect:
So, where is the flaw in the following proof ?
For example, s cannot have been created by existential instantiation
Exercice 7
Prove or disprove the following arguments

(there existsx ) (for ally ) Q(x,y) > (for ally ) (there existsx ) Q(x,y)
 (for allx ) (there existsy ) Q(x,y) > (there existsy ) (for allx ) Q(x,y)
1.2.5 Deduction Method and Temporary Hypothesis:
Exemple 18
P(s)>(for ally ) Q(x,y) > (for ally ) [P(s)> Q(x,y)]
1.3 Conclusion
Goal: formalization of arguments and proofs.

Propositional logic:

propositions A, B, ...
connectives, well formed formula
truth table
argument valid iff wff is a tautology
proofs:

compute the truth table (algorithm)
 formal logic, deduction rules
Ex 24, 37
 Predicate logic

variables, predicates
domain of interpretation
connectives, wff
interpretation
truth table: all possible interpretations (infinite)
argument valid iff wff is true for all possible interpretations
proofs:

no algorithm
 formal logic, deduction rules
Those two logic are correct and complete.
They are still not powerful enough to represent all real life argument.
For this we would need of more powerful logics (2nd order), that allows
for quantifying other sets.
Problem: it's often difficult, if not impossible to prove that those
logics are complete and correct!
We won't need to go into those details.
We have seen enough lowlevel logic to help us write safely less formal
proofs.
Propositional Logic
Class notes
Proof Techniques
Predicate Logic /
CSM MACS358 /
Nicolas M. Thiéry
Last modified: Fri Jan 19 13:12:15 2007