Каждое из логических выражений A и B зависит от одного и того же набора из 5 переменных. В таблицах истинности обоих выражений в столбцах значений стоит ровно по 16 единиц в каждой таблице. Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A → ¬B?

В таблице истинности для 5 переменных всего будет:

строки.

По условию, в таблице истинности выражения A ровно 16 единиц, то есть выражение A истинно в 16 строках. Аналогично выражение B истинно тоже в 16 строках.

Рассмотрим выражение:

Импликация ложна только в одном случае: когда первое выражение истинно, а второе ложно.

То есть:

Так как $\neg B=0$ означает $B=1$, единственный случай, когда выражение ложно:

Следовательно, количество единиц в столбце $A\to \neg B$ будет равно:

Нужно сделать пересечение наборов единиц A и B как можно меньше.

У A есть 16 единиц, у B есть 16 единиц. Всего строк 32, поэтому можно расположить их так, чтобы они вообще не пересекались:

• в первых 16 строках $A=1$, а $B=0$;

• в следующих 16 строках $A=0$, а $B=1$.

Тогда нет ни одной строки, где одновременно $A=1$ и $B=1$.

Значит, импликация никогда не будет ложной:

Максимально возможное число единиц в столбце значений выражения $A\to \neg B$ равно: