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

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

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


 Другие рефераты
Личность и культура
Творческое воображение и фантазия
Война 1812 года в истории народов России
Психологическая характеристика причин семейных конфликтов


 

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

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


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