Question

Suppose that a truth table in propositional variables is specified. Show that a compound proposition with this truth table can be formed by taking the disjunction of conjunctions of the variables or their negations, with one conjunction included for each combination of values for which the compound proposition is true. The resulting compound proposition is said to be in disjunctive normal form

Short answer

All compound propositions can be rewritten in disjunctive normal form, because conditional and biconditional statements can be rewritten in disjunctive normal form.

Step-by-step solution

Definitions

A compound proposition is in disjunctive normal form, if it only contains variables ( etc.) and the symbols and , where the compound proposition is a disjunction of conjunctions of variables or its negations.

INTERPRETATION SYMBOLS

Negation$\neg p:\mathrm{not}p$

Disjunction $\mathit{p}\mathbf{\vee }\mathit{q}\mathbf{:}\mathit{p}$or q

Conjunction $p\wedge q:p$and q

Conditional statement$p\to q$ : if p , then q

Biconditional statement $p\leftrightarrow q:p$if and only if q

Solution

The conditional statement and the biconditional statement are the only (basic) compound propositions that are not in disjunctive normal form, thus if we can rewrite the conditional statement and the biconditional statement in disjunctive normal form, then all compound propositions can be rewritten in disjunctive normal form.

The following logical equivalence holds for conditional statements and thus conditional statements can be rewritten in disjunctive normal form.

$p\to q\equiv \neg p\vee q$

The following logical equivalence holds for biconditional statements and thus biconditional statements can be rewritten in disjunctive normal form.

$p\leftrightarrow q\equiv (p\wedge q)\vee (\neg p\wedge \neg q)$