Одна теорема из логики

[MestnyBomzh]

Теорема:Всякая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от $0$ и $1$;
Док-во: Пусть дана булева формула, без отрицаний. Применим к ней процедуру приведения к ДНФ. Получим невырожденную ДНФ также не содержащую отрицаний. Пусть на наборе $a=(a_1......a_n) F(a)=1$. Тогда $F$ содержит конъюнкцию (без отрицаний!) $x_{i1}....x_{ik}=1$, равную $1$ на этом наборе. Следовательно, $a_{i1}=....=a_{ik}=1$. Рассмотрим любой набор $b$, больший чем $a$. В нем обязательно $b_{i1}=....=b_{ik}=1$, поэтому $x_{i1},.....x_{ik}$ обратится в $1$ и $F(b)=1$; Таким образом, условие монотонности для $F$ выполнено и функция $f$, представляемая ДНФ $F$ (а значит, и исходной формулой), монотонна.
Кто-нибудь, пожалуйста, объясните этот момент: ....Тогда $F$ содержит конъюнкцию (без отрицаний!) $x_{i1}....x_{ik}=1$, равную $1$ на этом наборе. Следовательно, $a_{i1}=....=a_{ik}=1$....здесь $x_{i1}....x_{ik}=1$ это элементы конъюнкции? То есть есть $x_{i1}\wedge ....\wedge x_{ik}=1$, а что тогда означает: Следовательно, $a_{i1}=....=a_{ik}=1$. Что это за набор, что он означает?

[patzer2097]

MestnyBomzh в сообщении #819375 писал(а):

Теорема:Всякая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от $0$ и $1$

чтобы это утверждение имело смысл, надо написать, в какой сигнатуре эта формула предполагается записанной. Иначе я возьму просто $x_1\rightarrow x_2$, и тогда - она содержит отрицания? а монотонна?

[MestnyBomzh]

patzer2097, ну тут, безусловно, имеется в виду минимальное ДНФ

[nikvic]

MestnyBomzh в сообщении #819375 писал(а):

Применим к ней процедуру приведения к ДНФ.

В этом нет нужды. Формула является деревом, и естественно воспользоваться индукцией по его построению.