Question

Show that, $\mathbf{\wedge }\mathbf{,}\mathbf{\vee }$and$\mathbf{\neg }$,∨form a functionally complete collection of logical operators. [Hint: Use the fact that every compound proposition is logically equivalent to one in disjunctive normal form, as shown in Exercise 42.]

Short answer

Let P be a compound proposition. Generate a proposition q in disjunctive normal form, which is equivalent to p.

Step-by-step solution

Definitions

Let p be a compound proposition.

We can generate its truth table, and according to the preceding exercise (42),

Solution

Generate a proposition q in disjunctive normal form, which is equivalent to p.

The disjunctive normal form involves, $\neg ,\vee$and $\wedge$only, which proves the statement,

given the definition of functionally complete collection of operators.