0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.