Существуют следующие способы задания множеств

1. Перечислением элементов множества. Например: А = {1, 3, 5, 7,9} - конечное множество; В = {1, 2,..., n,...} - бесконечное множество.

2. Указанием свойств элементов множества. Для этого способа пользуются следующим форматом записи: А = { а| указание свойства элементов}. Здесь а является элементом множества A, а А.

Пример 1.7.

Х= { х | х=2^к, где k= 1,2,3,...}.

А = { а | а — простое число}

В= { b|b²-1=0, b- действительное число}

Универсальным множеством называется такое множество U, что все рассматриваемые в данной задаче множества являются его подмножествами.

Для наглядного представления множеств и отношений между ними используются диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера - Венна).

Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, - в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга.

С помощью диаграмм Венна удобно иллюстрировать операции над множествами.

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

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

Для множеств определены следующие операции: объединение, пересечение, дополнение.

Объединением множеств А и В (записывается АÈВ) называется множество, состоящее из элементов как одного, так и второго множества. Например, А и В — множества точек, принадлежащих некоторым двум кругам, имеющим общие точки, тогда объединением АÈВ будет фигура, состоящая из общих точек.

Пересечением множеств А и В (записывается АÇВ) называется множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно.

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

Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается А = В-А (рис. 3.1).

Основы логики

Как было отмечено ранее, информатика — прикладная наука, находящаяся на стыке многих наук. Вместе с тем она опирается на спектр разделов такой фундаментальной науки, как математика. Наиболее важное прикладное значение для информатики имеют булева(я) алгебра, используемая в разработке алгоритмов программ и в синтезе цифровых устройств, теория множеств и теория графов, используемые в описании различных структур.

Аппарат алгебры логики (булевой алгебры) создан в 1854 г. Дж. Булем как попытка изучения логики мышления математическими методами.

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

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

Элементы. Схемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и управляющие. Первые производят обработку информации, представленной в бинарной форме; вторые служат для передачи бинарной формы информации; третьи выполняют управляющие функции, генерируя соответствующие сигналы. Во всех случаях в тех или иных точках логических схем сигналы двух различных уровней могут представляться бинарными символами {0,1} или логическими значениями {Истина (True), Ложь (False)}. Поэтому множество элементов булевой алгебры выбирается бинарным В - {0,1}, а сама алгебра называется бинарной, или переключательной. Ее элементы называются константами, или логическими 0 и 1, которым в ряде случаев соответствуют бинарные цифры, в других случаях — логические значения, соответственно ложь (False) и истина (True). В дальнейшем для обозначения булевых переменных будем использовать буквы латинского алфавита — х, у, г... Набор переменных х, у, z... может рассматриваться как n-разрядный двоичный код, разрядами которого являются эти переменные.

Операции. Основными, или базовыми, операциями булевой алгебры служат (табл. 3.1): И (AND), ИЛИ (OR) и НЕ (NOT). Операция И называется логическим умножением, или конъюнкцией, и обозначается знаком умножения {•, Ù}. Операция ИЛИ называется логическим сложением, или дизъюнкцией, иобозначается знаком сложения {+, Ú}. Операция НЕ называется логическим отрицанием, или инверсией (дополнением), и обозначается знаком {—, }.

Таблица 3.1 Базовые логические операции

Операция	Название операции	Обозначение операции
И (AND)	Логическое умножение — конъюнкция	Ù •
ИЛИ (OR)	Логическое сложение — дизъюнкция	+ Ú
ЕСЛИ (TO)	Импликация, следование	Þ, ®
НЕ (NOT)	Логическое отрицание — инверсия	—,

При выполнении операций применяются отношение эквивалентности «=» и скобки «()», которые определяют порядок выполнения операций. Если скобок нет, то операции выполняются в следующей последовательности: логическое отрицание, логическое умножение и логическое сложение.

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

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

Это правило можно записать в виде следующей таблицы:

А	Ā

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

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

Таблица истинности этой операции, как следует из определения, имеет вид

А	В	А&В

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

Таблица истинности такой операции следующая:

А	В	AÚB

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

Таблица истинности импликации следующая:

А	В	А→В

Импликация имеет следующие свойства:

А→В ¹ В → А

А→ А= 1

0 →А= 1

1 → А = А

А→ 1 = 1

А→ 0 = А

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

Таблица истинности:

А	В	А↔В

Эквиваленция имеет следующие свойства:

А↔ В = В ↔ А

А ↔ = ↔Ā

А↔ 1 = А

А ↔ 0 = Ā

С помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические выражения, которые также называются булевскими функциями. Например, С = ((A Ú В) → В) Ú А.

Чтобы избежать большого количества скобок в булевских функциях, принято следующее соглашение о старшинстве операций.

Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

Зависимости между логическими операциями

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

Законы алгебры логики

1. Закон двойного отрицания

2. коммутативный закон для конъюнкции

3. коммутативный закон для дизъюнкции

4. ассоциативный закон для конъюнкции

5. ассоциативный закон для дизъюнкции

6. дистрибутивные законы

8. законы де Моргана

10. закон идемпотенции для конъюнкции

11. закон идемпотенции для дизъюнкции

12. закон единицы для конъюнкции

13. закон нуля для конъюнкции

14. закон единицы для дизъюнкции

15. закон нуля для дизъюнкции

16. закон исключения третьего

17. закон противоречия

18.

19.

20. законы поглощения

21.

22.

23.

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

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

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

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

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