Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

P=P(xixi=(P(xi)(P(xi)

_ _ _ _ _ _ _ _ _

_ y=x1(x2x3(ДНФ)=(x1(x2)(x1(x3)(КНФ)=(x1(x2(x3x3)(x1(x3(x2x2)=

_ _ _ _ _ _ _ _
=(x1(x2(x3)(x1(x2(x3)(x1(x2(x3)(x1(x2(x3)(ККНФ)

y=[pic](4,6,7)

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

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

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

В кубическом представлении булевой функции от n переменных все множество из 2n наборов ее аргументов рассматривается как множество координат вершин 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 независимую координату.

Операция склеивания над кубами соответствует применению закона склеивания к конъюнктивным термам, отождествляемым с этими кубами.
Пример : для склеивания (*)
_ _ _ _ _ _ _ х1х2х3х4( х1х2х3х4= х1х3х4
(0101) (0001) (0х01)

_ _ _ _ для (**) х1х3х4( х1х3х4= х1х4

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

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

Кубическим комплексом K0(f) булевой функции f называется множество 0- кубов этой функции. В общем случае кубическим комплексом Kr(f) булевой функции f называется объеденение множеств кубов всех размерностей этой функции m k(f)=UKr(f) m-максимальная размерность кубов функции f. r=0
Пример получения кубических комплексов f3(x)=V(1,2,3,6,7) |001 (1) |0x1 (1-3) (1)

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

K0(f)=|011 (3) K1(f)=|x10 (2-4) (3)
K2(f)=|x1x (2-5)

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

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

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

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата