## 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.

 A ∃x(p(x) → W) ≡ ∀x p(x) → W B ∀x(p(x) → W) ≡ ∀x p(x) → W C ∃x(p(x) ∧ W) ≡ ∃x p(x) ∧ W D ∀x(p(x) ∨ W) ≡ ∀x p(x) ∨ W
Engineering-Mathematics       Propositional-Logic       GATE 2020       Video-Explanation
Question 1 Explanation:
Basic Rules:
~p→q ≡ ~p∨q
Demorgan laws:
~(∀x(a(x)) ≡ ∃x~a(x)
~(∃x(a(x)) ≡ ∀x~a(x)
(A) ∃x(p(x)→w) ≡ ∀x p(x)→w
LHS: ∃x(p(x)→w) ≡ ∃x(~p(x)∨w)
≡ ∃x(~p(x))∨w
Demorgan’s law:
~(∀x(a(x)) = ∃x ~ a(x)
≡ ~(∀x P(x)) ∨ w
≡ (∀x) P(x) → w ≡ RHS
It’s valid.
(B) ∀x(P(x) → w) ≡ ∀x(~P(x) ∨ w)
≡ ∀x(~P(x)) ∨ w
≡ ~(∃x P(x)) ∨ w
≡ ∃x P(x) → w
This is not equal to RHS.
(C) ∃x(P(x) ∧ w) ≡ ∃x P(x) ∧ w
‘w’ is not a term which contains x.
So the quantifier does not have any impact on ‘w’.
Thus it can be written as
∃x(P(x)) ∧ w) ≡ ∃x P(x) ∧ w
(D) ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
‘w’ is not a term which contains ‘x’.
So the quantifier does not have an impact on ‘w’.
Thus ∀(x)(P(x) ∨ w) ≡ ∀x P(x) ∨ w
 Question 2

Which of the following is false? Read ∧ as AND, ∨ as OR, ~ as NOT, → as one way implication and ↔ as two way implication.

 A ((x → y) ∧ x) → y B ((x → y) ∧ (x ∧ y)) → x C (x → (x ∨ ψ)) D ((x ∨ y) ↔ (x → y)
Engineering-Mathematics       Propositional-Logic       GATE 1996
Question 2 Explanation:
When x = F and y = F
then option (D) will be False.
 Question 3

Which of the following propositions is a tautology?

 A (p ∨ q) → p B p ∨ (q → p) C p ∨ (p → q) D p → (p → q)
Engineering-Mathematics       Propositional-Logic       GATE 1997
Question 3 Explanation: Question 4

What is the converse of the following assertion?

`  I stay only if you go. `
 A I stay if you go B If I stay then you go C If you do not go then I do not stay D If I do not stay then you go
Engineering-Mathematics       Propositional-Logic       GATE 1998
Question 4 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.
 Question 5

(a) Show that the formula [(~p ∨ q) ⇒ (q ⇒ p)] is not a tautology.
(b) Let A be a tautology and B be any other formula. Prove that (A ∨ B) is a tautology.

 A Theory Explanation.
Engineering-Mathematics       Propositional-Logic       GATE 1999
 Question 6

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

 A True B False C Same as the truth-value of b D Same as the truth-value of d
Engineering-Mathematics       Propositional-Logic       GATE 2000
Question 6 Explanation:
a ↔ (b ∨-b) and b ↔ c
Given ⇒ (a∧b) → (a∧c) ∨d
⇒ (a∧b) → (a∧c) ∨d (b⇔c)
⇒ T∨d
⇒ T
 Question 7

“If X then Y unless Z” is represented by which of the following formulas in prepositional logic? (“¬“, is negation, “∧” is conjunction, and “→” is implication)

 A (X∧¬Z)→Y B (X∧Y)→¬Z C X→(Y∧¬Z) D (X→Y)∧¬Z
Engineering-Mathematics       Propositional-Logic       GATE 2002
Question 7 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.
 Question 8

Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)

 A ((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α⇒β] B (∀x)[α] ⇒ (∃x)[α ∧ β] C ((∀x)[α ∨ β] ⇒ (∃x)[α] ⇒ (∀x)[α] D (∀x)[α ⇒ β] ⇒ ((∀x)[α] ⇒ (∀x)[β])
Engineering-Mathematics       Propositional-Logic       GATE 2003
Question 8 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.
 Question 9

Consider the following formula a and its two interpretations I1 and I2

```α: (∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Qyy]] ⇒ (∀x)[¬Px]
I1: Domain: the set of natural numbers
Px ≡ 'x is a prime number'
Qxy ≡ 'y divides x'
I2: same as I1 except that Px = 'x is a composite number'.```

Which of the following statements is true?

 A I1 satisfies α, I2 does not B I2 satisfies α, I1 does not C Neither I2 nor I1 satisfies α D Both I1 and I2 satisfy α
Engineering-Mathematics       Propositional-Logic       GATE 2003
Question 9 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 α.
 Question 10

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?

 A ((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid B (P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R)) is logically valid C (P ∨ Q) is satisfiable if and only if (P∨R) ∧ (Q∨¬R) is satisfiable D (P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable
Engineering-Mathematics       Propositional-Logic       GATE 2003
Question 10 Explanation:
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R)) It is may be True (or) False depending on values. So this is not valid.
 Question 11

Identify the correct translation into logical notation of the following assertion.

`      "Some boys in the class are taller than all the girls"  `

Note: taller(x,y) is true if x is taller than y.

 A (∃x) (boy(x) → (∀y) (girl(y) ∧ taller(x,y))) B (∃x) (boy(x) ∧ (∀y) (girl(y) ∧ taller(x,y))) C (∃x) (boy(x) → (∀y) (girl(y) → taller(x,y))) D (∃x) (boy(x) ∧ (∀y) (girl(y) → taller(x,y)))
Engineering-Mathematics       Propositional-Logic       GATE 2004
Question 11 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.
 Question 12

The following propositional statement is (P → (Q v R)) → ((P v Q) → R)

 A satisfiable but not valid B valid C a contradiction D None of the above
Engineering-Mathematics       Propositional-Logic       GATE 2004
Question 12 Explanation:
(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 13

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?

 A X ≡ Y B X → Y C Y → X D ¬Y → X
Engineering-Mathematics       Propositional-Logic       GATE 2005
Question 13 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 (✔️)
 Question 14

What is the first order predicate calculus statement equivalent to the following?

`   Every teacher is liked by some student  `
 A ∀(x) [teacher(x) → ∃ (y) [student(y) → likes (y, x)]] B ∀(x) [teacher(x) → ∃ (y) [student(y) ∧ likes (y, x)]] C ∃(y) ∀(x) [teacher(x) → [student(y) ∧ likes (y, x)]] D ∀(x) [teacher(x) ∧ ∃ (y)[student(y) → likes (y, x)]]
Engineering-Mathematics       Propositional-Logic       GATE 2005
Question 14 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.
 Question 15

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.`
 A ∀x [(tiger(x) ∧ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}] B ∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) ∧ attacks(x)}] C ∀x [(tiger(x) ∨ lion(x)) → {(attacks(x) → (hungry (x)) ∨ threatened (x))}] D ∀x [(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Engineering-Mathematics       Propositional-Logic       GATE 2006
Question 15 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.
∀x[(tiger(x) ∨ lion(x)) → {(hungry(x) ∨ threatened(x)) → attacks(x)}]
Note: Don’t confuse with the statement Tiger and Lion.
 Question 16

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?

 A P1 is a tautology, but not P2 B P2 is a tautology, but not P1 C P1 and P2 are both tautologies D Both P1 and P2 are not tautologies
Engineering-Mathematics       Propositional-Logic       GATE 2006
Question 16 Explanation:
It’s better to draw truth table such that Both P1 and P2 are not Tautologies.
 Question 17

Obtain the principal (canonical) conjunctive normal form of the propositional formula

`  (p ∧ q) V (¬q ∧ r) `

Where ‘∧’ is logical and, ‘v’ is inclusive or and ¬ is negation.

 A Theory Explanation.
Engineering-Mathematics       Propositional-Logic       GATE 1995
 Question 18

(a) Let * be a Boolean operation defined as If C = A * B then evaluate and fill in the blanks:
(i) A * A = _______
(ii) C * A = _______
(b) Solve the following boolean equations for the values of A, B and C: A Theory Explanation.
Engineering-Mathematics       Propositional-Logic       GATE 1994
 Question 19

Show that proposition C is a logical consequence of the formula

`     A ∧ (A →(B ∨ C)) ∧ (B → ~A)  `

Using truth tables.

 A Theory Explanation.
Engineering-Mathematics       Propositional-Logic       GATE 1993
 Question 20
Choose the correct choice(s) regarding the following propositional logic assertion S: A S is a contradiction. B The anecdote of S is logically equivalent to the consequent of S. C S is a tautology. D S is neither a tautology nor a contradiction.
Engineering-Mathematics       Propositional-Logic       GATE 2021 CS-Set-2       Video-Explanation
Question 20 Explanation:
 Question 21
Let p and q be two propositions. Consider the following two formulae in propositional logic. Which one of the following choices is correct?
 A Both S1and S2 are tautologies. B Neither S1and S2 are tautology. C S1is not a tautology but S2is a tautology. D S1is a tautology but S2is not a tautology.
Engineering-Mathematics       Propositional-Logic       GATE 2021 CS-Set-1       Video-Explanation
Question 21 Explanation:

A tautology is a formula which is "always true" . That is, it is true for every assignment of truth values to its simple components.

Method 1:
S1: (~p ^ (p Vq)) →q
The implication is false only for T->F condition.
Let's consider q as false, then
(~p ^ (p Vq)) will be (~p ^ (p VF)) = (~p ^ (p)) =F.
It is always F->F which is true for implication. So there are no cases that return false, thus its always True i.e. its Tautology.

S2:

q->(~p (p Vq))

The false case for implication occurs at T->F case.
Let q=T then (~p (p Vq))  = (~p (p VT))= ~p. (It can be false for p=T).
So there is a case which yields T->F = F. Thus its not Valid or Not a Tautology.

Method 2: Question 22

Which one of these first-order logic formula is valid?

 A ∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x)) B ∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x)) C ∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x)) D ∀x∃y P(x, y) ⇒ ∃y∀x P(x, y)
Engineering-Mathematics       Propositional-Logic       GATE 2007-IT
Question 22 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 (️×)
 Question 23

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.

 A [β→(∃x,α(x))]→[∀x,β→α(x)] B [∃x,β→α(x)]→[β→(∀x,α(x))] C [(∃x,α(x))→β]→[∀x,α(x)→β] D [(∀x,α(x))→β]→[∀x,α(x)→β]
Engineering-Mathematics       Propositional-Logic       GATE 2008-IT
Question 23 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.
 Question 24

Which of the following is the negation of [∀x, α →(∃y, β →(∀ u, ∃v, y))]

 A [∃x, α → (∀y, β → (∃u, ∀v, y))] B [∃x, α → (∀y, β → (∃u, ∀ v, ¬y))] C [∀x, ¬α → (∃y, ¬β → (∀u, ∃v, ¬y))] D [∃x, α ʌ (∀y, β ʌ (∃u, ∀v, ¬y))]
Engineering-Mathematics       Propositional-Logic       GATE 2008-IT
Question 24 Explanation:
~[∀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 25

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

 A satisfiable and valid B satisfiable and so is its negation C unsatisfiable but its negation is valid D satisfiable but its negation is unsatisfiable
Engineering-Mathematics       Propositional-Logic       GATE 2006-IT
Question 25 Explanation:
The given relation is 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 26

Which of the following well-formed formulas are equivalent?

 A P → Q B ¬Q → ¬P C ¬P ∨ Q D ¬Q → P E A, B and C.
Engineering-Mathematics       Propositional-Logic       GATE 1989       Video-Explanation
Question 26 Explanation:
P → Q ⇔ ¬P ∨ Q
¬Q → ¬P ⇔ Q ∨ ¬P
¬P ∨ Q ⇔ ¬P ∨ Q
¬Q → P ⇔ Q ∨ P
A, B and C are equivalent.
 Question 27

Choose the correct alternatives (More than one may be correct). Indicate which of the following well-formed formulae are valid:

 A (P⇒Q) ∧ (Q⇒R) ⇒ (P⇒R) B (P⇒Q) ⇒ (¬P⇒¬Q) C (P∧(¬P∨¬Q)) ⇒ Q D (P⇒R) ∨ (Q⇒R) ⇒ ((P∨Q)⇒R)
Engineering-Mathematics       Propositional-Logic       GATE 1990       Video-Explanation
Question 27 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.
 Question 28

(a) Uses Modus ponens (A, A →|= B) or resolution to show that the following set is inconsistent:

``` (1) Q(x) → P(x)V ~ R(a)
(2) R(a) ~ Q(a)
(3) Q(a)
(4) ~ P(y) ```

Where x and y are universally quantified variables, a is a constant and P, Q, R are monadic predicates.

(b) Let S be the set of all integers and let n > 1 be a fixed integer. Define for a, b ∈ S, a R biff a-b is a multiple of n. Show that R is an equivalence relation and finds its equivalence classes for n = 5.

 A Theory Explanation.
Engineering-Mathematics       Propositional-Logic       GATE 1992       Video-Explanation
 Question 29

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”?

 A ¬∀x (Graph (x) ⇒ Connected (x)) B ¬∃x (Graph (x) ∧ ¬Connected (x)) C ¬∀x (¬Graph (x) ∨ Connected (x)) D ∀x (Graph (x) ⇒ ¬Connected (x))
Engineering-Mathematics       Propositional-Logic       GATE 2007
Question 29 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.
 Question 30

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

 A (∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y)) B ∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y)) C ∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y)) D ∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y))
Engineering-Mathematics       Propositional-Logic       GATE 2008
Question 30 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.
 Question 31

P and Q are two propositions. Which of the following logical expressions are equivalent?

I. P∨∼Q
II. ∼(∼P∧Q)
III. (P∧Q)∨(P∧∼Q)∨(∼P∧∼Q)
IV. (P∧Q)∨(P∧∼Q)∨(∼P∧Q)
 A Only I and II B Only I, II and III C Only I, II and IV D All of I, II, III and IV
Engineering-Mathematics       Propositional-Logic       GATE 2008
Question 31 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 (✔️)
 Question 32

Which one of the following well formed formulae is a tautology?

 A ∀x ∃y R(x,y) ↔ ∃y ∀x R(x,y) B (∀x [∃y R(x,y) → S(x,y)]) → ∀x∃y S(x,y) C [∀x ∃y (P(x,y) → R(x,y)] ↔ [∀x ∃y (¬ P(x,y)∨R(x,y)] D ∀x ∀y P(x,y) → ∀x ∀y P(y,x)
Engineering-Mathematics       Propositional-Logic       GATE 2015 [Set-2]       Video-Explanation
Question 32 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.
 Question 33
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 _________.
 A 4 B 5 C 6 D 7
Engineering-Mathematics       Propositional-Logic       GATE 2016 [Set-2]       Video-Explanation
Question 33 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))
 Question 34

Which one of the following well-formed formulae in predicate calculus is NOT valid?

 A (∀x p(x) ⇒ ∀x q(x)) ⇒ (∃x ¬p(x) ∨ ∀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       Propositional-Logic       GATE 2016 [Set-2]       Video-Explanation
Question 34 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.
 Question 35
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
 A I only B I and IV only C II only D II and III only
Engineering-Mathematics       Propositional-Logic       GATE 2017 [Set-1]       Video-Explanation
Question 35 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.
 Question 36

Consider two well-formed formulas in prepositional logic

`   F1: P ⇒ ¬P          F2: (P⇒¬P)∨(¬P⇒P)  `

Which of the following statements is correct?

 A F1 is satisfiable, F2 is valid B F1 unsatisfiable, F2 is satisfiable C F1 is unsatisfiable, F2 is valid D F1 and F2 are both satisfiable
Engineering-Mathematics       Propositional-Logic       GATE 2001
Question 36 Explanation: F1 is satisfiable; F2 is valid.
 Question 37

Consider the first order predicate formula φ:

∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃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:

S1.  {1, 2, 3, ..., 100}
S2.  Set of all positive integers
S3. Set of all integers

Which of the above sets satisfy φ?

 A S1 and S3 B S1, S2 and S3 C S2 and S3 D S1 and S2
Engineering-Mathematics       Propositional-Logic       GATE 2019       Video-Explanation
Question 37 Explanation:
The first order logic gives the meaning that if z is a prime number then there exists another prime number in the set which is larger than it.
One of the case:
If -7 is a number which is prime (either divided by -7 or 1 only). then there exists some number like -3 which is larger than -7 also satisfy the property (either divided by -3 or 1 only).
So, S3 is correct
It's true for all integers too.
 Question 38
Which one of the following is not equivalent to p←→q A A B B C C D D
Engineering-Mathematics       Propositional-Logic       GATE 2015 [Set-1]       Video-Explanation
There are 38 questions to complete.

Register Now