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

Question

Show that $\sim$ and $\vee$ form a functionally complete collection of logical operators.

Answer 1

A functionally complete collection of logical operators is a set of logical operators that can be used to construct any logical statement. To show that "not" and "or" form a functionally complete collection of logical operators, we must demonstrate that any logical statement can be constructed using only these two operators.

One way to show that "not" and "or" form a functionally complete collection of logical operators is to use De Morgan's laws. These laws state that the negation of a logical disjunction (i.e. "or") is equivalent to the conjunction (i.e. "and") of the negations, and the negation of a logical conjunction is equivalent to the disjunction of the negations.

De Morgan's laws can be used to demonstrate that "not" and "or" form a functionally complete collection of logical operators as they allow to express any logical statement using only these two operators.

In summary, "not" and "or" form a functionally complete collection of logical operators because any logical statement can be constructed using only these two operators, using De Morgan's laws that allows to express any logical statement using only these two operators.

Answer 2

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$\wedge$q) $\equiv\,\sim$($\sim$p $\vee\sim$q) . 

proof: (p$\wedge$q)

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

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

Hence, proved. 

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

Comments

@ankitgupta.1729

---

similar to this