Prepositional-Logic

Question 1

Consider the first-order logic sentence F: ∀x(∃yR(x,y)). Assuming non-empty 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))
 
A
IV only
B
I and IV only
C
II only
D
II and III only
       Engineering-Mathematics       Prepositional-Logic       Gate 2017 set-01
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)
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
a tautology
B
a contradiction
C
always TRUE when p is FALSE
D
always TRUE when q is TRUE
       Engineering-Mathematics       Prepositional-Logic       Gate 2017 set-01
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.
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

A
(¬p ∧ r) ∧ (¬r → (p ∧ q))
B
(¬p ∧ r) ∧ ((p ∧ q) → ¬r)
C
(¬p ∧ r) ∨ ((p ∧ q) → ¬r)
D
(¬p ∧ r) ∨ (r → (p ∧ q))
       Engineering-Mathematics       Prepositional-Logic       GATE 2017(set-02)
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
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 satisfies ¬((p ⇒ q) ∧ (¬r ∨ ¬s))  is _________.

 
A
11
B
12
C
13
D
14
       Engineering-Mathematics       Prepositional-Logic       2016 set-01
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.
Question 5
 
A
If a person is known to corrupt, he is kind
B
If a person is not known to be corrupt, he is not kind
C
If a person is kind, he is not known to be corrupt
D
If a person is not kind, he is not known to be corrupt
       Engineering-Mathematics       Prepositional-Logic       GATE 2015 -(Set-2)
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
Question 6

A
The result is head
B
The result is tail
C
If the person is of Type 2, then the result is tail
D
If the person is of Type 1, then the result is tail
       Engineering-Mathematics       Prepositional-Logic       GATE 2015(Set-03)
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).
Question 7
Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?
A
((p↔q)∧r)∨(p∧q∧∼r)
B
(∼(p↔q )∧r)∨(p∧q∧∼r)
C
((p→q)∧r)∨(p∧q∧∼r)
D
(∼(p↔q)∧r)∧(p∧q∧∼r)
       Engineering-Mathematics       Prepositional-Logic       GATE 2014(Set-01)
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.
Question 8
Which one of the following Boolean expressions is NOT a tautology?
A
((a ⟶ b) ∧ (b ⟶ c)) ⟶ (a ⟶ c)
B
(a ⟷ c) ⟶ (∽ b ⟶ (a ∧ c))
C
(a ∧ b ∧ c) ⟶ (c ∨ a)
D
a ⟶ (b ⟶ a)
       Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -02
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
Question 9
A
Only L is TRUE.
B
Only M is TRUE.
C
Only N is TRUE.
D
L, M and N are TRUE.
       Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -03
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.
Question 10
The CORRECT formula for the sentence, “not all rainy days are cold” is
A
∀d (Rainy(d) ∧∼Cold(d))
B
∀d (∼Rainy(d) → Cold(d))
C
∃d (∼Rainy(d) → Cold(d))
D
∃d (Rainy(d) ∧∼Cold(d))
       Engineering-Mathematics       Prepositional-Logic       Gate 2014 Set -03
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]
Question 11
A
∃x(F(x)∧¬P(x))
B
∃x(¬F(x)∧P(x))
C
∃x(¬F(x)∧¬P(x))
D
¬∃x(F(x)∧P(x))
       Engineering-Mathematics       Prepositional-Logic       Gate 2013
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.
Question 12
A
0
B
1
C
2
D
3
       Engineering-Mathematics       Prepositional-Logic       Gate 2013
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.
Question 13
Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?
A
((∀x(P(x)∨Q(x))))⟹((∀xP(x))∨(∀xQ(x)))
B
(∀x(P(x)⟹Q(x)))⟹((∀xP(x))⟹(∀xQ(x)))
C
(∀x(P(x))⟹∀x(Q(x)))⟹(∀x(P(x)⟹Q(x)))
D
(∀x(P(x))⇔(∀x(Q(x))))⟹(∀x(P(x)⇔Q(x)))
       Engineering-Mathematics       Prepositional-Logic       Gate 2005-IT
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
Question 14
 
A
ac
B
bc
C
ab
D
cc
       Engineering-Mathematics       Prepositional-Logic       Gate-1995
Question 14 Explanation: 
concat (a, head (tail (tail (acbc))))
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  
A
true
B
multiple valued
C
false
D
cannot be determined
       Engineering-Mathematics       Prepositional-Logic       Gate-1995
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.
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.
A
True
B
False
       Engineering-Mathematics       Prepositional-Logic       Gate-1994
Question 16 Explanation: 

So, "imply" is False making "does not imply" True.
Question 17
The proposition p ∧(~p ∨ q) is:
A
a tautology
B
logically equivalent to p ∧ q
C
logically equivalent to p ∨ q
D
a contradiction
E
none of the above
       Engineering-Mathematics       Prepositional-Logic       Gate-1993
Question 17 Explanation: 
p ∧(~p ∨ q)
(p ∧ ~p) ∨ (p ∧ q)
F ∨ (p ∧ q)
(p ∧ q)
Question 18
Which of the following predicate calculus statements is/are valid:
A
(∀x) P(x) ∨ (∀x)Q(x) → (∀x){P(x) ∨ Q(x)}
B
(∃x)P(x) ∧ ∃(x)Q(x) → (∃x){P(x) ∧ Q(x)}
C
(∀x){P(x) ∨ Q(x)} → (∀x)P(x) ∨ (∀x)Q(x)
D
(∃x){P(x) ∨ Q(x)} → ~(∀x)P(x) ∨ (∃x)Q(x)
       Engineering-Mathematics       Prepositional-Logic       Gate-1992
Question 18 Explanation: 
(A) Valid
(B) Invalid
(C) Invalid
(D) Invalid
Question 19
Which of the following is/are tautology
A
a ∨ b → b ∧ c
B
a ∧ b → b ∨ c
C
a ∨ b → (b → c)
D
a → b → (b → c)
       Engineering-Mathematics       Prepositional-Logic       Gate-1992
Question 19 Explanation: 
Question 20
 
A
Both F1 and F2 are tautologies
B
The conjunction F1 ∧ F2 is not satisfiable
C
Neither is tautologous
D
Neither is satisfiable
E
None of the above
       Engineering-Mathematics       Prepositional-Logic       Gate-1991
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 ∧ F2 is not satisfiable means F1 ∧ F2 is always false.
And False → anything is always true.
There are 20 questions to complete.