11. Понятие теоремы. Основная теорема логического вывода и ее доказательство.

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

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

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

Построение вывода для заданной формулы является непростой задачей. Ещѐ более сложной задачей может быть ответ на вопрос: А существует ли данный вывод?

Одной из важнейших задач современной науки является:

1) Построение алгоритмов, определяющих существует доказательство алгоритмов или нет. Если такой алгоритм удается построить для теории, то теория называется разрешимой.

2) Построение методов алгоритмического доказательства теоремы.

12. Основная теорема логического вывода

Теорема. Формула G является логическим следствием формул F1, F2, . . . Fn тогда и только тогда, когда формула F1&F2&. . .&Fn → G является тавтологией.

(А≡В)=(А→В)&(В→А)Для доказательства теоремы необходимо доказать необходимость и достаточность

Доказательство.

Лемма 1. Если формула А→В является тавтологией, то В принимает истинное значение при тех интерпретациях при которых истина А.

А→В

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

Согласно Лемме1 можно сформулировать другое определение логического следствия, а именно:

Формула В является логическим следствием формулы А, если она истина при тех интерпретациях при которых истина А.

G (F1, F2,…Fn)

Докажем необходимость

Предположим чтоG является логическим следствием F1, F2,…Fn . Требуется доказать что (*) – тавтология.

Пусть I – произвольная интерпретация.

Если все формулы F1, F2,…Fn истина на I

I(f1)=I(F2)=….I(Fn)=И и по определению логического следствия I(G)=И, то формула

(*) – истина.

Если хотя бы одна из F принимает значение Л, то (*) все равно Истина(т.к. Л→И). Следовательно формула (*) - тавтология.

Докажем достаточность.

Предположим, что (*) - тавтология. Надо доказать что G является логическим следствием.

Для всякой интерпретации I, на которой все Fi истинны, формула (**) тоже истинна, и поскольку (*) - тавтология, G - тоже истинна. .

Теорема Формула G является логическим следствием формул F1, F2, . . . Fn тогда и только тогда, когда формула F1&F2&. . .&Fn→ ךG является противоречием.

13. !!! Ошибочные доказательства и парадоксы.

14. Дедуктивные и индуктивные доказательства. Примеры индуктивных доказательств.

Дедуктивное доказательство

Состоит в последовательности утверждений истинность которых следует из некоторых исходных утверждений посылок(гипотез).Конечные утверждения называются заключения.

Индуктивные доказательства

Существующий принцип индукциинаблюдение явления Х которое соответствует теории Т и увеличивает вероятность того что Т истинно

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

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

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

Принцип Дедукции

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

Принцип Индукции

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

Пусть X — явление, подтверждающее теорию T, и пусть I — наши знания об окружающей обстановке, кроме самого явления X.

Пусть Pr(T | XI) — вероятность того, что теория T верна, при условии, что известно, что X и I верны. Тогда

где Pr(T | I) — вероятность того, что теория T верна, при условии, что только

об I известно, что оно верно; Pr(X | TI) — вероятность того, что X верно, при условии, что о T и I известно, что они верны; и Pr(X | I) — вероятность того, что X верно, при условии, что только об I известно, что оно верно.

При использовании этой теоремы парадокс не появляется. Если наблюдатель выбирает яблоко случайным образом, то вероятность увидеть красное яблоко не зависит от того, являются ли все вороны чѐрными или нет. Вторая часть числителя будет равна знаменателю, и вероятность выбрать красное яблоко не изменится. Наблюдение X и теория T не связаны, и наблюдение красного яблока не увеличит уверенности в том, что все вороны чѐрные.

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