Propositional-Logic
Question 1 |
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
Note that W is a predicate formula without any free occurrence of x.
 | |
 | |
 | |
 |
Question 1 Explanation:
Question 2 |
Consider the first-order logic sentence
where ψ(s,t,u,v,w,x,y) is a quantifier-free first-order 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.
|
Question 2 Explanation:
φ = ∃s∃t∃u∀v∀w∀x∀y ψ (s,t,u,v,w,x,y)
"∃" 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’.
"∃" 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 |
The statement (¬p) ⇒ (¬q) is logically equivalent to which of the statements below?
-
I. p ⇒ q
II. q ⇒ p
III. (¬q) ∨ p
IV. (¬p) ∨ q
I only | |
I and IV only | |
II only | |
II and III only |
Question 3 Explanation:
Method 1:
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.
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 |
Consider the following expressions:
-
(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 |
Question 4 Explanation:
The expression is logically implied by P ∧ (P → Q) means
(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))
(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 well-formed 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)) |
Question 5 Explanation:
For the formulae to be valid there should not be implication like T → F.
But in option (D), we can generate T → F.
Hence, not valid.
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)
|
Question 6 Explanation:
Since P→R=¬P∨R
[∀x ∃y (P(x,y)→R(x,y)]↔[∀x ∃y ( ¬ P(x,y)∨R(x,y)] is a tautology.
[∀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 I1 and I2 are correct inferences | |
I1 is correct but I2 is not a correct inference | |
I1 is not correct but I2 is a correct inference | |
Both I1 and I2 are not correct inferences |
Question 7 Explanation:
I1: If it rains then the cricket match will not be played.
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.
I2: 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.
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.
I2: 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 |
∃x (real(x) ∨ rational(x)) | |
∀x (real(x) → rational(x)) | |
∃x (real(x) ∧ rational(x)) | |
∃x (rational(x) → real(x)) |
Question 8 Explanation:
∃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) 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 |
Question 9 Explanation:
Statement: x is not equal to 1 and if there exists some z for all y such that product of y and z is x, then y is either the no. itselfor 1.
This is the definition of prime nos.
This is the definition of prime nos.
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 |
Question 10 Explanation:
F(x,y,t) ⇒ Person 'x' can fool person 'y' at time 't'.
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.
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))
|
Question 11 Explanation:
Interpreting the options will lead to
(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.
(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 ?
Which one of the following is equivalent to P Ú Q ?¬Q□¬P
| |
P□¬Q
| |
¬P□Q
| |
¬P□¬Q
|
Question 12 Explanation:
The options are simple to draw the truth table then go with the corresponding options.
P∨Q=P□️Q
So, option B is correct.
P∨Q=P□️Q
So, option B is correct.
Question 13 |
Consider the following well-formed formulae:
Which of the above are equivalent?
Which of the above are equivalent?I and III | |
I and IV
| |
II and III
| |
II and IV
|
Question 13 Explanation:
I) ¬∀x(P(x)) = ∃x(¬P(x)) [De morgan's Law]
II ) ¬∃x(P(x))= ∀x(~P(x))
III) ¬∃x(¬P(x)) = ∀x(P(x))
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)) |
Question 14 Explanation:
Go through the options.
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.
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?
Only I and II
| |
Only I, II and III | |
Only I, II and IV
| |
All of I, II, III and IV |
Question 15 Explanation:
I. P∨∼Q (✔️)
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 (✔️)
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 |
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)→β]
|
Question 16 Explanation:
[(∃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 vice-versa).
Here, LHS = RHS
So, Option C is valid.
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 vice-versa).
Here, LHS = RHS
So, Option C is valid.
Question 17 |
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))] |
Question 17 Explanation:
Question 18 |
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))
|
Question 18 Explanation:
Option (A) and (C) are same, because in option (C) the given expression is
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.
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 19 |
Which one of these first-order 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)
|
Question 19 Explanation:
LHS = for every x, if P holds then Q holds
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️❌)
RHS = if P(x) holds for all x, then Q(x) holds for all x
LHS ⇒ RHS (✔)
RHS ⇒ LHS (️❌)
Question 20 |
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
|
Question 20 Explanation:
It’s better to draw truth table such that
Both P1 and P2 are not Tautologies.
Both P1 and P2 are not Tautologies.
Question 21 |
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)}]
|
Question 21 Explanation:
Tigers and lions attack if they are hungry (or) threatened.
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 vice-versa.
Then answer is
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
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 vice-versa.
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 22 |
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 22 Explanation:
The given relationis known to be symmetry. We have both symmetric relations possible as well as antisymmetric but neither always holds for all sets. So they both are valid but are satisfiable.
Question 23 |
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)]]
|
Question 23 Explanation:
Option A: If x is a teacher, then there exist a y such that if y is a student , then y likes 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.
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 24 |
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
|
Question 24 Explanation:
X: (P∨Q) → R
⇒ ∼(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 (✔️)
⇒ ∼(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 25 |
(∃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)))
|
Question 25 Explanation:
Don't confuse with '∧' and '→'
'∧' → 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.
'∧' → 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 26 |
The following propositional statement is (P ⇒ (QÚR)) ⇒ ((P Ù Q) ⇒ R)
satisfiable but not valid
| |
valid
| |
a contradiction
| |
None of the above
|
Question 26 Explanation:
(P ⇒ (QÚR)) ⇒ ((P Ù Q) ⇒ R)
(P→(Q∨R)) → (P∨Q)→R
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)
(P→(Q∨R)) → (P∨Q)→R
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 27 |
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)[β])
|
Question 27 Explanation:
Option D is valid.
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.
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 28 |
Consider the following formula a and its two interpretations I1 and I2
Which of the following statements is true?
Which of the following statements is true?
I1 satisfies α, I2 does not | |
I2 satisfies α, I1 does not
| |
Neither I2 nor I1 satisfies α
| |
Both I1 and I2 satisfy α
|
Question 28 Explanation:
Given that:
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒(∀x)[¬Px]
Qyy is always true, because y divide y, then ¬Qyy 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 I1 and I2 satisfies α.
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒(∀x)[¬Px]
Qyy is always true, because y divide y, then ¬Qyy 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 I1 and I2 satisfies α.
Question 29 |
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
|
Question 29 Explanation:
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R))
It is may be True (or) False depending on values. So this is not valid.
It is may be True (or) False depending on values. So this is not valid.
Question 30 |
“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 |
Question 30 Explanation:
"If X then Y unless Z" ⇒ ¬Z → (X→Y)
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option A:
(X ∧ ¬Z) → Y = ¬(X ∧ ¬Z ) ∨ Y = ¬X ∨ Z ∨ Y Hence, option (A) is correct.
Question 31 |
Let a, b, c, d be propositions. Assume that the equivalence a ↔ (b ∨-b) and b ↔ c hold. Then the truth-value of the formula (a ∧ b) → (a ∧ c) ∨ d is always
True | |
False | |
Same as the truth-value of b | |
Same as the truth-value of d |
Question 31 Explanation:
a ↔ (b ∨-b) and b ↔ c
Given ⇒ (a∧b) → (a∧c) ∨d
⇒ (a∧b) → (a∧c) ∨d (b⇔c)
⇒ T∨d
⇒ T
Given ⇒ (a∧b) → (a∧c) ∨d
⇒ (a∧b) → (a∧c) ∨d (b⇔c)
⇒ T∨d
⇒ T
Question 32 |
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 |
Question 32 Explanation:
"I stay only you go" = "If I 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.
⇒ 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 33 |
Which of the following propositions is a tautology?
(p ∨ q) → p | |
p ∨ (q → p) | |
p ∨ (p → q) | |
p → (p → q) |
Question 33 Explanation:
Question 34 |
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) |
Question 34 Explanation:
When x = F and y = F
then option (D) will be False.
then option (D) will be False.
Question 35 |
F1 is satisfiable, F2 is valid | |
F1 unsatisfiable, F2 is satisfiable | |
F1 is unsatisfiable, F2 is valid | |
F1 and F2 are both satisfiable |
Question 35 Explanation:
F1 is satisfiable; F2 is valid.
Question 36 |
(P ⇒ Q) ∧ (Q ⇒ R) ⇒ (P ⇒ R) | |
(P ⇒ Q) ⇒ (¬P ⇒ ¬Q) | |
(P ∧ (¬P ∨ ¬Q)) ⇒ Q | |
(P ⇒ R) ∨ (Q ⇒ R) ⇒ ((P ∨ Q) ⇒ R) |
Question 36 Explanation:
To prove any well formed formula valid or tautology try to use this analogy.
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.
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 37 |
Which of the following well-formed formulas are equivalent?
P → Q | |
¬Q → ¬P | |
¬P ∨ Q | |
¬Q → P | |
A, B and C. |
Question 37 Explanation:
P → Q ⇔ ¬P ∨ Q
¬Q → ¬P ⇔ Q ∨ ¬P
¬P ∨ Q ⇔ ¬P ∨ Q
¬Q → P ⇔ Q ∨ P
A, B and C are equivalent.
¬Q → ¬P ⇔ Q ∨ ¬P
¬P ∨ Q ⇔ ¬P ∨ Q
¬Q → P ⇔ Q ∨ P
A, B and C are equivalent.
There are 37 questions to complete.