Propositional And First-Order Logic

1. 1
Propositional and
First-Order Logic

2. 2
Propositional Logic

3. 3
Propositional logic
•Proposition : A proposition is classified as a declarative
sentence which is either true or false.
eg: 1) It rained yesterday.
•Propositional symbols/variables: P, Q, S, ... (atomic
sentences)
•Sentences are combined by Connectives:
Ù ...and [conjunction]
Ú ...or [disjunction]
Þ...implies [implication / conditional]
Û..is equivalent [biconditional]
Ø ...not [negation]
•Literal: atomic sentence or negated atomic sentence

4. 5
Propositional logic (PL)
Sentence or well formed formula
•A sentence (well formed formula) is defined as follows:
–A symbol is a sentence
–If S is a sentence, then ØS is a sentence
–If S is a sentence, then (S) is a sentence
–If S and T are sentences, then (S Ú T), (S Ù T), (S ® T), and (S ↔ T) are
sentences
–A sentence results from a finite number of applications of the above rules

5. Laws of Algebra of Propositions
•Idempotent:
p V p ≡ p p Λ p ≡ p

•Commutative:
p V q ≡ q V pp Λ q ≡ q Λ p
•Complement:
p V ~p ≡ T p Λ ~p ≡ F
•Double Negation:
~(~p) ≡ p
7

6. •Associative:
p V (q V r) ≡ (p V q) V r
p Λ (q Λ r) ≡ (p Λ q) Λ r
•Distributive:
p V (q Λ r) ≡ (p V q) Λ (p V r)
p Λ (q V r) ≡ (p Λ q) V (p Λ r)
•Absorbtion:
p V (p Λ q) ≡ p
p Λ (p V q) ≡ p
•Identity:
p V T ≡ T p Λ T ≡ p
p V F ≡ p p Λ F ≡ F
8

7. 9
•De Morgan’s
~(p V q) ≡ ~p Λ ~q
~(p Λ q) ≡ ~p V ~q
•Equivalence of Contrapositive:
p → q ≡ ~q → ~p
•Others:
p → q ≡ ~p V q
p ↔ q ≡ (p → q) Λ (q → p)

8. L3
10
Tautologies and contradictions
•A tautology is a sentence that is True under all
interpretations.
•An contradiction is a sentence that is False under all
interpretations.
T
F
F
T
Øpp
T
T
p ÚØp
T
F
F
T
Øpp
F
F
p ÙØp

9. L3
11
Tautology by truth table
pq¬pp Úq¬p Ù(p Úq )[¬p Ù(p Úq )]®q
TTFT F T
TFFT F T
FTTT T T
FFTF F T

10. 12
11/09/12
Propositional Logic - one last proof
Show that [p Ù (p ® q)] ® q is a tautology.
We use º to show that [p Ù (p ® q)] ® q º T.
substitution for ®
[p Ù (p ® q)] ® q
º [(p Ù Øp) Ú (p Ù q)] ® q
º [p Ù (Øp Ú q)] ® q
º [ F Ú (p Ù q)] ® q
º (p Ù q) ® q
º Ø(p Ù q) Ú q
º (Øp Ú Øq) Ú q
º Øp Ú (Øq Ú q )
º Øp Ú T
º T
distributive
complement
identity
substitution for ®
DeMorgan’s
associative
identity
complement

11. L3
13
Logical Equivalence of
Conditional and Contrapositive
The easiest way to check for logical equivalence is to
see if the truth tables of both variants have
identical last columns:
T
F
T
T
T
F
T
F
T
T
F
F
p ®qqp
T
F
T
T
T
T
F
F
¬q®¬pp
F
F
T
T
¬p
T
F
T
F
q
F
T
F
T
¬q

12. L3
14
Table of Logical Equivalences
•Identity laws
Like adding 0
•Domination laws
Like multiplying by 0
•Idempotent laws
Delete redundancies
•Double negation
“I don’t like you, not”
•Commutativity
Like “x+y = y+x”
•Associativity
Like “(x+y)+z = y+(x+z)”
•Distributivity
Like “(x+y)z = xz+yz”
•De Morgan

13. L3
15
Table of Logical Equivalences
•Excluded middle
•Negating creates opposite
•Definition of implication in terms
of Not and Or

14. 16
Inference rules
•Logical inference is used to create new sentences that
logically follow from a given set of predicate calculus
sentences (KB).

15. 17
Sound rules of inference
•Here are some examples of sound rules of inference
–A rule is sound if its conclusion is true whenever the premise is true
•Each can be shown to be sound using a truth table
RULE PREMISE CONCLUSION
Modus Ponens A, A ® B B
And Introduction/Conjuction A, B A Ù B
And Elimination/SimplificationA Ù B A
Double Negation ØØA A
Unit Resolution A Ú B, ØB A
Resolution A Ú B, ØB Ú C A Ú C

16. 18
Soundness of modus ponens
A B A → B OK?
True True True
Ö
True False False
Ö
False True True
Ö
False False True
Ö

17. 19
Soundness of the
resolution inference rule

18. 20
Proving things
•A proof is a sequence of sentences, where each sentence is either a
premise or a sentence derived from earlier sentences in the proof
by one of the rules of inference.
•The last sentence is the theorem (also called goal or query) that
we want to prove.
•Example for the “weather problem” given above.
1 Hu Premise “It is humid”
2 Hu®Ho Premise “If it is humid, it is hot”
3 Ho Modus Ponens(1,2) “It is hot”
4 (HoÙHu)®RPremise “If it’s hot & humid, it’s raining”
5 HoÙHu And Introduction(1,3)“It is hot and humid”
6 R Modus Ponens(4,5) “It is raining”

19. 21
Problems with Propositional Logic

20. 22
Propositional logic is a weak language
•Hard to identify “individuals” (e.g., Mary, 3)
•Can’t directly talk about properties of individuals or
relations between individuals (e.g., “Bill is tall”)
•Generalizations, patterns, regularities can’t easily be
represented (e.g., “all triangles have 3 sides”)
•First-Order Logic (abbreviated FOL or FOPC) is expressive
enough to concisely represent this kind of information
FOL adds relations, variables, and quantifiers, e.g.,
•“Every elephant is gray”: " x (elephant(x) → gray(x))
•“There is a white alligator”: $ x (alligator(X) ^ white(X))

21. 23
First-Order Logic

22. 24
First-order logic
•First-order logic (FOL) models the world in terms of
–Objects, which are things with individual identities
–Properties of objects that distinguish them from other objects
–Relations that hold among sets of objects
–Functions, which are a subset of relations where there is only one
“value” for any given “input”
•Examples:
–Objects: Students, lectures, companies, cars ...
–Relations: Brother-of, bigger-than, outside, part-of, has-color,
occurs-after, owns, visits, precedes, ...
–Properties: blue, oval, even, large, ...
–Functions: father-of, best-friend, second-half, one-more-than ...

23. 25
User provides
•Constant symbols, which represent individuals in the world
–Mary
–3
–Green
•Function symbols, which map individuals to individuals
–father-of(Mary) = John
–color-of(Sky) = Blue
•Predicate symbols, which map individuals to truth values
–greater(5,3)
–green(Grass)
–color(Grass, Green)

24. 26
FOL Provides
•Variable symbols
–E.g., x, y, foo
•Connectives
–Same as in PL: not (Ø), and (Ù), or (Ú), implies (®), if
and only if (biconditional «)
•Quantifiers
–Universal "x or (Ax)
–Existential $x or (Ex)

25. 27
Quantifiers
•Universal quantification
–("x)P(x) means that P holds for all values of x in the
domain associated with that variable
–E.g., ("x) dolphin(x) ® mammal(x)
•Existential quantification
–($ x)P(x) means that P holds for some value of x in the
domain associated with that variable
–E.g., ($ x) mammal(x) Ù lays-eggs(x)
–Permits one to make a statement about some object
without naming it

26. 28
Quantifiers
•Universal quantifiers are often used with “implies” to form “rules”:
("x) student(x) ® smart(x) means “All students are smart”
•Universal quantification is rarely used to make blanket statements
about every individual in the world:
("x)student(x)Ùsmart(x) means “Everyone in the world is a student and is smart”
•Existential quantifiers are usually used with “and” to specify a list of
properties about an individual:
($x) student(x) Ù smart(x) means “There is a student who is smart”
•A common mistake is to represent this English sentence as the FOL
sentence:
($x) student(x) ® smart(x)
–But what happens when there is a person who is not a student?

27. 29
Quantifier Scope
•Switching the order of universal quantifiers does not change
the meaning:
–("x)("y)P(x,y) ↔ ("y)("x) P(x,y)
•Similarly, you can switch the order of existential
quantifiers:
–($x)($y)P(x,y) ↔ ($y)($x) P(x,y)
•Switching the order of universals and existentials does
change meaning:
–Everyone likes someone: ("x)($y) likes(x,y)
–Someone is liked by everyone: ($y)("x) likes(x,y)

28. 30
Connections between All and Exists
We can relate sentences involving " and $
using De Morgan’s laws:
("x) ØP(x) ↔ Ø($x) P(x)
Ø("x) P ↔ ($x) ØP(x)
("x) P(x) ↔ Ø ($x) ØP(x)
($x) P(x) ↔ Ø("x) ØP(x)

29. 31
Quantified inference rules
•Universal instantiation
d"x P(x) \ P(A)
•Universal generalization
–P(A) Ù P(B) … \ "x P(x)
•Existential instantiation
d$x P(x) \P(F)
•Existential generalization
–P(A) \ $x P(x)

30. 32
Universal instantiation
(a.k.a. universal elimination)
•If ("x) P(x) is true, then P(C) is true, where C is any
constant in the domain of x
•Example:
("x) eats(Ziggy, x) Þ eats(Ziggy, IceCream)

31. 33
Translating English to FOL
Every gardener likes the sun.
"x gardener(x) ® likes(x,Sun)
You can fool some of the people all of the time.
$x "t person(x) Ùtime(t) ® can-fool(x,t)
You can fool all of the people some of the time.
"x $t (person(x) ® time(t) Ùcan-fool(x,t))
"x (person(x) ® $t (time(t) Ùcan-fool(x,t))
All purple mushrooms are poisonous.
"x (mushroom(x) Ù purple(x)) ® poisonous(x)
No purple mushroom is poisonous.
Ø$x purple(x) Ù mushroom(x) Ù poisonous(x)
"x (mushroom(x) Ù purple(x)) ® Øpoisonous(x)
Clinton is not tall.
Øtall(Clinton)
Equivalent
Equivalent

32. 34