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

Question

 The set of logical symbols of a propositional language is called the $\textit{logical signature}.$ A logical signature is called $\textit{functionally complete}$ if every Boolean function is representable by a formula in this signature. For example, $\{\neg, \vee,\wedge \}$ is functionally complete and similarly $\{\neg,\vee \}$ and $\{\neg,\wedge \}$ are functionally complete.      
        
Which of the following statement(s) is/are correct?     
       

• A. The signature $\{\rightarrow,0\}$ is functionally complete.     
          
• B. The signature $\{\rightarrow,\vee, \wedge \}$ is functionally complete.     
         
• C. The signature $\{\rightarrow\}$ is functionally complete.       
         
• D. The signature $\{\rightarrow\}$ is $\textit{not}$ functionally complete.

Answer 1

A hint in of form of {$\sim , \vee $} and {$\sim , \wedge$ } are functionally complete is given in the question.

Just see if you can generate either {$\sim , \vee $} or {$\sim , \wedge$} from the given set of logical symbols

Consider {$\rightarrow , 0$}

($p\rightarrow 0 )= \sim p$ ; negation is generated

$\left ( p\rightarrow 0 \right )\rightarrow q = p\vee q$ ; Disjunction is generated

{$\rightarrow , 0$} is functionally complete

$\left \{ \rightarrow , \wedge , \vee \right \}$ is not functionally complete as $\rightarrow$ needs $0$ to generate $\sim$

Option A, D are correct