Формы булевых функций

Лекция 10

Формы булевых функций.

Булевой функцией называется двоичная функция двоичных переменных. Любая логическая формула есть булева функция. Они определены на множестве вершин n-мерного куба.

Назовем знаком отдельную букву или букву с отрицанием.

Формы записи булевых функций.

1. Элементарное произведение – произведение, в котором каждый сомножитель есть знак.
2. Элементарная сумма – сумма, в которой каждое слагаемое есть знак.
3. Дизъюнктивная нормальная форма (ДНФ) – сумма элементарных произведений.
4. Конъюнктивная нормальная форма (КНФ) – произведение элементарных сумм.
5. Совершенное произведение:

• содержит точно n знаков;
• содержит все n переменных;
• нет одинаковых переменных.

1. Совершенная сумма:

• содержит точно n знаков;
• содержит все n переменных;
• нет одинаковых переменных.

1. Совершенная дизъюнктивная нормальная форма (СДНФ) – сумма совершенных произведений.
2. Совершенная конъюнктивная нормальная форма (СКНФ) – произведение совершенных сумм.

Чтобы привести функцию к СДНФ или СКНФ, её сначала упрощают, а затем преобразуют, используя следующие законы:

а*1=а; а+0=а; 1=а+¬а; 0=а*¬а.

Если F=1, то она не имеет СКНФ, а в СДНФ содержится 2n членов.

Если F=0, то она не имеет СДНФ, а в СКНФ содержится 2n членов.

Аналитическая запись булевой функции.

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

Собственной вершиной совершенного произведения называется такая вершина n-мерного куба, координаты которой получены из записи самого совершенного произведения заменой буквы единицей, а буквы с чертой нулем.

Собственной вершиной совершенной суммы называется такая вершина n-мерного куба, координаты которой получены из записи самой совершенной суммы заменой буквы нулем, а буквы с чертой единицей.

Пример:         P=x*¬y*z        (1,0,1)

                S=x+¬y+z        (0,1,0)

Совершенное произведение в своей собственной вершине =1.

Совершенная сумма в своей собственной вершине =0.

Зная таблицу истинности функции, можно составить её аналитическую формулу, используя совершенные произведения, если в таблице меньше единиц, либо совершенные суммы, если в таблице меньше нулей.

F=P1+P2+…+Pk (СДНФ), где Pi – соответствующие единицам совершенные произведения.

F+S1*S2*…*Sm (СКНФ), где Sj – соответствующие нулям совершенные суммы.

Пример: Дана логическая формула. Упростить формулу, привести ее к СДНФ, СКНФ; построить таблицу истинности для исходной логической формулы, по таблице истинности написать СДНФ, СКНФ; решить логическое уравнение.

F= ¬(x*y⬄z*y)+x*¬z+¬(y*z)

1. Упростим формулу:

F= ¬(xy ⬄ yz) + x*¬z + ¬(yz) = (xy)* ¬(yz) + ¬(xy)*(yz) + x*¬z + ¬y + ¬z = xy*(¬y + ¬z) + (¬x + ¬y)*(yz) + x*¬z + ¬y + ¬z = xy¬y + xy¬z + ¬xyz + ¬yyz + ¬z + ¬y =

                                             =0                           =0

= xy¬z + ¬xyz + ¬z + ¬y = ¬xyz + ¬z + ¬y = (¬z + z)( ¬z + ¬xy) + ¬y = ¬z + ¬xy + ¬y = ¬z + (¬y + y)( ¬y + ¬x) = ¬x + ¬y + ¬z;