Propositional Logic

Question 1
Choose the correct choice(s) regarding the following proportional logic assertion S:

S: (( P \wedge Q) \rightarrow R) \rightarrow (( P \wedge Q) \rightarrow (Q \rightarrow R))
[MSQ]
A
S is neither a tautology nor a contradiction
B
S is a tautology
C
S is a contradiction
D
The antecedent of S is logically equivalent to the consequent of S
GATE CSE 2021 SET-2   Discrete Mathematics
Question 2
Consider the two statements.

S1: There exist random variables X and Y such that \left(\mathbb E[(X-\mathbb E(X))(Y-\mathbb E(Y))]\right)^2 > \textsf{Var}[X]\textsf{Var}[Y]
S2: For all random variables X and Y, \textsf{Cov}[X,Y]=\mathbb E \left[|X-\mathbb E[X]||Y-\mathbb E[Y]|\right ]

Which one of the following choices is correct?
A
Both S1 and S2 are true.
B
S1 is true, but S2 is false.
C
S1 is false, but S2 is true.
D
Both S1 and S2 are false.
GATE CSE 2021 SET-1   Discrete Mathematics
Question 3
Let p and q be two propositions. Consider the following two formulae in propositional logic.

S1: (\neg p\wedge(p\vee q))\rightarrow q
S2: q\rightarrow(\neg p\wedge(p\vee q))

Which one of the following choices is correct?
A
Both S1 and S2 are tautologies.
B
S1 is a tautology but S2 is not a tautology
C
S1 is not a tautology but S2 is a tautology
D
Niether S1 nor S2 is a tautology
GATE CSE 2021 SET-1   Discrete Mathematics
Question 4
Given that
B(a) means "a is a bear"
F(a) means "a is a fish" and
E(a,b) means "a eats b"
Then what is the best meaning of
\forall x[F(x) \rightarrow \forall y(E(y, x) \rightarrow b(y))]
A
Every fish is eaten by some bear
B
Bears eat only fish
C
Every bear eats fish
D
Only bears eat fish
ISRO CSE 2020   Discrete Mathematics
Question 5
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
\forall x(p(x)\vee W)\equiv \forall xp(x)\vee W
B
\exists x(p(x)\wedge W)\equiv \exists xp(x)\wedge W
C
\forall x(p(x)\rightarrow W)\equiv \forall xp(x)\rightarrow W
D
\exists x(p(x)\rightarrow W)\equiv \forall xp(x)\rightarrow W
GATE CSE 2020   Discrete Mathematics
Question 6
Consider the first-order logic sentence
\varphi \equiv \exists s\exists t\exists u\forall v\forall w\forall x\forall y\varphi (s,t,u,v,w,x,y)
where \varphi (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 \varphi has a model with a universe containing 7 elements. Which one of the following statements is necessarily true?
A
There exists at least one model of \varphi with universe of size less than or equal to 3.
B
There exists no model of \varphi with universe of size less than or equal to 3.
C
There exists no model of \varphi with universe of size greater than 7.
D
Every model of \varphi has a universe of size equal to 7.
GATE CSE 2018   Discrete Mathematics
Question 7
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
(\neg p\wedge r)\wedge (\neg r\rightarrow (p\wedge q))
B
(\neg p\wedge r)\wedge ((p\wedge q)\rightarrow \neg r)
C
(\neg p\wedge r)\vee ((p\wedge q)\rightarrow \neg r)
D
(\neg p\wedge r)\vee (r \rightarrow (p\wedge q))
GATE CSE 2017 SET-2   Discrete Mathematics
Question 8
Let p, q, and r be propositions and the expression (p\rightarrowq)\rightarrowr be a contradiction. Then, the expression (r\rightarrowp)\rightarrowq is
A
a tautology
B
a tautology
C
always TRUE when p is FALSE
D
always TRUE when q is TRUE
GATE CSE 2017 SET-1   Discrete Mathematics
Question 9
Consider the first-order logic sentence F:\forall z(\exists yR(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F?
I. \exists y(\exists xR(x,y))
II. \exists y(\forall xR(x,y))
III. \forall y(\exists xR(x,y))
IV. \neg \exists x(\forall y\neg R(x,y))
A
IV only
B
I and IV only
C
II only
D
II and III only
GATE CSE 2017 SET-1   Discrete Mathematics
Question 10
The statement (\neg p)\Rightarrow (\neg q) is logically equivalent to which of the statements below?
I. p\Rightarrow q
II. q \Rightarrow p
III. (\neg q)\vee p
IV. (\neg p)\vee q
A
I only
B
I and IV only
C
II only
D
II and III only
GATE CSE 2017 SET-1   Discrete Mathematics
There are 10 questions to complete.

15 thoughts on “Propositional Logic”

  1. Qno. 40. Correction in option 4
    The actual option is ∀x [(tiger(x) ∨ lion(x)) → (hungry(x) ∨ threatened(x)) → attacks(x)]
    At the place of “∧ , there will be ” ∨”.

    Reply
  2. In the question 23 please update the answer. It is not 0, instead it needs to be ∀x(∃y(¬α)→∃z(¬β))

    Reply
  3. In the question 29 please update the question. In the option iv it is not ¬∃x(¬P(x)), instead it needs to be ∃x(¬P(x))

    Reply

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.