Понятие логического вывода

Глава III

ЕСТЕСТВЕННЫЙ ВЫВОД В ЛОГИКЕ ВЫСКАЗЫВАНИЙ

Понятие логического вывода

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

Правила логического следования отражают определенные отношения вещей. Эти правила сложились и складываются в процессе практической деятельности людей. «...Практическая деятельность человека миллиарды раз должна была приводить сознание человека к повторению разных логических фигур, дабы эти фигуры могли получить значение аксиом.»^[1]

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

Кратной импликацией называется формула вида

A ₁ ® (A ₂®... (А_n ® С)...) (*)

Формула (*) читается так: если A ₁, A ₂,..., А_n то С. Члены кратной импликации, обозначенные в (*) посредством A ₁, A ₂,..., А_n называются антецедентами, а член С — консеквентом.

При n = 1 имеем схему однократной (обычной) импликации

A ₁ ® С;

при n = 2 — схему двукратной импликации

A ₁ ® (A ₂ ® С);

при n = 3 — схему трехкратной импликации

A ₁ ® (A ₂ ® (А ₃ ® С)

и т. д.

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

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

В дальнейшем важно уметь анализировать формулу с помощью схемы кратной импликации. Этот анализ может иметь различную глубину, в зависимости от того, какие части анализируемой формулы рассматриваются в качестве антецедентов A ₁, A ₂,... А_n и консеквента С в схеме кратной импликации. Так, формулу

((p ® q) Ù (q ® r)) ® (p ® r)

можно рассматривать в качестве однократной импликации, т. е. как построенную по схеме

A ₁ ® С.

Очевидно, что в этом случае мы берем в качестве A ₁ формулу

((p ® q) Ù (q ® r)),

а в качестве С —

(p ® r).

Но если взять в качестве A ₁

((p ® q) Ù (q ® r)),

в качестве A ₂ —

p

и в качестве С —

r,

то формула

((p ® q) Ù (q ® r)) ® (p ® r)

рассматривается теперь уже как двукратная импликация, т. е. как формула вида

A ₁ ® (A ₂ ® С).

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

Между тем формулу р Ù (q Ú (~ p ® r)) можно рассматривать только в качестве нулькратной импликации.

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

((р ® q) ® p) ® q,

(р ® q) ® (р ® q)

может быть представлена в виде

A ₁ ® С,

но только вторая — в виде

A ₁ ® (A ₂ ® С).

Таким образом, проанализировать формулу F по схеме кратной импликации — значит для данной формулы подобрать схему

A ₁ ®(A ₂ ®... (А_n ® С)...)

с некоторым подходящим значением n и каждому A ₁, A ₂,..., А_n, С поставить в соответствие подформулы формулы F так, что, заменяя A ₁, A ₂,... А_n, С сопоставленными им подформулами, мы снова получаем анализируемую формулу.

Анализ формулы F по схеме кратной импликации мы назовем предельным, если букве С в этой схеме ставится в соответствие подформула формулы F, не содержащая знака ® в качестве главного логического знака. Заметим, что в дальнейшем нам чаще придется прибегать к предельному анализу, чем ограничиваться более грубым анализом формулы по схеме кратной импликации.

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

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

Таким образом, если кратная импликация тождественно-истинна, то во всех строках ее таблицы, где каждому антецеденту приписывается логическое значение «истинно», консеквенту приписывается то же значение.

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

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

Таким образом, одна из важных гносеологических (познавательных) функций логических тождеств рассматриваемого типа состоит в том, что они гарантируют получение новых истин из уже известных. «Если наши предпосылки верны и если мы правильно применяем к ним законы мышления, то результат должен соответствовать действительности, точно так же как вычисление в аналитической геометрии должно соответствовать геометрическому построению, хотя то и другое представляют собой совершенно различные методы».^[2]

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

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

В логике правила следования записываются в виде фигур рассуждения

A ₁, A ₂,..., А _n,

С

которые читаются так: из A ₁, A ₂,..., А_n следует (или выводится) С. Члены A ₁, A ₂,..., А_n называются посылками, а член С называется заключением данной фигуры. Но, конечно, не всякая фигура такого вида является правилом следования. Это понятие раскрывается в приводимом ниже определении.

Определение правила логического следования. Фигура

A ₁, A ₂,... А _n,

С

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

A ₁ ®(A ₂ ®... (А_n ® С)...)

есть логическое тождество.

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

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

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

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

Предлагаем читателю проверить корректность следующих фигур:

Правило МП — это уже известный читателю модус поненс. Словесно это правило можно сформулировать так: из импликации и формулы, совпадающей с ее антецедентом, следует формула, совпадающая с консеквентом данной импликации.

Заметим, что фигура

В А ® В,

А

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

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

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

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

Наконец, правило УД^[3] называется правилом удаления дизъюнкции и означает, что из двух импликаций, консеквенты которых одинаковы, и дизъюнкции формул, совпадающих с антецедентами этих импликаций, следует формула, совпадающая с консеквентом импликаций.

Пример рассуждения по правилу УД:

Если междометия выражают чувства, то они несут информацию; если междометия выражают волевые побуждения, то они также несут информацию. Но междометия выражают чувства, или междометия выражают волевые побуждения. Следовательно, междометия несут информацию.

Читателю предоставляется также установить корректность следующих фигур:

Правило МТ — это модус толленс.^[4] Правило УОК называется удалением отрицания конъюнкции. Наконец, правило УД/О, состоящее из четырех фигур, мы называем удалением дизъюнкции посредством отрицания.

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

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

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

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

есть вывод из исходных формул (посылок) 1—3 формулы 8 (заключения данного вывода), при построении которого используются правила МП, BK, УК.

Рассматриваемый вывод строится так. В первых трех строках записываются посылки; в строке 4 мы пишем формулу r, следующую из ранее написанной (строка 2) формулы p ₁ Ù r по второй схеме правила УК; в строке 5 мы пишем формулу p ₂, следующую по правилу МП из формул, стоящих в строках 3 и 4; далее, при получении формулы p ₁ (строка 6) к формуле p ₁ Ù r (строка 2) применяется первая схема правила УК; формула p ₁ Ù p ₂ (строка 7) следует из формулы р ₁ (строка 6) и формулы p ₂ (строка 5) по правилу BK; наконец, применяя правило МП к формулам (p ₁ Ù p ₂) ® q (строка 1) и p ₁ Ù p ₂ (строка 7), пишем в последней строке формулу q.

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

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

Пример. Ниже дается словесная формулировка следующей логической задачи.^[5]

(1) Если теорема о сложении скоростей верна и в системе неподвижных звезд свет распространяется по всем направлениям с одинаковой скоростью, то на Земле скорость распространения света не по всем направлениям одинакова. (2) Известно, что свет в системе неподвижных звезд распространяется по всем направлениям с одинаковой скоростью, а в опытах установлено, что скорость распространения света и на Земле по всем направлениям одинакова.

Что отсюда следует?

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

(1) (p Ù q) ® ~ r, (2) q Ù r,

где р стоит вместо Теорема о сложении скоростей верна; q — вместо В системе неподвижных звезд свет распространяется по всем направлениям с одинаковой скоростью; r — вместо На Земле скорость света по всем направлениям одинакова.

Применяя к формулам (1), (2) уже известные нам правила следования, мы строим такой формальный вывод:

Таким образом, из посылок, написанных в строках 1—2 вывода, мы получаем в качестве следствия ~р. Вспоминая, что р стоит вместо: Теорема о сложении скоростей верна, мы приходим к требуемому ответу на вопрос нашей словесно сформулированной задачи, а именно: Теорема о сложении скоростей не верна.

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

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

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

Если простое число k делит mn и k не делит m, то k делит n.

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

(1) простое число k делит mn и не делит m.

Тогда из (1) следует, что

(2) k делит mn.

В свою очередь из (2) и известного положения:

(3) Если простое число k делит mn, то k делит m или п, следует, что

(4) k делит m или n.

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

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

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

(6) k делит n.

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

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

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

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

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

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

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

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

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

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

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

Если простое число k делит mm, то k делит m.

Доказательство.^[6] Допустим, что

(1) простое число k делит mm и в то же время^[7]

(2) k не делит m. Известно,^[8] что

(3) Если простое число k делит mm и k не делит m, то k делит m.

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

(4) k делит mm и k не делит m.

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

(5) k делит m.

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

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

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

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

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

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

Описываемая ниже система естественного вывода, которую мы обозначаем буквой N, является модификацией логической системы, предложенной польскими логиками Е. Слупецким и Л. Борковским.^[9] Основные правила системы N содержат:

[I] Правила логического следования:

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

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

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

A ₁ ® (A ₂ ®... (А_n ® С)...) (*)

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

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

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

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

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

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

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

((p ® q) Ù (q ® r)) ® (p ® r).

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

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

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

A₁ ® (A₂ ® С);

поставив в соответствие букве A ₁ формулу (p ® q) Ù (q ® r), букве A ₂ — формулу p, и наконец, букве С — формулу r. В доказательстве строка 1 заполнена согласно п. 1 правила [II.1] формулой

(p ® q) Ù (q ® r).

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

p ® q

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

p

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

q,

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

q ® r,

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

r,

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

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

((p ® q) Ù (q ® r)) ® (p ® r).

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

q ® q.

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

q допущ.

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

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

(p Ú q) ® ((p ® q) ® q).

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

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

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

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

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

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

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

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

1а) формулу, противоречащую формуле С;

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

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

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

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

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

(p ® q) Ù ~ q) ® ~ p

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

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

~ p ® (p ® q).

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

1) ~ p

2) p допущ.;

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

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

((p ®q) ® p) ® p.

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

Построив это доказательство, мы проанализировали доказываемую формулу по схеме однократной импликации, т. е. рассматривали ее как формулу вида A ₁ ® С. Но ее нельзя представить в виде A ₁ ® (A ₂ ® С).

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

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

((p Ú q) Ù ~ p) ® q.

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

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

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

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

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

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

А «В =_df (А ® В) Ù (В ® А).

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

Из определения знака «непосредственно следует, что правила

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

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

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

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

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

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

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

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

Упражнения

I. Для каждого из следующих элементарных выводов укажите правило (правила) вывода, при помощи которых заключение следует из посылок:

1) ((А Ù В) ® С) ® (А Ù В) ® ((А Ù В) Ù С);

2) (А ® В) ® ((А ® В) Ú (А ® ~ В));

3) ((A Ú B) Ù (C Ú D)) ® (A Ú B);

4) (~(A Ù B) Ù (C ® ~ D)) ® ~ (A Ù B);

5) (((A Ú B) ® (C Ù ~ D)) Ù ~~(C Ù ~ D)) ® ~ (A Ú B);

6) (((A ® B) ® (C Ú D)) (A ® B)) ® (C Ú D);

7) (((E ® (F «~ G)) Ú (C Ú D)) Ù (E ® (F «~ G))) ® (C Ú D);

8) (((C Ú D) ® ((J Ú K) ® (J Ù K))) Ù ~ ((J Ú K) ® (J Ù K))) ® ~ (C Ú D);

9) (((J ® K) Ù (K ® L)) Ù (L ® M)) ® ((J ® K) Ù (K ® L) Ù (L ® M));

10) ((~(L ® (M ® N)) ® ~ (C Ú D)) Ù (~ (L ® (M ® N))) ® ~(C Ú D).

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

1) ((D ® E) ® (D Ù F)) ® E;

2) (G ® H ® ((G Ù H) Ú I);

3) (J ® K) ® J)) ® (K Ú L);

4) (M Ú N) ® (~ M Ù ~ O) ® N;

5) ((P Ù Q) ® R) ® (P Ù R);

6) ((G ® H) Ù (I ® J)) ® G ® (H Ú J);

7) ((P ® Q) Ù (R ® S)) ® ((P Ú R) Ù (Q Ú R)) ® (Q Ú S);

8) ((T ® U) Ù (T ® V)) ® T ® (U Ú V);

9) (((A Ú B) ® C) ® ((C Ú B) ® (A ® (D «E))) ® (A Ù D)) ® (D «E);

10) ((I Ú J) Ù K) ® (~ L ® ~ (K Ù J)) ® (K ® (I ® ~ M)) ® ~ (M Ù ~ L).

Не нашли, что искали? Воспользуйтесь поиском: