PrepositionalLogic
Question 1 
Consider the firstorder logic sentence F: ∀x(∃yR(x,y)). Assuming nonempty logical domains, which of the sentences below are implied by F?

I. ∃y(∃xR(x,y))
II. ∃y(∀xR(x,y))
III. ∀y(∃xR(x,y))
IV. ¬∃x(∀y¬R(x,y))
IV only  
I and IV only  
II only  
II and III only 
Question 1 Explanation:
Lets convert the given first order logic sentence into some english sentence.
F: ∀x(∃yR(x,y)) (given)
: For all girls there exist a boyfriend
(x for girls and y for boys)
I: ∃y(∃xR(x,y))
: There exist some boys who have girlfriends.
(Subset of statement F, so True)
II: ∃y(∀xR(x,y))
: There exists some boys for which all the girls are girlfriend. (False)
III: ∀y(∃xR(x,y))
: For all boys exists a girlfriend. (False)
IV: ~∃x(∀y~R(x,y))
= ∀x(~∀y~R(x,y))
= ∀x(∃yR(x,y)) (∵ ~∀y=∃y, ~∃x=∀x)
(True)
F: ∀x(∃yR(x,y)) (given)
: For all girls there exist a boyfriend
(x for girls and y for boys)
I: ∃y(∃xR(x,y))
: There exist some boys who have girlfriends.
(Subset of statement F, so True)
II: ∃y(∀xR(x,y))
: There exists some boys for which all the girls are girlfriend. (False)
III: ∀y(∃xR(x,y))
: For all boys exists a girlfriend. (False)
IV: ~∃x(∀y~R(x,y))
= ∀x(~∀y~R(x,y))
= ∀x(∃yR(x,y)) (∵ ~∀y=∃y, ~∃x=∀x)
(True)
Question 2 
Let p, q and r be prepositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is
a tautology  
a contradiction  
always TRUE when p is FALSE  
always TRUE when q is TRUE 
Question 2 Explanation:
Given that (p→q)→r is a contradiction.
So r = F and (p→q) = T.
We have to evaluate the expression
(r→p)→q
Since r = F, (r→p) = T (As F→p, is always true)
The final expression is T→q and this is true when q is true, hence option D.
So r = F and (p→q) = T.
We have to evaluate the expression
(r→p)→q
Since r = F, (r→p) = T (As F→p, is always true)
The final expression is T→q and this is true when q is true, hence option D.
Question 3 
Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by
(¬p ∧ r) ∧ (¬r → (p ∧ q))  
(¬p ∧ r) ∧ ((p ∧ q) → ¬r)  
(¬p ∧ r) ∨ ((p ∧ q) → ¬r)  
(¬p ∧ r) ∨ (r → (p ∧ q)) 
Question 3 Explanation:
p: It is raining
q: It is cold
r: It is pleasant
“If it is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold.”
We can divide the statement into two parts with “Conjunction”.
i.e., ¬r→(p∧q) ⇾(2)
From (1) & (2), the given statement can be represented as
q: It is cold
r: It is pleasant
“If it is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold.”
We can divide the statement into two parts with “Conjunction”.
i.e., ¬r→(p∧q) ⇾(2)
From (1) & (2), the given statement can be represented as
Question 4 
Let p,q,r,s represent the following propositions.

p: x ∈ {8,9,10,11,12}
q: x is a composite number
r: x is a perfect square
s: x is a prime number
The integer x≥2 which satisﬁes ¬((p ⇒ q) ∧ (¬r ∨ ¬s)) is _________.
11  
12  
13  
14 
Question 4 Explanation:
Given,
~((p→q) ∧ (~r ∨ ~S))
⇒ first simplify the given statement by converging them to ∧, ∨
⇒ [~(p→q) ∨ (~(~r ∨ ~s)]
Demorgan’s law:
⇒ [~(~p ∨ q) ∨ (r ∧ s)]
∵ p→q ≡ ~p ∨ q
⇒ [(p ∧ ~q) ∨ (r ∧ s)]
p ∧ ~q is {8,9,10,11,12} ∧ {not a composite number} i.e. {11}
r ∧ s is {perfect square} ∧ {prime} i.e. no answer
So, the one and only answer is 11.
~((p→q) ∧ (~r ∨ ~S))
⇒ first simplify the given statement by converging them to ∧, ∨
⇒ [~(p→q) ∨ (~(~r ∨ ~s)]
Demorgan’s law:
⇒ [~(~p ∨ q) ∨ (r ∧ s)]
∵ p→q ≡ ~p ∨ q
⇒ [(p ∧ ~q) ∨ (r ∧ s)]
p ∧ ~q is {8,9,10,11,12} ∧ {not a composite number} i.e. {11}
r ∧ s is {perfect square} ∧ {prime} i.e. no answer
So, the one and only answer is 11.
Question 5 
If a person is known to corrupt, he is kind
 
If a person is not known to be corrupt, he is not kind
 
If a person is kind, he is not known to be corrupt
 
If a person is not kind, he is not known to be corrupt

Question 5 Explanation:
Let p: candidate known to be corrupt
q: candidate will be elected
r: candidate is kind
then S1=p→~q
=q→~p (conrapositive rule)
and S2:r→q⇒r→~p (transitive rule)
i.e., If a person is kind, he is not known to be corrupt ∴ Option is C
q: candidate will be elected
r: candidate is kind
then S1=p→~q
=q→~p (conrapositive rule)
and S2:r→q⇒r→~p (transitive rule)
i.e., If a person is kind, he is not known to be corrupt ∴ Option is C
Question 6 
The result is head  
The result is tail
 
If the person is of Type 2, then the result is tail  
If the person is of Type 1, then the result is tail 
Question 6 Explanation:
We do not know the type of person from whom those words are coming from and so we can have two cases.
Case 1:
The person who speaks truth. This definitely implies that result of toss is Head.
Case 2:
The person who lies. In this the reality will be the negation of the statement.
The negation of (x⇔y) is exactly one of x or y holds. "The result of the toss is head if and only if I am telling the truth". So here two possibilities are there,
→ It is head and lie spoken.
→ It is not head and truth spoken.
Clearly, the second one cannot speaks the truth. So finally it is head.
Hence, option (A).
Case 1:
The person who speaks truth. This definitely implies that result of toss is Head.
Case 2:
The person who lies. In this the reality will be the negation of the statement.
The negation of (x⇔y) is exactly one of x or y holds. "The result of the toss is head if and only if I am telling the truth". So here two possibilities are there,
→ It is head and lie spoken.
→ It is not head and truth spoken.
Clearly, the second one cannot speaks the truth. So finally it is head.
Hence, option (A).
Question 7 
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
((p↔q)∧r)∨(p∧q∧∼r)  
(∼(p↔q )∧r)∨(p∧q∧∼r)  
((p→q)∧r)∨(p∧q∧∼r)  
(∼(p↔q)∧r)∧(p∧q∧∼r) 
Question 7 Explanation:
Method 1: construct the tables for all options and check with T, T, F combinations.
Method2: directly check with one of {TTF, TFT, FTT} options.
As there are two T’s in each option, replace them and check with the third value.
Eg: Place p=q= T
(∼(p↔q)∧r)∨(p∧q∧∼r)
=(∼(T↔T)∧r)∨(T∧T∧∼r)
=(∼(T)∧r)∨(T∧∼r)
=(F∧r)∨(T∧∼r)
=(F)∨(∼r)
=∼r
This is true for r=F.
Similarly with p=r=T and q=F.
q=r=T and p=F
Option B is the answer.
Method2: directly check with one of {TTF, TFT, FTT} options.
As there are two T’s in each option, replace them and check with the third value.
Eg: Place p=q= T
(∼(p↔q)∧r)∨(p∧q∧∼r)
=(∼(T↔T)∧r)∨(T∧T∧∼r)
=(∼(T)∧r)∨(T∧∼r)
=(F∧r)∨(T∧∼r)
=(F)∨(∼r)
=∼r
This is true for r=F.
Similarly with p=r=T and q=F.
q=r=T and p=F
Option B is the answer.
Question 8 
Which one of the following Boolean expressions is NOT a tautology?
((a ⟶ b) ∧ (b ⟶ c)) ⟶ (a ⟶ c)  
(a ⟷ c) ⟶ (∽ b ⟶ (a ∧ c))  
(a ∧ b ∧ c) ⟶ (c ∨ a)  
a ⟶ (b ⟶ a) 
Question 8 Explanation:
A:
((a → b) ∧ (b → c)) → (a → c)
If (a → b) is false with a = T, b = F,
then (F ∧ (b → c)) → (a → c)
F → (a → c)
which is True for any (a → c)
This is tautology.
B:
(a ⟷ c) ⟶ (∽b ⟶ (a ∧ c))
For (a ⟷ c) be True and
∽b → (a ∧ c) should be False
Let a = c = F
(F → F) → (∽b (F ∩ F))
T → (∽b → F)
This is False for b = F
So, this is not True.
C:
(a ∧ b ∧ c) ⟶ (c ∨ a)
(c ∨ a) is False only for a = c = F
if (c ∨ a) is False
(F ∧ b ∧ F) → F
F → F which is Tautology
True always.
D:
a ⟶ (b ⟶ a)
a ⟶ (~b ∨ a)
(~a ∨ a) ∨ ~b = T ∨ ~b = T which is tautology
((a → b) ∧ (b → c)) → (a → c)
If (a → b) is false with a = T, b = F,
then (F ∧ (b → c)) → (a → c)
F → (a → c)
which is True for any (a → c)
This is tautology.
B:
(a ⟷ c) ⟶ (∽b ⟶ (a ∧ c))
For (a ⟷ c) be True and
∽b → (a ∧ c) should be False
Let a = c = F
(F → F) → (∽b (F ∩ F))
T → (∽b → F)
This is False for b = F
So, this is not True.
C:
(a ∧ b ∧ c) ⟶ (c ∨ a)
(c ∨ a) is False only for a = c = F
if (c ∨ a) is False
(F ∧ b ∧ F) → F
F → F which is Tautology
True always.
D:
a ⟶ (b ⟶ a)
a ⟶ (~b ∨ a)
(~a ∨ a) ∨ ~b = T ∨ ~b = T which is tautology
Question 9 
Only L is TRUE.  
Only M is TRUE.  
Only N is TRUE.  
L, M and N are TRUE. 
Question 9 Explanation:
In the given statements observe that "not cheap" & cheap, "good & not good" are used.
So, given statement can be sub divided such that we can utilize the negation of this atomic statements.
Suppose, X is Good mobile and Y is cheap then
P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))
Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))
All these are contra positive.
All L, M, N are true.
So, given statement can be sub divided such that we can utilize the negation of this atomic statements.
Suppose, X is Good mobile and Y is cheap then
P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))
Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))
All these are contra positive.
All L, M, N are true.
Question 10 
The CORRECT formula for the sentence, “not all rainy days are cold” is
∀d (Rainy(d) ∧∼Cold(d))  
∀d (∼Rainy(d) → Cold(d))  
∃d (∼Rainy(d) → Cold(d))  
∃d (Rainy(d) ∧∼Cold(d)) 
Question 10 Explanation:
Not all rainy days are cold
= ∼[∀rainy days are cold]
= ∼[∀ days (rainy days ⇒ cold days]
= ∃ days[∼(cold days ∨ ∼rainy days)]
= ∃ days[rainy days ∧ ∼cold days]
= ∼[∀rainy days are cold]
= ∼[∀ days (rainy days ⇒ cold days]
= ∃ days[∼(cold days ∨ ∼rainy days)]
= ∃ days[rainy days ∧ ∼cold days]
Question 11 
∃x(F(x)∧¬P(x))  
∃x(¬F(x)∧P(x))  
∃x(¬F(x)∧¬P(x))  
¬∃x(F(x)∧P(x)) 
Question 11 Explanation:
Let F(x) = x is my friend
P(x) = x is perfect
The meaning of ∃x(P(x)∧F(x)) is atleast one person who is my friend and perfect.
The negation of ∃x(P(x)∧F(x)) is “This is not the case that atlease one person who is my friend and perfect”.
So ~∃x(P(x)∧F(x)) is none of my friends are perfect.
P(x) = x is perfect
The meaning of ∃x(P(x)∧F(x)) is atleast one person who is my friend and perfect.
The negation of ∃x(P(x)∧F(x)) is “This is not the case that atlease one person who is my friend and perfect”.
So ~∃x(P(x)∧F(x)) is none of my friends are perfect.
Question 12 
0  
1  
2  
3 
Question 12 Explanation:
After applying the code motion optimization the statement d = c*a; and e = c+a; can be moved down to else block as d and c are not used anywhere before that and also value of a and c is not changing.
In the above code total number of spills to memory is 1.
In the above code total number of spills to memory is 1.
Question 13 
Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?
((∀x(P(x)∨Q(x))))⟹((∀xP(x))∨(∀xQ(x)))  
(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))  
(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))  
(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))

Question 13 Explanation:
LHS: (P(x) ⟹Q(x)) which is True for every value thus ∀x(P(x) ⟹ Q(x)) becomes True.
RHS: (∀xP(x)) and (∀xQ(x)) both becomes False for assumed values which implies F→F and result will be True.
∴ LHS = RHS
RHS: (∀xP(x)) and (∀xQ(x)) both becomes False for assumed values which implies F→F and result will be True.
∴ LHS = RHS
Question 14 
ac  
bc  
ab  
cc 
Question 14 Explanation:
concat (a, head (tail (tail (acbc))))
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
Question 15 
If the proposition ¬p ⇒ ν is true, then the truth value of the proposition ¬p ∨ (p ⇒ q), where ¬ is negation, ‘∨’ is inclusive or and ⇒ is implication, is
true  
multiple valued  
false  
cannot be determined 
Question 15 Explanation:
From the axiom ¬p → q, we can conclude that p ∨ q.
So, either p or q must be True.
Now,
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
Since nothing c an be said about the truth values of p, it implies that ¬p ∨ q can also be True or False. Hence, the value cannot be determined.
So, either p or q must be True.
Now,
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
Since nothing c an be said about the truth values of p, it implies that ¬p ∨ q can also be True or False. Hence, the value cannot be determined.
Question 16 
Let p and q be propositions. Using only the truth table decide whether p ⇔ q does not imply p → q is true or false.
True  
False 
Question 16 Explanation:
So, "imply" is False making "does not imply" True.
Question 17 
The proposition p ∧(~p ∨ q) is:
a tautology  
logically equivalent to p ∧ q  
logically equivalent to p ∨ q  
a contradiction  
none of the above 
Question 17 Explanation:
p ∧(~p ∨ q)
(p ∧ ~p) ∨ (p ∧ q)
F ∨ (p ∧ q)
(p ∧ q)
(p ∧ ~p) ∨ (p ∧ q)
F ∨ (p ∧ q)
(p ∧ q)
Question 18 
Which of the following predicate calculus statements is/are valid:
(∀x) P(x) ∨ (∀x)Q(x) → (∀x){P(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) 
Question 18 Explanation:
(A) Valid
(B) Invalid
(C) Invalid
(D) Invalid
(B) Invalid
(C) Invalid
(D) Invalid
Question 19 
Which of the following is/are tautology
a ∨ b → b ∧ c  
a ∧ b → b ∨ c
 
a ∨ b → (b → c)  
a → b → (b → c) 
Question 19 Explanation:
Question 20 
Both F_{1} and F_{2} are tautologies  
The conjunction F_{1} ∧ F_{2} is not satisfiable  
Neither is tautologous  
Neither is satisfiable  
None of the above 
Question 20 Explanation:
For the propositional formula A→B to be tautology the T→F condition should never arise.
So, in option (B) it is saying that F< sub>1 ∧ F_{2} is not satisfiable means F_{1} ∧ F_{2} is always false.
And False → anything is always true.
So, in option (B) it is saying that F< sub>1 ∧ F_{2} is not satisfiable means F_{1} ∧ F_{2} is always false.
And False → anything is always true.
There are 20 questions to complete.