дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
когда для каждой из таких строк заключение является истинным. Это означает, что заключение тавтологически следует из посылок. В правиле модус поненс посылка р - q и посылка р одновременно являются истинными только впервой строке, таким же является и заключение. Поэтому правило модус поненс представляет собой действительное доказательство. А если бы в истинностной таблице находилась любая другая строка, в которой все посылки были бы истинными, а заключение ложным, то такое доказательство было бы недействительным. Более краткий способ выражения истинностной таблицы для правила модус поненс показан в табл. 3.5, где явно представлены все строки. Нона практике необходимо учитывать только те строки, в которых имеются истинные посылки, такие как первая строка. Глава 3. Методы логического вывода 226 Тем не менее некоторые доказательства могут вводить в заблуждение. Чтобы убедиться в этом, вначале рассмотрим следующий пример действительного доказательства по правилу модус поненс: Если в программе нет ошибок, то программа успешно проходит этап компиляции В программе нет ошибок .'. Программа успешно проходит этап компиляции Сравните его со следующим доказательством, которое немного напоминает доказательство по правилу модус поненс: Если в программе нет ошибок, то программа успешно проходит этап компиляции Программа успешно проходит этап компиляции .'. В программе нет ошибок Является ли это доказательство действительным Схема доказательства рассматриваемого типа является таковой Р +Ч а его истинностная таблица в краткой форме показана в табл. Таблица 3.6. Истинностная таблица доказательства р - q, q; .. р в краткой форме Заключение Посылки Р 'Я Т Т Обратите внимание на то, что это доказательство не является действительным. Безусловно, первая строка показывает, что заключение истинно, если все посылки являются истинными, но третья строка указывает на то, что при всех истинных посылках заключение становится ложным. Таким образом, данное доказательство не соответствует приведенному выше обязательному критерию определения действительного доказательства. Хотя многие программисты хотели бы, чтобы подобные доказательства были истинными, логика (и опыт) показывают, что это Т Т F ,' Т F Т Т Т Т F F 3.6. Правила вывода 227 РЧ Таблица 3.7. Истинностная таблица для доказательства р - q, др в краткой форме Заключение Посылки Р 'Я F Т F Т F F Т Т Т F Т / Т ,' Т Т Данная конкретная схема доказательства известна под разными названиями косвенное рассуждение, правило модус толленс и закон контрапозиции. Правила модус поненс и модус толленс представляют собой правила логического вывода, иногда называемые законами логического вывода. Некоторые из законов логического вывода показаны в табл. 3.8. Латинское слово modus (модус) означает "способ, слово ponere означает "утверждать, а слово tollere — "отрицать. Настоящие названия этих правил модуса и буквальные значения показаны в табл. Правила первых двух типов сокращенно именуются как модус поненс и модус толленс [89]. Номера правил вывода, приведенные в этой таблице, соответствуют номерам, которые были указаны в табл. 3.8. Правила логического вывода могут применяться к доказательствам, в которых участвуют больше чем две посылки. Например, рассмотрим следующее доказательство Цены на микросхемы растут, только если растет курс иены. Курс иены растет, только если курс доллара падает и если курс доллара падает, то курс иены растет. Поскольку цены на микросхемы выросли, курс доллара должен был упасть. доказательство — ошибочно, или недействительно. Данное конкретное ошибочное доказательство называется ошибочным обращением посылки и заключения (fallacy of the Понятие ошибочного обращения определено в табл. 3.9. В качестве еще одного примера укажем, что следующая схема доказательства является действительной, поскольку, как видно в табл. 3.7, заключение является истинным тогда и только тогда, когда все посылки истинны: Глава 3. Методы логического вывода 228 Таблица З.S. Некоторые правила вывода для пропозициональной логики Схемы Закон логического вывода Р 'Ч р 1. Закон отделения (правило модус поненс) .'. q Р +Ч 2. Закон контрапозиции Правило модус толленс 4. Цепное правило (закон силлогизма Г Др. Закон дизъюнктивного логического вывода Закон двойного отрицания ° '. р -р л q) (» vq) 7. Закон де Моргана 8. Закон упрощения гр \/ q РЛд ° ' р р q 9. Закон конъюнкции ...РЛд 10. Закон дизъюнктивного добавления Р -р л q) р -р л q) q 11. Закон конъюнктивного доказательства Таблица 3.9. Буквальные значения различных модусов (правил, или законов) Номер Латинское название Смысл, выраженный как "модус, который" правила вывода modus ponendo ponens modus tollendo tollens утверждая, утверждает отрицая, отрицает отрицая, утверждает утверждая, отрицает modus tollendo ponens modus ponendo tollens 1 3 5 11 q гр Р +Ч q ð Р +Ч q — + 7 .'. Р T pVq ð .. Др. Правила вывода Предположим, что высказывания определены следующим образом Сцены на микросхемы растут У — курс иены растет D — курс доллара падает СУ (У- В) Л(П-У) С Вторая посылка имеет очень интересную форму, поскольку может быть еще больше сокращена с использованием одного из вариантов условного выражения. Условное выражение р - q имеет несколько вариантов, которые представляют собой обратную, противоположную и контрапозитивную форму. Эти формы для полноты перечислены вместе с условным выражением в табл. 3.10. Таблица 3.10. Условное выражение и его варианты Название Запись Условное выражение Обратная форма Противоположная форма Контрапозитивная форма Как обычно, предполагается, что операция отрицания имеет более высокий приоритет по сравнению с другими логическими операциями, поэтому выражения р и д никогда не заключаются в круглые скобки. Если условное выражение р q и обратное ему выражение q - р одновременно являются истинными, то выражения р и q — эквивалентны. Это означает, что выражение р — q Л q — + р эквивалентно двустороннему условному выражению р — q, или эквивалентности р =— q. Обратите внимание на то, что обычные знаки операций присваивания или проверки на равенство записываются с двумя короткими горизонтальными чертами (=), а знак операции эквивалентности записывается стремя чертами (=). Иными словами, выражения р и о, связанные Как было указано в разделе 2.12, одним из значений условного выражения является "р, только если Такое высказывание, как "курс иены растет, только если курс доллара падает, имеет именно этот смысл, поэтому может быть представлено как D - У. Все доказательство имеет следующую форму Глава 3. Методы логического вывода символом эквивалентности, всегда принимают одни и те же истинностные значения. Если р имеет значение Т, то q истинно, а если р имеет значение F, то и q равно F. Приведенное выше доказательство принимает следующую форму () (2) (3) СУ В данном случае числа в круглых скобках используются для обозначения посылок. Поскольку, согласно посылке (выражения У и D эквивалентны, можно подставить D вместо У в посылку (1) и получить следующее выражение (4) СВ данном случае выражение (4) — это результат логического вывода, сделанного на основе выражений (1) и (2). Посылки (и (4), а также заключение применяют такой вид (4) (3) С — D С С — +У УЛУСУ С Эквивалентность 1 Подстановка 3, 5 Правило модус поненс Это доказательство распознается как имеющее схему правила модус поненс, поэтому оно является действительным. Правило, согласно которому допускается подстановка одной переменной вместо другой, по отношению к которой первая является эквивалентной, представляет собой правило логического вывода, называемое правилом подстановки (rule of Двумя основными правилами дедуктивной логики являются правило модус поненс и правило подстановки. Доказательство в формальной логике обычно записывается с применением нумерации посылок, заключения и этапов логического вывода, как в приведенным ниже примере. Ограничения пропозициональной логики 231 В строках 1 — 3 показаны посылки и заключение, а в строках 4 — 6 выполненные этапы логического вывода. В правом столбце указаны правила логического вывода и номера строк, используемых для обоснования этапов логического вывода. Ограничения пропозициональной логики Еще раз рассмотрим используемое в данной книге классическое доказательство Все люди смертны Сократ — человек Следовательно, Сократ смертен р — Все люди смертны q — Сократ — человек r Сократ смертен Таким образом, рассматриваемое доказательство имеет следующую схему Обратите внимание на то, что в посылках и заключении нет логических связок, поэтому для каждой посылки и заключения должна применяться отдельная логическая переменная. Кроме того, в пропозициональной логике не предусмотрено применение кванторов, и поэтому отсутствует способ представления квантора "все" впервой посылке. Таким образом, единственным способом представления данного доказательства в пропозициональной логике является приведенная выше схема, состоящая из трех независимых переменных. Для определения того, является ли это доказательство действительным, рассмотрим истинностную таблицу для трех независимых переменных, в которой используются всевозможные комбинации значений Т и F (табл. 3.11). Вторая строка этой истинностной таблицы показывает, что данное доказательство является недействительным, поскольку посылки истинны, а заключение — ложно. Недействительность этого доказательства не следует интерпретировать в том смысле, что его заключение является неправильным. Любой разумный человек Известно, что это — действительное доказательство, поскольку оно представляет собой действительный силлогизм. Сможем ли мы доказать его действительность с применением пропозициональной логики Чтобы ответить на этот вопрос, вначале запишем доказательство в виде схемы, обозначив высказывание буквами следующим образом Глава 3. Методы логического вывода Таблица Истинностная таблица для схемы р, q; .. r Если Сократ человек, то Сократ смертен Сократ — человек Следовательно, Сократ смертен Обозначим отдельные выражения этого высказывания следующим образом р — Сократ — человек q Сократ смертен признает, что это — правильное доказательство, а то, что проверка по таблице показывает его недействительность, просто означает, что это доказательство не может быть обосновано в рамках пропозициональной логики. То, что данное доказательство является действительным, можно было бы обосновать, исследуя внутреннюю структуру посылок. А для этого пришлось бы, например, приписать определенный смысл квантору "все" и учесть, что слово "люди" множественное число от слова "человек. Но такие области логики, как силлогизмы и пропозициональное исчисление, не позволяют исследовать внутреннюю структуру высказываний. Эти ограничения преодолены в логике предикатов, и поэтому рассматриваемое доказательство становится действительным в логике предикатов. Вся силлогистическая логика фактически является действительным подмножеством логики предикатов первого порядка, и можно показать, что она является действительной именно в рамках этой логики. Единственная действительная силлогистическая форма рассматриваемого выше высказывания является таковой 233 В таком случае доказательство принимает вид А это действительная силлогистическая форма правила модус поненс. В качестве еще одного примера рассмотрим следующее классическое доказательство Все лошади — животные Следовательно, голова лошади — голова животного Известно, что это — правильное доказательство, но оно все жене может быть доказано в рамках пропозициональной логики, хотя его можно доказать с помощью логики предикатов (см. задачу 3.12). 3.8 Логика предикатов первого порядка Силлогистическая логика может быть полностью описана с помощью логики предикатов. В табл. 3.12 показаны четыре категорических утверждения и их представления в логике предикатов. Таблица. Представление четырех категорических силлогизмов с помощью логики предикатов Тип Схема Представление предиката АО Все S есть Р Ни один S не есть Р Некоторые есть Р Некоторые S не есть Р В логике предикатов в дополнение к правилам вывода, описанным выше, предусмотрены правила, относящиеся к кванторам. В частности, в правиле универсальной конкретизации (rule of universal instantiation) по существу утверждается, что вместо универсального объекта может быть подставлен какой-то конкретный объект. Например, если ф — это некоторое высказывание или пропозициональная функция, то приведенное ниже доказательство, в котором а представляет собой экземпляр объекта, является действительным логическим выводом. (Vx) P(x) .'. фа) Логика предикатов первого порядках) (Чх)(Я(х) F(x)) (3x) (S(x) Р(х)) (3x)(S(x) Р(х)) 234 Глава 3. Методы логического вывода Таким образом, переменная а ссылается на конкретный отдельный объекта переменная х пробегает по всем отдельным объектам. Например, следующий логический вывод, в котором обозначена как H(x) пропозициональная функция, указывающая на то, что х — человек, позволяет доказать, что Сократ — человек (Vx) H(x) .. H(Socrates) Фактически выше сказано, что для каждого х, х человек, и поэтому, согласно правилу логического вывода, Сократ — человек. Ниже приведены другие примеры применения правила универсальной конкретизации. (b'õ) Ах) Ас) (у)(В(у) 1/ С(Ь)) .'. В(а) v С) (Чх) Ах) Л (Зх)(В(х) V С .'. А(о) Л (Зх)(В(х) V Су) Все люди смертны Сократ — человек Сократ смертен В первом примере вместо переменной х подставляется экземпляр с. Во втором примере заслуживает внимания то, что экземпляра подставляется вместо переменной у, ноне вместо переменной 6, поскольку b не включена в область определения квантора. Это означает, что такой квантор, как Vx, применяется только к вхождениям переменной х. Такие переменные, как хи у, используемые вместе с кванторами, называются связанными, а другие переменные называются свободными. В третьем примере в область определения квантифицированной переменной х входит только функция А(х). Это означает, что область определения квантора всеобщности не распространяется на квантор существованиях и на область определения этого квантора в составе выражения В(х) Су. Соглашение по использованию выражений с вложенными кванторами, подобных приведенным выше, состоит в том, что область определения первого квантора оканчивается с того места, где вступает в действие новый квантор, если в следующем кванторе применяется такая же переменная, как ив предыдущем (в рассматриваемом случае это — переменная х). Формальное доказательство следующего силлогизма. Логические системы 235 в котором используется обозначения Н — человек, М — смертен и s — Сократ, приведено ниже. (vx)(H(x) — + M(x)) Н) На) — М) М(з) / М) 3. 1 Универсальная конкретизация 2, 3 Правило модус поненс 3.9 Логические системы Логической системой называется коллекция таких объектов, как правила, аксиомы, утверждения и т.д., организованная в единообразной форме Логические системы создаются для достижения нескольких целей. Первая цель состоит в определении форм доказательств. С точки зрения семантики логические доказательства являются бессмысленными, поэтому для определения того, является ли доказательство обоснованным, чрезвычайно важно определить действительную форму доказательства. Таким образом, одним из наиболее важных назначений любой логической системы является определение правильно построенных формул (well formed formula — wff), используемых в доказательствах. В логических доказательствах разрешается применять только правильно построенные формулы. Например, в силлогистической логике выражение Все S есть Р может рассматриваться как правильно построенная формула, а следующие выражения не являются правильно построенной формулой Все Все есть S Р Есть S все Безусловно, символы алфавита лишены смысла, но правильно построенная формула приобретает смысл благодаря применению строго определенной последовательности символов. Вторая цель создания логической системы состоит в том, чтобы указать, какие правила вывода являются действительными. А третьей целью логической системы является обеспечение возможности расширения самой этой системы путем открытия новых правил вывода и тем самым увеличения разновидностей форм доказательств, которые могут быть обоснованы в этой системе. В результате расширения перечня разновидностей форм доказательств появляется возможность Глава 3. Методы логического вывода обосновывать с помощью логического доказательства все новые и новые правильно построенные формулы, называемые теоремами. Если логическая система хорошо разработана, то ее можно использовать для определения обоснованности любых доказательств с помощью способа, аналогичного вычислениям в таких научных системах, как арифметика, геометрия, исчисление, физика и инженерное дело. К настоящему времени были разработаны такие логические системы, как сентенциальное, или пропозициональное исчисление, исчисление предикатов и т.д. Каждая из этих систем основывается на формальных определениях ее аксиом, или постулатов, которые являются фундаментальными определениями данной системы. На основании этих аксиом люди (а иногда и компьютерные программы, такие как Automated Mathematician) пытаются определить, какое доказательство может быть обосновано. Любой, кто изучал евклидову геометрию в средней школе, знаком с аксиомами и стем, как происходит вывод геометрических теорем. Также как геометрические теоремы могут быть выведены из геометрических аксиом, логические теоремы могут быть выведены из логических аксиом. Аксиома — это просто факт, или утверждение, которое невозможно доказать в рамках самой системы. Иногда мы принимаем некоторые аксиомы за истину, поскольку им можно придать "смысл, обращаясь к здравому смыслу или к наблюдениям. А другие аксиомы, такие как "параллельные линии в бесконечности пересекаются, не имеют интуитивного смысла, поскольку противоречат привычной аксиоме Евклида, согласно которой параллельные линии не пересекаются. Но указанная аксиома, согласно которой параллельные линии в бесконечности пересекаются, с чисто логической точки зрения является не менее приемлемой, чем аксиома Евклида, и действительно лежит в основе одного из типов неевклидовой геометрии. Для определения формальной системы необходимо следующее. 1. Алфавит символов. Множество конечных строк, состоящих из этих символов, правильно построенных формул. 3. Аксиомы — определения системы. 4. Правила вывода, позволяющие вывести правильно построенную формулу А как заключение конечного множества других правильно построенных формул, где С = (А1,А2... А. Эти правильно построенные формулы должны представлять собой аксиомы или другие теоремы логической системы. Например, |