- •Введение
- •1. Теория множеств
- •1.1. Основные понятия
- •1.2. Операции над множествами
- •1.3. Алгебраические свойства операций над множествами
- •1.4. Нечёткие множества
- •2. Элементы комбинаторики
- •2.1. Основные правила комбинаторики
- •2.2. Выборки элементов без повторений
- •2.3. Выборки элементов с повторениями
- •2.4. Объединение комбинаторных конфигураций
- •2.5. Бином Ньютона
- •3. Отношения на множествах
- •3.1. Декартово произведение множеств
- •3.2. Булев куб и его свойства
- •3.3. Понятие отношения
- •3.4. Операции над отношениями
- •3.5. Свойства отношений на множестве
- •3.6. Отношения эквивалентности, толерантности и порядка
- •3.7. Нечеткие отношения
- •3.8. Понятие отображения
- •3.9. Алгебраическая операция
- •3.10. Общие сведения об алгебраических системах
- •4 Булевы функции
- •4.1. Основные определения и операции над высказываниями
- •4.2. Типы пф.
- •4.3. Равносильность формул
- •4.4. Дизъюнктивные и конъюнктивные нормальные формы
- •4.5 Алгоритм приведения пф к нормальным формам
- •4.6 Аналитический способ приведения к сднф
- •4.7. Табличный способ приведения к сднф
- •4.8. Табличный способ приведения к скнф
- •4.9. Логическое следствие
- •4.10. Алгоритм проверки правильности рассуждений
- •4.11. Алгоритм определения всех логических следствий из данных посылок
- •4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
- •4.13. Полнота систем булевых функций
- •4.14. Полином Жегалкина
- •4.15. Замкнутость
- •4.16. Теорема Поста
- •4.17. Нечеткая логика
- •5. Многозначные функции
- •5.1. Функции и формулы k-значной логики
- •5.2. Полнота и замкнутость функций k-значной логики
- •5.3. Особенности k – значной логики
- •6.. Основные понятия теории графов.
- •6.1. Задачи теории графов.
- •6.2. Основные определения.
- •6.3. Степени вершин графа.
- •6.4. Изоморфизм графов.
- •6.5. Матричные способы задания графов.
- •6.6. Основные операции над графами.
- •6.7. Маршруты в графах
- •6.8. Связность в графах.
- •Связность и матрица смежности графа.
- •6.9. Матрица взаимодостижимости.
- •6.10. Деревья Свободные деревья.
- •Ориентированные, упорядоченные и бинарные деревья.
- •6.11. Эйлеровы графы.
- •6.12 Гамильтоновы графы.
- •6.13. Планарные графы.
- •6.14. Потоки в сетях. Основные определения.
- •Теорема Форда и Фалкерсона.
- •Алгоритм построения максимального потока в сети.
- •7. Конечные автоматы
- •7.1. Понятие конечного автомата Общие сведения о конечных автоматах
- •7.2. Абстрактное определение конечного автомата
- •7.3. Автоматная функция и её моделирование Понятие ограниченно детерминированной функции
- •Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •7.4. Эксперименты с автоматами
- •8. Рекуррентные уравнения
- •8.1. Определение рекуррентного уравнения/ Решение линейного однородного рекуррентного уравнения
- •8.2. Решение линейного неоднородного рекуррентного уравнения
- •8.3. Решение рекуррентного уравнения для чисел Фибоначчи
- •Заключение
- •Библиографический список
- •Оглавление
- •1.Теория множеств 5
- •2 Элементы комбинаторики 14
- •3 Отношения на множествах 22
- •4. Булевы функции 42
- •5. Многозначные функции 64
- •6. Основные понятия теории графов 70
- •7. Конечные автоматы 106
- •8. Рекуррентные уравнения 120
- •394026 Воронеж, Московский просп., 14
4 Булевы функции
4.1. Основные определения и операции над высказываниями
Логика (в переводе с древнегреческого) означает слово, выражающее мысль. В современном понимании логика - это наука о способах мышления. Математическая логика служит для создания алгоритмов логического вывода.
Особенность математической логики состоит в использовании математического языка символов и формул. Это позволяет устранить двусмысленность, свойственную естественным языкам.
Исходным понятием математической логики является «высказывание». Высказывание - это повествовательное предложение, которое истинно или ложно. Оно не может быть истинным и ложным одновременно. Высказывания обозначаются большими буквами латинского алфавита А, В,…. Любое высказывание рассматривается как переменная величина, так называемая высказывательная или пропозициональная переменная, принимающая значения 1 (истина) или 0 (ложь).
Высказываниями являются, например, следующие предложения. «3 есть простое число». «Киев – столица Узбекистана». Первое из них истинно, второе – ложно.
Высказывание называется элементарным (простым), если любую его часть нельзя рассматривать как отдельное высказывание. В процессе рассуждений из одних высказываний формируются другие более сложные высказывания. Они получаются из исходных высказываний добавлением частицы «НЕ», а также соединением высказываний с помощью связок «И», «ИЛИ», «ЕСЛИ..,ТО» ТОГДА И ТОЛЬКО ТОГДА, КОГДА» и других. Эти связки соответствуют логическим операциям над пропозициональными переменными.
Далее указывается приоритет (очерёдность выполнения) основных логических операций и даются их определения.
Отрицанием высказывания X называется высказывание , которое истинно тогда и только тогда, когда Х ложно. В разговорной речи высказывание соответствует составлению из высказывания Х нового высказывания «не Х».
Конъюнкцией двух высказываний Х и Y называется высказывание ХY, которое истинно тогда и только тогда, когда истинны оба высказывания. Конъюнкция иначе называется логическим умножением, а Х и Y – сомножителями. В разговорной речи конъюнкция соответствует соединительному союзу «и».
Дизъюнкцией двух высказываний Х и Y называется высказывание ХY, которое ложно тогда и только тогда, когда Х и Y ложны. Дизъюнкция иначе называется логическим сложением, а Х и Y – слагаемыми. В разговорной речи дизъюнкция соответствует соединительному союзу «или».
Импликацией двух высказываний Х и Y называется высказывание Х→Y, которое ложно тогда и только тогда, когда Х – истинно, а Y – ложно. В разговорной речи импликация высказываний соответствует высказыванию вида: «если Х, то Y».
Эквиваленцией двух высказываний Х и Y называется высказывание Х↔Y, которое истинно тогда и только тогда, когда истинностные значения высказываний Х и Y совпадают. В разговорной речи эквиваленция двух высказываний соответствует выражению «Х тогда и только тогда, когда Y».
Пропозициональной формулой (ПФ) называется выражение, построенное из пропозициональных переменных с помощью основных (и, возможно, некоторых других) логических связок. Последовательность выполнения операций в формулах задаётся их приоритетом. Для его изменения используются скобки.
ПФ от n переменных можно рассматривать как функцию, которая произвольному набору из n нулей и единиц ставит в соответствие 0 или 1. Такая функция называется двоичной, булевой или переключательной функцией.
Каждой ПФ можно поставить в соответствие таблицу, называемую таблицей истинности, в которой перечислены все возможные значения входящих в нее переменных и значения ПФ на этих наборах.
Например, таблица истинности основных логических операций имеет вид
Таблица 11
X |
Y |
|
|
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |