Diskretka2

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

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

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

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

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

IФункция f : Bn ! B называется монотонной, если

(x1; : : : ; xn) (y1; : : : ; yn) =) f (x1; : : : ; xn) f (y1; : : : ; yn)

для всех (x1; x2; : : : ; xn); (y1; y2; : : : ; yn) 2 Bn.

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

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

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

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

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

IФункция f : Bn ! B называется монотонной, если

(x1; : : : ; xn) (y1; : : : ; yn) =) f (x1; : : : ; xn) f (y1; : : : ; yn)

для всех (x1; x2; : : : ; xn); (y1; y2; : : : ; yn) 2 Bn.

I0; 1; x; y; x _ y; x & y монотонные функции.

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство. Пусть x1 & x2 2 & : : : & xk k простой импликант монотонной функции f (x1; x2; : : : ; xn) при k n.

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство. Пусть x1 & x2 2 & : : : & xk k простой импликант монотонной функции f (x1; x2; : : : ; xn) при k n. Тогда

x1 = 0 & x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство. Пусть x1 & x2 2 & : : : & xk k простой импликант монотонной функции f (x1; x2; : : : ; xn) при k n. Тогда

x1 = 0 & x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

Но (0; 1; : : : ; k ; xk+1; : : : ; xn) (1; 1; : : : ; k ; xk+1; : : : ; xn).

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство. Пусть x1 & x2 2 & : : : & xk k простой импликант монотонной функции f (x1; x2; : : : ; xn) при k n. Тогда

x1 = 0 & x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

Но (0; 1; : : : ; k ; xk+1; : : : ; xn) (1; 1; : : : ; k ; xk+1; : : : ; xn). Значит

x1 = 1 & x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство (Продолжение). Таким образом,

x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

Доказательство (Продолжение). Таким образом,

x2 = 2 & : : : & xk = k =) f (x1; : : : ; xn) = 1:

Значит, x2 2 & : : : & xk k импликант f , а это противоречит тому, что x1 & x2 2 & : : : & xk k простой импликант.

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

Простые импликанты монотонных функций

Теорема. Простые импликанты монотонных функций не содержат отрицаний.

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