Теорія програмування

КРАТКОЕ ПОВТОРЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

§ 6.1. Логические формулы и булевы функции

Предмет логики. Логика, подобно арифметике и геометрии, является одной из математических дисциплин, с предметом кото­рой человек, даже того не ведая, имеет дело с первых лет своей сознательной жизни. Более правильным было бы, пожалуй, ска­зать, что законы правильного рассуждения о предметах и явле­ниях, наряду со свойствами форм предметов и количественными соотношениями между предметами, являются главным содержанием: математики, если говорить о ее вкладе в повседневную человече­скую практику. Интересно, однако, отметить, что логика, буду­чи как организующий элемент человеческого общения много стар­ше математики, стала сама объектом математического изучения совсем недавно: по-настоящему лишь в конце девятнадцатого века. Это тем более парадоксально, что математическая логика в чем-то проще многих других^ разделов математики. Этому парадоксу есть свое объяснение, которое, однако, автор не может изложить здесь с должной глубиной. Мы заметим только, что, с одной сто­роны, математики в течение долгого времени и при этом в целом успешно полагались на здравый смысл в применении законов ло­гического рассуждения, пока конкретный математический мате­риал (обоснование математического анализа, парадоксу теории множеств, неевклидова геометрия) не подвели их к необходимости заняться логическими основами самой математики. С другой сто­роны, необходимо было достичь высокого уровня абстрактного мышления и своего рода доверия к символике, чтобы правильно найти исходные абстракции логических рассуждений и быть уве­ренным в универсальной применимости формально выведенных законов логики, выраженных в символической форме.

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

Одна из целей логического рассуждения — это установление истины, т. е. возможности достоверно подтвердить или опровер­гнуть некоторое высказывание. Уже в одной этой фразе содержат­ся одновременно некоторое наблюдение и некоторое ограничение. Человек рассуждает, произнося фразы на человеческом, или, как говорят, естественном языке. Ограничение состоит в том, что мы рассматриваем лишь такие фразы естественного языка (высказы­вания), о которых имеет смысл говорить, что они правильны или неправильны, истинны или ложны. Наблюдение подсказывает нам, что свойства истинности или ложности оказываются взаимно дополняющими; другими словами, естественный язык устроен так, что если мы имеем некоторое ложное высказывание («Москва — столица Франции»), то всегда можно высказать его отрицание, являющееся истинным высказыванием («Неверно, что Москва — столица Франции»), и наоборот. При этом такой переход от утвер­ждения к его отрицанию можно осуществить" простой перестрой­кой фразы, не вникая в ее смысл (с этой точки зрения переход от ложного высказывания «Москва — столица Франции» к истин­ному — «Париж — столица Франции» или «Москва — столица СССР» — это не то правило перехода от утверждения к его отри­цанию с помощью приставки «неверно, что...», а содержательная подмена одного высказывания другим, выполняемая за рамками формальных законов логики.

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

НЕВЕРНО, ЧТО (НЕВЕРНО, ЧТО Москва — столица Фран­ции) — отрицание;

И (шел дождь И шли два студента) — конъюнкция;

ИЛИ (он пьет ИЛИ он курит) — дизъюнкция;

ВЛЕЧЕТ (преступление ВЛЕЧЕТ наказание, бузина в ого­роде ВЛЕЧЕТ дядьку в Киеве, свист рака ВЛЕЧЕТ молоко от козла, 2x2 = 4 ВЛЕЧЕТ, что Волга впадает в Каспийское море, но НЕВЕРНО, ЧТО истина ВЛЕЧЕТ ложь) — им­пликация;

ИЛИ . . . ИЛИ (ИЛИ он украл пальто, ИЛИ у него укради пальто) — альтернатива;

ТО ЖЕ, ЧТО (х простое число — ТО ЖЕ, ЧТО х делится только на себя и единицу) — тождество.

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

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

х & у - конъюнкция (другое обозначение: х /\ у;

х \/ у — дизъюнкция;

х $\supset$ у   — импликация (другое обозначение: х-± у;
х называется посылкой, а у — заключением импликации);

 x + y — альтернатива;

х ≡ у — тождество;

 и как операция над одним аргументом:

 ~]х — отрицание (другое обозначение: х).

 Значениями логических операций являются те же два значения f и t. Таким образом эти операции полностью описываются табли­цами своих значений, называемыми таблицами истинности

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

Логические формулы. Итак, мы осуществляем первый этап построения теории, вводящий некоторую символику для констру­ирования логических формул.

Логические формулы строятся из символов:

f, t — логические константы (значения истинности), .

A, B, С, . . ., X, У, Z — логические переменные,

( , ) — скобки,

 — двуместные логические операции,'

 — одноместная логическая операция {в дальнейшем для краткости будем слово «логический» иногда спускать).

Константа или переменная — это первичная формула.

Если Ф — формула, то (Ф) — первичная формула.

Если Ф — первичная формула, то Ф — одночлен.

Если Ф — одночлен, то  Ф — одночлен.

Если Ф — одночлен, то Ф — конъюнкция.

Если Ф₁ — конъюнкция, а Ф₂ — одночлен, то Ф₁& Ф₂—конъюнкция.

Если Ф — конъюнкция, то Ф — дизъюнкция.

Если Ф₁ — дизъюнкция, а Ф₂ — конъюнкция, то Ф₁\/ Ф₂ или

Ф₁ + Ф₂ — дизъюнкции.

Если Ф — дизъюнкция, то Ф — импликация.

Если Ф_х — импликация и Ф₂ — дизъюнкция, то Ф₁  Ф₂ — импликация.

Если Ф — импликация, то Ф — формула.

Если Ф₁ — формула иФ₂- импликация, то Ф₁ ≡ Ф₂ — фор­мула.

Других формул нет.

Эти педантичные определения хороши тем, что они дают со­вершенно точное определение логических формул, устанавливая одновременно правила старшинства в выполнении логических операций. На языке школьной алгебры можно сказать, что рань­ше всего выполняются действия в скобках, потом — в порядке перечисления — отрицание конъюнкция

дизъюнкция и альтернатива

импликация

тождество.

Автор надеется, что этой апелляции к опыту читателя будет достаточно, чтобы удостовериться, что, например, такой текст

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

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

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

Пусть нам дана какая-то логическая формула. По правилам БНФ-грамматики мы усматриваем, что она или оказывается им­пликацией, или строится из другой логической формулы, знака операции = и некоторой импликации. Читатель может проверить, что выбор альтернативы в этом анализе будет производиться од­нозначно. Эта однозначность является важным свойством удачно составленной БНФ-грамматики. Итак, для каждой логической формулы мы можем построить один из двух таких графов:

 

При этом мы не только единственным образом выбираем аль­тернативу, но и однозначно разбиваем текст исходной формулы на части, сопоставляемые нижним металингвистическим переменным. Это означает, что для каждой из выделенных, как говорят, «прямых конституент» исходной формулы мы можем в свою очередь однозначно выбрать составляющие их подформулы, нарастив наш граф снизу еще одним слоем металингвистических пе­ременных или символов исходного алфавита. Этот процесс «разбора» формулы будет продолжаться, пока по каждому направлению в строящемся графе (он, очевидно, окажется деревом) мы не доберемся до символа исходного алфавита, который станет терминалом дерева. Полученный граф, который оказался построен­ным однозначно для взятой логической формулы, называется ее деревом разбора. Его вершинами яляются символы исходного алфавита и металингвистические переменные. Для краткости и об­щности первые называются терминальными, а вторые — нетерминальными символами БНФ-грамматики.        |

Дерево разбора для приведенной логической формулы (*) показано на рис. 6.1.           .

Булевы функции. Здесь уместно вспомнить, ради чего был раз­веден этот формализм. Мы ввели логические формулы как средст­во точного описания сложных высказываний (логических формул),, истинность которых может быть установлена на основе истинно­сти исходных фактов (логических переменных) с использованием 13*
+++содержательных свойств логических связок (логических операций), виданных своими таблицами истинности.

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

 

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

Базис индукции: терминальным символам — переменным (логическим константам) заданы (присущи) некоторые значения истинности.

Шаги индукции: если нетерминальный символ n имеет един­ственную конституенту с приписанным ей значением истинности о, то а приписывается символу n;

если нетерминальный символ n является одночленом вида   и

символу n' приписано значение , том получает значение  (по таблице истинности);

если нетерминальный символ м является конструкцией вида   ,

 где р — одна из логических операций,   и