University-notes/1 курс/2 семестр/Дискретка/Билеты/13.md

Теорема о сокращённой ДНФ монотонной функции

Теорема

Функция является монотонной тогда и только тогда, когда её сокращённая ДНФ не содержит отрицаний.

Доказательство

Пусть f представлена 1 курс/2 семестр/Дискретка/Билеты/2#ДНФ, не содержащий отрицаний. Т.к. такая ДНФ содержит только операции \vee и \wedge, то f \in [\{\vee, \wedge\}]. В свою очередь, \{\vee, \wedge\} \subseteq M и [\{\vee, \wedge\}] \subseteq M Таким образом, f \in M

Теперь докажем, что если f \in M, то её 1 курс/2 семестр/Дискретка/Билеты/4#Сокращённая ДНФ не содержит отрицаний:

Пусть f(x_1, x_2, \dots, x_n) \in M. Рассмотрим простую 1 курс/2 семестр/Дискретка/Билеты/4#Импликанта A. Предположим, что A содержит отрицание. НУО, пусть A = x^0_1 \cdot x^{\alpha_2}_2 \cdot x^{\alpha_3}_3 \dots x^{\alpha_k}_k

Рассмотрим набор \tilde\alpha = (0, \alpha_2, \alpha_3, \dots, \alpha_k, 0, \dots, 0). Очевидно, A(\tilde\alpha) = 1. Т.к. A - импликанта f, то f(\tilde\alpha_0) = 1

Для любого набора \tilde\beta = (1, \alpha_2, \alpha_3, \dots, \alpha_k, \beta_{k+1}, \dots, \beta_n) выполняется \tilde\alpha \preceq \tilde\beta. Поскольку f \in M, то f(\tilde\beta) = 1. Итак, при любых \beta_{k+1}, \dots, \beta_n, любая элементарная конъюнкция x^1_1 \cdot x^{\alpha_2}_2 \cdot x^{\alpha_3}_3 \dots x^{\alpha_k}_k \cdot x^{\beta_{k+1}}_{k+1} \dots x^{\beta_n}_n является импликантой f

Склейкой по всем переменным x_{k+1}, \dots, x_n получаем импликанту A^` = x^1_1 \cdot x^{\alpha_2}_2 \cdot x^{\alpha_3}_3 \dots x^{\alpha_k}_k. Тогда по свойству склейки, A \vee A^` = x^{\alpha_2}_2 \cdot x^{\alpha_3}_3 \dots x^{\alpha_k}_k - тоже импликанта f. Но тогда A не является простой импликантой. Противоречие