Шпаргалка по "Логике"

Проблема  полноты исчисление высказываний

• Определение .Аксиоматическое исчисление высказываний называется полным в узком смысле, если добавление к списку его аксиом любой недоказуемой в исчислении формулы в качестве новой аксиомы приводит к противоречивому исчислению.
• Определение . Исчисление высказываний называется полным в широком смысле, если любая тождественно истинная формула в нем доказуема
• Проблема полноты исчисления высказываний содержит два вопроса:

Можно ли расширить систему аксиом аксиоматического исчисления путем добавления к ней  в качестве новой аксиомы какой-нибудь недоказуемой в этом исчислении формулы?

Является ли всякая тождественно истинная формула алгебры высказываний доказуемой  в исчислении высказываний?

Проблема  независимости аксиом исчисления высказываний.

Определение  Аксиома А называется независимой от всех остальных аксиом исчисления, если она не может быть выведена из остальных аксиом.

Определение Система аксиом исчисления называется независимой, если каждая аксиома системы независима.

В ИВ имеются два  правила вывода - подстановка и  modus ропепs (дедуктивного вывода).

   Правило подстановки применяется к имеющейся ППФ А, содержащей некоторый атом X. Одновременной заменой всех вхождений этого атома в А(X) на произвольную ППФ В мы получим формулу A(В), которую именуем результатом подстановки в ППФ А(X) формулы В.

   Если  А(X) – теорема ИВ, то A(В) – тоже теорема ИВ.

   Приведем  пример. Подставив в аксиому 8 ИВ формулу (С&D) вместо атома С, получаем следующую теорему ИВ:

            .

   Правило дедуктивного вывода (modus ponens) применяется к имеющейся паре ППФ А и А В; результатом применения данного правила является ППФ В. (MP(A, A=>B)=B)

   Если  A и А В являются теоремами ИВ, то В - также теорема ИВ.

Задание аксиом и правил вывода

В множестве  формул выделяется подмножество аксиом, и задается конечное число правил вывода — таких правил, с помощью которых (и только с помощью их) из аксиом и ранее выведенных теорем можно образовать новые теоремы. Все аксиомы также входят в число теорем. Иногда (например, в аксиоматике Пеано) теория содержит бесконечное количество аксиом, задающихся при помощи одной или нескольких схем аксиом. Аксиомы иногда называют «скрытыми определениями». Таким способом задается формальная теория (формальная аксиоматическая теория, формальное (логическое) исчисление).

Задание только аксиом

Задаются  только аксиомы, правила вывода считаются общеизвестными.

При таком задании теорем говорят, что  задана полуформальная аксиоматическая  теория.

Задание только правил вывода

Аксиом  нет (множество аксиом пусто), задаются только правила вывода.

По  сути, заданная таким образом теория — частный случай формальной, но имеет собственное название: теория естественного вывода.

Исчисление  высказываний: полнота, непротиворечивость, разрешимость(постройка таблиц)

Исчисление  предикатов: полнота, непротиворечивость

И арифметики: непротиворечивость

Аксиоматика Мендельсона:                    A1: A=>(B=>A)

                 A2: (A=>(B=>C))=>((A=>B)=>(A=>C))

                 A3: (⌐B=>⌐A)=>(( ⌐B=>A)=>B)

Аксиоматика Гильберта:                   а) AvA=>A

                б) A=>(AvB)

                в) (AvB)=>(BvA)

                г) (B=>C)=>((AvB)=>(AvC))

Теорема о полноте: А – такая и только такая, когда я является тавтологией. │- A iff │= A

Лемма о канонической замене: Если строка σ_1,… σ_n , то A₁ ^σ1,…A_n ^σn , тогда │- A ^σ – формула.

Алгоритм  Хорновской резолюции

Применять данный алгоритм можно только, если все дизьюнкты я вляются хорновскими.

Хорновский  дизъюнкт - дизъюнкт в котором не больше 1 буквы без отрицания.

Дизъюнкт  который состоит только из одной  буквы без отрицания называется фактом.

Перед началом работы алгоритма все  дизъюнкты записываем в отдельные столбци таблици.

1. Пока  есть не использованные факты  или пока нет пустых ячеек  в строке выполняем 2 пункт  иначе 3.

2. Выбираем 1 факт и вычеркиваем во всех  дизьюнктах данный факт с отрицанием.

3. Если  нет пустых ячеек то формула  не противоречие, иначе формула является противоречием.

Алгоритм Дэвиса-Патнема  
Данный алгоритм фактически представляет собой алгоритм Квайна для проверки выполнимости формулы, приведенной к КНФ.  
Исходные данные: формула, приведенная к КНФ.  
Возможный ответ: тавтология, нейтральная, противоречие.  
В начале для КНФ выписывается множество ее дизъюнктов, которое становится корнем семантического дерева. Для построения других вершин этого дерева введем понятия пустого дизъюнкта и пустого множества дизъюнктов. Пустым дизъюнктом называется дизъюнкт, тождественноравный 0 (очевидно, что такой дизъюнкт не имеет ни одной переменной, отсюда и название - пустой). Обозначать его будем □.  
Если КНФ тождественно равна 1, то будем говорить, что она представлена пустым множеством дизъюнктов, которое обозначим Æ.  
Пусть в качестве корня дерева задано множество дизъюнктов КНФ, не равное Æ. Получим для него два потомка, подставив вместо некоторой пропозициональной переменной 0, а затем 1 (приоритет для подстановки выше у той переменной, которая единственна в некотором дизъюнкте, если таких нет, то выбирается наиболее часто встречающаяся). Дуги помечаются переменной с указанием ее значения. Если в результате подстановки хотя бы один дизъюнкт стал равен 0 (а значит, и вся КНФ), то этот потомок обозначается □ (аналог 0). Если в результате подстановки дизъюнкт стал равен 1, то он удаляется из множества дизъюнктов потомка. Если дизъюнкт был последним из множества, то вершина обозначается Æ (аналог 1). Далее проверяются условия окончания:  
1. Все листья □ - формула противоречие.  
2. Все листья Æ - формула тавтология.  
3. Образованы листья □ и Æ — формула нейтральна.  
Если условия не выполнены, то для полученных вершин (не равных □ и Æ) образуются потомки аналогичным образом. И так далее (алгоритм рекурсивен).

Алгоритм  Вонга заключается в расписывании последовательности строк таким образом, что каждая последующая строка проще, чем предыдущая. Процедура продолжается до тех пор, пока не будет получено доказательство или опровержение. Строка включает произвольное число ППФ, располагающихся по обеим сторонам стрелочки, причем между собой ППФ разделяются запятыми. Доказательство проводится ниже.