Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Формальная логика.doc
Скачиваний:
7
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆
  1. Если простое число k делит m-n, то k делит m или п, следует, что

  2. K делит m или п.

В то же время из (1) следует, что

(5) k не делит т.

Наконец, на основании (4) и (5) устанавливаем

(6) k делит п.

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

  1. доказательство начинается введением в рассмотрение ус­ловия доказываемого предложения в качестве допущения (до­казательства);

  2. в дальнейшем из уже имеющихся предложений, к кото­рым всегда можно присоединить ранее установленные истины (аксиомы, ранее доказанные положения и т. п.), выводятся следствия;

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

Таким образом, можно обнаружить, что в данном доказа-, тельстве применяются два рода правил: а) правила, определя­ющие (более или менее подробную) схему или структуру дока­зательства, б) правила, по которым из уже имеющихся пред­ложений получаются в качестве следствий новые предло­жения.

Правила первого рода в дальнейшем мы будем называть правилами построения доказательства. Назначение их — очер­чивать, образно говоря, более или менее ясные контуры строя­щегося доказательства, подсказывать «идею» доказательства. Мы еще не располагаем точными в терминах логических исчис­лений формулировками этих правил. Ограничимся пока лишь ссылкой на то, что описательная характеристика одного из них содержится в объяснении схемы, по которой построено доказа­тельство в приведенном примере.

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

Что касается правил второго рода, то к ним относятся уже известные нам правила логического следования. Заметим, что выше в пр'имере можно обнаружить применение некоторых пра­вил, схемы которых были приведены paHeet

Действительно, строка "(2) получена по правилу УК (пер­вая схема) из строки (1); строка (4)—из строк (3) и (2) по правилу МП, строка (5)—из строки (1) по правилу УК (вто­рая схема). Наконец, на заключительном шаге доказательства применяется правило УД/О.

Рассмотрим еще один пример конкретного доказательства, в котором применяется так называемое правило построения кос-венного (апагогического) доказательства, или доказательства от противногог

Пример. Здесь доказывается предложение:

Если простое число к делит пг-пг, то к делит т.

Доказательство.s Допустим, что

  1. простое число к делит пг-пг и в то же время 5

  2. k не делит т. Известно,6 что

(3) Если простое число k делит пг-пг и к не делит ш, то к делит пг.

Далее, из (1) и (2) следует (по правилу ВК)., что

(4) к делит пг-пг и к не делит пг.

Наконец, из (3) и (4) следует (по правилу МП), что

(5) к делит т.

Однако последнее противоречит (2).

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

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

Сделанные выше' разъяснения по поводу дедуктивных пра­вил первого и второготюдов можно кратко выразить так: еслис помощью правил построения доказательства определяется схема (структура) возможного доказательства, то с помощью правил следования осуществляется заполнение свободных строк (пустых мест) в данной схеме с целью нахождения действитель­ного доказательства.

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

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

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

Основные правила системы N содержат: [I] Правила логического следования:

А А-»В

МП

В

А В АДВ АДВ

ВК ; УК ——, ■

АЛВ А В

А В А V В А->С В ВД , —--; УД

А V В А V В

[II] Правила построения доказательства. [II. 1] Правило построения прямого доказа­тельства.

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

Ai-*>(A2-»> ... (А„-»>С) ...) (*)

строится согласно следующему предписанию. На любом шаге построения можно написать:

1) одну из формул At, Аа, ..., An в качестве допущения;

2) формулу, следующую из ранее написанных формул по одному из правил логического следования,

3) ранее доказанную формулу.

Прямое доказательство формулы (*) считается построенным, если в соответствии с пп. 1)—3) получена последовательность формул, оканчивающаяся формулой С.

Пока еще у читателя свежо в памяти правило [II. 1], мы, не заканчивая описания всех правил системы, приведем в каче­стве примера несколько доказательств.

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

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

1- (Р~*-Ф A {q-*r) допущ.

2. p-*q УК (I);

(I) 3. р допущ.;

A. q МП (3, 2);

б. q-*r УК <1);

г МП (4, 5).

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

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

А,-*(А2->С),

поставив в соответствие букве Ai формулу (p-*q)A(q-*r), букве А2 — формулу р, и наконец, букве С — формулу г. В до­казательстве строка 1 заполнена согласно п. 1) правила [II. 1] формулой

(p-+q) A(q-*r).

Далее, применив первую схему правила УК, мы написали в строке 2 формулу

P~*q

согласно п. 2) данного правила после этого, написав формулу

Р

согласно п. 1), мы заполнили согласно п. 2) строку 4 формулой

Я,

следующей из формул, написанных в строках 2, 3 по правилу МП. Затем, в соответствии с п. 2) в строке 5 мы написали фор­мулу

q-+r,следующую по второй схеме правила УК из формулы в строке 1. Наконец, заключительный шаг состоит в заполнении соглас­но п. 2) последней строки формулой

г,

следующей по правилу МП из формул, написанных в стро­ках 5, 4.

Таким образом построена последовательность из шести фор­мул, которая согласно критерию, сформулированному во вто­рой части правила [II. 1], есть прямое доказательство формулы

((Р~*q) Л (q->-r))-*(p-*r).

Ниже приводится прямое доказательство формулы

q-*q.

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

q допущ.

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

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

ipVq)-+{(p -*q)-*q)-Доказательство.

3. q-*q р.д. ф.8

q УД (1, 2, 3).

Предоставляем читателю самостоятельно разобраться, по какой схеме анализируется доказываемая формула, почему здесь при построении доказательства было выбрано правило УД и как возникла идея использовать q-*- q в качестве ранее доказанной формулы?

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

Естественно, что при построении доказательства нулькрат­ной импликации, п. 1) правила [II. 1] не применяется и доказы­ваемая формула выводится «непосредственно» из ранее дока­занных формул,, возможность использования которых преду­сматривается п. 2) правила [II. 1].

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

[II. 2] Правило построения косвенного (апаго­гического) доказательства.

Косвенное доказательство формулы (*) строится согласно следующему предписанию.

На любом шаге построения можно написать:

1) одну из формул А], А2, .... Ап в качестве допущения; 1а) формулу, противоречащую формуле С;

2) формулу, следующую из ранее написанных форм по од- ному из правил логического следования;

3) ранее доказанную формулу.

Косвенное доказательство формулы (*) считается построен­ным, если в соответствии с пп. 1)—3), включая и п. 1а), полу­чена последовательность формул, содержащая пару противоре­чащих формул и оканчивающаяся одной из них.

Данное правило отличается от правила [II. 1] наличием до­полнительного п. 1а) и критерием окончания доказательства. Таким образом, косвенное доказательство кратной импликации осуществляется путем выведения из антецедентов и формулы, противоречащей консеквенту доказываемой формулы, противо­речия, т. е. некоторой формулы В и ее отрицания ~В (не обя­зательно в таком порядке) с помощью правил следования и с использованием, быть может, ранее доказанных формул.

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

((р-м) Л~<?)->

~ р.

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

допущ. косв. док.;

УК (1); МП (2, 3); УК (1);

(Ш)

q допущ.;

  1. {p-»q)A~q

  2. р

  3. p-*q

  4. q

  5. ~q

Пртврч.: 4, б.

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

~р-*(р->-<7).

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

(IV) 2. р допущу

Пртврч.: 1, 2.

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

((p-»q)-+p)-»p. Доказательство.

1. (р-*а)~*р допущ.

2, ~р допущ. косв. док.

(V) 3. ~p-+(p-+q) р. Д. ф.

  1. p-*q МП (2, 3)

  2. р МП (4, 1) •> Пртврч.: 5, 2.

Построив это доказательство, мы проанализировали доказы­ваемую формулу по схеме однократной импликации, т. е. рас­сматривали ее как формулу вида Ai —*■ С. Но ее нельзя предста­вить т виде Ai ->(А2 С).

Далее, в доказательстве (III) допущение косвенного доказа­тельства мы образовали, стерев знак ~ (т. е. знак отрицания) перед консеквентом доказываемой кратной импликации. Здесь же допущение косвенного доказательства образуется путем при­писывания знака ~ к консеквенту доказываемой формулы.

В заключение рассмотрим еще одно доказательство

((Р V<7)A~P)-»-<7. Доказательство.

  1. (р V q) Л~Р допущ.

  2. р V q УК (1)

  3. ~ р УК (1);

(VI) 4. ~p-*(p-+q) р. д. ф.;

  1. p-*q МП (3, 4);

  2. q-*q р. Д. ф.;

q УД (2, 5, 6)

Заметим, что хотя данное доказательство "(по форме)' яв­ляется прямым, но оно отличается от приведенных выше прямых доказательств тем, что доказательство формулы, вписанной4 в его четвертую етроку в качестве ранее доказанной, является косвенным.

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

Среди прямых доказательства имеет смысл выделить такие, которые не имеют и косвенных доказательств в числе предше­ствующих (не обязательно непосредственно). Доказательство этого рода мы будем называть чисто прямыми. Все прямые доказательства, рассмотренные в примерах, за исключением J (VI) являются чисто прямыми. В дальнейшем формулу, дока­зательство которой построено, будем называть тезисом дан­ного доказательства, а доказательства, тезисы которых совпа­дают, будем называть одноименными.

Завершая описание системы N, мы введем следующее опре­деление доказуемой формулы. Формула называется доказуемой формулой, или логической теоремой ;(системы AJ), если можно построить доказательство данной фор­мулы (по правилам системы N).

Кроме того, мы принимаем следующее определение знака эквивалентности:

A<->BW(A->B)A(B-»A).

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

Из определения знака .**-*■. непосредственно следует, что правила

А-+В В-*"А А-<-*-В А-<->В

ВЭ , УЭ , ,

А В А-*В В -+ А

называемые соответственно введением и удалением эквивалентности представляют собой частные случаи пра­вил ВК и УК.

Пример рассуждения по правилу ВЭ.

Если данное число делится на 6, то оно делится на 2 и на 3. Если данное число делится на 2 и на 3, то оно делится на 6. Следовательно, данное число делится на 6 тогда и только тог­да, когда оно делится на 2 и на 3.

Осуществляя поиск логических доказательств, мы руководст­вуемся догадками, идеями и т. п. относительно плана возмож­ного доказательства какого-либо тезиса и способов превращения этого плана в действительное доказательство. Иными словами, поиск логического доказательства направляется эвристическими принципами мышления, или эвристиками.

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

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

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

Таким образом, эвристический поиск логических доказа­тельств представляет собой аналитико-синтетическую процеду­ру, которая, как мы видели, имеет логическую природу. Заме­тим, что поиск логического доказательства практически не обязательно связан с точной формулировкой тезиса искомого доказательства. Часто мы располагаем лишь приближенной ха­рактеристикой — «смутной идеей тезиса». В этом случае логи­ческие правила могут быть использованы для исправления или уточнения первоначальной формулировки тезиса.