Дзержинский. Дискретная математика
.pdf0 |
0 0 |
|
|
1 1 0 |
|
Дизъюнкция 0 |
1 |
|
1 1 1 |
|
|
|
|
|
(по смыслу – логическое сложение)
|
0 1 1 0 0 |
|
Конъюнкция |
|
|
0 0 0 |
|
|
|
1 1 1 |
|
|
|
|
(По смыслу - логическое умножение)
_
0 1
Отрицание _
1 0
Рассмотрим Bn. Введем в Bn те же операции.
Логической суммой двух булевых векторов называется вектор, полученный покоординатным логическим сложением соответствующих векторов:
= ( 1 , …, n ); =( 1, …, n);
Логическое сложение:
( 1 1 ; 2 2 ; … ; n n ); (5.1)
Логическое умножение:
( 1 1 ; 2 2 ; … ; n n ); (5.2)
Логическое отрицание получается из первоначального покоординатным отрицанием:
=( 1 ; 2 ;…; n ).
Теорема: При таком определении операции булев куб становится булевой алгеброй. При этом роль соответственно нуля и единицы играют вектора
0= (0, …,0); 1= (1, …,1);
Доказательство достигается проверкой всех аксиом булевой алгебры.
2.5Характеристические векторы подмножеств.
Вернемся к
U = { 1 , …, n }; |U| = n
Пусть S U – произвольно, может быть . Сопоставим подмножеству S: αs Bn, где αs- некоторый n-ый вектор по следующему правилу:
13
S = ( 1 , 2 , …, n ),
|
1, |
i |
S; |
|
где i |
|
|
||
= |
|
|
|
|
|
0, i |
S |
|
Тогда вектор αs называется характеристическим для S.
Теорема.
Объединению подмножеств отвечает логическая сумма их характеристических векторов:
S T S T (7.1)
Пересечению отвечает логическое произведение
S T S T (7.2)
дополнению
_
S S (7.3)
соответствует отрицание характеристического вектора. Соответствие между подмножествами и характеристическими векторами взаимно однозначное.
Доказательство.
Покажем верность первого соответствия. Остальные весьма аналогично показываются.
Пусть T ( 1 , 2 ,..., n ) , S ( 1 , 2 ,..., n )
S T ( 1 1 ; 2 2 ; … ; n n ).
Вообще S лежит в этом множестве, если оно лежит либо в S, либо в T, т.е. либо n , либо n равно 1, но это и есть логическая сумма.
Пример. Пусть:
U = { 1 , 2 , 3 , 4 , 5 }, n = 5;
S= { 1 , 3 , 5 }; T = { 2 , 4 };
S = (1, 0, 1, 0, 1); T = (0, 1, 1, 0, 0);
S T = { 1 , 2 , 3 , 5 };S T = (1, 1, 1, 0, 1) ;
ST = { 3 }
S T = (0, 0, 1, 0, 0) ;
_
S = { 2 , 4 };
S = (0, 1, 0, 1, 0)
14
|
~ |
|
Две булевы алгебры M, |
M называются изоморфными, если существует |
|
|
|
~ |
такое взаимнооднозначное соответствие между их элементами |
M M , при |
|
котором дизъюнкция двух |
элементов из М переходит в |
дизъюнкцию |
~
соответствующих элементов из M , конъюнкция в конъюнкцию и обратно, отрицание в отрицание. Т.е. сохраняется соответствие.
a a' |
|
|
||||
|
|
|
||||
b b' |
|
|
||||
a b a'b' |
A |
|||||
|
|
|
||||
a b a'b' |
|
|||||
|
|
|
||||
|
|
|
|
|
|
|
a a' |
|
|
~
A (7.4)
Теорема.
Пусть U – некоторое множество, мощность которого равна |U| = n, (U) – подмножество этого множества, B(U) – булева алгебра высказываний об элементах этого множества и, например, Bn – булев n-ый куб. Имеет место следующий изоморфизм:
(U) B(U) Bn (7.5)
Доказательство.
1.(U) Bn ; U S Bn , что доказано.
2.(U) B(U); SA A (доказано в параграфе алгебре высказываний).
2.6Булевы функции.
Функция от n переменных (x1, …, xn) называется булевой, если областью ее задания является булев куб Bn , а областью значений – булев куб отображение = Bn B1. Другими словами – аргументы x1, …, xn
значения 0 или 1, сама же тоже 0 и 1.
Способы задания булевой функции.
1. Табличный |Bn| = n
При стандартном упорядочении вершин булева куба по двоичная запись которых приведена в строках таблицы, возрастают.
Лексикографический способ.
x1 |
… |
xn-1 |
xn |
|
0 |
… |
0 |
0 |
|
|
|
|
|
|
0 |
… |
0 |
1 |
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
0 |
… |
1 |
0 |
|
|
|
|
|
|
0 |
… |
1 |
1 |
|
|
|
|
|
|
1 |
… |
1 |
1 |
|
|
|
|
|
|
Теорема.
N= 2n различных функций от n-переменных.
Доказательство.
Функцию задает вектор = ( 1, 2,…, n) – N – мерный булев вектор. Всего таких векторов N.
2. Векторный при стандартном употреблении таблицы, т.е. вершин куба, достаточно указать векторные значения 2 ,…, n ) (эквивалентно табличному).
3. Геометрический. Вершина булева куба Bn: =( 1 , 2 ,…, n ); называется единичной (единичным набором), если для (x1, ..., xn):
(x1, ..., xn) = 1
Совокупность вершин единичных наборов для называется носителем функции и обозначается Nf, рис.12. Носитель полностью задает функцию .
Nf := { Bn ( ) = 1} (7.1)
Пример
Nf := { B3 (x1, ..., xn) = (01001100)} |B3| = 23=8
Применяя табличный способ
x1 |
x2 |
x3 |
|
0 |
0 |
0 |
0 |
|
|
|
|
0 |
0 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
0 |
|
|
|
|
0 |
1 |
1 |
0 |
|
|
|
|
1 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
1 |
1 |
0 |
0 |
|
|
|
|
1 |
1 |
1 |
0 |
|
|
|
|
16
Рис.12.
Звездочкой обозначены единичные вершины. Носитель:
Nf : = { B3 (001), (100),(101)}
Булевы функции одного переменного
(x); n=1; 22 = 4.
|
|
|
|
x |
f1 |
|
f2 |
f3 |
f4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
|
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
1 |
0 |
1 |
|
|
_ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f1 (x) 0; |
f2(x) x; |
f3(x) x ; |
f4 (x) 1. |
|
|
|
Булева функция двух переменных. Основные и элементарные функции.
Пусть задана (x1, …, xn). xn называется фиктивным переменным, если его значения не влияют на значение функции:
(x1, …, xn-1, 0) = ( x1, …, xn-1, 1); ( x1, xn-1). (8.1)
Понятие фиктивного переменного позволяет функцию от (n – 1) переменного рассматривать как функцию от n переменных. В частности, (x) входит в перечень функций от x переменных (которыми и задается).
|
(x) (x1, x2). |
|
|
|
|
|
|
|
|
|
||
|
( x1, x2); n = 2; 222 |
= 16. |
|
|
|
|
|
|
|
|||
|
Из них 4 функции одного переменного, а 12 функций существенно |
|||||||||||
зависят от двух переменных. |
|
|
|
|
|
|
|
|||||
|
Приведем таблицы для некоторых из них. |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
Таблица 4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
x2 |
x1& x2 |
x1 x2 |
x1 x2 |
|
x1 x2 |
x1 x2 |
x1 x2 |
x1 x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
|
0 |
1 |
|
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
1 |
|
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
|
1 |
0 |
|
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
1 |
1 |
|
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
В заголовке таблицы, слева направо следуют соответственно уже знакомые нам ранее конъюнкция, дизъюнкция, импликация, сложение по модулю два (остаток деления суммы на два) и новые – эквиваленция, штрих Шеффера (отрицание конъюнкции), стрелка Пирса (отрицание дизъюнкции). Основными функциями называются:
_
(x) = x ; ( x1 x2) = x1& x2; ( x1 x2) = x1 x2.
Другими словами новые функции через основные:
x1 x2 = |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
x1 & x2 ; (8.2) |
||||||||||||
x1 x2 |
|
|
|
|
|
|
|
|
|
|
|
||||
= x1 x2 ; (8.3) |
|||||||||||||||
x1 x2 = |
|
|
|
|
|
|
x2; (8.4) |
||||||||
|
x1 |
x2 |
|||||||||||||
x1 x2 = |
|
x2 |
x1 |
|
; (8.5) |
||||||||||
x1 |
x2 |
||||||||||||||
x1 x2 |
|
|
|
|
x2. (8.6) |
||||||||||
= x1 |
|
Элементарными функциями называются все основные функции и еще: , , ,
, .
Теорема.
Множество всех булевых функций является булевой алгеброй, если рассматривать следующие операции над функциями: , , &. Роль элемента 0 играет (x) 0, а роль элемента I (x) 1.
Доказательство.
Достигается путем проверки аксиом для каждой из функций. К примеру – коммутативность:
x1 & x2 = x2 & x1
x1 x2 = x2 x1 и т.д. x1 x2 = x =1
x1^ x =0 x1 ^ x2 = x1 x2 x1 x2 = x1 ^ x2
2.7Дизъюнктивные нормальные формы (ДНФ).
Рассмотрим функцию из n переменных (x1, …, xn).
1. Элементарной конъюнкцией называется произведение каких-либо из этих переменных или их отрицаний, причем каждая переменная входит не более
18
одного раза.
2. ДНФ – логическая сумма (дизъюнкция) элементарных конъюнкций, в которую каждая конъюнкция входит не более одного раза. Заметим, что две разные по записи ДНФ могут задавать одну и ту же булеву функцию.
Пример: x1 & x2
D1 = x1;
D2 = x1 x2 x1 x2 = x1(x2 x2 ) = x1 I = x1; D1 = D1 .
3.Элементарная конъюнкция называется полной, если она состоит из n сомножителей (если каждая переменная, либо ее отрицание входит в число сомножителей).
4.Совершенная ДНФ (СДНФ) – такая ДНФ, слагаемые которой являются полными конъюнкциями.
Теорема.
Если (x1, …, xn) 0, то ее можно представить единственным образом в виде СДНФ. Введем обозначение.
|
|
|
α |
def |
|
|
|
1; |
1; |
|
|
|
|
|||||
|
|
x |
|
, если |
|
|
(9.1) |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
, если |
|
0; 0 . |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
00= 1; 01= 0; 10= 1; 11= 1; = 1. |
|
|
|
|||||||||||||
Доказательство. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. Докажем, что СДНФ для . Пусть задано таблично: |
||||||||||||||||||
|
x1 |
… |
|
|
|
xn |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
0 |
… |
|
0 |
|
|
1 |
|
|
|
|
|
|||||||
0 |
… |
|
1 |
|
|
2 |
|
|
|
|
|
|||||||
|
G1 |
… |
|
|
|
Gn |
|
|
1 |
|
|
|
|
N = 2n |
|
|||
|
……………………………… |
|
|
|
|
|
|
|
|
|
|
|
||||||
1 |
… |
|
1 |
|
|
xn |
|
Nf = ? |
|
|||||||||
Nf; Каждому набору из носителя = () |
N↓ сопоставим полную |
|||||||||||||||||
конъюнкцию K = xG1 |
… xGn . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
1 |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим новую g(x , …, x |
) = xx |
xG1 |
… xGn |
(x |
, …, x |
n |
N |
) |
||||||||||
|
|
1 |
|
n |
|
|
|
1 |
|
|
n |
1 |
|
f |
|
xx – сумма по всем носителям.
В этой сумме столько слагаемых, сколько единичных наборов в Nf. Заметим, что g есть СДНФ.
Покажем, что (x1, …, xn) = g(x1, …, xn). Для этого докажем, что у них один и тот же Nf .
19
а) Пусть ' = ( 1 , 2 …, n ) Nf |
, т.е. |
|
|
|
|
|
|
|
( 1 , 2 …, n ) = 1, |
|
|
||||
тогда, что и покажем, |
|
|
|
|
|
|
|
|
|
|
g( ' ) = 1 |
|
|
||
Это значит, что среди слагаемых g есть слагаемое: |
|
|
|||||
g(x , …, x |
) = x 1 |
… x n … (9.2) |
|
||||
1 |
n |
|
1 |
|
n |
|
|
|
1 |
|
n |
… = 1 1 |
1 |
… |
|
g( 1 , 2 …, n ) = 1 |
|
… n |
|||||
= 1 ( 1 , 2 |
…, n ) Ng (9.3), |
|
т.е. всякий набор из Nf лежит в Ng. б) Пусть ( 1 , 2 …, n ) Ng, т.е.
g( 1 , 2 …, n ) = 1 в сумме g есть слагаемые, равные 1, т.е. слагаемые, вида: … n n = 1 = 1, i z n, (9.4)
т.е. набор ( 1 , 2 …, n ) Nf .
Из а) и б) следует, что Ng = Nf g.
2. Единственность СДНФ для булевой функции:
Итак, если (x1, …, xn) 0, то она может быть единственным образом представлена в виде совершенной ДНФ. Подсчитаем, сколько можно составить разных СДНФ для n переменных:
а) сколько имеется полных конъюнкций: x1 & x2 & … & xn n = N – полных конъюнкций.
б) сколько имеется СДНФ?
K1,K2,..,KN. Брать или нет – две возможности N возможности, но, однако, нельзя взять СДНФ из ни одной K, т.е. вариант 00…0 вылетает, и всего N - 1 возможность.
Поскольку из п. 1 следует, что каждой ненулевой булевой функции отвечает хоть одна СДНФ, а из п. 2 следует, что их не может быть больше одной, то, значит, соответствие однозначное.
Пример.
= (0110); g = (1001), функция
h (x1, x2, x3) = (g(x1, x3), x2)
Найти СДНФ для функции h.
Найдем таблицы для и g, а затем для h.
20
|
|
|
|
|
|
|
|
|
|
Таблица 4. |
|
|
|
|
|
g |
|
|
|
|
|
h |
|
|
|
|
|
|
|
|
|
|
|
|
|
B2{ |
0 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
{ |
0 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
||
|
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
B3 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
|
||
|
|
|
|
|
|
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
|
h (0, 0, 0) = (g(0, 0), 0) = (1, 0) = 1; h (0, 0, 1) = (g(0, 1), 0) = (0, 0) = 0;
h (1, 1, 0) = (g(1, 0), 1) = (0, 1) = 1 и т.д. h (0, 0, 1) = (0, 1) = 1;
h (1, 1, 1) = (g(1, 1), 1) = (1, 1) = 0.
В СДНФ выйдет столько слагаемых, сколько единичных вершин.
h (x1, x2, x3)= x1 x2 x3 x1 x2 x3 x1 x2 x3 (9.5)
Проверим, что эти функции равны, т.е. у них общие носители: h (0, 0, 0) = 1 1
h (0, 1, 1) = 1 1 и т.д. на всех вершинах h 1 и сумма 1.
Может правая часть 1 в других точках, в других вершинах? Тогда правая часть отличается от функции h. Легко видно, что каждое слагаемое равно 1 только в одной вершине лишних вершин нет.
2.8Методы приведения функции к совершенной ДНФ.
Даны булевы f1(x1,…,xn), g1 (x1,…,xk1), g2(x1,…,xk2), …, gn(x1,…,xn)
Суперпозицией этих функций называется: следующая функция
= f1 (g1 , g2 , …, gn ). (13.1)
Формулой называется булева функция, которая может быть получена из элементарных булевых функций с помощью одной или нескольких суперпозиций.
, &, , , , , , – основные.
1.Если ( x1,…,xn) заданы в табличной форме, то ее можно привести к СДНФ, как указано в доказательстве теории об СДНФ и в примере.
2.– представлена формулой. Для приведения СДНФ нужно:
21
а) все элементарные функции выразить через основные; x1 x2 x1 x2 = x1 x2 x1 x2 (13.2)
– двоичное сложение, остаток от деления обычной суммы на 2; логически это
разделительное «или»: или x1 = 1 и x2 = 0 или x1 |
= 0, x2 |
= 1; |
||||||
x1 x2 = |
|
x2(13.3) |
|
|||||
x1 |
|
|||||||
– импликация – логическое следование тогда, |
когда |
– ложь; либо – |
||||||
истина; |
|
|
|
|
|
|
|
|
= |
|
|
|
|
(13.4) |
|
||
– эквиваленция – равна единице, когда |
= 1 и = 1, либо = = 0; |
|||||||
= |
|
|
|
|
; (13.5) |
|
||
|
= |
|
|
|
|
|||
|
x1 x2 |
. (13.6) |
|
|||||
б) с помощью законов двойственности де Моргана все отрицания |
||||||||
опустить на сами переменные |
|
|
|
|
|
|
|
|
Пример. |
|
|
|
|
|
|
|
|
|
|
= |
|
; (13.7) |
|
|||
|
|
|
|
|
||||
|
1 2 |
= |
& . (13.8) |
|
||||
в) с помощью первого закона дистрибутивности раскрыть все скобки в |
||||||||
полученной формуле и убрать повторение слагаемых, если оно есть. |
||||||||
( ) |
= |
|
|
(13.9) |
Теперь получим просто ДНФ г) неполные конъюнкции полученных ДНФ дополняются до полных
конъюнкций:
k – некоторая конъюнкция (к примеру, не содержит x1). Тогда: k = k I=k () = k k
Из полученной суммы убирают лишние слагаемые, получается СДНФ.
Пример.
(x, y) = (x y) (x ) (13.10).
Привести данную формулу к СДНФ.
(x, y) = (x y) (x y) = ( ) ( ) = ( ( ) (13.10)
Пусть (x, y) = a, тогда:
( ) ( ) = a a = a (x, y) = & = () & () = = ( y) & (x ) = x yx y = xy (СДНФ). (13.11)
СДНФ единственная для только в том случае, когда фиксировано количество переменных n. С вводом новых фиктивных переменных СДНФ будет меняться.
22