CODEWITHSUNDEEP
booleanboolean-logicboolean-expression
user9513650
user9513650

Reputation:

Why does ! && equal ||?

I recently came across a problem in which we were to find an equivalent boolean expression for (x && !y) given a set of choices. While walking through a few of the examples my professor noted that !(!x && y) is not the correct answer because the ! distributes making this expression equivalent to (x || !y), so the ! changes && to ||. Inversely, the correct answer was !(!x || y).

I tried to play around with the truth tables for && and || and I cannot see why this would be true. Negating the results from the && truth table doesn't give results equal to ||. Negating the output of && would produce 

    0 && 0 --> 0 !-> 1
    0 && 1 --> 0 !-> 1
    1 && 0 --> 0 !-> 1
    1 && 1 --> 1 !-> 0

I can see how the answer above is correct, I just don't understand why. What am I missing here?

Upvotes: 1

Views: 482

Answers (1)

Pixelchemist
Pixelchemist

Reputation: 24946

De Morgan's laws https://en.wikipedia.org/wiki/De_Morgan%27s_laws are relevant.

They say:

I)   !(a && b) = (!a) || (!b)
II)  !(a || b) = (!a) && (!b)

where negating and means oring both negations while negating or means and of both negations.

Let's replace a by (!x) and b by y in II:

II)  !((!x) || y) = (!(!x)) && (!y)

which gives 

II)  !(!x || y) = x && (!y)

showing that ineed the correct equivalent is !(!x || y).

Upvotes: 1

Related Questions