Simplifying $(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$

Question

I'm looking at this logical formula:

$(\neg x\land \neg y \land \neg z) \lor (\neg x\land \neg y \land z) \lor (x\land \neg y \land z) \lor ( x\land y \land z)$

Asked to simplify it as much as possible, and I did something like this:

$((\neg x \land \neg y)\land(\neg z \lor z)) \lor ((x \land z)\land(y \land \neg y)) \equiv (\neg x \land \neg y) \lor (x \land z)$

The tutors book lists my solution along with an alternative one with this as the first step: $(1):(x \land \neg x) \lor (\neg x \land \neg y) \lor (x \land z) \lor (\neg y \land z)$

along with some more manipulation to reach:

$(\neg x \lor z) \land (x \lor \neg y)$

Which left me puzzled as this is one step, and can't figure out which rules they used to get to $(1)$ (I presume it's some standard rule). Any ideas?

Answer 1

In (1) the term : $(¬x∧¬y)$ comes from :

$(¬x∧¬y∧¬z)∨(¬x∧¬y∧z) \equiv [(¬x∧¬y) \land (z \lor \lnot z)] \equiv [(¬x∧¬y) \land T] \equiv (¬x∧¬y).$

---

The term : $(x \land z)$ comes from :

$(x∧¬y∧z)∨(x∧y∧z) \equiv [(x \land z) \land (y \lor \lnot y)] \equiv [(x \land z) \land T] \equiv (x \land z).$

---

Applying idempotency : $a \lor a \equiv a$, we can "duplicate" the 2nd and 3rd disjuncts :

$(¬x∧¬y∧z)∨(x∧¬y∧z) \equiv (¬y∧z) \lor (x \land \lnot x).$

---

Thus, the original formula is equivalent to :

$(¬x∧¬y) \lor (x \land z) \lor (¬y∧z) \lor (x \land \lnot x).$

---

Now we have :

$(x∧z)∨(¬y∧z) \equiv (x∨¬y)∧z$

$(x∧¬x)∨(¬x∧¬y) \equiv (x∨¬y)∧¬x$

and putting all together :

$[(x∨¬y)∧z] ∨ [(x∨¬y)∧¬x] \equiv [(x∨¬y)∧(¬x∨z)]$.

Answer 2

Make a 3-dimensional truth table. Here, I'll just make 2 two-dimensional truth tables:

$z$: $$\begin{array}{ccc} &x&\text{not }x\\ y&\checkmark\\ \text{not }y&\checkmark&\checkmark \end{array}$$

not $z$: $$\begin{array}{ccc} &x&\text{not }x\\ y&\\ \text{not }y&&\checkmark \end{array}$$

It seems simplest to me to group the first two checkmarks as $x\land z$, and the other two as $\lnot y\land\lnot x$, so that all together makes $$(x\land z)\lor(\lnot y\land\lnot x)$$

However we can view the collection of checkmarks as an intersection instead of a union. For the language I will use, view the entire three-dimensional table as a cube, with the "$z$" table as its top face, and the "not $z$" table as its bottom face. The checkmarks are the intersection of

• the top face unioned with the right face
• the left face unioned with the front face

This translates to the book's answer: $(z\lor\lnot x)\land(x\lor\lnot y)$