Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

Теория булевых функций. Булева алгебра.



 Другие рефераты
Дифференцированные уравнения Множество. Алгебра множеств. Определение и способ задания булевых функций Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ

Определение.
Множество M с двумя введенными бинарными операциями (& V), одной унарной
операцией (*) и двумя выделенными элементами называется булевой алгеброй,
если выполнены следующие свойства (аксиомы булевой алгебры). Названия
операций пока не введены.

1. X & Y = Y&X, X V Y = Y V X – коммутативность.
2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.
3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) –
   дистрибутивность.
4. Поглощение – X & X = X, X V X = X.
5. Свойства констант
   X & 0 = 0
   X & I = X, где I – аналог универсального множества.
6. Инвальтивность (X*)* = X
7. Дополнимость X V X* = I, X & X* = 0.
8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Булева алгебра всех подмножеств данного множества.
U = {a1, a2… an)
[U] = N
[P(U)] = 2n

Легко показать, что свойства операций над множествами совпадают со
свойствами (аксиомами) булевой алгебры. То есть, множество P(U) с
операциями объединения, пересечения и дополнения является булевой алгеброй.
Oбъединение эквивалентно V, пересечение - &, дополнение - *, пустое
множество – 0, а универсальное – I.
Все аксиомы булевой алгебры справедливы в операциях над множествами.

                 Булева алгебра характеристических векторов.

Пусть A <= U, A <- P(U) ? - характеристический вектор этого подмножества.

?A = {?1, ?2 ..?n)

n = [P(U)]

?i = 1, если ai <- A (принадлежит).
?i = 0, если ai не принадлежит A.

U = {1 2 3 4 5 6 7 8 9}
A = {2 4 6 8}
B = {1 2 7}
?A = {0 1 0 1 0 1 0 1 0}
?B = {1 1 0 0 0 0 1 0 0}
или
?A = 010101010 – скобки не нужны
?A= 110000100
Характеристические векторы размерностью n называются булевыми векторами.
Они располагаются в вершинах n – мерного булева куба.
Номером булевого вектора является число в двоичном представлении, которым
он является
1101 – номер.
Два булевых вектора называются соседними, если их координаты отличаются
только в одном разряде (если они отличаются только одной координатой).
Совокупность всех булевых векторов размерности n называется булевым кубом
размерностью Bn.

Булев куб размерности 1



Булев куб размерности 2



Булев куб размерности 3



0 – нулевой вектор.
I – вектор из одних единиц.

|XY |X&Y  |X V Y   |
|00 |0    |0       |
|01 |0    |1       |
|10 |0    |1       |
|11 |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}
SB = {1 2 3 4}

Высказывание, для которого множество истинности пусто, называется
тождественно ложным, а для которого 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. Множество классов эквивалентных высказываний.
Три булевых алгебры являются изоморфными, если между их элементами можно
установить такое однозначное соответствие, при котором операции
сохраняются.

Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре
чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения
операций сложения и умножения в алгебре чисел).

скачать работу


 Другие рефераты
Группа сверстников как институт социализации
Древняя цивилизация майя
Сенімхат түсінігі және жасалу тәртібі
Категории земель. Земли поселений


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ