Diskretka2

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

Пример–домашнее задание

1.Сокращенная ДНФ = ?

2.Тупиковые ДНФ = ?

3.Минимальная ДНФ = ?

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

Булевы функции как подмножества Rn

I B = f0; 1g R и Bn Rn:

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

Булевы функции как подмножества Rn

IB = f0; 1g R и Bn Rn:

IОтождествим функци f : Bn ! B с множеством

f(x1; x2; : : : ; xn) 2 Bnjf (x1; x2; : : : ; xn) = 1g

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

Булевы функции как подмножества Rn

IB = f0; 1g R и Bn Rn:

IОтождествим функци f : Bn ! B с множеством

f(x1; x2; : : : ; xn) 2 Bnjf (x1; x2; : : : ; xn) = 1g

z

(0; 0; 1) (0; 1; 1)

(1; 0; 1) (1; 1; 1)

(0; 1; 0)

(0; 0; 0)

y

(1; 0; 0)

x(1; 1; 0)

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

Элементарные конъюнкты

множеством (x1; x2; : : : ; xn) 2 Bn таких, что xi1 = 1; : : : xi2 = 2; : : : ; xik = k

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

Элементарные конъюнкты

множеством (x1; x2; : : : ; xn) 2 Bn таких, что xi1 = 1; : : : xi2 = 2; : : : ; xik = k

Полные конъюнкты вершины:

z

xyz xyz

xyz xyz

xyz

xyz

y

xyz

xxyz

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

Элементарные конъюнкты

xi1 = 1; : : : xi2 = 2; : : : ; xik = k

Конъюнкты длины n 1 ребра:

z

xz

yz yz

xxz