1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 41
Текст из файла (страница 41)
При этом такой переход от утвер»кдения к его отрицанию можно осуществить' простой перестройкой фразы, не вникая в ее смысл (с этой точки зрения переход от ложного высказывания «Москва — столица Франции» к истинному — «Париж — столица Франции» или «Москва — столица СССР» — это не то правило перехода от утверждения к его отрицанию с помощью приставки «неверно, что..л, а содержательная подмена одного высказывания другим, выполняемая за рамками формальных законов логики. Анализируя высказывания, образующие цепочку логического рассуждения, мы обнаруживаем в нем то, что обычно называется исходными фактами, т. е.
самыми простыми суждениями, истинность или ложность которых установлена заранее, или, более точно, средствами, находящимися за рамками данного логического рассуя«дения. Правила естественного языка позволяют из исходных фактов составлять более сложные производные высказывания.
При этом, как и в случае правила отрицания, мы усматриваем, что существуют такие правила построения сложных высказываний, в которых свойство высказывания быть истинным или ложным зависит только от истинности или ложности составляющих исходных фактов и от того, каким образом они комбинируются в сложное высказывание. В естественном языке эти правила выглядят как сочленение высказываний с помощью следующих выделенных слов: НЕВЕРНО, ЧТО (НЕВЕРНО, ЧТО Москва — столица Франции) — отрицание; И (шел дождь И шли два студента) — конъюнкция; ИЛИ (он пьет ИЛИ он курит) — дизьюякция; 5 ся, ЛОГИЧЕСКИЕ ФОРМУЛЫ И ВУЛЕВЫ ФУНКЦИИ 191 ВЛЕЧЕТ (преступление ВЛЕЧЕТ наказание, бузина в огороде ВЛЕЧЕТ дядьку в Киеве, свист рана ВЛЕЧЕТ молоко от козла, 2к2 = 4 ВЛЕЧЕТ, что Волга впадает в Каспийское море, но НЕВЕРНО, ЧТО истина ВЛЕЧЕТ ложь) — импликация; ИЛИ...
ИЛИ (ИЛИ он украл пальто, ИЛИ у него украли пальто) — альтернатива; ТО ЖЕ, ЧТО (х простое число — ТО ЖЕ, ЧТО х делится только на себя и единицу) — тождество. Мы позволили себе привести в качестве примеров несколько расхожих выражений, чтобы резче подчеркнуть, что можно точно говорить об истинности или ложности сложных высказываний, даже не задумываясь об их содержательном аначении, если только правила понимания укааанных союзов и оборотов (называемых логическими сеялками) раз и навсегда оговорены.
Эти правила употребления становятся, как обычно, особенно четкими, если их представить в символической форме, в которой исходные факты будут изобран1аться как неаависимые логические переменные, принимающие два значения 1 (ложь) и 1 (истина), а логическис свяаки — как логические операции с двумя а ргументами: хдгу ) — конъюнкция (другое обозначение: хну; х~/ у — диуьюнкция; х л у — имлликация (другое обозначение: х-ъ у; х называется посылкой, а у — заключением импликации); х .+- у — альтернатиеа; х = — у — тождество; н как операция над одним аргументом: 1х — отрицание (другое обозначение: х).
Значениями логических операций являются те же два значения $ и 1. Таким обрааом эти операции полностью описываются таблицами своих значений, нааываемыми таблицами истинности Глядя на эти таблицы истинности и на задающие их логические связки, можно сделать следующее наблюдение: если сложное высказывание осмысленно, то его смысл ие противоречит значе- 192 ГЛ.
«. КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ нию истинности, полученному по правилам вычисления логиче- ских операции. Именно это наблюдение (не теорема!) дает нам Основание верить в полеаность далее развиваемой теории. Логические формулы. Итак, мы осуществляем первый этап построения теории, вводящий некоторую символику для констру- ирования логических формул.
Логические формулы строятся из символов: д, » — логические константы (значения истинности), А, В, С,..., Х, У, Я вЂ” логические переменные, ( ) — скобки, дзуместные логические опера и ) — одноместная логическая операция (в дальнейшем для краткости будем слово «логический» иногда Опускать). Константа или переменная — это первичная формула. Если Ф вЂ” формула, то (Ф) — первичная формула. Если Ф вЂ” первичная формула, то Ф вЂ” одночлен. Если Ф вЂ” одночлен, то 1Ф вЂ” одночлен.
Если Ф вЂ” одночлен, то Ф вЂ” конъюнкция. Если Ф, — конъюнкция, а Ф» — одночлен, то Фдад Ф» †конь- юнкция. Если Ф вЂ” конъюнкция, то Ф вЂ” днаъюнкция. Если Фд — дизъюнкция, а Ф« — конъюнкция, то Фд~/Ф» или Ф + Ф« — дизъюнкции. Если Ф вЂ” дизъюнкция, то Ф вЂ” импликация. Если Ф, — имплдгкация и Ф» — дизъюнкцня, то Ф, Э Ф,— импликация.
Если Ф вЂ” импликация, то Ф вЂ” формула. Если Фд — формула и Ф» — импликация, то Ф, — = Ф, — фор- мула. Других формул нет. Эти педантичные определения хороши тем, что они дают со- вершенно точное определение логических формул, устанавливая Одновременно правила старшинства в выполнении логических Операций. На языке школьной алгебры можно сказать, что рань- ше всего выполняются действия в скобках, потом — в порядке перечисления— отрицание конъюнкция дизъюнкция и альтернатива импликация тождество.
Автор надеется, что этой апелляции к опыту читателя будет достаточно, чтобы удостовериться, что, например, такой текст ХА- ~У~/Я Э 1Х=У'~ 1Хбсу ЗЯшГ8« ~Х (*) $«Л. ЛОГИЧЕСКИЕ ФОРМУЛЪ| И БУЛЕВЫ ФУНКЦИИ юз является правильной формулой, в котором выделение аргументов для каждой операции происходит единственным образом, а именно ((((Х 8«( 1у)) )/ 2):э ( ) Х)) ж((У ~/ (( ) Е) 8«р)) -э у)) вп = — (1'б Г1Х)). Формальный синтаксис. Здесь нам будет уместно несколько отвлечься от основной нити излоя«ения. Дело в том, что только что данное индуктивное определение логических формул основано на общем приеме, который настолько важен в программировании, что не поговорить о нем, имея подходящий повод, было бы непростительно.
Сначала заметим, что для таких индуктивных конструкций применяется простая символика, позволяющая сделать определение более компактным и наглядным. Общий смысл индуктивного определекуя состоял в том, что мы последовательно определяли все более и б(»лее широкие классы формул, начиная с «первичных формул», череа «одночлены», «конъюнкции», «днзъюнкции» и «вмнлнкации» вЂ” к общему понятию «формулы».
Кроме этого, мы вводили промежуточные буквенные обозначения Ф, Ф, Ф, чтобы показать, как конкретно конструируется тот или иной класс формул. Первое правило символики, которую мы сейчас вводим, позволяет вместо буквенных обозначений использовать сами названия строящихся конструкций, заключенные для определенности в угловые скобки. Это позволит вместо фразы «если Фд — имплнкация и Ф, — днаъюнкция, то Ф,:» Ի— импликация» писать короче (имплнкация)к = (нмпликацня) ':э (днзъюнкция) где знак:: = означает«равно по определению». Эта запись, равно как и исходное словесное определение, означает способ задания множества формул, называемых «импликацнями» через мнолестзо «импликаций» же и множество «дизъюнкций» следующим образом.
Надо взять любую «импликацню», приписать к ней знак :э, за которым поместить любую «дизъюнкцию». Полученная строчка текста по определению является элементом множества «имплнкацнй». Заметив, что в нашей системе правил нет никакого заколдованного круга, так как для начального множества импликацнй есть другое определение, которое гласит «если Ф вЂ” дизъюнкцня, то Ф вЂ” имплнкация» пли — в новой символике— (имплнкация) н = (дизъюнкция). Таким образом для импликацни мы имеем два альтернативных определения, которые объединяются вместе с использованием 194 РЛ. Ь. КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКОИ ЛОГИКЕ вертикальной черты, отделяющей в правой части конструкции одну альтернативу от другой: (импликация) и (дизъюнкция)((импликация):э (дизьюнкция) Сама конструкция называется лгеталингвистической формулой, а определяемые конструкции — лгеталингвисгпическими переменными (имея в виду, что нх значениями являются элементы конструируемого множества допустимых обьектов, в данном случае— логических формул).
Все правила для логических формул целиком выглядят следующим обрааом: (константа) л= ЦФ (переменная):: = А )В)С... )Х)У~У (первичное):: = (константа) )(переменная) )((формула) ) (одночлен):: = (первггчное) ! ) (одночлен) (конъюнкция) к = (одночлен) )(коггъюнкция)гк (одночлен) (дизъюнкция):: (коныоикцня))(дизъюнкция) )/ (конъюнкция) ((дизъюнкция) +(конъюнкция) (импликация) к = (дизъюнкция) ((импликация):э (дизъюнкцня) (формула) и = (импликация) ((формула) ьи (импликация,'. В такой трактовке правила аадания формул напоминают грамматику естественного языка, в которой роль частей речи играют металингвистические переменные. Это сходство не случайно, и в математике часто называют языком любой регулярный способ задания конструктивных объектов, образующих некоторое множество А слов в заданном алфавите.
Более точно, языком называют само множество Ь, а способ задания языка г.называют его формальной грамматикой. Строгое описание формальной грамматики само требует некоторой символики, описываемой обычно в каком-то другом языке, называемом метаязыком, используемым для описания языка г., В нашем случае мы описываем язык логических формул, используя метаязык металингвистических формул. Список металингвистических формул называют синтаксисом описываемого языка. Понятно формальной грамматики в применении к естественным языкам сложилось наиболее полно в 50-е годы в работах американского лингвиста и математика Н.
Хомского. Аппарат металингвнстических формул был в 1959 г. предложен американским математиком и программистом Дж. Бэкусом п использован его датским коллегой П. Науром в 1960 г. для описания языка ' алгол 60. В их честь грамматики, описанные с помощью металипгвистических формул, называют БНФ-грамматиками (бэкусовонауроза форма). С тех пор этот аппарат широко применяется для описания яаыков программирования, а в последние годы перекочевывает и в чисто математические работы.
% «л. логичвскик ФОРМУЛЫ и вулевьг Функции Уточнение способа описания логичоских формул позволяет кам теперь более точно сказать, что значит, что «выделение аргументов для каждой операции происходит единственным образом». Пусть нам дана какая-то логическая формула'. По правилам БНФ-грамматики мы усматриваем, что она или оказывается.нмпликацией, или строится из другой логической формулы, анака операции — и некоторой импликации. Читатель моя«от проверить„ что выбор альтернативы в этом анализе будет производиться однозначно. Эта однозначность является важным свойством удачно составленной БНФ-грамматики. Итак, для каждой логической формулы мы можем построить один из двух таких графов: р и чпл~м оссил При атом мы не только единственным образом выбираем альтернативу, но и однозначно разбиваем текст исходной формулы на части, сопоставляемые нижним металингвистическим переменным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
