lec03
.pdf
Часть 2.
СДНФ.
Суперпозиция БФ.
Даны произвольная булева функция f (x1,x2, … xi … xn) и система БФ
G = { g1(y1,y2, … yn), g2(y1,y2, … yn), … gi(y1,y2, … yn) … gn(y1,y2, … yn) }
Элементарная суперпозиция – подстановка какой-то gi(y1,y2, … yn) в БФ f вместо аргумента xi.
Суперпозицией этих функций называется F полученная путем последовательного применения конечного числа подстановок gi (всех
F(x1,x2, … xn) = f (g1,g2 , …, gn). |
(3.4) |
22
Суперпозиция БФ (замечания).
Приведен случай, когда размерности f и gi совпадают.
Предположение о том, что размерности f и для всех функции gi совпадают не ограничивает общности, поскольку, любое G всегда можно рассматривать как множество БФ от одного и того же числа переменных. Т.е. можно уравнять арность gi добавлением фuктивных переменных. Т.к. это можно осуществлять разными способами, то суперпозиция
f (g1, ... , gn) определена однозначно лишь с точностью до равенства булевых функций.
В общем случае, когда gi имеет размерность mi, и нет эквивалентности аргументов, то суперпозиция F может иметь арность от n до
m
=1 |
23 |
|
Суперпозиция. Примеры.
Пример 3.4.
Пусть f (x1,x2) = x1 x2, g1(y1,y2) = y1 y2.
Суперпозиция:
F(y1,y2,x2) = f (g1(y1,y2),x2) = (y1 y2) x2 = y1 y2 x2
Пример 3.5.
Пусть f (x1,x2) = x1 x2,
g1(y1,y2) = y1 y2; g2(y1,y3) = y1 y3.
Суперпозиция:
F(y1,y2,y3) = f (g1(y1 y2),g2(y1,y3)) = (y1 y2) & (y1 y3).
24
Формулой называется булева функция, которая может быть получена из элементарных булевых функций с помощью одной или нескольких суперпозиций.
Элементарные функции: константы, тождество основные функции - ( , и) а также , , , ,
25
Методы приведения БФ к СДНФ.
1) Если (x1x2, … xn) задана в табличной форме, то ее можно привести к СДНФ в соответствии с теоремой 3.1.
Конструктивное построение в примерах 3.2 и 3.3.
2) Если (x1,x2, … xn) представлена формулой, тогда следующие этапы:
а) все элементарные функции выразить через основные:
1 2 = 1 2 1 2;1 2 = 1 2;1 2 = 1 2 1 2;1 2 = 1 2;
1 2 = 1 2.
26
Методы приведения БФ к СДНФ.
б) с помощью законов двойственности де Моргана все отрицания опустить на сами переменные
1 2 = 1 2;1 2 = 1 2.
в) с помощью первого закона дистрибутивности раскрыть все скобки в полученной формуле и убрать повторение слагаемых, если оно есть.
( 1 2) 3 = 1 3 2 3
Получена ДНФ!
г) неполные конъюнкции полученных ДНФ дополняются до полных конъюнкций: k – некоторая конъюнкция (к примеру, не содержит 1). Тогда:
k = k I = k ( 1 1) = k 1 k 1
Убрав лишние слагаемые, получается СДНФ. |
27 |
|
Пример 3.6а. Приведение БФ к СДНФ равносильными преобразованиями.
(x,y,z) = x (yz xy) A ≡ x (yz xy)
A ≡ x (yz xy) = x ( xy) = x ( xy) = = x x xxy = x x xy ≡ ДНФ (A)
A ≡ ДНФ (A) ≡ x (z ) x (y ) xy(z ) =
=x x x x xyz xy =
=x x x xyz ≡ СДНФ (A)
СДНФ (А) ≡ x x x
28
Пример 3.6б. Приведение БФ к СДНФ, получив коэффициенты разложения по переменным
Процедура эквивалентна получению характеристического вектора.
(x,y,z) = x (yz xy)
Таблица истинности:
|
|
|
|
|
|
|
|
x |
y |
z |
yz |
xy |
yz xy |
f |
конъюнкты |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
x |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
x |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
x |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
СДНФ (А) ≡ x x x
29
Пример 3.6в. Приведение БФ к СКНФ равносильными преобразованиями
(x y,z) = x (yz xy) |
A ≡ x (yz xy) |
|
A ≡ x x xy |
|
A ≡ x ( y) ≡ x 1 ≡ x. |
|
Т.е. КНФ (А) ≡ x |
А ≡ КНФ (А) ≡ x = x (y ) = (x y) (x ) =
=[(x y) (x )] (z ) =
=[(x y) (z )] [(x ) (z ) ] =
≡ x y z x y (x z) (x )
СКНФ (А) ≡ x y z x y (x z) (x )
30