Logic and Propositional Logic

• Mathematical logic or logic is the

discipline that deals with the methods
of reasoning.
• It provides rules and techniques for
determining whether a given argument
or mathematical proof or conclusion in
a scientific theory is valid or not.
1
 Uses of Logic
• Logic is used concerned with studying arguments
and conclusions.
• Logic is used in mathematics to prove theorems.
• Logic is used to draw conclusions from
experiments in physical sciences.
• Logic is used in our everyday life to solve many
types of problems.
• Logic is used in computer science to verify
correctness of programs.

2
 Propositions and Compound
Propositions
• A proposition (statement) is a declarative sentence
which is either true or false, but not both. Examples:
1. Paris is in France.
2. 1 + 1 = 2
3. 2 + 2 = 3
4. London is in Denmark.
5. 9 < 6
6. x = 2 is a solution of x2 = 4
7. Where are you going?
8. Do your homework.
3
 Compound Propositions
• Many propositions are composite, that is,
composed of sub-propositions and various
connectives. Such composite propositions are
called compound propositions.
• A proposition is said to be primitive if it
cannot be broken down into simpler
propositions, that is, if it is not composite.

4
 Compound Propositions
1. “Roses are red and violets are blue” is a
compound proposition with sub-propositions.
“Roses are red” and “Violets are blue”.
2. “John is intelligent or studies every night”
is a compound proposition with sub-propositions
“John is intelligent” and “John studies every
night”.

5
 Basic Logic Operations
1. Conjunction- English word (and)

2. Disjunction - English word (or)

3. Negation - English word (not)

6
 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, denotes conjunction of 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.

7
 Conjunction (p ^ q)
• If p and q are true, the p ^ q is true; otherwise
p ^ q is false. The truth value of p ^ q may be
equivalently by the truth table as
p Q p^q
True True True
True False False
False True False
False False False
8
 Conjunction (p ^ q)
• Example
1. Paris is in France and 2 + 2 = 4
2. Paris is in France and 2 + 2 = 5
3. Paris is in England and 2 + 2 = 4
4. Paris is in England and 2 + 2 = 5
Only 1 is True. Each of the other statements is
false, since at least one of its sub-statements is
false.
9
 Conjunction (p ^ q)
• Example: Translate the following statement
into symbolic form.

• Statement: Ramu and Raghu went to school.

• Solution P: Ramu went to school
Q: Raghu went to school
Symbolic Form p ^ q

10
 Disjunction (p ∨ q)
• 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.

11
 Disjunction (p ∨ q)
• The truth value of p ∨ q depends upon on the
truth values of p and q as follows.
p Q p∨q
True True True
True False True
False True True
False False False

• p ∨ q is false only in the fourth case when both

p and q are false.
12
 Disjunction (p ∨ q)
• Example
1. Paris is in France or 2 + 2 = 4
2. Paris is in France or 2 + 2 = 5
3. Paris is in England or 2 + 2 = 4
4. Paris is in England or 2 + 2 = 5
Only 4 is False. Each of the other statements is
True, since at least one of its sub-statements is
true.
13
 Disjunction (p ∨ q)
1. Inclusive OR / Inclusive Disjunction
(One or the other or both)
Example: “Sonmoy is an architect or Ashok is a
draftman”
2. Exclusive OR / Exclusive Disjunction
(One or the other, but not both)
Example: “He will go to Harvard or to Yale”
“I will buy a computer or a car next year”

14
 Negation (¬p, ~p)
• Negation of P,

“It is not the case that - - - ” or

“It is false that - - -”

If P is true, then ¬p, ~p is false; and

If P is false, then ¬p, ~p is true.

15
 Negation (¬p, ~p)
• Example:
1. Paris is in France.
2. It is not the case that Paris is in France.
3. Paris is not in France.
Statement 2 and 3 are each the negation of
Statement 1.

A1. 2 + 2 = 5
A2. It is not the case that 2 + 2 = 5
A3. 2 + 2 ≠ 5
16
 Logical Operations
• And, OR and NOT are not completely
standardized.
1. p & q, p.q, pq for p ^ q
2. p + q for p ∨ q
3. ~p for ¬p

17
 Composite Propositions
Q1. Give the truth value of the conjunction on
the following propositions.
a. “3 ÷ 5 = 2”, “Ram is in Delhi”
b. “5 + 7 = 12”, x2 ≥ 0
c. “x2 – 3x + 5 = 0 has two solutions”. “9 ≥ 7”.
 Composite Propositions
a. Let p: 3 ÷ 5 = 2”
q: “Ram is in Delhi”
The truth value of p is False
The truth value of q is True
Therefore truth value of p ^ q = False.

b. Let p: “5 + 7 = 12”
q: x2 ≥ 0
The truth value of p is True
The truth value of q is True
Therefore truth value of p ^ q = True.

c. Let p: “x2 – 3x + 5 = 0 has two solutions”

q: “9 ≥ 7”.
The truth value of p is True
The truth value of q is True
Therefore truth value of p ^ q = True.
 Conditional Statements

If p and q are any two statements P Q,

read as
“If P, then Q” is called a conditional
statement.
Statement P is called the antecedent, and Q
is called the consequent in P Q.
is called the sign of implication.
 Conditional Statements
Example: Let
P: Amulya works hard
Q: Amulya will pass the exam
Then, P Q.
If Amulya works hard, then she will pass the exam.
The condition p q is false only when the first part
p is true and the second part q is false.
Accordingly, when p is false, the conditional p q
is trueregardless of the truth value of q.
 Conditional Statements
Example: Let
P: Amulya works hard
Q: Amulya will pass the exam
Then, P Q.

p q p q
True True True
True False False
False True True
False False True
 Bidirectional Statements
(P Q) (P Q)

• If P and Q are any two statements, then

P Q is read as “P if and only if Q” and
abbreviated as “P iff Q” is called a bi-
conditional statement.
• The statement P Q has the truth value
whenever both P and Q have identical
values.
 Bidirectional Statements
• Truth Table (P Q)

P Q (P Q )
True True True
True False False
False True False
False False True
 Bidirectional Statements
• The bi-conditional P Q is the conjunction of
the conditionals P Q and Q P i.e.
(P Q) ^ (Q P) is an alternate notation
for P Q.
 Bi-directional Statements
• (P Q) ^ (Q P)
P Q (P Q) (Q P) (P Q) ^ (Q P)

True True

True False

False True

False False
 Bi-directional Statements
• (P Q) ^ (Q P)
P Q (P Q) (Q P) (P Q) ^ (Q P)

True True True

True False False

False True True

False False True

 Bi-directional Statements
• (P Q) ^ (Q P)
P Q (P Q) (Q P) (P Q) ^ (Q P)

True True True True

True False False True

False True True False

False False True True

 Bi-directional Statements
• (P Q) ^ (Q P)
P Q (P Q) (Q P) (P Q) ^ (Q P)

True True True True True

True False False True False

False True True False False

False False True True True

 Bi-directional Statements
• Example: Two lines are parallel if and only
if they have the same slope.
• Question
Write the following statement in symbolic form.

• If either Mr. Srinu takes calculus or Mr. Swami

takes Graph Theory then Mr. Mahesh will take
Computer Programming.
 Bi-directional Statements
Solution: Denoting the statements as:
• S: Mr. Srinu takes Calculus.
• W: Mr. Swami takes Graph Theory
• M: Mr. Mahesh takes Computer Programming

The above statements can be symbolized as

(S ∨ W) M
 Assignment
1. Write down propositions p and q for which
q p is true but p q is false.
 Exercise
Q. Check whether the following sentences are
statements or not.
a. Come in!
b. What are you doing?
c. 7 is a lucky number.
d. This statement you are reading is false.
 Exercise
Q. Check whether the following sentences are
statements or not.
a. Come in! Exclamation
b. What are you doing? Question
c. 7 is a lucky number. True/False
d. This statement you are reading is false.
True/False
Above sentences 1 and 2 not propositions
 Truth Table
• A table showing all the possible truth values of
a statement formula for each possible
combination of the truth values of the
component statements is called the truth table
of the formula.
• If there are ‘n’ distinct components in the
statement formula, then 2n possible
combinations of truth values in order to obtain
the truth table.
 Truth Table
• For example, if any statement formula have two component
statements namely P and Q, 22 possible combinations of truth
values must be considered.
• Example 1: Construct the truth table for P ^ ~P
Solution:

P ~P P ^ ~P

True False False

False True False

 Truth Table
Example 2: Construct the truth table for P ∨ ~P
Solution:

P ~P P ∨ ~P

True False True

False True True

 Truth Table
• P Q
Example: Let, P: Amulya works hard
Q: Amulya will pass the exam

p q p q
True True
True False
False True
False False
 Truth Table
• P Q
Example: Let, P: Amulya works hard
Q: Amulya will pass the exam

p q p q
True True True
True False False
False True True
False False True
 Truth Table
1. Construct the truth table for P (Q R)
3 statements P, Q and R, so there are 23 = 8
different sets of truth value assignments for
variables P, Q and R.
 Truth Table
P Q R Q R P (Q R)
True True True
True True False
True False True
True False False
False True True
False True False
False False True
False False False
 Truth Table
P Q R Q R P (Q R)
True True True True
True True False False
True False True True
True False False True
False True True True
False True False False
False False True True
False False False True
 Truth Table
P Q R Q R P (Q R)
True True True True True
True True False False False
True False True True True
True False False True True
False True True True True
False True False False True
False False True True True
False False False True True
 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True

True False

False True

False False
 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False

True False False True

False True True False

False False True True

 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False True

True False False True False

False True True False False

False False True True False

 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False True False

True False False True False False

False True True False False True

False False True True False False

 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False True False False

True False False True False False True

False True True False False True False

False False True True False False False

 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False True False False False

True False False True False False True False

False True True False False True False False

False False True True False False False True

 Truth Table
• Construct the truth table for the formula:
(P ^ Q) ∨ (~P ^ Q) ∨ (P ^ ~Q) ∨ (~P ^ ~Q) = I
P Q ~P ~Q P^Q (~P ^ Q P ^ ~Q ~P ^ ~Q I

True True False False True False False False True

True False False True False False True False True

False True True False False True False False True

False False True True False False False True True

 Truth Table
• For the proposition ~ (P ^ ~Q), draw the
truth table.
P Q ~Q (P ^ ~Q), ~ (P ^ ~Q),

True True

True False

False True

False False
 Truth Table
• For the proposition ~ (P ^ ~Q), draw the
truth table.
P Q ~Q (P ^ ~Q), ~ (P ^ ~Q),

True True False

True False True

False True False

False False True

 Truth Table
• For the proposition ~ (P ^ ~Q), draw the
truth table.
P Q ~Q (P ^ ~Q), ~ (P ^ ~Q),

True True False False True

True False True True False

False True False False True

False False True False True

 (P ∨ Q ) ^ (P R) ^ (Q S)
is equivalent to
a. S^R

b. S R

c. S∨R

d. None of the above

 (P ∨ Q ) ^ (P R) ^ (Q S)
a. S^R

b. S R

c. S ∨ R Correct Answer

d. None of the above

 Tautologies and Contradictions
• Some propositions P (p, q, _ _ _) contain only T
in the last column of their truth tables or
they are true for any truth values in their
variables. Such propositions are called
tautologies.
• Analogously, a proposition P (p, q, _ _ _) is called
a contradiction if it contains only F in the last
column of their truth table, or if it is false for any
truth values of its variables.
• For example, tautologies “p or not p”
 Tautologies and Contradictions
• Tautologies “p or not p” i.e. p ∨ ~p
p ~p p ∨ ~p
True False True
False True True

• Tautologies “p and not p” i.e. p ^ ~p

p ~p p ^ ~p

True False False

False True False

 Tautologies and Contradictions
• Verify whether (P ∨ Q) P is tautology
Solution
P Q P∨Q P∨Q P

True True

True False

False True

False False
 Tautologies and Contradictions
• Verify whether (P ∨ Q) P is tautology
Solution
P Q P∨Q P∨Q P

True True True

True False True

False True True

False False False

 Tautologies and Contradictions
• Verify whether (P ∨ Q) P is tautology
Solution (Since, last column contains one false, the formula is
not a tautology)

P Q P∨Q P∨Q P

True True True True

True False True True

False True True False

False False False True

 Tautologies and Contradictions
• Verify whether is a (P ^ (P Q) Q)
tautology.
P Q P Q P ^(P Q) (P ^(P Q)) Q

True True

True False

False True

False False
 Tautologies and Contradictions
• Verify whether is a (P ^ (P Q) Q)
tautology.
P Q P Q P ^(P Q) (P ^(P Q)) Q

True True True

True False False

False True False

False False True

 Tautologies and Contradictions
• Verify whether is a (P ^ (P Q) Q)
tautology.
P Q P Q P ^(P Q) (P ^(P Q)) Q

True True True True

True False False False

False True False False

False False True False

 Tautologies and Contradictions
• Verify whether is a (P ^ (P Q) Q)
tautology. All entries are True, so tautology
P Q P Q P ^(P Q) (P ^(P Q)) Q

True True True True True

True False False False True

False True False False True

False False True False True

 Which of the following are tautologies?

a. ((P ∨ Q) ^ Q) Q

b. (P ∨ (P Q)) P

c. ((P ∨ Q) ^ P) Q

d. ((P ∨ Q) ^ ~P) Q
 Which of the following are tautologies?

a. ((P ∨ Q) ^ Q) Q Tautology

b. (P ∨ (P Q)) P Contradiction

c. ((P ∨ Q) ^ P) Q Contradiction

d. ((P ∨ Q) ^ ~P) Q Tautology