GOA COLLEGE OF ENGINEERING

“BHAUSAHEB BANDODKAR TECHNICAL EDUCATION COMPLEX"

FARMAGUDI, PONDA- GOA - INDIA

MATHEMATICAL FOUNDATIONS OF
COMPUTER SCIENCE M.E.(ITE) SEM-I
PROPOSITIONAL CALCULUS

DEVELOPED BY MATHEMATICS FACULTY

DEPARTMENT OF SCIENCE & HUMANITIES
GOA COLLEGE OF ENGINEERING
 PROPOSITIONAL CALCULUS
TOPICS TO BE COVERED:
➢PROPOSITIONS OR STATEMENTS

➢CONJUNCTION, DISJUNCTION, NEGATION, CONDITIONAL, BICONDITIONAL

➢TRUTH TABLES AND WELL FORMED FORMULA

➢LOGICAL EQUIVALENCES

➢NORMAL FORMS

➢THEORY OF INFERENCE

➢FUNCTIONALLY COMPLETE SET OF CONNECTIVES

 PROPOSITIONAL CALCULUS
• A proposition or statement is a declarative sentence that is either true or
false.
• Examples:
i) The sun rises in the west----False
ii) 2+4=6------True
iii) {5,6} 𝑖𝑠 𝑎 𝑠𝑢𝑏𝑠𝑒𝑡 𝑜𝑓 7,6,5 -----True
iv) Every rectangle is a square.------False
• The following sentences are not propositions or statements.
i) Do you speak in Hindi?
ii) Close the door.
iii) What a hot today!
(Questions , commands and exclamations are not propositions.
• Propositions are denoted by p, q, r……
 PROPOSITIONAL CALCULUS
• The two propositional constants true and false are denoted by T and F
respectively.
• Atomic Proposition:
A proposition consisting of only a single propositional variable or single propositional
constant is called an atomic proposition.
• Compound Proposition:
A proposition obtained from the combination of two or more propositions or by
negating single proposition is called a compound proposition.

• Connectives: The words and phrases(or symbols) used to form compound

proposition are called connectives.
 PROPOSITIONAL CALCULUS
• Negation:
If 𝑝 is any proposition, then negation of 𝑝 is denoted by ~𝑝 or ℸ𝑝 𝑜𝑟 𝑝ҧ , is a
proposition which is false when 𝑝 is true and true when 𝑝 is false.
• It is obtained by inserting the word ‘not’ or ‘It is not the case that’ in an
appropriate place.
Examples: 𝑝: Paris is in France.
~𝑝:Paris is not in France.

𝑞: All students are intelligent

~𝑞: Not all students are intelligent
:Some students are not intelligent.
:At least one student is not intelligent.
:There exist students who are not intelligent.
 PROPOSITIONAL CALCULUS
• Conjunction:
If 𝑝 and 𝑞 are two statements, then the conjunction of 𝑝 and 𝑞 denoted by ‘𝑝 ∧ 𝑞 ′
𝑎𝑛𝑑 𝑟𝑒𝑎𝑑 𝑎𝑠 ′p and q′ is a statement which is true when both p and q are true and
false otherwise.
Examples:
𝑝 :Ram is healthy. 𝑞: Ram has blue eyes.
𝑝 ∧ 𝑞:Ram is healthy and has blue eyes.

𝑝 :It is cold. 𝑞: 𝐼𝑡 𝑖𝑠 𝑟𝑎𝑖𝑛𝑖𝑛𝑔.

𝑝 ∧ 𝑞: It is cold and raining.
 PROPOSITIONAL CALCULUS
• Disjunction:
If 𝑝 𝑎𝑛𝑑 𝑞 𝑎𝑟𝑒 𝑡𝑤𝑜 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡𝑠 , 𝑡ℎ𝑒 𝑑𝑖𝑠𝑗𝑢𝑛𝑐𝑡𝑖𝑜𝑛 𝑜𝑓 𝑝 𝑎𝑛𝑑 𝑞 𝑑𝑒𝑛𝑜𝑡𝑒𝑑
𝑏𝑦 p ∨ 𝑞 𝑎𝑛𝑑 𝑟𝑒𝑎𝑑 𝑎𝑠 "p or q“ 𝑖𝑠 𝑎 𝑠𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡 𝑤ℎ𝑖𝑐ℎ 𝑖𝑠 𝑡𝑟𝑢𝑒 𝑖𝑓 𝑎𝑡𝑙𝑒𝑎𝑠𝑡
𝑜𝑛𝑒 𝑜𝑓 𝑝 𝑜𝑟 𝑞 𝑖𝑠 𝑡𝑟𝑢𝑒.
• Note: “or” is used in inclusive sense.
Examples:
𝑝: 𝑇ℎ𝑒 𝑓𝑜𝑜𝑑 𝑖𝑠 𝑔𝑜𝑜𝑑. 𝑞: 𝑇ℎ𝑒 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑖𝑠 𝑔𝑜𝑜𝑑.
p ∨ 𝑞: 𝑇ℎ𝑒 𝑓𝑜𝑜𝑑 𝑖𝑠 𝑔𝑜𝑜𝑑 𝑜𝑟 𝑠𝑒𝑟𝑣𝑖𝑐𝑒 𝑖𝑠 𝑔𝑜𝑜𝑑.

𝑝: 𝐼 𝑤𝑖𝑙𝑙 𝑏𝑢𝑦 𝑎 𝑏𝑖𝑘𝑒. 𝑞: 𝐼 𝑤𝑖𝑙𝑙 𝑏𝑢𝑦 𝑎 𝑐𝑎𝑟.

p ∨ 𝑞: 𝐼 𝑤𝑖𝑙𝑙 𝑏𝑢𝑦 𝑎 𝑏𝑖𝑘𝑒 𝑜𝑟 𝑎 𝑐𝑎𝑟.

Note : When we combine any two sentences to form a conjunction or disjunction, there
is no requirement that the two sentences be related in content or subject matter.
 PROPOSITIONAL CALCULUS
• Conditional Proposition (Implication):
If 𝑝 𝑎𝑛𝑑 𝑞 𝑎𝑟𝑒 propositions , the compound proposition “𝐼𝑓 𝑝 𝑡ℎ𝑒𝑛 𝑞" 𝑑𝑒𝑛𝑜𝑡𝑒𝑑 𝑏𝑦
𝑝 → 𝑞 𝑜𝑟 𝑝 ⇒ 𝑞 is called a conditional proposition.
The conditional proposition 𝑝 → 𝑞 is false only when 𝑝 is true and 𝑞 𝑖𝑠 𝑓𝑎𝑙𝑠𝑒,
𝑎𝑛𝑑 𝑡𝑟𝑢𝑒 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒.
• 𝑝 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑎𝑛𝑡𝑒𝑐𝑒𝑑𝑒𝑛𝑡 𝑜𝑟 ℎ𝑦𝑝𝑜𝑡ℎ𝑒𝑠𝑖𝑠 𝑎𝑛𝑑 𝑞 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑐𝑜𝑛𝑠𝑒𝑞𝑢𝑒𝑛𝑡
𝑜𝑟 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛.
Examples:
𝑝: I am elected 𝑞: 𝐼 𝑤𝑖𝑙𝑙 𝑙𝑜𝑤𝑒𝑟 𝑡𝑎𝑥𝑒𝑠.
𝑝 ⟶ 𝑞: 𝐼𝑓 𝐼 𝑎𝑚 𝑒𝑙𝑒𝑐𝑡𝑒𝑑 , 𝑡ℎ𝑒𝑛 𝐼 𝑤𝑖𝑙𝑙 𝑙𝑜𝑤𝑒𝑟 𝑡𝑎𝑥𝑒𝑠.

𝑝: x is an integer 𝑞: 𝑥 𝑖𝑠 𝑎 𝑟𝑎𝑡𝑖𝑜𝑛𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟.

𝑝 ⟶ 𝑞: 𝐼𝑓 𝑥 𝑖𝑠 𝑎𝑛 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 , 𝑡ℎ𝑒𝑛 𝑥 𝑖𝑠 𝑎 𝑟𝑎𝑡𝑖𝑜𝑛𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟.
 PROPOSITIONAL CALCULUS
• Note: The connective “If,then “ can also be read as follows:
i) 𝑝 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑞.
ii) 𝑝 is sufficient for q.
iii) 𝑝 only if q.
iv) 𝑞 𝑖𝑠 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦 𝑓𝑜𝑟 𝑝
v) 𝑞 𝑖𝑓 𝑝
vi) 𝑞 𝑓𝑜𝑙𝑙𝑜𝑤𝑠 𝑓𝑟𝑜𝑚 𝑝
vii) 𝑞 𝑖𝑠 𝑎 𝑐𝑜𝑛𝑠𝑒𝑞𝑢𝑒𝑛𝑐𝑒 𝑜𝑓 𝑝.

• Related Implications:
Consider the conditional 𝑝 ⟶ 𝑞.
i) 𝑞 ⟶ 𝑝 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑐𝑜𝑛𝑣𝑒𝑟𝑠𝑒 𝑜𝑓 𝑝 ⟶ 𝑞.
ii) ~𝑞 ⟶ ~𝑝 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑡ℎ𝑒 𝑐𝑜𝑛𝑡𝑟𝑎𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑜𝑓 𝑝 ⟶ 𝑞.
iii) ~𝑝 ⟶ ~𝑞 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑 𝑡ℎ𝑒 𝑖𝑛𝑣𝑒𝑟𝑠𝑒 𝑜𝑓𝑝 ⟶ 𝑞
 PROPOSITIONAL CALCULUS
• Biconditional:
If 𝑝 and 𝑞 𝑎𝑟𝑒 𝑝𝑟𝑜𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛𝑠 , 𝑡ℎ𝑒 𝑐𝑜𝑚𝑝𝑜𝑢𝑛𝑑 𝑝𝑟𝑜𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛
"𝑝 , 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓, 𝑞“ denoted by 𝑝 ⟷ 𝑞 𝑜𝑟 𝑝 ⟺ 𝑞 𝑖𝑠 𝑐𝑎𝑙𝑙𝑒𝑑
𝑏𝑖𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛𝑎𝑙 𝑝𝑟𝑜𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛. The biconditional 𝑝 ⟷ 𝑞 is true when both
𝑝 𝑎𝑛𝑑 𝑞 𝑎𝑟𝑒 𝑡𝑟𝑢𝑒 𝑜𝑟 𝑏𝑜𝑡ℎ 𝑝 𝑎𝑛𝑑 𝑞 𝑎𝑟𝑒 𝑓𝑎𝑙𝑠𝑒.
• Examples:
𝑝: 𝐻𝑒 𝑠𝑤𝑖𝑚𝑠 𝑞: 𝑇ℎ𝑒 𝑤𝑎𝑡𝑒𝑟 𝑖𝑠 𝑤𝑎𝑟𝑚.
𝑝 ⟷ 𝑞: 𝐻𝑒 𝑠𝑤𝑖𝑚𝑠 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑡ℎ𝑒 𝑤𝑎𝑡𝑒𝑟 𝑖𝑠 𝑤𝑎𝑟𝑚.
• The connective “If and only if” can also be read as
𝑝 𝑖𝑠 𝑛𝑒𝑐𝑒𝑠𝑠𝑎𝑟𝑦 𝑎𝑛𝑑 𝑠𝑢𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑓𝑜𝑟 𝑞.
• The Precedence of connectives: The order is ~, ∧ , ∨ , ⟶ , ⟷.
 PROPOSITIONAL CALCULUS
Truth table: A truth table is a table that shows the truth value of a
compound proposition for all possible cases.
Negation:

𝑝 𝑞 𝑝∧𝑞 𝑝∨𝑞 𝑝⟶𝑞 𝑝⟷𝑞

T T T T T T
T F F T F F
F T F T T F
F F F F T T
 PROPOSITIONAL CALCULUS
Example 1: Let p, q, r represent the following propositions,
p: It is raining
q: The sun is shining
r: There are clouds in the sky
Symbolize the following statements.
(1) If it is raining, then there are clouds in the sky
(2) If it is not raining, then the sun is not shining and there are clouds in the sky.
(3) The sun is shining if and only if it is not raining.
Symbolic form: (1) 𝑝 → 𝑟
(2) ~𝑝 → (~𝑞 ∧ 𝑟)
(3) q ⟷ ~𝑝
 PROPOSITIONAL CALCULUS
Example 2: Symbolize the following statements:
(1) If the moon is out and it is not snowing, then Ram goes out for a walk.
(2) If the moon is out, then if it is not snowing, Ram goes out for a walk.
(3) It is not the case that Ram goes out for a walk if and only if it is not snowing or the
moon is out.
Solution: Let the propositions be,
p: The moon is out
q: It is snowing
r: Ram goes out for a walk.
Symbolic form: (1) (𝑝 ∧∼ 𝑞) → 𝑟
(2) 𝑝 → (∼ 𝑞 → 𝑟)
(3) ∼ (r ⟷ ~𝑞 ∨ 𝑝 )
 PROPOSITIONAL CALCULUS
• Statement Formula(Propositional Formula)(Compound propositional
Formula):A statement formula is a string consisting of variables,
parenthesis and connective symbols.
• Well formed formula: A statement formula (simply a formula) is called
well formed if it can be generated by the following rules:
i) A statement variable p standing alone is a well formed formula.
ii) If p is well formed formula , then ~𝑝 is a well formed formula.
iii) If p and q are well formed then 𝑝 ∧ 𝑞, 𝑝 ∨ 𝑞 , 𝑝 ⟶ 𝑞 and 𝑝 ⟷ 𝑞 are
well formed formula.
iv) A string of symbols is a well formed formula iff it is obtained by finite
application of the rule (i) ,(ii) and (iii)
Ex.~(𝑝 ∨ 𝑞) , ~ 𝑝 ∧ 𝑞 , 𝑝 ⟶ 𝑝 ∨ 𝑞 are well formed formulas.
 PROPOSITIONAL CALCULUS
Constructing the truth tables:
Ex. Construct the truth tables for the compound propositions
𝑖) 𝑝 ∧ (~𝑝 ∨ 𝑞)
 PROPOSITIONAL CALCULUS
𝑖𝑖) ~𝑝 ∨ (~𝑞 ∧ 𝑟)
 PROPOSITIONAL CALCULUS
• Tautology : A statement formula that is always true for all possible truth values of its
variables is called tautology.
• Examples: ~𝑝 ∨ 𝑝 , 𝑝 ∧ 𝐪 ⟶ p
• Contradiction: A statement formula that is always false for all values of its variables is
called contradiction.
• Examples: 𝑝 ∧ ~𝑝
• Contingency: A statement formula that is neither a tautology nor a contradiction is
called contingency.
• Logical equivalence: If two propositions P(p , q ,…) and Q(p , q,…) where p , q,…are
propositional variables have same truth values for every possible combination of
variables , they are said to be logically equivalent or simply equivalent.
• It is denoted by 𝑃 ⟺ 𝑄 𝑜𝑟 𝑃 ≡ 𝑄.
• Alternately : Two propositions P and Q are logically equivalent if and only if the
biconditional , P ⟷ 𝑄 𝑖𝑠 𝑎 𝑡𝑎𝑢𝑡𝑜𝑙𝑜𝑔𝑦.
• i.e. P ↔ 𝑄 ≡ 𝑇.
 PROPOSITIONAL CALCULUS
Examples:
1. 𝑝 ⟶ 𝑞 ≡ ~𝑝 ∨ 𝑞 ≡ ~𝑞 ⟶ ~𝑝
 PROPOSITIONAL CALCULUS
2. 𝑝 ⟷ 𝑞 ≡ 𝑝 ⟶ 𝑞 ∧ 𝑞 ⟶ 𝑝
≡ (~𝑝 ∨ 𝑞) ∧ (~𝑞 ∨ 𝑝)
≡ (𝑝 ∧ 𝑞) ∨ (~𝑝 ∧ ~𝑞)
 PROPOSITIONAL CALCULUS
• Substitution Instances : Let P and Q be two formulae . If P can be obtained
from Q by substitution of formulas for some variable of Q , then P is said
to be a substitution instance of Q , provided the same formula is
substituted for each occurrence of that variable.
• Ex. Let Q: 𝑝 ⟶ 𝑝 ∧ r
Substitute s ⟷ 𝑡 𝑓𝑜𝑟 𝑝 , 𝑤𝑒 𝑜𝑏𝑡𝑎𝑖𝑛𝑒𝑑
P: 𝑠 ⟷ 𝑡 ⟶ 𝑠 ⟷ 𝑡 ∧ r
P is the substitution instance of Q.
 PROPOSITIONAL CALCULUS
Example: An island has two tribes of natives . Any native from the first tribe always tells the truth, while any
native from the second tribe always lies. You arrive at the island and ask a native if there is gold on the island .
He replies “There is gold on the island if and only if I always tell the truth .” Use propositional calculus to
determine if there is gold on the island.
Solution:
Let p: He always tell the truth
q: There is a gold on the island.
P q 𝑞↔𝑝
The answer of native is “ 𝑞 ↔ 𝑝 ”.
T T T
Suppose the native belongs to the first tribe i.e He always speaks the truth
Therefore, p is T. T F F
His answer will also be true. i.e 𝑞 ↔ 𝑝 is T F T F
Therefore, q is T. F F T
Suppose the native belongs to second tribes i.e. he always lies.
Therefore, p is F.
His answer will also be lie. i.e. 𝑞 ↔ 𝑝 is F
Therefore, q is T.
Thus in both the cases , we conclude that there is gold on the island.
 PROPOSITIONAL CALCULUS
Example:There are two restaurants next to each other .One has the sign that says
“ Good food is not cheap “ and the other “cheap food is not good “ .
Are the signs saying the same things?
Solution:
Let p: Food is good.
q: Food is cheap
The first sign is 𝑝 → ~𝑞 𝑎𝑛𝑑 𝑡ℎ𝑒 𝑠𝑒𝑐𝑜𝑛𝑑 𝑠𝑖𝑔𝑛 𝑖𝑠 𝑞 → ~𝑝

Since 𝑝 → ~𝑞 ≡ 𝑞 → ~𝑝 , both the signs are saying the same thing.

 PROPOSITIONAL CALCULUS
Algebra of propositions:
1) Idempotent Laws:
𝑎) 𝑝 ∨ 𝑝 ≡ 𝑝 𝑏) 𝑝 ∧ 𝑝 ≡ 𝑝
2) Associative Laws:
𝑎) 𝑝 ∨ (𝑞 ∨ 𝑟) ≡ (𝑝 ∨ q) ∨ 𝑟 b) 𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ q) ∧ 𝑟
3) Commutative Laws:
𝑎) 𝑝 ∨ 𝑞 ≡ 𝑞 ∨ p b) 𝑝 ∧ 𝑞 ≡ 𝑞 ∧ p
4) Distributive Laws:
𝑎) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ q) ∧ 𝑝 ∨ r b) 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ q) ∨ (𝑝 ∧ r)
5) Identity Laws:
𝑎) 𝑝 ∨ 𝐹 ≡ 𝑝 𝑏) 𝑝 ∧ 𝑇 ≡ 𝑝
 PROPOSITIONAL CALCULUS
6)Domination laws:
a) 𝑝 ∨ 𝑇 ≡ 𝑇 𝑏) 𝑝 ∧ 𝐹 ≡ 𝐹
7)Complement Laws:
a) 𝑝 ∨ ~𝑝 ≡ 𝑇 𝑏) 𝑝 ∧ ~𝑝 ≡ 𝐹
8)De-Morgan’s Laws:
a) ~ p ∨ 𝑞 ≡ ~𝑝 ∧ ~𝑞 b) ~ p ∧ 𝑞 ≡ ~𝑝 ∨ ~𝑞
9) Double negation law:
~ ~𝑝 ≡ 𝑝
10)Absorption laws:
a) p ∨ p ∧ 𝑞 ≡ 𝑝 b) p ∧ p ∨ 𝑞 ≡ 𝑝
All the above laws can be proved by using truth tables.
 PROPOSITIONAL CALCULUS
• Without using truth tables , prove the following.
1. 𝑝 ∧ 𝑞 ≡ 𝑝 ∨∼ 𝑞 ∧ 𝑞
Proof: R.H.S = 𝑝 ∨∼ 𝑞 ∧ 𝑞
≡ 𝑝 ∧ 𝑞 ∨ (∼ 𝑞 ∧ 𝑞)
≡ 𝑝 ∧ 𝑞 ∨ 𝐹 ≡ 𝑝 ∧ 𝑞 = 𝐿. 𝐻. 𝑆

2. (𝑝 ∧ 𝑞) ∨∼ 𝑞 ≡ 𝑝 ∨∼ 𝑞
Proof: L.H.S = (𝑝 ∧ 𝑞) ∨∼ 𝑞 ≡ (𝑝 ∨∼ 𝑞) ∧ (𝑞 ∨∼ 𝑞)
≡ (𝑝 ∨∼ 𝑞) ∧ 𝑇
≡ 𝑝 ∨∼ 𝑞 = 𝑅. 𝐻. 𝑆
 PROPOSITIONAL CALCULUS
3.∼ 𝑝 ∧ 𝑞 → ∼ 𝑝 ∨ ∼ 𝑝 ∨ 𝑞 ≡∼ 𝑝 ∨ 𝑞
Solution: ∼ 𝑝 ∧ 𝑞 → ∼ 𝑝 ∨ ∼ 𝑝 ∨ 𝑞
≡∼ 𝑝 ∧ 𝑞 → ∼ 𝑝 ∨∼ 𝑝 ∨ 𝑞
≡∼ 𝑝 ∧ 𝑞 → ∼ 𝑝 ∨ 𝑞
≡∼∼ 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∨ 𝑞
≡ 𝑝∧𝑞 ∨ ∼𝑝∨𝑞
≡ [ 𝑝 ∧ 𝑞 ∨∼ 𝑝] ∨ 𝑞
≡ [ 𝑝 ∨∼ 𝑝 ∧ 𝑞 ∨∼ 𝑝 ] ∨ 𝑞
≡ [𝑇 ∧ 𝑞 ∨∼ 𝑝 ] ∨ 𝑞
≡ 𝑞 ∨∼ 𝑝 ∨ 𝑞
≡ ∼𝑝∨𝑞 ∨𝑞
≡∼ 𝑝 ∨ q ∨ 𝑞 ≡∼ 𝑝 ∨ 𝑞
 PROPOSITIONAL CALCULUS
4. 𝑝 ∨ 𝑞 ∧ ∼ 𝑝 ∧ ∼ 𝑝 ∧ 𝑞 ≡∼ 𝑝 ∧ 𝑞
Solution: 𝑝 ∨ 𝑞 ∧ ∼ 𝑝 ∧ ∼ 𝑝 ∧ 𝑞
≡ 𝑝 ∨ 𝑞 ∧ ( ∼ 𝑝 ∧∼ 𝑝) ∧ 𝑞
≡ 𝑝∨𝑞 ∧ ∼𝑝∧𝑞
≡ [ 𝑝 ∨ 𝑞 ∧∼ 𝑝] ∧ 𝑞
≡ [ 𝑝 ∧∼ 𝑝 ∨ 𝑞 ∧∼ 𝑝 ] ∧ 𝑞
≡ 𝐹 ∨ 𝑞 ∧∼ 𝑝 ∧ 𝑞
≡ (𝑞 ∧∼ 𝑝) ∧ 𝑞
≡ (∼ 𝑝 ∧ 𝑞) ∧ 𝑞
≡∼𝑝∧ 𝑞∧q
≡∼ 𝑝 ∧ 𝑞
 PROPOSITIONAL CALCULUS
5. 𝑞 ∨ 𝑝 ∧∼ 𝑞 ∨ ∼ 𝑝 ∧∼ 𝑞 ≡ 𝑇
Solution: 𝑞 ∨ 𝑝 ∧∼ 𝑞 ∨ ∼ 𝑝 ∧∼ 𝑞 ≡ 𝑞 ∨ 𝑝 ∨∼ 𝑝 ∧∼ 𝑞
≡ 𝑞 ∨ 𝑇 ∧∼ 𝑞
≡ 𝑞 ∨∼ 𝑞 ≡ 𝑇
6. 𝑝 → 𝑞 ∨ 𝑟 ≡ 𝑝 → 𝑞 ∨ 𝑝 → 𝑟
Solution: 𝑝 → 𝑞 ∨ 𝑝 → 𝑟 ≡ ∼ 𝑝 ∨ 𝑞 ∨ ∼ 𝑝 ∨ 𝑟
≡∼ 𝑝 ∨ ∼ 𝑝 ∨ 𝑞 ∨ 𝑟
≡ ∼ 𝑝 ∨∼ 𝑝 ∨ 𝑞 ∨ 𝑟
≡∼ 𝑝 ∨ 𝑞 ∨ 𝑟
≡𝑝→ 𝑞∨𝑟
 PROPOSITIONAL CALCULUS
7. ∼ 𝑝 ∧ ∼ 𝑞 ∧ 𝑟 ∨ 𝑞 ∧ 𝑟 ∨ 𝑝 ∧ 𝑟 ≡ 𝑟
Solution: ∼ 𝑝 ∧ ∼ 𝑞 ∧ 𝑟 ∨ 𝑞 ∧ 𝑟 ∨ 𝑝 ∧ 𝑟
≡ ∼ 𝑝 ∧∼ 𝑞 ∧ 𝑟 ∨ 𝑞 ∧ 𝑟 ∨ 𝑝 ∧ 𝑟
≡ ∼ 𝑝 ∧∼ 𝑞 ∧ 𝑟 ∨ 𝑞 ∨ 𝑝 ∧ 𝑟
≡ ∼ 𝑝∨𝑞 ∧𝑟 ∨ 𝑝∨𝑞 ∧𝑟
≡ ∼ 𝑝∨𝑞 ∨ 𝑝∨𝑞 ∧𝑟
≡𝑇∧𝑟
≡𝑟
• Duality: Two formulas 𝑃 𝑎𝑛𝑑 𝑃∗ are called duals of each other if either can be
obtained by interchanging ∧ 𝑏𝑦 ∨ ,∨ 𝑏𝑦 ∧ , 𝑇 𝑏𝑦 𝐹 𝑎𝑛𝑑 𝐹 𝑏𝑦 𝑇.
• Duality principle: If two statement formulas are equivalent then their duals are
equivalent.
 PROPOSITIONAL CALCULUS
Normal Forms:
Definition : A conjunction of propositions and their negations is called a
fundamental conjunction or elementary product.
Ex. 𝑝 , ~𝑝 , 𝑝 ∧ 𝑞 , ∼ 𝑝 ∧ 𝑞 , ∼ 𝑝 ∧∼ 𝑞 , 𝑝 ∧∼ 𝑞 𝑒𝑡𝑐.
Definition:A disjunction of propositions and their negations is called
fundamental disjunction or elementary sum.
Ex. . 𝑝 , ~𝑝 , 𝑝 ∨ 𝑞 , ∼ 𝑝 ∨ 𝑞 , ∼ 𝑝 ∨∼ 𝑞 , 𝑝 ∨∼ 𝑞 𝑒𝑡𝑐.
Note: The words “product” and “sum” is used in place of the connectives
conjunction and disjunction.
 PROPOSITIONAL CALCULUS
• Disjunctive Normal form(Sum of products): A statement form which is a
disjunction of fundamental conjunctions is called disjunctive normal form (dnf)
Ex. 𝑝 ∨ 𝑞 ∧ 𝑟 , 𝑝 ∧ 𝑞 ∨ ∼ 𝑞 ∧ 𝑟

• Conjunctive Normal Form(Product of sums): A statements form which is a

conjunction of fundamental disjunctions is called conjunctive normal form (cnf).
Ex. 𝑝 ∧ 𝑞 ∨ 𝑟 , (∼ 𝑝 ∨ 𝑞) ∧ (𝑞 ∨ 𝑟) ∧ (∼ 𝑝 ∨∼ 𝑟)

• Procedure to obtain disjunctive/conjunctive normal form :

i) Replace all the → 𝑎𝑛𝑑 ↔ by an equivalent expression containing the
connectives ∧ ,∨ 𝑎𝑛𝑑 ∼ 𝑜𝑛𝑙𝑦.
ii) Eliminate ∼ before sums and products by using double negation or De-
Morgan’s laws.
iii) Apply the distributive law until the required form is obtained.
 PROPOSITIONAL CALCULUS
• Examples: Obtain the disjunctive normal form of
1) 𝑝 ∧ 𝑝 → 𝑞 ≡ 𝑝 ∧ ∼ 𝑝 ∨ 𝑞
≡ (𝑝 ∧∼ 𝑝) ∨ (𝑝 ∧ 𝑞)______dnf

2) 𝑝 ∨ ∼ 𝑝 → 𝑞 ∨ 𝑞 →∼ 𝑟 ≡ 𝑝 ∨ ∼ 𝑝 → 𝑞 ∨∼ 𝑞 ∨∼ 𝑟
≡ 𝑝 ∨ 𝑝 ∨ 𝑞 ∨∼ 𝑞 ∨∼ 𝑟
≡ 𝑝 ∨ 𝑝 ∨ 𝑞 ∨∼ 𝑞 ∨∼ 𝑟
≡ 𝑝 ∨ 𝑞 ∨∼ 𝑞 ∨∼ 𝑟______dnf
 PROPOSITIONAL CALCULUS
3) 𝑝 → 𝑝 → 𝑞 ∧∼ ∼ 𝑞 ∨∼ 𝑝 ≡𝑝→ ∼𝑝∨𝑞 ∧ 𝑞∧𝑝
≡∼ 𝑝 ∨ ∼𝑝∨𝑞 ∧ 𝑝∧𝑞
≡∼ 𝑝 ∨ ∼ 𝑝 ∨ 𝑞 ∧ 𝑝 ∧ 𝑞
≡∼ 𝑝 ∨ ∼ 𝑝 ∧ 𝑝 ∨ 𝑞 ∧ 𝑝 ∧ 𝑞
≡∼ 𝑝 ∨ 𝐹 ∨ 𝑝 ∧ 𝑞 ∧ 𝑞
≡∼ 𝑝 ∨ 𝑝 ∧ 𝑞
≡∼ 𝑝 ∨ (𝑝 ∧ 𝑞) ______dnf
 PROPOSITIONAL CALCULUS
Obtain the conjunctive normal form of
1. 𝑝 ∧ (𝑝 → 𝑞) ≡ 𝑝 ∧ (∼ 𝑝 ∨ 𝑞)_________𝑐𝑛𝑓

2. 𝑞 ∨ 𝑝 ∧ 𝑞 ∧∼ 𝑝 ∨ 𝑟 ∧ 𝑞 ≡ 𝑞 ∨ 𝑝 ∧ 𝑞 ∧ ∼ 𝑝 ∨ 𝑟 ∨∼ 𝑞
≡ 𝑞 ∧ ∼ 𝑝 ∧∼ 𝑟 ∨∼ 𝑞
≡ 𝑞 ∧ ∼ 𝑝 ∨∼ 𝑞 ∧ ∼ 𝑟 ∨∼ 𝑞
≡ 𝑞 ∧ (∼ 𝑝 ∨∼ 𝑞) ∧ (∼ 𝑟 ∨∼ 𝑞) ____𝑐𝑛𝑓
 PROPOSITIONAL CALCULUS
• Minterms : Let p and q be two propositional variables. Then 𝑝 ∧ 𝑞 , 𝑝 ∧∼ 𝑞 , ∼ 𝑝 ∧∼
𝑞 , ∼ 𝑝 ∧ 𝑞 𝑎𝑟𝑒 𝑐𝑎𝑙𝑙𝑒𝑑 𝑚𝑖𝑛𝑡𝑒𝑟𝑚𝑠 𝑜𝑓 𝑝 𝑎𝑛𝑑 𝑞.
The number of minterms for n variables is 2𝑛 . If p is T, we take p and if p
is F then we take ∼ 𝑝.
• Maxterms : Let p and q be two propositional variables. Then 𝑝 ∨ 𝑞 , 𝑝 ∨∼ 𝑞 , ∼ 𝑝 ∨
𝑞 , ∼ 𝑝 ∨∼ 𝑞 𝑎𝑟𝑒 𝑐𝑎𝑙𝑙𝑒𝑑 𝑚𝑎𝑥𝑡𝑒𝑟𝑚𝑠 𝑜𝑓 𝑝 𝑎𝑛𝑑 𝑞.
The number of maxterms for n variables is 2𝑛 . If p is T , we take ∼ 𝑝, if p is F we take p.

P q Minterms Maxterms
T T 𝑝∧𝑞 ∼ 𝑝 ∨∼ 𝑞
T F 𝑝 ∧∼ 𝑞 ∼𝑝∨𝑞
F T ∼𝑝∧𝑞 𝑝 ∨∼ 𝑞
F F ∼ 𝑝 ∧∼ 𝑞 𝑝∨𝑞
 PROPOSITIONAL CALCULUS
• Principal disjunctive normal form (Sum of minterms): A statement form
consisting of disjunction of minterms only is called Principal disjunctive normal
form.
• Procedure to find principal disjunctive normal form.
1. Using truth table: Construct the truth table for the given proposition. Form a
minterm for the combination of variables for which the proposition is T. Take
disjunction of above minterms.
2. Without constructing the truth tables:
i) Express the given proposition is disjunctive normal form.
ii) Introduce the missing variable 𝑥 in each fundamental conjunction using
∧ (𝑥 ∨∼ x)
iii) Apply distributive law and simplify.
 PROPOSITIONAL CALCULUS
• Obtain the principal disjunctive normal form of
1) 𝑝 → 𝑞
Solution: By using truth table:

𝑝 → 𝑞 ≡ 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∧∼ 𝑞
 PROPOSITIONAL CALCULUS
Without using truth table:
𝑝 → 𝑞 ≡∼ 𝑝 ∨ 𝑞
≡ ∼ 𝑝 ∧ 𝑞 ∨∼ 𝑞 ∨ 𝑞 ∧ 𝑝 ∨∼ 𝑝
≡ ∼ 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∧∼ 𝑞 ∨ 𝑞 ∧ 𝑝 ∨ 𝑞 ∧∼ 𝑝
≡ (𝑝 ∧ 𝑞) ∨ (∼ 𝑝 ∧ 𝑞) ∨ (∼ 𝑝 ∧∼ 𝑞)

2) 𝑝 ∧∼ 𝑞 ∧∼ 𝑟 ∨ 𝑞 ∧ 𝑟 ≡ 𝑝 ∧∼ 𝑞 ∧∼ 𝑟 ∨ 𝑞 ∧ 𝑟 ∧ 𝑝 ∨∼ 𝑝
≡ 𝑝 ∧∼ 𝑞 ∧∼ 𝑟 ∨ 𝑞 ∧ 𝑟 ∧ 𝑝 ∨ 𝑞 ∧ 𝑟 ∧∼ 𝑝
≡ (𝑝 ∧∼ 𝑞 ∼ 𝑟) ∨ (𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (∼ 𝑝 ∧ 𝑞 ∧ 𝑟)
 PROPOSITIONAL CALCULUS
• Principal conjunctive normal form(Product of maxterms):A statement form
consisting of conjunction of maxterms is called principal conjunctive normal
form.
• Procedure to obtain principal conjunctive normal form:
1. Using Truth table : Construct the truth table for the given proposition.
Form a maxterm for the combination of variables for which the
proposition is F. Take conjunction of above maxterms.
2. Without constructing the truth tables:
i) Express the given proposition is conjunctive normal form.
ii) Introduce the missing variable 𝑥 in each fundamental disjunction by using
∨ (𝑥 ∧∼ x)
iii) Apply distributive law and simplify.
 PROPOSITIONAL CALCULUS
1. Obtain the Principal conjunctive normal form of 𝑝 ∨∼ 𝑞 → 𝑟.

• 𝑝 ∨∼ 𝑞 → 𝑟 ≡ (∼ 𝑝 ∨∼ q ∨ 𝑟) ∧ (∼ 𝑝 ∨ q ∨ 𝑟) ∧ (𝑝 ∨ q ∨ 𝑟)
 PROPOSITIONAL CALCULUS
2) ∼ 𝑝 → 𝑟 ∧ 𝑞 → 𝑝 ≡ 𝑝 ∨ 𝑟 ∧ ∼ 𝑞 ∨ 𝑝
≡ 𝑝 ∨ 𝑟 ∨ 𝑞 ∧∼ 𝑞 ∧ ∼ 𝑞 ∨ 𝑝 ∨ 𝑟 ∧∼ 𝑟
≡ (𝑝 ∨ 𝑟 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟 ∨∼ 𝑞) ∧ (∼ 𝑞 ∨ 𝑝 ∨ 𝑟) ∧ (∼ 𝑞 ∨ 𝑝 ∨∼ 𝑟)
≡ (𝑝 ∨ 𝑞 ∨ 𝑟) ∧ (𝑝 ∨∼ 𝑞 ∨ 𝑟) ∧ (𝑝 ∨∼ 𝑞 ∨∼ 𝑟)________𝑝𝑐𝑛𝑓

3) 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∧ 𝑞 ∨ 𝑞 ∧ 𝑟 ≡ 𝑝 ∨∼ 𝑝 ∧ 𝑞 ∧ 𝑞 ∧ 𝑟
≡ 𝑇∧𝑞 ∨ 𝑞∧𝑟
≡𝑞∨ 𝑞∧𝑟
≡𝑞
≡ 𝑞 ∨ 𝑝 ∧∼ 𝑝 ∨ 𝑟 ∧∼ 𝑟
≡ 𝑞 ∨ 𝑝 ∧ 𝑞 ∨∼ 𝑝 ∨ 𝑟 ∧∼ 𝑟
≡ 𝑞 ∨ 𝑝 ∨ 𝑟 ∧ 𝑞 ∨ 𝑝 ∨∼ 𝑟 ∧ 𝑞 ∨∼ 𝑝 ∨ 𝑟 ∧ 𝑞 ∨∼ 𝑝 ∨∼ 𝑟
≡ (𝑝 ∨ 𝑞 ∨ 𝑟) ∧ (𝑝 ∨ 𝑞 ∨∼ 𝑟) ∧ (∼ 𝑝 ∨ 𝑞 ∨ 𝑟) ∧ (∼ 𝑝 ∨ 𝑞 ∨∼ 𝑟)
 PROPOSITIONAL CALCULUS
• Logic in proof (Theory of inference)
A theorem is a proposition that can be proved to be true.
An argument that establishes the truth of a theorem is called a proof.
• An argument is a sequence of statements or propositions. All statements
except the final one is called premises(or assumptions or hypothesis). The
final statement is called a conclusion.

• An argument is said to be logically valid or consistent, if and only if, the

conjunction of the premises implies the conclusion i.e. if the premises are
all true, the conclusion must also be true.
 PROPOSITIONAL CALCULUS
Rules of Inference:
PROPOSITIONAL CALCULUS
 PROPOSITIONAL CALCULUS
• To test an argument for validity using truth table
1. Identify the premises and conclusion of the argument.
2. Construct a truth table showing the truth values of all the premises and
conclusion.
3. Find the rows (called critical rows) in which all the premises are true.
4. In each critical row, determine whether the conclusion of the argument
is also true.
a) If in each critical row , the conclusion is also true , then the argument
form is valid.
b) If there is at least one critical row in which the conclusion is false, the
argument is invalid.
 PROPOSITIONAL CALCULUS
1. Testing the validity of constructive dilemma:
 PROPOSITIONAL CALCULUS
The critical rows are 1,3,4,9,13.
The conclusion is true in all critical rows.
Hence the argument is valid.

2. Prove the validity of modus ponens.

There is only one critical row in which conclusion is true.

Therefore, the argument is valid.
 PROPOSITIONAL CALCULUS
1. Show that t is a valid conclusion from the premises 𝑝 → 𝑞 , 𝑞 → 𝑟, 𝑟 → 𝑠 , ∼ 𝑠 𝑎𝑛𝑑 𝑝 ∨ 𝑡.
Solution: The valid argument for deducing t from the given 5 premises is given as follows.

1. 𝑝→𝑞 Given premise

2. 𝑞→𝑟 Given premise
3. 𝑝→𝑟 Hypothetical syllogism using 1 and 2
4. 𝑟→ 𝑠 Given premise
5. 𝑝→𝑠 Hypothetical syllogism using 3 and 4
6. ∼𝑠 Given premise
7. ∼𝑝 Modus tollens using 5 and 6
8. 𝑝∨𝑡 Given premise
9. 𝑡 disjunctive syllogism using 7 and 8

Therefore, t is a valid conclusion.

 PROPOSITIONAL CALCULUS
2. Show that s is a valid conclusion from the premises 𝑝 → 𝑞 , 𝑝 → 𝑟, ∼ 𝑞 ∧ 𝑟 𝑎𝑛𝑑 𝑠 ∨ 𝑝.
Solution: The valid argument for deducing t from the given 5 premises is given as follows.

1. 𝑝→𝑞 Given premise

2. p→ 𝑟 Given premise
3. 𝑝→𝑞 ∧ p→𝑟 Conjunction using 1 and 2
4. ∼ 𝑞∧𝑟 Given premise
5. ∼ q ∨∼ r De−Morgan′s Law using 4
6. ∼ p ∨∼ p Destructive dilemma using 3 and 5
7. ∼p idempotent law using 6
8. 𝑠∨𝑝 Given premise
9. 𝑠 disjunctive syllogism using 7 and 8.
Therefore, s is valid conclusion.
 PROPOSITIONAL CALCULUS
.
3 Use the rule of inference to show that the premises 𝐸 → 𝑆 , 𝑆 → 𝐻 , 𝐴 →∼ 𝐻
𝑎𝑛𝑑 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 𝐸 ∧ 𝐴 𝑎𝑟𝑒 𝑖𝑛𝑐𝑜𝑛𝑠𝑖𝑠𝑡𝑒𝑛𝑡.
Solution:
1. 𝐸→𝑆 Given premise
2. 𝑆→𝐻 Given premise
3. 𝐸→𝐻 hypothetical syllogism using 1 and 2
4. 𝐴 →∼ 𝐻 Given premise
5. 𝐻 →∼ 𝐴 Contrapositive of 4
6. 𝐸 →∼ 𝐴 hypothetical syllogism using 3 and 5
7. ∼ E ∨∼ 𝐴 𝑢𝑠𝑖𝑛𝑔 𝑝 → 𝑞 ≡∼ 𝑝 ∨∼ 𝑞
8. ∼ 𝐸∧𝐴 𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤

Therefore, 𝐸 ∧ 𝐴 𝑖𝑠 𝑛𝑜𝑡 𝑎 𝑣𝑎𝑙𝑖𝑑 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 . 𝑇ℎ𝑒 𝑣𝑎𝑙𝑖𝑑 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 𝑖𝑠 ∼ 𝐸 ∧ 𝐴 .

 PROPOSITIONAL CALCULUS
.
4 Show that R ∧ 𝑃 ∨ 𝑄 𝑖𝑠 𝑎 𝑣𝑎𝑙𝑖𝑑 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 𝑜𝑓 𝑃 ∨ 𝑄 , 𝑄 → 𝑅, 𝑃 → 𝑀 𝑎𝑛𝑑 ∼ 𝑀.
Solution:
1. 𝑃→𝑀 Given premise
2. ∼𝑀 Given premise
3. ∼𝑃 Modus tollens using 1 and 2
4. 𝑃∨𝑄 Given premise
5. 𝑄 Disjunctive syllogism using 3 and 4
6. 𝑄→𝑅 Given premise
7. 𝑅 𝑀𝑜𝑑𝑢𝑠 𝑝𝑜𝑛𝑒𝑛𝑠 𝑢𝑠𝑖𝑛𝑔 5 & 6
8. 𝑅∧ 𝑃∨𝑄 𝐶𝑜𝑛𝑗𝑢𝑐𝑡𝑖𝑜𝑛 𝑢𝑠𝑖𝑛𝑔 4 𝑎𝑛𝑑 7

Therefore , R ∧ 𝑃 ∨ 𝑄 is a valid conclusion.

 PROPOSITIONAL CALCULUS
5. Prove that the validity of following argument.
“If I get the job and work hard, then I will get promoted. If I get promoted, then I will be
happy . I will not be happy. Therefore , either I will not get the job or I will not work hard.”
Solution:
Let 𝑝: 𝐼 𝑔𝑒𝑡 𝑡ℎ𝑒 𝑗𝑜𝑏
𝑞: 𝐼 𝑤𝑜𝑟𝑘 ℎ𝑎𝑟𝑑
𝑟: 𝐼 𝑔𝑒𝑡 𝑝𝑟𝑜𝑚𝑜𝑡𝑒𝑑
𝑠: 𝐼 𝑎𝑚 ℎ𝑎𝑝𝑝𝑦 .
The above argument can be written in symbolic form as
𝑝∧𝑞 →𝑟
𝑟→𝑠
∼𝑠
______
∴∼ 𝑝 ∨∼ 𝑞
 PROPOSITIONAL CALCULUS
1. 𝑝∧𝑞 →𝑟 Given premise

2. 𝑟→𝑠 Given premise

3. 𝑝∧𝑞 →𝑠 𝐻𝑦𝑝𝑜𝑡ℎ𝑒𝑡𝑖𝑐𝑎𝑙 𝑠𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚 𝑢𝑠𝑖𝑛𝑔 1 & 2

4. ∼𝑠 Given premise

5. ∼ 𝑝∧𝑞 𝑀𝑜𝑑𝑢𝑠 𝑡𝑜𝑙𝑙𝑒𝑛𝑠 𝑢𝑠𝑖𝑛𝑔 3 𝑎𝑛𝑑 4

6. ∼ 𝑝 ∨∼ 𝑞 𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤

Hence the argument is valid.

 PROPOSITIONAL CALCULUS
6. If I try hard and I have talent , then I will become a scientist . If I become a
scientist , then I will be happy. Therefore , If I will not be happy , then I did not try
hard or I do not have a talent.
Solution:
𝐿𝑒𝑡 𝑝: 𝐼 𝑡𝑟𝑦 ℎ𝑎𝑟𝑑.
𝑞: 𝐼 ℎ𝑎𝑣𝑒 𝑡𝑎𝑙𝑒𝑛𝑡
𝑟: 𝐼 𝑤𝑖𝑙𝑙 𝑏𝑒𝑐𝑜𝑚𝑒 𝑎 𝑠𝑐𝑖𝑒𝑛𝑡𝑖𝑠𝑡
𝑠: 𝐼 𝑤𝑖𝑙𝑙 𝑏𝑒 ℎ𝑎𝑝𝑝𝑦 .
The argument is
𝑝∧𝑞 →𝑟
𝑟→𝑠
_________
∴ ~𝑠 ⟶ (~𝑝 ∨∼ 𝑞)
 PROPOSITIONAL CALCULUS
1. 𝑝∧𝑞 →𝑟 Given premise

2. 𝑟→𝑠 Given premise

3. 𝑝∧𝑞 →𝑠 𝐻𝑦𝑝𝑜𝑡ℎ𝑒𝑡𝑖𝑐𝑎𝑙 𝑠𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚 𝑢𝑠𝑖𝑛𝑔 1 & 2

4. ∼ 𝑠 →∼ 𝑝 ∧ 𝑞 𝑐𝑜𝑛𝑡𝑎𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑜𝑓 3

5. ∼ 𝑠 →∼ 𝑝 ∨∼ 𝑞 𝐷𝑒 − 𝑀𝑜𝑟𝑔𝑎𝑛′ 𝑠 𝐿𝑎𝑤

Hence the argument is valid.

 PROPOSITIONAL CALCULUS
7. If I study , then I will pass in the examination. If I do not go for a movie ,
then I will study . But I failed in examination . Therefore , I went for a movie.
Solution: Let
𝑝: 𝐼 𝑠𝑡𝑢𝑑𝑦
𝑞: 𝐼 𝑝𝑎𝑠𝑠
𝑟: 𝐼 𝑔𝑜 𝑓𝑜𝑟 𝑡ℎ𝑒 𝑚𝑜𝑣𝑖𝑒.
The argument is 𝑝 → 𝑞
∼𝑟→𝑝
∼𝑞
_____
∴𝑟
 PROPOSITIONAL CALCULUS
1. ~𝑟 → 𝑝 Given premise

2. 𝑝→𝑞 Given premise

3. ∼𝑟→q 𝐻𝑦𝑝𝑜𝑡ℎ𝑒𝑡𝑖𝑐𝑎𝑙 𝑠𝑦𝑙𝑙𝑜𝑔𝑖𝑠𝑚 𝑢𝑠𝑖𝑛𝑔 1 & 2

4. ∼𝑞 Given premise

5. ∼ ∼𝑟 𝑀𝑜𝑑𝑢𝑠 𝑡𝑜𝑙𝑙𝑒𝑛𝑠 𝑢𝑠𝑖𝑛𝑔 3 𝑎𝑛𝑑 4

6. 𝑟 𝑑𝑜𝑢𝑏𝑙𝑒 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛 𝑙𝑎𝑤

Hence the argument is valid.

 PROPOSITIONAL CALCULUS
NAND Connective ↑ :
𝑝 ↑ 𝑞 ≡∼ 𝑝 ∧ 𝑞
NOR Connective ↓ :
𝑝 ↓ 𝑞 ≡∼ 𝑝 ∨ 𝑞
Functionally complete set of connectives: Any set of connectives in which
every formula can be expressed in terms of an equivalent formula
containing the connectives from this set is called a functionally complete
set of connectives.
A minimal functionally complete set of connectives is a set which does not
contain any connective that can be expressed in terms of the other
connectives from that set.
 PROPOSITIONAL CALCULUS
• Consider the connectives ∧ ,∨ , ∼ , → , ↔
• To eliminate conditional, we use 𝑝 → 𝑞 ≡∼ 𝑝 ∨ 𝑞
• To eliminate biconditional, we use 𝑝 ↔ 𝑞 ≡ ∼ 𝑝 ∨ 𝑞 ∧ 𝑝 ∨∼ 𝑞
≡ 𝑝 ∧ 𝑞 ∨ ∼ 𝑝 ∧∼ 𝑞
Thus all the conditionals and biconditionals can be replaced by the three
connectives ∧ ,∨ , ∼ .
Therefore ∧ ,∨ , ∼ 𝑖𝑠 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑎𝑙𝑙𝑦 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒.
Also p ∧ 𝑞 ≡∼ (∼ 𝑝 ∨∼ 𝑞)
p ∨ 𝑞 ≡∼ (∼ 𝑝 ∧∼ 𝑞)
Therefore, ∼,∧ 𝑎𝑛𝑑 ∼,∨ 𝑎𝑟𝑒 𝑚𝑖𝑛𝑖𝑚𝑎𝑙 𝑓𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑎𝑙𝑙𝑦 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝑠𝑒𝑡.
 PROPOSITIONAL CALCULUS
Show that the NAND connective ↑ is functionally complete.
Solution:
To show that ∼ ,∧ ,∨ 𝑐𝑎𝑛 𝑏𝑒 𝑟𝑒𝑝𝑙𝑎𝑐𝑒𝑑 𝑏𝑦 ↑.
(i) ∼ 𝑝 ≡∼ 𝑝 ∧ 𝑝
≡𝑝↑𝑝
(ii) 𝑝 ∨ 𝑞 ≡∼ ∼ 𝑝 ∧∼ 𝑞
≡∼ 𝑝 ↑∼ 𝑞
≡ 𝑝↑𝑝 ↑ 𝑞↑𝑞
(iii) 𝑝 ∧ 𝑞 ≡∼∼ (𝑝 ∧ 𝑞)
≡∼ (𝑝 ↑ 𝑞)
≡ (𝑝 ↑ 𝑞) ↑ (𝑝 ↑ 𝑞)
 PROPOSITIONAL CALCULUS
Show that the NOR connective (↓) is functionally complete.
Solution:
To show that ∼,∧ ,∨ 𝑐𝑎𝑛 𝑏𝑒 𝑟𝑒𝑝𝑙𝑎𝑐𝑒𝑑 𝑏𝑦 ↓.
(i) ∼ 𝑝 ≡∼ 𝑝 ∨ 𝑝
≡𝑝↓𝑝
(ii) 𝑝 ∧ 𝑞 ≡∼ ∼ 𝑝 ∨∼ 𝑞
≡∼ 𝑝 ↓∼ 𝑞
≡ 𝑝↓𝑝 ↓ 𝑞↓𝑞
(iii) 𝑝 ∨ 𝑞 ≡∼∼ (𝑝 ∨ 𝑞)
≡∼ (𝑝 ↓ 𝑞)
≡ (𝑝 ↓ 𝑞) ↓ (𝑝 ↓ 𝑞)
THANK YOU!