1 - Булевы функции. Булевы алгебры. Булевы функции. ДНФ и КНФ. Критерий Поста. Минимизация ДНФ (1059972), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. . . . . . . .. . . . . . . . . . .ющая булеву функцию, может выглядеть следую1, 1, . . . , 1f (1, 1, . . . , 1)щим образом (табл. 1.1).В качестве примера приведем таблицы булевых функций одного переменного (табл. 1.2) исеми наиболее важных функций двух переменных (табл. 1.3).ÌÃÒÓÔÍ-12ÌÃÒÓ3ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121.

БУЛЕВЫ ФУНКЦИИÌÃÒÓСитуацию здесь можно пояснить следующим образом. При записи математических формул используютчисловые константы, которые фигурируют в десятичной форме записи. Такая запись включает десять цифрзнак числа и десятичную запятую. правильных записей чисел существует счетное число. Но рассматриваясложные конструкции формул, можно каждую такую запись считать самостоятельным символом, не раскрываяспособ формирования записи.ÔÍ-12*ÌÃÒÓПервый пункт определения — базис индукции. Второй (и последующие, если они есть)определяет правила построения новых формул из уже построенных. Это шаг индукции.В данном случае под алфавитом следует понимать объединение P ∪ C ∪ F , к которомудобавлены еще три служебных символа: две круглые скобки и запятая. Но заметим, что притаком подходе нарушается требование конечности алфавита.

Мы сознательно идем на такоенарушение, чтобы не усложнять язык формул. Язык булевой алгебры — это множествовсех правильно составленных формул.Хотя мы выделили константы, т.е. символы, обозначающие объекты рассматриваемой алгебраической системы, в самостоятельный класс, часто удобно рассматривать их как специальный вид функциональных символов арности 0. Таким символам соответствуют постоянныебулевы функции.Индуктивное определение формулы позволяет корректно составлять сами формулы, как последовательности символов, но не придает им какого-либо смысла. Чтобы наполнить формулысмыслом, необходимо каждому функциональному символу сопоставить конкретную операциюÔÍ-121) элементы множества P ∪ C — формулы;2) если X1 , X2 , .

. . , Xn — формулы и f ∈ F — функциональный символ арности n, тоf (X1 , X2 , . . . , Xn ) — формулаÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓФормула интуитивно понимается как запись с помощью определенного языка некоторой последовательности действий над объектами алгебраической системы.В самом общем смысле под языком понимают следующее.

Рассмотрим некоторое непустоеконечное множество V , элементы которого будем называть символами. Произвольные последовательности символов называются словами или цепочками. Слова могут быть любойдлины. Вводится специальное слово нулевой длины. Множество всех слов обозначим V ∗ . Этомножество можно представить как объединение всех декартовых степеней множества V (нулевой, содержащей слово нулевой длины, первой со словами длины 1, второй со словами длины 2и т.д.). Язык — это некоторое подмножество в V ∗ , т.е.

некоторый фиксированный набор слов,составленных с помощью элементов множества V , которое называют алфавитом языка.Конкретный язык формируется правилами, по которым из всех слов, составленных с помощью данного алфавита, выбираются правильные“ или допустимые слова. В нашем случае”словами должны быть правильно записанные формулы булевой алгебры, а символами — символы переменных, знаков операций и элементов алгебры. Язык формул можно построить врамках данного выше понятия формального языка. Однако, упрощая изложение, мы снимемограничение конечности алфавита языка* , полагая, что алфавит может быть счетным множеством. Строго формальный математический язык можно ввести следующим образом.Пусть дана тройка объектов (P, C, F ), где P — счетное множество, элементы которого мыбудем называть булевыми переменными; C — счетное множество символов, используемыхдля обозначения элементов алгебраической системы (в данном случае двух элементов 0 и 1алгебры B), которые мы будем называть константами; F — счетное множество функциональных символов, каждый из которых имеет натуральную характеристику — арность.Понятие формулы в рассматриваемом языке вводится индуктивно, т.е.

указываются конкретные способы построения правильных формул на основе уже построенных формул. Базисиндукции — изначальный набор элементарных формул, под которыми мы будем пониматьэлементы множества P ∪ C. Шаг индукции описывает, как из уже построенных формул получаются новые: если X1 , X2 , . . . , Xn — формулы и f ∈ F — функциональный символ арностиn, то f (X1 , X2 , . . . , Xn ) — формула. Кратко сказанное можно сформулировать так:ÌÃÒÓÔÍ-12ÌÃÒÓ4ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÌÃÒÓ5ÌÃÒÓОсновная задача в связи с аналитическим способом задания булевых функций — описание класса функций, представимых формулами. В дальнейшем мы для упрощения изложениябудем отождествлять множество функциональных символов языка с соответствующим множеством булевых функций.

Можно считать, что каждой булевой функции соответствует свойуникальный символ и F состоит как раз из таких символов, так что, задав F , мы тем самымзадаем и интерпретацию формул.ÔÍ-12ÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓПример 1.1. Рассмотрим формулу f1 (f2 (x1 , x2 ), f3 (x2 ), f4 (x1 , f2 (x3 ), x4 )). Эта формула получена с помощью функционального символа f1 арности 3. Подформулами глубины 1 являютсяf2 (x2 ), f3 (x2 ) и f4 (x1 , f2 (x3 ), x4 ). Первая из них имеет подформулу — переменную x2 , втораяимеет также одну подформулу — переменную x2 , а третья — уже три подформулы: первая итретья — переменные x1 и x4 , вторая подформула — сложная подформула f2 (x3 ). В результате получаем дерево синтаксического анализа, представленное на рис.

1.2. Высоту дерева (вданном случае 3) называют сложностью формулы.ÌÃÒÓсоответствующей арности (конкретную булеву функции с соответствующим количеством аргументов). Другими словами, необходимо задать отображение множества F в множество всехбулевых функций, при котором арность функционального символа совпадает с арностью операции. Кроме того, необходимо фиксировать смысл символов, предназначенных для обозначенияконстант, т.е.

задать отображение множества C в алгебру B. Два указанных отображениясоставляют интерпретацию языка.Следует учесть еще одно обстоятельство. Общепринятым является запись бинарных операций не в виде f (x1 , x2 ), а в виде x1 f x2 (как правило, со специальным символом операции).Поэтому в наш язык следует ввести символы инфиксных операций, а в качестве шага индукцииввести дополнительное правило:3) если X1 и X2 — формулы, то и слова (X1 + X2 ), (X1 · X2 ), (X1 ⊕ X2 ), (X1 → X2 ), (X1 ∼ X2 ),(X1 | X2 ), (X1 ↓ X2 ) являются формулами.При использовании инфиксной формы записи бинарных операций в формулах оказываетсябольшое количество пар скобок, что затрудняет восприятие таких формул.

Скобки нужны длятого, чтобы однозначно определить последовательность шагов, которые приводят от элементарных формул к конечной формуле. Чтобы сократить количество скобок и сделать формулыболее читаемыми, используют правило приоритетов, согласно которому каждой бинарной операции с инфиксной формой записи присваивается приоритет — некоторое натуральное число.Сперва выполняются операции с большим приоритетом, затем с меньшим. Среди операцийс одинаковым приоритетом в первую очередь выполняется та, знак которой находится левее.Мы будем использовать инфиксную форму на практике, как более привычную и удобную, но втеоретических рассуждениях с целью упрощения ограничимся лишь префиксной формой записиопераций.Рассматривая различные множества F функциональных символов и различные их интерпретации, мы можем строить различные схемы построения формул, которые различаются наборомбазовых функций.

Например, в качестве базовых могут рассматриваться три базовые операции булевой алгебры: сложение, умножение и отрицание, но могут быть и другие варианты(например, сложение по модулю 2 и умножение — базовые операции в Z2 ).Любая корректная формула либо элементарная, либо получена в результате шага индукции, т.е. с помощью функционального символа f и некоторого набора формул X1 , . . . , Xn .Каждая из формул Xi в свою очередь либо элементарная формула, либо получена с помощьюсвоего функционального символа fi и некоторого набора формул XI1 , . .

. , Xini и т.д. Двигаясьот конечной формулы, мы за конечное число шагов придем к элементарным формулам — переменным и константам. Представленный анализ формулы называется синтаксическим. Егорезультаты можно представить в виде ориентированного дерева. Корень дерева — сам формула, вершины глубины 1, формулы Xi и т.д. Каждому листу дерева соответствует переменнаяили константа.

Вершинам, не являющимся корнем соответствуют формулы, которые входяткак составная часть в анализируемую формулу. Они называются подформулами.ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-121. БУЛЕВЫ ФУНКЦИИÌÃÒÓÌÃÒÓ0f1(f2(x1,x2),f3(x2),f4(x1,f2(x3),x4))1f2(x1,x2)f3(x2)f4(x1,f2(x3),x4)2x1x2x1x2ÔÍ-12Использование квадратных скобок подчеркивает, что это не обозначение функции. Здесь имеется в видуформула, обозначенная как Φ, все переменные которой входят в указанный список переменных.ÌÃÒÓ*ÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12Один из способов получения новых формул — замена одной из подформул другой.

Такоепреобразование называется подстановкой. Замене может подлежать как сложная формула,так и любая элементарная.В формулу, как правило, входят переменные (булевы переменные). Но есть формулы, вкоторых элементарные составляющие — все константы. Такие формулы имеют определенноезначение, соответствующее конкретному объекту алгебраической системы (т.е. в нашем случае0 и 1). Если в формулу входят переменные, то ее значение не определено. Однако если в формулезаменить каждую переменную константой (т.е. дать переменной конкретное значение), получимновую формулу, имеющую значение. Таким образом, каждому набору значений переменных,входящих в формулу, соответствует конкретное значение формулы.Это обстоятельство позволяет рассматривать формулу как форму записи функции. Однаконадо иметь в виду, что с помощью одной и той же формулы можно задавать различные функции.Например, формула x − t определяет функции f (x, t = x − t и f (t, x) = x − t, а также, например,функцию f (x, y, t) = x − t.Из этого примера можно сделать вывод: чтобы с помощью формулы задать функцию, необходимо установить соответствие между аргументами функции и переменными, входящимив формулу.

Характеристики

Список файлов лекций