СКНФ тавтологии

[Sinoid]

Здравствуйте! Скажите, пожалуйста, распространяется ли приведение к СКН-форме на тавтологии? В ответе сказано, что СКН-формы для тавтологии от трех переменных $X\vee\neg X$ этой формы не существует. А я думаю: а что мне помешает взять и привести стандартным методом эту тавтологию к этой форме?

[arseniiv]

Зависит от используемого определения СКНФ. Если допускается пустая конъюнкция, то она по определению является и тавтологией. Если должна быть хотя бы одна элементарная $\vee$, не получится.

-- Чт июн 09, 2016 23:15:56 --

(Вы ведь в курсе, что элементарные дизъюнкции в СКНФ соответствуют нулям в таблице истинности? Отсюда всё сразу следует.)

[Sinoid]

arseniiv в сообщении #1130420 писал(а):

Зависит от используемого определения СКНФ

Определение вот:




-- 10.06.2016, 13:00 --

arseniiv в сообщении #1130420 писал(а):

Зависит от используемого определения СКНФ

Определение вот:



Скорее всего, нет: и пустое множество еще не определено, множества вообще еще не определены.

arseniiv в сообщении #1130420 писал(а):

Вы ведь в курсе, что элементарные дизъюнкции в СКНФ соответствуют нулям в таблице истинности?

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

[arseniiv]

Sinoid в сообщении #1130526 писал(а):

Скорее всего, нет: и пустое множество еще не определено, множества вообще еще не определены.

А пустое множество тут и не нужно. Но да, видно, что с таким определением пустая конъюнкция не получится — исключение для одного дизъюнктивного одночлена описано явно, а для нуля нет.

Sinoid в сообщении #1130526 писал(а):

Так это получается, что пустая конъюнкция и дизъюнкция вводятся для восполнения пробела, вызванного отсутствием СКНФ и СДНФ у тавтологии и противоречия соответственно?

Можно сказать и так, а можно сказать, что булева алгебра с $\vee$ и 0 — это моноид, так же как и с $\wedge$ и 1. Потому мы можем определить дизъюнкцию $\operatorname{or}$ произвольного кортежа значений так, чтобы $\operatorname{or}\alpha\vee\operatorname{or}\beta = \operatorname{or}(\alpha\beta)$ для любых кортежей $\alpha,\beta$, хоть пустых ($\alpha\beta$ — конкатенация). Аналогично для $\wedge$. Если бы была полугруппа, могли бы определить такую штуку только для непустых кортежей. (Когда есть коммутативность, можно вместо кортежей брать мультимножества. Когда есть идемпотентность, можно брать просто множества. Так что, в принципе, можно сказать, что $\alpha,\beta$ — множества, вместо конкатенации их объединение, и тут, действительно, пустое множество будет нужно. Но конечные множества — это вообще довольно простая вещь, чтобы ими не пользоваться, если не определили ещё какую-то аксиоматическую теорию множеств. Ошибиться трудно.)

-- Пт июн 10, 2016 15:58:34 --

Выше я хотел сказать, что СКНФ — это не самая главная мотивация для введения конъюнкции нуля аргументов. Они появляются почти сами собой.

[Sinoid]

arseniiv в сообщении #1130555 писал(а):

А пустое множество тут и не нужно

Когда я писал про пустое множество, я имел ввиду просто аналогию, хотя... Вот у меня есть множество пропозициональных переменных $X_{1},X_{2},\ldots,X_{n}$. Я могу взять произвольное подмножество из двух переменных и ему будет соответствовать некоторый конъюнктивный одночлен. Но пустое-то множество тоже подмножество этого множества пропозициональных переменных, и, значит, для придания общности, ему должен соответствовать некоторый конъюнктивный одночлен, всегда равный 1, скорее всего ввиду справедливости равенства $\varnothing\cup X=X$ для любого множества $X$.

[Sinoid]

Спасибо за помощь. И подсказали интересную мысль про пустую конъюнкцию. Да, мысль интересная, на сегодня мне представляется это очень интересным.

[arseniiv]

Ну, собственно, пустые суммы и произведения вы, наверно, уже видели. Пустые СКНФ/СДНФ как раз на ура представляются где-нибудь в программах, где они находят применение: там каждый одночлен — это просто список, и вся С(К|Д)НФ — тоже список. Чтобы вычислить значение этой С(К|Д)НФ, нужно пройтись по этому списку довольно простым циклом. С пустыми списками всё это работает не хуже, чем с непустыми.

[Sinoid]

arseniiv в сообщении #1131553 писал(а):

Ну, собственно, пустые суммы и произведения вы, наверно, уже видели

Честно говоря, я припоминаю, сто лет назад, когда изучал определители, я наткнулся на один пример, где нужен был пустой определитель и для общей картины он должен был равняться 1, а так пока на подобные вещи не натыкался.