Proposition Calculus

Rules of Inference
Predicate Calculus

PROPOSITIONAL AND PREDICATE CALCULUS

October 21, 2020

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

1 Proposition Calculus

2 Rules of Inference

3 Predicate Calculus

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Proposition Calculus

A declarative sentence that is either true or false is called

”PROPOSITION”
Example
It rained yesterday.

”True” or ”False” are called the truth vales of the proposition and are
denoted by T and F respectively.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

A proposition that is true under all circumstances is called ”Tautology”

Example
15 is divisible by 3.

A proposition that is false under all circumstances is called

”Contradiction”

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

A proposition that is true under all circumstances is called ”Tautology”

Example
15 is divisible by 3.

A proposition that is false under all circumstances is called

”Contradiction”
Example
-3 is a natural number.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Two or more propositions can be combined using words like ”and, ”or”,
”iff”, ”if, then” etc. These are called Logical Connectivities.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Two or more propositions can be combined using words like ”and, ”or”,
”iff”, ”if, then” etc. These are called Logical Connectivities.

Definition
A proposition having one or more logical connectivities is called a
Compound Proposition. Otherwise is called Simple/ Atom

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Two propositions p and q are said to be Equivalent if when p is T, q is
also T and when p is F, q is also F and conversely.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Two propositions p and q are said to be Equivalent if when p is T, q is
also T and when p is F, q is also F and conversely.

Example
p: He was born in 1934
q: He’ll be 60 years old in 1994
p and q are equivalent

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Two propositions p and q are said to be Equivalent if when p is T, q is
also T and when p is F, q is also F and conversely.

Example
p: He was born in 1934
q: He’ll be 60 years old in 1994
p and q are equivalent

Example
p: x is a prime number
q: x is not divisible by 2
p and q are not equivalent, as x not divisible by 2 doesn’t mean its
prime

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Let p be a proposition, we define Negation of p denoted by ¬p to be a
proposition which is true when p is false and is false when p is true

¬ p ¬p

T F

F T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Let p be a proposition, we define Negation of p denoted by ¬p to be a
proposition which is true when p is false and is false when p is true

¬ p ¬p

T F

F T

Example
If p is ” monthly volume of sales is less than 20K”, then negation p is ”
monthly volume of sales exceeds or equal to 20K”

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Let p and q be two propositions. The Disjunction of two propositions
is denoted by p ∨ q(read as p or q)

∨ p q p∨q

T T T

T F T

F T T

F F F

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Let p and q be two propositions. The Conjunction of two propositions
is denoted by p ∧ q(read as p and q)

∧ p q p∧q

T T T

T F F

F T F

F F F

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
The Conditional statement is denoted by p → q(read as if p then q)

→ p q p→q
T T T
T F F
F T T
F F T

Note: 1) p is called the ” first component” or ”ANTECEDENT” and q

is called the ”second component” or ”CONSEQUENT”

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Note: 2) For the conditional p → q,

(i) q → p is called ”converse”

p q p→q q→p ¬p → ¬q ¬q → ¬p ¬p ∨ q
T T T T T T T
T F F T T F F
F T T F F T T
F F T T T T T

Table: 1

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Note: 2) For the conditional p → q,

(i) q → p is called ”converse”
(ii) ¬p → ¬q is called ” inverse”

p q p→q q→p ¬p → ¬q ¬q → ¬p ¬p ∨ q
T T T T T T T
T F F T T F F
F T T F F T T
F F T T T T T

Table: 1

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Note: 2) For the conditional p → q,

(i) q → p is called ”converse”
(ii) ¬p → ¬q is called ” inverse”
(iii) ¬q → ¬p is called ”contrapositive”

p q p→q q→p ¬p → ¬q ¬q → ¬p ¬p ∨ q
T T T T T T T
T F F T T F F
F T T F F T T
F F T T T T T

Table: 1

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Observations

Note: 3) From Table 1 we make the following observations:

(i) p → q and ¬q → ¬p are logically equivalent

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Observations

Note: 3) From Table 1 we make the following observations:

(i) p → q and ¬q → ¬p are logically equivalent
(ii) Inverse and Converse are logically equivalent. i.e., q → p and
¬p → ¬q are logically equivalent

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Observations

Note: 3) From Table 1 we make the following observations:

(i) p → q and ¬q → ¬p are logically equivalent
(ii) Inverse and Converse are logically equivalent. i.e., q → p and
¬p → ¬q are logically equivalent
(iii) p → q and ¬p ∨ q are logically equivalent

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 1
Question: There are two restaurants next to each other. One
has a sign that says ” Good food is not cheap”. The other has a
sign that says ” Cheap food is not good”. Are the signs saying
the same thing?
Solution : Let A: Food is good
B: Food is cheap
We have to examine A → ¬B and B → ¬A

A B A → ¬B B → ¬A
T T F F
T F T T
F T T T
F F T T

Inference: Both are saying the same thing.

PROPOSITIONAL AND PREDICATE CALCULUS
 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 1

Question: John made two statements:

I love Lucy

Given that John either told the truth or lied in both the cases,
determine whether John really loves Lucy?

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 1

Question: John made two statements:

I love Lucy
If I love lucy, then I also love Vivian.
Given that John either told the truth or lied in both the cases,
determine whether John really loves Lucy?

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Definition
Let p and q be two propositions. The Biconditional is denoted by
p ↔ q read as ”p iff q

↔ p q p↔q
T T T
T F T
F T F
F F T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 2
Question: An island has 2 tribes of natives. Any native from the
first tribe always tells the truth, while any native from the other
tribe always lies. You arrive at island and ask a native if there is
gold at the island. He answers ”there is gold on the island iff I
always tell the truth”. Which tribe is he from? Is there gold on
the island?
Solution : Let p: There is gold on the island
q: I always tell the truth

p q p↔q
T T T
T F F
F T F
F F T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Consider the following cases:

Case 1: If the person belongs to first tribe. Then q is true and the
statement p ↔ q is true. From the truth table above, p is also
true. Therefore, ”there is gold”

Thus there is gold on the island and the native could have been
from either tribe.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Consider the following cases:

Case 1: If the person belongs to first tribe. Then q is true and the
statement p ↔ q is true. From the truth table above, p is also
true. Therefore, ”there is gold”
Case 2: If the person belongs to second tribe. Then q is false and the
statement p ↔ q must be false. From the truth table above, p is
true. Therefore, ”there is gold”
Thus there is gold on the island and the native could have been
from either tribe.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Well formed formulas

A WFF is a formula generated using the following groups:

i) A statement variable is a WFF

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Well formed formulas

A WFF is a formula generated using the following groups:

i) A statement variable is a WFF
ii) If A is WFF, then ¬A is also a WFF

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Well formed formulas

A WFF is a formula generated using the following groups:

i) A statement variable is a WFF
ii) If A is WFF, then ¬A is also a WFF
iii) If A and B are WFF’s, A ∨ B, A ∧ B, A → B, A ↔ B are also
WFFs.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Well formed formulas

A WFF is a formula generated using the following groups:

i) A statement variable is a WFF
ii) If A is WFF, then ¬A is also a WFF
iii) If A and B are WFF’s, A ∨ B, A ∧ B, A → B, A ↔ B are also
WFFs.
iv) A string of symbols consisting of statement variables,
connectivities and parenthesis is a WFF iff it can be obtained by
finite many applications of the rules (i), (ii) and (iii)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Well formed formulas

A WFF is a formula generated using the following groups:

i) A statement variable is a WFF
ii) If A is WFF, then ¬A is also a WFF
iii) If A and B are WFF’s, A ∨ B, A ∧ B, A → B, A ↔ B are also
WFFs.
iv) A string of symbols consisting of statement variables,
connectivities and parenthesis is a WFF iff it can be obtained by
finite many applications of the rules (i), (ii) and (iii)

Example
(1) p ∧ q, ¬(p ∧ q), (¬(p → q)) ∨ r , ((p → q) → r are WFFs.
(2) p ∧ q → r is not a WFF as it can be (p ∧ q) → r or p ∧ (q → r )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Equivalence of formulas

Definition
Let A and B be two statement formulas and P1 , P2 , · · · Pn denote all
the variables occurring in A and B. If the truth value of A is same as
that of B for each of 2n possible set of assignments to the variables
P1 , P2 , · · · Pn , then A and B are said to be equivalent. We write as
A ⇔ B.
Two statement formulas A and B are equivalent iff A ↔ B is a
Tautology.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q
(2) Commutative: (a) p ∨ q ⇔ q ∨ p
(b) p ∧ q ⇔ q ∧ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q
(2) Commutative: (a) p ∨ q ⇔ q ∨ p
(b) p ∧ q ⇔ q ∧ p
(3) Associative: (a) p ∨ (q ∨ r ) ⇔ (p ∨ q) ∨ r
(b) p ∧ (q ∧ r ) ⇔ (p ∧ q) ∧ r

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q
(2) Commutative: (a) p ∨ q ⇔ q ∨ p
(b) p ∧ q ⇔ q ∧ p
(3) Associative: (a) p ∨ (q ∨ r ) ⇔ (p ∨ q) ∨ r
(b) p ∧ (q ∧ r ) ⇔ (p ∧ q) ∧ r
(4) Distributive: (a) p ∨ (q ∧ r ) ⇔ (p ∨ q) ∧ (p ∨ r )
(b) p ∧ (q ∨ r ) ⇔ (p ∧ q) ∨ (p ∧ r )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q
(2) Commutative: (a) p ∨ q ⇔ q ∨ p
(b) p ∧ q ⇔ q ∧ p
(3) Associative: (a) p ∨ (q ∨ r ) ⇔ (p ∨ q) ∨ r
(b) p ∧ (q ∧ r ) ⇔ (p ∧ q) ∧ r
(4) Distributive: (a) p ∨ (q ∧ r ) ⇔ (p ∨ q) ∧ (p ∨ r )
(b) p ∧ (q ∨ r ) ⇔ (p ∧ q) ∨ (p ∧ r )
(5) Absorption: (a) p ∨ (p ∧ q) ⇔ p
(b) p ∧ (p ∨ q) ⇔ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(1) ¬¬p ⇔ q
(2) Commutative: (a) p ∨ q ⇔ q ∨ p
(b) p ∧ q ⇔ q ∧ p
(3) Associative: (a) p ∨ (q ∨ r ) ⇔ (p ∨ q) ∨ r
(b) p ∧ (q ∧ r ) ⇔ (p ∧ q) ∧ r
(4) Distributive: (a) p ∨ (q ∧ r ) ⇔ (p ∨ q) ∧ (p ∨ r )
(b) p ∧ (q ∨ r ) ⇔ (p ∧ q) ∨ (p ∧ r )
(5) Absorption: (a) p ∨ (p ∧ q) ⇔ p
(b) p ∧ (p ∨ q) ⇔ p
(6) Idempotent: (a) (p ∧ p) ⇔ p
(b) (p ∨ p) ⇔ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T
(8) (a) p ∨ F ⇔ p
(b) p ∧ F ⇔ F

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T
(8) (a) p ∨ F ⇔ p
(b) p ∧ F ⇔ F
(9) (a) p ∨ T ⇔ T
(b) p ∧ T ⇔ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T
(8) (a) p ∨ F ⇔ p
(b) p ∧ F ⇔ F
(9) (a) p ∨ T ⇔ T
(b) p ∧ T ⇔ p
(10) (a) ¬(p ∨ q) ⇔ (¬p ∧ ¬q)
(b) ¬(p ∧ q) ⇔ (¬p ∨ ¬q)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T
(8) (a) p ∨ F ⇔ p
(b) p ∧ F ⇔ F
(9) (a) p ∨ T ⇔ T
(b) p ∧ T ⇔ p
(10) (a) ¬(p ∨ q) ⇔ (¬p ∧ ¬q)
(b) ¬(p ∧ q) ⇔ (¬p ∨ ¬q)
(11) (a) p → q ⇔ ¬p ∨ q
(b) ¬(p → q) ⇔ p ∧ ¬q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of equivalence

(7) (a) p ∧ (¬p) ⇔ F

(b) p ∨ (¬p) ⇔ T
(8) (a) p ∨ F ⇔ p
(b) p ∧ F ⇔ F
(9) (a) p ∨ T ⇔ T
(b) p ∧ T ⇔ p
(10) (a) ¬(p ∨ q) ⇔ (¬p ∧ ¬q)
(b) ¬(p ∧ q) ⇔ (¬p ∨ ¬q)
(11) (a) p → q ⇔ ¬p ∨ q
(b) ¬(p → q) ⇔ p ∧ ¬q
(12) (a) p → q ⇔ (¬q → ¬p)
(b) q → p ⇔ (¬p → ¬q)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 4

Question: Show that (¬p ∧ (¬q ∧ r )) ∨ (q ∧ r ) ∨ (p ∧ r ) ⇔ r

(¬p ∧ (¬q ∧ r )) ∨ (q ∧ r ) ∨ (p ∧ r ) ⇔ (¬p ∧ (¬q ∧ r )) ∨ (r ∧ (q ∨ p))

⇔ ((¬p ∧ ¬q) ∧ r ) ∨ (r ∧ (p ∨ q))
⇔ (¬(p ∨ q) ∧ r ) ∨ (r ∧ (p ∨ q))
⇔ r ∧ [(p ∨ q) ∨ ¬(p ∨ q)]
⇔ r ∧T
⇔ r

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Excerise 5

Question: Show that 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

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 4

Question: Show that

((p ∨ q) ∧ ¬[(¬p) ∧ (¬q ∨ ¬r )]) ∨ (¬p ∧ ¬q) ∨ (¬p ∧ ¬r ) is a tautology.
Solution: [(p ∨ q) ∧ ¬((¬p) ∧ (¬q ∨ ¬r ))] ∨ (¬p ∧ ¬q) ∨ (¬p ∧ ¬r )
= [(p ∨ q) ∧ ¬(¬p ∧ (¬q ∨ ¬r ))] ∨ (¬p ∧ (¬q ∨ ¬r ))
= [(p ∨ q) ∧ ¬¬p ∨ (q ∧ r )] ∨ (¬p ∧ ¬(q ∧ r ))
= [(p ∨ q) ∧ (p ∨ (q ∧ r ))] ∨ ¬(p ∨ (q ∧ r ))
= [(p ∨ q) ∧ (p ∨ q) ∧ (p ∨ r )] ∨ ¬(p ∨ (q ∧ r ))
= [(p ∨ q) ∧ (p ∨ r )] ∨ ¬(p ∨ (q ∧ r ))
= [(p ∨ (q ∧ r )] ∨ ¬(p ∨ (q ∧ r ))
=T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Excerise 6

Question: Show that q ∨ (p ∧ ¬q) ∨ (¬p ∧ ¬q) is a tautology

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Tautological Implications

Definition
A is said to tautologically imply to statement B if A → B is a
tautology. In this case, we write A ⇒ B ( read as A implies B)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q
(3) ¬p =⇒ p → q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q
(3) ¬p =⇒ p → q
(4) q =⇒ p → q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q
(3) ¬p =⇒ p → q
(4) q =⇒ p → q
(5) ¬(p → q) =⇒ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q
(3) ¬p =⇒ p → q
(4) q =⇒ p → q
(5) ¬(p → q) =⇒ p
(6) ¬(p → q) =⇒ ¬q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(1) p ∧ q =⇒ p
p ∧ q =⇒ q
(2) p =⇒ p ∨ q
q =⇒ p ∨ q
(3) ¬p =⇒ p → q
(4) q =⇒ p → q
(5) ¬(p → q) =⇒ p
(6) ¬(p → q) =⇒ ¬q
(7) p ∧ (p → q) =⇒ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(8) ¬q ∧ (p → q) =⇒ ¬p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(8) ¬q ∧ (p → q) =⇒ ¬p
(9) ¬p ∧ (p ∨ q) =⇒ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(8) ¬q ∧ (p → q) =⇒ ¬p
(9) ¬p ∧ (p ∨ q) =⇒ q
(10) (p → q) ∧ (q → r ) =⇒ p → r

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Table of Tautological Implications

(8) ¬q ∧ (p → q) =⇒ ¬p
(9) ¬p ∧ (p ∨ q) =⇒ q
(10) (p → q) ∧ (q → r ) =⇒ p → r
(11) (p ∨ q) ∧ (p → r ) ∧ (q → r ) =⇒ r

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 7
Question: Show that ¬q ∧ (p → q) =⇒ ¬p
Solution: Suppose ¬q ∧ (p → q) is true.
¬q is true and p → q is true
q is false and p → q is true
=⇒ p is false
=⇒ ¬p is true
∴ ¬q ∧ (p → q) =⇒ ¬p
Remark
To show that A =⇒ B, we can assume B is false and show that A is
false. So the above problem can also be analyzed as follows: Consider
again ¬p is false, =⇒ p is true. If q is true, ¬q is false and its
understood that ¬q ∧ (p → q) is false. If q is false, ¬q is true and
p → q is false. Again ¬q ∧ (p → q) is false.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Problem 8

Question: Show that ¬(p → q) =⇒ ¬q

Solution: We say that A =⇒ b if A → B is true in all conditions

p q p→q ¬(p → q) ¬q ¬(p → q) → ¬q

T T T F F T
T F F T T T
F T T F F T
F F T F T T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 9

Question: Show that (p ∨ q) ∧ (p → r ) ∧ (q → r ) =⇒ r

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 10

Question: Prove that

(i) ¬p =⇒ p → q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 10

Question: Prove that

(i) ¬p =⇒ p → q
(ii) p ∧ (p → q) =⇒ q

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 10

Question: Prove that

(i) ¬p =⇒ p → q
(ii) p ∧ (p → q) =⇒ q
(iii) p ∧ q =⇒ p

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Rules of Inference

Let A and B be two statement formula. We say that ” B logically

follows from A” or ”B is a valid conclusion of the premise A” iff A → B
is a Tautology i.e., A =⇒ B.
To demonstrate that a particular formula is valid consequence of a
given set of premises, we use the follow rules of inference.

Rule P : A premise may be introduced at any point in the derivation

Rule T : A formula S may be introduced in a derivation if S is
tautologically implied by any one or more of the preceding
formulas in the derivation

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question : Demonstrate that r is a valid inference from the premises

p → q, q → r and p
Solution :

p→q (Rule P)
p (Rule P)
q (Rule T , p ∧ (p → q) =⇒ q)
q→r (Rule P)
r (Rule T , q ∧ (q → r ) =⇒ r )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question : RVS follows logically from the premises C ∧ D,

C ∨ D → ¬H, ¬H → (A ∧ ¬B), (A ∧ ¬B) → (R ∨ S).
Solution :

C ∨ D → ¬H (Rule P)
¬H → A ∧ ¬B (Rule P)
C ∨ D → A ∧ ¬B (Rule T )
A ∧ ¬B → R ∨ S (Rule P)
C ∨D →R ∨S (Rule T )
C ∨D (Rule P)
R ∨S (Rule T )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question : Show that S ∨ r is tautologically implied by

(p ∨ q) ∧ (p → r ) ∧ (q → s)
Solution :

p∨q (Rule P)
¬p → q (Rule T i.e., p → q ⇔ ¬p ∨ q)
q→S (Rule P)
¬p → S (Rule T )
¬S → p (Rule T , p → q ⇔ ¬q → ¬p)
p→r (Rule P)
¬S → r (Rule T )
S ∨r (Rule T , p → q ⇔ ¬(¬p ∨ q))

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise Q1 : R ∧ (p ∨ q) is a valid conclusion from the premises

p ∨ q, q → r , p → M and ¬M.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise Q2 : If A works hard, then either B or C will enjoy

themselves. If B enjoys himself, then A will not work hard. If D enjoys
himself, then C will not, therefore prove that if A works hard, D will
not enjoy himself.
Solution hint :

A : A works hard
B : B will enjoy himself
C : C will enjoy himself
D : D will enjoy himself

To prove A → ¬D follows from A → B ∨ C , B → ¬A and D → ¬C

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

A part of declarative sentence describing the properties of an object or

relation among objects is called a ”PREDICATE”
Example
Consider two propositions, Ram is a Bachelor, Shyam is a Bachelor.
Both Ram and Shyam have the same property of having bachelor. The
part ”is a bachelor” is called a predicate.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Notations

The predicate is denoted by capital letters and names of individuals or

objects by small letters. Let ”B” denote the predicate ”is bachelor”,
then the sentence ”x is a bachelor” can be written as B(x), where x is
a predicate variable B(x) is also called a propositional function, which
becomes a statement when values are submitted in place of x. A
predicate requiring m(> 0) names is called m−place predicate
Example
x is taller than y; T(x,y)- the two place predicate

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Universal and existential quantifiers

Quantifiers are words that refer to quantifiers such as ”some” or ”all”

and indicate now frequently certain statement is true.
The phrase ”for all” (∀) is called the UNIVERSAL QUANTIFIERS
Example
All human beings are mortal. For all natural numbers ”n”, ”2n” is an
even number.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

The phrase ”there exists” (∃ ) is called the

EXISTENTIAL QUANTIFIER
Example
There exists x such that x 2 = 5. This can be written as ∃xP(x) where
P(x) : x 2 = 5.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 1

”there exists” (∃) represents the following:

there exists an x

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 1

”there exists” (∃) represents the following:

there exists an x
there is an x

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 1

”there exists” (∃) represents the following:

there exists an x
there is an x
for some x

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 1

”there exists” (∃) represents the following:

there exists an x
there is an x
for some x
there is atleast one x

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 2

(∀x)P(x) is true iff P(x) is true ∀x in U

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 2

(∀x)P(x) is true iff P(x) is true ∀x in U

(∀x)P(x) is false iff P(x) is false for atleast one x in U

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 2

(∀x)P(x) is true iff P(x) is true ∀x in U

(∀x)P(x) is false iff P(x) is false for atleast one x in U
(∀x)P(x) is true if P(x) is true for atleast one x in U

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

NOTE 2

(∀x)P(x) is true iff P(x) is true ∀x in U

(∀x)P(x) is false iff P(x) is false for atleast one x in U
(∀x)P(x) is true if P(x) is true for atleast one x in U
(∀x)P(x) is false if P(x) is false for every x in U

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 1

Example
Let D = {1, 2, 3, ...9} Determine the truth value of each of the follow
statements.

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 1

Example
Let D = {1, 2, 3, ...9} Determine the truth value of each of the follow
statements.
(∀x)x + 4 < 15 T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 1

Example
Let D = {1, 2, 3, ...9} Determine the truth value of each of the follow
statements.
(∀x)x + 4 < 15 T
(∃x)x + 4 = 10 T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 1

Example
Let D = {1, 2, 3, ...9} Determine the truth value of each of the follow
statements.
(∀x)x + 4 < 15 T
(∃x)x + 4 = 10 T
(∀x)x + 4 > 15 F

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 1

Example
Let D = {1, 2, 3, ...9} Determine the truth value of each of the follow
statements.
(∀x)x + 4 < 15 T
(∃x)x + 4 = 10 T
(∀x)x + 4 > 15 F
(∀x)x + 4 ≤ 10 F

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 2

Example
Symbolize the statement: All men are mortal
Solution: Let M(x) : x is an integer
N(x) : x is either positive or negative
(∀x)(M(x) → N(x))

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 3

Example
Symbolize the statement: An integer is either positive or negative.
Solution: Let M(x) : x is a man
H(x) : x is a mortal
(∀x)(M(x) → H(x))

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Negation of quantified statements

¬(∀x)P(x) ⇔ (∃x)¬P(x)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Negation of quantified statements

¬(∀x)P(x) ⇔ (∃x)¬P(x)
¬(∃x)P(x) :⇔ (∀x)¬P(x)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 4

Negate the following statements: For all real numbers x, if x > 3 then
x2 > 9
Solution: Given : Let P(x) : x > 3
Q(x) : x 2 > 9,
∴(∀x)(P(x) → Q(x))

Negation is : ¬∀x(P(x) → Q(x))

⇔ (∃x)¬(P(x) → Q(x))
⇔ (∃x)¬(P(x) ∧ ¬Q(x))

that is there exists a real number x such that x > 3 and x 2 ≤ 9

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise Q5 : Negate the following statement ” Every city in Canada

is clean”

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Rules of Inference
The method of derivation involving predicate formulas uses the rules of
inference given for the statement calculus and also certain additional
rules which are required to deal with the formulas involving quantifiers
( In addition to Rule P and T)
(1) Rule US(Universal Specification)
From (∀x)A(x), we can conclude A(y ).

(∀x)A(x) =⇒ A(y )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Rules of Inference
The method of derivation involving predicate formulas uses the rules of
inference given for the statement calculus and also certain additional
rules which are required to deal with the formulas involving quantifiers
( In addition to Rule P and T)
(1) Rule US(Universal Specification)
From (∀x)A(x), we can conclude A(y ).

(∀x)A(x) =⇒ A(y )
(2) Rule ES ( Existential Specification)
From (∃x)A(x) one can conclude A(y ) provided that y is not free
in any given premise and also not free in any prior step of the
derivation.
(∃x)A(x) =⇒ A(y )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

(3) Rule EG(Extential Generalization)

From A(x) one can conclude (∃y )A(y ).

A(x) =⇒ (∃y )A(y )

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

(3) Rule EG(Extential Generalization)

From A(x) one can conclude (∃y )A(y ).

A(x) =⇒ (∃y )A(y )

(4) Rule UG ( Universal Generalization)
From A(x) one can conclude (∀y )A(y ) provided that x is not free
in any of the given premises and provided that if x is free in a prior
step which resulted from use of ES, then no variables introduced
by that use of ES appear free in A(x)

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 5

Show that (∀x)[H(x) → M(x)] ∧ H(s) =⇒ M(s)

[Note that this problem is a symbolic representation or translation of a
well known argument known as ”Socrates argument” which is given by
”All men are mortal
Socrates is a man
Therefore Socrates is a mortal”]
Solution : Denote H(s) : x is a man
M(s) : Socrates is mortal
(1) (∀x)[H(x) → M(x)] Rule P
(2) H(s) → M(s) Rule US
(3) H(s) Rule P
(4) M(s) Rule T

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Question 6

Show that (∃x)M(x) follows logically from the premises

(∀x)[H(x) → M(x)] and (∃x)H(x)
Solution

(1) (∃x) Rule P

(2) H(y ) Rule ES
(3) (∀x)[H(x) → M(x)] Rule P
(4) [H(y ) → M(y )] Rule US by (3)
(5) M(y ) Rule T by (2) and (4)
(6) (∃x)M(x) Rule EG

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 7

Show that
(∀x)[P(x) → Q(x)] ∧ ∀x[Q(x) → R(x)] =⇒ (∀x[P(x) → R(x)]
Solution

(1) (∀x)[P(x) → Q(x)] Rule P

(2) [P(y ) → Q(y )] Rule US by (1)
(3) (∀x)[Q(x) → R(x)] Rule P
(4) [Q(y ) → R(y )] Rule US by (3)
(5) [Q(y ) → R(y )] Rule T by (2) and (4)
(6) (∀x[P(x) → R(x)] Rule UG

PROPOSITIONAL AND PREDICATE CALCULUS

 Proposition Calculus
Rules of Inference
Predicate Calculus

Exercise 8

Show that from

(a)(∀x)[F (x) ∧ S(x)] → ∀y [M(y ) → W (y )]
(b)(∃y )[M(y ) ∧ ¬W (y )]
the conclusion (∀x)[F (x) → ¬S(x)] follows

PROPOSITIONAL AND PREDICATE CALCULUS