Is the following boolean expression a tautology?

Question

I have the following boolean Expression:

!(x && z) || (x && !y && z) || (z && !x && y) || !(!x && y) || (!y && !x && z)

or

(¬(x ∧ z) ∨ ((x ∧ (¬y ∧ z)) ∨ ((z ∧ (¬x ∧ y)) ∨ (¬(¬x ∧ y) ∨ (¬y ∧ (¬x ∧ z))))))

So im asked to simplify this Expression and later build the conjunctive normalform.

For me it seems like !(!x && y) can be converted to x || !y and !(x && z) can be converted to !x || !z After that you can sum up both expressions and !x || x will give you 1. So now there is:

1 || !z || (x && !y && z) || (z && !x && y) || !y || (!y && !x && z)

And this equals to 1. But is 1 the minimal Expression of this boolean expression?

So i'm almost 100% sure this is a tautology and i also checked it with a truth table. What i'm missing here?

Answer 1

Yes. You are right. Here's the derivation.

$$(xz)' \lor (xy'z) \lor (x'yz) \lor (x'y)' \lor (x'y'z)$$

Applying De Morgan's Law $$\Leftrightarrow \color{red}{(x' \lor z')} \lor (xy'z) \lor (x'yz) \lor \color{red}{(x\lor y')} \lor (x'y'z)$$

Applying associativity law to remove brackets $$\Leftrightarrow x' \lor z' \lor xy'z \lor x'yz \lor x \lor y' \lor x'y'z$$

$$\Leftrightarrow \color{red}{x'} \lor z' \lor xy'z \lor x'yz \lor \color{red}{x} \lor y' \lor x'y'z$$

Applying commutativity of $\lor$ to rearrange $$\Leftrightarrow \color{red}{(x \lor x')} \lor {\text {rest of expression}}$$

$$\Leftrightarrow \color{red}{TRUE} \lor {\text {rest of expression}}$$

$$\Leftrightarrow TRUE$$

So, TRUE is the equivalent minimal expression.