- •Формулы логики высказываний и логики предикатов
- •Равносильность в логике высказываний и влогике предикатов
- •Тавтологии
- •Понятие предиката. Кванторы
- •Нормальные формулы логики предикатов
- •Языки. Аксиомы. Правила вывода
- •Вывод. Вывод из гипотез
- •Теорема Дедукции. Следствия
- •Примеры выводимых формул
- •Непротиворечивость ив
- •Полнота ив
- •Правило суммы, произведения
- •Размещения и сочетания
- •Бином Ньютона
- •Разбиение. Полиномиальная теорема
- •Булевы функции
- •Формулы. Равносильность формул
- •Метод рекуррентных соотношений
- •Решение линейных рекуррентных соотношений
- •Понятие производящей функции
- •Интуитивное понятие алгоритма
- •Машины Тьюринга. Вычислимые функции
- •Рекурсивные функции
- •Алгоритмически неразрешимые проблемы
- •Нумерации машин Тьюринга
- •Критерии эффективности алгоритма
- •Полиномиальные и неполиномиальные алгоритмы
- •Основные понятия теории графов
- •Маршруты, цепи, циклы
- •Виды графов
- •Способы задания графов
- •Эйлеровы графы
- •Геометрическая реализация графов
- •Деревья. Лес.
- •Остовное дерево
- •Важнейшие числовые характеристики графов
- •Основные понятия теории кодирования
- •Критерий однозначности алфавитного кодирования
- •Алгоритм распознавания однозначности кодирования
- •Коды Хэмминга
- •Понятие множества
- •Операции над множествами. Свойства
- •Формулы включения и исключения.
-
Нормальные формулы логики предикатов
Df. 2.7: Формула называется приведенной, если она удовлетворяет условиям:
-
В формуле нет символов .
-
Знак отрицания относится только лишь к символам элементарных высказываний и предикатов.
Зам: Пользуясь имеющимися равносильностями, каждую формулу можно преобразовать в равносильную ей нормальную.
Df 2.18: Приведенная формула называется нормальной, если в ней нет кванторов либо кванторы вынесены за скобки.
Теор 2.2: Каждую формулу логики предикатов можно преобразовать в равносильную ей нормальную формулу.
Д-во: Пусть дана формула А. Будем считать, что она уже является приведенной, и доказательство теоремы проведем по принципу математической индукции относительно g(A) – числа символов операции в формуле А. (А=. ) С) g(А) = 3);
-
g(А)=0, т.е. ф-ла А не содержит символов операции и поэтому является нормальной.
-
Пусть для всех формул, имеющих не более, чем k символов операций, доказываемое высказывание выполняется. Докажем теорему для такой формулы А, что g(А) = k+1. Для А возможны следующие случаи:
Сл.1: А=(В). Т.к. g(A)=k+1 и А= А=(В), то g(В)=k. Поэтому по индуктивному предположению ф-ла В является нормальной, а приписывая слева к нормальной формуле квантор мы вновь получаем нормальную формулу.
Сл.2: А=(В). Этот случай рассматривается аналогично случаю 1.
Сл.3: А=. Т.к. g(A)=k+1 и А=, то g(B)=k. Поэтому по индуктивному предположению формула В является нормальной. Тогда, избавляясь вначале от отрицания над кванторами, а затем от отрицания над операциями логики высказываний, мы получаем нормальную формулу.
Сл.4: А=В С. Т.к. g(A)=k+1 и А=В С, то g(B)k, g(C)k. Поэтому по индуктивному предположению формулы В и С являются нормальными. Тогда, переименовывая в формулах В и С связные переменные по равносильностям 35,36 так, чтобы они стали различными, а затем, вынося кванторы за скобки, мы получим нормальную формулу.
Сл.5: А=В С. Этот случай рассматривается аналогично случаю 4. Чтд.
-
Языки. Аксиомы. Правила вывода
Df. При исследовании высказываний используется Аксиоматическая теория, которая называется ИВ.
Каждая аксиоматическая теория имеет 3 характерные черты:
-
Язык.
Он состоит из алфавита и способа образования формул.
Df. 3.1: Алфавитом называется множества попарно различных символов.
Df. 3.2: Алфавит исчислений высказываний(ИВ) состоит из следующих 3 групп символов:
- Большие печатные буквы латинского алфавита: А, В, С, …;
- следующие символы: ;
- скобки: (, );
Зам: При построении аксиоматической теории разрешается пользоваться только лишь символами алфавита этой теории.
Способы образования формул – это те правила, по которым строят формулы. В ИВ такими правилами являются следующие:
- Каждый символ 1-ой группы алфавита является формулой;
- если А- формула, то и – так же является формулой;
- если А и В - формулы, то и () – тоже формула;
- других формул нет.
Зам: В определение формулы использовались формулы А,В алфавиту. Такие символы называются метасимволами, и они являются удобным средством для сокращений записи.
Зам: Символам алфавита не придается, пока, никакого содержательного смысла.
-
Аксиомы.
Во множестве формул каждой аксиоматической теории выделяют некоторое подмножество, формулы которого и объявляют аксиомы. В ИВ все аксиомы задаются с помощью следующих схем:
1. ;
2.(А;
3. ;
-
Правила вывода
Они позволяют из данных формул получать новые. В ИВ имеется единственное правило вывода:
Modus ponens(MP) – это правило будучи примененным к формулам вида А и АВ дает формулу В.