1

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?

sparpo
  • 15
  • 1
    Yes, you can convert any Boolean expression such way. It is so for any adequate set of logical connectives, not only for ${AND, NOT}.$ To learn more, see https://en.m.wikipedia.org/wiki/Functional_completeness – user376343 Feb 18 '19 at 20:33
  • You can change any boolean expression to use only NAND (not (A and B)). Or you can change it to use only NOR (not (A or B)). Using only AND and NOT also works, AND alone doesn't. – gnasher729 Dec 09 '22 at 10:07

2 Answers2

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.

Robert Shore
  • 23,332
0

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