1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972)
Текст из файла
Московский государственный технический университетимени Н.Э. БауманаÌÃÒÓФакультет «Фундаментальные науки»Кафедра «Математическое моделирование»À.Í. ÊàíàòíèêîâÄÈÑÊÐÅÒÍÀßÌÀÒÅÌÀÒÈÊÀÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÊîíñïåêò ëåêöèéÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÄëÿ ñòóäåíòîâ ñïåöèàëüíîñòè<Ïðèêëàäíàÿ ìàòåìàòèêà>ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÔÍ-12Москва2006ÌÃÒÓÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓ1.
БУЛЕВЫ ФУНКЦИИАлгебра (R, {∨, ∧}), для которой (R, ∨) и (R, ∧) есть полурешетки, причем операции связаны тождествами поглощения a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a, называется решеткой. Бинарные операции называются решеточными (решеточное объединение и решеточное пересечение). Решеточные операции входят в структуру решетки симметрично. Поэтому любуюÌÃÒÓÔÍ-121ÔÍ-12inf {x, sup {x, y}} = x.ÌÃÒÓsup {x, inf {x, y}} = x,ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12Напомним, что по определению булева алгебра — это симметричное полукольцо, в которомвведена еще одна унарная операция — дополнение. Дополнение элемента x, обозначаемое x,удовлетворяет аксиомам x + x = 1, x x = 0.
Отметим, что эти два равенства для любогоx определяют элемент x однозначно, т.е. существование дополнения определяется свойствамидвух бинарных операций.Подробнее можно сказать, что булева алгебра — универсальная алгебра вида (L, {+, ·, }),удовлетворяющая условиям:а) каждая бинарная операция коммутативна, ассоциативна, идемпотентна и имеет нейтральный элемент;б) каждая бинарная операция дистрибутивна относительно другой;в) нейтральный элемент каждой бинарной операции является аннулирующим другой бинарной операции;г) дополнение связано с бинарными операциями аксиомами x + x = 1, x x = 0.Обе операции порождают два отношения порядка, являющиеся взаимно обратными. Так,отношение x 6 y, равносильное равенству x + y = y, также определяется равенством xy = x.Если в булевой алгебре B ввести операцию x ⊕ y = xy + xy, то получим алгебраическуюсистему (L, {⊕, ·}), которая является кольцом с единицей, в котором операция умножения идемпотентна (булевым кольцом).
Короче говоря, булева алгебра является булевым кольцом. Наоборот, в любом булевом кольце (L, {⊕, ·}) умножение коммутативно, а сложение удовлетворяетусловию x ⊕ x = 0. Положив x + y = x ⊕ y ⊕ xy, x = x + 1, получим алгебраическую систему(L, {+, ·, }), представляющую собой булеву алгебру.К понятию булевой алгебры можно подойти и с другой стороны. Коммутативная идемпотентная полугруппа называется полурешеткой. В полурешетке (как и в полукольце) можноввести отношение естественного порядка согласно правилу x 6 y ⇔ x + y = y. Наоборот, любоеупорядоченное множество, в котором любое двухэлементное множество имеет точную верхнююгрань, можно интерпретировать как полурешетку с операцией x + y = sup {x, y}.
Если в упорядоченном множестве каждое двухэлементное множество имеет и точную верхнюю, и точнуюнижнюю грани, то на это множестве можно ввести структуру полурешетки двумя способами:с операцией sup {x, y} и с операцией inf {x, y}. Первую структуру называют верхней полурешеткой, а вторую — нижней. Две решеточные операции связаны тождествамиÌÃÒÓÌÃÒÓБулева алгебра: симметричное полукольцо с унарной операцией дополнения x → x с аксиомами x + x = 1, x x = 0. Единственность дополнения. Булевы алгебры и булевы кольца.Булева алгебра как решетка. Решетка — алгебра (L, ∨, ∧) в которой операции (hешеточныеобъединение и пересечение) ассоциативны, коммутативны, идемпотентны и связаны тождествами поглощения a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a.
Всякое симметричное полукольцо являетсярешеткой, а дистрибутивная решетка (каждая операция дистрибутивна относительно другой)с нулем и единицей — симметричным полукольцом. Пример булевой алгебры — булев кубBn . Теорема: любая конечная булева алгебра изоморфна булеву кубу некоторой размерности.ÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓ1.1. Булевы алгебрыÌÃÒÓB = ({0, 1}, {+, ·,})1.2. Булевы функции*Диаграмма Хассе — изображение в виде неориентированного графа конечного упорядоченного множества.При этом ребрами соединяются вершины, связанные отношением доминирования, причем вершина, изображенная ниже, предшествует расположенной выше.ÔÍ-12Пусть задана булева алгебра (B, {∨, ∧, }).
Булева функция — это отображение f : B n →→ B, т.е. функция от n переменных, область изменения каждой из которых есть сама алгебра,причем значениями функции также являются элементы булевой алгебры. Мы остановимся наÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓБулева функция — отображение f : B n → B, где B — некоторая булева алгебра. Наибольшийинтерес — двухэлементная алгебра B. Табличный способ задания булевой функции. Примеры – функции одной и двух переменных. Вектор значений булевой функции. Аналитический способ.
Язык булевой алгебры: тройка (P, C, F ) (переменные, константы, функциональные символы). Интерпретация языка: сопоставление каждому функциональному символу арности n конкретной булевой функции от n аргументов. Синтаксическое дерево. Подформулыи значение формулы. Неоднозначность соответствия формул и функций. Эквивалентностьфункций и эквивалентность формул. Теорема о замене подформулы эквивалентной и теоремао замене переменной в эквивалентных формулах. Замыкание множества булевых функций.Замкнутые и полные множества функций.ÔÍ-12с операциями x+y = max {x, y}, xy = min{x, y}, x = x+1.
Обобщением этого примера являетсябулева алгебра Bn с покомпонентным выполнением операций алгебры B на кортежах. АлгебруBn называют n-й декартовой степенью B или n-мерным булевым кубом. Оказывается, чтолюбая конечная булева алгебра изоморфна некоторому булеву кубу. Попросту говоря, другихпримеров конечных алгебр, отличных от булева куба, нет.Другой важный пример булевой алгебры — алгебра SA = 2A , {∪, ∩, } , т.е. множествовсех подмножеств множества A с теоретико-множественными операциями объединения, пересечения и дополнения. Отметим, что все практически значимые примеры булевых алгебр можноинтерпретировать в рамках алгебры SA или какой-либо ее подалгебры.
Например, элементы булевой алгебры Bn (n-мерные булевы векторы) можно рассматривать как запись характеристической функции подмножества в множестве из n элементов. А тогда операции в Bn будут соответствовать теоретико-множественным операциям. Симметричное полукольцо ([a, b], {max, min})можно преобразовать в алгебру множеств, поставив в соответствие каждому x ∈ [a, b] отрезок[a, x].
Множество таких отрезков замкнуто относительно операций объединения и пересечения,т.е. образует подалгебру в 2[a,b] . Правда это полукольцо не является булевой алгеброй, так какв нем нельзя ввести операцию дополнения.ÌÃÒÓÔÍ-12из них можно назвать объединением, тогда втораябудет пересечением.
Структуру решеткиимеет любое упорядоченное множество, в котором для любого двухэлементного множества существует точная верхняя и точная нижняя грани. В этом случае решеточными операциямибудут a ∨ b = sup {a, b} и a ∧ b = inf {a, b}.Структуру решетки имеет любое симметричное полукольцо. Ре1шетка в общем случае может и не быть симметричным полукольцом.Например, пентагон — упорядоченное множество {0, a, b, c, 1} сcотношением порядка, заданным диаграммой Хассе* на рис.
1.1, —является решеткой, но в этой решетке операции не являются дисbтрибутивными друг относительно друга, как должно быть в симмеaтричном полукольце. Однако всякая дистрибутивная решетка (т.е. решетка, в которой каждая операция дистрибутивна относительно дру0гой) с нулем и единицей (нейтральными элементами объединения иРис. 1.1пересечения) является симметричным полукольцом.Простейший пример булевой алгебры — двухэлементная булева алгебраÌÃÒÓÌÃÒÓÌÃÒÓ2ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓx01f1 (x) f2 (x) f3 (x) f4 (x)00111010Таблица 1.3x1 , x200011011f1 (x) f2 (x) f3 (x) f4 (x) f5 (x) f6 (x) f7 (x)0001111101101010100101101100Инфиксная форма записи и представление штриха Шеффера и стрелки Пирсона с помощьюопераций булевой алгебры указывает еще на один способ представления булевых функций —аналитический.
Вообще говоря, любая алгебраическая система содержательна, если для нееудается создать такие формы записи операций и их последовательностей, для которых возникают многообразные способы преобразования выражений. Речь идет о понятии формула“.”ÔÍ-12x1 ↓ x2 = x1 ∨ x2 .ÌÃÒÓx1 | x2 = x1 ∧ x2 ,ÔÍ-12Отметим, что булева функция n переменных представляет собой n-арную операцию на булевой алгебре B. В частности, функции двух переменных — это бинарные операции, для которыхобычно используют инфиксную форму записи.
Так, для функций приведенных в табл. 1.3, используют следующие названия и символы операций:f1 (x1 , x2 ) = x1 ∨ x2 = x1 + x2 — дизъюнкция;f2 (x1 , x2 ) = x1 ∧ x2 = x1 · x2 — конъюнкция;f3 (x1 , x2 ) = x1 ⊕ x2 — сложение по модулю 2;f4 (x1 , x2 ) = x1 → x2 — импликация;f5 (x1 , x2 ) = x1 ∼ x2 — эквивалентность;f6 (x1 , x2 ) = x1 | x2 — штрих Шеффера ( не и“);”f7 (x1 , x2 ) = x1 ↓ x2 — стрелка Пирсона ( не или“).”Функции f1 и f2 — базовые операции булевой алгебры B, т.е. сложение и умножение (или,по-другому, решеточное объединение и пересечение), но в теории булевых функции традиционно предпочитают названия, указывающие на связь с математической логикой. Сложениепо модулю 2 — альтернатива дизъюнкции, превращающая полукольцо B в поле Z2 .
ШтрихШеффера и стрелка Пирсона — это отрицания соответственно конъюнкции и дизъюнкции, т.е.ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Таблица 1.2ÌÃÒÓÌÃÒÓпростейшем случае, имеющем наибольший интерес, когда B — это двухэлементная алгебраB. В этом случае каждый аргумент функции принимает два возможных значения 0 и 1 исама функция принимает лишь два тех же значения. Подобная функция представляет собойотображение f : Bn → B. Комбинируя такие функции, можно получить любое отображениевида F : Bn → Bm , а в конечном счете булевы функции нескольких переменных для любойконечной булевой алгебры.Нетрудно подсчитать количество возможных булевых функций вида f : Bn → B: это колиnчество равно 22 (по формуле Y X , где X количество элементов области определения, а Y —количество элементов области значений).Таблица 1.1Поскольку и область определения, и областьзначений конечны, булевы функции удобно задаx1 , x2 , .
. . , xnf (x1 , x2 , . . . , xn )вать с помощью таблиц. Элементы области опре0, 0, . . . , 0f (0, 0, . . . , 0)деления — n-мерные векторы, которые можно рас. . . . . . . . . .. . . . . . . . . . .сматривать как двоичные записи целых неотрицаαk1 , αk2 , . . . , αkn f (αk1 , αk2 , . . . , αkn )тельных чисел от 0 до 2n − 1. Таблица, определя. .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
