Что такое творческие
кладовые по дискретной математике
портала "Русский след"?
14.Булевы функции и формы их представления.
Определение.
Множество M с
двумя введенными бинарными операциями (Ù
- конъюнкцией
, Ú
- дизъюнкцией),
одной унарной операцией
(* - отрицанием. которая обозначается ли бо
звёздочкой, либо чертой над элементом или выражением, или знаком минус перед
рассматриваемым элементом) и двумя выделенными элементами называется
булевой алгеброй, если выполнены следующие
свойства (аксиомы булевой
алгебры).
1. X Ù Y = YÙX, X Ú Y = Y Ú X – коммутативность.
2. (X Ù Y) Ù Z = X Ù (Y Ù Z), (X Ú Y) Ú Z = X Ú (Y Ú Z) – ассоциативность.
3. (X Ú Y) Ù Z = (X Ù Z) Ú (Y Ù Z), (X Ù Y) Ú (Y Ù Z) = (X Ú Z) Ù (Y Ù Z) – дистрибутивность.
4. Поглощение – X Ù X = X, X Ú X = X.
5. Свойства констант
X Ù 0 = 0
X Ù I = X, где I – аналог универсального множества.
6. Инвальтивность (двойное отрицание) (X*)* = X
7. Дополнимость X Ú X* = I, X Ù X* = 0.
8. Законы двойственности(законы де Моргана): (X Ù Y)* = X* Ú Y*, (X Ú Y)* = X* Ù Y*
Булева алгебра 2n всех подмножеств данного множества.
U = {a1, a2… an}
[U] = N - мощность U
[P(U)] = 2n - мощность подмножеств P множества U
Легко показать, что свойства операций над множествами совпадают со свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с операциями объединения, пересечения и дополнения является булевой алгеброй.
Oбъединение эквивалентно Ú, пересечение - Ù дополнение - *, пустое множество – 0, а универсальное – I.
Все аксиомы булевой алгебры справедливы в операциях над множествами.
Различные определения булевой алгебры, включают: булевы алгебры - это частично- упорядоченные множества специального типа: булева алгебра = эт о алгебраическая система, которая в зависимости от обстоятельств может бвть интерпретирована либо как система событий, либо как система высказываний, либо как дистрибутивная структура , то есть структура с двумя операциями, с неравными друг другу единицей (1) и нулём (0), в которой всякий элемент имеет дополнение
Формы представления булевой алгебры включают формы характеристических вектороы, формы высказываний, формы иножеств.
Булева алгебра характеристических векторов.
Пусть A £ U, A < - P(U) a - характеристический вектор этого подмножества.
aA = {a, a2 ..an)
n = [P(U)]
ai = 1, если ai <- A (принадлежит).
ai = 0, если ai не принадлежит A.
U = {1 2 3 4 5 6 7 8 9}
A = {2 4 6 8}
B = {1 2 7}
aA = {0 1 0 1 0 1 0 1 0}
aB = {1 1 0 0 0 0 1 0 0}
или
aA = 010101010 – скобки не нужны
aA= 110000100
Характеристические векторы размерностью n называются булевыми векторами.
Они располагаются в вершинах n – мерного булева куба.
Номером булевого вектора является число в двоичном представлении, которым он является
1101 – номер.
Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (если они отличаются только одной координатой).
Совокупность всех булевых векторов размерности n называется булевым кубом размерностью Bn.
Булев куб размерности 1
Булев куб размерности 2
Булев куб размерности 3
0 – нулевой вектор.
I – вектор из одних единиц.|
X |
Y |
X ÙY - конъюнкция(логическое умножение) |
X Ú Y -дизъюнкция (логическое сложение) |
|
0 |
0 |
0 |
0 |
| 0 |
1 |
0 |
1 |
| 1 |
0 |
0 |
1 |
| 1 |
1 |
1 |
1 |
Отрицание
X = 0 Y = 0
_
_
Х = 1 Y= 1
Для размерности n операции над векторами производятся покоординатно.
Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.
Между множеством всех подмножеств множества U и булевым кубом Bn, где n= =[U] можно установить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.
Множество всех характеристических векторов является булевой алгеброй.
Булева алгебра высказываний (алгебра логики)
Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно.
U = {1 2 3 4 5 6 7 8 9}
A = «число четное»
B = «число, меньшее пяти»
Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.
SA = {2 4 6 8} , где SA - подмножество высказывания А на множестве U
SB = {1 2 3 4} , где SB - подмножество высказывания B на множестве U
Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным.
Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными.
Равносильные высказывания объединим в один класс Р.В. и не будем их разделять, т.к. все они имеют одно и то же множество истинности.
Операции над высказываниями
Дизъюнкция высказываний (V, ИЛИ, OR)
Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний.
Конъюнкция высказываний (&, И, AND).
Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания.
Отрицание высказываний (- над буквой, НЕ, NOT).
Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.
|
A B |
A & B |
A V B |
Not A |
|
Л Л |
Л |
Л |
И |
|
Л И |
Л |
И |
И |
|
И Л |
Л |
И |
Л |
|
И И |
И |
И |
Л |
Л – ложно.
И – истинно.
Утверждение (основа всей алгебры логики)
Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения.
Следствие. Множество классов эквивалентных высказываний является булевой алгеброй.
Теорема
Существуют 3 булевых алгебры:
1. P(U)
2. Bn
3. Множество классов эквивалентных высказываний.
Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.
Следует заметить , что часто конъюнкцию обозначають точкой (как знак умножения в алгебре чисел), причём. конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).