Redirected
edited by
1,891 views
4 votes
4 votes

The notation "$\Rightarrow$" denotes "implies" and "$\wedge$"  denotes "and" in the following formulae.

  • Let $X$ denote the formula: $(b \Rightarrow a ) \Rightarrow ( a \Rightarrow b)$
  • Let $Y$ denote the formula: $(a \Rightarrow b) \wedge b$


Which of the following is TRUE?

  1. $X$ is satisfiable and $Y$ is not satisfiable.
  2. $X$ is satisfiable and $Y$ is tautology.
  3. $X$ is not tautology and $Y$ is not satisfiable.
  4. $X$ is not tautology and $Y$ is satisfiable.
  5. $X$ is a tautology and $Y$ is satisfiable,
edited by

3 Answers

Best answer
6 votes
6 votes

Since we only have to deal with $2$ variables ($a$ and $b$), solving this with truth table is feasible.

Truth table for $X$ will be:

$$\begin{array}{|c|c|c|c|c|} \hline \textbf{a} & \textbf{b}& \textbf{b} \Rightarrow \textbf{a} &\textbf{a} \Rightarrow \textbf{b} & (\textbf{b} \Rightarrow \textbf{a}) \Rightarrow  (\textbf{a} \Rightarrow \textbf{b})  \\\hline \text{0} & \text{0}& \text{1} & \text{1} & \text{1}\\\hline \text{0} & \text{1}& \text{0} & \text{1} & \text{1}\\\hline \text{1} & \text{0}& \text{1} & \text{0} & \text{0}\\\hline \text{1} & \text{1}& \text{1} & \text{1} & \text{1} \\\hline \end{array}$$

So, clearly, $X$ is satisfiable but not a tautology.

Truth table for $Y$ will be:

$$\begin{array}{|c|c|c|c|} \hline \textbf{a} & \textbf{b}& \textbf{a} \Rightarrow \textbf{b} & (\textbf{a} \Rightarrow \textbf{b}) \wedge  \textbf{b} \\\hline \text{0} & \text{0}& \text{1} & \text{0}\\\hline \text{0} & \text{1}& \text{1} & \text{1}\\\hline \text{1} & \text{0}& \text{0} & \text{0}\\\hline \text{1} & \text{1}& \text{1} &\text{1}\\\hline \end{array}$$

So, $Y$ is also satisfiable but not a tautology.

This gives the OPTION (D) as the correct answer.

edited by
5 votes
5 votes
for X let a= true and b= false then value of statement X become false so it can't be Tautology

for Y let b= false and value of Y become false so Y can't be Tautology.

for a= true and b= true both X and Y become True hence both are satisfiable.

most correct option would be d
1 votes
1 votes
option D

X is not a tautology: Input a=1,b=0 gives 0

Y is not a tautology: Input a=0, b=1 gives 0

But Y is satisfiable for a=1 , b=1 gives 1
Answer:

Related questions

4 votes
4 votes
1 answer
1