- •Тема 1. Множества, отношения, функции.
- •1.1 Элементы и множества
- •1.2 Задание множеств
- •1.3 Операции над множествами
- •1.4 Свойства операций над множествами.
- •Тема 2. Булевы функции
- •2.1 Функции алгебры логики
- •2.2 Булевы функции одной переменной
- •2.3 Булевы функции двух переменных
- •2.4 Реализация функций формулами.
- •3 Логические исчисления
- •3.1 Основные понятия.
- •3.2 Высказывания.
- •3.3 Формулы.
- •3.4 Интерпретация.
- •3.5 Формальная теория.
- •Тема 4. Графы и сети
- •4.1 История возникновения теории графов.
- •4.2 Определение графа.
- •Смежность.
- •Графическое изображение графа.
- •4.5 Основные определения теории графов.
- •Представление графа в эвм матрицей смежности.
- •Тема 5 комбинаторные задачи
- •5.1 Комбинаторные конфигурации.
- •5.2 Комбинаторные задачи.
- •Тема 6 основы теории алгоритмов
1.4 Свойства операций над множествами.
Пусть задан универсум U. Тогда выполняются следующие свойства:
1. идемпотентность:
2. коммутативность:
3. ассоциативность:
;
4. дистрибутивность:
;
5. поглощение:
;
свойства нуля:
свойства единицы:
,
8. инволютивность:
Пояснение: В справедливости перечисленных свойств можно убедиться различными способами. Например, нарисовать диаграммы Венна для левой и правой частей равенства и убедиться, что они совпадают, или же провести формальное рассуждение для каждого равенства. Рассмотрим для примера первое равенство: . Возьмем произвольный элемент x, принадлежащий левой части равенства, . По определению операции объединения имеем . В любом случае . Взяв произвольный элемент из множества в левой части равенства, обнаружили, что он принадлежит множеству в правой части. Отсюда по определению включения множеств получаем, что . Пусть теперь . Тогда, очевидно, верно . Отсюда по определению операции объединения имеем . Таким образом, . Следовательно, по определению равенства множеств, . Аналогичные рассуждения нетрудно провести и для остальных равенств.
Тема 2. Булевы функции
2.1 Функции алгебры логики
Функции где , называются функциями алгебры логики, или булевыми функциями, по имени Дж. Буля. Множество булевых функции от n переменных обозначим .
Булеву функцию от n переменных можно задать таблицей истинности:
Таблица истинности
|
…, |
|
|
|
0 |
… |
0 |
0 |
|
0 |
… |
0 |
1 |
|
0 |
… |
1 |
0 |
|
… |
... |
… |
… |
|
1 |
… |
1 |
1 |
Если число переменных n, то в таблице истинности имеется строк, соответствующих всем различным комбинациям значений переменных, которым можно сопоставить различных столбцов, соответствующих различным функциям. Таким образом, число булевых функций от n переменных с ростом n растет весьма быстро:
2.2 Булевы функции одной переменной
Переменная х |
0 |
1 |
|
Название |
Обозначение |
|
|
нуль тождественная отрицание единица |
0 x
1 |
0 0 1 1 |
0 1 0 1 |
2.3 Булевы функции двух переменных
|
Переменная x |
0 |
0 |
1 |
1 |
|
Переменная у |
0 |
1 |
0 |
1 |
Название |
Обозначение |
|
|
|
|
нуль |
0 |
0 |
0 |
0 |
0 |
конъюнкция |
|
0 |
0 |
0 |
1 |
сложение по модулю 2 |
|
0 |
1 |
1 |
0 |
дизъюнкция |
|
0 |
1 |
1 |
1 |
стрелка Пирса |
|
1 |
0 |
0 |
0 |
эквивалентность |
|
1 |
0 |
0 |
1 |
импликация |
|
1 |
1 |
0 |
1 |
штрих Шеффера |
| |
1 |
1 |
1 |
0 |
единица |
1 |
1 |
1 |
1 |
1 |