Булева алгебра (стр. 4 )

Количество конъюнкций в СДНФ всегда должно равняться количеству единичек в векторе значений функции (в данном примере их 6).

Теорема: Любая булева функция, зависящая от заданного числа аргумента может быть представлена в виде СДНФ, причём единственным образом.

Совершенная Конъюнктивная Нормальная Форма (СКНФ)

СКНФ это еще один способ представления булевых функций.

Совершенной конъюнктивной нормальной формой (СКНФ) данной формулы алгебры высказываний называется такая ее КНФ, которая удовлетворяет следующим свойствам:

1.  КНФ не содержит двух одинаковых дизьюнкций.

2.  Ни одна дизъюнкция не содержит одновременно двух одинаковых переменных.

3.  Ни одна кдизъюнкция не содержит одновременно некоторую переменную и ее отрицание.

4.  Каждая дизъюнкция СКНФ содержит либо переменную , либо ее отрицание для всех переменных, входящих в формулу.

СКНФ для любой функции может быть получена также как и СДНФ с помощь таблицы истинности. Все действия которые мы совершали для построена СДНФ нам надо выполнить наоборот.

Для построения СКНФ нас будут интересовать наборы на которых функция принимает значение равное 0.

Далее, если переменной соответствует 0, то переменная берется без инверсии, если 1 то с инверсией. Из переменных строим не конъюнкция, а дизъюнкции.

Полученные дизъюнкции соединяем знаком конъюнкции.

Все это будет легче понять па примере. Возьмем первую функцию для которой мы строили СДНФ: . Таблица истинности для нее уже построена.

xyz	f
000 001 010 011 100 101 110 111	0 1 0 1 0 0 1 1	* * * *

В результате СКНФ будет выглядеть так:

Теорема: Любая булева функция зависящая от заданного числа аргументов может быть представлена в виде СКНФ, причём единственным образом.

Упражнение №1:

Постройте СДНФ и СКНФ для функций:

f(0,1,0,0,1,1,0,1);

f(1,1,0,1,0,1,1,0);

f(0,1,0,1,1,0,1,0);

f(1,0,1,0,0,0,0,1);

f(0,1,1,1,0,1,0,0);

f(1,1,0,0,0,1,0,1).

Упражнение №2:

Постройте СДНФ и СКНФ.

f(x, y)=(0,1,0,1);

f(x, y)=(1,0,0,1);

f(x, y,z, u)=(1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1);

f(x, y,z, u)=(1,0,1,1,0,0,1,0,1,0,0,0,0,1,0,1).

Упражнение №3:

Постройте СДНФ и СКНФ. Для функций а), b), c), d), e) постройте СДНФ.

f(x, y)=xy; g)f(x, y,z, u)=xyu

f(x, y)=; h)f(x, y,z, u)=xz.

f(x, y,z)=xy; f(x, y,z)=xy;

f(x, y,z)=xzx; f(x, y,z)=x;

9.  Минимизация булёвых функций с помощью карты Вейча

Этот метод используется для функций с малым числом переменных.

Две соседние ячейки отличаются значением только одной переменной. На рисунке 2. представлены карты Вейча для функций, зависящих от двух, трех и четырех переменных.

Рис.2 Карты Вейча

Все ячейки отмеченные скобкой хi (по строке и столбцу), представляют наборы с хi = 1, а в неотмеченных строках и столбцах ячейки соответствуют наборам с хi =0.

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

Незаполненные ячейки соответствуют нулям функции. Для нанесения функции на карту Вейча ее необходимо представить в виде СДНФ.

Пример 1. Построим карту Вейча для функции

ƒ(x1,x2,x3,) =123 12 x3 1 x2 3x1 x2 x3.

Пример 2. Построим карту Вейча для функции

ƒ(x1,x2)= x1 x2

Представим ее в виде СДНФ: ƒ(x1,x2) =12 x12

С помощью карты Вейча можно находить простые импликанты. Для этого будем строить покрытия ячеек карты по следующим правилам.

1. Две ячейки, содержащие единицы “склеиваются”, если они являются соседними, то есть расположены рядом (но не на диагонали). При этом считается, что ячейки на противоположных концах строки или столбца являются соседними, как будто карта расположена на торе (Рис. 4.5.2.).

2. Четыре ячейки, содержащие единицы “склеиваются”, если они расположены в одной строке или в столбце, или квадратом (Рис. 4.5.3.).

3. Восемь ячеек, содержащих единицы “склеиваются” если все они лежат в зоне, относящейся к какой-либо переменной или ее инверсии (Рис. 4.5.4.).

Соединение соседних ячеек, соответствует операции склеивания конъюнкций. В результирующую конъюнкцию, входят переменные, в зоне которых полностью лежат объединенные ячейки. Рассмотрим рисунок 4.5.2. В левом верхнем углу карты объединены две ячейки, соответствующие конъюнкциям x1x234 и x1x2 x34 в результате склеивания этих конъюнкций по переменной x3 получается конъюнкция x1x24. На этой же карте в левом нижнем углу склеивание ячеек определяет конъюнкцию x123, ячейки, помеченные единицами в правом верхнем и правом нижнем углах определяют конъюнкцию. На карте Вейча на рисунке 4.5.3. представлены конъюнкции x1x2 (ячейки, образующие квадрат), x13 и14. На карте Вейча на рисунке 4.5.4. представлены конъюнкции 3(пунктиром) и 4.

Для построения минимальной ДНФ по карте Вейча следуют двум правилам.

1. Выбирают интервалы наибольшего размера, содержащие ячейки, которые не могут быть ни в каком другом интервале.

2. Для оставшихся ячеек выбирают интервал наибольшего размера.

Пример Найдем минимальную ДНФ для функции

ƒ(x1,x2,x3,x4) = (0,3,4,6,7,9,14,15).

Выпишем двоичные номера всех соответствующих наборов: 0000, 0011, 0100, 0110, 0111, 1001, 1110, 1111.

Построим карту Вейча.

Простые импликанты образуют минимальную ДНФ, которая имеет вид:

x123 x4 x2x31 x3 x4134.

10.Функциональная полнота системы булевых функций

10.1. Полные системы

В типичной современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевой функции. Любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Вопрос состоит в том, существуют ли иные системы булевых функций, обладающих тем свойств, что с их помощью можно выразить все другие функции.

10.2. Понятие функциональной полноты

Рассмотрим множество булевых функций , назовем его системой функций.

Определение 1. Множество является полной системой, если любую булеву функцию можно представить формулой над М.

Другими словами, система будет полной, если любую функцию можно представить суперпозицией функций,,…,.

Пример из обычной математики. Функцию возведения в степень можно представить через функцию умножения , проделав операцию умножения k раз. Аналогично булевы функции представимы через другие булевы функции.

Примеры:

{,⌉} конъюнкция, дизъюнкция и инверсия образуют полную систему;

{,⌉} конъюнкция и инверсия также образуют полную систему;

{/}| полная система может содержать всего одну функцию, например Штрих Шеффера.

Еще одно определение полной системы.

10.3. Замкнутые классы булевых функций

Замыкание

Определение. Замыканием множества М называется множество, обозначаемое [M], которое состоит из функций множества М и функций, которые могут быть получены из функций множества М путем отождествления переменных и суперпозиций (конечным их числом)

Изобразим множество и его замыкание на диаграмме Вена (рис.1). Как видно из диаграммы само множество М является подмножеством замыкания [М]. Функции из замыкания представимы формулами составленными из

функций множества М. Например, функция представлена формулой составленной из,,, где , , .

 

рис.2

Определение. Множество функций М называется замкнутым, если его замыкание совпадает с самим множеством [M]=M.

Определение 2. Система М называется полной, если её замыкание есть множество всех булевых функций ([М]=P2).

Например замкнуто и неполно, P2 замкнуто и полно, незамкнуто и полно.

Другими словами, если функция представима формулой над множеством М, где М - замкнутый класс, то эта функция также принадлежит классу М.

Свойства замыкания

1. Обозначим Р2 множество всех булевых функций. Замыкание множества всех булевых функций есть само множество Р2. [P2]=P2.

2. Замыкание замыкания М равно замыканию множества М. [[M]]=[M]

3. Если N⊂M (N подмножество множества M), то [N]⊂[M].

4. [M]⋃[N]⊂[M⋃N].

Для полной системы диаграмма Венна будет выглядеть следующим образом (рис.3). Как видите [P2]=[M].

 

рис.3

10.4. Пять замкнутых классов.

1. Класс функций, сохраняющих нуль (То)

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

Множество всех функций сохраняющих нуль образуют замкнутый класс.

Пример.

Функция сохраняет нуль, так как она равна нулю наборе 00 ()=0. Функция х/у не сохраняет нуль, поскольку на нулевом наборе она принимает единичное значение.

Функция, представленная дизъюнкцией конъюнкций (ДНФ) или СДНФ, сохраняет нуль, если в неё не входит конъюнкция, в которой все переменные взяты со знаком инверсии.

Например,

сохраняет 0, а функция не сохраняет 0.

Функция сохраняет нуль, так как .

Класс замкнут, это означает, что любая функция может быть

представлена формулой над множеством функций сохраняющих

нуль будет также сохранять нуль, то есть будет принадлежать классу.

2. Класс функций, сохраняющих единицу ()

Определение. Булева функция сохраняет единицу, если на единичном наборе она принимает значение единицы (единичный набор состоит из п единиц, где п - число аргументов булевой функции).

Множество всех функций сохраняющих единицу образуют замкнутый класс .

Пример, функция не сохраняет единицу, так как она равна нулю на наборе 11 ()=0,

функция х\/у сохраняет единицу, поскольку на единичном наборе она принимает единичное значение 1.

Проверим функцию .

, отсюда следует что .

Функция, представленная дизъюнкцией конъюнкций или СДНФ, сохраняет единицу, если в нее входит конъюнкция в которой все переменные взяты без знака инверсии.

Например, сохраняет 1, так как есть конъюнкция ху, а функция не сохраняет 1.

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

Упражнение №1: