Конъюнкции и дизъюнкции над множеством переменных. Нормальные формы

Определение.Конъюнкцией над множеством переменных Х=(х₁,... ,х_n) называется логическое произведение вида:

К= х_i1^{a i1}& . . . & х_is^{a is} ,

где (х_{i1 , ... ,} х_is ) Í Х, х_ik^{a ik} = x_ik либо`x_ik .

Конъюнкцию К можно представить как результат (s-1)применения двуместной функции логического умножения либо одной обобщенной функции &, а также одноместной функции Ø . Аналогом функции & по принципу действия (выделение 1 на крайней позиции вектора истинности) является функция Вебба¯. Поскольку правило x& у=`x ¯ у справедливо для любого числа переменных, то любая конъюнкция Кможет быть представлена в виде: К=¯( х<sub>i1</sub><sup>Øa i1</sup>, . . . , х<sub>is</sub><sup>Øa i s</sup> ), где ¯ ― обобщенная функция Вебба. Данное представление назовем представлением в базисном наборе(Ø, ¯). Отрицание`x может быть выражено при помощи функции Вебба следующими способами:`x = ¯(х, х) = ¯(х, 0) =¯(0, х ) (дублирующая подстановка (х, х) на практике реализуется замыканием входов элемента ¯ , а подстановка 0 ― заземлением соответствующего входа у функционального элемента (рис.1.5)). Поэтому любая конъюнкция Кможет быть полностью выражена при помощи элементов ¯ ( в базисном наборе(¯)). При этом общее число функциональных элементов в конъюнкции Кпри использовании обоих базисных наборов одинаково.

Рис.1.5

Определение. Дизъюнкцией над множеством переменных Х=(х₁, ... , х_n)называется логическая сумма вида:

D= х_i1^{a i1}Ú. . . Ú х_is ^{a is},

где (х_{i1, ... ,} х_is ) Í Х, х_ik^{a ik} = x_ik либо`x_ik .

Дизъюнкция D может быть реализована как при помощи (s-1)двуместной функции Ú, так и применением одной обобщенной функции Ú, а также одноместной функции Ø. Поскольку аналогом функции Úпо принципу действия (выделение 0 на крайней позиции вектора истинности) является функция штрих Шеффера |, то с учетом зависимости xÚ у =`x |` у, любая дизъюнкция D может быть представлена в виде:

D = | ( х_i1^{Øa i1}, . . . , х_is^{Øa is} ),

где | ― обобщенная функция Шеффера. Данное представление назовем представлением в базисном наборе(Ø, | ).

Так как отрицание можно выразить через | :`x =| (х, х) = | (х,1) = |(1,х)(рис.1.6), то с использованием данных правил любая дизъюнкция D может быть полностью выражена при помощи элементов| ( в базисном наборе( | )). При этом у одной и той же дизъюнкции общее число функциональных символов при использовании обоих наборов также одинаково.

Рис.1.6

Определение. Дизъюнктивной нормальной формой (ДНФ) булевой функции f (х ⁿ)называется формульное выражение вида:

f = К₁Ú ... Ú К_р ,

где К₁ , ... , К_р - конъюнкции.

Для соединения конъюнкций в ДНФ могут использоваться как 2—местная, так и обобщенная функция Ú. Последняя с использованием эквивалентного соотношения

Ú (К₁ , ... , К_р ) = Ø ¯ ( К₁ , ... , К_р )

может быть заменена обобщенной функцией Вебба.

Определение. Веббовой нормальной формой (ВНФ) булевой функции f (`х ⁿ)назовем её выражение вида:

f = Ø ¯ ( К₁ , ... , К_р ),

где К₁,...,К_р — конъюнкции, представленные как К_s =¯( х_i1^Øai1, ... , х_is^Øais), (1£ s £ p).

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

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

Замечание 2. Выражения с одним слагаемым вида f = К₁для сохранения общности также будем относить к ДНФ (ВНФ). Назовем такие формы вырожденными.

Пример 1. Представить ДНФ булевой функции f = х`у Ú`х у z в эквивалентной ВНФ. Дать решение задачи а) в базисном наборе(Ø, ¯)и б) в базисном наборе(¯) .

Решение. Заменяя умножение во внутренних конъюнкциях ДНФ функцией Вебба, вначале изменим внутренние конъюнкции формы: х`у = ¯(х, у), `х у z = ¯(х,`у,`z). Внешнее сложение преобразуем с использованием правила: Ú (К₁, ... , К_р) = Ø ¯ (К₁ , ... , К_р ). В итоге получим искомое выражение функции в базисном наборе(Ø, ¯):

f = د (¯(х, у), ¯(х, у, z )).

Применяя эквивалентную замену`x = ¯(х, х), находим формульное выражение функции, содержащее только функцию Вебба:

f =¯[¯ (¯(¯(х, x), у), ¯( х, ¯(y, у), ¯(z, z))), ¯ (¯(¯(х, x), у), ¯( х, ¯(y, у), ¯(z ,z)))].

Полученные выражения дают искомое решение задачи.

Определение. Конъюнктивной нормальной формой (КНФ) булевой функции f (х ⁿ)называется её формульное выражение вида:

f=D₁&...& D_р,

где D₁ ,..., D_р — дизъюнкции.

В КНФ могут использоваться 2 — местная или обобщенная функции &. Последняя с использованием эквивалентного соотношения & (D₁, ... , D_р) = Ø|(D₁, ... , D_р ) может быть заменена обобщенной функцией Шеффера.

Определение. Шефферовой нормальной формой (ШНФ) булевой функции f (х ⁿ)назовем её выражение вида:

f = Ø|(D₁, ..., D_р),

где D₁, ... ,D_р — дизъюнкции, представленные в эквивалентной форме D_i =| (х_i1^{Øa i1}, . . . , х_is^{Øa i s} ),(1£ i £ p).

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

Замечание 4. Выражения с одним сомножителем вида f = D₁для сохранения общности будем считать вырожденными КНФ (ШНФ).

Пример 2. Перевести КНФ булевой функции f =(`х Ú у Ú z)& (`у Ú z) в эквивалентную ШНФ. Дать решение задачи а) в базисном наборе(Ø, |)и б) в однофункциональном наборе(|) .

Решение. Заменим сложение во внутренних суммах (дизъюнкциях) КНФ обобщенной функцией Шеффера: (х Ú у Ú z) = | (х,`у,`z); (у Ú` z)= | (у, z). Затем по правилу & (D₁, ... , D_р)= Ø |(D₁, . . . , D_р )производим замену внешнего сложения. В итоге получаем выражение функции в базисном наборе(Ø, | ):

f = Ø| (|(х,`у,`z),| (у, z)).

После эквивалентной замены`x = |(х, х), находим формулу функции, содержащую только функцию Шеффера:

f =|[| (| (х,|(у, у), |(z, z)),| (у , z)),|(| (х,|(у, у),|(z, z)),|(у , z))].

Таким образом, получены обе искомые формулы.

ЗАДАЧИ

1. Доказать (например, с использованием таблиц истинности) правильность следующих подстановок:

а)`x = ¯(х, х) = ¯(х,0) =¯(0, х);

б)`x =| (х, х) = |(х, 1) = |(1, х) .

2. Доказать эквивалентность следующих обобщенных формул:

а) F₁=Ú ( х₁, ... , х_s )и F₂= د ( х₁, ... , х_s );

б) F₁ = & ( х₁, ... , х_s )и F₂= Ø| ( х₁, ... , х_s).

3. Представить ДНФ в виде эквивалентной ВНФ. Дать решения задачи в базисных наборах(Ø, ¯)и (¯) :

а) f =`х у z Ú`у Ú`z ;

б) f = х уÚ`х`у Ú у z .

4. Преобразовать КНФ булевых функций в эквивалентные ШНФ с использованием базисных наборов(Ø , | ) и (| ):

а) f = (х Ú у Ú`z)(х Ú`у Ú`z);

б) f = (х Ú у)(у Ú`z)(х Ú`z).