TAOCP 7.1.1 Exercise 23
Let F = (\alpha \wedge \alpha z)\vee(\bar\alpha xz)\vee(x\bar y z).
Exercise 23. [15] [15] What is the conjunctive prime form of $(\alpha\wedge\alpha z)\vee(\bar\alpha xz)\vee(x\bar y z)$?
Verified: yes
Solve time: 1m04s
Solution
Let
$$ F = (\alpha \wedge \alpha z)\vee(\bar\alpha xz)\vee(x\bar y z). $$
Since juxtaposition denotes conjunction, $\alpha z = \alpha \wedge z$. Hence
$$ \alpha \wedge \alpha z = \alpha \wedge (\alpha \wedge z) = (\alpha \wedge \alpha)\wedge z = \alpha \wedge z. $$
Thus
$$ F = (\alpha z)\vee(\bar\alpha xz)\vee(x\bar y z). $$
Each disjunct contains $z$, so distributivity $(x\vee y)\wedge z = (x\wedge z)\vee (y\wedge z)$ applied in reverse yields
$$ F = z \wedge (\alpha \vee (\bar\alpha x)\vee (x\bar y)). $$
Let
$$ G = \alpha \vee (\bar\alpha x)\vee (x\bar y). $$
Apply $(x\wedge y)\vee z = (x\vee z)\wedge (y\vee z)$ from (2) with $x=x$, $y=\bar\alpha$, $z=\alpha$:
$$ (\bar\alpha x)\vee \alpha = (x\vee \alpha)\wedge(\bar\alpha \vee \alpha). $$
Since $\bar\alpha \vee \alpha = 1$,
$$ (\bar\alpha x)\vee \alpha = x\vee \alpha. $$
Hence
$$ G = (x\vee \alpha)\vee (x\bar y). $$
Apply absorption in the form $x \vee (x\wedge y)=x$, derived from distributivity (1):
$$ (x\vee \alpha)\vee (x\bar y) = \alpha \vee \bigl(x \vee (x\bar y)\bigr) = \alpha \vee x. $$
Thus
$$ F = z \wedge (\alpha \vee x). $$
To verify conjunctive primality, the expression is already a conjunction of clauses. The clause $z$ is necessary since substituting $z=0$ forces $F=0$ regardless of $\alpha$ and $x$. The clause $(\alpha \vee x)$ is necessary since for $\alpha=0$, $x=0$, and $z=1$, the value of $F$ is $0$, while both literals in the clause fail. Each clause is minimal since removing either changes the function.
Therefore the conjunctive prime form is
$$ \boxed{z \wedge (\alpha \vee x)}. $$
This completes the solution. ∎