авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

СЕРВИСА (ПВГУС)»

Кафедра «Высшая математика»

СОГЛАСОВАНО УТВЕРЖДАЮ

Протокол УМС № Проректор по УР и КО

от «»_ 2009 г. _ О.Н. Наумова Проректор по УМР С.П. Ермишин КОНСПЕКТ ЛЕКЦИЙ по курсу «Математическая логика и теория алгоритмов»

для студентов специальности 230100.62 «Информатика и вычислительная техника»

Составитель: М.С. Спирина 5 СОДЕРЖАНИЕ Введение 5 Лекция №1. Логика высказываний 1.1. Определения логических операций 1.2. Формулы логики высказываний 1.3. Тавтология алгебры высказываний 1.4. Нормальные формы формул логики высказываний Лекция №2. Логика предикатов. Язык логики предикатов 2.1. Высказывательные формы 2.2. Язык логики предикатов 2.3. Кванторы 2.4. Формулы 2.5. Логические операции над предикатами 2.6. Логическое следование 2.7. Равносильности логики предикатов 2.8. Нормальные формы логики предикатов 2.9. Клаузальная нормальная форма 2.10. Общезначимость формул логики предикатов Лекция № 3. Основы теории формальных систем. Требования, предъявляемые к формальным системам. Аксиоматические системы 3.1. Принцип дедукции 3.2. Аксиоматический метод 3.3. Аксиоматические теории 3.4. Требования, предъявляемые к формальным системам 3.5. Теоремы Геделя 3.6. Интерпретация формальной теории 3.7. Проблемы аксиоматического построения исчисления высказываний 3.8. Проблемы аксиоматического построения исчисления предикатов 3.9. Формальная аксиоматическая теория для арифметики натуральных чисел Лекция №4. Исчисление высказываний 4.1. Язык исчисления высказываний 4.2. Логическое следование 4.3. Метод резолюций в ИВ 4.4. Дизъюнкты Хорна. Метод резолюций для хорновских дизъюнктов. Лекция № 5. Исчисление предикатов 5.1. Язык исчисления предикатов 5.2. Формулы исчисления предикатов 5.3. Теоремы исчисления предикатов 5.4. Метод резолюций в логике предикатов 5.5. Общезначимость формул исчисления предикатов 5.6. Принцип логического программирования Лекция № 6. Формализация понятия алгоритма. Рекурсивные функции.

Машина Тьюринга 6.1. Понятие алгоритмической системы 6.2. Рекурсивные и вычислимые функции 6.3. Примитивно рекурсивные предикаты 6.4. Машина Тьюринга Лекция № 7. Основы нечеткой логики 7.1.

Модальная логика 7.2. Темпоральные (временные) логики 7.3. Алгоритмические логики 7.4. Нечеткая логика Лекция № 8. Сложность вычислений 8.1. Алгоритмически неразрешимые проблемы 8.2. Меры сложности алгоритмов 8.3. Классы сложности 8.4. Сложность алгоритмов Математические символы, обозначения и сокращения Список литературы Практика последних десятилетий XX века показывает, что логика высказываний является эффективным инструментом для решения как гуманитарных, так и многих технических задач. Например, при конструировании и оснащении ЭВМ инженерам и программистам вместо того, чтобы работать с контактными схемами, достаточно произвести необходимые известные логические операции. Однако, логики высказываний недостаточно для конструирования умозаключений, необходимых для работы интеллектуальных машин. Для обработки текстов естественного языка для ЭВМ необходимо создание особых логических языков – некоторых формальных систем. Они должны удовлетворять известным требованиям непротиворечивости, полноты и др. для того, чтобы избежать различных логических ошибок и парадоксов. При работе с интеллектуальными машинами для того, чтобы они могли выполнять умозаключения, т.е.

«мыслить», необходимо с помощью аппарата математической логики создать такую теорию, которая удовлетворяла бы всем перечисленным требованиям. Установлено, что такой формальной системой являются исчисления предикатов первого порядка. Наиболее важный прикладной характер логики предикатов заключается в поиске эффективной процедуры обоснования равносильностей, в ней применяемых.

Таким образом, проблема построения умозаключений за два тысячелетия своего существования нисколько не устарела, а даже приобрела особое значение. Так, работа будущих интеллектуальных машин нового поколения будет основана на идее логического программирования, в связи с чем востребованность в построении формальных систем будет возрастать. Поэтому необходимо познакомиться с видами умозаключений, известными из классической логики, также с правилами выводов, которые проще и доступнее сформулированы в исчислении предикатов.

Лекция №1. Логика высказываний Основные законы алгебры логики, способы проверки формул на равносильность, приемы приведения логических формул к конъюнктивной и дизъюнктивной нормальным формам (КНФ и ДНФ), а также минимальной дизъюнктивной нормальной форме.

Совершенные формы.

1.1. Определения логических операций. Всякое суждение (повествовательное предложение), утверждающее что-либо о чем-либо, называют высказыванием, если о нем можно сказать, истинно оно или ложно в данных условиях места и времени.

Характеристика суждения по признаку истинности-ложности называется семантической.

Если простое высказывание является истинным, то ему соответствует значение логической переменной 1. Если простое высказывание является ложным, то ему соответствует значение логической переменной 0.

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

Связка называется унарной, если она применима только к одному высказыванию. Связка называется бинарной, если она применима к двум высказываниям.

не содержащие Тогда утвердительные предложения логические связки называют содержащие элементарными высказываниями.

составными Истинность составных высказываний определяется только истинностью входящих в него составных высказываний.

Для того, чтобы определить, истинно или ложно некоторое сложное высказывание, используют таблицы истинности, в которых латинскими буквами обозначаются сами высказывания, а цифрами 1 и 0 их семантическая характеристика — соответственно «истина» или «ложь».

Введем определения логических операций («словарь перевода» естественного языка на язык алгебры высказываний (алгебры логики) представлен в табл.1):

– Отрицанием или инверсией высказывания A называется высказывание А, которое истинно, когда высказывание A ложно, и ложно, когда A истинно.

– Дизъюнкцией (нестрогой или соединительной) высказываний A и B называется высказывание AB, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.

Высказывание на Соответствие Название Таблица Круги русском языке в алгебре операции истинности Эйлера логики Не A;

Отрица- А А неверно, что A;

ние, A, A 1 А A A не имеет места инверсия 0 A или B;

A B 2 Дизъюнк AB AB или A, или B, или оба ция 1 1 B вместе (соединит 1 0 A ельная) 0 1 0 0 Либо A, либо B;

AB A B AB 3 Строгая A или B, но не оба дизъюнкц 1 1 AB А вместе ия 1 0 1 В (разделит 0 1 ельная) 0 0 A и B;

A B AB 4 Конъюнк AB как A, так и B;

ция 1 1 AB A не только A, но и B;

1 0 A B B A вместе с B;

0 1 A&B A, несмотря на B;

0 0 A, в то время как B Если A, то B;

A только A B AB 5 Имплика AB если B;

A достаточно ция, 1 1 1 В для B;

B необходимо следова- 1 0 0 А для A;

A влечет B;

из A ние 0 1 следует B 0 0 A эквивалентно B;

A A B 6 Тождеств AB AB енность, 1 тогда и только тогда, AB A B когда B;

A, если и равносиль 1 0 AB только если B;

A ность, 0 1 необходимо и эквивален 0 0 достаточно для B ция Табл.1. Словарь перевода естественного языка на язык алгебры высказываний – Конъюнкцией высказываний A и B называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания.

– Строгой дизъюнкцией высказываний A и B называется высказывание A B, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний.

– Импликацией высказываний A и B называется высказывание AB, которое ложно тогда и только тогда, когда из истины следует ложь.

– Эквиваленцией высказываний A и B называется высказывание AB, которое истинно тогда и только тогда, когда оба высказывания либо истинны, либо ложны одновременно.

Высказывание BA является обратным для высказывания AB.

обратные AB (основное) BA противо- противо положные положные обратные A B B A (противопоста вление обратному) Рис. Высказывание A B является противоположным к импликации AB.

Диагональные стрелки рис.1 показывают одновременную истинность (т.е. эквиваленцию) соответствующих высказываний. Равенство A B B A называется правилом контрапозиции (от лат. contrapositio – противопоставление).

Пример 1. Проверим истинность полученных обратных и противоположных высказываний с помощью таблицы дл высказывания «Если ABCD – ромб, то его диагонали взаимно перпендикулярны» (табл.2.):

Если ABCD - ромб, то его диагонали взаимно перпендикулярны AB (или: «Перпендикулярность диагоналей АС и BD – необходимое (прямая условие для того, чтобы четырехугольник ABCD был ромбом) импликация) «Если диагонали взаимно перпендикулярны, то ABCD – ромб»

BA (ложное) (обратная Т.к. взаимно перпендикулярные диагонали могут быть и у импликация) некоторого вида четырехугольников.

«Если ABCD – не ромб, то его диагонали не взаимно AB (противоположная перпендикулярны» (ложное) Например, ABCD – четырехугольник, причем AСВD, но в теорема) точке пересечения не делятся пополам.

«Если у четырехугольника диагонали не взаимно BA перпендикулярны, то этот четырехугольник - не ромб»

(противоположная (истинное высказывание).

обратной) Табл.2.

Существуют такие высказывания, для которых одновременно справедливы и прямая, и обратная импликации: т.е. AB и BA истинны. Такие высказывания называются равносильными или эквивалентными, а логическая операция, справедливая (выполняющаюся, истинная) на эквивалентных высказываниях, и только на них, называется эквиваленцией. На языке логических операций A B ( A B ) ( B A).

1.2. Формулы логики высказываний. Высказывательными или пропозициональными переменными (элементарными высказываниями) называют такие переменные, вместо которых можно подставить конкретные высказывания.

В математической логике для определения понятий часто пользуются индуктивными (рекурсивным) определениями, которые обычно состоят из трех пунктов, двух прямых и одного косвенного. Первые два пункта состоят из нескольких подпунктов. В первом пункте – «базисе индукции» указываются исходные объекты (элементарные объекты), которые следует непосредственно относить к определяемому понятию. Во втором пункте – «шаге индукции» задается порождающее правило, позволяющее получать из заданных новые объекты относящиеся к определяемому понятию. В третьем пункте утверждается, что никаких других объектов, кроме описанных в первых двух пунктах, не существует.

Дадим определение (индуктивное) формулы алгебры высказываний:

а) Элементарные высказывания и символы логических переменных есть формулы.

F1, F б) Если есть формулы алгебры высказываний, то F1, F1 F2, F1 F2, F1 F2, F1 F2, F1 F2 есть формулы алгебры высказываний.

в) Других формул алгебры высказываний нет.

В процессе формализации учтем следующие правила:

1) простому высказыванию соответствует элементарная формула;

2) для построения формулы, соответствующей составному высказыванию, надо:

а) выделить все элементарные высказывания и логические связки, соответствующие структуре высказывания;

б) заменить их соответствующими символами;

в) расставить скобки в соответствии с логической структурой высказывания.

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

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

Двойственность логических операций заключается в том, что если в формуле, содержащей операции дизъюнкции, конъюнкции и отрицания, заменить операции и на и соответственно, а символы 1 на 0, а 0 на 1, то получатся новые равносильности, сохраняющие структуру формулы, т.е. соответствующий порядок действий. Примеры двойственных операций – в аналогичных законах для операций дизъюнкции и конъюнкции: (табл.3) Табл. Законы Дизъюнкция Конъюнкция аb = bа 1 Переместительный закон ab = ba a(bc) = (аb)c 2 Сочетательный закон a(bc) = (ab)c 3 Распределительный закон a(bc) = аbаc a(bc) = (ab)(ac) 4 Правила идемпотентности aa=a aa = a 5 Законы Де Моргана a b a b ab a b 6 Правила операций с a0 = a a0 = константами.

7 a1=1 a1 = a 8 Законы aаb = a a(ab) = a поглощения 9 a( a b) = ab a( a b) = аb 10 Законы инверсии(отрицания) a a = 1 a a = 11 аba b =a Законы склеивания (ab)(a b )=a 12 a a – Снятие двойного отрицания.

13. ab= a b – Снятие импликации.

14. ab=аb a b – Снятие эквиваленции.

15. a b= ab ab – Снятие строгой дизъюнкции Соглашения о написании формул.

Для упрощения формул, содержащих скобки и различные логические операции, будем учитывать ряд правил. Так, при опускании скобок:

1) внешние скобки не используются;

2) действия в скобках выполняются в первую очередь;

3) учитываются приоритеты логических операций в порядке возрастания: отрицание, следствие, конъюнкция, дизъюнкция.

а) самой первой выполняется конъюнкция между элементарными высказываниями и их отрицаниями;

б) дизъюнкция выполняется раньше импликации и эквиваленции;

в) знак отрицания над формулой дает возможность опустить скобки, в которых эта формула заключена.

Рангом формулы называется число логических операций, встречаемых в этой формуле, причем каждая операция учитывается столько раз, сколько раз она в ней встретилась. Так, в последней формуле ранг равен трем.

Интерпретацией формулы в логике высказываний называется приписывание каждой элементарной формуле, входящей в составную, истинностного значения 1 (И) или 0 (Л). Интерпретация, при которой формула истинна, называется моделью данной формулы.

1.3. Тавтология алгебры высказываний. Формула F ( x1, x2,..., xn ) называется выполнимой, если существует такой набор высказываний a1,a2,…,an, который опровержимой истинное обращает эту формулу в высказывание.

ложное истинной тавтологией Формула называется тождественно, если она или ложной противоречием истинно принимает значение при всех значениях переменных, входящих в нее.

ложно Так, тавтологиями будут: 1) a a ;

2) a ( b a );

3) a (a (b a )).

Чтобы проверить, является ли некоторая формула тавтологией, достаточно построить для нее таблицу истинности. Если самый правый из столбцов – столбец значений, содержит единицы (истина), и только единицы, то формула есть тавтология.

Если в этом столбце присутствует хотя бы один ноль (ложь), то эта формула тавтологией не является. Если в этом столбце все значения – нули, то эта формула есть противоречие.

Если хотя бы при одном наборе значений переменных, формула истинна, то она выполнима.

1.4. Нормальные формы формул логики высказываний. Минимизируют формулы логики высказываний, приводя их к нормальным формам: дизъюнктивной (ДНФ) и конъюнкцией конъюнктом конъюнктивной (КНФ). Элементарной называется дизъюнкцией дизъюнктом выражение, состоящее из конечного числа переменных и их отрицаний, взятых не более конъюнкции Дизъюнктивной нормальной одного раза и разделенных операциями.

дизъюнкции Конъюнктивной ДНФ дизъюнкция конъюнктов формой называется конечного числа.

КНФ дизъюнктов конъюнкция Нормальная форма называется совершенной КНФ, или СКНФ (совершенной ДНФ или СДНФ), если в каждом дизъюнкте (конъюнкте) представлены все переменные, входящие в данную формулу (либо сами, либо с отрицанием).

На СДНФ накладываются требования:

1) формула не является тождественно ложной;

2) формула приведена к одному из видов ДНФ;

3) удалены элементарные конъюнкции, включающие одновременно переменную и ее отрицание (согласно закона инверсии);

4) удалены одинаковые элементарные конъюнкции, кроме одной (согласно правилу идемпотентности);

5) каждая элементарная конъюнкция в ДНФ включает все логические переменные, входящие в эту формулу.

Если в формуле не выполняется требование 5), то в неполную элементарную конъюнкцию необходимо ввести дополнительный множитель, включающий дизъюнкцию отсутствующей переменной и ее отрицание (т.к. согласно закону инверсии a a 1, а 1a = a).

Аналогично, любую формулу, имеющую вид ДНФ, можно привести к СКНФ, для которой выполняются требования:

1) формула не является тождественно ложной;

2) формула приведена к одному из видов КНФ;

3) удалены одинаковые элементарные дизъюнкции, кроме одной;

4) каждая элементарная дизъюнкция в КНФ включает все логические переменные, входящие в эту формулу.

Если формула имеет вид КНФ, то привести ее к виду совершенной КНФ (т.е.

СКНФ) можно, дополняя каждую элементарную дизъюнкцию логическим нулем. В следующем шаге логический ноль заменяется конъюнкцией недостающей переменной и ее отрицания. Для сравнения приведем примеры нормальных форм, расположив их в табл.4.:

Формы Конъюнктивные Дизъюнктивные Нормальные КНФ ДНФ х1 х 2 х1 х3 х1 х 2 х1 х Совершенные СКНФ СДНФ нормальные х1 х 2 х3 х1 х 2 х3 х1 х 2 х3 х1 х 2 х3 х1 х 2 х Табл.4.

Для того чтобы привести формулу к совершенной нормальной форме (СНФ) надо:

1) Используя равносильности алгебры логики, заменить все имеющиеся операции на конъюнкцию, дизъюнкцию и отрицание.

2) Применяя законы де Моргана, снять отрицание с логических операций конъюнкции и дизъюнкции.

3) Используя распределительный и другие законы, привести формулу к нормальной форме.

4) Используя законы идемпотентности, склеивания и др., минимизировать полученные булевы выражения.

5) Применяя правила операций с константами, привести минимизированные нормальные формы к совершенному виду.

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

Выделим формулы алгебры высказываний ранга 0 и представим их ДНФ и КНФ:

0 x x x (x ) и 1 x x x x.

Формула x является одновременно и ДНФ, и КНФ.

Любая формула алгебры логики может быть представлена множеством различных дизъюнктивных форм, равносильных между собой.

Пример: F1 ( x1, x 2, x3 ) x1 x1 x3 x1 x 2 x3 x1 x1 x2 x3 x1 x1 x2 x3 x1 x 2 x3 x1 x 2 x3 и т.д.

Минимальная или сокращенная нормальная форма получается из совершенной конъюнктивной дизъюнкций нормальной формы удалением некоторых элементарных дизъюнктивной конъюнкций КНФ согласно основным равносильностям. Тупиковой нормальной формой называется, ДНФ конъюнкции из которой нельзя удалить ни одной элементарной так, чтобы сохранить дизъюнкции неизменной заданную формулу.

Литература: [1], ч.1;

[2], гл.1, 5;

[3], гл.1, 2;

[4], гл.1, 2;

[6], гл.1, [7], гл.2, п.2.1, 2.2;

[8], гл.4;

[9], гл.8;

[10], гл.2-11;

[13], гл.6.

Лекция №2. Логика предикатов. Язык логики предикатов Высказывательные формы. Понятие предиката и квантора, их классификация.

Логические операции над предикатами, операции логического следования и включения.

Клаузальная нормальная форма.

2.1. Высказывательные формы. Логика высказываний не дает возможности выполнять действия с суждениями, содержащими переменные. Значительное число различных, причем не только математических предметных областей, представленных с помощью переменных, могут быть описаны средствами логики предикатов.

В логике предикатов предложение с n переменными из множества M, которое превращается в высказывание при любой подстановке вместо всех его переменных каких либо элементов из множества M, называется высказывательной формой с n переменными во множестве M. Язык логики предикатов дает возможность формализовать заданную предметную область, представив высказывательные формы в виде формул, а затем доказать их общезначимость или непротиворечивость.

Одноместным предикатом P(x) называется всякая функция одной переменной, в которой аргумент принимает любые значения из некоторого множества M, а сама функция при этом принимает одно из значений 0 (ложь) или 1 (истина).

Множество M, на котором задан предикат, называется областью определения предиката. Произвольная функция P:МnB, заданная на произвольном множестве M, называется n-местным предикатом P(х1,…, хn). Т.о., предикат есть логическая функция, заданная на произвольном множестве M, принимающая значения 0 или 1 на этом множестве.

Пример 2. Рассмотрим двухместную высказывательную форму x 1 y, где x определено на множестве Мх={4;

7}, а y – на множестве Мy={1;

5;

9}. Этой форме соответствуют два предиката Р1 и Р2, определенные на множествах M x M y и M y M x, которые образованы с помощью декартова произведения двух множеств. Сравним предикаты Р1(x;

y) и Р2(x;

y)=Р1(y;

x) по табл.5.

Р1(x;

y) Р2(x;

y) x 1 y x 1 y M x M y :(x;

y) M y M x :(y;

x) (4;

1) 0 (1;

4) 51 (4;

5) 1 (1;

7) 55 (4;

9) 1 (5;

4) 59 (7;

1) 0 (5;

7) 81 (7;

5) 0 (9;

4) 85 (7;

9) 1 (9;

7) 89 Табл. Отсюда видно, что двухместная высказывательная форма, вообще говоря, определяет два различных предиката.

Принято одноместный предикат называть «предикатом-свойством», n-местный (для n1, n) – «предикатом-отношением», 0-местный предикат – высказыванием.

Тождественно истинным называется предикат, множество истинности которого совпадает с его областью определения. Тождественно ложным называется предикат, множество истинности которого пусто.

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

Пусть даны две высказывательные формы, определенные на одном множестве. Такие высказывательные формы Ф1 и Ф2 назовем равносильными или эквивалентными, если при любом наборе значений переменных, входящих в них, высказывательные формы принимают одинаковые значения истинности, т.е. Ф1Ф2, Ф1~Ф2 или Ф1Ф2.

2.2. Язык логики предикатов. Алфавит логики предикатов:

1) предметные переменные X, Y, Z, Xi, Yi, …, т.е. отдельные предметы – «имена» в указанной предметной области;

2) предметные константы x0, y0, z0, a, b, c, аi, bi,… – принимающие значения 0 и 1 в указанной предметной области;

3) предикатные переменные P, Q, R,…;

4) переменные высказывания p, q, r … –, принимающие два значения: 1 (истина) и (ложь), тогда p0, q0, r0, … – фиксированные значения.

5) символы логических операций,, ( ),, (, ) ;

6) кванторные символы, ;

7) вспомогательные символы ( ), – запятая и скобки.

Термы, кванторы и формулы логики предикатов.

Терм – выражение на языке логики предикатов, которое аналогично имени объекта.

Понятие формулы и терма введем рекурсивно (через «предыдущее»).

Определим понятие терма:

а) Всякая предметная константа и всякая предметная переменная есть терм.

б) Если t1, t2, …,tn – термы, а f – функциональная переменная, то f(t1, t2,…,tn) – терм.

в) Других термов, кроме определенных в пунктах а) и б) логика предикатов не имеет.

2.3. Кванторы. Для количественных характеристик в логике предикатов используют понятия все, некоторые, существуют и другие, которые называют кванторами (от лат.

quantum – сколько).

Символ x называется квантором общности и читается «для любого x», «для всех x». Квантор общности x P(x) превращает предикат P(x) в высказывание «Для любого x высказывание P(x) – истинно».

Символ x называется квантором существования и читается «существует x».

Квантор существования x P(x) превращает предикат P(x) в высказывание «Существует такой элемент x, что высказывание P(x) – истинно». Часть формулы, на которую распространяется действие квантора, называется областью действия этого квантора: в формуле x P(x) областью действия квантора x служит предикат P(x).

Если переменная расположена либо непосредственно после знака квантора, либо в области действий квантора, после которого стоит переменная, то ее вхождение в формулу называется связным. Все прочие вхождения – свободные. Переменная называется свободной, если после подстановки вместо нее имени некоторых конкретных объектов предикат превращается в осмысленное предложение. Так, переменная x в предикате P(x) является свободной.

Так, для одноместного предиката предложение «По меньшей мере один объект обладает свойством P» имеет тот же смысл, что и предложение «Существует хотя бы один объект, обладающий свойством P»: xP (x).

2.4. Формулы. Слово в алфавите логики предикатов называется формулой или правильно построенным словом, если оно удовлетворяет требованиям:

а) переменные есть формулы;

б) Если A,B – формулы, x – переменная, то A(x),( A ), (AB), A B, A B,x A(x, …) и x A(x, …) – формулы, а их свободные переменные – свободные переменные формул A и B;

в) других формул, кроме определенных в пунктах а) и б), нет.

Если в формулу вместо свободных переменных подставить термы, то получатся новые формулы. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисления высказываний, а также большинство правил вывода умозаключений из классической логики. Поэтому язык логики предикатов даёт возможность анализировать рассуждения естественного языка, а также науки, делать выводы в различных формальных системах.

Отдельно можно выделить понятие атомарной формулы: если P – символ предиката, (t1, t2, …,tn) – термы, то P(t1, t2, …,tn) – атомарная формула (атом). Терм формулой не является.

Например, термами являются выражения 5x, x+y-z, ax 2 bx c, x 4, f(x), f(x+ t) и т.д.

Формулами являются P(x)= «x=1», P(f(x)), P( ax 2 bx c ).

2.5. Логические операции над предикатами. Над предикатами можно выполнять операции, аналогичные тем, которые выполняются в алгебре высказываний.

Пусть, например, P(x) и Q(x) – одноместные предикаты, которые определены на множестве D причем T(P) и T(Q) – их множества истинности.

Отрицанием предиката P(x) называется предикат Р (х), также определенный на множестве D и истинный при тех значениях D\T(P) D переменной x, при которой P(x) ложен, т.е. Т ( Р ) D \ Т ( Р ). (рис.2).

T(P) Аналогично вводятся и остальные операции.

Конъюнкция предикатов P(x,…) и Q(x,…) есть новый предикат Р ( х) Q( x), определенный на множестве D и истинный при тех Рис. значениях переменной x, при которой истинны одновременно оба предиката P(x,…) и Q(x,…), поэтому ( Q) T ( P ) T (Q).

Дизъюнкцией предикатов P(x,…) и Q(x,…) называется предикат Р ( х) Q ( x), определенный на множестве D и истинный при тех значениях переменной x, при которых истинен хотя бы один из предикатов P(x) или Q(x). Поэтому Т ( Р Q ) T ( P ) T (Q ).

Импликацией предиката P(x,…) в Q(x,…) называется предикат Р ( х) Q ( x), определенный на множестве D и ложный только при тех значениях переменной x, при которой предикат P(x,…) истинен, а предикат Q(x,…) ложен.

Эквиваленцией предикатов P(x,…) и Q(x,…) называется предикат Р ( х) Q ( x) определенный на множестве D и истинный при тех значениях переменной x, при которых либо оба предиката истинны, либо оба предиката ложны.

Для двухместного предиката «Не более одного объекта обладает свойством P»

тождественно предложение «Если есть объекты, обладающие свойством P, то они совпадают»: x, y ( P ( x) P ( y ) x y ). Тогда предложение «Один и только один объект обладает свойством P» является конъюнкцией этих предложений.

Предложения «По меньшей мере два объекта обладают свойством P» и «Существуют несовпадающие объекты x и y, которые обладают свойством P»

тождественны между собой и символически записываются в виде:

xy ( P ( x) P ( y ) x y ).

Предложения «Не более, чем два объекта обладают свойством P» и «Каковы бы ни были объекты x, y, z, если все они обладают свойством P, то, по меньшей мере два из них совпадают» тождественны между собой и могут быть записаны символически:

x, y, z ( P ( x) P ( y ) P ( z )) ( x y ) ( x z ) ( y z ).

Тогда, конъюнкция двух последних предложений будет читаться «Два и только два объекта обладают свойством P». Например, «Уравнение ax2+bx+c=0 имеет не более двух действительных корней» и «Уравнение вида ax3+bx2+cx+d=0 имеет хотя бы один действительный корень» («не менее одного», «по меньшей мере один» – возможные варианты словосочетаний).

Определение формулы лежит в основе так называемой логики предикатов первого порядка, в которой разрешается квантифицировать (связывать кванторами) только предметные переменные. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисления высказываний, а также большинство правил вывода умозаключений из классической логики. Поэтому язык логики предикатов даёт возможность анализировать рассуждения естественного языка, а также науки, делать выводы в различных формальных системах.

Так, высказывательная форма p Q ( x) q является формулой. В то же время х Р ( х ) Q ( x ) высказывательная форма не будет формулой;

в формуле x P (x) переменная x связана квантором существования, тогда как в формуле Q(x) эта же переменная свободна.

Между кванторами и и логическими операциями существует тесная связь.

Пусть предикат P(x) определен на конечном множестве D a1, a 2,..., а n. Тогда высказывание x D P ( x) будет истинным только в том случае, если истинны одновременно все высказывания P (a1 ), P (a 2 ), P (a n ), т.е. если истинна их конъюнкция:

P (a1 ) P (a 2 ) P (a n ).

Аналогично, высказывание xP (x) означает, что оно истинно, когда истинно хотя бы одно из высказываний P (a1 ), P (a 2 ), P (a n ). Тогда должна быть истинной дизъюнкция высказываний P (a1 ) P (a 2 ) P (a n ).

Поэтому для конечной области определения выполняются равносильности:

(x D) P ( x) P (a1 ) P (a 2 ) P (a n ) и (x D) P ( x) P (a1 ) P (a 2 ) P (a n ) Таким образом, кванторы общности и существования являются обобщениями соответственно логических операций конъюнкции и дизъюнкции.

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

Пусть высказывательные формы Ф1(x1, x2, …, xn) и Ф2(x1, x2, …, xn) соответствуют предикатам P1 и P2, а их множества истинности соответственно T(P1) и T(P2). Поскольку Ф1|=Ф2, то если (x1, x2, …, xn) T(P1), т.е. Ф1 истинна, то должна быть истинна Ф2, т.е. (x1, x2, …, xn) T(P2). Поскольку такое свойство должно быть у любого элемента из T(P1), то это определение подмножества. Итак, T(P1)T(P2). Если Ф1 Ф2, а Ф2 Ф1, то Ф1Ф2.

Тогда T(P1) = T(P2). Т.о., две формулы равносильны тогда, и только тогда, когда каждая из них является логическим следствием другой. Для операции логического следования справедливо Ф1 Ф2 Ф1 Ф2.

2.7. Равносильности логики предикатов 1 xyQ( x, y ) yxQ( x, y ) Правила xyQ( x, y ) yxQ( x, y ) перестановки одноименных кванторов 2 xyQ( x, y ) yxQ( x, y ) Перенос xF ( x) x F ( x) xF ( x) x F ( x) 3 отрицания с квантора на 4 x F ( x) xF ( x) x F ( x) xF ( x) предикат 5 x( F ( x) Ф( х)) x( F ( x) Ф( х)) xF ( x) xФ( x) хF ( x) хФ( х) Правила 6 х( F ( x) ( хФ( ) F ( ) ( ) )) дистрибутивности хF ( х) х х ( F ( x) ( )) кванторов 7 x( M F ( x)) M xF ( x ) 7 x( M F ( x)) M xF ( x ) 8 x( M F ( x)) M xF ( x ) 8 x( M F ( x)) M xF ( x ) 9 хР( х) х Р ( х) хР( х) х Р ( х) Табл.6.

В частности, равносильность (3) (табл.6.) означает, что если не существует x, при которых истинным будет P(x), то для всех x истинно P(x). Эта равносильность может также быть записана в виде: хР( х) ( х) Р ( х).

Равносильность (3) означает, что если не для всех x истинно F(x), то существует x, при которых истинным будет F(x). Эта равносильность может также быть записана в виде: хР( х) х Р ( х).

Равносильности (9) и (9) получаются из равносильностей (3) и (3) соответственно, если от обеих их частей взять отрицание и воспользоваться законом снятия двойного отрицания.

2.8. Нормальные формы логики предикатов. Формулы, содержащие в качестве логических символов только стандартный базис: ( ),,, где символ встречается только перед элементарными (атомарными) подформулами, называются приведенными.

xP ( x) yQ ( y, z ) Так формула является приведенной, а формула P( x) Q ( y, z ) (или ( P ( x) Q ( y, z )) ) – не является.

Приведенная формула называется нормальной, если она содержит все символы кванторов впереди или не содержит кванторов вообще (т.е. логические символы и символы предикатов стоят в области действия каждого квантора).

Назовем длиной формулы общее число входящих в нее символов предикатов, кванторов и логических символов. Доказано, что для любой приведенной формулы логики предикатов есть равносильная ей нормальная формула той же длины.

Предваренная нормальная форма. Формула A логики предикатов задана в предваренной (пренексной) нормальной форме, если она имеет вид Q1x1… Qnxn B(x1,…, xn,), где Qi – квантор или, а формула B(x1,…, xn,) не содержит кванторов и приведена к КНФ. Если пренексная форма содержит только квантор, она называется скулемовской.

Под скулемовскими функциями понимают константы и функции, используемые для замены переменных квантора существования.

Доказано, что любую формулу логики предикатов можно привести к предваренной нормальной форме. Для этого надо:

1) исключить из формул все вхождения связок, с помощью эквивалентных преобразований (13) ab= a b – снятие импликации и (14) ab=аb a b – снятие эквиваленции;

2) перенести все вхождения символа отрицания с квантора на предикат с помощью эквивалентных преобразований 3, 3, 4, 4, а также законов де Моргана и др;

3) вынести все кванторы из формул в их начало, за скобки, с помощью эквивалентных преобразований 7, 7;

4) из формул исключаются кванторы существования, а переменные, связанные этими кванторами, заменяются скулемовскими функциями;

5) в стандартной форме все кванторы общности переносятся в начало формулы;

область действия каждого из них включается в формулу. Поэтому кванторы больше не несут никакой информации и опускаются;

6) формула приводится к КНФ с помощью эквивалентных преобразований;

7) символы конъюнкции тоже исключаются, и все формулы распадаются на множество дизъюнктов.

Преобразование к стандартному виду можно выполнять независимо от того, существует или нет интерпретация, при которой формула истинна. К образовавшемуся множеству применим метод резолюций.

Пример 3. Приведем к предваренной нормальной форме (ПНФ) формулу Ф xyP ( x, y ) xyQ ( x, y ).

Решение: С помощью эквивалентных преобразований имеем:

xyP ( x, y ) xyQ ( x, y ) xyP ( x, y ) x, yQ ( x, y ) x(yP ( x, y ) zQ ( x, z )) xy ( P ( x, y ) zQ ( x, z )) xy z ( P ( x, y ) Q ( x, z )).

2.9. Клаузальная нормальная форма. КНФ формулы логики предикатов называется клаузальной нормальной формой.

Пример 4. Приведем к пренексной и клаузальной формам формулу:

x(yP( x, y ) yQ ( x, y ) x (yP ( x, y ) yQ ( x, y )) x(yP( x, y ) yQ ( x, y ) x (yP ( x, y ) yQ ( x, y )) x(yP( x, y ) yQ ( x, y ) x (yP ( x, y ) yQ ( x, y )) x(yP ( x, y ) yQ ( x, y ) x (yP ( x, y ) yQ ( x, y )) x(yP ( x, y ) yQ ( x, y ) x(yP ( x, y ) y Q ( x, y )) x(yP ( x, y ) yQ ( x, y ) x (yP ( x, y ) y Q ( x, y )) xyuvw(P ( x, u ) Q ( x, y ) P (v, w) Q (v, w).

Получили пренексную нормальную форму. Введем подстановку для получения клаузальной нормальной формы:

x x, y y y, u u h( x, y ), v v f ( x, y ), w w g ( x, y ).

Тогда формула примет вид:

P ( x, h( x, y )) Q ( x, y ) P ( f ( x, y ), g ( x, y )) Q ( f ( x, y ), h ( x, y )).

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

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

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

В логике под интерпретацией понимается истолкование, разъяснение смысла, значения языкового выражения;

приписывание конкретного содержательного смысла, значения символам и формулам формального языка: рассмотрение его как языка, описывающего некоторую предметную область. Для данной интерпретации каждая формула без свободных переменных есть высказывание, которое может быть истинным либо ложным. Каждая формула, содержащая свободные переменные, есть предикат на множестве M, который может быть истинным при одних значениях из этого множества и ложным при других.

Литература: [2], ч.2;

[3], гл.IV;

[4], гл.2;

[6], гл.2;

[7], гл.2;

[8], гл.4;

[9], гл.9;

[10], гл.14;

[12], гл.2.

Лекция № 3. Основы теории формальных систем. Требования, предъявляемые к формальным системам. Аксиоматические системы Принцип дедукции. Аксиоматические системы. Формальный вывод.

Метатеория формальных систем. Аксиоматический метод построения формальных систем. Требования, предъявляемые к формальным системам: непротиворечивость, полнота, независимость. Теоремы Геделя. Метатеория и метаязык. Синтаксис и семантика языка логики предикатов. Исчисления. Интерпретации.

3.1. Принцип дедукции. Под умозаключением понимают форму мышления, посредством которой из одного или нескольких суждений на основании правил выводится новое суждение. В состав умозаключения входят посылки, вывод и заключение.

По направлениям логического следования умозаключения делятся на:

– дедуктивные – от общих суждений к частным, – индуктивные – от частных суждений к общим, – по аналогии (традуктивные) – от частных суждений к частным.

Правильные дедуктивные умозаключения образуются через отношение логического следования между посылкой и заключением: из истинных посылок, если соблюдены все необходимые правила выводов (т.е. импликация истинна), может следовать только истинное заключение. Поэтому дедуктивные умозаключения — самый строгий вид умозаключений, который при соблюдении всех правил всегда дает достоверный результат. Принцип дедукции ориентирует на применение дедуктивных умозаключений как основного вида рассуждений, применяемых в математике.

На рубеже IXX и XX века в математике сложилась ненормальная ситуация, связанная с обнаружением парадоксов теории множеств. В частности, в теории множеств, которая выстраивалась как строгая дедуктивная наука, были обнаружены противоречия, когда одно и тоже суждение одновременно и доказывается, и опровергается.

Чтобы спасти математику от парадоксов теории множеств, разрушающих ее основы, Гильбертом была предложена программа построения математических теорий, которую назвали формальной или «формализмом». Идея формализма заключалась в том, что всякую теорию, в том числе классическую математику, надо строить как дедуктивную науку, т.е. формальную аксиоматическую систему, а затем в рамках формализма попытаться обосновать ее характерные особенности: полноту, непротиворечивость, независимость и разрешимость. Одним из условий, накладываемых на формальную систему, является конструктивное оперирование с бесконечными совокупностями объектов, как с потенциально строящимися, а не как с окончательно завершенными.

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

а) неопределяемые понятия, с помощью которых дают определения всем остальным математическим понятиям;

б) аксиомы – утверждения, принимаемые без доказательства: («фундамент», на котором строится «здание» науки);

в) теоремы – утверждения, истинность которых необходимо доказать с помощью аксиом и, ранее доказанных теорем («строительный» материал для построения «здания» науки).

В зависимости то избранной системы аксиом и неопределяемых понятий выстраивается и сама наука.

3.3. Аксиоматические теории. Аксиоматическая теория, построенная на основе данной системы аксиом есть совокупность всех теорем, доказываемых исходя из этой системы аксиом. Аксиоматические теории делятся на формальные и неформальные.

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

Свойства формальных систем:

1) Дискретность, которая проявляется в том, что дискретный характер носят и сами объекты системы, и правила их соединений друг с другом конечным числом способов.

2) Формальность, суть которой заключается в соблюдении ряда принципов, таких как принцип педантизма (все, что в системе делается, подчинено строго определенным правилам), принцип явного описания (все условия применения правил и действия, которые надо совершать при их применении, формализуются явно) и др.

Такой формальный подход принципиально важен в различных системах, имеющих дело с множеством однотипных объектов, при описании точных наук, а особенно при общении с ЭВМ, когда необходимо четко описать каждый шаг. Функционируя строго по правилам, формальная система задает некоторую модель, используемую в различных ситуациях. Но при реальном применении модели элементы формальной системы наполняются конкретным содержанием. Этот процесс называют интерпретацией формальной системы в некоторой предметной области. Уровень изучения формальных систем есть метауровень, т.е. уровень работы с объектами, которые используются для описания иных различных предметных областей.

Представлением системы называется любой способ рассмотрения объектов формальной системы как конкретных объектов, полученных из опыта (эмпирически), при условии, что содержательные объекты сохраняют структуру формальных.

Формальная аксиоматическая теория считается определенной, если выполнены следующие условия:

1) задан язык теории;

2) определено понятие формулы в этой теории;

3) выделено некоторое множество формул, называемых аксиомами;

4) определены правила вывода в этой теории.

Язык формальной системы представляет собой совокупность цепочек в некотором алфавите. К формальным языкам, в частности, относятся искусственные языки для общения человека с машиной – языки программирования. Последовательность правил, используемых в процессе порождения некоторой цепочки, является ее выводом.

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

Любая формальная аксиоматическая теория T задается следующим образом:

1) Выделен алфавит A – непустое конечное множество символов, которые следует понимать единственным определенным образом. Каждый элемент (символ) алфавита принято называть буквой, а совокупность символов – словом или выражением над A.

Пустая последовательность букв называется пустым словом и обозначается.

Множеством всех выражений над алфавитом A будет бесконечное множество A m, которое назовем C.

A A 2 A 3... A m...

m 2) Определено некоторое подмножество выражений, называемых формулами теории T (правильно построенные выражения).

Для этого из множества всех слов C выделяем некое подмножество FC, характеристическое свойство которого, отличающее F от C\F, заключается в том, что его составляют только те выражения, которые «имеют смысл». Элементы множества F называются формулами над алфавитом A.

3) Выделено некоторое множество формул, называемых аксиомами теории T.

На содержательном, т.е. неформальном уровне – аксиомы есть формулы, по определению считающиеся истинными.

Пусть задано множество f=f1, f2, …, fnFn – набор формул. Образуем декартово произведение FnF, и выделим из него некое подмножество R: RFnF – отношение между двумя множествами. Это отношение назовем правилом вывода. Если пара (f,g), где f = f1, f2, …, fnFn, а gF, принадлежит R (т.е. (f,g)R или f R g), то формула g называется непосредственным следствием формул f1, f2, …, fn или непосредственно выводимым выражением из формул f1, f2, …, fn, полученным по правилу вывода R.

Основным требованием считается конечность правил вывода: совокупность отношений {R1, R2, …, Rk}, которую далее будем обозначать R, – конечна. Если существует RlR, такое, что (f1, f2, …, fn, g)Rl, то g называется непосредственным следствием формул f1, f2, …, fn (безотносительно одного определенного правила вывода), что обозначается f, f,..., f n f1, f2, …, fn |=g или 1 1.

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

4) Во множестве формул F выделим подмножество PF, элементы которого назовем аксиомами теории. Выбор этого подмножества опять же произволен: это те формулы, которые (условно) можно считать «априорно истинными», т.е. истинными изначально и безоговорочно.

5) Формула h называется выводимой из формул {f1, f2, …, fn}=Г или следствием формул Г, если существует кортеж формул g1, g2, …, gpFp, такой что gp=h, и ip gi P Gi, где Gi={g Г, g1, g2, …, gi-1|= g}, т.е. каждая формула в цепочке является либо аксиомой теории T, либо исходной формулой, либо непосредственно выводимой из предыдущих (непосредственное следствие каких-либо).

Тогда кортеж g1, g2, …, gp называется выводом или доказательством формулы h, а набор {f1, f2, …, fn} – гипотезами или посылками, что обозначается: Г |– h или f1, f2, …, fn |– h называется секвенцией. Аксиомы всегда подразумеваются в качестве посылок, поэтому как гипотезы в явном виде они не пишутся. Очевидно, что если Г |=h, то Г |– h.

Вывод есть последовательное проведение элементарных шагов, составляющее доказательное рассуждение.

6) Формула h называется теоремой теории T, если существует вывод, в котором последней формулой является h, т.е., если Г = и Г |– h и формула является следствием только аксиом.

Вместо записи |– h обычно используют |– h. Каждый элемент g1, g2, …, gp вывода теоремы h также является теоремой. Т.о., теоремы в аксиоматической теории - это формулы, которые могут быть выведены из аксиом по принятым правилам.

7) Заданные алфавит, множество формул, аксиомы и правила вывода, т.е. совокупность T=A, F, P, R, называется формальной системой (теорией) T.

Т.о., формальная система – это математическая модель, задающая множество дискретных объектов с помощью описания некоторых исходных объектов и правил построения новых объектов из исходных и уже построенных.

Под объектами мы понимаем символические и графические представления о ситуациях, состояниях, различных системах связей и информационных структур.

3.4. Требования, предъявляемые к формальным системам.

Непротиворечивость. формально T 1) Формальная теория называется непротиворечивой, если в ней не являются одновременно выводимыми формула f и ее отрицание. Непротиворечивость некоторой формальной системы S означает, что в ней нельзя из некоторого набора аксиом вывести одновременно два противоречивых суждения A и А, что соответствует закону логики А А = 0.

Непротиворечивость различных обширных областей, охватывающих по меньшей мере все разделы элементарной математики, оказалась сведенной к проблеме непротиворечивости арифметики натуральных чисел.

2) Полнота. Из аксиом должны следовать истинные (в смысле некоей модели) высказывания, и, наоборот, для полноты нужно, чтобы все истинные высказывания модели выводились из аксиом. Если L – модель формальной теории T (x:FL), то T называется полной, если всякому истинному высказыванию из L соответствует теорема из T.

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


3) Независимость. В определении функционально полных систем функций базисом называлась такая функционально полная система, удаление любой функции из которой превращает ее в функционально неполную. Добавление же произвольной функции в базис не влияет на функциональную полноту, но лишает систему свойства базиса.

Так, в 3 есть только три линейно независимых вектора (например, декартов базис (0,0,1), (0,1,0) и (0,0,1));

любые четыре уже будут зависимы, т.е. четвертый можно разложить по первым трем.

Независимой системой аксиом непротиворечивой формальной теории T=A,F,P,R называется такая система, в которой любая аксиома не может быть выведена на основании всех остальных аксиом этой системы.

3.5. Теоремы Гёделя. В 1931 году в одном из журналов была опубликована статья австрийского ученого Курта Гёделя (1906-1978) «О формально неразрешимых противоречиях Principia Mathematica и родственных систем». В ней была доказана невозможность полной формализации не только человеческих знаний и мышления, но даже невозможность полной формализации арифметики натуральных чисел.

Рассматривая непротиворечивую систему S, которую удалось свести к системе натуральных чисел, Гёдель построил формулу f и доказал, что она не может быть выведена в этой системе аксиом. Т.о., в этой системе с помощью известных аксиом и правил выводов нельзя доказать ни справедливость формулы f, ни справедливость формулы f.

Поэтому невозможна полная формализация арифметики натуральных чисел – достаточно обширной и известной формальной системы. Вывод о неполноте аксиоматики натуральных чисел одновременно доказывает и невозможность сведения математики к формальной логике.

Смысл второй теоремы, доказанной Гёделем, состоит в том, что непротиворечивость любой достаточно мощной математической системы не может быть выявлена средствами этой же системы. Это значит, необходимо применение языка другой, более мощной формальной системы для вывода новых формул. Поэтому можно утверждать, что полная формализация не может осуществиться на некотором этапе развития науки.

Эти две теоремы можно обобщить: в любой формальной системе есть формулы, недоказуемые средствами только этой системы. Теоремы Гёделя имеют настолько важное значение в математике и логике, что признаны одним из выдающихся открытий XX века.

Формальная система потому и называется формальной, что она оперирует с формальными, абстрактными объектами: символами, словами и их последовательностями.

Реальное содержание имеют интерпретации формальных систем, которые для одной и той же системы могут быть различными. Как известно, алгебра множеств и алгебра логики описываются одинаково, т.е. они изоморфны.

3.6. Интерпретация формальной теории. Интерпретация теории есть установления соответствия между элементарными высказываниями этой формальной теории и содержательными высказываниями некоторой предметной области. Интерпретацией формальной теории A,F,P,R во множество «содержательных высказываний» метаязыка L называется отображение вида x:FL. Рассматривая обозначения объектов из метаязыка L как переменные формул, будем придавать им значения из некоторого мира объектов.

Обозначения между объектами будем истолковывать как отношения между формулами.

Метаязык должен содержать, помимо прочего, семантические или смысловые характеристики высказываний (если таковые имеются). Каждому утверждению – формуле языка L – поставим в соответствие конкретное утверждение об объектах данной интерпретации. Выберем такую интерпретацию, где все аксиомы – истинные утверждения для объектов и отношений этой теории. Тогда применяя их к истинным утверждениям, они порождают новые истинные утверждения. Такую интерпретацию называют семантикой данной теории. Если для некоторой аксиоматической теории удастся подобрать соответствующую семантику, то все выводимые из аксиом формулы будут истинными в этой интерпретации. Т.о., с помощью интерпретаций все синтаксические понятия наделяются конкретным содержанием, т.е. приобретают семантический смысл.

Тогда при построении новых аксиоматических теорий (исчислений, формальных систем) все понятия, введенные ранее, получат свои точные определения.

В частности, мы сопоставляли истинным высказываниям символ «1», а ложным – «0», т.е. эти элементы или слова «ложь», «истина» должны содержаться в метаязыке.

Поскольку некоторые элементы L несут на себе семантическую характеристику, это значит, что определено отображение v: L{истина, ложь}, которое отождествим со знакомым множеством B={0, 1}. Тогда автоматически определена суперпозиция vx:

FB, ставящая в соответствие некоторым формулам их семантическую характеристику.

Пусть fF. Тогда если высказывание x(f) является истинным в смысле L (т.е. v(x(f))=1), то считают, что формула f выполняется в интерпретации x.

Интерпретация x: FL называется моделью формальной теории T=A, F, P, R, если в ней выполняются все теоремы T. Т.о., модель как интерпретация языка некоторой теории нужна для более простого и наглядного описания формальной теории, а формальная теория является «законодательным актом», подтверждающим существование модели. В частности, для законов алгебры логики моделью могут служить булевы функции, их геометрическая интерпретация на графе или на кубе, релейно-контактные схемы, безконтактные логические схемы.

Возможно ли, чтобы одна и та же формула выполнялась в одной интерпретации, но не выполнялась в другой? Такое положение невозможно: для любой интерпретации ее образ всегда должен быть «тождественно истинным». Формула fF формальной теории T=A, F, P, R называется общезначимой (или тавтологией), если она выполняется в любой интерпретации, и противоречивой, если в любой интерпретации ее образ ложен.

Поэтому с помощью понятия модели можно решить вопрос о противоречивости соответствующей формальной аксиоматической теории. Т.к. пара двух противоречивых теорем теории T отображается на пару противоречащих друг другу высказываний о модели, то теория T противоречива, а каждая ее модель содержит противоречие. Отсюда, теория непротиворечива, если можно указать соответствующую ей модель, свободную от противоречий. Если среди теорем формальной теории T нет противоречивых, то формальная теория T называется семантически непротиворечивой.

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

– Для теории T не существует ни одной подходящей семантики, т.е. не существует конкретной интерпретации. Говорят: «теория невыполнима». Такие исчисления не могут адекватно описывать мир объектов. Если исчисление имеет хотя бы одну интерпретацию, то оно называется выполнимым.

– Для теории T существует единственная семантика. Т.е., даже если и есть две различные интерпретации, отличающиеся друг от друга обозначениями, то они не различимы на языке L, т.к. они характеризуют одни и те же отношения в теории T. Такие интерпретации называют изоморфными. Примером могут служить табличные (матричные) и графические задания отношений в теории графов.

– Для теории T существует несколько принципиально различных неизоморфных семантик. Такие неизоморфные интерпретации нельзя отличить друг от друга с помощью исчисления T.

В частности, в геометрии используются некоторые синтаксические правила (формулы) для обозначения объектов (точек, прямых, плоскостей и отношений между ними). Эти формулы должны отражать отношения между реально существующими соответствующими объектами. Такие объекты в любой семантике должны иметь аналогичные имена. Тогда в различных неизоморфных семантиках объекты с одинаковыми названиями могут иметь совершенно различные интерпретации. Главное, что им придали вполне конкретный смысл, указывающий на отношения между ними и способ получения новых отношений между объектами в этой интерпретации.

Построенная формальная теория T описывает весьма общие объекты, поэтому надо ее интерпретировать – показать, как она может быть реализована на различных объектах.

Рассмотрим две интерпретации формальной теории: исчисление высказываний (ИВ) и исчисление предикатов (ИП).

3.7. Проблемы аксиоматического построения исчисления высказываний. Всякая аксиоматическая теория для ее обоснования требует рассмотрения четырех проблем:

проблемы разрешимости, проблемы непротиворечивости, проблемы полноты, проблемы независимости.

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

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

Таким алгоритмом, который позволяет для любой заданной формулы исчисления высказываний определить, является ли она доказуемой или не является, служит построение таблицы истинности и проверка истинности формулы для каждого набора значений аргументов.

Проблема непротиворечивости исчисления высказываний заключается в выяснении вопроса: является ли данное исчисление непротиворечивым или нет? Можно доказать, что ИВ непротиворечиво.

При решении проблемы полноты ИВ необходимо учитывать, что эта проблема может быть сформулирована как в узком, так и в широком смысле.

Аксиоматическое исчисление называется полным в узком смысле, если добавление к списку его аксиом любой недоказуемой в исчислении формулы в качестве новой аксиомы приводит к противоречивому исчислению.

Аксиоматическое исчисление называется полным в широком смысле, если любая тождественно-истинная формула в нем доказуема. Поэтому при решении проблемы полноты ИВ необходимо ответить на два вопроса:

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

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

Вопрос независимости аксиоматического исчисления формулируется следующим образом: «Можно ли какую-нибудь аксиому вывести из остальных аксиом, применяя правила вывода данной системы?».


В исчислении высказываний доказано, что ее система аксиом независима. Т.о., в исчислении высказываний все проблемы аксиоматической системы оказались решенными, т.е. ИВ есть одна из возможных интерпретаций исчислений как формальной системы.

3.8. Проблемы аксиоматического построения исчисления предикатов.

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

1) Определенные формулы исчисления предикатов совпадают с соответствующими и уже известными формулами логики предикатов.

2) Выбор системы аксиом исчисления предикатов, так же как и для исчисления высказываний может осуществляться по-разному. Но мы для аксиоматического построения исчисления предикатов ограничимся тремя известными аксиомами исчисления высказываний.

3) К правилу вывода исчисления высказываний добавляются правила введения кванторов:

4) Понятия вывода и доказуемой формулы определяются аналогично соответствующим понятиям исчисления высказываний.

5) Как и всякая иная аксиоматическая теория для обоснования аксиоматического построения исчисления предикатов требуется рассмотрение четырех проблем: проблемы разрешимости, проблемы непротиворечивости, проблемы полноты, проблемы независимости.

Проблема разрешимости исчисления предикатов, так же как и исчисления высказываний, заключается в доказательстве существования алгоритма, который позволил бы для любой заданной формулы исчисления предикатов определить, является ли она доказуемой, общезначимой или тождественно ложной. Как известно, в исчислении высказываний таким алгоритмом является построение таблицы истинности.

Однако в исчислении предикатов не применим метод перебора всех вариантов значений переменных, входящих в конкретную формулу ИП из-за того, что таких значений бесконечно много. В 1936 году американский математик Чёрч доказал, что не существует эффективный алгоритм, способный установить к какому классу формул относится любая формула логики предикатов, т.е. проблема разрешимости исчисления предикатов в общем виде не разрешима. Однако существуют алгоритмы распознавания общезначимости формул для частных случаев, например, заданных на конечных множествах.

Математические теории делят на теории первого порядка и теории высших порядков. Теории первого порядка отличаются от теорий высших порядков тем, что не допускают в своем изложении предикаты, которые имеют среди своих значений другие предикаты и функции, а также кванторные операции. Теорий первого порядка или элементарных теорий достаточно для описания известных математических теорий. Теории первого порядка могут служить интерпретацией исчисления предикатов.

Доказано, что всякое исчисление предикатов первого порядка непротиворечиво.

Рассмотрим примеры построения по описанной схеме некоторых исчислений.

Пример 5. Для введения всякого исчисления необходимо указать перечень употребляемых символов, описание формул исчисления и определение истинных формул. Рассмотрим построение некоторого исчисления Z.

1. Алфавит A исчисления Z состоит из трех символов: A {|, §, }.

2. Формулы исчисления Z:

а) Исходная формула - одна: |.

б) Правила построения (ПП) формул, где,, - обозначения для формул:

ПП1. Если - формула, то | - формула.

ПП2. Если и - формулы, то § - формула.

ПП3. Если и - формулы, то - формула.

3. Аксиома - одна: | § | ||.

4. Правила вывода (ПВ):

ПВ1. Если § | - выводимая формула, то | § | | - выводимая формула.

ПВ2. Если § - выводимая формула, то § | | - выводимая формула.

Правила построения формул позволяют определить для любого слова в алфавите A, является ли оно формулой исчисления Z или нет. Например, из исходной формулы, применяя несколько раз правило ПП1, можно получить формулу, представляющую собой последовательность символов |. Применяя правила ПП2, ППЗ, можно построить, например, формулы | | | § |, | | | |, | | § | | | | | § | |, | | § | | | | | |.

Покажем, например, что | | § | - формула. Нижеследующая последовательность формул представляет последовательные этапы порождающей процедуры. Для удобства рассмотрения формулы занумерованы;

справа приводится комментарий, указывающий, из каких предшествующих формул и с помощью каких правил построения получается очередная формула.

1. | – исходная формула 2. || – 1, ПП 3. – 2, 1, ПП ||§| Для формулы | | | § | | | | | | | порождающая процедура такова:

1. | – исходная формула 2. || – 1, ПП 3. – 2, ПП ||| 4. – 3, ПП |||| 5. – 4, ПП ||||| 6. – 3, 2, ПП |||§|| 7. – 6, 5, ППЗ |||§|| ||||| Можно показать, что в любой формуле и первым, и последним символом может быть только |;

каждый из символов § и обязательно соседствует с символом | как слева, так и справа, т.е. формула не может содержать подслов §§, §, §,.

Некоторые из формул являются выводимыми в рассматриваемом исчислении Z.

Покажем, что формула | | | § | | | | | | | выводима, представив ее вывод: в комментарии для каждой формулы поясняется, что такое,, - выше отмечено, что все они являются формулами.

1. | § | | | - аксиома.

– 1, ПВ1 ( = |, = | | ).

2. ||§| ||| – 2, ПВ1 ( = | |, = | | ).

3. |||§| |||| – 3, ПВ2( = | | |, = |, = | | | ).

4. |||§|| ||||| В то же время можно доказать, что формула | | § | | | | | | | не является выводимой.

Приведем теперь естественную интерпретацию рассмотренного исчисления. Если под |, | |, | | | понимать натуральные числа 1, 2, 3, …, под § - знак обычного сложения "+", а под - знак обычного равенства "=", то получим модель исчисления Z в терминах обычной арифметики натуральных чисел с единственной операцией сложения, а приведенный вывод формулы есть доказательство теоремы "3 + 2 = 5".

Замечание. Можно расширить исчисление Z следующим образом.

1. Алфавит дополнить знаком.

2. Правила построения формул дополнить правилом ПП4. Если и - формулы, то - формула.

3. Включить еще одну аксиому: | | |.

4. Правила вывода дополнить двумя правилами:

ПВЗ. Если | - выводимая формула, то | | | - выводимая формула.

ПВ4. Если и § - выводимые формулы, то | - выводимая формула.

В таком расширенном исчислении выводимой является, например, формула | | | | | | | | | | |. Если считать символ знаком умножения, то расширенное исчисление можно интерпретировать как алгебру (, +, ) натуральных чисел с операциями сложения и умножения, и последняя формула выражает утверждение "3 2 = 6".

3.9. Формальная аксиоматическая теория S для арифметики натуральных чисел.

1. Введем формальные символы в качестве букв алфавита языка теории S. Будем использовать алфавит из 12 букв:

а) логические символы:,,, = ;

б) символы для обозначения предметных переменных языка теории: x, I;

в) символы, обозначающие операции в теории S: 0,, +,;

г) левая и правая скобка: (, ).

Других знаков в теории S нет, кроме слов метаязыка.

Так, переменные предметного языка системы S можно записать с помощью двух букв x и в виде x, x и т.д. Но т.к. записи вида x – громоздкие, то для удобства принято в записи переменных использовать арабские цифры 1, 2,..., 9,..., (т.е. x =x9) и др. Так как алфавит теории S не содержал таких символов, то их взяли из другого языка – метаязыка, поэтому мы называем их «метазнаки». Рассмотрим семантический смысл знаков.

1) Выбрав в качестве минимального набора, набор логических символов « » (отрицание), «=»(равенство), «» (логическое следование), «»(знак общности), мы сможем через них выразить и все остальные логические символы, такие как,,,, например, Р х х Р х.

Знак «=» будем применять при совпадении объектов.

2) Переменные предметного языка (т.е. метаматематические обозначения x1, x2,..., xn) принимают значения из натурального ряда чисел и числа 0.

3) Функциональная буква « » (штрих) обозначает функцию с одним аргументом (унарную операцию) – операцию перехода от числа x к следующему за ним x, т.е. x=x+1.

Функциональные знаки «+», «» совпадают по смыслу с привычными бинарными операциями сложения и умножения (умножение определяется через сложение). Символ «0» обозначает, что, можно дополнить одним элементом, называемым нулем, так, что x x+0=x.

4) Левая и правая скобки предназначены для знаков препинания.

2. Рассмотрим синтаксис теории S – т.е. правила образования формул. Существуют два класса слов: термы и формулы. На этом конкретном примере покажем, что индуктивное задание является основным.

Дадим индуктивное определение терма.

1. 0 – терм;

x1, x2,... – термы;

2.

если t – терм, то (t) – терм;

3.

Если t и r – термы, то t+r и tr – термы;

4.

5. других термов, кроме определенных согласно 1) - 4).

В привычном понимании термы – имена существительные в широком смысле, т.е. имена и именные формы.

Дадим индуктивное определение формулы:

1. если t и r – термы, то t = r – элементарная формула;

2. если A – формула, то А – тоже формула;

3. если A и B формулы, то А В – формула;

4. если, A – формула, то x (A) – формула;

5. других формул, кроме определенных согласно 1-4. нет.

Так, если x1;

x2;

5 – термы, то x1+x2 = 5x1 – формула, включающая термы x1+x2 и 5x1.

x1;

x2;

5– термы по п.2 определения термов, x1+x2 и 5x1 – термы по п.4, значит, x1+x2 = 5x – формула по п.1 определения формул. Формула (x1+x2=5x1)(4x1=x2) включает две другие, причем скобки можно по договоренности убирать.

Выражение x(A) станет формулой только после того, когда вместо A будет подставлена формула. В такой теории S недостаточно знаков для выражения всех отношений. Например, отношение «больше» (x1x2) может быть выражено формулой x3(x1=x2+x3). Тогда «недостающие» знаки для записи всех возможных отношений можно включать в теорию, но заимствовать их из метаязыка.

Определив синтаксис теории S, включающий алфавит и правила образования (термы и формулы), необходимо определить и правила вывода новых предложений предмета этой теории (т.е. всех натуральных чисел).

а) Так, для любых формул A, B, C теории S справедливы формулы, называемые логическими аксиомами:

P1: A (B A);

P2: A (B C) ((A B) (A C));

P3: (A B) ((A B ) А );

P4: x A(x) A(x);

P5: x (A B) (A x B).

Выражения P1-P5 называют формальными схемами (аксиом), т.к. из математической логики нам известна их общезначимость. Эти аксиомные схемы выражают те логические законы, которые вместе с правилами вывода и собственно математическими аксиомами образуют логику теории S.

б) В качестве исходных примем правила вывода:

1. Из A и AB выводимо B (modus ponens): R1: (A(A B))B.

2. Из A выводимо xA (правило обобщения): R2: AxA.

в) К собственным аксиомам теории S относятся следующие формулы:

S1: x1 = x2 (x1 = x3 x2 = x3) S2: x1 = x2 x1 = x S3: x1 S4: x1 = x2 x1 = x S5: x1 + 0 = x S6: x1 + x2 = (x1 + x2) S7: x1 0 = S8: x1 x2 = x1 x2 + x S9: A(0) x(A(x) A(x) xA(x) (или A(0)x(A(x) A(x)) xA(x), где A(x) – произвольная формула теории S.

Схему S9 называют аксиомой индукции.

Какой семантический смысл вкладывается в эти аксиомы?

1. S1 и S2 выражают свойства отношения равенства с учетом отношения «непосредственно следовать».

2. S3 и S4 – соответствуют аксиомам Пеано и выражают отношение «непосредственно не следуют ни за каким натуральным числом».

3. S5 и S6 – дают возможность индуктивно (рекурсивно) ввести операцию сложения.

4. S7 и S8 – дают возможность индуктивно ввести операцию умножения. В логике теории S принято добавлять два важных понятия: определение формального доказательства и вывода, и тогда с помощью правил вывода можно получать любые новые.

Аксиомы Пеано. Сформулируем аксиомы Пеано:

1) Для каждого натурального числа a существует одно и только одно следующее за ним число. Новое число принято обозначать a'.

2) Единица является натуральным числом, причем она не следует ни за каким натуральным числом: a1 (a ).

3) Ни одно натуральное число не следует за двумя различными числами (a=b)(a=b) a, b.

4) Если множество A содержит единицу и вместе с каждым числом a содержит следующее за ним число a, то A содержит все натуральные числа A=. Эта аксиома дает возможность делать достоверные выводы на бесконечном множестве натуральных чисел с помощью математической индукции, поэтому ее называют «аксиомой математической индукции».

Действительно, если истинно некоторое высказывание T(1), а из истинности T(a) следует истинность T(a+1), причем 1A, aA, a+1=aA, где A – подмножество натуральных чисел, для которых истинно T(n), то множество A совпадает со всем множеством натуральных чисел и T(n) истинно для всех натуральных n.

Литература: [3], гл.III;

гл. IV;

[4], гл.5;

[7], ч.3;

[9], гл.10, 11;

[12], гл.1, 2;

[13], гл.7.

Лекция №4. Исчисление высказываний.

Язык исчисления высказываний. Схемы аксиом исчисления высказываний. Логическое следование. Метод резолюций в исчислении высказываний 4.1. Язык исчисления высказываний. Описывая булевы (переключательные) функции, мы пользовались такими логическими понятиями, как истина и ложь. Но эти понятия не математического, а философского характера, носят субъективный характер. Поэтому возникла необходимость построить математическую логику как формальную аксиоматическую теорию, не используя понятия «истина» и «ложь», а также не использовать сами законы логики.

Исчисление высказываний – раздел математической логики, в котором формально аксиоматическим методом изучаются сложные высказывания, составленные из простых (элементарных, не анализируемых) высказываний с помощью логических связок «и», «или», «если,…то», «неверно». При этом ставится цель охарактеризовать общезначимые высказывательные формы, т.е. те формулы, которые при любой подстановке высказываний вместо переменных дают высказывания, верные в соответствующем смысле. Отсюда объектом изучения логики высказываний являются выводы.

Исчисление высказываний (ИВ) выполняет задачу порождения общелогических законов как тождественно истинных высказываний. Исчисление высказываний – есть аксиоматическая логическая теория, интерпретацией которой является алгебра высказываний. Задание любого исчисления включает в себя описание символов этого исчисления (или алфавита), формул, представляющих собой конечные конфигурации символов, а также правила выводов новых утверждений этого исчисления на основе некоторого списка имеющихся утверждений (аксиом).

Исчисление высказываний есть формальная теория T, в которой заданы:

1. Алфавит ИВ A: а) связки (), ( );

def def (дополнительно можно ввести связки и : A B A B, A B A B );

б) (, ) – служебные символы, позволяющие определить порядок выполнения связок;

в) D, B,…, A1,B1,…– переменные высказывания или пропозициональные переменные.

Других символов, кроме определенных в пунктах а- в) ИВ не имеет.

2. Формулы F: а) переменные есть формулы ИВ;

б) если A,B – формулы ИВ, то ( A ) и (AB) – формулы ИВ;

Других формул, кроме определенных в пунктах а) б) в) ИВ не имеет. Переменные высказывания будем называть элементарными формулами или «атомами».

3. Аксиомы ИВ P1 : (A(BA));

P2 : ((A(BC))((AB)(AC));

P3: ( B A )(( B A)B));

A, A B 4. Правило modus ponens (mp): – правило вывода или заключения ИВ (от лат.

B modus – способ, правило;

ponens – отделение, заключение).

Смысл правила вывода: если A и AB – выводимые (или доказуемые) формулы ИВ, то B – тоже выводимая (доказуемая) формула. Так, если выводимы (доказуемы) формулы A B, A B ( A C ), то AC – тоже выводимая (доказуемая) формула.

Символы или, обозначающие отрицание, эквивалентны, но использование черты позволяет компактно и более понятно описать отрицание сложных выражений, а «уголок» позволяет правильно «оценить» длину полученного слова. Например, В С D и B ((C)D) – суть одно и то же слово, состоящее из 11 букв, где связка есть импликация.

Перечисленные формулы называются схемами аксиом ИВ. Подстановка конкретных формул в любую схему дает частный случай схемы аксиом. В исчислении высказываний множество аксиом теории T и множество правил вывода бесконечны (т.к. зависят от бесконечного числа различных высказываний-переменных), хотя задаются соответственно тремя и одним правилом.

4.2. Логическое следование. В математической логике рассматривают два различных, но эквивалентных между собой определения логического следования, первое из которых – «семантическое» основано на понятии интерпретации, а второе – «синтаксическое» или «дедуктивное» основано на понятии вывода.

Пусть A1, A2,…, An, B – формулы ИВ.

Определение 1. Говорят, что формула B логически следует из формул A1,A2,…,An, если при каждой интерпретации, при которой все формулы A1, A2,…, An истинны, будет истинной и формула B. Отсюда, формула B называется логическим следствием формул A1,A2,…,An тогда, и только тогда, когда истинна конъюнкция формул A1 A2 … An.

Определение 2. Символическая запись логического следования формулы B из A1,A2,…,An имеет вид A1,A2,…,An B или A1,A2,…,An |– B, что читается: «B выводимо из A1,A2,…,An,». Пусть A1 A2 … An=A. Тогда справедлива формула A |– B, что читается: «B выводимо из A». Говорят, что формула A выводима из формул A1,A2,…,An, если существует последовательность формул B1, B2,…, Bm, A, в которой любая формула есть либо аксиома, либо принадлежит списку формул A1,A2,…,An, называемых гипотезами, либо получается из предыдущих по правилу вывода mp. Обозначение: A1,A2,…,An |– A.

Принято множество гипотез обозначать Г. Тогда Г|– A, т.е. формула A выводима из Г.

Выводимость формулы A из пустого множества аксиом равносильна тому, что A – теорема ИВ, т.е. доказуема. Обозначение: |– A.

Доказательством или выводом формулы A из множества формул Г (гипотез) называется такая конечная последовательность B1, B2,…, Bm, A, в которой любая формула есть либо аксиома, либо формулой из Г, либо получена из двух предыдущих по правилу вывода mp, причем последняя формула в цепочке формул B1, B2,…, Bm совпадает с A.

Тогда доказательство теорем ИВ сводится к построению таких цепочек, состоящих из аксиом и гипотез по приведенным правилам.

В исчислении предикатов доказано, что всякая выводимая формула исчисления предикатов тождественно истинна (т.е. общезначима, тавтология), и наоборот. В настоящее время разработан ряд методов, позволяющих стандартизировать обоснование этих равносильностей. Но в отличие от логики высказываний, логика предикатов вообще говоря, неразрешима, т.к. невозможно указать алгоритм установления истинного значения формул для многоместных предикатов (n1). Однако, логика одноместных предикатов, наиболее полно соответствующая логике исчисления высказываний, разрешима.

Формула F называется тавтологией или тождественно истинной формулой, если она истинна при любой интерпретации. Две формулы A и B называются логически эквивалентными, если их эквиваленция является тавтологией (общезначимой формулой), т.е. если она всегда истинна. С другой стороны, формулы A и B называются логически эквивалентными, если AB и BA.

Справедливы утверждения:

1. Если A1, A2,…, An, B – формулы ИВ, Г={A1, A2,…, An }, Г|– A, то Г, A |– B. Смысл этого утверждения заключается в том, что можно увеличивать число гипотез.

2. Сведение множества гипотез к одной: (A1,A2,…,An |– Г)( A1 A2 … An |–Г).



Pages:   || 2 | 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.