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 
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 
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)) 
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 
~((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

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 
In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following:
“The result of the toss is head if and only if I am telling the truth.”
Which of the following options is correct?
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 
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 
((p↔q)∧r)∨(p∧q∧∼r)  
(∼(p↔q )∧r)∨(p∧q∧∼r)  
((p→q)∧r)∨(p∧q∧∼r)  
(∼(p↔q)∧r)∧(p∧q∧∼r) 
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 
((a ⟶ b) ∧ (b ⟶ c)) ⟶ (a ⟶ c)  
(a ⟷ c) ⟶ (∽ b ⟶ (a ∧ c))  
(a ∧ b ∧ c) ⟶ (c ∨ a)  
a ⟶ (b ⟶ 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
Question 9 
Only L is TRUE.  
Only M is TRUE.  
Only N is TRUE.  
L, M and 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 
∀d (Rainy(d) ∧∼Cold(d))  
∀d (∼Rainy(d) → Cold(d))  
∃d (∼Rainy(d) → Cold(d))  
∃d (Rainy(d) ∧∼Cold(d)) 
= ∼[∀rainy days are cold]
= ∼[∀ days (rainy days ⇒ cold days]
= ∃ days[∼(cold days ∨ ∼rainy days)]
= ∃ days[rainy days ∧ ∼cold days]
Question 11 
"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) = 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 
In the above code total number of spills to memory is 1.
Question 13 
((∀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)))

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 
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
Question 15 
true  
multiple valued  
false  
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 
True  
False 
So, "imply" is False making "does not imply" True.
Question 17 
a tautology  
logically equivalent to p ∧ q  
logically equivalent to p ∨ q  
a contradiction  
none of the above 
(p ∧ ~p) ∨ (p ∧ q)
F ∨ (p ∧ q)
(p ∧ q)
Question 18 
(∀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) 
(B) Invalid
(C) Invalid
(D) Invalid
Question 19 
a ∨ b → b ∧ c  
a ∧ b → b ∨ c
 
a ∨ b → (b → c)  
a → b → (b → c) 
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 
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.