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

Пусть F - производная функция алгебры логики n переменных. Рассмотрим формулу:

(1)

Формула (1) составлена следующим образом: каждое слагаемое этой логической суммы предоставляет собой конъюнкцию, в которой первый член является значением функции F при некоторых определенных значениях переменных , остальные же члены конъюнкции представляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значение 0.

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

Например, если принимает значение 0, а остальные переменные принимают значение 1, то функция F принимает значение F(0, 1, 1, …, 1).

При этом логическое слагаемое

,

входящее в формулу (1), принимает также значение F(0, 1, …,1), все остальные логические слагаемые формулы (1) имеют значение 0.

Действительно, в них знаки отрицания над переменными распределяются иначе, чем в рассмотренном слагаемом, но тогда при замене в конъюнкцию войдет символ 0 без знака отрицания, символ 1 под знаком отрицания. В таком случае один из членов конъюнкции имеет значение 0, а поэтому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности значением формулы (1) является F(0, 1, …, 1).

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

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

1.Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F .

2.Все логические слагаемые формулы различны.

3.Ни одно логическое слагаемое формулы не содержит одновременно переменную и отрицание.

4.Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

Перечисленные свойства называются свойствами совершенства.

Каждой не тождественно ложной функции соответствует единичная формула вида (1).

Если функция F задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто. Действительно, для каждого набора значений переменных, на котором функция F принимает значение 1, запишем конъюнкцию элементарных переменных, взяв за член конъюнкции , если значение на указанном наборе значений переменных есть 1 и отрицание , если значение есть 0. дизъюнкция всех записанных конъюнкций и будет искомой формулой.

Пусть, например, функция F имеет следующую таблицу истинности (табл. 18)

Таблица 18

			F				F

Для наборов значений переменных (1, 1, 0), (1, 0, 1), (0, 1, 0), (0, 0, 0), на которых функция принимает значение 1, запишем конъюнкцию , , , , а искомая формула, обладающая свойствами совершенства, имеет вид .

Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания. Будем называть операцию конъюнкции двойственной операции дизъюнкции, а операцию дизъюнкции двойственной операции конъюнкции.

Определение. Формулы А и называется двойственными, если формула получается из формулы А путем замены в ней каждой операции на двойственную.

Например, для формулы двойственной будет формула .

Лемма. Если для формулы А двойственной является формула , то справедлива равносильность

Теорема. Если формулы А и В равносильны ,то равносильны и двойственные им формулы, т.е.