Человеческое мышление


Похожие статьи:

Популярные записи


  • Исчисление высказываний

    Исчисление высказываний ЧВ согласно поданной в разделе 1 схемой означається таким образом.

    1. Алфавит исчисление высказываний состоит из элементарных и переменных высказываний пропозицийних переменных : A, B, C, D,.., X, Y, Z возможно с индексами, знаков логических операций, и круглых скобок и .

    2. Понятие Формулы Означається аналогично алгебре высказываний.

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

    Б если A и B - формулы, то выражения слова A B, A B, A, A B также являются формулами;

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

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

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

    3. Аксиомами Исчисления высказываний будут такие формулы:

    A1. A B A

    A2. A B A B C A C

    A3. A B A

    A4. A B B

    A5. A B A C A B C

    A6. A A B

    A7. B A B

    A8. A C B C A B C

    A9. A B B A

    A10. A A

    4. Правилами выведения есть:

    1 Правило подстановки. Если A - выводная формула, которая содержит букву P обозначим этот факт A P, то выводной является и формула A B, что добывается из A заменой всех вхождений буквы P на произвольную формулу B; записывается

    A P

    A B

    2 Правило вывода Modus ponens. Если A и A B - выводные формулы, то выводной является и формула B; записывается

    A, A B

    B

    В поданном описании исчисления высказываний аксиомы являются формулами исчисления соответствующими к определению формулы; формулы, которые используют в правилах выведение A, A B и тому подобное, есть Метаформулами, или так называемыми Схемами формул.

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

    Например, для схемы формул A B, если заменить A на P, а B - на P Q, то из данной схемы получим формулу исчисления P P Q; если же метапеременную A заменить на P Q, а B - на P Q P, то достанем формулу P Q P Q P и тому подобное.

    Использование схем формул можно распространить и на все аксиомы. Например, если в системе аксиом пропозицийни переменные A, B, C заменить метапеременными A, B, C, то получим десять схем аксиом, которые задают десять бесконечных множеств аксиом. Таким образом приходим к другому способу построения исчисления высказываний : с бесконечным множеством аксиом что задается конечным числом схем аксиом, но без правила подстановки, поскольку оно неявно содержится в объяснении Интерпретации схем аксиом.

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

    С другой стороны, второй способ более отвечает математической традиции толкования интерпретации формул : например, тождественность <алгебраизма i> A+ B2= A2+2 Ab+ B2 или известны логарифмические или тригонометрические тождественности толкуются именно как схемы тотожностей, а не конкретные тождественности, справедливые лишь для конкретных букв. Правило подстановки при этом имеется в виду и присутствует неявно. Впрочем, достаточно очевидно, что переход от одного способа построения исчисления к другому является несложным.

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

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

    Рассмотрим примеры выведения теорем ЧВ.

    Пример 5.2. Докажем, что формула A A является теоремой ЧВ.

    1 Подставляя в аксиому A2 переменную A вместо переменной C и B A вместо B, будем иметь выводную формулу

    A B A A B A A A A

    2 Подформула A B A является аксиомой A1. Тогда из выводных формул

    A B A и A B A A B A A A A

    По правилу вывода виводимо формулу

    A B A A A A.

    3 Заменим в аксиоме A1 B на B A:

    A B A A.

    4 Опять, применяя правило вывода до двух последних формул, будем иметь, что формула A A Является выводной.

    Для удобства примем такую форму записи выведения формул в ЧВ:

    А последовательность формул выведения будем писать в столбик, нумеруя их в порядке следования F1, F2,...

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

    Правило подстановки будем записывать в виде A= A B, а правило вывода - в виде MP A, A B = B.

    Тогда последнее выведение примет вид:

    F1: A2 = A B A A B A A A A

    F2: MP A1, F1 = A B A A A A

    F3: A1 = A B A A

    F4: MP F3, F2 = A A

    Следовательно, мы довели такую метатеорему исчисление высказываний : |- A A.

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

    Приведем примеры выведения некоторых формул из заданных множеств формул.

    Пример 5.3. 1. A |- B A

    F1: A

    F2: MP F1, A1 = B A

    2. A, B, A B C |- C

    F2: B

    F3: A B C

    F4: MP F1, F3 = B C

    F5: MP F2, F4 = C

    3. A, B |- A B

    F1: A5 = A A A B A A B

    F2: A A см. пример 5.2

    F3: MP F2, F1 = A B A A B

    F4: B

    F5: A1 = B A B

    F6: MP F4, F5 = A B

    F7: MP F6, F3 = A A B

    F8: A

    F9: MP F8, F7 = A B

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

    Лемма 1. Если |- B, то Г |- B.

    Лемма 2. Если A1, A2.., An |- B, то A1, A2.., An,Г |- B.

    Лемма 3. Если Г |- A и A |- B, то Г |- B транзитивность отношения выводной.

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

    Например, доказанную в примере 31 выводная A |- B A вместе с правилом подстановки можно рассматривать как правило, что может быть интерпретировано так: "если формула A является выводной, то выводной является и формула B A, где B - произвольная формула". Это правило в дальнейшем можно использовать для построения новых выведений. Такие правила будем называть Производными правилами. С помощью дополнительных производных правил получаем возможность сократить выведение формул, не выполняя полного выведения. Имея сокращенное выведение, всегда можно построить полное выведение, заменяя каждую формулу, которая является результатом применения производного правила выведения, на полное ее выведение. Такой формулой является, например, формула F2 в примере 33. Iнакше говоря, производные правила - это строительные блоки при построении выведений формул ЧВ, каждый из которых заменяет несколько шагов обычного выведения.

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

    Теорема 3 Метатеорема дедукции. Если Г, A|- B, то Г|- A B, где Г- множество формул возможно, пустая, A и B - формулы.

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

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

    Пусть Г, A|- B. Тогда существует выведение B1, B2.., Bn из Г, A такое, что Bn= B. Доведем за индукцией, что для любого K, N Г|- A Bk.

    Рассмотрим сначала случай K=1, то есть формулу B1. B1, как первая формула выведения, должна или быть аксиомой, или содержаться в Г, или совпадать из A.

    Из схемы аксиомы A1 выплывает, что B1 A B1 является аксиомой. Если B1 - аксиома или содержится в Г, то по правилу вывода A B1 является выводной из Г. Если же i> B1= A, то из примера 2 имеем, что A A, то есть A B1 является выводной формулой. Следовательно, в любом случае получим Г|- A B1.

    Следовательно, допустим, что Г|- A для произвольного I K и рассмотрим формулу Bk. Возможны четыре ситуации:

    А Bk - аксиома;

    Б Bk Содержится в Г;

    В Bk = A;

    Г Bk является выводной из некоторых предыдущих формул Bj но Bl по правилу вывода; в этом случае формула Bl должна иметь вид Bj Bk.

    В случаях а, бы, в доведение утверждения Г|- A Bk осуществляется аналогично доведению для B1 случаи но и бы - с помощью схемы аксиомы A1; случай в - с помощью результата примера 5.2.

    В случае г за индуктивным предположением имеем Г|- A Bj и Г|- A Bl, где Bl - это Bj Bk, то есть Г|- A Bj Bk.

    Подставим в схему аксиомы A2 A вместо A, Bj вместо B и Bk вместо C. Достанем A Bj A Bj Bk A Bk.

    Применяя к последней выводной формуле дважды правило вывода, получим Г|- A Bk. Осталось положить K= N.

    Рассмотрим несколько Применений метатеореми дедукции.

    1. Очень распространенным методом математических доведений является Метод доведения от противоположного: допускаем, что A является верным истинным утверждением, и доказываем, что, во-первых, из A выводится B, а во-вторых, что из A выводится B, что невозможно; следовательно, A неверно, то есть верно A.

    В сроках исчисления высказываний этот метод формулируется так:

    "если Г, A|- B и Г, A |- B, то Г|- A".

    Доведем справедливость этого правила в исчислении высказываний.

    Действительно, за теоремой дедукции, если

    Г, A|- B и Г, A|- B, то Г|- A B и Г|- A B

    F1: A B

    F2: A B

    F3: A9 = A B B A

    F4: MP F2, F3= B A

    F5: A2 = A B A B C A C

    F6: MP F1, F5 = A B C A C

    F7: F6 = A B B A A B A

    F8: A1 = B A A B B A

    F9: MP F4, F8 = A B B A

    F10: MP F9, F7 = A B A

    F11: MP F1, F10 = A

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

    Г, A | - B; Г, A | - B

    Г|- A

    Кроме того, нетрудно убедиться в справедливости для исчисления высказываний такого утверждения или метатеореми, которую можно считать обратной к метатеореми дедукции ОМТД : "если Г|- A B, то Г, A|- B"

    Последовательно имеем

    F2: A B

    F3: MP F1, F2 = B

    2. Доведем теперь Закон исключения третьего: |- A A.

    F1: A6 = A A A

    F2: A A = A A A A см. пример 2

    Из формул F1 и F2 имеем за ОМТД

    F3: A A, A |- A A

    F4: A A, A |- A A

    По доказанному правилу введения отрицания в формула из F3 и F4 получим:

    F5: A A |- A.

    Аналогично используем аксиому A7, в которой вместо B подставляем A.

    A7 = A A A

    A A, A |- A A

    A A, A |- A A

    Получаем

    F6: A A |- A.

    По правилу введения отрицания из F5 и F6 достанем:

    F7: |- A A

    F8: A10 = A A A A

    F9: MP F7, F8 = A A, то есть |- A A.

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

    Например, рассмотрим исчисление высказываний ЧВ1, которое использует только логические операции и и имеет такую систему аксиом :

    S1. A B A

    S2. A B C A B A C

    S3. A B A B A

    Правилами выведения в новом исчислении являются те же правила, что и в старике, то есть правило подстановки и правило вывода.

    Если в системе аксиом первого исчисления заменить подформулы A B на A B, а подформулы A B - на A B, то справедливой является такая теорема.

    Теорема 4. Оба приведенных исчисления высказываний ЧВ и ЧВ1 являются равносильными в том смысле, что множества формул выводных в каждом из этих исчислений множества теорем этих исчислений совпадают между собой.

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

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

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