- •Введение
- •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.10. Алгоритм проверки правильности рассуждений
Проверка правильности рассуждений или проверка того, что данная формула X является логическим следствием формул X1, X2, ..., Xn осуществляется по следующему алгоритму.
Шаг 1. Образовать конъюнкцию посылок X1, X2, …, Xn.
Шаг 2. Составить импликацию X1 X2 ... Xn X.
Шаг 3. Полученную формулу исследовать на тождественную истинность: если она является тождественно истинной, то X является логическим следствием формул X1, X2, ..., Xn, иначе – не является.
Пример. Если два числа равны, то, как известно, их модули равны. Данные числа не равны. Можно ли из этого заключить, что их модули не равны?
Рассмотрим следующие элементарные высказывания: X= «Два числа равны», Y= «Модули чисел равны». Тогда высказыванию «Если два числа равны, то, как известно, их модули равны» соответствует формула XY, высказыванию «Данные числа не равны» – , высказыванию «Модули чисел не равны» – . Заметим, что вопрос задачи сводится к проверке правильности рассуждений, то есть является ли логическим следствием посылок и X Y:
.
Составив таблицу истинности формулы (XY) , можно увидеть, что она не является тождественно истинной, следовательно, рассуждения не являются правильными, и утверждение «Модули чисел не равны» не верно.
С помощью СКНФ можно решить более общую задачу построения всех логических следствий из данных посылок.
4.11. Алгоритм определения всех логических следствий из данных посылок
Шаг 1. Образовать конъюнкцию всех посылок X1, X2,..., Xn.
Шаг 2. Полученную конъюнкцию привести к СКНФ.
Шаг 3. Множество всех формул, равносильных следствиям из данных посылок, образуют произведения сомножителей СКНФ, взятых по одному, по два и так далее.
Пример. Найти все следствия из посылок XY иXYX Y.
Образуем конъюнкцию посылок и найдем ее СКНФ.
(X Y)(X Y X Y)(X Y)(X Y)(X Y)
(X Y)(X Y) – СКНФ. Тогда следствиями являются XY; X Y; (X Y)(X Y).
СКНФ позволяет решить и обратную задачу: для данной формулы найти все посылки, логическим следствием которых она является.
4.12. Алгоритм определения всех посылок, логическим следствием которых является данная формула
Шаг 1. Данную формулу привести к СКНФ.
Шаг 2. Составить ее произведения с каждым из недостающих до соответствующей полной СКНФ множителей – по одному, по два и так далее (под полной понимается СКНФ тождественно ложной формулы с теми же переменными).
Пример. Следствием каких посылок является импликация XY?
Для импликации XY СКНФ имеет вид . Соответствующая полная СКНФ имеет вид
.
Образуем всевозможные произведения с недостающими сомножителями:
(X Y)(X Y) Y;
(X Y)(X Y) XY;
(X Y)(X Y) X;
(X Y)( X Y) (X Y) XY;
(X Y)( X Y) (X Y) XY;
(X Y) (X Y) (X Y) XY;
(X Y)( X Y) (X Y) (X Y) 0.
4.13. Полнота систем булевых функций
Ранее отмечалось, что любая функция алгебры логики может быть выражена в виде формулы через элементарные функции x̅, x1 x2 , x1 x2. Однако, такими свойствами обладают и другие системы элементарных функций.
Система функций {ƒ1,ƒ2,…ƒn} из P2 (множество всех булевых функций) называется (функционально) полной, если любая булева функция может быть записана в виде формулы через функции этой системы.
Примеры фундаментально полных систем:
1) P2 – множество всех булевых функций – полная система
2) Система {x̅, x1 x2, x1 x2} – полная система
Заметим, что система {0,1} не является полной.
Теорема. Пусть даны две системы функций из P2 . A = {ƒ1, ƒ2…} и B = {g1, g2…}, относительно которых известно, что система функций A полна и каждая ее функция выражается в виде формулы через функции системы B. Тогда система B является полной.
Опираясь на эту теорему можно установить полноту ряда систем и тем самым расширить список примеров полных систем.
3) Система {x̅, x1 x2} является полной, т.к. известно, что 2) полна и .
4) Система {x̅, x1 x2} является полной, т.к. полна система 2) и, кроме того, .
5) Система {x1 | x2} является полной, т.к. взяв за систему A систему 3), а за систему B систему 5) и определив и .
6) Система {0, 1, x1x2, x1 x2} является полной. Для этого за систему A берется система 3), а за B – система 6).
При этом: x1 1 = x̅1, x1x2 = x1 x2
Приведенные примеры показывают, что существует целый ряд полных систем. Каждая из них может быть принята за множество элементарных функций. Таким образом, для задания булевых функций можно использовать различные языки формул. Какой из них является более удобным, зависит от характера рассматриваемой задачи.