Логика высказываний. Доказательство утверждения

[kernel1983]

Почему-то не получается доказать простое на вид утверждение: "Отрицание не являющейся противоречием формулы логики высказываний есть дизъюнкция тех и только тех элементарных конъюнкций (от тех же самых переменных), которые не входят в СДНФ данной формулы".

Пусть формула $ F$ представлена в совершенной дизъюнктивной нормальной форме:

$ F(P_1,P_2, \ldots, P_n) \simeq \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}) $.

Требуется доказать, что

$ \overline{F(P_1,P_2, \ldots, P_n)} \simeq \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=0}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}) $.

Запись

$ \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}) $

обозначает дизъюнкцию всех конъюнкций

$ P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n} $,

где $ P_i^{\alpha_i}=P_i $, если $ \alpha_i=1 $, $ P_i^{\alpha_i}=\overline{P_i }$, если $ \alpha_i=0 $, когда индексы дизъюнктирования пробегают все наборы $ (\alpha_1, \alpha_2, \ldots, \alpha_n) $, на которых $ F(P_1,P_2, \ldots , P_n) =1 $.

Используя второй закон де Моргана, получим:

$ \overline{\underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( P_1^{\alpha_1} \wedge P_2^{\alpha_2} \wedge \ldots \wedge P_n^{\alpha_n}) } \simeq $ $\underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \wedge } \ (\overline{P_1^{\alpha_1}} \vee \overline{ P_2^{\alpha_2} } \vee \ldots \vee \overline{ P_n^{\alpha_n}})$.

Применяя дистрибутивность дизъюнкции относительно конъюнкции, имеем:

$ \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \wedge } \ ( \overline{P_1^{\alpha_1}} \vee \overline{ P_2^{\alpha_2} } \vee \ldots \vee \overline{ P_n^{\alpha_n}}) \simeq $ $\underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( \overline{P_1^{\alpha_1}} \wedge \overline{ P_2^{\alpha_2} } \wedge \ldots \wedge \overline{ P_n^{\alpha_n}})$.

А вот дальше не могу сообразить... В общем, прошу подсказки.

[mihaild]

kernel1983 в сообщении #1167995 писал(а):

$ \underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \wedge } \ ( \overline{P_1^{\alpha_1}} \vee \overline{ P_2^{\alpha_2} } \vee \ldots \vee \overline{ P_n^{\alpha_n}}) \simeq $ $\underset{F(\alpha_1, \alpha_2 , \ldots , \alpha_n)=1}{ \vee } \ ( \overline{P_1^{\alpha_1}} \wedge \overline{ P_2^{\alpha_2} } \wedge \ldots \wedge \overline{ P_n^{\alpha_n}})$.

Это какая-то очень странная дистрибутивость. Представьте что у вас всего один элемент в конъюнкции слева. Получите $x \vee y = x \wedge y$.

Попробуйте посмотреть, как связаны элементарные конъюнкты в СДНФ функции и в СДНФ ее отрицания.

[kernel1983]

mihaild в сообщении #1168000 писал(а):

как связаны элементарные конъюнкты в СДНФ функции и в СДНФ ее отрицания

Как связаны, понятно, и это можно показать на примере: на тех наборах, где конъюнкты функции принимает значение нуль, конъюнкты отрицания принимают значение единица, и наоборот. Но как это в общем виде доказать...

[mihaild]

Сколько разных наборов значений переменных, на которых один элементарный конъюнкт принимает значение $1$?

Попробуйте подумать о множестве всех элементарных конъюнктов $n$ переменных. Сколько их? Как связаны множества элементарных конъюнктов из СДНФ функции и ее отрицания?

[kernel1983]

mihaild в сообщении #1168075 писал(а):

Как связаны множества элементарных конъюнктов из СДНФ функции и ее отрицания?

Они не пересекаются.

[mihaild]

kernel1983 в сообщении #1168121 писал(а):

Они не пересекаются.

Правильно. Вы умеете это доказывать?
Плюс можно сказать еще кое-что. Возьмем один элементарный конъюнкт, и посмотрим в какие из этих двух СДНФ он входит. Есть 4 варианта (какие?). Вы сказали, что не может реализоваться вариант "входит в обе". Могут ли реализоваться остальные три?