- •Введение
- •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.2. Типы пф.
ПФ называется тождественно истинной, общезначимой или тавтологией, если она принимает значение 1 на всех наборах значений переменных. Для обозначения того, что ПФ F есть тавтология используют запись ├ F.
ПФ называется тождественно ложной или противоречием, если она принимает значение 0 на всех наборах значений переменных.
ПФ называется выполнимой (опровержимой), если на некоторых наборах значений переменных она принимает значение 1(0).
Пример. Определить тип ПФ . Для определения типа ПФ составим таблицу истинности
Таблица 12
X |
Y |
|
|
|
|
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
Как видно из таблицы истинности, данная формула является тождественно ложной.
Отрицание тавтологии будет, очевидно, тождественно ложной формулой, а отрицание тождественно ложной формулы является тавтологией. Формула будет тавтологией, если формулы A и B равносильны.
С точки зрения логики тавтология, есть не что иное, как некоторый логический закон. Наиболее важными тавтологиями являются ( А, В, С – произвольные формулы ).
А А; - закон исключения третьего;
А А;
А (В А);
(А В) ((А В) (А С)); - цепное рассуждение;
(А (В С)) ((А В) (А С));
(А В) А; (А В) В;
А (В (А В));
А (А В); В (А В);
(В А) ((В А) В);
((А В) А) А. - закон Пирса.
Каждую из этих тавтологий можно проверить, составив для неё таблицу истинности (Это нужно проделать самостоятельно).
4.3. Равносильность формул
Определение. Две формулы алгебры высказываний, зависящие от одинакового числа переменных, называются равносильными (эквивалентными), если они принимают одинаковые значения на одних и тех же наборах переменных. Равносильность формул обозначается знаком равенства.
Равносильность формул можно определить при помощи таблиц истинности или методом эквивалентных (равносильных) преобразований.
Для любых формул X, Y, Z справедливы следующие равносильности (законы алгебры высказываний), которые являются основными свойствами логических операций:
, (коммутативность);
, (ассоциативность);
, (дистрибутивность);
, (идемпотентность);
, (законыны поглощения);
(закон двойного отрицания);
, (законы де Моргана);
, , , , , (законы, определяющие действия с константами);
, (исключение импликации и эквиваленции);
(исключение дизъюнкции);
11. (исключение конъюнкции).
Понятия «равносильность» и «тавтология» связаны между собой. А именно, справедливо следующее:
Теорема. F1=F2 тогда и только тогда, когда F1↔F2 является тавтологией.
Справедливость этой теоремы вытекает непосредственно из определений равносильности и тавтологии.
Если формула F содержит подформулу Fi, то замена подформулы Fi в формуле F на эквивалентную ей формулу Fj не изменяет значения формулы F при любом наборе пропозициональных переменных. Если необходима подстановка в формулу F вместо формулы Fi новой формулы Fj, то эту операцию нужно выполнить всюду по символу Fi .
Правила замены и подстановки расширяют возможности эквивалентных преобразований формул сложных высказываний.
Пример. Дано F=(X1X2) ((X2X3) (X1X2 X3).
Выполним преобразования для упрощения алгебраического выражения.
Удалим всюду логическую связку :
F= ;
Приведем отрицание к переменным по закону де Моргана:
F=X1 X2 X3;
Выполним преобразование по закону дистрибутивности:
F=( X1 ) X2 X3;
Удалить член (X1 ), так как (X1 )=1:
F= X2 X3;
Выполним преобразование по закону дистрибутивности:
F= (X2X3) ( X3);
Удалим ( X3 )=1:
F= (X2X3);
7) Применим закон ассоциативности:
F=( X2)X3;
Приравняем «истине» значение формулы X, т. к.
(X2 )=1:
F=1X3=1.
Проблемой разрешимости для логики высказываний называют следующую проблему: существует ли такая процедура, которая позволяет для произвольной формулы в конечное число шагов определить, является ли она тавтологией.
Ясно, что данная проблема разрешима, поскольку всегда можно составить таблицу истинности для любой формулы.