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 1 Explanation:
 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 2 Explanation:
 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 3 Explanation:
 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 4 Explanation:
 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 5 Explanation:
 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 6 Explanation:
 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 7 Explanation:
 Question 8
Let p, q, and r be propositions and the expression (p$\rightarrow$q)$\rightarrow$r be a contradiction. Then, the expression (r$\rightarrow$p)$\rightarrow$q 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 8 Explanation:
 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 9 Explanation:
 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
Question 10 Explanation:
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 ” ∨”.

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

• Thank You MOUNIKA DASA,

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))

• Thank You MOUNIKA DASA,
We have updated the question.

4. question 18 options given has a disjunction sign.

• Thank You PRAFUL Rahul,
We have updated the question.

5. Question no. 34 none option is correct,

• Thank You dp,
We have updated the option.

6. Please update the b and c options of 37th question

• Thank You Mounika Dasa,
We have updated the option