Конъюнкции и дизъюнкции над множеством переменных. Нормальные формы
Определение.Конъюнкцией над множеством переменных Х=(х1,... ,хn) называется логическое произведение вида:
К= хi1a i1& . . . & хisa is ,
где (хi1 , ... , хis ) Í Х, хika ik = xik либо`xik .
Конъюнкцию К можно представить как результат (s-1)применения двуместной функции логического умножения либо одной обобщенной функции &, а также одноместной функции Ø . Аналогом функции & по принципу действия (выделение 1 на крайней позиции вектора истинности) является функция Вебба¯. Поскольку правило x& у=`x ¯ у справедливо для любого числа переменных, то любая конъюнкция Кможет быть представлена в виде: К=¯( хi1Øa i1, . . . , хisØa i s ), где ¯ ― обобщенная функция Вебба. Данное представление назовем представлением в базисном наборе(Ø, ¯). Отрицание`x может быть выражено при помощи функции Вебба следующими способами:`x = ¯(х, х) = ¯(х, 0) =¯(0, х ) (дублирующая подстановка (х, х) на практике реализуется замыканием входов элемента ¯ , а подстановка 0 ― заземлением соответствующего входа у функционального элемента (рис.1.5)). Поэтому любая конъюнкция Кможет быть полностью выражена при помощи элементов ¯ ( в базисном наборе(¯)). При этом общее число функциональных элементов в конъюнкции Кпри использовании обоих базисных наборов одинаково.
Рис.1.5
Определение. Дизъюнкцией над множеством переменных Х=(х1, ... , хn)называется логическая сумма вида:
D= хi1a i1Ú. . . Ú хis a is,
где (хi1, ... , хis ) Í Х, хika ik = xik либо`xik .
Дизъюнкция D может быть реализована как при помощи (s-1)двуместной функции Ú, так и применением одной обобщенной функции Ú, а также одноместной функции Ø. Поскольку аналогом функции Úпо принципу действия (выделение 0 на крайней позиции вектора истинности) является функция штрих Шеффера |, то с учетом зависимости xÚ у =`x |` у, любая дизъюнкция D может быть представлена в виде:
D = | ( хi1Øa i1, . . . , хisØa is ),
где | ― обобщенная функция Шеффера. Данное представление назовем представлением в базисном наборе(Ø, | ).
Так как отрицание можно выразить через | :`x =| (х, х) = | (х,1) = |(1,х)(рис.1.6), то с использованием данных правил любая дизъюнкция D может быть полностью выражена при помощи элементов| ( в базисном наборе( | )). При этом у одной и той же дизъюнкции общее число функциональных символов при использовании обоих наборов также одинаково.
Рис.1.6
Определение. Дизъюнктивной нормальной формой (ДНФ) булевой функции f (х n)называется формульное выражение вида:
f = К1Ú ... Ú Кр ,
где К1 , ... , Кр - конъюнкции.
Для соединения конъюнкций в ДНФ могут использоваться как 2—местная, так и обобщенная функция Ú. Последняя с использованием эквивалентного соотношения
Ú (К1 , ... , Кр ) = Ø ¯ ( К1 , ... , Кр )
может быть заменена обобщенной функцией Вебба.
Определение. Веббовой нормальной формой (ВНФ) булевой функции f (`х n)назовем её выражение вида:
f = Ø ¯ ( К1 , ... , Кр ),
где К1,...,Кр — конъюнкции, представленные как Кs =¯( хi1Øai1, ... , хisØais), (1£ s £ p).
С помощью ДНФ и ВНФ наиболее просто выражаются булевы функции, у которых в векторе истинности преобладают нули и мало единиц.
Замечание 1. В виде ДНФ и ВНФ могут быть представлены все функции алгебры логики, не равные константе 0. Эта функция не представима в данных формах, поскольку при наличии хотя бы одной конъюнкции в формулах ДНФ или ВНФ в векторе истинности функции также должна присутствовать хотя бы одна единица.
Замечание 2. Выражения с одним слагаемым вида f = К1для сохранения общности также будем относить к ДНФ (ВНФ). Назовем такие формы вырожденными.
Пример 1. Представить ДНФ булевой функции f = х`у Ú`х у z в эквивалентной ВНФ. Дать решение задачи а) в базисном наборе(Ø, ¯)и б) в базисном наборе(¯) .
Решение. Заменяя умножение во внутренних конъюнкциях ДНФ функцией Вебба, вначале изменим внутренние конъюнкции формы: х`у = ¯(х, у), `х у z = ¯(х,`у,`z). Внешнее сложение преобразуем с использованием правила: Ú (К1, ... , Кр) = Ø ¯ (К1 , ... , Кр ). В итоге получим искомое выражение функции в базисном наборе(Ø, ¯):
f = د (¯(х, у), ¯(х, у, z )).
Применяя эквивалентную замену`x = ¯(х, х), находим формульное выражение функции, содержащее только функцию Вебба:
f =¯[¯ (¯(¯(х, x), у), ¯( х, ¯(y, у), ¯(z, z))), ¯ (¯(¯(х, x), у), ¯( х, ¯(y, у), ¯(z ,z)))].
Полученные выражения дают искомое решение задачи.
Определение. Конъюнктивной нормальной формой (КНФ) булевой функции f (х n)называется её формульное выражение вида:
f=D1&...& Dр,
где D1 ,..., Dр — дизъюнкции.
В КНФ могут использоваться 2 — местная или обобщенная функции &. Последняя с использованием эквивалентного соотношения & (D1, ... , Dр) = Ø|(D1, ... , Dр ) может быть заменена обобщенной функцией Шеффера.
Определение. Шефферовой нормальной формой (ШНФ) булевой функции f (х n)назовем её выражение вида:
f = Ø|(D1, ..., Dр),
где D1, ... ,Dр — дизъюнкции, представленные в эквивалентной форме Di =| (хi1Øa i1, . . . , хisØa i s ),(1£ i £ p).
Замечание 3. В виде КНФ и ШНФ могут быть представлены все функции алгебры логики, не равные константе 1. Данная функция не представима в виде КНФ и ШНФ, поскольку при наличии хотя бы одной дизъюнкции в их формулах вектор истинности функции также должен иметь хотя бы один нуль.
Замечание 4. Выражения с одним сомножителем вида f = D1для сохранения общности будем считать вырожденными КНФ (ШНФ).
Пример 2. Перевести КНФ булевой функции f =(`х Ú у Ú z)& (`у Ú z) в эквивалентную ШНФ. Дать решение задачи а) в базисном наборе(Ø, |)и б) в однофункциональном наборе(|) .
Решение. Заменим сложение во внутренних суммах (дизъюнкциях) КНФ обобщенной функцией Шеффера: (х Ú у Ú z) = | (х,`у,`z); (у Ú` z)= | (у, z). Затем по правилу & (D1, ... , Dр)= Ø |(D1, . . . , Dр )производим замену внешнего сложения. В итоге получаем выражение функции в базисном наборе(Ø, | ):
f = Ø| (|(х,`у,`z),| (у, z)).
После эквивалентной замены`x = |(х, х), находим формулу функции, содержащую только функцию Шеффера:
f =|[| (| (х,|(у, у), |(z, z)),| (у , z)),|(| (х,|(у, у),|(z, z)),|(у , z))].
Таким образом, получены обе искомые формулы.
ЗАДАЧИ
1. Доказать (например, с использованием таблиц истинности) правильность следующих подстановок:
а)`x = ¯(х, х) = ¯(х,0) =¯(0, х);
б)`x =| (х, х) = |(х, 1) = |(1, х) .
2. Доказать эквивалентность следующих обобщенных формул:
а) F1=Ú ( х1, ... , хs )и F2= د ( х1, ... , хs );
б) F1 = & ( х1, ... , хs )и F2= Ø| ( х1, ... , хs).
3. Представить ДНФ в виде эквивалентной ВНФ. Дать решения задачи в базисных наборах(Ø, ¯)и (¯) :
а) f =`х у z Ú`у Ú`z ;
б) f = х уÚ`х`у Ú у z .
4. Преобразовать КНФ булевых функций в эквивалентные ШНФ с использованием базисных наборов(Ø , | ) и (| ):
а) f = (х Ú у Ú`z)(х Ú`у Ú`z);
б) f = (х Ú у)(у Ú`z)(х Ú`z).
Дата добавления: 2015-10-05; просмотров: 1134;