Сколько наборов логических переменных удовлетворяют условиям:
((xi ∧ yj) → (xi ∧ yj+1)) ∧ ((xi ∧ yj)→(xi+1 ∧ yj)) = 1
для всех i < 5, j < 6.
Решение. Пусть есть m переменных x1, x2, x3, …, xm-1, xm и n переменных y1, y2, y3, … yn-1, yn.
И пусть есть (m−1)*(n−1) уравнений вида (xi∧yj→xi+1∧yj)∧(xi∧yj→xi∧yj+1)=1 для всех i<m и j<n. Конъюнкция двух выражений равна 1 тогда и только тогда, когда каждое из двух выражений равно 1. Следовательно, каждая из импликаций истинна.
Воспользуемся тем, что выражение A→B равносильно A≤B. Это значит, что xi∧yj≤xi+1∧yj и xi∧yj≤xi∧yj+1 для всех i<m и j<n. Исходя из этого, запишем значения всевозможных конъюнкций в таблицу, в которой значения в каждой строке и каждом столбце, кроме, возможно, последних, не убывают.
Рассмотрим ячейки таблицы со значениями 1, расположенные не в последней строке и не в последнем столбце. Выберем из них ячейки с минимальным номером строки k, а среди них выберем ячейку с минимальным номером столбца l. Это означает, что xk∧yl=1, а все конъюнкции xi∧yl=0, xk∧yj=0 и xi∧yj=0, где i<k и j<l. Отсюда следует, что xk=1 и yl=1, а все xi=0 и yj=0, где i<k и j<l, поэтому первые (k−1) строка и (l−1) столбец полностью состоят из нулей.
Внутри каждой строки и каждого столбца, кроме, возможно, последних, значения расположены по принципу не убывания, поэтому все клетки строки k правее выбранной ячейки, а также все клетки столбца l ниже выбранной ячейки, тоже должны быть равны 1. Поэтому xi=1 при k≤i≤m и yj=1 при l≤j≤n, откуда следует, что весь правый нижний прямоугольник состоит из единиц.
Получаем, что для нашего выбора ячейки существует ровно одна таблица значений конъюнкций и ровно один набор переменных. Поскольку ячейку со значением 1, находящуюся не в последнем столбце и не в последней строке, можно выбрать (m−1)*(n−1) способами, следовательно, существует столько же таблиц значений конъюнкций и столько же наборов переменных.
Теперь рассмотрим случай, когда такой ячейки нет, то есть на пересечении первых (m−1) строк и первых (n−1) столбцов стоят только нули. Это означает, что xi=0 при i<m или yj=0 при j<n (возможно, одновременно).
Если xi=0 при i<m, то xm и все yj могут принимать любые значения, то есть существует 2*2n вариантов наборов переменных. Если yj=0 при j<n, то yn и все xi могут принимать любые значения, то есть существует 2*2m вариантов.
Осталось посчитать случаи, которые мы посчитали дважды. Если xi=0 при i<m и yj=0 при j<n, то эти наборы мы посчитали 2 раза. В этих случаях xm и yn могут быть любыми, поэтому имеем 4 лишних случая.
В итоге получаем формулу (m−1)*(n−1)+2n+1+2m+1−4.
Подставляя значения m = 5 и n = 6 получаем:
(5 − 1) · (6 − 1) + 26 + 1 + 25 + 1 − 4 = 208.
Ответ: 208.