- •Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «кемеровский государственный университет»
- •Кафедра автоматизации исследований
- •И технической кибернетики
- •Дискретная математика
- •Содержание
- •Глава 1. Теория множеств. Дискретная теория вероятности......5
- •Глава 2. Теория графов.....................................................................53
- •Глава 3. Дискретные структуры: конечные автоматы, коды...76
- •Глава 4. Алгебра логических функций..........................................88
- •Глава 5. Логика высказываний и логика предикатов..............109
- •Глава 6. Схемы переключателей. Комбинационные схемы...................................................................................................123
- •Глава 1. Теория множеств. Дискретная теория вероятности
- •Множества и операции над ними
- •Упражнения
- •1.2. Векторы и прямые произведения множеств. Проекция вектора на ось
- •Упражнения
- •1.3. Комбинаторика Правило суммы
- •Правило произведения
- •Число размещений без повторений
- •Число размещений с повторениями
- •Число перестановок без повторений
- •Число сочетаний без повторений
- •Упражнения
- •1.4. Введение в дискретную теорию вероятностей
- •Свойства элементарных событий:
- •Соотношения между событиями:
- •Свойства операций над событиями:
- •Упражнения
- •1.5. Соответствия и функции
- •Взаимно однозначные соответствия и мощность множеств
- •Упражнения
- •1.6. Отношения
- •Способы задания бинарных отношений
- •Свойства бинарных отношений
- •Отношение эквивалентности
- •Отношение порядка
- •Лексико-графический порядок.
- •Упражнения
- •1.7. Операции и алгебры
- •Свойства бинарных алгебраических операций
- •1.8. Гомоморфизм и изоморфизм алгебр
- •Полугруппы, группы, решетки
- •Упражнения
- •Глава 2. Теория графов
- •2.1. Основные определения, способы задания, основные классы, изоморфизм графов
- •Способы задания графа
- •Степени вершин графа
- •Части, суграфы и подграфы
- •Операции над частями графа
- •Графы и бинарные отношения
- •Упражнения
- •Среди пар графов, изображенных на рисунке, указать пары изоморфных графов и пары неизоморфных графов. Ответ обосновать.
- •Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы
- •Упражнения
- •Деревья, их свойства. Характеристические числа графов. Сети
- •Упражнения
- •Глава 3. Дискретные структуры: конечные автоматы, коды
- •3.1. Машина Тьюринга
- •Упражнения
- •Основы теории кодирования
- •Упражнения
- •Глава 4. Алгебра логических функций
- •4.1. Основные определения
- •Упражнения
- •4.2. Эквивалентные преобразования
- •Упражнения
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы
- •Упражнения
- •4.4. Дизъюнктивные нормальные формы и импликанты
- •Упражнения
- •4.5. Минимизация днф. Тупикова днф
- •Упражнения
- •4.6. Алгебра Жегалкина
- •Упражнения
- •4.7. Двойственность в алгебре логики. Самодвойственные функции
- •Принцип двойственности
- •Упражнения
- •4.8. Функциональная полнота систем
- •Упражнения
- •Глава 5. Логика высказываний и логика предикатов
- •5.1. Логика высказываний
- •Алгебра логики
- •Исчисление высказываний
- •Упражнения
- •5.2. Логика предикатов
- •Упражнения
- •Глава 6. Схемы переключателей. Комбинационные схемы
- •Схемы переключателей
- •Комбинационные схемы
- •Упражнения
- •Литература
- •650043, Кемерово, ул. Красная, 6.
Алгебра логики
Алгебра логики рассматривает логические формулы как алгебраические выражения, которые можно преобразовать по определенным правилам. Знаки операций обозначают логические операции (логические связки).
В формулах алгебры логики переменные – это высказывания. Они принимают только два значения – ложь и истина, которые обозначаются либо 0 и 1, либо Л и И, либо false и true.
Каждая формула задает логическую функцию: функцию от логических переменных, которая сама может принимать только два логических значения.
Таблица функций одной переменной:
|
Константа 0:
|
Тождество:
|
Отрицание:
|
Константа 1: |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
Таблица функций двух переменных , соответствующих основным логическим связкам:
|
|
Дизъюнкция |
Конъюнкция |
Импликация |
Эквивалентность (равнозначность) |
Неравнозначность (сложение по модулю 2) |
Штрих Шеффера (НЕ – И) |
Стрелка Пирса (НЕ – ИЛИ) |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
Значение любой логической формулы, содержащей знаки этих функций, на заданном наборе значений переменных можно вычислить, используя эти таблицы.
Интерпретацией формулы логики высказываний называется набор значений высказываний, входящих в нее.
Формула F называется тождественно истинной или тавтологией, если она принимает значение «истина» независимо от значений входящих в нее высказывательных переменных. Формула F называется выполнимой, если при некоторых значениях ее высказывательных переменных она принимает значение «истина». Такой набор значений высказывательных переменных называется моделью формулы F.
Исчисление высказываний
Пусть интерпретация определена на всех высказывательных переменных, встречающихся в формулах множества . Говорят, что выполняет или модель , если каждая формула из принимает значение «истина», при интерпретации . Говорят, что выполнимо, если имеет модель. Если не выполнимо, то пишут =.
Пусть – множество формул логики высказываний, А – произвольная формула. Говорят, что множество логически влечет формулу А, если любая модель являются моделью для А и обозначается = А.
Утверждение того, что некоторое высказывание (заключение) следует из других высказываний (посылок), называется аргументом. Аргумент часто представляют в виде:
... гипотезы
заключение
Аргумент называется правильным, если из множества гипотез логически следует заключение аргумента.
Второе правило исчисления высказываний: Modus Ponens.
Правило Modus Ponens: , т.е.
«Если , то ; но истинно, следовательно, истинно ».