Equivalence of Formulas and Normal Forms

Prove that formula $\Psi$ follows from formula $\Phi$ if and only if $\Phi \wedge \Psi \equiv \Phi$, if and only if $\Phi \vee \Psi \equiv \Psi$.

Verify all the equivalences 1)–9) given in Section 4.1 by directly constructing truth tables for the functions represented by their left- and right-hand sides.

The nine equivalences (with $\Phi$, $\Psi$, $\Theta$ arbitrary formulas):

1. Associativity: $(\Phi \wedge \Psi ) \wedge \Theta \equiv \Phi \wedge (\Psi \wedge \Theta )$; $(\Phi \vee \Psi ) \vee \Theta \equiv \Phi \vee (\Psi \vee \Theta )$; $(\Phi \oplus \Psi ) \oplus \Theta \equiv \Phi \oplus (\Psi \oplus \Theta )$.

2. Commutativity: $\Phi \wedge \Psi \equiv \Psi \wedge \Phi$; $\Phi \vee \Psi \equiv \Psi \vee \Phi$; $\Phi \oplus \Psi \equiv \Psi \oplus \Phi$.

3. Distributivity: $(\Phi \vee \Psi ) \wedge \Theta \equiv (\Phi \wedge \Theta ) \vee (\Psi \wedge \Theta )$; $(\Phi \wedge \Psi ) \vee \Theta \equiv (\Phi \vee \Theta ) \wedge (\Psi \vee \Theta )$; $(\Phi \oplus \Psi ) \wedge \Theta \equiv (\Phi \wedge \Theta ) \oplus (\Psi \wedge \Theta )$.

4. De Morgan’s laws: $\neg (\Phi \vee \Psi ) \equiv \neg \Phi \wedge \neg \Psi$; $\neg (\Phi \wedge \Psi ) \equiv \neg \Phi \vee \neg \Psi$.

5. Double negation: $\neg \neg \Phi \equiv \Phi$.

6. Idempotence: $\Phi \wedge \Phi \equiv \Phi$; $\Phi \vee \Phi \equiv \Phi$.

7. Laws for constants: $\Phi \wedge \neg \Phi \equiv 0$; $\Phi \vee \neg \Phi \equiv 1$; $\Phi \wedge 0 \equiv 0$; $\Phi \vee 0 \equiv \Phi$; $\Phi \wedge 1 \equiv \Phi$; $\Phi \vee 1 \equiv 1$.

8. $\Phi \rightarrow \Psi \equiv \neg \Phi \vee \Psi$.

9. $\Phi \oplus \Psi \equiv (\Phi \wedge \neg \Psi ) \vee (\neg \Phi \wedge \Psi ) \equiv (\Phi \vee \Psi ) \wedge (\neg \Phi \vee \neg \Psi )$.

Call a formula of the form $\Phi_{1} \wedge \Phi_{2} \wedge \ldots \wedge \Phi_{n}$ a logical product. We call its subformulas $\Phi_{i}, 1 \leqslant i \leqslant n$, the factors. Likewise, call a formula of the form $\Phi_{1} \vee \Phi_{2} \vee \ldots \vee \Phi_{n}$ a logical sum. We call its subformulas $\Phi_{i}, 1 \leqslant i \leqslant n$, the summands.

Show that the following rules for transforming logical products and sums can be derived from the basic identities:

Using the basic identities, prove the equivalence of the following pairs of formulas.

Let the interpretation $J$ differ from the interpretation $I$ only in that $J(x)=I(\Theta )$. By induction on the construction of the formula $\Phi$, prove that $J(\Phi )=I\left((\Phi )_{\Theta }^{x}\right)$.

Prove Proposition 19 on p. 81.

Proposition 19: If in two equivalent formulas $\Phi$ and $\Psi$ the propositional variable $x$ is replaced by a formula $\Theta$, then the resulting formulas are again equivalent: if $\Phi \equiv \Psi$, then $(\Phi )_{\Theta }^{x} \equiv (\Psi )_{\Theta }^{x}$.

A Boolean function $f^{*}\left(x_{1}, \ldots , x_{n}\right)$ is called dual to the function $f\left(x_{1}, \ldots , x_{n}\right)$ if $f^{*}\left(x_{1}, \ldots , x_{n}\right)=\neg f\left(\neg x_{1}, \ldots , \neg x_{n}\right)$ for every assignment of values to the variables. For example, conjunction is dual to disjunction and vice versa.

By induction on the construction of the formula $\Phi$, prove the inequality

Give an example where the inequality is strict.

Recall the notation: for a formula $\Phi$ and $\sigma \in \left\{ 0,1\right\}$, write $\Phi^{\sigma } = \Phi$ if $\sigma = 1$ and $\Phi^{\sigma } = \neg \Phi$ if $\sigma = 0$; consequently $1^{\sigma } \equiv \sigma$, $0^{\sigma } \equiv \neg \sigma$, $\sigma^{\sigma } \equiv 1$, and $\sigma^{\tau } \equiv 0$ for $\sigma \neq \tau$ (formula (7)). For a Boolean function $f\left(x_1, \ldots , x_n\right)$ define

Theorem 21: Let $f$ be a Boolean function. 1) If $f$ is not identically zero, then $\mathcal{D}_{f}$ is a perfect DNF representing $f$. 2) If $f$ is not identically one, then $\mathcal{C}_{f}$ is a perfect CNF representing $f$. (Part 1 is proved in the text; part 2 is this problem.)

Prove the second part of Theorem 21 on p. 84: for every assignment of argument values $\sigma_{1}, \ldots , \sigma_{n}$ we have $f\left(\sigma_{1}, \ldots , \sigma_{n}\right)=\mathcal{C}_{f}\left(\sigma_{1}, \ldots , \sigma_{n}\right)$.

Propose procedures for solving the following problems:

Prove that for all $k \leqslant n$ every Boolean function $f \in \mathcal{P}_{n}$ can be represented as

Such a representation is called the expansion of $f$ in $x_{1}, \ldots , x_{k}$. For $k=n$ it yields the perfect DNF from Theorem 21 on p. 84.

How should the procedure for reducing to a perfect DNF be changed so as to obtain a procedure for reducing to a perfect CNF?

Propose a method for simultaneously constructing equivalent DNF and CNF for an arbitrary formula $\Phi$ of propositional logic, using induction on the construction of $\Phi$.

Find equivalent reduced DNFs and prove the equivalence of the following pairs of formulas:

Suppose a DNF $\mathcal{D}$ contains no negations and the absorption laws cannot be applied to it. Prove that $\mathcal{D}$ is a reduced DNF.

Prove the equivalences (8)–(11).

1. $\neg x \equiv (x \oplus 1)$.

2. $\left(x_{1} \wedge x_{2}\right) \equiv \left(x_{1} x_{2}\right)$.

3. $\left(x_{1} \vee x_{2}\right) \equiv \left(x_{1} x_{2} \oplus x_{1} \oplus x_{2}\right)$.

4. $\left(x_{1} \oplus x_{2}\right)\left(x_{3} \oplus x_{4}\right) \equiv \left(x_{1} x_{3} \oplus x_{1} x_{4} \oplus x_{2} x_{3} \oplus x_{2} x_{4}\right)$.

Prove equalities (12) and (13).

Using the basic equivalences and identities (8)–(11), find the equivalent reduced Zhegalkin polynomials and prove the equivalence of the following pairs of formulas:

Find the Zhegalkin polynomials (by the method of undetermined coefficients and using the matrix $J$) for the following functions $f(x, y, z)$. Assume that the argument tuples of the functions are ordered lexicographically and their values are given by a sequence of 8 zeros and ones:

Find the Boolean function of $n$ variables whose reduced Zhegalkin polynomial has the greatest length.