Приведённая формула — формула, в которой из логических символов имеются только символы конъюнкции , дизъюнкции и отрицания ¬ , причём отрицание встречается лишь перед символом предиката.
Нормальная формула — формула, в которой все кванторы стоят в начале или отсутствуют.
Теорема (о существовании равносильной приведённой формулы для любой формулы). Для любой формулы в ИП существует равносильная ей приведённая формула, причём множества свободных и связанных переменных этих двух формул совпадают.
Теорема (о существовании равносильной нормальной формулы для любой приведённой). Для любой приведённой формулы существует равносильная ей нормальная формула, причём длины обоих формул совпадают.
Из этих двух теорем сразу же следует общая теорема.
Теорема (о существовании равносильной приведённой нормальной формулы для любой формулы). Для любой формулы в ИП существует равносильная ей приведённая нормальная формула.
17. Выполнимость и общезначимость формул ИП. Общезначимость формул
( ) ( ), ( ) ( ).
Формула в ИП называется выполнимой, если существует хотя бы одна интерпретация, в которой выполнима (принимает истинное значение).
Пример. : ( ) ¬ ( ) ≡ 0 в любой интерпретации невыполнима.
Формула в ИП называется выполнимой в данной интерпретации , если существует хотя бы один набор 1, 2, … , , значений свободных переменных формулы такой, что эта формула принимает значение 1: | 1,2,…, = 1.
Формула в ИП называется истинной в данной интерпретации , если она принимает значение 1 на любом наборе 1, 2, … , , значений своих свободных переменных.
Формула в ИП называется общезначимой или тождественно-истинной, если она истинна в любой возможной интерпретации.
Пример 1. : ( ) ¬ ( ) ≡ 1 в любой интерпретации, то есть эта формула общезначима. Этот логический закон называется «закон исключённого третьего».
Пример 2. Пусть ( , , ): < на множестве {1,2,3}3 , то есть на {1,2,3} × {1,2,3} × {1,2,3}. Рассмотрим формулу ( )( ) ( , , ). Эта формула выполнима, например, при = 3. Действительно:
= 1 3 1 < 32 = 2
= 2 3 2 < 32 = 2
= 3 3 3 < 33 = 3
Однако, если = 1, то ( )( )(1 < 1 ) не выполнима, так как при любых нетакой , что 1 < 1 .
Делаем вывод: формула не общезначима.
Теорема. Формула общезначима тогда и только тогда, когда ¬ — невыполнима и формула выполнима тогда и только тогда, когда ¬ не является общезначимой.
Действительно, если ≡ 1, то ¬ = 0, то есть невыполнима.
Если ≡ 1 в какой-то интерпретации, то есть выполнима, то ¬ = 0 в этой интерпретации, то есть не является общезначимой.
Замечание. Очевидно, что если и равносильные в ИП формулы, то формула ≡
— общезначимая формула, что позволяет получать новые общезначимые формулы. Докажем общезначимость некоторых формул.
Теорема 1. Пусть ( ) формула в ИП, в которой — свободная переменная, а не входит в формулу ( ) (но мы считаем, что и берутся из одной и той же интерпретации). Тогда формула ( )( ) ( ) общезначима.
Действительно, если формула ( ) ( ) при каких-то конкретных значениях свободных переменных (в любой возможной интерпретации) принимает значение 0, то формула ( )( ) ( ) принимает значение 1. Если же ( )( ) принимает значение 1, то очевидно, и ( ) также принимает значение 1. Таким образом, формула ( )( ) ( ) в любой возможной интерпретации всегда принимает значение 1, то есть она общезначима.
Теорема 2. Пусть ( ) формула в ИП, в которой — свободная переменная, а не входит в формулу ( ) (но мы считаем, что и берутся из одной и той же интерпретации). Тогда формула ( ) ( ) ( ) общезначима.
Действительно, если ( ) = 0, то формула ( ) ( ) принимает значение 1 в силу свойства импликации. Если же для какого-то (при конкретном наборе других свободных переменных) ( ) = 1, то и формула ( ) также примет значение 1 и, значит, формула ( ) ( ) будет истинной, а значит и общезначимой.
Покажем, что общезначимость формулы теоремы 2 есть следствие общезначимости формулы теоремы 1.
Подставим в формулу теоремы 1 вместо — ¬:
( )(¬( )) ¬ ( ) ≡ | ≡ ¬ | ≡ ¬( )(¬( )) ¬ ( )
≡ ( )(¬¬( )) ¬ ( ) ≡ ¬ ( ) ( )( ) ≡ ( ) ( )( )
Теорема 3. Пусть — тождественно-истинная формула ИВ, 1, 2, … , — набор её переменных. Если вместо каждой переменной подставить формулы логики ИП так, чтобы не нарушались пункты 1-4 определения формулы ИП, то получим общезначимую формулу ИП.
Задача распознавания общезначимости формул ИП существенно сложнее, чем формул ИВ. Действительно, в ИВ можно по таблицам истинности установить тождественную истинность.
В ИП неприменим метод перебора всех вариантов наборов переменных, так как их может быть ∞ много (если интерпретаций ∞). В общем случае эта так называемая «проблема разрешимости» в ИП неразрешима.
Теорема Чёрча. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, логически общезначима формула или нет.
Однако в некоторых частных случаях, например, если рассматривать только одноместные предикаты, эта проблема разрешима, то есть существует алгоритм распознавания общезначимости формулы. Такая логика, в которой употребляются только одноместные предикаты, была описана ещё Аристотелем.
Поэтому в ИП выделение общезначимых формул осуществляется путём указания некоторой совокупности формул (аксиом) и правил вывода, позволяющих из общезначимых формул получать общезначимые.
18. Аксиомы ИП. Общезначимость аксиом ИП. Правила вывода ИП. Оформление ИП как ФАТ
Аксиомы ИП (для любых формул ИП , , ):
А1. ( ).
А2. ( ( )) (( ) ( )). А3. (¬ ¬) ((¬ ) ).
А4. ( ) ( ) ( ), где формула ( ) не содержит переменной . А5. ( ) ( ) ( ), где формула ( ) не содержит переменной . Первые три аксиомы аналогичны аксиомам ИВ.
Теорема. Все аксиомы ИП — общезначимые формулы. Для аксиом А1, А2 и А3 это следует из теории ИВ. Для аксиом А4 и А5 — это следует из доказанных теорем для
( ) ( ) и для ( ) ( ) (см. 17-ый вопрос).
Правила вывода:
1.Правило modus ponens (. .): , B.
2.Правило связывания квантором всеобщности ( не содержит ):
( ) B ( ) ( )
3.Правило связывания квантором существования ( не содержит ):
( ) ( ) ( )
4.Правило переименования связанной переменной. Связанную переменную формулы (в кванторе и во всех вхождениях в области действия квантора) можно обозначить другой переменной, не являющейся свободной переменной формулы .
Понятия вывода, теоремы, вывода из системы гипотез определяются в ИП так же, как
ив любой аксиоматической теории (ФАТ). Теорема (ослабленная теорема дедукции).
Если , и существует вывод в ИП, построенный с применением только правила . ., то . Доказательство аналогично доказательству теоремы дедукции ИВ.
19. Теорема об общезначимости формул ИП, получающихся из общезначимых по любому из 4-х правил вывода ИП
Предложение. Формула, получающаяся из общезначимой формулы с помощью правил вывода 1-4, является общезначимой.
Доказательство.
1) Для правила вывода 1 (. .) наше утверждение следует из свойств импликации.
, !, |
≡ 1, |
≡ 1, |
1 ≡ 1 |
Значит и ≡ 1. |
|
|
|
2)Рассмотрим правило вывода 2 ( ( ) ( ) ( )). Пусть ( ) — общезначимая формула. Докажем, что формула ( ) ( ) тоже общезначима. Возможны два случая.
a)на произвольном наборе своих свободных переменных принимает значение 1 (истина). Тогда по свойству импликации 1 ( ) ≡ 1, то есть ( ) ≡ 1, то есть ( ) ( ) ≡ 1 . Отсюда следует, что на любом наборе аргументов формулы : ( ) ( ) ≡ 1.
b)на каком-то наборе своих свободных переменных принимает значение 0
(ложь), но тогда ( ) ( ) = 1, то есть в любом случае B ( ) ( ) ≡ 1.
3)Рассмотрим правило вывода 3 (( ) ( ) ( ) ). Пусть формула ( )
общезначима. Докажем, что и формула ( ) ( ) также общезначима.
a)Если формула ( ) ( ) (для каких-то значений свободных переменных) принимает значение 0, то для этих значений свободных переменных по свойству импликации формула ( ) ( ) принимает значение 1.
b)Если же ( ) ( ) (для каких-то значений свободных переменных) принимает значение 1 и так как ( ) общезначима, то принимает значение 1 и,
значит, формула ( ) ( ) принимает значение 1, следовательно, ( ) ( ) ≡ 1, то есть эта формула общезначима.
4)То, что правило вывода 4 сохраняет общезначимость, очевидно из свойств кванторов.
Так как аксиомы исчисления предикатов — общезначимые формулы (см. 18-ый вопрос) и формула, получающаяся из общезначимой формулы с помощью правил вывода 1-4, является общезначимой (как показано выше), то любая выводимая из аксиом формула в ИП является общезначимой.
20. Полнота и непротиворечивость ИП. Теорема Гёделя. Тезис Чёрча
Так как аксиомы исчисления предикатов — общезначимые формулы (см. 18-ый вопрос) и формула, получающаяся из общезначимой формулы с помощью правил вывода 1-4, является общезначимой (см. 19-ый вопрос), то любая выводимая из аксиом формула в ИП является общезначимой.
Знаменитый немецкий математик-логик Курт Гёдель доказал и обратное утверждение.
Теорема (о выводимости формул в ИП). Формула в ИП выводима (из аксиом), если
итолько если она общезначима. То есть выводимость в ИП общезначимость. Из этой теоремы сразу же следует.
Теорема (о непротиворечивости). Исчисление предикатов — непротиворечивая теория. Непротиворечивая, так как не могут быть одновременно общезначимы (то есть тождественно истинны в любой возможной интерпретации) формулы и ¬.
Теорема Гёделя (о полноте исчисления предикатов). Всякая общезначимая формула выводима в исчислении предикатов.
Таким образом, в ИП формула выводима (из аксиом) тогда и только тогда, когда она общезначима. Однако не существует алгоритма, позволяющего определить общезначимость любой формулы. Это связано с тем обстоятельством, что
интерпретация предикатов может содержать бесконечные возможные значения переменных.
21. Алгоритмы. Определение (интуитивное) алгоритма. Свойства алгоритмов. Направления поисков точного определения алгоритма. Вычислимые функции.
Проблема алгоритмической неразрешимости
Алгоритм — (интуитивное определение) общая определенная последовательность элементарных действий, приводящая к решению любой задачи из данной массовой проблемы.
Слово «алгоритм» происходит от имени узбекского математика XIII века Абу ал Хорезми. Оно претерпело эволюцию: ал Хорезми – ал Горезми – алгоритм.
Примеры алгоритмов:
•Алгоритм Эвклида (правило отыскания наибольшего общего делителя).
•Правило отыскания решений квадратного уравнения.
•Правило отыскания производной от многочлена степени.
•Правило интегрирования рациональных дробей.
Вкаждом из приведённых примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров.
Свойства алгоритмов:
•Дискретность — изначально задаётся исходная конечная система величин (параметров), и на каждом следующем шаге система величин получается по определенному закону из системы величин, имевшихся на предыдущем шаге.
•Детерминированность (определённость) — система величин, получаемых на каком-то шаге, однозначно определяется системой величин, полученных на предыдущем шаге.
•Элементарность каждого шага — решение задачи разбивается на этапы, каждый из которых должен быть простым.
•Результативность (направленность) — последовательный процесс построения системы величин должен быть конечным и давать результат, то есть решение задачи.
•Массовость — начальная система величин может выбираться из некоторого потенциально бесконечного множества (то есть алгоритм служит не для решения какой-то одной задачи, а для целого класса однотипных задач).
Для того, чтобы доказать существование алгоритма, достаточно дать описание фактического процесса, решающего задачу и здесь достаточно интуитивного понятия алгоритма.
Если же нужно доказать, что алгоритм решения такой задачи не существует, то нужно знать точно, что такое алгоритм, то есть знать строгое математическое определение алгоритма.
В 30-е годы 20-го века шли интенсивные поиски строгого определения понятия алгоритма. В подходе к решению этой задачи были выделены три основных направления:
1.Первое направление связано с уточнением понятия вычислимой функции (Чёрч, Гёдель, Клини). В результате был выделен класс так называемых частично-