a) Поступим аналогично с СДНФ. Во-первых, очевидно, что если функция равна нулю только на наборе , то

(просто-напросто левая и правая части равенства равны нулю одновременно, и равны единице одновременно).

Но тогда верен и более общий факт. Любую функцию можно представить в виде

где .

Почему любая стоит в кавычках? Из этого правила есть ровно одно исключение. По аналогии с тем, как в СДНФ не получится выразить тождественно нулевую функцию, в нашем случае, то есть в СКНФ, не получится выразить тождественно единичную функцию. Все остальные - можно.

2. Как же выразить эту функцию

в СКНФ? Надо для начала составить её таблицу истинности.

А далее, чтобы выписать СКНФ нашей функции, мы должны просто написать конъюнкцию по всем наборам, на которых равна 0 всевозможных дизъюнкций переменных или их отрицаний, причем в дизъюнкцию переменная входит с отрицанием, если соответствующая координата в соответствующем наборе равна единице. Получаем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Действительно, построив таблицу истинности, убеждаемся:

Заметим, что и обладают таким свойством, что они равны 1, если обе и равны 1.

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

Однако на наборе принимает значение ноль.

Следовательно, нельзя выразить никакой композицией и .

Таблица истинности:

Тогда для такой СДНФ будет выглядеть так:

Для начала, запишем таблицу истинности этой функции.

Далее, чтобы записать СДНФ, нужно написать дизъюнкцию конъюнкций всех возможных наборов переменных или их отрицаний, на которых функция равна 1. Причем в каждом дизъюнкте мы берем переменную без отрицания, если в соответствующем наборе она была равна 1, и с отрицанием, если она была равна 0.

Тогда для такой СДНФ будет выглядеть так:
.

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

Однако если мы рассмотрим функцию, тождественно равную нолю:

То справа получится пустая дизъюнкция - ведь нет ни одного набора, на котором функция была бы равна 1. Поэтому формально тождественный ноль выразить в СДНФ нельзя.

Комментарий: однако через систему тождественный ноль все таки выражается, например, как .