4-

Монотонные функции Самодвойственные функции

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

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

Доказательство. Пусть 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; 2; : : : ; k ; xk+1; : : : ; xn) (1; 2; : : : ; 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; 2; : : : ; k ; xk+1; : : : ; xn) (1; 2; : : : ; 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 простой импликант.

Монотонные функции Самодвойственные функции

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

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

Следствие. Функция является монотонной тогда и только тогда, когда она может быть выражена через суперпозицию функций 0, 1; x & y и x _ y.

Монотонные функции Самодвойственные функции

Сокращенная ДНФ монотонных функций

Теорема. Сокращенная ДНФ монотонной функции является тупиковой (и, следовательно, минимальной).

Монотонные функции Самодвойственные функции

Сокращенная ДНФ монотонных функций

Теорема. Сокращенная ДНФ монотонной функции является тупиковой (и, следовательно, минимальной).

Доказательство. Пусть K = x1 & : : : & xk простой импликант f (x1; x2; : : : ; xn), k n, f = K _ f 0, где f 0 дизъюнкция всех простых импликантов f , кроме K .

Докажем, что f 6= f 0.

Монотонные функции Самодвойственные функции

Сокращенная ДНФ монотонных функций

Теорема. Сокращенная ДНФ монотонной функции является тупиковой (и, следовательно, минимальной).

Доказательство. Пусть K = x1 & : : : & xk простой импликант f (x1; x2; : : : ; xn), k n, f = K _ f 0, где f 0 дизъюнкция всех простых импликантов f , кроме K .

Докажем, что f 6= f 0. Заметим, что каждый импликант K 0 6= K должен содержать литерал xi , i > k, так как K простой.