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))
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 satisfies ¬((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 |
Consider the following statements:
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 |
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 |
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 |
Consider the following statements:
P:Good mobile phones are not cheap
Q:Cheap mobile phones are not good
L:P implies Q
M:Q implies P
N:P is equivalent to Q
Which one of the following about L, M, and N is CORRECT?
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 |
What is the logical translation of the following statement?
"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)) |
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 |
The following code segment is excuted on a process which allows only register operands in its instructuoins. Each instructions can have atmost two sources operands and one destination opernad. Assume that all variables are dead after this code segement
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 F1 and F2 are tautologies | |
The conjunction F1 ∧ F2 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 ∧ F2 is not satisfiable means F1 ∧ F2 is always false.
And False → anything is always true.
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.