.02 Булевы функции. Таблицы истинности. Булев куб.

1. Поймем вначале, какие переменные у нее являются существенными, а какие - нет.

Во-первых, легко заметить, что - существенная переменная, поскольку есть два набора

отличающиеся только в первой координате, на которых функция различна:

Далее, - тоже существенная переменная, поскольку есть два набора

отличающиеся только в третьей координате, на которых функция различна:

Переменная - наоборот, несущественная. Поскольку на всех возможных наборах, отличающихся только во второй координате:

наша функция совпадает (на первых двух наборах она равна единице, а на всех остальных парах наборов она равна нулю).

Следовательно, переменная - несущественная.

В таком случае, от переменной можно насильно избавиться, и получить уже функцию от двух переменных , которую мы не будем отличать от исходной функции .

Как избавиться от ? Ну, просто вычеркнуть столбец из таблицы истинности нашей функции:

И что же, на этом все? Нет конечно. Должна ведь получиться таблица истинности функции от двух переменных, а у нас получилась пока ерунда - функция уже от двух переменных, но таблица у неё слишком длинная.

Теперь надо склеить полностью совпадающие столбцы таблицы в один (а совпадающие столбцы обязательно будут, это, собственно, и означает, что была фиктивной). Получим такую таблицу истинности:

2. Как теперь задать эту функцию формулой? Во-первых, можно просто построить её СДНФ - это вообще универсальный способ перейти от таблице истинности к формуле. Но можно поступить быстрее. Ясно, что если взять отрицание этой функции:

То мы получим обыкновенную дизъюнкцию . Поэтому наша исходная функция - это отрицание дизъюнкции, т.к. если , то

(здесь мы воспользовались законом двойного отрицания).