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)