Discrete Mathematics | Propositional Logic | Test 2 | Question: 1

Question

Let $\Phi$ be a well-formed formula having atleast one occurrence of atomic variable $x.$ Consider $\Psi$ be any formula. Now, $_x\Phi_{\Psi}$ is the formula obtained by replacing each occurrence of $x$ by $\Psi$ in $\Phi$ and the following statements can be proved:    
$\textit{1.}$ If $\Phi$ is a contradiction, then $_x\Phi_{\Psi}$ is also a contradiction
$\textit{2.}$ If $\Phi$ is a tautology, then $_x\Phi_{\Psi}$ is also a tautology   
Based on the above statements, consider the following two statements:   
     
i. $((x \rightarrow y) \wedge (y \leftrightarrow z)) \wedge \neg ((x \rightarrow y) \wedge (y \leftrightarrow z))$ is a tautology      
ii. $((x \rightarrow y) \wedge (y \leftrightarrow z)) \vee \neg ((x \rightarrow y) \wedge (y \leftrightarrow z))$ is a contradiction      
(x, y and z are atomic propositional variables in two-valued logic)      
Which one of the following statements is correct ?   
     

• A. Only (i) is correct     
• B. Only (ii) is correct     
• C. Both (i) and (ii) are correct     
• D. None of the above

Answer 1

​​​​​​Consider ((x → y) $\wedge$ (y $\leftrightarrow$ z)) as P.

Statement 1: P $\wedge$ P’ is a tautology. This is false because P $\wedge$ P’ is a contradiction.

Statement 2: P V P’ is a contradiction. This is false because P V P’ is a tautology.

Ans is D. (both statements are false)

Answer 2

1. $((x → y) \wedge (y ↔ z)) \wedge \neg ((x → y) \wedge (y ↔ z))$ is a tautology.

$By$ $case$ $Method:$

Let’s take, $y \equiv T$

$((x → y) \wedge (y ↔ z)) \wedge \neg ((x → y) \wedge (y ↔ z))$

$=> ((x → T) \wedge (T ↔ z)) \wedge \neg ((x → T) \wedge (T ↔ z))$

$=> z \wedge \neg z$

So, here we take $z$ anything $(T / F)$ it will be $F$.

Let’s take, $y \equiv F$

$((x → y) \wedge (y ↔ z)) \wedge \neg ((x → y) \wedge (y ↔ z))$

$=> ((x → F) \wedge (F ↔ z)) \wedge \neg ((x → F) \wedge (F ↔ z))$

$=> (\neg x \wedge \neg z) \wedge \neg (\neg x \wedge \neg z)$

So, here we take $(\neg x \wedge \neg z)$ anything $(T/F)$ it will be $F$.

$\therefore$ It’s not a $tautology$.It’s a $contradiction$

2. $((x → y) \wedge (y ↔ z)) \vee \neg ((x → y) \wedge (y ↔ z))$ is a contradiction.

$By$ $case$ $Method:$

Let’s take, $y \equiv T$

$((x → y) \wedge (y ↔ z)) \vee \neg ((x → y) \wedge (y ↔ z))$

$=> ((x → T) \wedge (T ↔ z)) \vee \neg ((x → T) \wedge (T ↔ z))$

$=> z \vee \neg z$

So, here we take $z$ anything $(T / F)$ it will be $T$.

Let’s take, $y \equiv F$

$((x → y) \wedge (y ↔ z)) \vee \neg ((x → y) \wedge (y ↔ z))$

$=> ((x → F) \wedge (F ↔ z)) \vee \neg ((x → F) \wedge (F ↔ z))$

$=> (\neg x \wedge \neg z) \vee \neg (\neg x \wedge \neg z)$

So, here we take $(\neg x \wedge \neg z)$ anything $(T/F)$ it will be $T$.

$\therefore$ It’s not a $contradiction$.It’s a $tautology$.

So, both statements are $incorrect$.

$Ans: D$