Конституенты единицы. Совершенные дизъюнктивные и веббовы нормальные формы

Определение. Пусть функция f(х ⁿ)на наборе`a <sup>n</sup> = (a<sub>1</sub>, ..., a<sub>n</sub>) равна 1. Конъюнктивной конституентой единицы функции f на наборе `a ⁿ назовем конъюнкцию К = х₁^a1& ... & х_n^an, где х_i^{a i}= х_i при a_i =1 и х_i^{a i} = `х_i при a_i = 0(i=1,…,n).

Аналогично веббовой конституентой единицы функции f назовем подстановку вида V = ¯ (х₁^Øa1 , . . . , х_n^Øan).

И конъюнктивная и веббова конституенты единицы, соответствующие набору`a ⁿ, принимают значение 1 только на нем. На всех остальных наборах они равны 0.

Пример 1. Построить все конъюнктивные и веббовы конституенты единицы функции F, заданной таблицей истинности.

Решение.

Функция принимает значение 1 на наборах (0, 0, 1), (0, 1, 1), (1, 1, 0). На наборе (0,0,1) конъюнктивная конституента единицы К₁ = `х`у z , на наборе(0, 1, 1) К₂ =`х у z , на наборе(1, 1, 0) К<sub>3</sub> = х у`z . В таблице истинности даны векторы истинности конституент К₁— К₃. Они показывают назначение конституент — выделение одной из единиц в векторе истинности исходной функции.

Веббовы конституенты получаем из К₁— К₃с использованием двух преобразований: 1) инвертирования внутренних переменных в коньюнкциях и 2) замены конъюнкции функцией Вебба. В итоге получим все веббовы конституенты единицы функции F: V₁=¯(х, у,`z); V<sub>2</sub> =¯(х,`у,`z); V<sub>3</sub> =¯(х,` у, z).

Векторы истинности конституент V₁— V₃совпадают с векторами истинности К₁— К₃.

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

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

где К₁ , ... , К_р — все конъюнктивные конституенты единицы функции f (х ⁿ).

Совершенной веббовой нормальной формой (СВНФ) булевой функции f (х ⁿ)называют выражение вида:

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

где V₁, ..., V_р — веббовы конституенты единицы функции f(х ⁿ).

СДНФ (как и все ДНФ) задают формульные выражения булевых функций в базисном наборе {Ø, &, Ú}. СВНФ задает выражение функций в базисном наборе {Ø, ¯}. Так как Ø (х) = ¯(х, х), то данную формулу всегда можно представить в однофункциональном наборе {¯}.

Пример 2. Построить СДНФ и СВНФ ( с использованием наборов {Ø, ¯} и {¯}) функции f =(01010010) из Примера 1.

Решение.

1. Конъюнктивные конституенты единицы функции К₁ — К₃ построены в Примере 1. СДНФ получаем, логически складывая их:

f =`x`y z Ú`x y z Ú x y`z = Ú (`x `y z ,`x y z, x y`z).

2. Веббовы конституенты единицы функции V₁— V₃также берём из Примера 1. СВНФ в базисном наборе {Ø, ¯}получаем, подставляя V₁— V₃в функцию Вебба и инвертируя её:

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.

Как и все ДНФ и ВНФ, их совершенные виды существуют только для функций, не равных тождественному нулю. В том случае, когда вектор истинности функции имеет только одну единицу, ее СДНФ и СВНФ являются вырожденными, т.е. состоят только из одной конституенты.