- •Оглавление
- •Высказывания. Примеры высказываний. Пропозициональные переменные. Определения основных логических операций.
- •Теорема о подстановке ппф вместо пропозициональной переменной в тождественно истинной формуле.
- •Теорема о существовании эквивалентной днф
- •Теорема о существовании эквивалентной кнф
- •Теоремы о виде тождественно ложной днф, тождественно истинной кнф
- •Понятия сднф, скнф. Построение сднф, скнф по таблице истинности данной формулы.
- •Построение сднф по данной днф.
- •Построение скнф по данной кнф
- •Условия существования скнф, сднф
- •Понятие логического следствия в ав. Содержательный пример.
- •Непротиворечивые (выполнимые) и противоречивые (невыполнимые) множества посылок. Примеры.
- •Установление факта логического следствия из данного множества посылок по таблице истинности.
- •Установление факта логического следствия из данного множества посылок путем определения совместности соответствующей системы логических уравнений.
- •Понятие алгебраической системы данной сигнатуры
- •Характерные черты алгоритма
- •Элементы модели алгоритма
- •Основные предположения об элементах модели алгоритма
- •Устройство машины Тьюринга
- •Комбинации машин Тьюринга: композиция
- •Комбинации машин Тьюринга: разветвление
- •Комбинации машин Тьюринга: разветвление с циклом.
- •Вычислимые по Тьюрингу функции.
- •Разрешимые (рекурсивные) множества. Пример. Рекурсивно перечислимые множества. Пример.
- •Алгоритмически неразрешимые проблемы. Пример. Тезис Тьюринга.
Понятие алгебраической системы данной сигнатуры
Алгебраической системой сигнатурыназовем алгебраическую систему, в которой:
Каждому n-местному предикатному символу изсопоставленn-местный предикат из, заданный на М.
Каждому n-местному функциональному символу изсопоставленаn-местная функция из, заданная на М.
Каждой предметной константе изсопоставлен элемент
Свободные и связанные переменные. Термы, свободные для данной переменной в данной формуле.
Переменная называется свободной в ппф, если имеются свободные вхождения этой переменной в этой ппф.
Переменная называется связанной в ппф, если имеются связанные вхождения этой переменной в этой ппф.
Все свободные и связанные переменные обозначаются разными буквами.
Терм свободен для переменнойв формулеесли никакое свободное вхождениевне находится в области действия никакого квантораили, где– переменная, входящая в.
Значение терма данной сигнатуры в алгебраической системе той же сигнатуры. Пример.
Определим значение терма системы, все предметные переменные которого содержатся в наборев алгебраической системепри значениях переменныхсоответственно следующим образом:
Если есть константа, то значениеесть значение
Если есть переменная, то значениеесть
Если , асоответственно, тосогласно функции
Пример:
Пусть , тогда
Значение ппф АП данной сигнатуры в алгебраической системе той же сигнатуры
Значение в алгебраической системеприопределим следующим образом:
Если , тотолько если
в, иначе
Если , тотолько еслии, иначе
Если , тотолько еслиииначе
Если , тотолько еслиииначе
Если , тотолько еслии наоборот.
Если , тотолько еслидля всех, иначе
Если , тотолько еслихотя бы для одного, иначе
Кванторыикак обобщения логических связок & и.
Если М – конечное основное множество алгебраической системы сигнатуры,– ппф данной сигнатуры, то предложенияи, где, имеют одно и то же значение.
Если М – конечное основное множество алгебраической системы сигнатуры,– ппф данной сигнатуры, то предложенияиимеют одно и то же значение.
Выполнимые формулы АП. Пример.
Ппф сигнатурыназовем выполнимой, если существует такая алгебраическая система, чтоистинна впри некоторых значениях свободных предметных переменных.
Пример:
выполнима.
Тождественно истинные формулы АП. Пример доказательства тождественной истинности.
Ппф сигнатурыназовем тождественно истинной, еслиистинна в любой алгебраической системе сигнатурыпри любых значениях свободных предметных переменных.
Пример:
– тождественно истинная.
Доказательство производится методом от противного, тоесть
такое возможно лишь при, что невозможно.
Эквивалентные формулы АП. Пример.
Две ппф алгебры предикатов исигнатурыназываются эквивалентными, если они принимают одинаковые значения (tилиf) в любых алгебраических системах данной сигнатуры. Факт эквивалентности ппфизаписывается в виде.
Если они эквивалентны только в какой-то алгебраической системе , то факт эквивалентности записывается как(а внизу такая хуевинка
Пример:
в любой алгебраической системе
эквивалентны лишь в системе с одноместной базой (вместоxТОЛЬКОtили ТОЛЬКОf)
Теорема о замене подформулы на эквивалентную подформулу в ппф алгебры предикатов.
Пусть – подформула,, тогда
Теорема о подстановке ппф вместо атомной формулы в эквивалентные ппф алгебры предикатов
Пусть - ппф сигнатуры,– атомная формула, тогда если
Пренексные нормальные формы. Теорема о существовании эквивалентной пнф: алгоритм получения эквивалентной пнф.
Пусть Qобозначает некоторый кванторили. Тогда ппф вида, где– бескванторная формула, называетсяпренексной нормальной формой.
Теорема о существовании:
Для любой ппф алгебры предикатов существует эквивалентная ей пренексная форма.
Алгоритм получения:
Исключаем
Продвигаем до атома.
Переименовываем связанные переменные
Вынесим кванторы
Сколемовская стандартная форма (ссф): основная теорема, функции Сколема.
Пренексная форма вида называется сколемовской.
Основная теорема:
Пусть предложение сигнатурыимеет вид
Также пусть –nместные функциональные символы.
Пусть предложение сигнатурыимеет вид
Тогда для любой алгебраической системы существует алгебраическая систематакая, что значениевсовпадает со значением.
- обогащение, а– обеднение. Функции, вводимые вместо кванторов, называются функциями Сколема.
Сколемовская стандартная форма (ссф): следствие основной теоремы.
Пренексная форма вида называется сколемовской.
Следствие:
Для любого предложения сигнатурысуществует некотороепредложениерасширенной сигнатуры, полученное добавлением кновых функциональных символов, и обладающее свойством: для любой алгебраической системысуществует обогащениетакое, что значениевсовпадает со значениемв.
Сколемовская стандартная форма(ссф): процедура построения, алгоритм Сколема.
Алгоритм Сколема:
Представить исходное предложение в виде пнф
Найти квантор
Если квантор самый первый, то заменить все вхожденияна
Если нет, то заменить все вхождения на
Повторять до усеру.
Понятие логического следствия в АП. Пример.
Ппф сигнатурыназывается логическим следствием множества формултой же сигнатуры в алгебре предикатов, если в любой алгебраической системеппфполучает значениеtкаждый раз, как каждая ппф ппфпринимает значениеtв этой системе.
Пример:
Пусть ,.
Рассмотрим произвольную алгебраическую модель . Пусть в этой модели, тогда, значит. Значит.
Выполнимые и невыполнимые множества посылок в АП
Множество посылок выполнимо в алгебре предикатов, если найдется алгебраическая система соответствующей сигнатуры такая, что в базе этой системы существует набор значений свободных переменных, на котором все формулы изпринимают значениеt.
Множество посылок невыполнимо в АП, если в любой алгебраической системе соответствующей сигнатуры для любого набора значений свободных предметных переменных найдется ппф, значение которой =f.
Понятие резольвенты в АВ. Пример.
Пусть – кнф,– элементарные дизъюнкции (дизъюнкты).
Резольвентой дизъюнктов назовем дизъюнкт
Теорема о свойстве резольвенты.
или
Основная теорема
Кнф тождественно ложно тогда и только тогда, когда тождественно ложна кнф
Формулировка принципа резолюции в АВ
Пусть - некоторое множество дизъюнктов и пусть для, где– резольвента некоторой пары дизъюнктов из. Тогда, если для некоторогоi, то кнф.
Схема применения принципа резолюции для доказательства факта логического следствия в АВ. Пример применения принципа резолюции для доказательства факта логического следствия.
Необходимо определить, имеет ли место факт логического следствия
Образуем ппф
Для строим эквивалентную ей кнф
Образуем и применяем принцип резолюции. Если на каком-то шагеi-1 получаем «пустой дизъюнкт» - тождественно ложную резольвенту, то
Пример:
Проверим
видим чтообразуют контрарную пару литер и дают, значит
Схема построения модели алгоритма
Выделение основных свойств (характерных черт, присущих алгоритму)
Определение основных элементов модели, исходя из выделенных характерных черт.
Принятие основных предположений об элементах модели (установление основных ограничений)
В рамках принятых предположений построение и анализ конкретных моделей алгоритмов
Установление взаимосвязи между различными моделями алгоритмов.