PropositionalLogic
Question 1 
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 2 
Consider the firstorder logic sentence
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 3 
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 4 
(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 5 
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 6 
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 7 
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 8 
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 9 
Which one of the following options is CORRECT given three positive integers x,y and z, and a predicate
P(x) = ¬(x=1)∧∀y(∃z(x=y*z) ⇒ (y=x)∨(y=1))P(x) being true means that x is a prime number  
P(x) being true means that x is a number other than 1  
P(x) is always true irrespective of the value of x
 
P(x) being true means that x has exactly two factors other than 1 and x 
This is the definition of prime numbers.
Question 10 
Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. Which one of the statements below expresses best the meaning of the formula ∀x∃y∃t(¬F(x,y,t))?
Everyone can fool some person at some time  
No one can fool everyone all the time  
Everyone cannot fool some person all the time
 
No one can fool some person at some time 
For better understanding propagate negation sign outward by applying Demorgan's law.
∀x∃y∃t(¬F(x, y, t)) ≡ ¬∃x∀y∀t(F(x,y,t))
Now converting ¬∃x∀y∀t(F(x,y,t)) to English is simple.
¬∃x∀y∀t(F(x,y,t)) ⇒ There does not exist a person who can fool everyone all the time.
Which means "No one can fool everyone all the time".
Hence, Option (B) is correct.
Question 11 
Which one of the following is the most appropriate logical formula to represent the statement?
“Gold and silver ornaments are precious”.
The following notations are used:
G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is precious
∀x(P(x) → (G(x) ∧ S(x)))  
∀x((G(x) ∧ S(x)) → P(x))  
∃x((G(x) ∧ S(x)) → P(x)  
∀x((G(x) ∨ S(x)) → P(x))

(A) for all ornaments, if it is precious then they should be gold and silver.
But, given statement does not says that, “ only gold and silver are precious “ . So this is wrong.
(B) For all ornaments, which contains gold and silver are precious.
Which is only the shaded region in the venn diagrams. But, it misses p,r regions. So, this is wrong option.
C) Some ornaments, which are gold and silver are precious. It is false, because all gold or silver ornaments are precious.
D) For all ornaments, Any ornament which is gold or silver is precious. Which is true.
Question 12 
The binary operation □ is defined as follows
Which one of the following is equivalent to P ∨ Q ?
¬Q□¬P  
P□¬Q  
¬P□Q  
¬P□¬Q 
P∨Q = P□️Q
So, option B is correct.
Question 13 
Consider the following wellformed formulae:
 I. ¬∀x(P(x))
II. ¬∃(P(x))
III. ¬∃(¬P(x))
IV. ∃x(¬(P(x))
Which of the above are equivalent?
I and III  
I and IV  
II and III  
II and IV 
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
Question 14 
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 15 
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 16 
Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?
¬∀x (Graph (x) ⇒ Connected (x))  
¬∃x (Graph (x) ∧ ¬Connected (x))  
¬∀x (¬Graph (x) ∨ Connected (x))  
∀x (Graph (x) ⇒ ¬Connected (x))

Given expression is
¬∀x(¬Graph(x) ∨ Connected(x)
which can be rewritten as,
¬∀x(Graph(x) ⇒ Connected(x)
which is equivalent to option (A)
(∵ ¬p∨q ≡ p→q)
So, option (A) and (C) cannot be the answer.
Coming to option (B), the given expression is,
∃x (Graph (x) ∧ ¬Connected (x))
"There exist some graph which is not connected", which is equivalent in saying that "Not every graph is connected".
Coming to option (D),
For all x graph is not connected, which is not correct.
Hence, option (D) is the answer.
Question 17 
Which one of the first order predicate calculus statements given below correctly express the following English statement?
Tigers and lions attack if they are hungry or threatened.
∀x [(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x))
→ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x))
∧ attacks(x)}]  
∀x [(tiger(x) ∨ lion(x)) → {(attacks(x) → (hungry (x)) ∨ threatened (x))}]  
∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]

Here we have two cases.
i) If Tiger is hungry (or) threaten that will attack.
ii) If Lion is hungry (or) threaten that will attack.
If Tiger is hungry (or) threaten then both lion and tiger will not attack only Tiger will attack and viceversa.
Then answer is
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
Question 18 
Consider the following propositional statements:
 P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))
Which one of the following is true?
P1 is a tautology, but not P2  
P2 is a tautology, but not P1  
P1 and P2 are both tautologies  
Both P1 and P2 are not tautologies 
Both P1 and P2 are not Tautologies.
Question 19 
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 (✔️)
Question 20 
What is the first order predicate calculus statement equivalent to the following?
Every teacher is liked by some student
∀(x) [teacher(x) → ∃ (y) [student(y) → likes (y, x)]]  
∀(x) [teacher(x) → ∃ (y) [student(y) ∧ likes (y, x)]]  
∃(y) ∀(x) [teacher(x) → [student(y) ∧ likes (y, x)]]  
∀(x) [teacher(x) ∧ ∃ (y)[student(y) → likes (y, x)]] 
Option B: If x is a teacher, then there exists some y, who is a student and like x. (✔️)
Option C: There exists a student who likes all teachers.
Option D: If x is a teacher and then there exists some y, if y is a student then y likes x.
Question 21 
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 22 
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 23 
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 24 
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 25 
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 26 
“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 27 
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 28 
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 29 
(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 30 
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 31 
Which of the following propositions is a tautology?
(p ∨ q) → p  
p ∨ (q → p)  
p ∨ (p → q)  
p → (p → q) 
Question 32 
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 33 
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 34 
(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 35 
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 36 
Show that proposition C is a logical consequence of the formula
A ∧ (A →(B ∨ C)) ∧ (B → ~A)
Using truth tables.
Theory Explanation. 
Question 37 
(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 38 
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 39 
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 40 
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 41 
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 42 
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 43 
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 44 
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 45 
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 46 
(∃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 47 
((a → b) ∧ (b → c)) → (a → c)  
(a ↔ c) → ( ¬b → (a ∧ c))  
(a ∧ b ∧ c) → (c ∨ a)  
a → (b → a) 
Note: Above (A↔C) →( ¬B→(A∧C)) is not tautology.
Question 48 
tautology  
contradiction  
contingency  
absurdity 
Question 49 
Chetan does not attend  
Akash does not attend  
either (a) or (b)  
none of the above 
Question 50 
Consider a vocabulary with only four propositions A, B, C and D. How many models are there for the following sentence ? B ∨ C
10  
12  
15  
16 
Total 12 TRUE for given sentence.
Question 51 
Consider the following statements :

(a) False╞ True
(b) If α╞ (β ∧ γ) then α╞ β and α╞ γ.
Which of the following is correct with respect to the above statements ?
Both statement (a) and statement (b) are false.  
Statement (a) is true but statement (b) is false.  
Statement (a) is false but statement (b) is true.
 
Both statement (a) and statement (b) are true.

(b) α╞ (β ∧ γ) also write αV(β ∧ γ)
α╞ β and α╞ γ also write (αVβ)∧(αVγ)
Finally, we proved as LHS=RHS. αV(β ∧ γ) = (αVβ)∧(αVγ)
So, both the statements are correct.
Question 52 
Consider the following two sentences :
 (a) The planning graph data structure can be used to give a better heuristic for a planning problem.
(b) Dropping negative effects from every action schema in a planning problem results in a relaxed problem.
Which of the following is correct with respect to the above sentences ?
Both sentence (a) and sentence (b) are false.  
Both sentence (a) and sentence (b) are true.
 
Sentence (a) is true but sentence (b) is false.
 
Sentence (a) is false but sentence (b) is true. 
• When these negative effects are dropped, then the number of actions increase and dropping all of the negative effects from the action schema results in a relaxed problem.
• A planning graph is a directed graph organized into levels: first a level S_{0} for the initial state, consisting of nodes representing each fluent that holds in S_{0}; then a level A_{0} consisting of nodes for each ground action that might be applicable in S_{0}; then alternating levels S_{i} followed by A_{i} ; until we reach a termination condition.
• As a tool for generating accurate heuristics, we can view the planning graph as a relaxed problem that is efficiently solvable.
Question 53 
A knowledge base contains just one sentence, ∃x AsHighAs (x, Everest). Consider the following two sentences obtained after applying existential instantiation.
 (a) AsHighAs (Everest, Everest)
(b) AsHighAs (Kilimanjaro, Everest)
Which of the following is correct with respect to the above sentences ?
Both sentence (a) and sentence (b) are sound conclusions.
 
Both sentence (a) and sentence (b) are unsound conclusions.  
Sentence (a) is sound but sentence (b) is unsound.
 
Sentence (a) is unsound but sentence (b) is sound.

• In the statement (a) AsHighAs (Everest, Everest), both are Everest then we can’t compare.
• The statement (b) AsHighAs (Kilimanjaro, Everest) means there kilimanjaro which is as highest as Everest So this valid statement.Because we are comparing Kilimanjaro with Everest.
Question 54 
The equivalence of ¬∃ x Q(x) is :
∃x ¬Q(x)  
∀x ¬Q(x)  
¬∃ x ¬Q(x)  
∀x Q(x) 
Question 55 
Z  
Q  
R  
C 
Z number set:
• Z is the set of integers, ie. positive, negative or zero.
• Example: ..., 100, ..., 12, 11, 10, ..., 5, 4, 3, 2,  1, 0, 1, 2, 3, 4, 5, ... 10, 11, 12, ..., 100, ...
• The set N is included in the set Z (because all natural numbers are part of the relative integers).
• The set A consists of Positive, negative and zero numbers.
Question 56 
Match the following in ListI and ListII, for a function f :
ListI ListII (a) ∀x∀y(f(x)=f(y)⟶x=y) (i) Constant (b) ∀y∃x(f(x)=y) (ii) Injective (c) ∀xf(x)=k (iii) Surjective
(a)(i), (b)(ii), (c)(iii)
 
(a)(iii), (b)(ii), (c)(i)  
(a)(ii), (b)(i), (c)(iii)  
(a) (ii), (b)(iii), (c)(i)

x, x' ∈ X, f(x) = f(x') ⇒ x = x'
Or, equivalently (using logical transposition),
x, x' ∈ X, x ≠ x' f(x) ≠ f(x')
• The function is surjective (onto) if each element of the codomain is mapped to by at least one element of the domain. (That is, the image and the codomain of the function are equal.) A surjective function is a surjection. Notationally:
∀y ∈ Y, ∃x ∈ X such that y = f(x)
A constant function is a function whose (output) value is the same for every input value.
For example, the function y(x) = 4 is a constant function because the value y(x) is 4 regardless of the input value x.
Question 57 
~p → q  
~p V q  
~p V ~q  
p → ~q 
Question 58 
Consider the vocabulary with only four propositions A, B, C and D. How many models are there for the following sentence?
(⌐A∨⌐B∨⌐C∨⌐D)8  
7  
15  
16 
Question 59 
(p Vq) → q  
p V(q → p)  
pV(p → q)  
Both B) and C) 
Question 60 
Match the List 1 and List 2 and choose the correct answer from the code given below
LIST 1 LIST 2 (a) Equivalence (i) p ⇒ q (b) Contrapositive (ii) p ⇒ q : q ⇒ p (c) Converse (iii) p ⇒ q : ∼q ⇒ ∼p (d) Implication (iv) p ⇔ qCode:
(a)(i), (b)(ii), (c)(iii), (d)(iv)
 
(a)(ii), (b)(i),(c)(iii), (d)(iv)  
(a)(iv), (b)(iii), (c)(ii), (d)(i)  
(a)(iii), (b)(iv), (c)(ii), (d)(i)

∼q⇒ ∼p
According to above table,
equivalence means p ⇔ q
Contrapositive means p⇒ q : ∼q⇒ ∼p
Converse means p ⇒ q : q ⇒ p
Implication means p ⇔ q
Question 61 
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 ⋁ y))  
((x ⋁ y) ⬌ (~x ⋁ ~y)) 
Question 62 
a V b → b ⋀ c  
a ⋀ b → b V c  
a V b → (b → c)  
a → b → (b → c) 
Question 63 
In mathematical logic, which of the following are statements ?
 (i) There will be snow in January
(ii) What is the time now ?
(iii) Today is Sunday
(iv) You must study Discrete Mathematics.
Choose the correct answer from the code given below :
Code :(iii) and (iv)  
(i) and (ii)
 
(i) and (iii)  
(ii) and (iv)

(a) a meaningful declarative sentence that is true or false, or
(b) the assertion that is made by a true or false declarative sentence.
From the above four statements, statement 2 and 4 wont give meaning like true or false answers and statements 1 and 3 will give either true or false answers.
Question 64 
Consider the statements below :
“There is a country that borders both India and Nepal.“
Which of the following represents the above sentence correctly ?
∃c Border(Country(c), India ∧ Nepal)
 
∃c Country(c) ∧ Border(c, India) ∧ Border(c, Nepal)
 
[∃c Country(c)] ⇒ [Border(c,India) ∧ Border(c, Nepal)]
 
∃c Country(c) ⇒ [ Border(c, India) ∧ Border(c, Nepal)]

→ Border(c, India) which represents border between c and india
→ Border(c, Nepal) which represents border between c and Nepal
→ “∧” represents both
Option2 represents the sentence “There is a country that borders both India and Nepal".
Question 65 
P  
Q  
R  
True≅T 
Question 66 
(P⋀Q)V(~P⋀Q)V(P⋀~Q) is equal to ~Q⋀~P  
(P⋀Q)V(~P⋀Q)V(P⋀~Q) is equal to QVP  
(P⋀Q)V(~P⋀Q)V(P⋀~Q) is equal to QV(P⋀~q)  
(P⋀Q)V(~P⋀Q)V(P⋀~Q) is equal to PV(Q⋀~p) 
The last two columns of the above table are different. So option A is false.
Question 67 
Let P, Q and R be three atomic prepositional assertions, and
 X : (P ∨ Q) → R
Y : (P → R) ∨ (Q → R)
Which one of the following is a tautology?
X → Y
 
Y → X  
X ≣ Y  
~Y → X

Question 68 
Which of the given options is the logical translation of the following statement, where F(x) and P(x) express the terms friend and perfect, respectively?
“None of my friends are perfect”?
∃x(~F(x)∧P(x))
 
∃x(F(x)∧ ~P(x))
 
~∃x(F(x)∧P(x))  
∃x(~F(x)∧~P(x))

P(x) represents x is perfect.
Given statement is “None of my friends are perfect”.
F(x)∧P(x) > X is both Friend and perfect.
~∃x > There is exist no one.
We can also write the above statement as follows
∀x[F(x) ⟹ ¬P(x)]
≡ ∀x[¬F(x) ∨ ¬P(x)]
≡∀x¬[F(x) ∧ P(x)]
≡¬∃x[F(x) ∧ P(x)]
Question 69 
Which of the following statements are logically equivalent?
 (i) ∀x(P(x))
(ii) ~∃x(P(x))
(iii) ~∃x(~P(x))
(iv) ∃x(~P(x))
Only (ii) and (iv)  
Only (ii) and (iii)
 
Only (i) and (iv)
 
Only (i) and (ii) 
Question 70 
In algebra of logic, the conjunction of two tautologies is:
Contradiction
 
Tautology
 
Negation  
Disjunction

1. The negation of a contradiction is a tautology.
2. The disjunction of two contingencies can be a tautology.
3. The conjunction of two tautologies is a tautology.
Question 71 
(I) P ↔ ¬ Q
(II) ¬ P ↔ Q
(III) ¬ P ↔ ¬ Q
(IV) Q → P
Only (I) and (II)  
Only (II) and (III)  
Only (III) and (IV)  
None of the above 
So, (I) and (Ii) are TRUE.
Question 72 
∃x ⌐H(x)  
∀x ⌐H(x)  
∀x H(x)  
⌐x H(x) 
Question 73 
ai, bii, ciii, div  
ai, biii, civ, dii  
aii, biii, civ, di  
aii, bii, ciii, div 
Ambiguous→ Capable of more than one interpretation or meaning.
Axiom→ An assertion that is accepted and used without a proof.
Conjecture→ An opinion preferably based on some experience or wisdom
Question 74 
P ∨ R  
P ∨ S  
Q ∨ R  
Q ∨ S  
None of These 
OptionB: Let P be TRUE and S be false then the conclusion PVS is TRUE. Now, if we make R as TRUE then the premises (P→ Q)∧(R→ S) will be false because (R→ S) will be false. Hence this option is not correct.
OptionC: Let Q be false, R be TRUE then conclusion QVR will be TRUE. Now if we make S as FALSE then Premises (P→ Q)∧(R→ S) will be FALSE because (R→ S) will be false. Hence, this option is not correct.
OptionD: Let Q be TRUE and S be FALSE then conclusion QVS will be TRUE. Now if we make R as TRUE then premises (P→ Q)∧(R→ S) will be FALSE because (R→ S) will be false.
Therefore None of the given options are correct.
Note: As per UGC NET key, given option D as correct answer.
Question 75 
(a)∃m ∀n P(m, n)
(b)∀n P(1, n)
(c) ∀m ∀n P(m, n)
(a)  True; (b)  True; (c)  False  
(a)  True; (b)  False; (c)  False  
(a)  False; (b)  False; (c)  False  
(a)  True; (b)  True; (c)  True 
StatementA is ∃m ∀n P(m, n). Here, there exists some positive integer which divides every positive integer. It is true because there is positive integer 1 which divides every positive integer.
StatementB is ∀n P(1, n). Here, 1 divided every positive integer. It is true.
StatementC is ∀m ∀n P(m, n). Here, every positive integer divided every positive integer. It is false.
Question 76 
(i)(ii)(iii)(iv)  
(ii)(iii)(i)(iv)  
(iii)(ii)(iv)(i)  
(iv)(iii)(ii)(i) 
→ Trivial proof is a proof that the implication p → q is true based on the fact that q is true.
→ Direct proof is a proof that the implication p → q is true that proceeds by showing that q must be true when p is true.
→ Indirect proof is a proof that the implication p → q is true that proceeds by showing that p must be false when q is false.
Question 77 
(a)p ∨ ~(p ∧ q)
(b)(p ∧ ~q) ∨ ~(p ∧ q)
(c)p ∧ (q ∨ r)
Which of the above propositions are tautologies?
(a) and (c)  
(b) and (c)  
(a) and (b)  
only (a) 
Question 78 
if (c Λ b)→r and ¬b→p, then (¬r Λ p)→¬c  
if (c ∨ b)→r and ¬b→¬p, then (r Λ p)→c  
if (c Λ b)→r and ¬p→b, then (¬r ∨ p)→¬c  
if (c ∨ b)→r and ¬b→¬p, then (¬r Λ p)→¬c 
“c” for my computations are correct
“b” for I pay the electric bill.
“r” for I will run out of money
“p” for the power is on.
(c Λ b) means my computations are correct and I pay the electric bill.
(¬r Λ p) means I don’t run out of money and the power is still on.
According to the statement , the option (A) is correct.
Question 79 
(a)(i), (b)(ii), (c)(iii), (d)(iv)  
(a)(ii), (b)(iii), (c)(i), (d)(iv)  
(a)(iii), (b)(ii), (c)(iv), (d)(i)  
(a)(iv), (b)(ii), (c)(iii), (d)(i) 
→ The equivalence relation translates verbally into "if and only if" and is symbolized by a doublelined, double arrow pointing to the left and right (↔). If A and B represent statements, then A ↔ B means "A if and only if B."
→ The exportation rule is a rule in logic which states that "if (P and Q), then R" is equivalent to "if P then (if Q then R)".
→ The exportation rule may be formally stated as: (P ∧ Q) → R is equivalent to P → (Q →R)
→ A mode of argumentation or a form of argument in which a proposition is disproven by following its implications logically to an absurd conclusion. Arguments that use universals such as, “always”, “never”, “everyone”, “nobody”, etc., are prone to being reduced to absurd conclusions. The fallacy is in the argument that could be reduced to absurdity  so in essence, reductio ad absurdum is a technique to expose the fallacy.
Question 80 
Identity law  
De Morgan’ s law  
Idempotent law  
Complement law 
(i). (A V B)’ = A' ∧ B'
(ii). (A ∧ B)’ = A' V B'
→ Identity Law :
(i). 1 AND A = A
(ii). 0 OR A = A
→ Complement law:
(i). A AND A'=1
(ii). A OR A'=0
→ Idempotent law:
The idempotence in the context of elements of algebras that remain invariant when raised to a positive integer power, and literally means "(the quality of having) the same power", from idem + potence (same + power).
(i). A V A=A
(ii). A ∧ A=A
According to boolean algebra
Question 81 
True  
Multi  Valued  
Flase  
Can not determined 
Here, we can minimize the boolean form into
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
In question, they are not discussed about the truth values of p, it implies that ¬p ∨ q also be True or False. So, we cannot be determined.
Question 82 
Not given any option  
Not given any option  
Not given any option  
Not given any option  
~q ∨ p ≣ q → p 
~q ∨ p ≣ q → p
Question 83 
q →p  
p→ q  
(q →p)∨(p→ q)  
(p →q)∨(q→ p)  
None of the above 
Question 84 
( ⌐ A ∨ ⌐ B ∨ ⌐ C ∨ ⌐ D)
8  
7  
15  
16 
Question 85 
Give the truth values of the following statements :
I. ∃!xP(x) → ∃xP(x)
II. ∃!x ¬ P(x) → ¬∀xP(x)
Both I & II are true.  
Both I & II are false.  
I – false, II – true  
I – true, II – false 
II: If there exists a unique x with P(x) false, then there does not exist an x with P(x) true. This is FALSE (contradiction) as all except one x can are having P(x) true.
Question 86 
(p∨q∧¬r) ∧ (p∧¬q∧r) ∧ (¬p∧q∧r)  
(p∧q∧¬r) ∧ (p∨q∧¬r) ∧ (¬p∧q∧r)  
(p∧q∧¬r) ∨ (p∧¬q∧r) ∧ (¬p∧q∧r)  
(p∧q∧¬r) ∨ (p∧¬q∧r) ∨ (¬p∧q∧r) 
Here, As per the given question, optionD is correct answer.
Question 87 
(i) There will be snow in January
(ii) What is the time now ?
(iii) Today is Sunday
(iv) You must study Discrete Mathematics.
(iii) and (iv)  
(i) and (ii)  
(i) and (iii)  
(ii) and (iv) 
(a) a meaningful declarative sentence that is true or false, or
(b) the assertion that is made by a true or false declarative sentence.
From the above four statements , statement 2 and 4 wont give meaning like true or false answers and statements 1 and 3 will give either true or false answers
Question 88 
“ There is a country that borders both India and Nepal. “
Which of the following represents the above sentence correctly ?
∃c Border(Country(c), India ∧ Nepal)  
∃c Country(c) ∧ Border(c, India) ∧ Border(c, Nepal)  
[∃c Country(c)] ⇒ [Border(c,India) ∧ Border(c, Nepal)]  
∃c Country(c) ⇒ [ Border(c, India) ∧ Border(c, Nepal)] 
→ Border(c, India) which represents border between c and india
→ Border(c, Nepal) which represents border between c and Nepal
→ “∧” represents both
Option2 represents the sentence “ There is a country that borders both India and Nepal.
Question 89 
∃x P(x) ∨ ∀x∀y ((P(x) ∨ P(y)) → x = y)  
∀x P(x) ∧ ∀x∀y ((P(x) ∨ P(y) → x = y)  
∃x P(x) ∧ ∀x∀y ((P(x) ∧ P(y)) → x = y)  
∃x P(x) ∧ ∃x∃y ((P(x) ∨ P(y)) → x = y) 
Question 90 
I. ∀m ∀n P(m, n),
II. ∃m ∀n P(m, n)
Both I and II are true  
Both I and II are false  
I – false & II – true  
I – true & II – false 
Question 91 
p → q  
q → p  
p ↔ q  
p ∨ q 
Hence OptionB is correct answer
Question 92 
p → q  
q → p  
p ↔ q  
p ∨ q 
Question 93 
(p ∨ q ∧ ⌐r) ∨ ( p ∧ q ∧ r) ∧ (⌐p ∧ q ∨ r)  
(p ∧ q ∨ r) ∧ ( p ∧ q ∧ r) ∨ (⌐q ∧ ⌐p∧ ⌐r)  
(p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)  
(p ∨ r ∧ q) ∨ ( p ∧ q ∧ r) ∨ (⌐p ∧ q ∧ r) 
Only option C consists of exactly two of the variables are true and all remaining variables deviating this rule.
In this proposition, (p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)
(p ∧ q ∧⌐ r) → p and q are true
( p ∧ ⌐q ∧ r) → p and r are true
(⌐ p ∧ q ∧ r) → q and r are true
Finally the proposition consists of “V” operation , so the entire proposition is true.
Question 94 
True and False  
False and True  
False and False  
True and True 
→ If P(x) is true for at least one element in the domain, then ∃xP(x) is true. Otherwise it is false.
→ Accordingly DeMorgan’s laws for quantifiers:the following statements are true.
¬∀xP(x) ≡ ∃x¬P(x)
¬∃xP(x) ≡ ∀x¬P(x) then the statement is ∃!x ⌐P(x) →⌐∀xP(x) is true.
Question 95 
∧ ∨ x_{2} ∨ x_{1}¬x_{1}¬x_{1}  
(x_{2}∨ ¬x_{2}) ∧ (x_{1} ∨ x_{2})  
(¬x_{1}∨ x_{2}) ∧ (¬x_{1}∨ x_{2})  
None 
Inorder traversal starts from left,root and right.
Inorder traversal = (¬x_{1}∨ x_{2}) ∧ (¬x_{1}∨ x_{2})
Question 96 
∀m. ∃n. m ≤ n and not(TwinPrime(n))  
∃m. ∀n. n ≤ m implies TwinPrime(n)  
∀m. ∃n. n ≤ m and TwinPrime(n)  
∃m. ∀n. TwinPrime(n) implies n ≤ m 
Question 97 
1/3  
1/2  
2/3  
3/4 
Question 98 
x v y  
x v (~y)  
x v (~x)  
(x=>y) v (x<=y) 
Question 99 
If the mother is happy, then Aditi got bangles.  
If Aditi got bangles, then Abhay got shoes.  
If the mother is not happy, then Asha did not get a necklace and Arun did not get a Tshirt.  
None of the above. 
Question 100 
y=> x  
~ y=> x  
~ y=> ~ x  
y=> ~ x 
Question 101 
Only (i) is true.  
Only (ii) is true.  
Both (i) and (ii) are true.  
Neither (i) nor (ii) is true. 
(ii) is false too. Note that (b^{ 3} − b) = (b − 1)b(b + 1), and at least one of these factors is even and one is divisible by 3. Hence 6  (b ^{3} − b).
Question 102 
Playing tennis.  
Watching tennis.  
Reading about tennis.  
None of the above. 
Question 103 
The workers union did not resort to a strike.  
The number of voters was more than the number of abstainers.  
(a) or (b).  
If the workers union resorted to a strike, then the number of voters was greater than or equal to the number of abstainers. 
p : abstainers > voters
q : interview repeated
r : workers strike
s : shipment missed
Premises: p IMPLIES q, (q AND r) IMPLY s
Since it is given that shipment was sent on time, s is false.
By contrapositive, (NOT q) OR (NOT r) and (NOT q) IMPLIES (NOT p) are valid conclusions.
(a) says (NOT r), which not valid since since r could be true when s is false.
(b) says voters > abstainers, which is not valid since even if voters ≤ abstainers, s could be false.
(c) says (NOT r) OR (voters > abstainers), which not valid since we can have both r and voters ≤ abstainers true and still have s false.
(d) says r IMPLIES (voters ≥ abstainers). This is valid since (NOT q) OR (NOT r) is valid, which means r is false or q is false. If r is true, then q is false and hence p is false, which means abstainers ≤ voters.
Question 104 
True  
False  
Same as truth table of Q  
Same as truth table of S 
 Equivalence condition(Both RHS and LHS should be TRUE)= P ⇔ (Q V ~Q)
 Holding condition(Both RHS and LHS may TRUE/FALSE)= Q ⇔ R
Question 105 
(X ∧ Y) → ¬ Z  
(X ∧ ¬ Z) → Y  
X → (Y ∧ ¬ Z)  
Y → (X ∧ ¬ Z) 
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option B: (X ∧ ¬Z) → Y
= ¬(X ∧ ¬Z ) ∨ Y
= ¬X ∨ Z ∨ Y
Hence, option (B) is correct.
Question 106 
F1 : P ⇒ ¬ P
F2 : (P ⇒ ¬ P) ∨ (¬ P ⇒ P)
Which of the following statements is correct?
F1 is Satisfiable, F2 is valid  
F1 is unsatisfiable, F2 is Satisfiable  
F1 is unsatisfiable, F2 is valid  
F1 and F2 both are Satisfiable 
Question 107 
((R ∨ ¬Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))
 
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))  
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ ¬P))  
((R ∨ Q) ∧ (P ∨ ¬Q) ∧ ( ¬R ∨ P)) 
((R ∨ Q) ∧ (P ∨ Q’))
(R∨Q)∧(P∨Q’)∧(R∨P)
(PR ∨ Q’R ∨ PQ) ∧ (R∨P)
PR ∨ RQ’ ∨ PQR ∨ PR ∨ PRQ’ ∨ PQ
(RQ’∨PQ’R)∨(PQR∨PQ)∨PR
RQ’ ∨ PQ ∨ PR
((R ∨ Q) ∧ (P ∨ Q’) ∧ (R ∨ P))
Method2: Using Truth table
Question 108 
I. ∀x ν(x ) ⇔ (∀y e(x, y) ⇒ ¬m(y))
II. ∀x ν(x ) ⇔ (¬(∃ym(y) ∧e(x, y)))
III. ∀x (∃y m(y) ∧e(x, y)) ⇔ ¬ν(x)
One can determine that
Only I and II are equivalent sentences  
Only II and III are equivalent sentences.  
Only I and III are equivalent sentence  
I, II, and III are equivalent sentences. 
Question 109 
I_{1} : If it is Sunday then school will not open.
The school was open.
Inference : It was not Sunday.
I_{2} : If it is Sunday then school will not open.
It was not Sunday.
Inference : The school was open.
Which of the following is correct ?
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. 
Question 110 
~ Q  
Q  
P ∧ Q  
~ P ∧ Q 
Question 111 
pV~q  
pVq  
~p Vq  
~p V ~q 
Question 112 
ListI ListII
(a) p → q (i) ¬(q → ¬p)
(b) p v q (ii) p ∧ ¬q
(c) p ∧ q (iii) ¬p → q
(d) ¬(p → q) (iv) ¬p v q
Choose the correct option from those given below:
(a)(ii);(b)(iii);(c)(i);(d)(iv)  
(a)(ii);(b)(i);(c)(iii);(d)(iv)  
(a)(iv);(b)(i);(c)(iii);(d)(ii)  
(a)(iv);(b)(iii);(c)(i);(d)(ii) 
Question 113 
Let X denote the formula: (b ⇒ a) ⇒ (a ⇒ b)
Let Y denote the formula: (a ⇒ b) ∧ b
Which of the following is TRUE?
X is satisfiable and Y is not satisfiable.  
X is satisfiable and Y is a tautology.  
X is not a tautology and Y is not satisfiable.  
X is not a tautology and Y is satisfiable.  
X is a tautology and Y is satisfiable. 
Question 114 
A ∧ B ∧ C ⇒ D  
A ∨ B ∨ C ∨ D ⇒ true  
A ∧ B ∧ C ∧ D ⇒ true  
A ∧ B ∧ C ∧ D ⇒ false 
Question 115 
~( P ∨ Q ) ∧ ~ ( Q ∨ P )  
( ~P ∨ Q ) ∧ (~ Q ∨ P )  
( P ∨ Q ) ∧ ( Q ∨ P )  
~( P ∨ Q ) → ~ ( Q ∨ P ) 
Question 116 
Consider the following statements:
Which of the following statements is/are correct?
Only S_{1}  
Only S_{2}  
Both S_{1 } and S_{2}  
Neither S_{1} nor S_{2} 
Question 117 
If he doesn’t end up in the dispensary with tummy ache, then he did not finish
his homework or the school closed late.  
If he doesn’t end up in the dispensary with tummy ache, he didn’t eat ice cream
and he didn’t play in the park.  
Both (a) and (b)  
None of the above. 
Question 118 
B() means “is a bear”
F() means “is a fish” and
E(a,b) means “ eats b”
Then what is the best meaning of
Every fish is eaten by some bear
 
Bears eat only fish  
Every bear eats fish  
Only bears eat fish 
Question 119 
∼∃x P(x)  
∃x ∼P(x)  
∀x ∼P(x)  
the given expression is not a well formed 
Question 120 
a tautology  
not a tautology  
contradiction  
not a wellformed formula 
Question 121 
∼∃x(Student(x)∧∼Failed(x))  
∼∀x(∼Student(x)∧∼Failed(x))  
∀x(∼Student(x)∧FAiled(x))  
∼∃x(Student(x)∧Failed(x)) 
Question 122 
What are you predicting by the logic:
∨x:€y:loyalto(x,y)
Everyone is loyal to someone  
Everyone is loyal to all  
Everyone is not loyal to someone
 
Everyone is loyal 
Question 123 
An inference rule that says, if you know x and you know that if x is true, then y is true, then you can conclude y is
Minmax rule  
Modus Pones rule
 
Chain rule  
None of the given options 
Question 124 
An example of a tautology is
x ∨ y  
x ∨ (¬ y)  
x ∨ (¬ x)  
(x →y) ^ (x ← y)

Question 125 
The idempotent law in the Boolean algebra says that
¬ (¬ x) = x  
x + x = x  
x + xy = x  
x(x + y) = x 
Question 126 
The proposition (p→q) ^ (¬ q ∨ (p ∨ p) is equivalent to
q → p  
p → q
 
(q → p) ∨ (p → q)  
(p → q) ∧ (q → p) 
= (p>q) ^ (q >p) (since ¬ q v p = q>p)
Question 127 
Which of the following are tautologies?
((PvQ)^Q↔Q  
(Pv(P→Q))→P  
((PvQ)^P)→Q  
((PvQ)^P)→Q 
((P v Q) ^ Q) <> Q
Lets solve LHS,
(P v Q) ^ Q = (P ^ Q) v (Q ^ Q) = (P ^ Q) v Q = PQ + Q = Q(1+P) = Q
So LHS = RHS. Hence tautology.
Similarly check for all other options, none of the other options will get LHS = RHS.
Question 128 
Zeroorder  
Firstorder  
Secondorder  
Highorder 
Question 129 
Equivalent logical expression for the Well Formed Formula (WFF),
~(∀x) F[x]
is
∀x (~F[x])  
~(∃x) F[x]  
∃x (~F[x])  
∀x F[x] 
Question 130 
The resolvent of the set of clauses
(A v B, ~A v D, C v ~B) is
A v B  
C v D  
A v C  
A v D 
Question 131 
q  
ϕ itself  
q ∨ s  
q ∨ r  
¬q ∧ s 
Question 132 
B(x) means “x is a bat”,
F (x) means “x is a ﬂy”, and
E(x, y) means “x eats y”,
what is the best English translation of
∀x(F(x) → ∀y(E(y, x) → B(y)))?
all ﬂies eat bats  
every ﬂy is eaten by some bat  
bats eat only ﬂies  
every bat eats ﬂies  
only bats eat ﬂies 
Question 133 
((p ∨ q) ∧ (r ∨ s)) ⇒ ((p ∧ r) ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (r ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (p ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (p ∨ q) 
Question 135 
If Kareena and Parineeti do not go to the shopping mall then it is not raining.  
If Kareena and Parineeti do not go to the shopping mall then it is raining.  
If it is raining then Kareena and Parineeti go to the shopping mall.  
If it is not raining then Kareena and Parineeti do not go to the shopping mall.  
None of the above 
Question 136 
(Hint: Formulate the problem using the following predicates
G – Mr. M is guilty
W(x) – x is a witness
L(x) – x is lying
A(x) – x is afraid )
Mr.M is guilty  
Mr.M is not guilty  
From these facts one cannot conclude that Mr.M is guilty  
There is a witness who is lying  
No witness is lying. 
Question 137 
∀x : [(w(x) ∧ L(x)) ⇒ (∃y : (J(y) ∧ w(y) ∧ A(x, y)))]  
∀x : [(w(x) ⇒ L(x)) ⇒ (∃y : (J(y) ∧ A(x, y)))]  
∀x∀y : [(w(x) ∧ L(x)) ⇒ (J(y) ∧ A(x, y))]  
∃y∀x : [(w(x) ∧ L(x)) ⇒ (J(y) ∧ A(x, y))]  
∀x : [(w(x) ∧ L(x)) ⇒ (∃y : (J(y) ∧ A(x, y)))] 
Question 138 
Let n=4224165165. Consider the statements p,q,r and s as below:
P: 3 divides n
Q: 5 divides n
R: 7 divides n
S: 11 divides n
Which of the following logical expressions is TRUE?
P’ ⋀ q ⋀ r ⋀ s  
P ⋀ q’ ⋀ r ⋀ s  
P ⋀ q ⋀ r’ ⋀ s  
P ⋀ q’ ⋀ r ⋀ s’ 
n = 4224165165
P = 3 divides n = True
Q = 5 divides n = True
R = 7 divides n = False
S = 11 divides n = True
Now, let’s check option wise,
Question 139 
For some n, there is a word w in the dictionary L, w has at least n meanings  
For some n, there is at least one word w in the dictionary L, w has at most n
meanings.
 
Given any n, all the words w in the dictionary L have at most n meanings.  
Given any n, there is at least one word w in the dictionary L that has at most
n meanings.
 
None of the given options is correct. 
Question 140 
~p V Q  
p V ~q  
p V q  
~p V ~q 
Question 141 
A contradiction (always false)  
A regular expression  
A tautology (always true)  
None of the above. 
Hence in question it is clearly given that the right side of ’ ⇒’ is 1(or true).Hence the complete expression is always true.
Question 142 
Which of the above logical assertions are true?
Choose the correct answer from the options given below:
(B) only  
(C) only  
(A) and (C) only  
(B) and (D) only 
This is not equivalent. It says that all (and only) conservatives are radical and electable.
2. R →(E ↔C)
This one is equivalent. if a person is a radical then they are electable if and only if they are conservative.
3. R →((C →E) ∨¬E)
This one is vacuous. It’s equivalent to ¬R ∨ (¬C ∨ E ∨ ¬E), which is true in all interpretations.
4.R ⇒ (E ⇐⇒ C) ≡ R ⇒ ((E ⇒ C) ∧ (C ⇒ E))
≡ ¬R ∨ ((¬E ∨ C) ∧ (¬C ∨ E))
≡ (¬R ∨ ¬E ∨ C) ∧ (¬R ∨ ¬C ∨ E))
Question 143 
This is a valid argument.  
Steps (C) and (E) are not correct inferences  
Steps (D) and (F) are not correct inferences  
Step (G) is not a correct inference 
Question 144 
Question 145 
f(x)=x is my friend
p(x) = x is perfect
So, they are asking about SOME. Finally, outer most parentheses will get SOME.
So, based on this we will eliminate 2 options.
They are given conditions like NOT perfect. So, we get ⌐p(x).
The final condition is ∃_{x}(f(x)∧⌐p(x))
Question 146 
Harish is happy  
No bubble gums in Rekha’s box  
No toffees in Harish’s box  
There are peppermints in Rekha’s box 
Question 147 
Akash was late for school  
Akash reached school in time  
Geyser worked  
Milkman did not deliver milk 