- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
6.1. Операции над высказываниями
Условимся считать высказывание элементарным (простым), если никакую его часть нельзя рассматривать как отдельное высказывание. Для образования составных (сложных) высказываний используют логические связки (логические операции).
Пусть X и Y – два высказывания. Определим основные логические операции.
Отрицанием высказывания X называется высказывание , которое истинно тогда и только тогда, когда Х ложно. В разговорной речи высказывание соответствует составлению из высказывания Х нового высказывания «не Х» или «неверно, что Х». Для обозначения отрицания высказывания также используют запись ¬Х (Х).
Конъюнкцией двух высказываний Х и Y называется высказывание ХY, которое истинно тогда и только тогда, когда истинны оба высказывания. Конъюнкция иначе называется логическим умножением, а Х и Y – сомножителями. В разговорной речи конъюнкция соответствует соединительному союзу «и», ХY – читается как «Х и Y». Для обозначения конъюнкции высказываний также используют запись Х&Y.
Дизъюнкцией двух высказываний Х и Y называется высказывание ХY, которое ложно тогда и только тогда, когда Х и Y ложны. Дизъюнкция иначе называется логическим сложением, а Х и Y – слагаемыми. В разговорной речи дизъюнкция соответствует соединительному союзу «или», ХY – читается как «Х или Y».
Замечание. Следует обратить внимание, что в повседневной речи союз «или» употребляется в двух смыслах: «исключающее или», когда истинность составного высказывания определяется истинностью только одного из высказываний, и «не исключающее или», когда истинность составного высказывания определяется истинностью хотя бы одного из высказываний. «Исключающее или» не является операций дизъюнкцией.
Импликацией двух высказываний Х и Y называется высказывание Х→Y, которое ложно тогда и только тогда, когда Х – истинно, а Y – ложно. В разговорной речи импликация высказываний соответствует составлению высказывания вида: «Х имплицирует Y», «из Х следует Y», «если Х, то Y», «Х достаточно для Y», «Х только тогда, когда Y», «Y необходимо для Х», «Y тогда, когда Х». В обозначении Х→Y Х – посылка, Y – заключение.
Употребление в повседневной речи слов «если…, то…» несколько отличается от использования их в математической логике. Так в повседневной речи, если высказывание X ложно, то сложное высказывание Х→Y вообще не имеет смысла. В математической логике при ложном высказывании X значение сложного высказывания (импликации) всегда истинно.
Пример. Пусть даны высказывания A=«по проводнику протекает электрический ток» и B = «вокруг проводника есть магнитное поле». Тогда формула AB отражает высказывание «если по проводнику протекает электрический ток, то вокруг проводника возникает магнитное поле».
Эквиваленцией двух высказываний Х и Y называется высказывание Х↔Y, которое истинно тогда и только тогда, когда истинные значения высказываний Х и Y совпадают. В разговорной речи эквиваленция двух высказываний соответствует составлению нового высказывания вида «Х эквивалентно Y», «Х тогда и только тогда, когда Y», «Х необходимо и достаточно для Y».
Примеры.
1. Пусть даны высказывания A=«быть четным числом» и B=«число делится на два». Тогда формула F=(AB) отображает высказывание «для того, чтобы число было четным необходимо и достаточно, чтобы оно делилось на два».
2. Если высказывание «3 – вещественное или целое число», то высказывание A1A2 = 1;
3. Если высказывание «3,14… – рациональное число», то высказывания B1=0 или = 1;
4. Если высказывание «3 есть простое число тогда и только тогда, когда оно целое», то высказывание А1А2=1.
Обозначения элементарных высказываний А1, А2, В1 взяты из первого примера.
Правила построения сложных высказываний в виде последовательности пропозициональных переменных, логических связок и вспомогательных символов определяют возможность формального описания любого текста. При формальной записи сложного высказывания всегда нужно исходить из его содержания. До тех пор пока не определена логическая структура сложного высказывания, его нельзя формально описывать.
Правила выполнения логических операций над сложными высказываниями на основе заданных логических связок и пропозициональных переменных формирует алгебру высказываний.
Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения логических операций , , , →, ↔, будем называть формулой алгебры высказываний. Исходные высказывания при этом могут быть постоянными, то есть иметь определенное значение И или Л, или могут не иметь определенного значения. В первом случае исходные высказывания будем называть постоянными элементарными высказываниями, во втором – переменными элементарными высказываниями. Переменные элементарные высказывания будем обозначать заглавными буквами латинского алфавита.
При вычислении по формуле учитывается приоритет операций
=> => => → => ↔,
где знак => обозначает убывание приоритета. При необходимости изменить естественную последовательность действий используют скобки.
Символы, соответствующие переменным элементарным высказываниям, называются пропозициональными переменными.
Пропозициональной формулой (ПФ) называется выражение, построенное из пропозициональных переменных с помощью логических связок (и, возможно, некоторых других) по следующим правилам:
каждая пропозициональная переменная есть ПФ;
если Х и Y – ПФ, то , , , ,
– тоже ПФ.
Если даны формулы F1, F2,…Fn, то истинное значение формулы F=F1F2…Fn определяется истинностью всех формул F1, F2,…Fn.
Пример. Пусть даны высказывания A=«компьютер содержит микропроцессор», B=«компьютер содержит оперативную память», C=«компьютер содержит контроллеры»; D=«компьютер содержит порты ввода–вывода». Тогда формула F=ABCD отражает высказывание «компьютер содержит микропроцессор, оперативную память, контроллеры и порты ввода-вывода»
Если даны формулы F1, F2,…Fn, то истинностное значение формулы F=F1F2…Fn определяется истинностью хотя бы одной формулы F1, F2,… или Fn.
Пример. Пусть даны высказывания S=«полная система функций математической логики», A=«система функций содержит хотя бы одну нелинейную функцию», B=«система функций содержит хотя бы одну немонотонную функцию», C=«система функций содержит хотя бы одну не самодвойственную функцию», D=«система функций содержит хотя бы одну функцию, не сохраняющую 0», E=«система функций содержит хотя бы одну функцию, не сохраняющую 1». Тогда формула F=S(ABCDE) отражает сложное высказывание «для того чтобы система функций математической логики была полной, необходимо и достаточно, чтобы она содержала хотя бы по одной нелинейную, немонотонную и не самодвойственную функции, а также функции, не сохраняющие 0 и 1».