Построение СКНФ

[volgusha]

Вопрос такой: как построить СКНФ, если при построении таблицы истинности в итоговом столбце только одна строка приводит к лжи? Выходит, что в конъюнкции только один множитель?но тогда она принимает вид простой дизъюнкции трех переменных, такое может быть?

[Desmond]

Какая разница,сколько строк с ложным результатом.

[volgusha]

В моем понимании, в произведении (конъюнкции), должно быть минимум два множителя. Если строка с ложным результатом одна, то и множитель один. Поэтому и спрашиваю, является ли такая форма - СКНФ?

[arseniiv]

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

[volgusha]

Мое определение: Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:
*в ней нет одинаковых элементарных дизъюнкций
*в каждой дизъюнкции нет одинаковых пропозициональных переменных
*каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

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

[arseniiv]

Тогда нужно определение КНФ.

[volgusha]

Ну допустим: Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.

Чем определение поможет?вопрос в том, является ли в данном случае конъюнкция с одним множителем КНФ, а потом уже и СКНФ

[arseniiv]

volgusha в сообщении #985232 писал(а):

Ну допустим

Вижу, копировать определения из русской вики вы умеете. Но а в вашем курсе-то какие определения? Тут важны именно детали. Вы уверены, что они совпадают до деталей?

По мне вот и пустая КНФ возможна. Но что значит «пустая»? Формулы, например, пустыми не бывают, там обязательно хотя бы одна переменная стоит или константа. Значит, КНФ в моих воззрениях — не формула. Действительно, я понимаю её как какую-то конечную последовательность формул с ярлычком «конъюнктивная» (чтобы не перепутать с ДНФ). Тогда и пустая, и из одного элемента вполне возможны.

Другие же люди могут требовать, чтобы КНФ была именно формулой с реальными $\wedge$ в ней. Тогда корректное определение здорово усложняется, и пустую с одноэлементной не определишь прямо, придётся отдельно.

-- Ср мар 04, 2015 00:27:26 --

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

здорово усложняется

(Придётся про ассоциативность $\wedge$ разговаривать и выбирать, какую именно из эквивалентных через применение ассоциативности формул называть КНФ.)

[svv]

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

По мне вот и пустая КНФ возможна.

И её значение равно 1, правильно? А значение пустой ДНФ — нулю.

[arseniiv]

Именно!

-- Ср мар 04, 2015 01:25:34 --

(Оффтоп)

Вообще, я реально сдерживаюсь, чтобы не расписывать на месте индуцируемую ассоциативной бинарной операцией на $A$ [с единицей] функцию $A^+\to A$ [$A^*\to A$]. Уже было, и даже упоминалось название этих штук, оформленных как алгебра с элементами $A^n\to A$. Операды, вроде.

Тут-то они ни к чему.