Логика - Учебник - Войшвилло Е.К., Дегтярев М.Г. (PDF). Учебник для студентов высших учебных заведений
 Скачать 3.83 Mb.
|
|
НАТУРАЛЬНАЯ СИСТЕМА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ Постулатами натуральной системы являются только правила вывода. В выводах и доказательствах в качестве посылок используются только допущения. К их числу можно относить, конечно, и специальные аксиомы теорий, отличая их при этом от таких допущений, которые играют в доказательствах промежуточную роль ив конечном счете, исключаются из доказательств. Более того, всякий выводи в частности, доказательство) начинается с некоторых допущений. Мы будем строить выводы, учитывая зависимость получаемых в них на каждом шаге результатов — формул вывода от введенных допущений. Указания на эту зависимость будут называться характеристиками зависимости формул вывода отд опущен и й . Каждый шаг вывода, представляющий собой некоторую формулу этого вывода с характеристикой зависимости, будет иметь вид А Г, где А — сама формула вывода, а Г — множество формул, от которых зависит Л в этом выводе. Г — может быть, конечно, и пустым множеством. Этот случай будет указывать, что формула является законом логики и вместе с этим — теоремой логического исчисления Понятие зависимости формул определяется индуктивно: Каждое допущение вывода зависит от самого себя. Это означает, что характеристикой зависимости допущения А является одноэлементное множество Л, однако фигурные скобки мы далее будем опускать и будем употреблять обозначение А А. Для остальных формул вывода, получаемых по правилам вывода из других, зависимости определяются в самих формулировках правил. Правила вывода Мы будем рассматривать систему, включающую в качестве постулатов правила вывода (исходные правила) относительно всех ранее выделенных в языке логики высказываний логических констант (связок конъюнкции, дизъюнкции — импликации — и отрицания Как обычно в натуральных системах, для каждой логической константы имеется правило введения этой константы и правило удаления ее (этим объясняются специальные обозначения правил, например — правило введения конъюнкции », » — первое и второе правило исключения конъюнкции А, В, С — далее любые формулы; Г, Д — любые, возможно пустые, множества допущений. В правилах мы различаем также посылки применения данного правила с характеристиками зависимости (записываются над чертой) и заключения применения данного правила, — формула с характеристикой зависимости (указывают под чертой. Посылки — уже имеющиеся в выводе формулы, аза- ключение — формула, которую согласно правилу мы имеем право добавлять (и добавляем при применении правила) к имеющемуся выводу. Итак, мы принимаем следующую систему правил А[Г],В[А] множеств Г и А, то есть ГА Для завершения описания исчисления необходимо сформулировать понятие вывода и доказательства. Выводом некоторой формулы Виз множества допущений А называется непустая конечная последовательность формул с характертистиками зависимости ... , в которой каждая формула есть либо допущение, либо поручена из предыдущих по какому-либо правилу вывода, причем есть В (заключение вывода, а — некоторое множество допущений Г, являющееся подмножеством А. Ясно, что данную последовательность можно охарактеризовать также Поданной формулировке это правило выглядит как введение дизъюнкции. В каком смысле оно является исключением дизъюнкции, будет разъяснено позже. Вместо правила может быть взято прямое правило Это известная форма вывода, называемая modus tollendo ponens разделительного силлогизма • 123 как вывод Виз Г. Характеризуя же его как вывод из А, мы подчеркиваем то обстоятельство, что каждый вывод формулы В с характеристикой Г, представляет бесконечное множество выводимостей, поскольку А может быть любым расширением Г. Выводимость Г В является для данного вывода наиболее сильной, так как в выводе использованы все допущения изданного множества Г (хотя возможен и другой вывод с меньшим числом использованных допущений). Данная система исчисления эквивалентна рассмотренной выше аксиоматической формулировке исчисления высказываний. Это значит, что формализация следования здесь адекватна, то есть каждому случаю отношения следования ГА в системе соответствует отношение формальной выводимос- ти ГА и наоборот. Поскольку согласно определению следования Если В следует из Г, то оно следует из любого расширения Г, постольку аналогичное свойство имеет и отношение формальной выводимости (если Г В то и А В где А любое расширение Г, то есть Итак, вывод с заключением В зависящим от множества допущений Г — при непустом Г — мы будем обычно характеризовать как Г В В случае если Г пусто, вывод называется доказательством формулы В и характеризуется как В (вывод Виз пустого множества допущений. Но ив этом случае любое доказательство В представляет собой также вывод А В при любом Очевидно, что в силу указанного понятия [Г] выводимости правомерно правило допускающее возможность расширения характеристик зависимости. Это правило, называемое часто правилом утончения и являющееся производным, мы будем применять наряду с указанными выше основными правилами (как будет показано дальше, его применение может быть исключено за счет более сильной формулировки правил И Формально — как производное правило — оно может быть получено из основных правил системы) В самом деле, положим, что в каком-то выводе получено заключение В с характеристикой зависимости Г, то есть имеем В Г. Тогда мы можем продолжить этот вывод, добавив допущение А то есть Л Аи получить (по правилу А Га отсюда (по правилу ) — ВАГ. Итак имея в выводе В Г, мы по основным правилам системы получили ВАГ .Рассмотрим теперь несколько примеров выводов и доказательств. Допущения будем выделять знаком + ». Как и обещали, приведем доказательство закона тождества. Пример 1. Схема доказательства формул вида A A — закон тождества \.А[А] ; 2. А ИЗВ дальнейшем, как ив приведенном примере, будем нумеровать все формулы вывода и для упрощения записей вместо формул характеристиках зависимости будем указывать их номера в выводе. Пример 2. Схема доказательства формул вида — закон экспортации: + 1. + 2. А [2]; + 3. В [3]; 4. & Виз и 3, 5. 3] — из 1 и 2] — из. Аз из 6, 8. [-] — Последовательность представляет собой здесь доказательство нужной формулы. Любая часть этой последовательности есть некоторый вывод. Так, часть 1 есть вывод (А & В z> С часть представляет собой вывод (А & В С, А В Сит. п. Пример 3. Схема доказательства формул вида закон консеквента: + 1. + 2. В. А — из правило утончения — из из Решение вопроса о том, какие вспомогательные допущения использовать для построения того или иного вывода, относится к числу творческих моментов. Приданном построении системы (с характеристиками зависимости) в вывод могут вводиться, вообще говоря, любые допущения, они просто не найдут отражения в характеристиках зависимости. Любое допущение может использоваться независимо оттого, применялись ли правила, исключающие его. Однако при введении вспомогательных допущений существенно иметь ввиду возможность устранить в конечном счете зависимость от них подлежащей выведению или доказательству формулы. Это может быть осуществлено только применением правил С учетом этого могут быть указаны некоторые эвристические принципы введения допущений. Если в качестве заключения вывода должна быть получена формула вида то можно использовать в качестве вспомогательных допущений стремясь вывести В Формула, выведение которой является конечной целью, может быть получена тогда, очевидно, по Правило обеспечивает возможность строить выводы по принципу или, способу, опровержение сведением каб- сурду», а в сочетании с также по принципу доказательство от противного. Первый способ состоит в том, что, желая вывести отрицание некоторого высказывания В то есть берут в качестве допущения В конечно, в дополнение к другие посылкам, например, допущениям, введенным согласно пункту 1). Цель теперь должна состоять в том, чтобы получить противоречие (абсурд, то есть вывести некоторое Тогда по получаем В ипритом независящее от допущения В. Способ доказательства от противного состоит в том, что, желая вывести В вводим допущение В Если теперь удастся вывести некоторое Си его отрицание Сто получаем Вне зависящее от допущения и выводим нужное В. Конечно, для того, чтобы полнить упомянутые в пунктах и 3 Си Смогут понадобиться дополнительные допущения. Так, если Весть высказывание вида v то наряду с можно использовать или (или и то, и другое. Это целесообразно, в частности, когда желательно иметь в выводе или Совершенно очевидно, что уже в указанных допущениях содержится противоречие, которое обнаруживается как только (или ) мы получаем v из (или Аналогично, если учесть, что эк Бивалентно A v В — желая получить А или В при наличии в выводе (А В) — следует брать допущения А или В. Если В которое желательно вывести, имеет вид то вывод его, очевидно, обеспечен (по если выведены и Для осуществления выводов этих составляющих, естественно опираться на сформулированные уже принципы. Рассуждая, например, по принципу доказательство от противного, можем ввести допущения и. Если в некотором выводе получена формула вида а цель состоит в получении некоторой (отличной от указанной) формулы С, которую не удается вывести имеющихся посылок, естественно прибегнуть к способу рассуждения по случаям, вводя сначала допущение А, затем В и стремясь в каждом случае получить С. Если С выводимо при допущении А невыводимо также из допущения В (независимо от А), то получаем С независимо от допущений А В (если v В является в выводе допущением, то Сбудет зависеть теперь от него. (Введенная выше оговорка относительно того, что при допущении В формула С должна быть выведена независимо от допущения Ане означает каких-либо ограничений на применение правила В случае невыполнения оговоренного условия мы просто не получим желаемого резуль- тата.) Мы уже упоминали выше, что наличие правила утончения необязательно в данной системе. Можно заметить (см. примеры 3 и 4), что оно применяется только в двух существенных случаях, связанных с правилами и Первое указывает на то, что если выведена некоторая формула В зависящая от множества допущений Г, и при этом мы хотим получить высказывание A В тогда нужно, — согласно формулировке правила — чтобы в числе элементов Г была и А. Однако согласно понятию логического следования в применении к системе рассматриваемых логических связок (классической логике) это необязательно, то есть мы можем получить В даже в том случае, когда Вне зависит от А. Это позволяет сформулировать правило в виде В ГА любое имеющееся в выводе допущение (при этом если его нет в выводе, то его всегда можно приписать) и где ГА есть множество допущений, которое получается из Г исключением А (если, конечно, таковое имеется в Г, в противном случае, ГА есть само Г ясно также, что если ГА, то ГЛ) есть пустое множество, как в примере доказанной выше формулы А А). Аналогично дело обстоит и с правилом введения отрицания Содержательно правомерно выводить совокупности формул В и ив том случае, когда какая-нибудь из этих формул и даже обе не зависят от А. Отсюда возникает возможность более общей формулировки этого правила ГА любое имеющееся в выводе допу- щение. • У пр аж не ни я. Осуществите доказательства, данные в примерах 3 и без применения правила утончения, пользуясь только что введенными формулировками правили. Постройте доказательства формула) (A В (А & В — закон импортации; б) (А В А) — закон контрапозиции; в) — закон сильной контрапозиции; г) — закон Пирса. Осуществите выводы: а) б) СВ СВ С. Постройте доказательства формул (законов логики, соответствующие выводимостям упражнения 3): а) б) в) Мы уже употребляли такие понятия, как основные правила и производные. Основные это исходные правила системы (постулаты системы. Производным является правило, заключение которого может быть выведено из его посылок по основным правилам. Мы могли видеть это уже на примере правила утончения. По существу, таким образом производные правила — это некоторые выводы по основным правилам системы. Они используются в системах для сокращения выводов применение производного правила есть сокращение именно того вывода, которое оно представляет. Если читатель выполнил предшествующее упражнение 3, тотем самым он получил три производных правила: Ясно, что применение производных правил не является обязательным каждое такое применение может быть заменено соответствующей этому правилу последовательностью формул. Читателю должно быть ясно и то, что каждой доказуемой в системе формуле (теореме) вида AID В соответству- А[Г] ет производное правило Упражнение. Доказать теоремы: б) ((A В & (A ID (А В & и указать соответствующие им производные правила. Существенное значение при анализе рассуждений имеет различение прямых и непрямых правил. Прямые правила указывают на выводимость какого-то высказывания из каких-либо высказываний (в исчислении — выводимость формулы из формул. В предлагаемой системе все правила сформулированы как прямые. Однако существенной особенностью обладают правила введения импликации введения отрицания и правило исключения дизъюнкции В отличие от других они исключать некоторые 129 допущения из характеристик зависимости формул (возможно с заменой их — как при — другими допущениями), что характерно для непрямых правил рассуждения. При применении исключаются допущения Аи с заменой их на A v В при « и « исключается допущение А. В других системах (без характеристик зависимости) они формулируются явным образом как непрямые, соответствен- но: В этой формулировке очевидна их особенность, состоящая в том, что они указывают на возможность заключения о наличии некоторой выводимости на основе других выводи- мостей. Специфика их в рассуждениях состоит в том, что они дают возможность использовать в рассуждениях наряду сданными посылками вспомогательные допущения с последующим исключением их из рассуждения. Так, желая получить вывод Г, A v В С мы совершаем обходной маневр, используя правило : учитывая указанные в дизъюнкции v B возможности — истинность А или истинность В — рассуждаем по случаям — осуществляем вывод ГС соответствующий случаю истинности Аи вывод Г В С, соответствующий случаю истинности В Пользуясь указанным правилом заключаем после этого о наличии нужной нам выводимости Г, A v В С (здесь содержится обещанное ранее разъяснение, почему именно данное правило называется правилом исключения, а не введения дизъюнкции дизъюнкция исключается из рассуждения. Например, надо вывести, что данное число делится на 5» — из дизъюнкции это число оканчивается на 0 или на 5» — (A С уче- В силу того, что само это правило часто называют правилом рассуждения по случаям том множества аксиом арифметики и выводимых из них утверждений — Г и рассуждая по случаям, осуществляем сначала вспомогательные выводы ГАС и Г В С, затем заключаем о наличии нужной нам выводимости: Г, A v В С. По правилу вместо того, чтобы непосредственно выводить условное высказывание посылок Г (что обычно представляет определенную сложность, мы заключаем она- личии этой выводимости на основе вспомогательного вывода Г, В Из аксиом геометрии Г можно вывести «если углы, полученные при пересечении двух параллельных линий третьей, являются соответственными (Л, то они равны В на основании вспомогательного вывода ГЛ В. Правило в истории логики, как ив конкретных науках, например, в математике, известно как опровержения путем каб сур- ду». Часто этот прием опровержения составляет часть другого рассуждения, которое называется доказательством от противного. Этой форме рассуждения соответствует также не- Г, прямое правило Оном о же т быть получено из предыдущего с использованием правила снятия двойного отрицания обозначенного в нашей системе как Г, По правилу опровержения имеем теперь по правилу получаем ГА. Желая доказать, например, что согласно аксиомам геометрии (Г) изданной точки плоскости, лежащей вне этой плоскости, можно опустить только один перпендикулярна прямую, принадлежащую этой плоскости, предположим, что это А неверно, то есть имеет место (можно опустить не один, по крайней мере, два перпендикуляра. Теперь оказывается, что если из точки опущено два перпендикуляра, то сумма углов полученного треугольника больше 180°, поскольку каждый перпендикуляр образует с соответствующей прямой угол, равный 90° (обозначим это В оно представляет собой отрицание утверждения Во том, что сумма углов всякого треугольника равна 180°, которое является следствием аксиом геометрии, а значит, и расширения множества Г за счет добавления нашего утверждения Таким образом, мы имеем две вы- водимости: Г В и ГАВ по указанному правилу доказательства от противного получаем отсюда ГАВ дополнение к уже рассмотренным примерам законов логики приведем список некоторых других наиболее важных схем законов логики (которые читатель может использовать в качестве упражнений для доказательств (В ((A & B) v & 11. (A v (B z> ((A v B) & (A Эти законы, как нетрудно заметить, выражают связь между логическими константами языка логики высказываний. Язык, логика и исчисление предикатов ЯЗЫК ЛОГИКИ ПРЕДИКАТОВ Приступая к изучению языка логики предикатов, полезно вспомнить основные особенности языков этого типа (см. § К языку логики предикатов (сокращенно — ЯЛП) мы переходим от языка логики высказываний, устраняя те недостатки последнего, которые были связаны с лежащим в его основе абстракциями относительно пропозициональных переменных. В ЯЛП явно должны быть представляемы субъектно- предикатные структуры высказываний, от которых происходило отвлечение при введении пропозициональных символов. Выражаемыми должны быть, например, высказывания видов а обладает свойством Р, аи Ъ находятся в отношении Р, Для всякого предмета из некоторого множества верно, что он обладает свойством Р, Для всякого предмета из множества S существует предмет этого множества такой, что эти предметы находятся в отношении Если неверно, что всякие два предмета некоторого множества находятся в отношении то существуют по крайней мере два предмета этого множества, не находящиеся в этом отношении, Если в множестве 5 существует предмет х который находится вот- ношении R с любым предметом у этого множества, то для всякого предмета у того же множества существует предмет х такой, что последний находится в отношении R к первому» и т. п. Ясно, во-первых, что для выражения таких утверждений у нас нет средств в языке логики высказываний. Ясно и то, что для выражения подобных высказываний в ЯЛП мы должны иметь в числе его исходных символов общие имена предметов аналогами последних в ЯЛП будут предметные переменные х, у, z, а также они же с числовыми индексами ... и т.д. Потребность в общих именах при употребле- ний ЯЛП сохранится лишь для описания областей возможных значений этих переменных, что относится уже не к самому языку, а к метаязыку. Нужны также знаки свойств и отношений. Для выражения высказываний вида Объем тела больше объема тела Ь или Синус х меньше косинуса и т. п конечной предметные функторы. Впрочем, перечислим систематически основные типы выражений описываемого языка, каковыми являются исходные символы, термы и формулы. Описание этих выражений составит синтаксис ЯЛП. |