FINISH (675729), страница 3

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

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

y=(x₁Úx₂Úx₃) (x₁Úx₂Úx₃) (x₁Úx₂Úx₃) (x₁Úx₂Úx₃) (*)

Преобразование произвольной аналитической формы Булевой функции в нормальную

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

Пример:

_ _ _ _ _ _

y=f⁴(x)=(x₁x₂Úx₂x₃)(x₁|x₄)=(x₁x₂Úx₂x₃)(x₁x₄)=(x₁x₂Úx₂x₃)(x₁Úx₄)=

_ _ _ _ _ _ _ _ _ _

=x₁x₂Úx₁x₂x₄Úx₁x₂x₃Úx₂x₃x₄₌x₁x₂Úx₁x₂x₃Úx₂x₃x₄=x₁(x₂Úx₂x₃)Úx₂x₃x₄=

_ _ _ _

=x₁(x₂Úx₃) Úx₂x₃x₄=x₁x₂Úx₁x₃Úx₂x₃x₄ (КДНФ)

Замечания:

1) В общем случае любая Булева функция может иметь несколько КДНФ, отличающихся либо количеством термов, либо количеством букв в этих термах.

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

3) По сравнению со схемой, построенной по ДНФ, схема, построенная по скобочной форме (*), является более предпочтительной т.к. при одном и том же числе логических элементов (И, ИЛИ) содержат меньшее число входов (9 вместо 10).

Задача преобразования нормальной формы Булевой функции в скобочной форме называют задачей фактеризации.

4) Сущность конструктивного подхода при получении ДНФ состоит в следуюшем:

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

б) снятие отрицаний над выражениями с применением законов двойственности

в) раскрытие скобок с применением дистрибутивного закона

г) упрощения выражения с применением закона поглощения

Приведение произвольных нормальных форм Булевой функции к каноническим

Для приведения произвольной ДНФ к КНФ необходимо использовать правило дизъюнктивного развертывания применительно к каждому из неполных конъюнктивных термов.

_ _

P=P(x_iÚx_i)=Px_iÚPx_i, где P-неполный конъюнктивный терм (ранг этого терма

меньше n), а x_i - недостающий в терме аргумент.

Пример:

_ _ _ _ _ _ _ _ _ _

y=x₁Úx₂x₃(ДНФ)=x₁(x₂Úx₂)(x₃Úx₃) Úx₂x₃(x₁Úx₁)=x₁x₂x₃Ú x₁x₂x₃Ú

_ _ _ _ _ _ _ _ _

Úx₁x₂x₃Úx₁x₂x₃Ú x₁x₂x₃Ú x₁x₂x₃ (КДНФ)

Замечание:

После раскрытия скобок могут получиться одинаковые термы, из которых нужно оставить только один.

y= (0,1,2,3,5)=f³

Преобразование КНФ к ККНФ реализуется путем применения правила конъюнктивного развертывания к каждому неполному дизъюнктивному терму.

_ _

P=PÚx_ix_i=(PÚx_i)(PÚx_i)

_ _ _ _ _ _ _ _ _ _

y=x₁Úx₂x₃(ДНФ)=(x₁Úx₂)(x₁Úx₃)(КНФ)=(x₁Úx₂Úx₃x₃)(x₁Úx₃Úx₂x₂)=

_ _ _ _ _ _ _ _

=(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(x₁Úx₂Úx₃)(ККНФ)

y= (4,6,7)

Минимизация булевых функций на картах Карно(см. Практику).

Метод Квайна-МакКласски базируется на кубическом представлении булевых функций.

Кубическое представление булевых функций.

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

Существенные вершины образуют так называемые ноль-кубы (0-кубы). Между 0-кубами существует отношение соседства и определена операция склеивания. Два 0-куба называются соседними если они отличаются только по одной координате.

Пример : n=4 0101

0001 - два соседних 0-куба

результат склеивания : 0x01 (*)

Склеивание 2-х соседних 0-кубов дает в результате 1-куб. Координата, отмечаемая символом х, называется свободной (независимой, несвязанной), а остальные (числовые) координаты называются зависимыми (связанными). Аналогичное отношение соседства существует между 1-кубами, в результате склеивания которых получается 2-куб.

0х01

0х11 - 0хх1 (**)

В продолжении аналогии два r-куба называются соседними если они отличаются только по одной (естественно зависимой) координате. r-куб содержит r независимых и n-r зависимых координат. В результате склеивания 2-х соседних r-кубов образуется (r+1)-куб содержащий r+1 независимую координату.

Операция склеивания над кубами соответствует применению закона склеивания к конъюнктивным термам, отождествляемым с этими кубами.

Пример : для склеивания (*)

_ _ _ _ _ _ _

х₁х₂х₃х₄Ú х₁х₂х₃х₄= х₁х₃х₄

(0101) (0001) (0х01)

_ _ _ _

для (**) х₁х₃х₄Ú х₁х₃х₄= х₁х₄

(0х01) (0х11) (0хх1)

Определения.

Кубическим комплексом K⁰(f) булевой функции f называется множество 0-кубов этой функции. В общем случае кубическим комплексом K^r(f) булевой функции f называется объеденение множеств кубов всех размерностей этой функции

m

k(f)=UK^r(f) m-максимальная размерность кубов функции f.

r=0

Пример получения кубических комплексов

f³(x)=V(1,2,3,6,7) |001 (1) |0x1 (1-3) (1)

(f=1) |010 (2) |01x (2-3) (2)

K⁰(f)=|011 (3) K¹(f)=|x10 (2-4) (3) K²(f)=|x1x (2-5)

|110 (4) |x11 (3-5) (4)

|111 (5) |11x (4-5) (5)

K³(f)=пустому множеству

K(f)=K⁰(f)UK¹(f)UK²(f)

Для получения кубического комплекса K(f) необходимо провести всевозможные операции склеивания над 0-кубами, 1-кубами и т.д. до тех пор пока на очередном шаге не получится K^r+1(f)=пустому множеству. При склеивании 1-кубов 2-кубы представлены в 2-х экземплярах как результаты склеивания 2-х различных пар 1-кубов.

Распространяя этот принцип можно утверждать, что r-кубы как результат склеивания (r-1)-кубов получаются в r-кратном количестве экземпляров.

Куб, входящий в состав кубического комплекса K(f) называется максимальным, если он не вступает ни в одну операцию склеивания.

В приведенном примере максимальными кубами являются х1х и 0х17.

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

Подобный подход носит ограниченный характер и как правило является наглядным для булевых функций от 2-х и 3-х переменных.

F³(x)=V(1,2,3,6,7)

(f=1)

Геометрическим местом 0-куба является точка, представляющая существенную вершину.

Два соседних 0-куба являются концами какого-либо ребра.

Геометрическим местом 1-куба является ребро, замыкаемое склеивающимися 0-кубами, образующими данный 1-куб.

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

Геометрическим образом 3-куба можно считать 3-х мерный куб. Так как он может быть образован 3-мя способами как пара параллельных граней, то при склеивании он получается в трех экземплярах.

Покрытия булевых функций.

Между кубами различной размерности, входящих в кубический комплекс K(f), существует отношение включения или покрытия. Принято говорить, что куб А меньшей размерности покрывается кубом Б большей размерности, если куб А включается в куб Б. Это означает, что при образовании куба Б хотя бы в одном склеивании учавствует куб А.

Отношение включения (покрытия) между кубами принято обозначать АÌБ. В теории множеств отношение включения связывает между собой некоторое множество и его подмножества.

Для рассмотренного примера отношения включения имеют место между 001Ì0х1; 011Ìx11Ìx1x... любой 1-куб покрывает 2 0-куба, 2-куб - 4 0-куба и 2 1-куба, 3-куб покрывает 8 0-кубов, 12 1-кубов и 6 2-кубов.

Покрытием булевой функции f называется такое подмножество кубов из кубического комплекса K(f), которое покрывает все существенные вершины функции.

В связи с тем, что любому кубу комплекса K(f) можно поставить в соответствие конъюнктивный терм, для любого покрытия можно представить некоторую ДНФ булевой функции.

Частным случаем покрытия булевой функции является кубический комплекс K⁰(f), покрытие c⁰(f)=K⁰(f). Этому покрытию соответствует КДНФ.

Для примера покрытием является также

|0x1

|01x

c1(f)=K1(f)=|x10

|x11

|11x

этому покрытию соответствует ДНФ вида

_ _ _ _ _ _ _ _ _ _

f=x₁x₃vx₁x₂vx₂x₃vx₂x₃vx₁x₂ приведенная ДНФ не является минимальной.

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

|0x1

c²(f)=|x1x

Действительно, куб 0х1 покрывает существенные вершины 0х1É(001, 011), а куб x1xÉ(010, 011, 110, 111).

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

Покрытие c²(f) соответствует ДНФ вида х₁х₃vx₂. Эта ДНФ является минимальной. Покрытие булевой функции, которое соответствует минимальной ДНФ называется минимальным покрытием.

Минимальное покрытие должно состоять только из максимальных кубов.

В частном случае все множество максимальных кубов является минимальным покрытием. Это справедливо для нашего примера. В общем случае множество максимальных кубов является избыточным и для получения минимального покрытия достаточно взять некоторое его подмножество.

Пример : f3(x)=V(0,1,4,6,7)

(f=1)

|000 (1) |00x (1-2)

|001 (2) |x00 (1-3)

K⁰(f)=|100 (3) K¹(f)=|1x0 (3-4)

|110 (4) |11x (4-5)

|111 (5)

Для данного примера множество максимальных кубов совпадает с комплексом K¹(f). Z(f)=K¹(f)

Минимальными покрытиями являются

|00x |00x

с¹(f)=|11x c²(f)=|11x

|x00 |1x0

Из анализа покрытия существенных вершин максимальными кубами из комплекса K¹(f) следует :

1. Куб 00х должен обязательно включаться в покрытие, так как только он покрывает существенную вершину 001, аналогично 11х покрывает 111.

Множество максимальных кубов без которых не может быть образовано покрытие булевой функции называется ядром покрытия T(f)=|00x

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

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