Пятница, 26.04.2024, 22:17
Мультимедийное пособие по дискретной математике
|
Меню сайта
Лекции
Лекции
|
Теория булевых функций. Булева алгебра.Определение.Множество 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) - характеристический вектор этого подмножества. 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.   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). Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.  Л – ложно. И – истинно. Утверждение (основа всей алгебры логики) Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения. Следствие. Множество классов эквивалентных высказываний является булевой алгеброй. Теорема Существуют 3 булевых алгебры: 1. P(U) 2. Bn 3. Множество классов эквивалентных высказываний. Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются. Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел). |
Поиск
Счеткич визитов
Друзья сайта
|