Kenneth Rosen Edition 7 Exercise 1.3 Question 44 (Page No. 36)

Question

Show that $\sim$ and $\wedge$ form a functionally complete collection of logical operators. [Hint: First use a De Morgan law to show that $p \vee q$ is logically equivalent to $(\sim(\sim p \wedge \sim q)).$]

Answer 1

Functionally complete: A collection of logical operators is called functionally complete if every compound proposition is logically equivalent to a compound proposition involving only these logical operator. 

Suppose, we prove that  (p$\vee$q) $\equiv$ $\sim$($\sim$p $\wedge\sim$q) . 

proof: $(p\vee q)$

=$\sim(\sim(p\, \vee q))$ by applying Double Negation Law

=$\sim(\sim p\, \wedge\sim q)$ by applying demorgan law, 

Hence, proved. 

Now, we can say that $\sim$ , $\wedge$ are functionally complete because resultant compound proposition $\sim(\sim p\, \wedge\sim q)$ contain only these logical operator. 

Comments

@ankitgupta.1729

---

This system or a set $\{\sim, \wedge \}$ is functionally complete because any compound proposition which involves  $\vee$ and/or $\{\sim, \wedge \}$ can be replaced by a compound proposition in which $p \vee q$ is replaced by a   $\sim (\sim p \wedge \sim q)$ as you have shown and in this way both propositions are logically equivalent and hence, every compound proposition is logically equivalent to a compound proposition involving set $\{\sim, \wedge \}.$

This proof depends on the proof in we have to show set $\{\sim, \wedge, \vee\}$ is functionally complete which can be shown by writing a compound proposition into its equivalent DNF because every compound proposition can be written into its equivalent DNF by using truth table.