A, B and C are three boolean values. Write an expression in terms of only !(not) and &&(and) which always gives the same value as A||B||C

Question

Chanced upon this beautiful problem. Since I am new to Boolean expressions, it is looking quite difficult.

I guess parentheses can be used.

If one of A, B, C is true, A||B||C must be true. Using AND and NOT, it can be done but, how do we know which one has which value?

I tried using truth tables, but three variables were too much.

Any ideas on how to solve, or at least how to make it faster?

Answer 1

Learn De Morgan's laws. It's a little piece of a basic knowledge for a programmer.

They state, among others, that not(X or Y) = (not X) and (not Y).

If you negate both sides and then apply the formula twice—first to ((A or B) or C), treating the (A or B) subexpression as X, and then to (A or B) itself—you'll get the desired result:

A || B || C =
(A || B) || C =
!(!(A || B) && !C) =
!((!A || !B) && !C) =
!(!A && !B && !C)

Answer 2

DeMorgan's Law (one of them, anyway), normally applied to two variables, states that:

A or B == not (not A and not B)

But this works equally well for three (or more) variables:

A or B or C == not (not A and not B and not C)

This becomes obvious when you realise that A or B or C is true if any of them are true, the only way to get false if if all of them are false.

And, only if they're all false will not A and not B and not C give true (hence not(that) will give false). For confirmation, here's the table, where you'll see that the A or B or C and not(notA and notB and notC) columns give the same values:

A B C     A or B or C     notA notB notC     not(notA and notB and notC)
-----     -----------     --------------     ---------------------------
f f f          f           t    t    t                     f
f f t          t           t    t    f                     t
f t f          t           t    f    t                     t
f t t          t           t    f    f                     t
t f f          t           f    t    t                     t
t f t          t           f    t    f                     t
t t f          t           f    f    t                     t
t t t          t           f    f    f                     t