- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 7.2.Операции на множестве высказываний
Из элементарных высказываний можно составлять сложные высказывания с помощью логических операций. Чтобы уметь однозначно выявить истинное значение сложных высказываний, строго определим логические операции. Единственное свойство сложного высказывания, которое нас интересует, это его истинностное значение. Элементарные высказывания, входящие в состав сложного высказывания, связываются логическими операторами не по смысловому описанию, а только по их истинностным значениям. Следовательно, сложные высказывания являются функциями от входящих в них элементарных высказываний. Все операции в логике высказываний описываются хорошо знакомыми нам таблицами Кейли, которые в логике принято называть таблицами истинности. Все языковые конструкции, которые мы будем использовать для описания той или иной операции, не более чем средство запоминания. Дадим более строгое определение.
Определение:Функцияназывается–местной булевой функцией, если каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0;1}.
Отрицание
Определим унарную логическую операцию – отрицание, которая обозначается следующим образом: .
-
0
1
1
0
Аналогом отрицания в естественном языке служит частица «не», или слова «неверно, что».
Пример 7.2:если мы хотим отрицать, что
Точка М принадлежит прямой а (1)
Мы скажем
Точка М не принадлежит прямой а (2)
Если (1) – это высказывание , то (2) –.
Обратите внимание, что истинностные значения высказываний (1) и (2) находятся в определённой зависимости: если (1) – истинно, то (2) – ложно.
Если (1) – ложно, то (2) – истинно.
Пример 7.3:покажем, что
-
0
1
0
1
0
1
Это один из законов Булевой алгебры, называемый законом двойного отрицания. Следует отметить, что отрицание составных формул не такая уж тривиальная операция. Чуть позднее мы проиллюстрируем это утверждение.
Конъюнкция
Введём бинарную логическую операцию – конъюнкцию(от лат. Conjunctio – соединение).
Определение:Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны. Таблица истинности выглядит следующим образом:
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Эту логическую операцию называют ещё логическим умножением, или логическим минимумом. В естественном языке эта операция чаще всего интерпретируется союзом «и».
Свойства конъюнкции:
– коммутативность;
– ассоциативность;
– идемподентность;
– закон исключённого противоречия;
;
.
Замечание:В силу коммутативности конъюнкции, формальная интерпретаций утверждений: «Мэри вышла замуж и родила ребёнка» и «Мэри родила ребёнка и вышла замуж» - эквивалентны. В то время уже пятиклассник способен уловить семантическую разницу.
Замечание:Таким образом, 1 является элементом идентичности для конъюнкции на множестве высказываний.
Пример 7.4:Выведем формулу счастливой любви по Шекспиру. Для этого проанализируем следующие строки:
Увы, я никогда не слышал
И не читал – в истории ли, в сказке
Чтоб гладким был пут истинной любви.
Но или разница в происхождении
О горе, высшему – плениться низшей.
Или различье в летах
О, насмешка!
Быть слишком старым для невесты юной
Иль выбор близких и друзей
О, мука! Но как любить по выбору чужому?
А если выбор всем хорош – война,
Болезнь иль смерть всегда грозят любви.
Выделим в этом примере следующие элементарные высказывания:
– наличие у любящих разницы в происхождении;
– разница в летах;
– любовь по выбору близких и друзей;
– война;
– болезнь одного из любящих;
– смерть одного из любящих.
Тогда формула будет выглядеть следующим образом
Пример 7.5:Всякая система уравнений
Представляет собой конъюнкцию решений: