- •Оглавление
- •Глава 1. Алгебраические системы 17
- •Глава 2. Элементы комбинаторики 88
- •Глава 3. Основы теории графов 101
- •Глава 4. Основы математической логики 169
- •4.1.1.4. Эквивалентные преобразования формул 179
- •4.1.4. Выполнить подстановку: 247
- •Глава 5. Основы теории алгоритмов 252
- •Глава 6. Конечные автоматы 289
- •Введение
- •Глава 1. Алгебраические системы
- •1.1 Множества
- •1.1.1. Четкие множества
- •1.1.2. Нечеткие множества
- •1.2. Соответствия, отображения и функции
- •1.2.1. Четкие отображения и функции
- •1.2.2. Нечеткие отображения
- •1.3. Отношение
- •1.3.1. Четкие отношения
- •1.3.2. Нечеткое отношение
- •1.4. Элементы общей алгебры
- •1.5. Булева алгебра
- •1.5.1. Булевы операции
- •1.5.2. Законы булевой алгебры
- •1.5.3. Формула булевой функции
- •1.5.4. Описание булевой функции
- •1.5.5. Суперпозиция булевых функций
- •1.5.6. Свойства булевых функций
- •1.5.6.1. Самодвойственные булевы функции
- •1.5.6.2. Монотонные булевы функции
- •1.5.6.3. Линейные булевы функции
- •1.5.6.4. Функции, сохраняющие “0”
- •1.5.6.5. Функции, сохраняющие “1”
- •1.5.6.6. Функционально полные системы
- •1.5.7. Разложение булевых функции
- •1.5.7.1. Днф булевой функции
- •1.5.7.2. Кнф булевой функции
- •Алгоритм преобразования формулы к скнф:
- •1.5.8. Минимизация булевых функций.
- •1.5.8.1.Минимизация днф булевой функции
- •1.5.8.2. Минимизация кнф булевой функции
- •1.6. Алгебра четких множеств
- •1.6.1. Операции над множествами
- •1.6.2. Законы алгебры множеств
- •1.6.3. Эквивалентные преобразования формул
- •1.6.4. Композиция отображений и отношений
- •1.6.5. Поиск неизвестного множества
- •1.7. Алгебра нечетких множеств
- •1.7.1. Операции над нечеткими множествами
- •1.7.2. Композиция нечетких отображений
- •1.7.3. Композиция нечетких отношений
- •1.7.4. Свойства нечетких отношений
- •Вопросы и задачи
- •Глава 2. Элементы комбинаторики
- •2.1. Размещение из n элементов по k
- •2.2. Перестановка элементов
- •2.3 Сочетание из n элементов по k
- •2.4. Разбиение множества
- •2. 5 Правила комбинаторики
- •Вопросы и задачи
- •Глава 3. Основы теории графов
- •3.1. Граф и его характеристики
- •3.2. Описание графа
- •3. 3. Числа графа
- •3.4. Операции над графами
- •3.4.1. Унарные операции
- •3.4.1.1 Поиск дополнительного графа
- •3.4.1.2. Введение и удаление вершин графа
- •3.4.1.3. Стягивание вершин графа
- •3.4.1.4. Введение и удаление ребер графа
- •3.4.1.5. Поиск плотности и неплотности графа
- •3.4.1.6. Поиск числа компонент связности графа
- •3.4.1.7. Поиск устойчивости графа
- •3.4.1.8. Поиск цикломатического числа графа
- •3.4.1.9. Поиск хроматического числа графа
- •3.4.2. Бинарные операции
- •3.4.2.1. Объединение графов
- •3.4.2.2. Пересечение графов
- •3.4.2.3. Композиция графов
- •3.4.2.4. Соединение графов
- •3.4.2.5. Прямое произведение графов
- •3.4.2.6. Изоморфизм графов
- •3.5. Некоторые алгоритмы на графах
- •3.5.1. Построение покрывающего остова
- •3.5.2. Построение остова минимального веса
- •3.5.3. Поиск кратчайших путей в сети.
- •3.5.4. Поиск максимального потока в сети
- •3.5.5. Метод критического пути в управлении
- •3.6. Нечеткие графы
- •Вопросы и задачи
- •Глава 4. Основы математической логики
- •4.1. Логика высказываний
- •4.1.1. Алгебра высказываний
- •4.1.1.1. Логические операции
- •4.1.1.2. Правила записи сложных формул.
- •4.1.1.3. Законы алгебры высказываний
- •4.1.1.4. Эквивалентные преобразования формул
- •4.1.1.5. Нормальные формы формул
- •4.1.2. Исчисление высказываний
- •4.1.2.1. Интерпретация формул
- •4.1.2.2. Аксиомы и правила введения и удаления логических связок
- •4.1.2.3. Метод дедуктивного вывода
- •4.1.2.4. Принцип резолюции
- •4. 2. Логика предикатов
- •4.2.1. Алгебра предикатов
- •4.2.1.1. Законы алгебры предикатов
- •4.2.1.2. Предваренная нормальная форма формулы
- •4.2.1.3 Сколемовская стандартная форма формулы
- •4. 2. 2. Исчисление предикатов
- •4.2.2.1. Правила подстановки
- •4.2.2.2. Правила введения и удаления кванторов
- •4.2.2.3. Правила заключения
- •4.2.2.4. Метод дедуктивного вывода
- •4.2.2.5. Принцип резолюции
- •4.2.2.6. Логическое программирование
- •4.3. Логика реляционная
- •4.3.1 Реляционная алгебра
- •4.3.1.1. Унарные операции
- •4.3.1.2. Бинарные операции
- •4.3.1.3. Правила реляционной алгебры
- •4.3.2. Реляционное исчисление
- •4.3.3. Языки реляционной логики
- •4.4. Нечеткая логика
- •4.4.1. Нечеткое исчисление
- •4.4.2. Экспертные системы
- •Вопросы и задачи
- •Глава 5. Основы теории алгоритмов
- •5.1. Рекурсивные функции
- •5.1.1. Базовые функции
- •5.1.2. Элементарные операции
- •5.2. Машина Тьюринга
- •5.2.1. Описание машины Тьюринга
- •5.2.2. Примеры машин Тьюринга
- •5.2.3. Композиция машин Тьюринга
- •5.3. Нормальные алгоритмы Маркова
- •5.4 Сложность вычислений
- •Вопросы и задачи
- •Глава 6. Конечные автоматы
- •6.1. Абстрактный автомат
- •6.1.1. Типы конечных автоматов
- •6.1.2. Описание автоматов
- •6.1.3. Автоматное моделирование алгоритмов
- •6.1.3.1. Автомат Мили - модель управляющего автомата
- •6.1.3.2. Автомат Мура - модель управляющего автомата
- •6.1.3.3. Микропрограммный автомат
- •6.1.4. Эквивалентность автоматов
- •6.1.5. Эквивалентность внутренних состояний автомата
- •6.1.5.1. Детерминированный автомат
- •6.1.5.2. Недетерминированный автомат
- •6.2. Структурный автомат
- •6.2.1. Произведение автоматов
- •6.2.1.1. Последовательное соединение автоматов
- •6.2.1.2. Параллельное соединение автоматов
- •Обратная связь автоматов
- •6.2.3. Сумма автоматов
- •6.2.4. Структурный автомат и кодирование
- •6.3. Логическое проектирование автоматов
- •6.3.1. Кодирование алфавитов автомата
- •6.3.2. Автоматы без “памяти”.
- •6.3.2.1. Формирование оператора
- •6.3.2.2. Формирование системы операторов
- •Логическая схема комбинационного автомата
- •6.3.3. Автоматы с “памятью”
- •6.3.3.1. Формирование оператора
- •6.3.3.2. Формирование оператора
- •.3.3.3. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
4. 2. Логика предикатов
Если объект высказывания, т.е. то, о чем говорится в предложении, не определен, то это предложение называют высказывательной функцией. Аргументами высказывательной функции являются предметные переменные и предметные постоянные, которые обозначают строчными буквами латинского алфавита {х, у, z...} и {а, в, с, } соответственно. Высказывательная функция приобретет значение "и" или "л" только при подстановке вместо предметных переменных их постоянных значений.
Высказывательную функцию иначе называют предикатом (лат. praedicatum - логическое сказуемое).
Например,
а) если на множестве натуральных чисел задать высказывательные функции:
Р1(x):= "x - простое число",
P2(6, y):="y меньше 6",
P3(6, y, z):="z есть частное от деления числа 6 на y",
где z и y есть предметные переменные (целые числа), а 6 – предметная постоянная (целое число), то высказываниями будут
P1(3) = и, P1(4) = л,
P2(6,2) = и, P2(6,7) = л,
P3(6,2,3) = и, P3(6,2,5) = л,
б) если на множестве имен индивидов, университетов и специальностей задать высказывательные функции или предикаты
P4(x):="х - студент",
P5(x, КГТУ):="студент х университета КГТУ",
P6(x, y, прикладная информатика):= "студент x университета y, обучающийся по специальности "прикладная информатика””,
где x и y есть предметные переменные, а КГТУ и “прикладная информатика” – предметные постоянные, то высказываниями будут
P4(Петров) = и, P4(Сидоров) = л,
P5(Петров, КГТУ) = и, P5(Сидоров, КГТУ) = л,
P6(Петров, КГТУ, "прикладная информатика") = и,
P6(Сидоров, КГТУ, "прикладная информатика") = л.
Для ограничения области определения предметных переменных вводят операторы, которые называют кванторами.
Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений у части переменных области определения, называют частным суждением. Как правило, эти суждения на естественном языке выражают словами "несколько", "часть" и т.п. Для формализации таких суждений используют логическую операцию, ограничивающую область определения предиката. Оператор, ограничивающий область определения. получил название квантора существования, который обозначают “x”. Предикат записывают после квантора существования в круглых скобках x(Рn(x)). На естественном языке эта запись означает: “существуют такие элементы х, что Рn(х) истинно".
Если частное суждение распространяется на несколько предметных переменных, то перед предикатом записывают кванторы существования для всех предметных переменных, по которым есть частное суждение, т.е. x y z...(Pn(x, y, z, ...)).
Например, x(P1(x)):= "cуществуют целые числа, которые являются простыми". Это условие выделяет на множестве целых чисел подмножество X = {2, 3, 5, 7, 11, ..}, для которого предикат P1(x) принимает значение “и”.
y(P22(6,y)):="существуют числа y, которые меньше 6". Это условие выделяет на множестве целых чисел подмножество Y= {1, 2, 3, 4, 5}, для которого предикат P2(6,y) принимает значение “и”.
z(P33(6,2,z)):="существует число z, которое является частным от деления 6 на 2". Это условие выделяет на множестве целых чисел единственное число Z=3, для которого предикат P3(6,2,z) принимает значение “и”.
Если P7(x):="x имеет зачетную книжку", то x(P4(x)&P7(x)):= "существуют студенты (x), которые не имеют зачетной книжки"; xy(P25(x,y)&P7(x)):="существуют студенты (x) некоторых университетов (y), которые не имеют зачетной книжки" и т.п..
Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений для всех переменных области определения, называют общими суждениями. Как правило, эти суждения в естественном языке отмечают словами "все", "каждый", "любой" и т.п. Для формализации этих суждений используют логическую операцию над всей областью определения предиката. Оператор этой логической операции получил название квантора всеобщности, который обозначают x. Предикат записывают после квантора всеобщности в круглых скобках.
x(Рn(x)) . На естественном языке эта формальная запись означает: “для всех х значение Рn(х) истинно“.
Если общее суждение распространяется на несколько предметных переменных, то перед предикатом записывают кванторы всеобщности для всех предметных переменных, по которым есть общее суждение, т.е.
x y z... (Pn(x, y, z, ...)).
Например, x(P4(x)&P7(x)):= "все студенты (x) имеют зачетную книжку";
xy(P5(x,y)&P7(x)):="все студенты (x) всех университетов (y) имеют зачетную книжку";
x(P36(x, КГТУ, "прикладная информатика")&P7(x)):= "все студенты (x) университета КГТУ, обучающиеся по специальности "прикладная информатика", имеют зачетную книжку";
xz(P36(x, КГТУ, z)&P7(x)):= "все студенты (x) университета КГТУ, обучающиеся на всех специальностях (z), имеют зачетную книжку";
xyz(P36(x,y,z)&P7(x)):= "все студенты (x) всех университетов (y), обучающиеся на всех специальностях (z), имеют зачетную книжку".
Существуют предикаты, для которых область определения по различным предметным переменным ограничивают различными кванторами.
Например,
xy(P22(x, y)):= "для всех целых чисел x существует меньшее число y".
xyz(P33(x, y, z)):="для всех целых чисел x и y существует число z, которое является частным от деления x на y".
Предметную переменную предиката, если по меньшей мере одно ее вхождение связано квантором, называют связанной переменной. Предметную переменную предиката, если все ее вхождения в формулу свободны от квантора, называют свободной переменной.
Например,
y(P22(x,y)):="для всех целых чисел x существуют меньшие числа y". В этом примере x – свободная, а y –связанная переменные.
x z(P36(x,y,z)&P7(x)):= “есть студенты университета, которые не имеют зачетной книжки”. В этом примере x и z –связанные, а y –свободная переменные.
x y (Р21 (x; y) z (Р2(z)) все предметные переменные связаны.
z (Р1(z)x(Р22(x; z))(Р22(z; y)(Р22(x; z)) предметные переменные x и z связанные, а y – свободная.
Cвободная переменнная есть переменная вне текущей процедуры, а связанная переменная есть локальная переменная для текущей процедуры.
Если высказывательная функция содержит один аргумент, то задан одноместный предикат, если она содержит n аргументов, то n-местный предикат. Одноместный предикат, как правило, описывает наличие какого-либо признака у предмета, а n-местный предикат – наличие отношений между n предметами.
Между элементами области определения может быть задана некоторая структура или функциональные отношения. Тогда функциональный символ f(x1, x2,...xn) указывает на задание этой структуры между предметными переменными и/или предметными постоянными.
Например, дату можно рассматривать как структуру, заданную на предметных переменных: число, месяц и год. В этом случае функциональным символом является “дата”, а аргументами число, месяц и год, т.е. “дата (число, месяц, год)”. Для предметных постоянных эта структура формирует выражение (например, “дата (1 января 2001)”). Описание треугольника также можно рассматривать как структуру на предметных переменных, описывающих координаты вершин треугольника. Тогда функциональным символом является “треугольник”, а аргументы этой функции следующие: вершина (координаты x1, y1), вершина (координаты x2, y2), вершина(координаты x3, y3).