Аналитическая запись функций алгебры логики

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

Для этого введем параметризацию, позволяющую охарактеризовать значение переменной в «энке». Обозначим , где параметр  равен нулю или единице. Таким образом, . Т.е. если на наборе значение переменной х равно 0, то будем писать «», а в случае, когда соответствующее значение равно 1, то будем записывать просто «х». Заметим, что х^=1 тогда и только тогда, когда х=.

1. о разложении функции по переменным

Каждую истинностную функцию от n аргументов f(x₁,x₂,…,x_n) при любом m (1  m  n) можно представить формулой вида: (1)  , где дизъюнкция берется по всевозможным наборам значений переменных х₁,…,х_m.

Представление функции в виде (1) называется разложением функции по m переменным х₁,…,х_m.

Доказательство:

Рассмотрим произвольный набор значений переменных (₁, ₂,…, _n). Покажем, что левая и правая части (1) имеют на этом наборе одинаковые значения. Значение левой части равно f(₁, ₂,…, _n). Вычислим значение правой части: . Ненулевые члены в дизъюнкции получаются только в том случае, когда набор ₁,₂,…,_m совпадает с набором ₁,₂,…,_m, т.е. в последнем выражении остается только одно ненулевое слагаемое: . И т.к. , то это слагаемое равно f(₁, ₂,…, _n). Таким образом, значения левой и правой части (1) совпадают на произвольном наборе (₁, ₂,…, _n).

Следствия:

1) О разложении по одной переменной.

Если в выражении (1) m=1, то f(х₁, х₂,…, х_n) = x_n& f(х₁, х₂,…, 1) & f(х₁, х₂,…, 0);

2) О разложении по всем n переменным или совершенные дизъюнктивные нормальные формы (СДНФ).

Если в выражении (1) m=n, то . Если f(х₁, х₂,…, х_n) не равна тождественно нулю, то в последнюю дизъюнкцию будут давать вклад только те компоненты, где f(₁, ₂,…, _n)=1, поэтому . Это разложение называется совершенной дизъюнктивной нормальной формой (СДНФ). И, как следует из её определения, для построения СДНФ в таблице истинности функции f надо рассматривать лишь те строки, где функция равна единице. Для каждой такой строки записывается элементарная конъюнкция, состоящая из всех переменных функции. При этом переменная входит в конъюнкцию с отрицанием, если в рассматриваемой строке её значение равно нулю, и без отрицания – в противном случае.

3) Совершенные конъюнктивные нормальные формы (СКНФ).

Совершенная дизъюнктивная нормальная форма есть выражение вида – сумма произведений. Используя принцип двойственности для построения эквивалентных формул, можно получить разложение вида – произведение сумм, которое носит название совершенной конъюнктивной нормальной формы. Так как , то для

, но . Поэтому . Заметим, что при построении последней формулы участвуют лишь такие наборы ₁,₂,…,_n, на которых f(₁,₂,…,_n)=1. Тогда в построении формулы для будут участвовать наборы ₁,₂,…,_n, где , или f(₁,…,_n)=0.

Таким образом, если f(х₁,…,х_n)  1, то – это и есть СКНФ. И, как следует из её определения, для построения СКНФ в таблице истинности функции f надо рассматривать лишь те строки, где функция равна нулю. Для каждой такой строки записывается элементарная дизъюнкция, состоящая из всех переменных функции. При этом переменная входит в дизъюнкцию с отрицанием, если в рассматриваемой строке её значение равно единице, и без отрицания – в противном случае.

Примеры построения СДНФ и СКНФ.

Таким образом, построение СДНФ и СКНФ – это ещё одна возможность записать тождество.