Diskretka3

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

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 простой импликант.

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

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

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