Почему !&& равно ||?

Question

Недавно я столкнулся с проблемой, в которой мы должны были найти эквивалентное логическое выражение для (x && !y) при заданном наборе вариантов.Проходя через несколько примеров, мой профессор отметил, что !(!x && y) не правильный ответ, потому что!распределяет, делая это выражение эквивалентным (x || !y), поэтому!меняется && на ||.И наоборот, правильный ответ был !(!x || y).

Я пытался поиграть с таблицами правды для && и ||и я не могу понять, почему это было бы правдой.Отрицание результатов из таблицы && true не дает результатов, равных ||.Отрицание вывода && приведет к

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

. Я вижу, как ответ выше, правильный, я просто не понимаю, почему.Что мне здесь не хватает?

Answer 1

Законы де Моргана https://en.wikipedia.org/wiki/De_Morgan%27s_laws имеют отношение.

Они говорят:

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

, где отрицание и означает или Обе отрицания при отрицании или означают и обоих отрицаний.

Заменим a на (! x) и b на y в II:

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

, что дает

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

, показывая, что в действительности правильный эквивалент равен !(!x || y).