Построение формулы алгебры высказываний по заданной логической функции

Рассмотрим задачу, обратную той, о которой шла речь в разделах III, IV - построение функции для некоторой формулы алгебры высказываний. Задана некоторая функция f(x₁, x₂, ... x_n), нужно построить для нее формулу S. Задача эта неоднозначна, существует множество равносильных между собой формул, соответствующих этой функции. Будем строить совершенную нормальную форму. При этом учтем, что полная элементарная дизъюнкция имеет единственный ноль, а полная элементарная конъюнкция - единственную единицу. Решение задачи рассмотрим на примере.

Пусть задана некоторая функция трех аргументов f(1,1,1)=f(1,0,0)=f(0,1,0)=1. Это значит, что на наборах (1,1,1), (1,0,0), (0,1,0) функция принимает значение 1, а на остальных наборах - 0.

Построим S в виде совершенной дизъюнктивной нормальной формы. Так как S не тождественно ложна, это можно сделать. СДНФ состоит из стольких слагаемых, сколько единиц содержит функция. Первому значению 1 соответствует слагаемое xyz, принимающее значение 1 при х=1, y=1, z=1. Второму значению 1 соответствует слагаемое , принимающее значение 1 при х=1, y=0, z=0. Аналогично третье слагаемое, соответствующее 1, стоящей в шестой строке таблицы f есть . Следовательно, . Итак:

1) Совершенная дизъюнктивная нормальная форма содержит столько слагаемых, сколько единиц имеет функция.

2) Эти единицы соответствуют тем наборам переменных, при которых каждое слагаемое (элементарная конъюнкция) обращается в единицу, т.е. переменным, входящим в элементарную конъюнкцию без знака отрицания, соответствует значение 1, а со знаком отрицания - 0.

Чтобы написать СКНФ по заданной функции, нужно выбрать все значения 0, встречающиеся в ней, и рассмотреть наборы значений переменных, отвечающие этим нулям. В заданном примере таблица содержит пять нулей. Первому значению 0 отвечает сомножитель , обращающийся в 0 при х=1, y=1, z=0. Второму - при х=1, y=0, z=1 и т.д. В результате получим

Итак:

1. СДНФ содержит столько сомножителей, сколько нулей имеет истинностная таблица.

2. Эти нули соответствуют тем наборам переменных, при которых каждый сомножитель (каждая элементарная сумма) обращается в 0, т.е. переменным, входящим в элементарную сумму без знака отрицания, соответствует значение 0, а со знаком отрицания - 1.

Заметим, что используя список основных равносильных формул, полученные выражения для S упрощают, если это возможно.