Can any boolean expression with OR operators be converted to only AND operators?

Question

I'm fairly new to Boolean algebra and I was wondering, using Boolean theorems,can any Boolean expression with an OR operators in it be converted to an equivalent expression using only AND operators? Do some expressions come to a point where you don't have any choice but to use OR operators?

For example, I have tried to simplify the following expression into only AND operators, but I don't think I'm getting the write answer:

xy'z' + x'y'z = y'(xz' + x'z) = y'(xz' + (xz')') = y'(1) = y'

y' isn't the right answer as it has different truth tables to the original expression. So what am I doing wrong in my simplification? And can you convert any expression with an OR to one with only AND's?

Answer 1

The answer to your question is yes. You can prove it by induction on the number of OR operators, using the fact that for any two formulae $\sigma$ and $\tau$,

$\sigma \lor \tau = \lnot (\lnot \sigma \land \lnot \tau)$.

Using this substitution will always allow you to reduce the number of OR operators by one, until eventually you get down to $0$.

This is an important observation in first-order logic because it vastly simplifies the proof of any statement that must be proved via induction on the length of a formula.

In your problem, I'm assuming you're using multiplication as "and," addition as "or," and prime as "not." Then

$$(x \land \lnot y \land \lnot z) \lor (\lnot x \land \lnot y \land z)=\lnot(\lnot (x \land \lnot y \land \lnot z) \land \lnot (\lnot x \land \lnot y \land z))$$

which is free of OR operators as required.

Answer 2

The DeMorgan laws

$ \neg (p \wedge q) \iff ( \neg p \lor \neg q) $

and

$ \neg (p \lor q) \iff ( \neg p \wedge \neg q) $

together with double negation elimitation

$ \neg \neg p \iff p $

may be used to convert between conjuctive and disjunctive phrases, but notice you'll often need negation too