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

Question

The $\textit{dual}$ $P^d$ of a formula $P$ involving the connectives $\{\wedge,\vee, \neg \}$ is obtained by interchanging $\vee$ with $\wedge$ and $\wedge$ with $\vee$. For example, the dual of $\neg (x \wedge y) \vee \neg z$ is $\neg (x \vee y) \wedge \neg z.$      
Also, $f$ and $g$ are equivalent i.e. $f \equiv g$ if and only if $f \leftrightarrow g$ is a tautology.     
    
      
Now, consider the following statements:    
           
i. Let $f(p_1,p_2,...,p_n)$ be a formula involving the distinct atomic variables $p_1,p_2,...,p_n$ and connectives $\wedge, \vee, \neg.$     
     
If $f(\neg p_1,\neg p_2,...,\neg p_n)$ is obtained by replacing each $p_i$ with $\neg p_i$ in $f$ for all $1 \leq i \leq n$ then $f( p_1,p_2,...,p_n) \equiv  f^d(\neg p_1,\neg p_2,...,\neg p_n)$        
       
        
ii. If $f$ and $g$ be formulas that use only the connectives $\wedge, \vee$ and $\neg.$ If $f \equiv g,$ then $f^d \equiv g^d$          
      
Which one of the following 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

1. is not correct

          f  $\not\equiv$  $f^{^{d}}$

                     for eg.      f = A V B

                                     $f^{^{d}}$ = A $\wedge$  B

       ii.  is correct

                 

                       for eg.      f = A’ V B’                                       g =  (A $\wedge$ B)’ 

                                       $f^{^{d}}$ = A’ $\wedge$ B’                                    $g^{^{d}}$ = (A V B)’               

 

 

 f $\equiv$ g           By Demorgan’s law

Therefore,  $f^{^{d}}$ $\equiv$ $g^{^{d}}$

 

Ans: B)

Comments

A formal proof is required for (ii), examples are not used to prove something.

---

Yes right, a counter example enough to disprove something. But a single example not enough to prove something, proof is required.