Элементы теории множеств

Алгебра высказываний (булева алгебра)

Математические основы информатики

Основное понятие булевой алгебры – выказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать, истинно оно или ложно, поэтому высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (0) или ИСТИНА (1). Например, содержание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержательная часть высказываний, а только их истинность. Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логических операций. Рассмотрим их подробней.

Операцией отрицания А (Ø А, не А) называют высказывание А, которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «завтра будет снег», то Ø А - «завтра НЕ будет снега», истинность одного утверждения автоматически означает ложность второго. Отрицание – унарная (т.е. для одного операнда) логическая операция.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А Ù В или С = А & В (С равно А и В). Например, пусть высказывание А «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери».

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A Ú В (С равно А ИЛИ В). Пример: высказывание А «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе».

Импликацией двух высказываний А (А - посылка) и В (В - заключение) является новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно, записывается С = А ® В (из А следует В). Пример: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Операция не симметрична, т.е. из В ® А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Эквиваленцией двух высказываний А и В является новое вы сказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А «В (С = А º В).

С помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические

выражения, которые также называются булевскими функциями. Например, С = (( Ú В) ® В) Ú А. Чтобы избежать большого количества скобок в булевских функциях, принято соглашение о старшинстве операций. Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности:

1. = А	закон двойного отрицания
2. А & В = В & А	коммутативный закон для конъюнкции
3. A Ú B = B Ú A	коммутативный закон для дизъюнкции
4. (А & В) & С = А & (В & С)	ассоциативный закон для конъюнкции
5. (A Ú B) Ú C = A Ú (B Ú C)	ассоциативный закон для дизъюнкции
6. А & (В Ú С) = (А & В) Ú (А & С)	дистрибутивные законы
7. A Ú (В & С) = (A Ú В) & (A Ú С)
8.	законы де Моргана
9.
10. А & А = А	закон идемпотенции для конъюнкции
11. A Ú A = А	закон идемпотенции для дизъюнкции
12. А & 1 = А	закон единицы для конъюнкции
13. А & 0 = 0	закон нуля для конъюнкции
14. A Ú 1 = 1	закон единицы для дизъюнкции
15. A Ú 0 = А	закон нуля для дизъюнкции
16. A Ú = 1	закон исключения третьего
17. А & = 0	закон противоречия
18. А ® В = Ú В
19. А «В = (А ® В) & (В ® А) = ( Ú В) & (A Ú ) = (A & B) Ú ( & )
20. A Ú (А & В) = А	законы поглощения
21. А & (A Ú В) = А
22. А & ( Ú B) = A & B
23. A Ú ( & В) = A Ú В

Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований.

Первая из них – дизъюнктивная нормальная форма (ДНФ), имеет вид A _l Ú A ₂ Ú... Ú A_n, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например:

В = ( & А ₂ & A ₃) Ú (А ₄ & А ₅).

Вторая – конъюнктивная нормальная форма (КНФ), имеет вид А ₁ Ù А ₂ Ù... Ù A_n, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например:

В = .

Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку.

Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается Æ. Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным. Задать множество можно перечислением его элементов. Например, множество образованное из n элементов а ₁, а ₂,..., а_n, обозначается А = { а ₁, а ₂,..., а_п }; пишется а Î А, если а является элементом множества А, в противном случае a Ï A. Задать множество можно также, указав общее свойство для всех его и только его элементов.

Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт А = В. Множество А ₁, называется подмножеством А, если все элементы множества А ₁ являются элементами А (записывается А ₁ Ì А).

Для множеств определены следующие операции: объединение, пересечение, дополнение. Объединением множеств А и В (записывается A È B) называется множество, состоящее из элементов как одного, так и второго множества. Пересечением множеств А и В (записывается А Ç В) называется множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно. Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается = В – А (рис. 1.7).

Рис. 1.2. Операции над множествами

Дата добавления: 2014-11-29