XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 64
Текст из файла (страница 64)
Определение 6.3 равносильно следующему (на „языке суперпоэицнй"): множество Р функций замкнуто, если каждая суперпозиция над Р есть функция из Р, т.е. [Р] = Р, и полно, если всякая булеза функция есть некоторал суперпозиция над Р, т.е. [Р] =Рэ. Замечание 6.6. Можно заметить, что определение формулы и суперпозиции над заданным множеством булевых функций похоже на определение й-замыкания множества в алгебрах (см.
4.2). Эти определения, равно как и основанные на них определения замкнутости и полноты множеств булевых функций, могут быть переведены полностью на алгебраический язык. Тогда замкнутое множество булевых функций, согласно определению 6.3, окажется не чем иным, как эамкиушмм подмнохееством некоторой алгебры булевых функций, а полное множество булевых функцнй — свсщемой образующих этой алгебры. Однако при попытке чисто алгебраической интерпретации определения 6.3 возникают некоторые технические трудности, обсуждение которых выходит за рамки этой книги'.
'См., папрпмер: Мапьросоо В.Л., Сюпецецко В.А. 6. БУЛЕВЫ ФУНКДИИ 402 Пример 6.8. Для каждой нз определенных в 6.1 функций от двух переменных мы можем записать следующие формулы над стандартным базисом: Х1 Щ Х2 = Х1 ' Х2 Ч Х1Х2! Х1 ~ Х2 = Х1 Ч Х2~ х1 х2=(х1Чхг) (х2Чх1), ХЦХ2 = Х1 Х2~ Х1.~, Х2 = Х1 ТХ22 Если мы пополним стандартный базис функцией -1 (импликацией), то формула для эквивалентности примет вид Х1 Х2 = (Х1 -+ Х2) ' (Х2 -+ Х1).
ф Тот факт, что одна и та же функция (в данном случае эквивалентность) может быть представлена по крайней мере двумя разными формулами над одним и тем же множеством, а именно над (Ч...-+), показывает, что соответствие между формулами над фиксированным множеством и представляемыми ими функциями не является взаимно однозначным. Эта ситуация до некоторой степени аналогична разложению по базису векторое конечномерного линейного пространства Щ.
Формула, представляющая некоторую булеву функцию, выражает „разложение" этой функции по фиксированному „функциональному базису". Одна и та же функция может иметь несколько таких разложений. В отличие от линейной алгебры в этом случае возникает ситуация, когда возможны различные разложения заданной функции по одному и тому же базису. Например, формулы (х Ч р) и И Р над стандартным базисом представляют одну и ту же функцию. Назовем эквивалентными формулы, которые представляют равные функции.
Эквивалентным (или пгождеспгвенным) преобразованием Формулы Ф называют переход (по определенным правилам) к любой формуле Ф, эквивалентной б.4. Формулы и суперпоэюппс формуле Ф. Необходимо сделать несколько замечаний относительно правил, согласно которым осуществляются эквивалентные преобразования формул.
Введем понятие тождества. Тождестволе (над множеством Р С 'Рг) называют выражение где формулы Ф и Ф вЂ” эквивалентные формулы над Р. Формула Ф называется при этом левой, а формула Ф вЂ” правой часгпью пзоасдесгпва (6.7). Левая и правая части тождества представляют равные булевы функции. Поэтому пересечение множеств переменных айаг(Ф) = (хы ...,хп) и Уаг(Ф) = (уы ..., ую) должно содержать все существенные переменные функций у(хы...,хо) и у(уы...,Ь~), представляемых формулами Ф и Ф соответственно. В частности, если зто пересечение пусто, то обе функции равны некоторой константе. Пример 6.9.
В тождествах хЧх = уЧу, хЧх = 1 пересечение множеств переменных в левых и правых частях пусто, причем во втором тождестве правая часть вообще не содержит переменных. В тождестве (х Чу) (з ЧУ) = хЧ уЧ и. и указанное пересечение равно (х, у). Все записанные в примере 6.8 выражения являются тождествами над множеством (Ч... 9, ~,, ~,Ц, причем во всех этих тождествах множества переменных в левой и правой частях тождества совпадают. Такого же рода тождества— аксиомы булевой алгебры' (кроме тождеств х Ч х = 1 и х Л х = 0) и вытекающие иэ них тождества (подобные, например, закопав де Моргана). Ф Беэ доказательства сформулируем следующие правила тождественных преобразований.
'Поскольку все переменные, фигурируюппее в этих тождествах, есть булевы переменные, то речь здесь идет об аксиомах булевой алгебры применительно к частному случаю — двулэлементной булевой алгебре В. 404 б. БУЛЕВЫ ФУНКЦИИ Теорема 6.1. 1. Если в тождестве (6.7) некоторые переменные заменить произвольными формулами (над множеством г'), то тождество сохранится, т.е. полученные в результате такой замены новые формулы останутся эквивалентными.
2. Если в формуле Ф произвольную ее подформулу заменить любой эквивалентной ей, то получится формула, эквивалентная формуле Ф. Чтобы использовать сформулированные в теореме 6.1 правила, нужно фиксировать какую-то систему исходных тождеств. Тогда возникает вопрос можно ли утверждать, что при надлежащем выборе исходных тождеств с помощью пра вил 1 и 2, сформулированных в теореме 6.1, можно из формулы Ф получить эквивалентную ей формулу Ф, каковы бы ни были зти формулы, или, говоря неформально, любые ли две эквивалентные формулы над заданным множеством Г можно „трансформировать" друг в друга, используя фиксированную систему основных тождеств над Р и правила, сформулированные в теореме 6.1? Рассмотрение этого вопроса выходит за рамки учебника.
Ответ на него зависит от того, какое множество булевых функций Р и какая система исходных тождеств над Г выбраны. Отметим, что для стандартного базиса ответ на вопрос положителен, причем в качестве исходных тождеств используются аксиомы булевой алгебры. В свете изложенного может быть поставлена задача поиска наиболее простой (в определенном смысле) формулы, среди всех эквивалентных между собой формул, представляющих данную булеву функцию. Решение этой задачи для некоторого класса формул над стандартным базисом будет рассмотрено в 6.6. Понятие формулы позволяет также взглянуть по-новому на логическую интерпретацию булевой функции.
В силу установленного в 6.2 взаимно однозначного соответствия между логическими связками Ч, Л,, =ь, с~ и булевыми функциями Ч... -+, ° любому сложному высказыванию, составленно- В.о. Дизъюннтнвные и нонъюннтивные норывеьные формы 405 му из некоторых „простых" высказываний с использованием указанных вьппе логических связок, однозначно сопоставляется формула над множеством Ь = (Ч, Л,, -т, ° ), т.е. каждому простому высказыванию сопоставляется булево переменное (так что разным высказываниям сопоставляются и разные переменные), а связки Ч, Л,, =~, сФ заменяются соответствующими функциями из множества Ь.
Тогда, например, высказыванию (Р ~ Я) Л Я =~ Р) (читается: „если Р, то Я, и если Я, то Р") будет сопоставлена формула (х -т у).(у -+х). Таким образом, с логической точки зрения формула над множеством Ь есть высказывание. Поскольку мы имеем возможность вычислять значения формул и проводить их эквивалентные преобразования (используя, в частности, аксиомы булевой алгебры), мы получаем алгебраический аппарат для упрощения сложных высказываний (путем эквивалентных преобразований) и вычисления их истинностных значений.
Но тогда возникают вопросы: как практически построить для любой наперед заданной булевой функции представляющую ее формулу над фиксированным множеством базисных функций Р? Каковы условия пыноты множества Р? Далее (см. 6.5 и 6.6) мы рассмотрим вопрос о представлении любой булевой функции над стандартным базисом и вопрос о поиске минимальной (в уточняемом ниже смысле), наиболее простой формулы над стандартным базисом, представляющей данную функцию. 6.5. Дизъюнктивные и конъюнктивные нормальные формы Любая формула вида х или х над стпандартпнмм базисом, где х — произвольное переменное, называется лптперамом.
Таким образом, литерал есть обозначение либо самого переменного х, либо его отрицания. Часто используют такое обозначение: для о' Е (О, 1) пишут х, понимая под этим само переменное х, если 406 б. БУЛЕБЫ ФУНКЦИИ а = 1, и отрицание х, если о = О, т.е. (х, а=1; х 1х, о=О. (6.8) Подставляя в (6.8) 0 и 1 вместо х, получаем )О, а=1; 11, а=О, Часто используют также обозначение х, понимая под этим любой нз двух литералов — х нли х.
Формула вида х1хз... х,„(соответственно вида х1 Ч хз Ч... ... Ч х,„), где все фигурирующие в ней переменные попарно различны, называется элеменгпарной конъюнкиией (соответственно элеменпырной дизъюнкиией). Определение 6.4. Дизъюнктпивная нормальная форма (ДНФ) от переменных хм ..., х„— это формула вида К1 Ч... Ч К~в, где К;, 1 = 1, п1, — элементарная конъюнкция, содержащая некоторые ю литералов хм ..., х„.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
