1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 45
Текст из файла (страница 45)
Вернемся назад к обсуждению побудительных мотивов к разработке математической логики. Логическая формула — это символическая, сокращенная и точная эдпись некоторого суждения,— высказывания,— ' об исходных фактах — логических переменных, взятых.в определенной взаимосвязи, изобрандаемой с помощью связок — логических операций. Выяснилось, что истинность или ложность высказывания является однозначной функцией значений истинности исходных фактов. Алгебра логики — это способы преобразования логических формул, оставляющие неизменным их логическое содержалие, т.
е. задаваемую ими функцию истинности (булеву функцию). ь 6.3. Исчислении Высклзывлний гг« Среди логических формул естественно выделяются такие„ которые задают тождественно истинную булеву функцию. Этм формулы называются общегначимыми, тавтологиями, или логическими законами, Напишем несколько формул подобного рода и дадим одновременно их словесное выражение. А~/ 1 А: каково бы ни было высказывание А, справедливо„ что А либо истинно, либо ложно; А~ А~/В:извсякого факта А следует.он сам, каков бы нж был дополнительный факт В; (А:э В):э (С~/А~ С~/В): каково бы ни было отношение- следования, оно сохраняется при рассмотрении как посылки, так и ааключения в дизыонктивном объединении с любым дополнительным фактом С. Понятие общеаначимости подчеркивает тот факт, что задаваемая формулами булева функция сохраняет свое значение истинности на всех значениях аргументов.
Понятие тавтологии подчеркивает, что тождественно истинное утверждение является в некотором смысле тривиальным, не дающим никакой информации о вааимосвязи входящих в него высказываний. Действительно, если мы знаем, что А б«В истинно, то мы знаем,что и Аи В являются истинными утверждениями.
Однако же истинность утвержде-- ния А ~ А~/В не налагает никаких связей на А и В. Таким образом, общезначимая формула характеризует скорее некоторое. свойство входящих в него логических связок, проявляющее себя безотносительно не только к смысловому содержанию, но дая«е и к значениям истинности входящих в нее логических переменных. Эта высшая степень общности подчеркивается употреблением термина «логический законы Сконцентрировав наше внимание на общезначимых формулах мы немедленно усматриваем тесную связь вопроса с равносильными преобразованиями логических формул.
Действительно, иь сделанных определений немедленно вытекает Те о р е ма 8. Пусть А и  — логические формула. Равносильность А В будет тоокдеставенной тогда и только тогда, когда формула А пи В общегьачима. Эта теорема наводит нас на мысль, что задача нахождению системы равносильных преобразований логических формул является лишь частным случаем более общей задачи построения исчисления, позволяющего выводить из некоторых аксиом с помощью. правил вывода все общезначимые формулы, в том числе и те, которые описывают тождественные равносильности.
Мы приступим к рассмотрению атой задачи, опираясь на опыт. построения исчисления равносильностей алгебры логики. Нам. уже приходилось мимоходом замечать некоторую пестроту, разноплановость аксиоматики равносильностей. Одки аксиомы отражают скорее свойства способа конструирования формул («скоб- яэ гл. а кРАткое повтОРение мАтемАтическои логики кология» аксиом А12 — А14), нежели свойства логических операций. Другие аксиомы просто выражают одну операцию через другие (например, А11) или один объект через другой (например, А1).
Действительно, А кв В общезначима тогда и только тогда, когда общеаначима.'формула (А~ В) й (В:»А).Любаяконъюнкция общеаначима тогда и только тогда, когда общезначимы ее сомножители, в данном случае, А ~ В и В ~ А. Другими словами, если уметь выводить общезначимые формулы вида А:»В и располагать правилом вывода «если выводимы А и В, то выводимо Ай В», то все общезначимые формулы, которые можно трактовать как эквивалентности, будут выводимы. Таким образом, в отличие от других логических операций, мы трактуем знак вв не как фундаментальную логическую связку, смысл которой раскрывается независимыми аксиомами, а как обозначение более сложной конструкции, вводимое ради сокращения письма. ' В атом направлении можно пойти и дальше.
В качестве синонима 1 можно ваять, например, формулу Х')/ ) Х, а 1 изображать формулой Х 8с ) Х, и все мыслимые общезначимые формулы, упоминающие значения истинности, стараться выводить с учетом атой синоннмни. Можно, далее, упростить синтаксис логических формул, отказавшись от формализации старшинства двуместных операций: (переменная):: = А)В(С) ... )Х)1 (Я (первичное):: = (переменная)( ~(операнд) (операнд) к = (первичное))((двучлен)) (двуместная операция):: ~/(л)~ (двучлен) к (операнд)(двуместная операция) (операнд) (формула):: (первичное))(двучлен) Опять-таки, мы можем по соглашению опускать скобки в формулах, но это уже будет содержательное сокращение для удобства написания и чтения, а не правило формальной теории.
Повсеместное испольаование схем аксиом поаволит избавиться от правила вывода, разрешающего аамену переменных и подстановку. Исчисление высказываний. После сделанного предисловия мы продемонстрируем исчисление общезначимых логических формул (исчисление Ь), близкое к описанному американским математиком С. Клики в 1952 г. Исчисление высказываний (исчисление Ь) Схемы аксиом А1) А~ (В~ А) А2) (А ~ (В:з С)) ~ ((А ~ В):э (А:» С)) АЗ) (АЙВ)~ А А4) (А А В):» В % 6.3.
Нсчислкник ВыскАзыВАнии 213 А 5) А ~ (В ':) (А й В)) Аб) А:э(а ~/ В) А7) В:з(А ~/ В! А8) (А~С):э((В:ЗС)~((А Ч В) ~ С)) А9) ( )А~ ~В)~ (( 1А:э В)-э А), Правило вывода ПХ) зг (зл)':>(м) Исчисление выскааываний корректно, если любая выводимая формула оказывается обййзначимой, и полно, если любая обще- значимая формула выводима в атом исчислении. Для исчисления высказываний важным является еще одно свойство — иелротилоречивость, т. е. несуществование такой формулы А, чтобы в исчислении вь(водились как А, так и 1А. Понятие непротиворечивости позволяет по-другому сформулировать свойство полноты: исчисление выскааываний является полным (в узком смысле), если добавление к нему хотя бы одной невыводимой из него формулы в качестве аксиомы делает расширенное исчисление противоречивым. Описанное исчисление Ь корректно и полно,непротиворечиво и полно в узком смысле.
Свойства непротиворечивости и полноты в узком смысле интересны тем, что они определяются в терминах самого исчисления, не требуя интерпретации формул как конструкций, задающих функции истинности. В то же время эти свойства (по крайней мере для исчисления Ь) в точности соответствуют свойствам корректности и полноты, использующим понятие общезначимости. Способность исчисления высказываний характеризовать свои полеаные сйойства, не используя интерпретацию, основанную на.понятиях истинности и ложности, а опираясь только на понятие противоречия, понимаемого к тому же чисто формально, является своеобразной чертой логики выскавываний, не столь частой для формальных теорий *).
Поясним аксиоматику исчисления Ь. В атих неформальных пояснениях мы будем трактовать высказывания как события, влекущие одно другое. Аксиома А1 постулирует, что наличное событие может быть признано следствием любого другого еобытия (аистина следует иа всегоь). Аксиома А2 подтверждает„что если руществует цепная двуввенная зависимость событий и наличествует первое звено цепоч- ° ) Позволял себе некоторую вольность в ацалогллв, можно залетать, что эта авеоблаатольиостьэ ввтерпротацвв лагкое~жив айокааываввй как васвтолей истинности влл ложвостл отрюкает бытующее мнение, что длл фор мал ьвого логического расоуждоввя ла первом месте стоит вмавво его новротл воречлвость суждеввй, а ва алражшьвооты аавлючитальвого вывода.
2$4 ГЛ. В. БРАТКОВ ПОВТОРВНИВ МАТВМАТИЧВСКОН ЛОГИКИ ки, то допустимо считать, по исходное собьпие влечет заключительное. Аксиомы АЗ и А4 постулируют, что наличие совместного события влечет наличие каждого иэ его составляющих событий. Аксиома А5 постулирует, по последовательное наступление двух событий влечет наступление совместного события. Аксиомы Аб и А7 показывают, что наступление любого из двух событий выаывается либо одним, либо другим событием.
Аксиома А8 гласит, что если каждое из двух событий влечет третье, то для гарантии его наступления нам достаточно знать„ что имело место любое иэ них. Аксиома А9 постулирует метод доказательства от противного: если посылка влечет как заключение, так и его отрицание, то посылка неверна. Правило П1 — это хорошо известное в логике правило ваключения: если известно, что при заходе солнца наступает ночь, и известно, что солнце зашло, то справедливо заключить, что ночь наступила. Свойства исчисления высказываний.
Корректность исчисления Ь устанавливается очень просто с использованием таблиц истинности. Доказательство остальных свойств требует целой серии промежуточных утверждений, большинство из которых имеют самостоятельное значение в качестве правил логического вывода. Говоря об исчислении Т, мы уже употребляли понятие «условного вывода», используемого как доказательство некоторого производного правила вывода. Условный вывод — зто дерево вывода, корнем которого является выводимая конструкция, а среди терминалов могут быть как аксиомы, так и вхождения произвольных формул, играющих роль посылок.
Для сокращенной записи утверждений о существовании условного вывода формулы (схемы формулы) В из множества посылок (А»..., А„) употребляется «знак выводимостн») —, с помощью которого утверждениеобусловной выводимостн записывается в виде так называемой секвенции А„..., А„)- В. Запись )- В означает утверждение о (безусловной) выводимости В. Условную выводимость В нэ посылок А„... ..., А„называют просто виводимвстью В из Ам..., А . Разрешается, чтобы реальное'дерево вывода В из посылок Ап..., А„ содержало бы в качестве терминальных вершин вхождения из любого подмножества нз (А„..., А„). Правила логического вывода ТЛ: Если А,..., А„, А„) — В, то А„..., А„, )- А„:» В. $ аз.
исчислвние выскАзывАнии 215 Другое обозначение: Л>' '"' А» — >' А,> > Т2: А, А:»В~ — В, ТЗ: А, В» — АЬВ, Т4: А>йВ(-А, Т5: А>хВ~ — В, ТГ>: А (- А )/ В, Ту: В~ — А~/В, А„...,А„,В )-0,А„...,А„,С)- Р Л,, ..., А„, В '>/ С )- >» Л,..., А„, 1В~-С,А„...,А„, ~В)- 1С А>,..., А„~н Т10: ) ~А) — А. Правило Т1 называется теоремой о дедукции. В сочетании с Т2, которое, являясь правилом вывода П1, помещено в этот перечень для полноты, эта теорема объясняет точный логический смысл импликации как эквивалента выводимости: ~ — А:» В тог- да и только тогда, когда А )- В. Остальные правила, опираясь на эту эквивалентность, являются перефразировками и простыми обобщениями аксиом из исчисления Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
