# Propositional Logic

 Question 1
The number of arrangements of six identical balls in three identical bins is ____.
 A 7 B 8 C 12 D 5
GATE CSE 2022   Discrete Mathematics
Question 1 Explanation:
 Question 2
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 Explanation:
 Question 3
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 Explanation:
 Question 4
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 Explanation:
 Question 5
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 Explanation:
 Question 6
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 Explanation:
 Question 7
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 Explanation:
 Question 8
Which one of the following Boolean expressions is NOT a tautology?
 A $((a \rightarrow b) \wedge(b \rightarrow c)) \rightarrow(a \rightarrow c)$ B $(a \leftrightarrow c) \rightarrow(\sim b \rightarrow(a \wedge c))$ C $(a \wedge b \wedge c) \rightarrow(c \vee a)$ D $a \rightarrow(b \rightarrow a)$
ISRO CSE 2017   Discrete Mathematics
Question 8 Explanation:
 Question 9
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 9 Explanation:
 Question 10
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 10 Explanation:
There are 10 questions to complete.

### 16 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 ” ∨”.

• Thank You Intekhab Ahmad,
We have updated the answer.

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,
We have updated the answer.

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

7. In question 23 please update option c .

• Thank You rajeev dubey,
We have updated the answer.

8. 9. 