Mathematical Logic Questions and Answers | Computer Science Quiz

Answer: (a) ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)
Explanation:
Option (a) is well known valid formula (tautology) because it is a rule of inference called a hypothetical syllogism. By applying Boolean algebra and simplifying, we can show that (b), (c), and (d) are invalid.
For example,
Choice (b) ≡(P ⇒ Q) ⇒ (¬P ⇒ ¬Q)
≡(P ⇒ Q) ⇒ (P ⇒Q’)
≡(P’ + Q) ⇒ (P + Q’)
≡(P’ + Q)’ + (P+Q’)
≡PQ’ + P+Q’
≡P+ Q’
≠1
So, invalid.

Answer: (a) (∀x) P(x)∨ (∀x) Q(x) → (∀x) {P(x) ∨ Q(x)}
Explanation:
According to distributive properties
∀x (P(x) ∧ Q(x)) ↔ ∀xP(x) ∧ ∀xQ(x)
(∀xP(x) ∨∀xQ(x)) → ∀x(P(x) ∨ Q(x))
∃x (P(x) ∨ Q(x)) ↔ ∃xP(x)∨∃xQ(x)
∃x(P(x) ∧Q(X)) → ∃xP(x) ∧∃xQ(X)
So option (a) is valid.

Answer: (b) (a ∧ b) → (b ∨ c)
Explanation:
(a) (a ∨ b) → (b ∧ c)
≡ (a + b)’ + bc
≡ a’b’+ bc
Therefore, ((a ∨ b) → (b ∧ C)) is contingency and not tautology.
(b) (a ∧ b) → (b ∨ c)
≡ ab → b + c
≡ (ab)’ + b + c
≡a’ + b’ + b + c
≡a’ + 1 + c
≡1
So ((a ∧b) → (b ∨c)) is tautology.
(c) (a ∨ b) → (b → c)
≡ (a + b) → (b’ + c)
≡(a +b)’ +b’ + c
≡a’b’ + b’ + c
≡b’ + c
So ((a ∨b) → (b → c)) is contingency but not a tautology.
(d) (a → b) → (b → c)
≡(a’ + b) → (b’ + c )
≡(a’ + b)’ + b’ + c
≡ ab’ + b’ + c
≡b’ + c
Therefore, ((a → b) → (b → c)) is contingency but not tautology.

Answer: (b) ⇔ (p ∧ q)
Explanation:
The proposition p ∧ (~p ∨ q)
≡p(p’ + q) ≡pq
≡p ∧ q

Answer: TRUE
Explanation:

From the truth table, (p ↔ q) → (p → ~q) is not a tautology, hence it is true that p ↔ q doesn’t imply p →¬q.

Answer: (d) Cannot be determined
Explanation:

Now since ¬p → q is given true, We reduce the truth table as follows.

In the reduced truth table we need to find the true value of ¬p ∨(p → q) ≡p’ +(p → q) ≡p’ + p’ +q ≡p’ + q
The truth value of p’ + q in the reduced truth table is given below.

Since in the reduced truth table also, the given expression is sometimes true and sometimes false, therefore the truth value of proposition ¬p ∨(p → q) can not be determined.

Answer: (d) ((x ∨ y)↔(~ x → ~ y))
Explanation:
(d) ((x ∨y) ↔ (~x →~y))
= (x ∨ y) ↔ (~(~x ) ∨~y)
= (x ∨ y) ↔ (~x ∨~y)
= ((x ∨ y) ∧ (~x ∨~y)) ∨(~(x ∨y) ∧~(x ∨~y))
= ((x ∨(y ∧ ~y)) ∨(( ~x ∧ ~y) ∧ (~x ∧ y))
= (x ∨ F) ∨ ((~x ∧ ~y) ∧(~x ∧ y))
= x ∨ (~x ∧(y ∧~y)) = x ∨(~x ∧F)
= x ∨ F = x

Answer: (a) True
Explanation:
. a ↔ (b ∨¬b)
a ↔ True
So a is true, i.e. a = 1
. b ↔ c holds. So b = c
Now the given expression is
(a ∧ b) → ((a ∧ c) ∨d) ≡(a . b) → ((a . c) + d)
putting a=1 in above expression We get
1 . b →((1 . c) +d)
≡ b → c + d
≡ b’ + c + d
Now putting b=c in above expression We get
≡c’ + c + d ≡1 + d ≡1
So the expression is always true.

Answer: (a) I stay if you go
Explanation:
Let p: I stay
q: you go
I stay only if you go
p → q
The converse of p → q is q → p
Now convert the answers one-by-one into boolean form. Only option (a) i.e. “I stay if you go” converts to q → p.

Answer: (a) F₁ is satisfiable, F₂ is valid
Explanation:
F₁: P → ~P ≡ p → p’ ≡ p’ + p’ ≡p’
So F₁ is contingency. Hence, F₁ is satisfiable but not valid.
F₂: (P → ~P) ∨ (~P → P)
≡ (p → p’) + (p’ → p)
≡ (p’+p’) + (p + p)
≡ p’ + p ≡ 1
So F₂ is tautology and therefore valid.

Answer: (a) (X ∧¬ Z) → Y
Explanation:
If X then Y unless Z is represented by
X →Y unless Z ≡ (X → Y) + Z
≡ X’ + Y + Z
Now convert the answers one-by-one into boolean form only choice (a) converts to X’+ Y+ Z as can be seen below:
(X∧~Z) →Y ≡ XZ’ → Y
≡ (XZ’)’ + y
= X’+ Y+Z

Answer: (d) (∀x) [α ⇒ β ] ⇒ ((∀x) [α] ⇒ (∀x) [β])
Explanation:
(∀x) [α ⇒ β] ⇒ ((∀x) [α] ⇒ ∀(x) [[β]) is a logical equivalence and therefore, a valid first order formula.

Answer: (d) Both I₁ and I₂ satisfy α
Explanation:
Q_xy ≡ “y divides y” is always true
∴Q_xy ⇔ ¬ Q_xy is the same as Q_xy ⇔False
Now α becomes
(∀x)[P(x)⇔(∀y)(Q_xy⇔false)]
⇒ (∀x) [¬ P(x)]
Now consider I₁: P(x) = “x is a prime number”. α becomes
(∀x x is a prime number if and only if ∀y (y does not divide x)) ⇒ (∀x) x is not prime. which means that x is a prime number if and only if no number divides x implies that no number is prime. Since x always divides x, the above sentence is true.

Now consider I₂: P(x) = “x is a composite number”. Now α becomes

(∀x x is a composite number if and only if ∀y (y does not divide x)) ⇒ (∀x) x is not composite. This means that x is a composite number if and only if no number divides x implies that no number is composite.
Since x always divides x, the above sentence is true.
∴ Both I₁ and I₂ satisfy α.

Answer: (b) (P ∨ Q) ⇒ (P ∨ R) ∧ (Q ∨¬ R) is logically valid
Explanation:
Derive clause P ∨ Q from clauses P ∨ R, Q ∨¬R means that (P ∨ R) ∧ (Q ∨ ¬R) ⇒ P ∨ Q
.’. (a) is true
Since x ⇒ y does not imply that y ⇒ x
.’. P ∨ Q ⇒ (P ∨ R) ∧ (Q ∨¬R)
.’. may or may not be true.
Hence (b) is false.

Answer: (d) (∃x) (boy(x) ∧ (∀y) (girl(y) → taller (x, y)))
Explanation:
The statement is “some boys in the class are taller than all the girls”. so the notation for the given statement is (∃x) (boy(x) ∧(∀y) (girl(y) → taller (x,y)))

Answer: (c) ¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)]
Explanation:
Choice (c) is
¬(∀x)(∃y)[(a(x,y) ∧ b(x,y)) → c(x,y)]
= ¬(∀x)(∃y)[a ∧ b → c]
= ¬(∀x)(∃y)[(ab)’ + c]
= ∃x ∀y[(ab)’ + c]’
= ∃x ∀y [abc’] = ∃x ∀y [a ∧ b ∧ ¬C] which is same as the given expression. (∃x)(∀y)[(a(x,y) ∧ b(x,y)) ∧ ¬c(x,y)]

Answer: (c) P and S only
Explanation:
p: [(¬p ∨q) ∧(r → s) ∧(p ∨r)] →q
≡p(p’ +r)(q + r’) →q
≡pr(q +r’) →q
≡prq →q
≡(prq)’ + q
≡p’ + r’ + q’ + q
≡p’ + r’ + 1
≡1
Therefore S is valid.
Q and R can be similarly simplified in boolean algebra to show that is both not equivalent to 1.

Answer: (a) Satisfiable but not valid
Explanation:
(p → (Q ∨R)) → ((P ∧Q) → R)
≡(P → Q + R) → (PQ → R)
≡[P’ + Q + R] → [(PQ)’ + R]
≡[P’ + Q + R] → [P’ + Q’ + R]
≡(P’ + Q + R)’ + P’ + Q’ + R
≡P Q’ R’ + P’ + Q’ + R
≡Q’ + Q’ P R’ + P’ + R
≡Q’ + P’ + R (by absorption law)
which is a contingency (i.e. satisfiable but not valid).

Answer: (b) X → Y
Explanation:
X: (P ∨ Q) → R
Y: (P → R) ∨(Q → R)
X: P + Q → R ≡(P + Q)’ + R ≡P’ Q’ + R
Y: (P’ + R) + (Q’ +R) ≡P’ + Q’ + R
Clearly X ≠ Y
Consider X → Y
≡(P’Q’ +R) →(P’ + Q’ + R)
≡(P’Q’+R)’ + P’ + Q’ + R
≡(P’Q’)’ . R’ + P’ + Q’ + R
≡(P + Q) . R’ + P’ + Q’ + R
≡ PR’ + QR’ + P’ + Q’ + R
≡ (PR’ + R) + (QR’ + Q’) + P’
≡(P + R) (R’ + R) + (Q + Q’) × (R’ +Q’) + P’
≡(P + R) + (R’ + Q’) + P’
≡P + P’ + R + R’ + Q’
≡1 + 1 + Q’
≡ 1
∴X → Y is a tautology.

Answer: (b)∀(x) [teacher (x) → ∃ (y) [student (y) ∧ likes (y, x)]]
Explanation:
Every teacher is liked by some student: then the logical expression is ∀(x) [teacher(x) → ∃(y) [student (y) ∧ likes (y, x)]] Where likes (y, x) means y likes x, such that y represent the student and x represents the teacher.

Answer: (b) (∀x(P(x) ⇒ Q(x))) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
Explanation
Consider choice (b)
(∀x(P(x) ⇒ Q(x))) ⇒ ((∀xP(x)) ⇒ (∀xQ(x))) Let the LHS of this implication be true This means that
P₁ → Q₁
p₂ → Q₂

.
.
.
P_n → Q_n
Now we need to check if the RHS is also true. The RHS is ((∀xP(x)) ⇒ (∀xQ(x)))
To check this let us take the LHS of this as true i.e. take∀xP(x) to be true. This means that (P₁ P₂,…P_n ) is taken to be true. Now P₁ along with P₁ → Q₁ will imply that is true. Similarly
P₂ along with P₂ → Q₂, will imply that Q₂ is true. And so on…
Therefore (Q₁, Q₂,……Q_n) all true.
i.e. ∀x Q(x) is true. Therefore statement (b) is a valid predicate statement.

Answer: (b) Satisfiable and so is its negation
Explanation:
Since a relation may or may not be symmetric, the given predicate is satisfiable but not valid. So (a) is clearly false.
Whenever a predicate is satisfiable its negation also is satisfiable. So option (b) is the correct answer.

Answer: (d) ∀x [(tiger (x) ∨ lion (x)) → {(hungry (x) ∨ threatened (x)) → attacks (x)}]
Explanation:
The given statement should be read as “If an animal is a tiger or a lion, then (if the animal is hungry or threatened, then it
will attack). Therefore the correct translation is ∀x [(tiger (x) ∨ lion (x)) → {(hungry (x) ∨ threatened (x)) → attacks (x)}] which is choice (d).

Answer: (d) Both P₁ and P₂ are not tautologies
Explanation:
P₁: ((A ∧ B) → c) ≡ ((A → c) ∧ (B → c))
LHS :
(A ∧ B) → C
≡ AB → C
≡ (A B)’ + C
≡ A’ + B’ + C
RHS:
(A → C) ∧ (B → C)
≡ (A’+ C) (B’ + C)
≡ A’B’ + C
Clearly, LHS ≠ RHS
P₁ is not a tautology
P₂: ((A ∨ B → C)) ≡ ((A → C) ∨(B → C))
LHS ≡ (A + B → C)
≡ (A + B)’+C
≡ A’B’ + C
RHS = (A → C) ∨ (B → C)
≡ (A’+ C) + (B’ + C)
≡ A’+ B’ + C
Clearly, LHS ≠ RHS ⇒ P₂ is also not a tautology. Therefore, both P₁ and P₂ are not tautologies. The correct choice is (d).

Answer: (d) ~ (~ A ⊙ B)
Explanation:
By using min terms we can define
A⊙B = AB + AB’ + A’B’
= A + A’B’
= (A + A’) . (A + B’) = A + B’
(a) ~ A⊙B = A’⊙ B = A’ + B’
(b) ~ (A ⊙ ~B) = (A ⊙ B’)’ =(A + (B’)’)’
= (A + B)’ = A’B’
(c) ~ (~A ⊙ ~B) = (A’ ⊙ B’)’ = (A’ + (B’)’)’
= (A’ + B)’ = AB’
(d) ~ (~A ⊙ B) = (A’ ⊙ B)’ = (A’ + B’)’
= A . B = A ∧ B
∴ Only, choice (d) = A ∧ B
Note: This problem can also be done by constructing a truth table for each choice and comparing it with the truth table for A ∧ B.

Answer: (d) ∀x (Graph(x) ⇒ ¬ Connected (x))
Answer:
Explanation:
The statement “Not every graph is connected” is the same as “There exists some graph which is not connected” which is the same as
∃x {graph (x) ∧ ¬ connected (x)}
Which is choice (b)
By boolean algebra, we can see that options (a) and (c) are the same as (b). Only option (d) is not the same as (b).
In fact option (d) means that “all graphs are not connected”.
Alternate solution:
We can translate the given statement “NOT (every graph is connected)” as ¬(∀x graph (x) → connected (x))
≡∃x¬(graph (x) →connected (x))
≡ ∃x¬(¬graph (x) ∨connected (x))
≡ ∃x (graph (x) ∧ ¬ connected (x))
By boolean algebra, we can see that options (a) and (c) are the same as (b). Only option (d) is not the same as (b).
In fact option (d) means that “all graphs are not connected”.

Answer: (a) For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
Explanation:
In conjunction normal form, for any particular assignment of truth values, all except one clause, will always evaluate to true. So, the proportion of clauses which evaluate to true to the total

number of clauses is equal to \(\frac{2^{n}-1}{2^{n}}\)
Now putting n = 1, 2, . . . . ., We get \(\frac{1}{2}\) , \(\frac{3}{4}\) , \(\frac{7}{8}\) ….
All of these proportions are ≥ \(\frac{1}{2}\) and so choice (a) at least half of the clauses evaluate to true, is the correct answer.

Answer: (a) ∀x(P(x) ⇒ Q(x)) ⇒ ((∀xP(x)) ⇒ (∀xQ(x)))
Explanation:
Option (a) is a standard one-way distributive property of predicates.

Answer: (a) ∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent (x, y)))
Explanation:
“For x which is a fsa, there exists a y which is a pda and which is equivalent to x.” ∀x (fsa(x) ⇒ ∃y (pda(y) ∧ equivalent (x, y))) is the logical representation.

Answer: (c) [(∃x, α(x)) → β] → [∀x,α(x) → β]
Explanation:
Option (c) is [(∃x, α(x)) → β] → [∀x,α(x) → β] Let us check the validity of this predicate. Let the LHS of this predicate be true.
This means that some α → β.
Let a₅ → β
Now we will check if the RHS is true. The RHS is [∀x,α(x) → β] to check this implication let us take ∀x,α(x)to be true.
This means that all the a are true. It means that a5 is also true.
But α₅ → β. Therefore β is true.
So the RHS [∀x,α(x) → β] is true.
Whenever the LHS [(∃x, α(x)) → β] is true. So option (c) is valid.

Answer: (d) [∀x,α ∧ (∃y, β ∧ (∃U, ∀U, ¬Y))]
Explanation:
The given predicate is
[∀x, α → (∃y,β → (∀u, ∃u, y))]
The negation is of this predicate is
¬[∀x, α → (∃y,β → ∀u, ∃u, y)]
¬[∀x, α →(∀y, ¬β ∨∀u, ∃u, y)]
¬[∃x, ¬α ∨(∀y, ¬β ∨∀u, ∃u, y)]
[∀x, α ∧ (∃y, β ∧(∃y, β ∧ (∃u, ∀u, ¬y))]
which is an option (d).

Answer: (b) Only 1, 2 and 3
Explanation:
1. P ∨ ~Q ≡ P + Q’
2. ~(~P ∧ Q) ≡ (P’Q)’ ≡P+Q’
3. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)
≡ PQ + PQ’ + P’Q’
≡ P(Q + Q’) + P’Q’
≡ P + P’Q’
≡ (P + P’) (P + Q’)
≡ P + Q’
4. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)
≡ PQ + PQ’ + P’Q
≡ P(Q + Q’) + P’Q
≡ P + P’Q
≡ (P + P’) (P + Q) = P + Q
Clearly (i), (ii) and (iii) are equivalent. Correct choice is (b).

Answer: (d) ∀x ((G(x) ∨ S(x)) → P(x))
Explanation:
The correct translation of “Gold and silver ornaments are precious” is choice (d)
∀x((G(x) ∨ S(x)) → P(x))
which is read as “if an ornament is a gold or silver, then it is precious”. Now since a given ornament cannot be both gold and silver at the same time.
Choice (b) ∀x ((G(x) ∧ S(X)) → P(x)) is incorrect.

Answer: (b) P □ ¬ Q
Explanation:
The given table can be converted into a boolean function by adding minterms corresponding to true rows.

Since there is only one false in the above truth table, we can represent the function P □ Q more efficiently, in conjunctive normal form. Translates P □ Q = P + Q’ (the max-term corresponding to the third row, where the function is false).
Now, we can easily translate the choices into boolean algebra as follows:
Choice (a) ¬Q □ ¬P ≡ Q’ □ P’ ≡ Q’ + P
Choice (b) P □ ¬Q ≡ P □ Q’ ≡ P + Q
Choice (c) ¬P □ Q ≡ P’ □ Q ≡ P’ + Q’
Choice (d) ¬P □ ¬Q ≡ P’ □ Q’ ≡ P’ + Q
As we can clearly see only choice (b) P □ ¬ Q is equivalent to P + Q.

Answer: (b) I and IV
Explanation:
I ¬∀xP(x) ≡ ∃x¬P(x)
and IV ∃x ¬P(x)
Clearly, choices I and IV are equivalent.
II ¬∃xP(x) ≡ ∀x ¬P(x)
and III ¬∃x[¬P(x)] ≡ ∀xP(x)
Clearly, II and III are not equivalent to each other or to I and IV.

Answer: (b) No one can fool everyone all the time
Explanation:
∀x ∃y ∃t ¬ F(x, y, t)
≡ ¬{∃x ∀y ∀t F(x, y, t)}
≡ it is not true that (someone can fool all people at all times)
≡ no one can fool everyone all the time

Answer: (a) P(x) being true means that x is a prime number
Explanation:
If P(x) is true, then
x ≠ 1 and also
x is broken into two factors, only if, one of the factors is x itself and the other factor is 1, which is exactly the definition of a prime number.
So P(x) is true means x is a prime number.

Answer: (b) I₁ is correct but I₂ is not a correct inference
Explanation:
Let p: It rains
q: cricket match will not be played.
I₁: p ⇒ q
∴ \(\underline{\sim q}{\sim p}\)
Clearly I₁ is correct since it is in the form of modus Tollens (rule of contrapositive)

I₂: p ⇒ q
∴ \(\underline{\sim q}{\sim p}\)
which corresponds [p ⇒ q ∧~p] ⇒ ~ q
≡ [(p’ + q) p’] ⇒ q’
≡ [p’ + qp’] ⇒ q’
≡p’ ⇒ q’
≡(p’)’ + q’ ≡p + q’
which is not a tautology. So I₂ is incorrect inference.

Answer: (c) ∃x (real (x) ∧ rational (x))
Explanation:
Some real numbers are rational ≡∃x [real (x) ∧rational (x)]

Answer: (d) ¬∃x (F(x) ∧ P(x))
Explanation:
None of my friends are perfect i.e., all of my friends are not perfect
∀x((F(x) → ¬ P(x))
∀x(¬ F(x) ∨¬ P(x))
¬ ∃x (F(x) ∧ P(x))
Alternatively
∃x (F(x) ∧ P(x)) gives
there exist some of my friends who are perfect, ¬∃x (F(x) ∧ P(x))
there does not exist any friend who is perfect i.e., none of my friends are perfect. So (d) is the correct option.

Answer: (a) ∀x(∃z(¬β) → ∀y(α))
Explanation:
Let, ∀y(α) = p, ∀z(β) = Q
then, ∃y(¬α) = ¬p and ∃z (¬β) = ¬Q
Given, ¬∃x(∀y(α) ∧∀z(β))
= ¬∃x(P ∧ Q) = ¬∀x (¬P ∨¬Q)
= ∀x (P →¬Q)
(a) ∀x(∃z(¬β) → ∀y(α)) = ∀x (¬Q → P)
(b) ∀x(∀z(β) → ∃y(¬α)) = ∀x (Q → ¬ P)
= ∀x (P →¬Q)
(c) ∀x (∀x(α) → ∃z (¬β)) = ∀x (P → ¬ Q)
(d) ∀x (∃y(¬α) ∨ ∃z (¬β)) = ∀x (¬ P ∨ ¬ Q)
= ∀x (P → ¬ Q)
∴ Only (a) is not logocally equivalent to ∀x(P → ¬ Q).

Answer: (d) ∃x: glitters(x) ∧¬gold(x)
Explanation:
(a) ∀x glitters (x) ⇒¬gold (x) All glitters are not gold
(b) ∀x gold(x) ⇒ glitters(x) All golds are glitters
(c) ∃x gold(x) ∧ ¬ glitters(x) There exist gold which is not glitter i.e. not all golds are glitters.
(d) ∃x glitters(x) ∧ ¬ gold(x) Not all that glitters is gold i.e., there exist some which glitters and which is not gold.

Answer: (b) (~ (p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~ r)
Explanation:
Option (b) is (~(p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~r)
≡((p ⊕ q)r) + pqr’ ≡(pq’ + p’q)r + pqr’
≡pq’r + p’qr + pqr’ ≡pqr’ + pq’r + pq’r
This is exactly the mm-term form of a logical formula which is true when exactly two variables are true (only p, q true or only p, r true or the only q, r true).

Answer: (b) (a ↔ c) → (~b → (a ∧ c))
Explanation:
(a ↔ c) → (~ b → (a ∧c))
≡ (a ↔ c )’ + (b’ → ac)
≡(a ⊕ c)’ + (b’ → ac)
≡ac’ + a’c + b + ac
≡a(c’ + c) + a’c + b
≡a + a’c + b ≡a + c + b
which is not a tautology.

Answer: (d) L, M, and N are TRUE.
Explanation:
g: mobile is good
C: mobile is cheap
P: Good mobile phones are not cheap
g → c’ ≅ (g’ + c’)
Q: Cheap mobile phones are not good
c → g’ ≅ (c’ + g’)
:. Both P and Q are equivalent.
L: P → Q
M: Q → P
N: P ≡ Q
Since both P and Q are equivalent, all three of L. M, N are true. So the correct option is (d).

Answer: (d) ∃d (Rainy (d)∧ ~ Cold (d))
Explanation:
Not (all rainy days are cold):
~ (∀d (Rainy (d) → Cold (d)))
≡~ (∀d (~ Rainy (d) ∨ Cold (d)))
≡ ∃d (Rainy (d)∧ ~ Cold (d))
Alternate Method:
Not all rainy days are cold is same as some rainy days are not cold which is the same as ∃d (Rainy (d)∧ ~ Cold (d))

Answer: (c) (¬p ∧ q) ∨ (p ∧ ¬q)
Explanation:
Here, option (a) and (b) can be reduced to (p → q) ∧ (q → p) and hence = p ↔ q
Option (d) is p’q’ + pq ≡ p ↔ q.
Option (c) is p’q + pq’ = p ⊕ q which is not equivalent to p ↔ q.

Answer: (a) Both commutative and associative
Explanation:
The given truth table corresponds to p’q + pq’ = P ⊕ q. ⊕ is known to be both commutative and associative.

Answer: (c) If a person is kind, he is not known to be corrupt
Explanation:
C: Person is corrupt
K: Person is kind.
E : Person is elected
S₁ : C → \(\bar{E}\)
S₂: K → E
S₂ ↔ \(\bar{E}\) → \(\bar{K}\)
So from S₁ and S₂:(C → \(\bar{E}\)) ∧ (\(\bar{E}\) → \(\bar{K}\)) ≅ C → \(\bar{K}\) We can conclude C → \(\bar{K}\) which is same as K → \(\bar{C}\), which is same as option (c).

Answer: (c) [∀x ∃y (P(x, y) → R(x, y))] ↔ [∀x ∃y (¬P(x, y) ∨ R(x, y))]
Explanation:
Since P → R ≡¬P ∨R, and both the sides are the same (∀x∃y) Option (e) is clearly a tautology.

Answer: (a) The result is head
Explanation:
Type 1 always tells truth.
Type 2 always tells lies.
The statement is “toss is head if and only if I am telling the truth”.
There are two cases possible.
Case-1: Let the person be type 1.
Case-2: Let the person be type 2.
In each case, we shall prove that result is head.
Case-1: Let the person be type 1. Type 1 always tells truth.
So the statement “toss is head if and only if I am telling the truth” is true.
So toss head ⇔ telling truth. Since type 1 is telling truth so toss head is also true. So in case, 1 the result is that the toss is head.
Case-2: Let the person be type 2. Type 2 always tells lies.
So the statement “toss is head if and only if I am telling the truth” is false.
So toss head ⇔ telling truth is false. So toss head ⊕ telling truth. So toss head and telling truth to have opposite truth values. Now, since type 2 telling truth is false, so toss head has to have the opposite truth value which is true.
So toss head is true. So in case 2 also, the result is head.
So in both cases, we have proved that the result is head.
So option (a) is correct.

Explanation: We wish to make
¬ ((p ⇒ q) ∧ (¬r ∨ ¬s)) = 1
⇒ (p ⇒ q) ∧ (¬r ∨ ¬s) = 0
⇒ (p ⇒ q) = 0
or ¬r ∨ ¬s = 0

Now (1) is satisfies only when p 1 and q = 0.
Equation (2) ¬r ∨ ¬s = 0, iff r ∧ s = 1
i.e. r 1 and s= 1
i.e. x is a perfect square and x is a prime number. Which is not possible so condition (2) cannot be satisfied by any x. So condition (1) must be satisfies which is p = 1 and q = 0 i.e. x e {8, 9, 10, 11, 12,) and x is not a composite. Now the only value of x which satisfies this is x = 11. So correct answer is x = 11.

Solution:
p∧(p ⇒ q) = p(p’ + q) =pq
Take (i) false
pq ⇒ false ≡ pq ⇒ 0
≡ (pq)’ + 0
≡ p’ + q’ + 0
≡ not valid

Take (ii)
pq ⇒ q = (pq)’ + q
≡ (pq)’ + q
≡ p’ + 1 = 1
≡ valid

Take (iii)
pq ⇒ true ≡ pq ⇒ 1
≡ (pq)’ + 1 ≡ 1
≡ valid

Take (iv)
pq ⇒ p + q ≡ (pq)’ + p + q
≡ P’ + q’ + P + q
≡ 1 + 1
≡ 1
≡ valid

Take (v)
pq ⇒ q’ + p ≡ (pq)’ + q’ + p
≡ p’ + q’ + q’ + p
≡ 1
≡ valid

So the number of expressions that are logically implied by p ∧ (p ⇒ q) is 4.

Answer: (d) ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀xq(x))

Explanation:
∀x is only one way distribution over “∨” so let us check (d)
(d) ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀xq(x))
Let LHS be true, so we have,
P₁ ∨ q₁ (true)
p₂ ∨ q₂ (true)
p₃ ∨ q₃ (true)
.
.
.

Now take p₁ is true, q₁ is false and p₂ is false, q₂ is true.
Now LHS is true, but RHS, ∀x p(x) is false (since p₂ is false) and ∀x q(x) is also false (since q₁ is false)
So, LHS ≠ RHS.

Answer: (b) I and IV only
Explanation:
I. ∀x ∃y R(x,y) →∃y (∃x R(x,y)) is true, since ∃y (∃x R(x,y))
II. ∀x ∃y R(x,y) →∃y (∀x R(x,y)) is false Since ∃y when it is outside is stronger than when it is inside.
III. ∀x ∃y R(x,y) → ∀y ∃x R(x,y) is false Since R(x, y) may not be symmetric in x and y.
IV. ∀x ∃y R(x,y) →¬ (∃x ∀y ¬R(x,y)) is true since ¬ (∃x ∀y ¬R(x,y)) ≡∀x ∃y R (x,y)
So, IV will reduce to ∀x ∃y R(x,y) → ∀x ∃y R(x,y) which is trivially true.
So the correct answer is I and IV only which is an option (b).

Answer: (d) II and III only
Explanation:
Statement p’ ⇒ q’ ≡p + q’
I. p → q ≡p’ + q
II. q → p ≡ q’ + p
III. (¬q ∨ p) ≡ q’ + p.
IV. (¬p ∨ q) ≡p’ + q
So, clearly, the given statement is the same as II and III only.

Question 57.
Let p, q and r be propositions 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

Question 58.
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))

Question 59.
Consider the first order predicate formula φ:∀x[∀z z|x ⇒∃w (w >x) ∧(∀z z | w ⇒ (( w = z) ∨ (z = 1)))]
Here ‘a | b’ denotes that ‘a divides b’, where a and b are integers. Consider the following sets:
S₁:{1, 2, 3, …, 100}
S₂: Set of all positive integers
S₃: Set of all integers
Which of the above sets satisfy φ?
(a) S₁ and S₃
(b) S₂ and S₃
(c) S₁ S₂ and S₃
(d) S₁ and S₂

Question 60.
Which one of the following predicate formulae is NOT logically valid?
Note that W is a predicate formula without any free occurrence of x.
(a) ∃x(p(x) ∧ W) ≡ ∃x p (x) ∧ W
(b) ∀x(p(x) → W) ≡ ∀xp(x) → W
(c) ∃x(p(x) → W) ≡ ∀xp(x) → W
(d) ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W

Question 61.
Let p and q be two propositions. Consider the following two formulae in propositional logic.
S₁: (¬ p ∧ (p ∨ q)) → p
S₂: q → ( ¬ p ∧ (p ∨ q))
Which one of the following choices is correct?
(a) Neither S₁ nor S₂ is a tautology.
(b) Both S₁ and S₂ are tautologies.
(c) S₁ is a tautology but S₂ is not a tautology.
(d) S₁ is not a tautology S₂ is a tautology.

Question 62.
Choose the correct choice(s) regarding the following propositional logic assertion S:
S : ((p ∧ Q) →R) → ( (P ∧Q) →(Q → R))
(a) S is a tautology.
(b) S is neither a tautology nor a contradiction.
(c) The antecedent of S is logically equivalent to the consequent of S.
(d) S is a contradiction.