• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q43E

Expert-verified
Found in: Page 35

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Show that, ${\mathbf{\wedge }}{\mathbf{,}}{\mathbf{\vee }}$and$\mathbf{¬}$, ∨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.]

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

See the step by step solution

## Step1: Definitions

Let p be a compound proposition.

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

## Step 2: Solution

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

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

given the definition of functionally complete collection of operators.