Конституенты единицы. Совершенные дизъюнктивные и веббовы нормальные формы
Определение. Пусть функция f(х n)на наборе`a n = (a1, ..., an) равна 1. Конъюнктивной конституентой единицы функции f на наборе `a n назовем конъюнкцию К = х1a1& ... & хnan, где хia i= хi при ai =1 и хia i = `хi при ai = 0(i=1,…,n).
Аналогично веббовой конституентой единицы функции f назовем подстановку вида V = ¯ (х1Øa1 , . . . , хnØan).
И конъюнктивная и веббова конституенты единицы, соответствующие набору`a n, принимают значение 1 только на нем. На всех остальных наборах они равны 0.
Пример 1. Построить все конъюнктивные и веббовы конституенты единицы функции F, заданной таблицей истинности.
x | y | z | F | К1 | К2 | К3 |
Решение.
Функция принимает значение 1 на наборах (0, 0, 1), (0, 1, 1), (1, 1, 0). На наборе (0,0,1) конъюнктивная конституента единицы К1 = `х`у z , на наборе(0, 1, 1) К2 =`х у z , на наборе(1, 1, 0) К3 = х у`z . В таблице истинности даны векторы истинности конституент К1— К3. Они показывают назначение конституент — выделение одной из единиц в векторе истинности исходной функции.
Веббовы конституенты получаем из К1— К3с использованием двух преобразований: 1) инвертирования внутренних переменных в коньюнкциях и 2) замены конъюнкции функцией Вебба. В итоге получим все веббовы конституенты единицы функции F: V1=¯(х, у,`z); V2 =¯(х,`у,`z); V3 =¯(х,` у, z).
Векторы истинности конституент V1— V3совпадают с векторами истинности К1— К3.
Определение. Совершенной дизъюнктивной нормальной формой (СДНФ) булевой функции f (х n)называют выражение вида:
f = К1Ú ... Ú Кр ,
где К1 , ... , Кр — все конъюнктивные конституенты единицы функции f (х n).
Совершенной веббовой нормальной формой (СВНФ) булевой функции f (х n)называют выражение вида:
f = Ø ¯ ( V 1, ... , V р ),
где V1, ..., Vр — веббовы конституенты единицы функции f(х n).
СДНФ (как и все ДНФ) задают формульные выражения булевых функций в базисном наборе {Ø, &, Ú}. СВНФ задает выражение функций в базисном наборе {Ø, ¯}. Так как Ø (х) = ¯(х, х), то данную формулу всегда можно представить в однофункциональном наборе {¯}.
Пример 2. Построить СДНФ и СВНФ ( с использованием наборов {Ø, ¯} и {¯}) функции f =(01010010) из Примера 1.
Решение.
1. Конъюнктивные конституенты единицы функции К1 — К3 построены в Примере 1. СДНФ получаем, логически складывая их:
f =`x`y z Ú`x y z Ú x y`z = Ú (`x `y z ,`x y z, x y`z).
2. Веббовы конституенты единицы функции V1— V3также берём из Примера 1. СВНФ в базисном наборе {Ø, ¯}получаем, подставляя V1— V3в функцию Вебба и инвертируя её:
f =د (¯ (x, y,`z),¯ (x,`y,`z),¯ (x,`y, z)) .
СВНФ в базисном наборе {¯}имеет вид:
f = ¯[¯(¯(x, y, ¯(z, z)),¯(x, ¯(у, y), ¯(z, z)), ¯(¯(х, x),¯(у, y), z)),
¯ (¯(x, y,¯(z, z)),¯(x,¯(у, y),¯(z, z)),¯(¯(х, x),¯(у, y),z))].
Три полученных формульных выражения дают искомое решение задачи для булевой функции из примера 1.
Как и все ДНФ и ВНФ, их совершенные виды существуют только для функций, не равных тождественному нулю. В том случае, когда вектор истинности функции имеет только одну единицу, ее СДНФ и СВНФ являются вырожденными, т.е. состоят только из одной конституенты.
Дата добавления: 2020-10-14; просмотров: 584;