Question

Show that$\neg$and$\wedge$form a functionally complete collection of logical operators.

Short answer

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

Step-by-step solution

Definition of De Morgan’s law

ADe 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 \(\neg \)and \( \wedge \)form a functionally complete collection of logical operators.

Take two variables as inputs 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.