7.

Mathematical Logic/Propositional Logic 

The rules of mathematical logic specify methods of reasoning mathematical statements.

Greek philosopher, Aristotle, was the pioneer of logical reasoning. Logical reasoning
provides the theoretical base for many areas of mathematics and consequently computer
science. It has many practical applications in computer science like design of computing
machines, artificial intelligence, definition of data structures for programming languages etc.

Propositional Logic is concerned with statements to which the truth values, "true" and
"false", can be assigned. The purpose is to analyze these statements either individually or in
a composite manner.

Definition: Propositional Logic 

A proposition is a collection of declarative statements that has either a truth value "true" or a
truth value "false". A propositional consists of propositional variables and connectives. We
denote the propositional variables by capital letters (A, B, etc). The connectives connect the
propositional variables.

Some examples of Propositions are given below −

 "Man is Mortal", it returns truth value "TRUE"

 "12 + 9 = 3 − 2", it returns truth value "FALSE"

The following is not a Proposition −

 "A is less than 2". It is because unless we give a specific value of A, we cannot say
whether the statement is true or false.

Propositional Calculus:

Propositional calculus also known as propositional logic is the branch of

mathematical logic concerned with the study of propositions (whether they are
true or false) that are formed by other propositions with the use of logical
connectives and how their values depends on the truth values of their
components.

Page 1 of 12
Therefore, “A proposition is a declarative sentence that is either true or false,
but not both”

Example 1:

1. Dhaka is in Bangladesh.
2. 1+1=2
3. 2+2=3
4. Prof. Farzana Islam is a VC of DU.
5. 9<6
6. X = 2 is a solution of X2 =4

Above all are propositions, 1, 2 and 6 are TRUE, whereas 3, 4 and 5 are
FALSE. But all are declarative.

Example 2:

1. Where are you going?

2. Do your homework.

These are not propositions because they are not declarative sentence.

3. X + 1 = 2
4. X + Y = Z

These are also not propositions because, they are neither true nor false, as
the value of X, Y, Z are not assigned.

Basic Logical Operation:

There are three basic logical operations such as:

1. Negation:“not” → Symbol: ¬ , ¬p
2. Conjunction: “and” → Symbol: ^ , p ^ q
3. Disjunction: “or” → Symbol: v, p∨p

1. Negation:
Let p be any proposition, then negation of p is defined as –p, as the false
of p. If p is true then –p is false. And if p is false, then –p is true.

Page 2 of 12
 Truth table for Negation proposition:

P ¬p
T F
F T

Example 3:

Today is Friday: negation is,“Today is not Friday” (It is not Friday today).

Symbolically: ¬p and real “not p”.

2. Conjunction: p ^ q

Any two propositions can be combined by the word “and” to form a

compound proposition called the conjunction of the original propositions.
Symbolically, p ^ q → read “p and q”, since p ^ q is a proposition, it has a
truth value, and this truth value depends only on the truth values of p and
q. That means, if p and q both are true, then p ^ q is true; otherwise p ^ q
is false.

Truth table of conjunction proposition:

p q p^q
T T T
T F F
F T F
F F F

Example 4:

1. Paris is in France and 2 + 2 = 4. (True)

2. Paris is in France and 2 + 2 = 5. (False)
3. Paris is in England and 2 + 2 = 4. (False)
4. Paris is in England and 2 + 2 = 5. (False)

3. Disjunction: p∨q

Page 3 of 12
 Any two propositions can be combined by the word “or” to form a
compound proposition called the disjunction of the original propositions.

Symbolically → p∨q , read “p or q”, denotes the disjunction of p and q.

The truth values of p∨q depends only the truth values of p and q as
follows.
Truth table of disjunction proposition:

P q p∨q
T T T
T F T
F T T
F F F

If p and q are false, then p∨q is false; otherwise p∨q is true.

*In Example 4; only the last statement (4) is false. All other statements
are true, since at least one of its sub statements is true.

Other Operations

4. Exclusive OR: p⊕ q

The exclusive of p and q denoted by p⊕q, is the proposition, that is true

when exactly one of p and q is true and is false otherwise.

Truth table of exclusive proposition

P q p⊕q
T T F
T F T
F T T
F F F

Example 5:

1. Paris is in France and 2 + 2 = 4. (False)

2. Paris is in France and 2 + 2 = 5. (True)

Page 4 of 12
 3. Paris is in England and 2 + 2 = 4. (True)
4. Paris is in England and 2 + 2 = 5. (False)

5. Implication: p → q / conditional (p only if q) or (p implies q)

The implication p → q is the proposition that is false when -

p is true and q is false and true otherwise.

In the implication p is called the hypothesis (or antecedent or promised)

and q is called the conclusion (or consequence)

The truth table for the Implication

P q P→q
T T T
T F F
F T T
F F T

Example 6:

1. Paris is in France and 2 + 2 = 4. (True)

2. Paris is in France and 2 + 2 = 5. (False)
3. Paris is in England and 2 + 2 = 4. (True)
4. Paris is in England and 2 + 2 = 5. (True)
An implication is sometimes called a conditional statement.

6. Biconditional p ↔ q (p is and only if q)

The biconditional p ↔ q is the proposition that is true when

p and q have the same truth/false values and is false otherwise.

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

Page 5 of 12
 In Example 4; statement 1, 4 is satisfied by biconditional.

6.1 Converse: The proposition q → q is called the converse of p → q.

6.2 Contrapositive: The contrapositive of (p → q) is (¬q → ¬p).

6.3 Inverse: The inverse of (p → q) is (¬p → ¬q)

6.1 Converse truth table

p Q p →q q→p
T T T T
T F F T
F T T F
F F T T
 False when q is true p is false

6.2 Contrapositive truth table

p q Q ¬q p ¬p
→q (¬q) → (¬p)
T T T
T F F
F T T
F F T
p
T T F F T
T F T F F
F T F T T
F F T T T

6.3 Inverse truth table

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

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

Page 6 of 12
 7. Compound propositions
Many propositions are composite, that is composed of sub
propositions and various connectives discussed subsequently. Such
composite propositions are called compound postpositions.

A proposition is said to be primitive if it cannot be broken down into

simpler proposition, that is, it is not composite.

Example 7:

1. Dhaka is in Bangladesh.
2. 1+1=2
3. 2+2=3
4. Prof. Farzana Islam is a VC of DU.
5. 9<6
6. X = 2 is a solution of X2 = 4
7. Where are you going?
8. Do your homework.

The above proposition (1) through (6) are all primitive propositions; They
cannot be broken down into simpler propositions. (7) and (8) are not primitive
because they are not propositions because they are not declarative statements.

8. Contradiction:

A compound proposition that is always false is called a contradiction.

p ¬p p ^ (¬p)
T F F
F T F

9. Tautology:

A compound proposition that is always true no matter what the truth

values of the proposition that occur in it, called a tautology.

P ¬p p∨(¬p)
T F T

Page 7 of 12
 F T T

10. Contingency:

A composition that is neither a tautology no a contradiction is called a

contingency.

p q p→q
T T T
T F F
F T T
F F T
Here the result values are neither True or False consistently.

Logical equivalences of implications (→)

1 p→q ¬p∨q
2 p→q ¬q → ¬p
3 p∨q ¬p → q
4 p^q ¬(p → ¬q)
5 ¬(p → q) p ^ ¬q
6 (p → q) ^ (p → r) p → (q ^ r)
7 (p → r) ^ (q → r) (p∨q) → r
8 (p → q)∨(p → r) p → (q∨r)
9 (p → r)∨(q → r) (p ^ q) → r

Logical equivalences of biconditionals

1 p↔q (p → q) ^ (q → p)
2 p↔q ¬q ↔ ¬p
3 p↔q (p → q)∨(q → p)
4 ¬(p ↔ q) p ↔ ¬q

Q. Verify that the proposition p∨¬(p ^ q) is a tautology.

Ans: fig. 4.13
Q. Show that the propositions ¬(p ^ q) and (¬p∨¬q) are logically equivalent.
p ¬p q ¬q p^q ¬(p ^ q) (¬p∨¬q)
T F T F T F F

Page 8 of 12
 T F F T F T T
F T T F F T T
F T F T F T T

Laws of Algebra of proposition

Name of the Law Equivalence

1 Identity laws p ^ True = p
p∨False = p
2 Domination laws p∨True = True
p ^ False = False
3 Idempotent laws p∨p = p
p^p=p
4 Double negation law ¬(¬p) = p
5 Communicative laws p^q=q^p
p∨q = q∨p
6 Associative laws (p∨q)∨r = p∨(q∨r)
(p ^ q) ^ r = p ^ (q ^ r)
7 Distributive laws p∨(q ^ r) = (p∨q) ^ (p∨r)
p ^ (q∨r) = (p ^ q)∨(p ^ r)
8 De Morgan’s laws ¬(p ^ q) = ¬p∨¬q
¬(p∨q) = ¬p ^ ¬q
9 Absorption laws p∨(p ^ q) = p
p ^ (p∨q) = p
10 Negation laws p∨¬p = True
p ^ ¬p = False

Q. Show that: [(p → q) ^ (q → r)] → (p → r) is a tautology

p q r (p → q) (q → r) ^ (p → r) [(p → q) ^ (q → r)] → (p → r)
T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F F F F T
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 T T T T T

Page 9 of 12
So, [(p → q) ^ (q → r)] → (p → r) is a tautology.

Propositional Function:
Let A be a given set. A propositional function (or an open sentence or
conditional) defined on A is an expression P(x), which has the property that P(a)
is true of false for each of a∈A .
That is P(x) becomes a statement (with a truth value) whenever any element
a ∈A is substituted for the variable x.
The set A is called the domain of P(x) and the set Tp of all elements of A for
which P(a) is true is called the Truth set of P(x).
Mathematical notation:
Tp = {x: x∈ A, P(x) is true}
or
Tp = {x: P(x)}

P(x) could be true:

For all x∈A, for some x∈A, for no x∈A.
Example:
Find the truth set of each propositional function P(x) defined on the set N of
positive integers (+ve).
(a) x + 2 > 7
(b) x + 5 < 3
(c) x + 5 > 1
Solution:
(a) Let P(x) be x + 2 > 7.

It’s truth set is {x:x∈N, x + 2 > 7} = {6, 7, 8, 9, …….}.

That is P(x) → the truth set is consisting of all integers greater than 5.

(b) Let P(x) be x + 5 < 3.

It’s truth set is {x:x∈N, x + 5 <3} = { ϕ}.

That is the truth set is the empty set. Or P(x) is not true for any positive
integer in N.

Page 10 of 12
 (c) Let P(x) be x + 5 >1.

It’s truth set is {x:x∈N, x + 5 >1} = N. That is P(x) is true for all positive
integer in N.

Duality Principle

Duality principle set states that for any true statement, the dual statement obtained by
interchanging unions into intersections (and vice versa) and interchanging Universal set into
Null set (and vice versa) is also true. If dual of any statement is the statement itself, it is
said self-dual statement.

Example − The dual of (A∩B)∪C is (A∪B)∩C

Normal Forms
We can convert any proposition in two normal forms −

 Conjunctive normal form

 Disjunctive normal form

Conjunctive Normal Form

A compound statement is in conjunctive normal form if it is obtained by operating AND
among variables (negation of variables included) connected with ORs. In terms of set
operations, it is a compound statement obtained by Intersection among variables connected
with Unions.

Examples

Disjunctive Normal Form

A compound statement is in conjunctive normal form if it is obtained by operating OR
among variables (negation of variables included) connected with ANDs. In terms of set

Page 11 of 12
operations, it is a compound statement obtained by Union among variables connected with
Intersections.

Examples

Page 12 of 12