lec02
.pdfПример 2.1. Эквивалентность операций над подмножествами и их характеристическими векторами.
Пусть:
U = {α1, α2, α3, α4, α5}, n = 5; S = {α1, α3, α5}; T = {α2, α3};
α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); |
S T = {α3}; |
αS∩T = (0, 0, 1, 0, 0); |
S = {α2, α4}; |
αS = (0, 1, 0, 1, 0) |
21
Изоморфизм булевых алгебр.
Две булевы алгебры M, M называются изоморфными, если существует такое взаимнооднозначное соответствие (биективное отображение) между их элементами M M, при котором дизъюнкция двух элементов из М переходит в дизъюнкцию соответствующих элементов из M и обратно, конъюнкция в конъюнкцию, отрицание в отрицание. Т.е. сохраняется соответствие.
↔ ′
↔ ′ |
A A |
↔ ′ ′ |
|
↔ ′ ′ |
|
↔ ′ |
|
22
Теорема о взаимосвязи множества-степени, БА и Вn
Пусть U – некоторое множество, мощность которого равна |U| = n, P(U) – подмножества этого множества, B(U) – булева алгебра высказываний об элементах этого множества и, например, Вn – булев n-мерный куб.
Теорема 2.4. Имеет место следующий изоморфизм:
P(U) B(U) Вn
Доказательство:
P(U) Вn;
U S Вn,
(Теорема 2.3 о взаимно однозначном соответствии между подмножествами и характеристическими векторами).
P(U) B(U);
SA A
(Теорема 1.2 о том, что алгебра высказываний – БА).
Часть 4.
Булевы функции. Способы задания булевой функции.
Булевы функции.
Функция от n переменных (x1, … xn) называется булевой, если областью ее задания является булев куб Вn, а областью значений – булев куб В1.
задает отображение : Вn В1.
Аргументы x1, … xn принимают значения 0 или 1, сама же тоже принимает значения 0 и 1.
25
Способы задания булевой функции: табличный (лексикографический).
При стандартном |
|
x1 |
x2 |
… |
xi |
… |
xn |
|
|
|
0 |
0 |
… |
0 |
… |
0 |
α1 |
||
упорядочении вершин булева |
|
||||||||
куба по n, числа, двоичная |
|
0 |
0 |
… |
0 |
… |
1 |
α2 |
|
запись которых приведена в |
N |
… |
… … … |
… |
… |
… |
|||
строках таблицы, возрастают. |
|||||||||
|
|
|
|
|
|
|
|||
0 |
0 |
… |
1 |
… |
0 |
αi |
|||
|
|
||||||||
N = 2n |
|
… |
… |
… … … |
… |
… |
|||
|
|
1 |
1 |
… |
1 |
… |
1 |
αN |
26
Способы задания булевой функции: векторный.
При стандартном употреблении таблицы, т.е. вершин куба Вn, достаточно указать векторные значения
(α1, α2, … αi, … αN)
(эквивалентно табличному). N = 2n
f = (α1, α2, … αi, … αN)
27
Способы задания булевой функции: геометрический.
Вершина булева куба Вn: = (α1, α2, … αi, … αN); называется единичной (единичным набором), если для (x1, x2, … xi, … xn):
(x1, x2, … xi, … xn) = 1
Совокупность вершин единичных наборов для называется носителем функции и обозначается Nf. Носитель полностью задает функцию .
Nf := { Вn ( ) = 1}
28
Теорема 2.5. (о числе булевых функций от n-переменных).22n различных булевых функций от n-переменных.
Доказательство:
Булеву функцию (размерности n) задает вектор
= ( 1, 2,… i, … N) – N–мерный булев вектор (N=2n).
Всего таких векторов N. i 10 , т.е. может принимать 2 значения
{( 1, 2,… i, … N) | i=0 или i=1} = 2n
Если интерпретировать количеством носителей Nf, то все единичные наборы для образуют P( ) (множество степень , т.е. множество всех подмножеств для ) для которого
P( ) = 2|γ| = 22n
При n≤2 это обозримое число, поэтому все БФ интуитивно понятны и их
можно просто перечислить. |
29 |
|
Пример. 2.2. Способы задания булевой функции: ТИ.
В3. Размерность n=3.
(x1,x2,x3) задается вектором = ( 1, 2,… N). N = 2n = 23 = 8
= (01001100)
x1 |
x2 x3 |
(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 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
30 |
|
|
|
|