Question

Show that$\neg$and$\wedge$form a functionally complete collection of logical operators.[Hint: First use De Morgan’s law to show thatis logically equivalent to$\neg (\neg \text{p}\wedge \neg \text{q})$.

Short answer

For showing,$\neg$and $\wedge$form a functionally complete collection of logical operators, it is provedby an example $\text{p}\vee \text{q}\equiv \neg (\neg \text{p}\wedge \neg \text{q})$ that a disjunction can be written with the help of negation and conjunction using De Morgan’s law.

Step-by-step solution

Definition of Truth Table

A De Morgan’s lawstates that if two inputs are AND'ed and negated, the result is the OR of the respective variables' complements.of these inputs and vice versa.

To show ¬ and  ∧form a functionally complete collection of logical operators.

Take two variables as inputs such as P and q.

The De Morgan’s law states that$\neg (\text{p}\vee \text{q})\equiv \neg \text{p}\wedge \neg \text{q}$

Take negation of each statement.

$\neg (\neg (\text{p}\vee \text{q}))\equiv \neg (\neg \text{p}\wedge \neg \text{q})$

Use double negation law

$\text{p}\vee \text{q}\equiv \neg (\neg \text{p}\wedge \neg \text{q})$

As a result of De Morgan's rule, the disjunction can be expressed using negation as well as conjunction.

Therfore, it has been shown that $\mathbf{\neg }$and $\wedge$form a functionally complete collection of logical operators.