Diskretka2

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

Метод получения сокращенной ДНФ

1. Выписываем все грани, содержащиеся в f .

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

Метод получения сокращенной ДНФ

1.Выписываем все грани, содержащиеся в f .

2.Выписываем все ребра, содержащиеся в f , но не содержащиеся в 1.

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

Метод получения сокращенной ДНФ

1.Выписываем все грани, содержащиеся в f .

2.Выписываем все ребра, содержащиеся в f , но не содержащиеся в 1.

3.Выписываем все вершины, содержащиеся в f , но не содержащиеся в 1 и 2.

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

Пример построения сокращенной ДНФ

z

xz

yz

xy

xy

yz y

xxz

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

Тупиковая ДНФ № 1

z

xz

yz

yz y

xxz

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

Тупиковая ДНФ № 2

z

yz

xy

xy

yz y

x

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

Тупиковая ДНФ № 3

z

xz

xy

xy

y

xxz

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

Тупиковая ДНФ № 4

z

xz

xy

yz y

x

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

Тупиковая ДНФ № 5

z

yz

xy

y

xxz

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

Монотонные функции

IНабор (x1; x2; : : : ; xn) 2 Bn меньше или равен набору

(y1; y2; : : : ; yn) 2 Bn, (x1; x2; : : : ; xn) (y1; y2; : : : ; yn), если

x1 y1; x2 y2; : : : ; xn yn: