DISCRETE MATHEMATICS

Mathematical Logic
Introduction

Many proofs in Mathematics and many algorithms in computer science use

logical expressions such as “If P then Q”. We use different types of sentences
say declarative, interrogative, exclamatory and imperative to express our
ideas. But in mathematics, sentences which are declarative and about which it
is possible to judge, whether they are true or false but not both are used to
draw conclusions and to prove theorems. Such sentences are statements. This
value associated with the truthfulness or falsity of a statement is called its
truth values.

A Proposition (Statement): It is a well defined argument, which is either true or

false, but not both.
Ex:- 1) Chennai is in Tamil Nadu.
2) 5+4=9
3) Close the door.
4) Where are you going (or) what are you doing?
1,2 are Statements, where as 3,4 are not statements: neither true nor false.

Statements are denoted by P,Q,R,… (or) p,q,r, …

Note:- T, F will be used for True and False respectively. Sometimes use 1, 0 for T,
F.

Atomic Statement:- Any statement which do not contain any of the connectives is
called atomic statement. It is also called as primary (or) primitive statement.

Connectives:-
There are five basic connectives which are frequently used

S.No. Symbol Name Connective word

1 ∼ or ⏋ Negation Not
2 ∧ Conjunction And
3 ∨ Disjunction Or
4 → Implication (or) Conditional Implies or If….then
 5 ↔ Bi-conditional If and only if

Negation: The negation of a statement is generally formed by introducing the word

“not” at a proper place in the statement or by prefixing the statement with the
phrase “ It is not the case that or it is not true that”.

If P denotes a statement, then the negation of P is written as

P P
T F
F T

∼P: Nikhil is not playing badminton.

Ex:- P: Nikhil is playing badminton

Or ∼P: It is not the case that Nikhil is playing badminton.

∼P: There are not 12 months in a year.

Ex: P: There are 12 months in a year.

0r ∼P: It is not true that there are 12 months in a year.

Note:- Alternative symbols that can be used to represent negation are “∼” , “a bar”
( ) or “Not”.

Thus, ⏋P is written as ∼P or 𝑃 or Not P

“𝑃 ∧ 𝑄”, which read as “ P and Q” . The statement 𝑃 ∧ 𝑄 have truth value T

Conjunction:- Conjunction of two statements P and Q is denoted by the statement

whenever both P and Q have the truth value T otherwise it has truth value F.

Truth table for conjunction:

P
T T T
 T F F
F T F
F F F

∴ 𝑃 ∧ 𝑄, 𝑄 ∧ 𝑃 have same truth values.

Note: A is symmetric.

Ex: P: Today is holiday.

𝑃 ∧ 𝑄: Today is holiday & there are fruits in this room.

Q: There are fruits in this room

Ex: P: It is raining today , Q: There are 20 tables in this room.

𝑃 ∧ 𝑄: It is raining today and there are 20 tables in this room

statement 𝑃 ∨ 𝑄, which is read as “P or Q” (or) P Join Q. The truth value of 𝑃

Disjunction:- Disjunction of two statements P and Q may be denoted by the

∨ 𝑄 is true whenever P is true (or) Q is true (or) both P, Q are true, Otherwise 𝑃
∨ 𝑄 is False.
Truth Table for Disjunction:

P Q 𝐏∨𝐐
T T T
T F T
F T T
F F F

Note: Disjunction is Symmetric. i.e., 𝑃 ∨ 𝑄, 𝑄 ∨ 𝑃 have same truth values.

Ex: I shall either watch the cricket on TV or go to the stadium.

Molecular ( compound or composite) Statements:

Those statements which contain one or more atomic statements and some
connectives are called Molecular Statements.
using P & Q are ∼ P, 𝑃 ∧ 𝑄, (𝑃 ∧ 𝑄) ∨ (∼ P)
Ex: Let P, Q be any two statements, Some of the molecular statements formed by

Conditional Statement:

If P & Q are any two statements, the statement 𝑃 → 𝑄 which we read “If P then
Q” is called a conditional statement or implication statement. The statement 𝑃 →
𝑄 has a truth value F when Q has the truth value F & P has the truth value T,
otherwise it has the Truth Value T.

Truth table for conditional statement:

P Q 𝐏→𝐐
T T T
T F F
F T T
F F T

Here the statement P is called antecedent & Q is called consequent in 𝑃 → 𝑄.

Ex: If I get the book then I begin to read.

Symbolic form is 𝐏 → 𝐐
P: I get the book, Q: I began to read

Note: The Statement 𝑃 → 𝑄 may be read as

(i) If P, then Q ii) Q if P iii) Q is necessary for P
iv) P is sufficient for Q v) P only if Q vi) P implies Q
vii) Q whenever P

Write the following statement in symbolic form.

Statement: If either John prefers tea or Jim prefers Coffee, then Rita prefers milk.
Solution:
Let A: John prefers tea, B: Jim prefers Coffee,C: Rita prefers milk.
Symbolic form is (AVB) →C
Statement: The crop will be destroyed if there is a flood.
Solution:
Let the statements be denoted as
A: The crop will be destroyed
B: There is a flood

be destroyed”. Now it is easy to symbolize it as B → 𝐴

It is better to rewrite the given statement as “If there is a flood, then the crop will

Statement: If the sun is shining today, then 2+3 > 4.

In symbolic form is P → 𝑄
Solution: Let P: The sun is shinig today, Q:2+3 > 4

If P & Q are any two statements, then the statement𝑃 ⟷ 𝑄, which is read as “P if
Bi-conditional Statements:

and only if Q”, is called a biconditional statement. The statement 𝑃 ⟷ 𝑄 has

truth value T whenever both P & Q have identical truth values; otherwise its truth
value is F.

Truth table for Bi-conditional statements:

P Q 𝐏⟷𝐐
T T T
T F F
F T F
F F T

Note: The statement 𝑃 ⟷ 𝑄 may be read as

i) P if and only if Q
ii) If P then Q & conversely
iii) P is necessary & sufficient for
Q.
Ex: Vijayawada is in A.P. if and only if 9 ÷ 3 =3

Let P:Ravi is rich, Q:Ravi is happy

Write each of the following in symbolic form

i) Ravi is poor but happy -⌈P˄Q
 ii) Ravi is neither rich nor happy- -⌈P˄⌈Q
iii) Ravi is rich and unhappy- P˄⌈Q

1) Ramu reads Newsweek or the new Yorker but not time.

Write each of the following in symbolic form:

2) Ramu reads Newsweek and New Yorker , or he does not Newsweek and Time.
3) It is not true that
4) It is not true that

Solution:
1. (P ˅Q)

2) (P

3)
Well-formed formulas:
A string of symbols containing the statement variables, connectives and parenthesis
is said to be well-formed formula if it can be obtained by finitely
many applications of the rules
: A statement variable standing alone is a well-formed formula.
: If A is a well-formed formula, then A is a well-formed formula.
: If A & B are well-formed formulas, then (A B), (A B), (A B) & (A B)
are well formed formulas.

Ex: -1) P Q is not well-formed formula but (P Q) is a well-formed formula.

2)( →( Q) is not well-formed formula because Q is not statement variable.
3) ( is not well-formed formed but ( is a well-formed formula.

Construction of Truth Tables:

A Truth Table consists of columns and rows. The number of columns depend upon
the numbers of sample propositions and connectives used to form a compound
proposition. The number of rows in a truth table are found on the basis of simple
propositions.
For example, if there are two simple propositions, there will be =4 rows. For n
simple propositions, the total number of rows will be .

Construct the Truth table for P (P Q)

P Q P Q P (P Q)

T T T T

T F F F

F T T F

F F T F

Construct the Truth table for P Q , P Q

P Q P P Q P Q

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

Construct the Truth table for

P Q R [(P ∧ Q) V ⎾R]
T T T T F T T
T T F T T T T
T F T F F F F
T F F F T T T
F T T F F F T
F T F F T T F
F F T F F F T
F F F F T T F

Construct the Truth Table for (P ∧ Q) V (Q ∧ R) V (R ∧ P)

P Q R (P ∧ Q) (Q ∧ R) (R ∧ P) (P ∧ Q) V (Q ∧ R) (P ∧ Q) V (Q ∧ R) V (R ∧
P)
T T T T T T T T
T T F T F F F T
T F T F F T F T
T F F F F F F F
F T T F T F T T
F T F F F F F F
F F T F F F F F
F F F F F F F F

Construct the Truth Table for ( R

P Q R (P V Q) ∧ ⎾ R) R ( R
T T T T F F T F
T T F T T T F F
T F T T F F T F
T F F T T T T T
F T T T F F T F
F T F T T T F F
F F T F F F T F
F F F F T F T F

Construct the Truth Table for (P Q) Q R)

P Q R P Q Q R (P Q) Q R)
T T T T T T
T T F T F F
T F T F T F
T F F F T F
F T T T T T
F T F T F F
F F T T T T
F F F T T T

Construct the Truth Table for P P Q)

P Q P P Q P P Q)

T T F T F

T F F F F
F T T T T

F F T T T

Construct the Truth Table for(P ∧ (Q⟶ R)) ⟶ (Q⟶ R)

Solution:

P Q R Q⟶ P ∧ (Q⟶ (P ∧ ((Q⟶ R)) ⟶ (Q⟶ R)

R R))
T T T T T T
T T F F F T
T F T T T T
T F F T T T
F T T T F T
F T F F F T
F F T T F T
F F F T F T

Two logical expressions are said to be equivalent if they have the same truth value in all cases. Sometimes
this fact helps in proving a mathematical result by replacing one expression with another equivalent
expression, without changing the truth value of the original compound proposition.
Types of propositions based on Truth values
There are three types of propositions when classified according to their truth values

1. Tautology – A proposition which is always true, is called a tautology.

2. Contradiction – A proposition which is always false, is called a contradiction.
3. Contingency – A proposition that is neither a tautology nor a contradiction is called a contingency

Tautology:-

A statement formula that is true regardless of the truth values of the statements that
replace the variables in it is called a Universally valid formula (or) a Tautology (or)
a logical truth.
The formula PV~P represents a Tautology.

P ~P PV~P
T F T
F T T

Note: -If all the entries in the last column of a table are T, then given formula is a
Tautology.

Contradiction:- A statement formula which is false regardless of the truth values

of the statements which replace the variables in it is called a contradiction.

The Formula P

P ~P P P
T F F
F T F

Note:- i) P
i) P

Contingency:- A proposition that is neither a Tautology nor a contradiction is

called a Contingency.
Write the statement in the symbolic form & find whether it is a Tautology or not. If
I am hungry & thirsty, then I am hungry.
Solution:
Let P: I am hungry Q: I am thirsty
In symbolic form (P Q)

(P Q)
P Q P Q
T T T T
T F F T
F T F T
F F F T

So it is a Tautology.

Check whether the following formulas are tautologies or not (P Q)

P Q PVQ (P Q)
T T T T
T F T T
F T T F
F F F T

Since all the entries in the last column of the truth table of (P Q) are not T, the
formula is not a tautology.

Check whether P V [ (
Q ((P ∧ Q) P V [ ((P ∧ Q)]
T T T F T

T F F T T

F T F T T

F F F T T
Since all the entries in the last column of the truth table are T,the formula is a
Tautology.
Check whether the formula P (PVQ) is a

Prove that ~( ~ ) ~

Q ~P ~ ~ ~( ~ ) ~( ~ ) ~
T T F F T F T

T F F T T F T

F T T F F T T

F F T T T F T

Therefore the given formula is a

Q R) P P ) is a Tautology.

P P (P P Q R) P
P Q R Q R P Q R)
P
T T T T T T T T T
T T F T T T F T T
T F T T T F T T T
T F F T F F F F T
F T T F F F F F T
F T F T F F F F T
F F T T F F F F T
F F F F F F F F T
Show that the proposition ( ~ (~ ~ )

Q ~P ~ ~ ~ ~ ( ~ (~ ~ ) ( ~ (~ ~ )
T T F F T F F T
T F F T T T T T
F T T F F T F T
F F T T T T T T

Since all the entries in the last column of the truth table are T,the formula is a
Tautology.

EQUIVALENCE OF FORMULAS

Two formulas A & B are said to be equivalent to each other if and only if is
a Tautology.

The equivalence of two formulas A & B is denoted by B, which is read as A is

equivalent to B.

Note:-  is only symbol, but not connective.

A B if and only if the truth values of A, B are same.

i.e., the final columns in the truth tables of A, B are same
i.e., truth tables of A,B are same.
Equivalence relation is symmetric & transitive.

Ex: i) ∼(∼P) is equivalent to P

ii)P∧P is equivalent to P iii)PV∼P
is equivalent to QV∼Q
iv)(P∧∼P)VQ is equivalent to Q

Method I(truth Table Method):

One method to determine whether any two statement formulas are equivalent is to
construct their truth tables.

1)(P∧∼P)VQ  𝑄
Prove the following:

Since truth values are same, therefore (P∧∼P)VQ  𝑄

2) (P → 𝑄)  (∼PVQ)

Since truth values are same, therefore (P → 𝑄)  (∼PVQ)

Show that P

P (Q ∧ R)
Solution:
P Q R (P V Q)
T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F
Since the truth values of given formulas are same, therefore they are Logically Equivalent. Show

that

Since the truth values of given formulas are same, therefore they are Logically
Equivalent.

Method II (Replacement Process)

In this method ,we replace any part of a statement formula by another equivalent
formula
Ex: 
Equivalent Formulas:

Let P,Q,R be any 3 statements, Then all possible formulas may be written as:

1.  

2. 


3. 

4. 


5. 
 
6. 


7.


8. 


9.




P→ Q  P Q
→R Q R

Sl.No Logical Equivalence involving implications

P→ Q  P Q
1

2 P→Q Q→ P

3 P Q P → Q

4 P Q  (P → Q)

5 → 

6 → →  →(

7 →R →  →

8 →Q →  →(

9 →R →  →

10 P↔Q →Q →

11 P↔Q ↔ Q
 12 P↔Q Q (∼P⋀ ∼Q)

13 P↔Q) P↔ Q

1)
 





(P⋀Q)→R (Law of implication) Hence
proved.

2) a)P → (Q→ P)  ∼P → (P → Q) Solution:

Show the following equivalences:



 

 
  ( =T Negation
 law)


 

→ (Q ⋁ R)  (P → Q) ⋁ (P → R)
Therefore, the two given formulas are equivalent. b) P

Solution:-

 

(P → Q) ⋁ (P → R)


 (∼P ⋁ Q) ⋁ (∼P ⋁ R)

(o

 (∼P ⋁ Q) ⋁ (∼P ⋁ R) (associative

(by law of r) 

  (P → Q) ⋁ (P → R) (by law of

3) Show that [∼P⋀(∼Q⋀R)]⋁[(Q⋀R)⋁(P⋀R)]  R

Solution:-
Let us consider [∼P⋀(∼Q⋀R)]⋁[(Q⋀R)⋁(P⋀R)]


[∼(PVQ)⋀R]⋁[(P⋁Q)⋀R] (Commutative law)

 T R ( P P=T Negation law)  (Identity law) Hence proved.
4)Show that ((P Q) ( P ( Q R))) ( P Q) ( P R) is a tautology.
Solution:-
By using Demorgans laws, We have
P  
( P Q) ( P R)  (P Q) (P R)  ((P Q) (P R))
( P ( Q R))
 ( P (Q


((P Q) (P R))
 T (since P P  T)
Therefore given formula is a tautology.
5)Show that P 

 P
 P 


 



6)Show that P P 
 P P P= P )

 ( Q ⋀ ∼P)
P P) P) P P=F

 P) ( 
 
Hence proved.

7)
 P
 P
P )

 (by law of implication)

 P (by law of implication)
 P
1) From (1) & (2) the given two formulas are not logically equivalent.

By using the truth tables

Q
P R

T T T T T T T
T T F T F F F
T F T F T T T
T F F F T T T
F T T T T T T
F T F T F F T
F F T T T T T
F F F T T F T
The two formulas are not equivalent Duality
Law:
Two formulas A and A* are said to be duals of each other if either one can be
obtained from the other by replacing
 A*, its duals, is obtained by replacing T by F and F by T
in
addition to the above mentioned interchanges.
Write the duals of
1 )(P Q)

(P Q)
2)(P Q) T
(P Q)

A*
A*:
TAUTOLOGICAL IMPLICATIONS

: Any set of connectives in which every formula can

P
T T F
T F T
F T T
F F T

P
T T F
 T F F
F T F

Basic properties of the connectives NAND and NOR 1) 𝑷

F F T

↑ 𝑸 = 𝑸 ↑ 𝑷 2) 𝑷 ↓ 𝑸 = 𝑸 ↓ 𝑷 (Commutative law)
2) The connectives ↑ & ↓ are not associative.

𝑷 ↑ 𝑸  ∼(P∧Q)  ∼P ⋁ ∼Q


 





𝑃 ⊕ 𝑄 (𝑜𝑟)𝑃 ∨ 𝑄, is the proposition that is true when exactly one of P & Q is

Exclusive OR:- The Exclusive OR (or) XOR of P & Q is denoted by

true, but not both and is false otherwise.

Truth Table for the Exclusive OR:

P
T T F
T F T
F T T
F F F