Discrete Mathematics (DM)

GTU # 3140708

Unit-2
Propositional logic
&
Predicate logic
 Unit-2

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 2

 Introduction
 Statements
 Connectives
 Statement formulas
 Conditional
 Biconditional
Introduction
 One of the main aim of logic is to provide rules by which one can determine
whether any particular argument or reasoning is valid (correct).
 Logic is concerned with all kinds of reasoning, whether they be legal arguments or
mathematical proofs or conclusions in a scientific theory based upon a set of
hypothesis.

For example:

“4 is an even number.” “3 is an even number.”

 This is a valid argument. × This is not a valid argument.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 4

 All the declarative sentences to which it is possible to assign
one and only one truth value(either T or F) are called statements.

Statements

We begin with declarative sentences.(primitive sentences)

Only, one truth value should be possible to assigned.

So, this sentence is a declarative

 𝟏 𝐓
sentence with truth value true(or 1).
𝟎 𝐅
This is a statement.
“we live on a planet Earth”
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 5
 All the declarative sentences to which it is possible to assign
one and only one truth value(either T or F) are called statements.

Statements

Declarative sentences are of two types.

The first type includes primitive(simple) The second type are obtained from primitive
sentences denoted by capital letters ones by using certain symbols, connectives,
A, B, C, … , P, Q, . etc.. and parentheses, to join primitive sentences.

“𝐧 is an even number”
“𝐧 is an even number or odd number”
“𝐧 is an odd number”

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 6

 All the declarative sentences to which it is possible to assign
one and only one truth value(either T or F) are called statements.

Statements Because it is a command.

× “Close the door.”

Its truth value depend upon
It has truth value true.
context. × “This formula is false.”
In decimal system it is
It has no truth value.
false.  “Canada is a country.”
But, in binary it is true.
 “Delhi is the capital of Spain.”

 “𝟏 + 𝟏𝟎𝟏 = 𝟏𝟏𝟎”
It has truth value false.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 7

 “I have a pencil.” Primary(simple) statements “I have a pen.”

“I have a pen and a pencil.”

Compound statements
“I have a pen or a pencil.”
Connectives
“or”, “and” are connectives.
Consider simple statements, called atomic or primary statements.
Connect them by words or expressions.(sentential connectives)
New statements are called molecular or compound statements.
These words or expressions are called connective.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 8

 Negation(Ί)

Connectives Conjunction(∧)

Disjunction(˅)

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 9

 P ∶ I am poor.
ℸP ∶ I am not poor. or ℸP ∶ I am rich.
Negation(Ί)
Negation will give the opposite of the statement.
The negation of “P” is denoted by “ℸP”(or ~P or Pത ) and read as “not
P.”
To obtain negation the word “not” is introduced at a proper
Connectives
place. Conjunction(∧)
We can also give the statement with opposite meaning to obtain it.
The truth value of “P” and “ℸP” are opposite to each other.
Disjunction(˅)
Truth table: 𝐏 ℸ𝐏
ℸ(opposite truth value)
𝐓 𝐅
𝐅 𝐓
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 10
 P ∶ It is raining today. Q ∶ There is a wind storm.
P ∧ Q ∶ It is raining today and there is a wind storm.
Conjunction connect two statements PNegation(Ί)
and Q by word “and”.
It is denoted by P ∧ Q which is read as “P and Q”.

Connectives
Truth value of P ∧ Q is T whenever Conjunction(∧)
both P and Q are T otherwise F.

Truth table: 𝐏 𝐐 𝐏∧𝐐

𝐓 𝐓 𝐓
∧ (both 𝐓 then 𝐓 otherwise 𝐅) Disjunction(˅)
𝐓 𝐅 𝐅 Truth values of P ∧ Q
and Q ∧ P are same.
𝐅 𝐓 𝐅
𝐅 𝐅 𝐅
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 11
 P ∶ Number is even. Q ∶ Number is odd.
P ∨ Q ∶ Number is even or odd.
Negation(Ί)
Disjunction connect two statements P and Q by word “or”.
It is denoted by P ∨ Q which is read as “P or Q”.

Connectives Conjunction(∧)
Truth value of P ∨ Q is F whenever both P and Q are F otherwise T.

Truth table: 𝐏 𝐐 𝐏∨𝐐

𝐓 𝐓 𝐓
∨ (both 𝐅 then 𝐅 otherwise 𝐓) Disjunction(˅)
𝐓 𝐅 𝐓 Truth values of P ∨ Q
and Q ∨ P are same.
𝐅 𝐓 𝐓
𝐅 𝐅 𝐅
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 12
Method 1 ⟹ Example 3
Que: Translate the statement “Jack and Jill went up the hill.” into symbolic form.
Sol:
 Let us first define two statements(simple/primitive) as follows.
P ∶ Jack went up the hill. Q ∶ Jill went up the hill.

 So, the symbolic form of the given statement is conjunction(∧) of the statements
P and Q.
Connectives
Conjunction (∧) connect with “and”
 Hence, symbolic form of the given statement is
Disjunction (∨) connect with “or”
Negation𝑷 (ℸ)
∧ gives
𝑸 opposite case

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 13

Method 1 ⟹ Example 4
Que: Consider the statements P ∶ Mark is rich. and Q ∶ Mark is happy. Write the
following statement in symbolic form.
(a) Mark is poor but happy.
Sol:
 Here, the statement indicates that “Mark is poor and Mark is happy.”.
 Now, “Mark is poor.” can be symbolized by opposite of P i.e. ℸP.
 Also, “Mark is happy.” can be symbolized by Q itself.
“Mark is poor and Mark is happy.”

ℸ𝑷 ∧ 𝑸
 Hence, symbolic form of the given statement is ℸ𝐏 ∧ 𝐐.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 14
Method 1 ⟹ Example 4(continue)
Que: Consider the statements P ∶ Mark is rich. and Q ∶ Mark is happy. Write the
following statement in symbolic form.
(b) Mark is rich or unhappy.
Sol:
 Here, the statement indicates that “Mark is rich or Mark is unhappy”.
 Now, “Mark is rich.” can be symbolized by P itself.
 Also, “Mark is unhappy.” can be symbolized by opposite of Q i.e.ℸQ.
“Mark is rich or Mark is unhappy”

𝑷 ∨ ℸ𝑸
 Hence, symbolic form of the given statement is 𝑷 ∨ ℸ𝑸.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 15
Method 1 ⟹ Example 4(continue)
Que: Consider the statements P ∶ Mark is rich. and Q ∶ Mark is happy. Write the
following statement in symbolic form.
(c) Mark is neither rich nor happy.
Sol:
 Here, the statement indicates that “Mark is not rich and Mark is not happy”.
 Now, “Mark is not rich.” can be symbolized by opposite of P i.e.ℸP.
 Also, “Mark is not happy.” can be symbolized by opposite of Q i.e.ℸQ.
“Mark is not rich and Mark is not happy”

ℸ𝑷 ∧ ℸ𝑸
 Hence, symbolic form of the given statement is ℸ𝑷 ∧ ℸ𝑸.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 16
Method 1 ⟹ Example 4(continue)
Que: Consider the statements P ∶ Mark is rich. and Q ∶ Mark is happy. Write the
following statement in symbolic form.
(d) Mark is poor or he is both rich and unhappy.
Sol:
 Here, the statement indicates that “Mark is poor or Mark is rich as well as
unhappy.”.
 Now, “Mark is poor.” can be symbolized by opposite of P i.e. ℸP.
 Also, second part “Mark is both rich and unhappy.” can be represented by
connecting “Mark is rich.” and “Mark is unhappy.” by connective conjunction i.e.
P ∧ ℸQ.
 So, the symbolic form of given statement is disjunction(∨) of both part.
 Hence, symbolic form of the given statement is ℸ𝐏 ∨ 𝐏 ∧ ℸ𝐐 .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 17
 So, statement formulas are formulas formed by connecting the
statements by connectives(negation, conjunction or disjunction).

Statement
formulas

Let P and Q be any two statements.

Then, ℸP, P ∧ Q,(P ∨ Q) ∧ (ℸP) etc. are compound statements.
Here, P and Q are called the components.

ℸ𝐏 ℸ𝐐 𝐏 ∧ ℸ𝐐

𝐏∨𝐐 𝐏∧𝐐 𝐏 ∧ 𝐐 ∨ ℸ𝐐
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 18
Method 1 ⟹ Example 5
Que: Construct the truth table for the statement formula P ∨ ℸQ.
Sol: The truth table for the formula P ∨ ℸQ is as follows.

𝐏 𝐐 ℸ𝐐 𝐏 ∨ ℸ𝐐
T T F T
T F T T
F T F F
F F T T
∨ (both 𝐅 then truth
ℸ(opposite 𝐅 otherwise
value) 𝐓)
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 19
Method 1 ⟹ Example 7
Que: Construct the truth table for P ∨ (Q ∧ R). ∨ (both 𝐓
∧ 𝐅 then 𝐅 otherwise 𝐓)
𝐓 otherwise 𝐅)
Sol: The truth table for the formula P ∨ (Q ∧ R) is as follows.
𝐏 𝐐 𝐑 𝐐∧𝐑 𝐏 ∨ (𝐐 ∧ 𝐑)
T T T T T
T T F F T
T F T F T
T F F F T
F T T T T
F T F F F
F F T F F
F F F F F
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 20
Method 1 ⟹ Example 9(b)
Que: Given the truth values of P and Q as T and those of R and S as F, find the truth
Que: value for the formula P ∧ Q ∧ R ∨ ℸ P ∨ Q ∧ R ∨ S .
Sol:
 Here, we are given the truth values of P and Q as T and those of R and S as F.
 Substituting theses truth values in given formula, we get,
𝐏∧ 𝐐∧𝐑 ∨ℸ 𝐏∨𝐐 ∧ 𝐑∨𝐒
= T∧ T∧F ∨ℸ T∨T ∧ F∨F
∧ (both 𝐓 then 𝐓 otherwise 𝐅)
= T ∧ (F)
F ∨ ℸ T ∧ (F)
F
∨ (both 𝐅 then 𝐅 otherwise 𝐓)
= F ∨ℸ F
ℸ(opposite truth value)
= F ∨ T
= T
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 21
Conditional(→)
If P and Q are any two statements, then the statement P → Q which
is read as “If P, then Q” is called a conditional statement.

The statement P → Q has a truth value F, “when Q has truth value F

and P has T ”, otherwise it has the truth value T.

Truth table: 𝐏 𝐐 𝐏→𝐐

𝐓 𝐓 𝐓 Here, the statement P
𝐓 𝐅 𝐅 is called the antecedent
𝐅 𝐓 𝐓 and Q the consequent.
𝐅 𝐅 𝐓
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 22
Biconditional(⇄)
If P and Q are any two statements, then the statement P ⇄ Q which
is read as “P if and only if Q” is called a biconditional statement.

The statement P ⇄ Q has the truth value T whenever both P and Q

have identical truth values.

Truth table: 𝐏 𝐐 𝐏⇆𝐐

𝐓 𝐓 𝐓
𝐓 𝐅 𝐅
𝐅 𝐓 𝐅
𝐅 𝐅 𝐓
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 23
Method 1 ⟹ Example 10
Que: Write the statement “If either Jerry takes Calculus or Ken takes Sociology, then
Que: Larry will take English.” in symbolic form.
Sol:
 Let us first define simple statements as follows.

P ∶ Jerry takes Calculus. Q ∶ Ken takes Sociology. R ∶ Larry will take English.

 So, the symbolic form of the given statement is,

“If either Jerry takes Calculus or Ken takes Sociology, then Larry will take English.

𝑷 ∨ 𝑸 → 𝐑
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 24
Method 1 ⟹ Example 12
Que: Construct the truth table for (P → Q) ∧ (Q → P).
Sol: The truth table for the formula (P → Q) ∧ (Q → P) is as follows.

𝐏 𝐐 𝐏→𝐐 𝐐→𝐏 𝐏→𝐐 ∧ 𝐐→𝐏

T T T T T
T F F T F
F T T F F
F F T T T
𝐐
𝐏→𝐐 𝐏 is a condition “ if 𝐐 𝐏 is true”.
𝐏 is true then 𝐐
∧ (both 𝐓 then 𝐓 otherwise 𝐅)
(whenever condition break value is 𝐅 otherwise 𝐓)
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 25
Method 1 ⟹ Example 13
Que: Construct the truth table for ℸ P ∧ Q ⇄ ℸP ∨ ℸQ .
Sol: The truth table for the formula ℸ P ∧ Q ⇄ ℸP ∨ ℸQ is as follows.

𝐏 𝐐 𝐏 ∧ 𝐐 ℸ(𝐏 ∧ 𝐐) ℸ𝐏 ℸ𝐐 ℸ𝐏 ∨ ℸ𝐐 ℸ(𝐏 ∧ 𝐐) ⇄ (ℸ𝐏 ∨ ℸ𝐐)

T T T F F F F T
T F F T F T T T
F T F T T F T T
F F F T T T T T
ℸ(𝐏 ∧ 𝐐) ⇄ (ℸ𝐏 ∨ ℸ𝐐) is a Biconditional statement.
∧∨ (both
(both 𝐓𝐅 thentruth
ℸ(opposite 𝐓 value) 𝐅)
𝐅 otherwise 𝐓)
(both have same truth value then 𝐓 otherwise 𝐅)
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 26
 Well-formed formula
 Tautology
 Tautological implications
 Equivalence formulas
 Duality law
 d.n.f. & c.n.f
 A string of symbols is a well-formed formula, if and only if it can
be obtained by finitely many applications of these rules.

Well-formed  ℸ 𝐏∧𝐐 × ℸ𝐏 ∧ 𝐐 × 𝐏→𝐐

formula  𝐏→ 𝐏∧𝐐 × 𝐏 → 𝐐 → ∧𝐐 × 𝐏→𝐐 →𝐐

A well-formed formula can be generated by the following rules.

1. A statement variable standing alone is a well-formed formula.
2. If A is a well-formed formula, then ℸA is a well-formed formula.

3. If A and B are well-formed formulas, then A ∧ B , A ∨ B ,

A → B and A ⇄ B are well-formed formulas.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 28

 In truth table, if all truth values are true then statement formula
is called a tautology or a universally valid formula or logical truth.

Tautology

In truth table, if all truth values are false then statement formula
is called contradiction.
For example: Consider the formula ℸP ∨ P.
Truth table: 𝐏 ℸ𝐏 𝐏 ∨ ℸ𝐏
𝐓 𝐅 𝐓
𝐅 𝐓 𝐓
The statement formula ℸP ∨ P is a tautology.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 29
Method 2 ⟹ Example 1
Que: Check whether the given formulas are well-formed formulas. Also, indicate
Que: which ones are tautologies or contradictions.
(a) P → P ∨ Q
Sol:
 Here, given formula is a well-formed formula.
 To check whether formula is tautology or contradiction, we will construct truth
table of given formula.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 30

Method 2 ⟹ Example 1(continue)
 The truth table for the formula P → P ∨ Q is as follows.

𝐏 𝐐 𝐏∨𝐐 𝐏→ 𝐏∨𝐐
T T T T
T F T T
F T T T
F F F T
 Here, all truth
𝐏→ values
𝐏∨𝐐 istrue
are∨ a condition
in the “ if 𝐏 column
final is true then
of truth is true”.
𝐏 ∨ 𝐐table.
(both 𝐅 then 𝐅 otherwise 𝐓)
(whenever condition break value is 𝐅 otherwise 𝐓)
 Hence, P → P ∨ Q is a tautology.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 31
Method 2 ⟹ Example 1(continue)
Que: Check whether the given formulas are well-formed formulas. Also, indicate
Que: which ones are tautologies or contradictions.
b P → ℸP → ℸP
Sol:
 Here, given formula is a well-formed formula.
 To check whether formula is tautology or contradiction, we will construct truth
table of given formula.
 The truth table for the formula P → ℸP → ℸP is as follows.
Home work
 Here, all truth values are true in the final column of truth table.
 Hence, P → ℸP → ℸP is a tautology.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 32
Method 2 ⟹ Example 1(continue)
Que: Check whether the given formulas are well-formed formulas. Also, indicate
Que: which ones are tautologies or contradictions.
(c) ℸQ ∧ P ∧ Q
Sol:
 Here, given formula is a well-formed formula.
 To check whether formula is tautology or contradiction, we will construct truth
table of given formula.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 33

Method 2 ⟹ Example 1(continue)
 The truth table for the formula ℸQ ∧ P ∧ Q is as follows.

𝐏 𝐐 ℸ𝐐 ℸ𝐐 ∧ 𝐏 ℸ𝐐 ∧ 𝐏 ∧ 𝐐
T T F F F
T F T T F
F T F F F
F F T F F
∧ (both 𝐓 then
ℸ(opposite
 Here, all truth values are false in the truth
final value)of truth
otherwise
𝐓column 𝐅) table.
 Hence, ℸQ ∧ P ∧ Q is a contradiction.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 34
Method 2 ⟹ Example 1(continue)
Que: Check whether the given formulas are well-formed formulas. Also, indicate
Que: which ones are tautologies or contradictions.
(d) ( P → Q → R → P→Q → P→R

(e) ℸ𝑃 → 𝑄 → 𝑄 → 𝑃 )

Sol:
 Here, given formula (d) is not a well-formed formula.

 Here, given formula (e) is not a well-formed formula.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 35

Method 2 ⟹ Example 1(continue)
Que: Check whether the given formulas are well-formed formulas. Also, indicate
Que: which ones are tautologies or contradictions.
(f) P∧Q ⇆ P
Sol:
 Here, given formula is a well-formed formula.
 To check whether formula is tautology or contradiction, we will construct truth
table of given formula.
 The truth table for the formula P ∧ Q ⇆ P is as follows.
Home work
 Hence, P ∧ Q ⇆ P is neither tautology nor contradiction.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 36

 A statement P is said to tautologically imply a statement Q if and
only if P → Q is a tautology.

Tautological
implications
It is denoted by P ⇒ Q and read as “P implies Q”.
Here, “→” is a conditional operator.
For example: Consider the formula P → Q.
𝐏 𝐐 𝐏→𝐐 So, the formula P → Q
Truth table:
is not a tautology.
𝐓 𝐓 𝐓
𝐓 𝐅 𝐅 Hence, we can say that
P⇏ Q
𝐅 𝐓 𝐓
𝐅 𝐅 𝐓
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 37
Method 2 ⟹ Example 3(b)
Que: Check the implication P ⇒ Q → P
Sol: The truth table for the formula P → Q → P is as follows.

𝐏 𝐐 𝐐→𝐏 𝐏→ 𝐐→𝐏
T T T T
T F T T
F T F T
F F T T
 Here, all truth values are true in the final column of truth table.
𝐏 → 𝐐𝐐→→𝐏𝐏 is a condition “ if 𝐐
𝐏 is true then 𝐏𝐐is→true”.
𝐏 is true”.
 Hence, P → (whenever is a tautology.
Q → P condition i.e. Pis⇒
break value Q ⟶ P𝐓).
𝐅 otherwise
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 38
 If the truth values of P is equal to the truth values of Q, then P
and Q are said to be equivalent.

Equivalence
formulas
It is denoted by P ⇔ Q.
Properties: 1 If P ⇔ Q then Q ⇔ P.(symmetric property)
2 If P ⇔ Q and Q ⇔ R then P ⇔ R.(transitive property)

For example: Truth table:

𝐏 ℸ𝐏 ℸℸ𝐏 The truth values of P

and ℸℸP are same.
𝐓 𝐅 𝐓
𝐅 𝐓 𝐅 Hence, ℸℸP ⇔ P
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 39
Method 2 ⟹ Example 10(b)
Que: Check the equivalence ∶ P → Q ∨ R ⇔ P → Q ∨ P → R
Sol: Here, first we find truth values of P → Q ∨ R and P → Q ∨ P → R .
P Q R 𝐐∨𝐑 𝐏 → (𝐐 ∨ 𝐑) 𝐏 → 𝐐 𝐏→𝐑 (𝐏 → 𝐐) ∨ (𝐏 → 𝐑)
T T T T T T T T
T T F T T T F T
T F T T T F T T
T F F F F F F F
F T T T T T T T
F T F T T T T T
F F T T T T T T
F F F F T T T T
 So, truth values of 𝐑P𝐐→ Q ∨ R and P → Q ∨ 𝐐 P → 𝐑R isare same.
true”.
𝐏→ 𝐐 𝐏∨ → 𝐑 is a condition “ if 𝐏 is true then 𝐑𝐐is∨true”.
 Hence, P → Q(whenever (both
P → 𝐅Qthen
∨ R ⇔∨condition otherwise
∨ 𝐅Pvalue 𝐓)
→ Ris. 𝐅 otherwise
break 𝐓)
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 40
 The formula P and P ∗ are said to be duals of each other if either one
can be obtained from the other by replacing ∧ by ∨ and ∨ by ∧.

Duality
law
The connectives ∧ and ∨ are also called duals of each
other.
Also, if the formula contain truth values then we will replace
T by F and F by T to obtain dual.
For example:
The dual of 𝐏 ∨ 𝐐 ∧ 𝐑 is 𝐏∧𝐐 ∨𝐑

The dual of 𝐏 ∧ 𝐐 ∨ 𝐓 is 𝐏∨𝐐 ∧𝐅

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 41

Method 2 ⟹ Example 9
Que: If A P, Q, R = ℸP ∧ ℸ Q ∨ R then show that ℸA P, Q, R ⇔ A∗ ℸP, ℸQ, ℸR .
Sol:
 Here, 𝐀 𝐏, 𝐐, 𝐑 = ℸ𝐏 ∧ ℸ 𝐐 ∨ 𝐑 and so, 𝐀∗ (𝐏, 𝐐, 𝐑) = ℸ𝐏 ∨ ℸ(𝐐 ∧ 𝐑)

L.H.S = ℸA P, Q, R R.H.S = A∗ ℸP, ℸQ, ℸR

= ℸ ℸP ∧ ℸ Q ∨ R = ℸℸP ∨ ℸ ℸQ ∧ ℸR
= ℸ ℸP ∨ ℸ ℸ Q ∨ R = ℸℸP ∨ ℸ ℸQ ∨ ℸ ℸR
=P∨ Q∨R =P∨ Q∨R

∗ De Morgan's laws
 Hence, ℸA P, Q, R ⇔ A ℸP, ℸQ, ℸR .
ℸ 𝐀 ∧ 𝐁 = ℸ𝐀 ∨ ℸ𝐁
ℸ 𝐀 ∨ 𝐁 = ℸ𝐀 ∧ ℸ𝐁
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 42
 How to find dnf(disjunctive normal form)?
Que: Find the dnf of P → Q ∧ Q → P .
Sol:
𝐏 𝐐 𝐏→𝐐 𝐐→𝐏 𝐏→𝐐 ∧ 𝐐→𝐏
T T T T T
T F F T F
F T T F F
F F T T T
Hence, required dnf is 𝐏 ∧ 𝐐 ∨ ℸ𝐏 ∧ ℸ𝐐
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 43
 How to find cnf(conjunctive normal form)?
Que: Find the cnf of P → Q ∧ Q → P .
Sol:
𝐏 𝐐 𝐏→𝐐 𝐐→𝐏 𝐏→𝐐 ∧ 𝐐→𝐏
T T T T T
T F F T F
F T T F F
F F T T T
Hence, required cnf is ℸ𝐏 ∨
∧𝐐 ∧ 𝐏∨
∧ ℸ𝐐
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 44
Method 2 ⟹ Example(GTU)(4-marks)
Que: Obtain the dnf of the form P → Q ∧ ℸP ∧ Q .
Sol: Truth table for P → Q ∧ ℸP ∧ Q is as follows.

𝐏 𝐐 𝐏→𝐐 ℸ𝐏 ℸ𝐏 ∧ 𝐐 𝐏 → 𝐐 ∧ ℸ𝐏 ∧ 𝐐
T T T F F F
T F F F F F
F T T T T T
F F T T F F
Hence, required dnf is ℸ𝐏 ∧ 𝐐
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 45
Method 2 ⟹ Example(GTU)(4-marks)
Que: Obtain the dnf of the form ℸ P → Q ∧ R .
Sol: Truth table for ℸ P → Q ∧ R is as follows.
P Q R 𝐐∧𝐑 𝐏 → (𝐐 ∧ 𝐑) ℸ 𝐏→ 𝐐∧𝐑
T T T T T F
T T F F F T
T F T F F T
T F F F F T
F T T T T F
F T F F T F
F F T F T F
F F F F T F
Hence, required dnf is
𝐏 ∧ 𝐐 ∧ ℸ𝐑 ∨ 𝐏 ∧ ℸ𝐐 ∧ 𝐑 ∨ 𝐏 ∧ ℸ𝐐 ∧ ℸ𝐑
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 46
 Predicate
 Statement function
 Quantifiers
 Free & bound variables
 The universe of discourse
 This part “is a bachelor” is called a predicate.
Symbolize “is a bachelor” by B, “John” by j, and “Smith” by s.
Let us consider two statements.
𝐁 𝐣 ∶ John is a bachelor. 𝐁 𝐬 ∶ Smith is a bachelor.
Predicate
𝐆 𝐣𝟏 , 𝐣𝟐 ∶ Jack is taller than Jill.

Consider another statement “Jack is taller than Jill.”

Symbolize “is taller than” by G, “Jack” by j1 , and “Jill” by j2 .
This part “is taller than” is called a predicate.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 48

 𝐆 𝐱 , 𝐲 ∶ 𝐱 is taller than 𝐲.

𝐆 𝐦 , 𝐧 ∶ Mayur is taller than Nikhil.

Statement
function 𝐆 𝐧 , 𝐦 ∶ Nikhil is taller than Mayur.

Let G be a predicate “is taller than.”.

If we replace x and y by object name , then we get a statement.
Let m denote “Mayur” and n denote “Nikhil”.
Here, x and y are called statement variables.
Also, G(x , y) is called a statement function.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 49

 Some students are clever.
𝐌 𝐱 ∶ 𝐱 is a student. 𝐆 𝐱 ∶ 𝐱 is clever.
For some x, if x is a student then x is clever”.
Quantifiers
(∃𝐱) 𝐌 𝐱 →𝐆 𝐱

We symbolize the word “some” by “(∃x)”.

We have two predicates “x is a student” and then “x is clever”.
So, we will define two statements.
Here, “(∃x)” is called a quantifier and is used for words “some”
and “there exists”.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 50

 Every integer is either positive or negative.
𝐌 𝐱 ∶ 𝐱 is an integer. 𝐆 𝐱 ∶ 𝐱 is either positive or negative.
for every x, if x is an integer then x is either positive or negative”.
Quantifiers
(∀𝐱) 𝐌 𝐱 →𝐆 𝐱

We symbolize the word “every” by “(∀x)” or “(x)”.

We have two predicates “x is an integer” and then “x is either
positive or negative”.
Here, “(∀x)” or “(x)” is called a quantifier and is also used for
words “all”, “every” and “any”.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 51

Method 3 ⟹ Example 1
Que: Let P x ∶ x is a person. F x , y ∶ x is the father of y. M x , y ∶ x is the
Que: mother of y. Write the predicate “x is the father of the mother of y.”.
Sol:
 Let us assume that x is the father of a person z.
 Then, the statement looks like “x is the father of z and z is the mother of y.”
 So, the statement function looks like “there exists z, z is a person and x is the
father of z and z is the mother of y.”

∃𝐳 𝐏(𝐳)
𝐏 𝐅 𝐱, 𝐳𝐳) ∧ 𝐌(𝐳,
𝐳 ∧ 𝐅(𝐱, 𝐌 𝐳, 𝐲)
𝐲
 Thus, the statement formula is ∃z P z ∧ F x, z ∧ M z, y .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 52
Method 3 ⟹ Example 2
Que: Symbolize the expression “All the world loves a lover.”.
Sol: The statement means that “All the persons loves a lover.”.
 Here, we symbolize “all” by quantifier “(∀x)” or “(x)”.
 Now, we have three predicate “x is a person”, “x is lover” and “x loves y”.
𝐌 𝐱 ∶ 𝐱 is a person. 𝐆 𝐱 ∶ 𝐱 is a lover. 𝐑 𝐱 , 𝐲 ∶ 𝐱 loves 𝐲.
 If we denote x as a person and y as a lover, then expression looks like,
For all 𝐱, if 𝐱 is a person, for all 𝐲, if 𝐲 is a person and a lover, then 𝐱 loves 𝐲.

∀𝐱 𝐌 𝐱 → ∀𝐲 𝐌 𝐲 ∧ 𝐆 𝐲 → 𝐑(𝐱 , 𝐲)
 Thus, the statement formula is (∀x)M(x) → ∀y M y ∧ G y → R(x, y).

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 53

 In statement formula, if variable occurs in quantifier then it
has
bound occurrence otherwise free occurrence.
Free & bound
variables
Formula immediately following quantifier is called the scope
of
the quantifier.
∀𝐱 𝐏 𝐱 ∧ 𝐐 𝐱
So, occurrence of x in P(x) is bound occurrence.
Also, occurrence of x in Q(x) is bound occurrence.
Here, the scope of quantifier (∀x) is P x ∧ Q x .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 54
 In statement formula, if variable occurs in quantifier then it
has
bound occurrence otherwise free occurrence.
Free & bound
variables
Formula immediately following quantifier is called the scope
of
the quantifier.
∀𝐱 𝐏 𝐱 ∧ 𝐐 𝐱
So, occurrence of x in P(x) is bound occurrence.
But, occurrence of x in Q(x) is free occurrence.
Here, the scope of quantifier (∀x) is P x .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 55
Method 3 ⟹ Example 4
Que: Indicate the variables that are free and bound. Also, show the scope of
Que: quantifiers.
Sol:
 First three occurrence of x are bound. But, last occurrence of x in Q(x) is free.
 Here, the scope of quantifier x is P x ∧ R x and the scope of second
quantifier x is P x .

 First three occurrence of x are bound. But, last occurrence of x in Q(x) is free.
 Here, the scope of quantifier x is P x ∧ ∃x Q x .
 While, the scope of ∃x is Q x , and the scope of x is P x .

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 56

Method 3 ⟹ Example 4(continue)
Que: Indicate the variables that are free and bound. Also, show the scope of
Que: quantifiers.
Sol:

 First three occurrence of x are bound. But, last occurrence of x in S(x) is free.

 Here, the scope of quantifier x is P x ⇄ Q x ∧ ∃x R x and the scope of

second quantifier ∃x is R x .

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 57

 If statement function is true over a limited set or class then that
set or class is called the universe of discourse or the domain of
individuals or simply the universe.
The universe of
discourse
𝐏 𝐱 ∶ 𝐱 is a number. 𝐐 𝐱 ∶ 𝐱 is either positive or negative.

“for all x, if x is a number, then x is either positive or negative.”

Statement function 1 is true over E.

𝐄 = {−𝟑, 𝟏, 𝐚, 𝐛} So, E is the universe of discourse of 1.

# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 58

 If statement function is true over a limited set or class then that
set or class is called the universe of discourse or the domain of
individuals or simply the universe.
The universe of
discourse
𝐏 𝐱 ∶ 𝐱 is a number. 𝐐 𝐱 ∶ 𝐱 is either positive or negative.

“for all x, x is a number and x is either positive or negative.”

Statement function 2 is not true over E.

𝐄 = {−𝟑, 𝟏, 𝐚, 𝐛} So, E is not the universe of discourse of
2.
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 59
Method 3 ⟹ Example 5(a)
Que: Find the truth values of x P x ∨ Q x , where P x ∶ x = 1, Q x ∶ x = 2,
Que: and the universe of discourse E = 1,2 .
Sol:
 P(x) is true.  P(x) is false.
 Q(x) is false.  Q(x) is true.
 So, truth value of statement function  So, truth value of statement function
is is
𝐏 𝐱 ∨𝐐 𝐱 =𝐓∨𝐅 𝐏 𝐱 ∨𝐐 𝐱 =𝐅∨𝐓
=𝐓 =𝐓
 So, the truth values of given statement function are true over the universe of
discourse E = 1,2 .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 60
Method 3 ⟹ Example 5(c)
Que: Find the truth value of ∃x P x ⟶ Q x ∧ T , where P x ∶ x > 2,
Q x ∶ x = 0, and T is any tautology, with the universe of discourse 𝐸 = 1 .
Sol:
 P(x) is false.
 Q(x) is false.
 So, truth value of statement function is ∃𝐱 𝐏 𝐱 ⟶ 𝐐 𝐱 ∧𝐓
= 𝐓 ∧𝐓
=𝐓
 So, the truth value of given statement function is true over the universe of
discourse E = 1 .
# 3140708 (DM)  Unit 2 – Propositional logic & Predicate logic 61