Булева алгебра всех подмножеств данного множества

Основные понятия математической логики

Основные законы логики. Таблицы истинности

Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности и ложности) и логических операций над ними [4].

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно [4].

Для обозначения истины (истинного высказывания) используется символ 1, а для обозначения лжи (ложного высказывания) используется символ 0.

Рассмотрим примеры логических высказываний (см. Таблицу 1):

Таблица 1. Примеры логических выражений

Предложение	Характеристика с точки зрения алгебры логики
Иваново – Родина Первого Совета	Истинное логическое высказывание
За зимой наступит весна	Истинное логическое высказывание
В городе Иваново проживают только граждане России	Ложное логическое высказывание
После дождя всегда тепло	Ложное логическое высказывание
После вторника будет выходной	Не является логическим высказыванием, т.к. не известно, о каком человеке, каком месяце и дне идет речь (если у человека текущий график работы, возможно, что у него в среду будет выходной, в противном случае среда – рабочий день; если в среду будет праздничный день, например, 8 марта, то этот день также будет выходным)

Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить более сложные высказывания. Такие слова и словосочетания называют логическими связками. Высказывания, образованные с помощью логических связок – называют составными высказываниями. Высказывания, не являющиеся составными, называют элементарными.

Для обозначения логических высказываний, им назначают имена. Например, если А – высказывание «В четверг был дождь», В – высказывание «В пятницу было солнечно», то составное высказывание «В четверг был дождь, а в пятницу было солнечно», можно записать в виде: А и В.

Здесь А, В – логические высказывания (могут быть либо истинными, либо ложными), и – логическая связка.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (см. Таблицу 2):

Таблица 2. Логические связки

№	Логическая связка	Название	Обозна-чение	Высказы-вание	Математическая запись
	и	конъюнкция логическое умножение	Ù, & *, And	A и В	A Ù B, A & B A * B, A And B
	или	дизъюнкция логическое сложение	Ú +, Or	A или В	A Ú B A + B, A Or B
	не	инверсия, логическое отрицание	¬,, Not	не А	¬А,, Not A
	Если…то	импликация, логическое следование	→, Þ	Если A, то В	A → B A Þ B
	тогда и только тогда	эквивалентность, равносильность, логическое тождество	«, º Û, ~	А тогда и только тогда, когда В	А«В, АºВ АÛВ, А~В

Импликацию можно выразить через дизъюнкцию и отрицание: A → B = ¬А Ú B (1)

Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию: A «B = (¬А Ú B) Ù (¬B Ú А) (2)

Вычисление значения логического выражения производится слева направо в соответствии с таблицей истинности (см. Таблицу 3) и приоритетом выполнения логических операций (см. Таблицу 4). Порядок выполнения операций можно менять, используя круглые скобки.

Таблица 3. Таблица истинности

A	B	A Ú B	A Ù B	¬A

Таблица 4. Приоритет выполнения логических операций

Приоритет операции	Логическая операция
Первый (высший)	Логическое отрицание
Второй	Конъюнкция (логическое умножение)
Третий	Дизъюнкция (логическое сложение)
Четвертый	Импликация (следование)
Пятый (низший)	Эквивалентность (равносильность)

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.

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] можно становить взаимное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Следствие Множество всех характеристических векторов является булевой алгеброй.

Дата добавления: 2013-12-12