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