PropositionalLogic
Question 1 
Which one of the following choices is correct?
Both S_{1}and _{S2} are tautologies.  
Neither _{S1}and _{S2} are tautology.  
_{S1}is not a tautology but _{S2}is a tautology.  
_{S1}is a tautology but _{S2}is not a tautology. 
A tautology is a formula which is "always true" . That is, it is true for every assignment of truth values to its simple components.
Method 1:
S1: (~p ^ (p Vq)) →q
The implication is false only for T>F condition.
Let's consider q as false, then
(~p ^ (p Vq)) will be (~p ^ (p VF)) = (~p ^ (p)) =F.
It is always F>F which is true for implication. So there are no cases that return false, thus its always True i.e. its Tautology.
S2:
q>(~p (p Vq))
The false case for implication occurs at T>F case.
Let q=T then (~p (p Vq)) = (~p (p VT))= ~p. (It can be false for p=T).
So there is a case which yields T>F = F. Thus its not Valid or Not a Tautology.
Method 2:
Question 2 
(a) Let * be a Boolean operation defined as
If C = A * B then evaluate and fill in the blanks:
(i) A * A = _______
(ii) C * A = _______
(b) Solve the following boolean equations for the values of A, B and C:
Theory Explanation. 
Question 3 
Obtain the principal (canonical) conjunctive normal form of the propositional formula
(p ∧ q) V (¬q ∧ r)
Where ‘∧’ is logical and, ‘v’ is inclusive or and ¬ is negation.
Theory Explanation. 
Question 4 
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
∃x(p(x) → W) ≡ ∀x p(x) → W  
∀x(p(x) → W) ≡ ∀x p(x) → W
 
∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W  
∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W 
~p→q ≡ ~p∨q
Demorgan laws:
~(∀x(a(x)) ≡ ∃x~a(x)
~(∃x(a(x)) ≡ ∀x~a(x)
(A) ∃x(p(x)→w) ≡ ∀x p(x)→w
LHS: ∃x(p(x)→w) ≡ ∃x(~p(x)∨w)
≡ ∃x(~p(x))∨w
Demorgan’s law:
~(∀x(a(x)) = ∃x ~ a(x)
≡ ~(∀x P(x)) ∨ w
≡ (∀x) P(x) → w ≡ RHS
It’s valid.
(B) ∀x(P(x) → w) ≡ ∀x(~P(x) ∨ w)
≡ ∀x(~P(x)) ∨ w
≡ ~(∃x P(x)) ∨ w
≡ ∃x P(x) → w
This is not equal to RHS.
(C) ∃x(P(x) ∧ w) ≡ ∃x P(x) ∧ w
‘w’ is not a term which contains x.
So the quantifier does not have any impact on ‘w’.
Thus it can be written as
∃x(P(x)) ∧ w) ≡ ∃x P(x) ∧ w
(D) ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
‘w’ is not a term which contains ‘x’.
So the quantifier does not have an impact on ‘w’.
Thus ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
Question 5 
What is the correct translation of the following statement into mathematical logic?
“Some real numbers are rational”
∃x (real(x) ∨ rational(x))  
∀x (real(x) → rational(x))  
∃x (real(x) ∧ rational(x))  
∃x (rational(x) → real(x)) 
∃x (real(x) ∧ rational(x))
(A) ∃x(real(x) ∨ rational(x))
means There exists some number, which are either real or rational.
(B) ∀x (real(x)→rational(x))
If a number is real then it is rational.
(D) ∃x (rational(x)→real(x))
There exists a number such that if it is rational then it is real.
Question 6 
Consider the following logical inferences.
 I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.
Which of the following is TRUE?
Both I_{1} and I_{2} are correct inferences  
I_{1} is correct but I_{2} is not a correct inference  
I_{1} is not correct but I_{2} is a correct inference  
Both I_{1} and I_{2} are not correct inferences 
The cricket match was played.
Let p = it rains
q = playing cricket/ match played
If (it rains) then (the match will not be played)
p ⇒ (∼q)
Inference: There was no rain. (i.e., p = F)
So for any F ⇒ (∼q) is true.
So this inference is valid.
I_{2}: If it rains then the cricket match will not be played.
It did not rain.
p ⇒ (∼q)
Inference: The cricket match was played.
q = T
p ⇒ (∼q)
p ⇒ (∼T)
p ⇒ F
This is false for p = T, so this is not true.
Question 7 
Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.
((x → y) ∧ x) → y  
((x → y) ∧ (x ∧ y)) → x  
(x → (x ∨ ψ))  
((x ∨ y) ↔ (x → y) 
then option (D) will be False.
Question 8 
Which of the following propositions is a tautology?
(p ∨ q) → p  
p ∨ (q → p)  
p ∨ (p → q)  
p → (p → q) 
Question 9 
What is the converse of the following assertion?
I stay only if you go.
I stay if you go  
If I stay then you go  
If you do not go then I do not stay  
If I do not stay then you go 
⇒ i.e., A→B
Where A = If I stay; B = you go
Converse for (A→B) is (B→A)
⇒ If you go then I stay.
Question 10 
(a) Show that the formula [(~p ∨ q) ⇒ (q ⇒ p)] is not a tautology.
(b) Let A be a tautology and B be any other formula. Prove that (A ∨ B) is a tautology.
Theory Explanation. 
Question 11 
Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨ b) and b ↔ c hold. Then the truthvalue of the formula (a ∧ b) → (a ∧ c) ∨ d is always
True  
False  
Same as the truthvalue of b  
Same as the truthvalue of d 
Given ⇒ (a∧b) → (a∧c) ∨d
⇒ (a∧b) → (a∧c) ∨d (b⇔c)
⇒ T∨d
⇒ T
Question 12 
Consider two wellformed formulas in prepositional logic
F1: P ⇒ ¬P F2: (P⇒¬P)∨(¬P⇒P)
Which of the following statements is correct?
F1 is satisfiable, F2 is valid  
F1 unsatisfiable, F2 is satisfiable  
F1 is unsatisfiable, F2 is valid  
F1 and F2 are both satisfiable 
F1 is satisfiable; F2 is valid.
Question 13 
“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“¬“, is negation, “∧” is conjunction, and “→” is implication)
(X∧¬Z)→Y  
(X∧Y)→¬Z  
X→(Y∧¬Z)  
(X→Y)∧¬Z 
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.
Question 14 
The following resolution rule is used in logic programming.
Derive clause (P ∨ Q) from clauses (P ∨ R), (Q ∨ ¬R)
Which of the following statements related to this rule is FALSE?
((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid  
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R)) is logically valid
 
(P ∨ Q) is satisfiable if and only if (P∨R) ∧ (Q∨¬R) is satisfiable  
(P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

It is may be True (or) False depending on values. So this is not valid.
Question 15 
Consider the following formula a and its two interpretations I_{1} and I_{2}
α: (∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒ (∀x)[¬Px] I_{1}: Domain: the set of natural numbers Px ≡ 'x is a prime number' Qxy ≡ 'y divides x' I_{2}: same as I_{1} except that Px = 'x is a composite number'.
Which of the following statements is true?
I_{1} satisfies α, I_{2} does not  
I_{2} satisfies α, I_{1} does not
 
Neither I_{2} nor I_{1} satisfies α
 
Both I_{1} and I_{2} satisfy α 
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Q_{yy}]] ⇒(∀x)[¬Px]
Q_{yy} is always true, because y divide y, then ¬Q_{yy} is false.
∀x[(P(x) ⇔ ∀y [Qxy ⇔ False]]
∀y [Qxy ⇔ False] can be written as ∀y[¬axy]
⇒(∀x)[P(x) ⇔ ∀y[¬Qxy]]
Here, ¬Qxy says that y doesnot divides x, which is not always be true.
For example, if x=y then it is false then ∀y[¬Qxy] is not true for all values of y.
⇒(∀x)[P(x) ⇔ False]
⇒(∀x)[¬P(x) = RHS]
LHS = RHS
⇒ Irrespective of x, whether x is prime of composite number I_{1} and I_{2} satisfies α.
Question 16 
Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)
((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α⇒β]
 
(∀x)[α] ⇒ (∃x)[α ∧ β]  
((∀x)[α ∨ β] ⇒ (∃x)[α] ⇒ (∀x)[α]  
(∀x)[α ⇒ β] ⇒ ((∀x)[α] ⇒ (∀x)[β]) 
Here, α, β are holding values of x. Then and RHS saying that α holding the value of x and β is holding value of x.
Then LHS ⇒ RHS.
Question 17 
Show that proposition C is a logical consequence of the formula
A ∧ (A →(B ∨ C)) ∧ (B → ~A)
Using truth tables.
Theory Explanation. 
Question 18 
(a) Uses Modus ponens (A, A →= B) or resolution to show that the following set is inconsistent:
(1) Q(x) → P(x)V ~ R(a) (2) R(a) ~ Q(a) (3) Q(a) (4) ~ P(y)
Where x and y are universally quantified variables, a is a constant and P, Q, R are monadic predicates.
(b) Let S be the set of all integers and let n > 1 be a fixed integer. Define for a, b ∈ S, a R biff ab is a multiple of n. Show that R is an equivalence relation and finds its equivalence classes for n = 5.
Theory Explanation. 
Question 19 
S is a contradiction.  
The anecdote of S is logically equivalent to the consequent of S.  
S is a tautology.  
S is neither a tautology nor a contradiction. 
Question 20 
Consider the following first order logic formula in which R is a binary relation symbol.
∀x∀y (R(x, y) => R(y, x))The formula is
satisfiable and valid  
satisfiable and so is its negation  
unsatisfiable but its negation is valid  
satisfiable but its negation is unsatisfiable 
Question 21 
Which one of these firstorder logic formula is valid?
∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x))  
∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x))  
∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x))  
∀x∃y P(x, y) ⇒ ∃y∀x P(x, y) 
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️×)
Question 22 
Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
[β→(∃x,α(x))]→[∀x,β→α(x)]  
[∃x,β→α(x)]→[β→(∀x,α(x))]  
[(∃x,α(x))→β]→[∀x,α(x)→β]  
[(∀x,α(x))→β]→[∀x,α(x)→β] 
L.H.S. : If there is an x such that α(x) is true, then β is true.
R.H.S. : For all x, if α(x) true, then β is true.
Here, the given LHS and RHS are to be same as β is a formula which can be independent of x (if β is true for one x, it is true for every x, and viceversa).
Here, LHS = RHS
So, Option C is valid.
Question 23 
Which of the following is the negation of [∀x, α →(∃y, β →(∀ u, ∃v, y))]
[∃x, α → (∀y, β → (∃u, ∀v, y))]  
[∃x, α → (∀y, β → (∃u, ∀ v, ¬y))]  
[∀x, ¬α → (∃y, ¬β → (∀u, ∃v, ¬y))]  
[∃x, α ʌ (∀y, β ʌ (∃u, ∀v, ¬y))] 
⇔ [∃x, [α × ~(∃y, β → (∀u, ∃v, y))]
⇔ [∃x, [α × ∀y, ~(β → (∀u, ∃v, y)]
⇔ [∃x, [α × ∀y, ~(β × ~(∀u, ∃v, y)]
⇔ [∃x, [α × ∀y(β × (∃u, ∀v, y)]
Question 24 
Which of the following wellformed formulas are equivalent?
P → Q  
¬Q → ¬P  
¬P ∨ Q  
¬Q → P  
A, B and C. 
¬Q → ¬P ⇔ Q ∨ ¬P
¬P ∨ Q ⇔ ¬P ∨ Q
¬Q → P ⇔ Q ∨ P
A, B and C are equivalent.
Question 25 
Choose the correct alternatives (More than one may be correct). Indicate which of the following wellformed formulae are valid:
(P⇒Q) ∧ (Q⇒R) ⇒ (P⇒R)  
(P⇒Q) ⇒ (¬P⇒¬Q)  
(P∧(¬P∨¬Q)) ⇒ Q
 
(P⇒R) ∨ (Q⇒R) ⇒ ((P∨Q)⇒R) 
Since implication A → B is False only when A = T and B = F. So to prove any implication is valid or not try to get
TRUE → FALSE, if we succeed then it is not valid, if we not then well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes False.
LHS:
(P→Q) ∧ (P→R)
To get true here we need T∧T. So substitute Q=T which makes P→Q TRUE and P→R FALSE.
So, T∧F = F which makes LHS = False.
Hence, we are unable to get T→F which proves well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.
Question 26 
The following propositional statement is (P → (Q v R)) → ((P v Q) → R)
satisfiable but not valid
 
valid  
a contradiction  
None of the above 
If P=T; Q=T; R=T
(P→(T∨T)) → ((T∨T)→R)
(P→T) → (T→R)
(T→T) → (T→T)
T→T
T(Satisfiable)
Question 27 
Identify the correct translation into logical notation of the following assertion.
"Some boys in the class are taller than all the girls"
Note: taller(x,y) is true if x is taller than y.
(∃x) (boy(x) → (∀y) (girl(y) ∧ taller(x,y)))  
(∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller(x,y)))  
(∃x) (boy(x) → (∀y) (girl(y) → taller(x,y)))  
(∃x) (boy(x) ∧ (∀y) (girl(y) → taller(x,y))) 
'∧' → predicts statements are always true, no matter the value of x.
'→' → predicts there is no need of left predicate to be true always, but whenever it becomes true, then right predicate must be true.
Option D:
There exists a some boys who are taller than of all girls y.
Question 28 
Which one of the following well formed formulae is a tautology?
∀x ∃y R(x,y) ↔ ∃y ∀x R(x,y)
 
(∀x [∃y R(x,y) → S(x,y)]) → ∀x∃y S(x,y)
 
[∀x ∃y (P(x,y) → R(x,y)] ↔ [∀x ∃y (¬ P(x,y)∨R(x,y)]  
∀x ∀y P(x,y) → ∀x ∀y P(y,x) 
[∀x ∃y (P(x,y) → R(x,y)] ↔ [∀x ∃y (¬ P(x,y)∨R(x,y)] is a tautology.
Question 29 
A  
B  
C  
D 
Question 30 
Which one of the following wellformed formulae in predicate calculus is NOT valid?
(∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬p(x) ∨ ∀x q(x))  
(∃x p(x) ∨ ∃x q(x)) ⇒ ∃x (p(x) ∨ q(x))  
∃x (p(x) ∧ q(x)) ⇒ (∃x p(x) ∧ ∃x q(x))  
∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)) 
But in option (D), we can generate T → F.
Hence, not valid.
Question 31 
(i) false
(ii) Q
(iii) true
(iv) P ∨ Q
(v) ¬Q ∨ P
The number of expressions given above that are logically implied by P ∧ (P ⇒ Q) is _________.
4  
5  
6  
7 
(P ∧ (P → Q))→ expression is a tautology. So we have to find
How many tautological formulas are there for the given inputs.
(P ∧ (P → Q)) → True is always tautology
(P ∧ (P → Q)) → False is not a tautology
(P ∧ (P → Q)) → Q is a tautology
(P ∧ (P → Q)) → ¬Q ∨ P is a tautology
(P ∧ (P → Q)) → P ∨ Q is a tautology
So there are 4 expressions logically implied by (P ∧ (P → Q))
Question 32 
∃x P(x) ∧ ∀yQ(x, y)  
∀x∀yQ(x, y)  
∃y∀x P(x) ⇒ Q(x, y)  
∃x P(x) ∧ ∃yQ(x, y) 
Question 33 
I. p ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q
I only  
I and IV only  
II only  
II and III only 
Construct Truth tables:
~p ⇒ ~q
II, III are equivalent to (~p) ⇒ (~q)
Method 2:
(I) p⇒q ≡ ~p∨q
(II) q⇒p ≡ ~q∨p
(III) (~q) ∨ p ≡ ~q∨p
(IV) (~p) ∨ p ≡ ~p∨q
Also, from question:
(~p) ⇒ (~q)
≡ p∨~q
So, (II) & (III) are equivalent to the statement given in question.
Question 34 
φ ≡ ∃s∃t∃u∀v∀w∀x∀y ψ(s,t,u,v,w,x,y)
where ψ(s,t,u,v,w,x,y) is a quantifierfree firstorder logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose φ has a model with a universe containing 7 elements.
Which one of the following statements is necessarily true?
There exists at least one model of φ with universe of size less than or equal to 3.  
There exists no model of φ with universe of size less than or equal to 3.
 
There exists no model of φ with universe of size greater than 7.  
Every model of φ has a universe of size equal to 7. 
"∃" there exists quantifier decides whether a sentence belong to the model or not.
i.e., ~∃ will make it not belong to the model. (1) We have ‘7’ elements in the universe, So max. size of universe in a model = ‘7’
(2) There are three '∃' quantifiers, which makes that a model have atleast “3” elements. So, min. size of universe in model = ‘7’.
(A) is False because: (2)
(B) is true
(C) is false because of (1)
(D) is false, because these all models with size {3 to 7} not only ‘7’.
Question 35 
Consider the first order predicate formula φ:
 ∀x[(∀z zx ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z zw ⇒ ((w = z) ∨ (z = 1)))]
Here 'ab' denotes that 'a divides b', where a and b are integers. Consider the following sets:

S1. {1, 2, 3, ..., 100}
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy φ?
S1 and S3  
S1, S2 and S3  
S2 and S3  
S1 and S2 
One of the case:
If 7 is a number which is prime (either divided by 7 or 1 only). then there exists some number like 3 which is larger than 7 also satisfy the property (either divided by 3 or 1 only).
So, S3 is correct
It's true for all integers too.
Question 36 
S1: (P # Q) # R = P # (Q # R)
S2: Q # R = R # Q
Which of the following is/are true for the Boolean variables P, Q and R?
Only S1 is True  
Only S2 is True  
Both S1 and S2 are True  
Neither S1 nor S2 are True 
Question 37 
P and Q are two propositions. Which of the following logical expressions are equivalent?
 I. P∨∼Q
II. ∼(∼P∧Q)
III. (P∧Q)∨(P∧∼Q)∨(∼P∧∼Q)
IV. (P∧Q)∨(P∧∼Q)∨(∼P∧Q)
Only I and II  
Only I, II and III  
Only I, II and IV  
All of I, II, III and IV 
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
Question 38 
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following:
Each finite state automaton has an equivalent pushdown automaton
(∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y))  
∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y))  
∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y))  
∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y)) 
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
So answer is option A.
Question 39 
Let P, Q and R be three atomic prepositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?
X ≡ Y  
X → Y  
Y → X  
¬Y → X 
⇒ ∼(P∨Q) ∨ R
⇒ (∼P∧∼Q) ∨ R
⇒ (∼P∨R) × (∼Q∨R)
⇒ (P→R) ∧ (Q→R)
Option B: X→Y
[(P→R) × (Q→R)] → [(P→R) ∨ (Q→R)]
∼[(P→R) × (Q→R) ∨ (P→R) ∨ (Q→R)]
[∼(P→R) ∨ ∼(Q→R)] ∨ [(P→R) ∨ (Q→R)]
[∼(P→R) ∨ (P→R)] ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] ∨ [∼(Q→R) ∨ (Q→R)]
T ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] V T
T (✔️)