Гипотеза Кука — проблема ли?

[CherkasovMY]

Dmitriy40 в сообщении #1236175 писал(а):

Это не так. Всего лишь комбинация $x=y=z=1$ не подходит, но это не значит что нет другой подходящей комбинации. Например $z=u=1, \, x=y=v=0$ обращает выражение в $1$.

Этот пример не имеет доказательной силы, т.к. любое непротиворечивое логическое выражение при любом наборе значений переменных должно принимать значение либо истина, либо ложь. Если же есть хотя бы один пример набора значений переменных, приводящих к противоречию, то это говорит о его противоречивости.
Например, вряд ли кто-нибудь будет искать значения переменных, придающих значение истина выражению: $ (x \bar{x} \vee xy)$ Приведем его к виду: $ x(\bar{x} \vee y)$ и получим: при $x=1, y=1$ выражение равно $1$, а при $x=1, y=0$ — противоречие.

[Xaositect]

Вообще-то задача о выполнимости и состоит в том, чтобы найти набор значений, при котором выражение равно $1$.

[Sender]

CherkasovMY в сообщении #1236391 писал(а):

Этот пример не имеет доказательной силы, т.к. любое непротиворечивое логическое выражение при любом наборе значений переменных должно принимать значение либо истина, либо ложь. Если же есть хотя бы один пример набора значений переменных, приводящих к противоречию, то это говорит о его противоречивости.

Это где вы такое вычитали?

[Red_Herring]

CherkasovMY в сообщении #1236391 писал(а):

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

Просветите нас, чем противоречие отличается от лжи?

[mihaild]

CherkasovMY в сообщении #1236391 писал(а):

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

Что такое "противоречивая КНФ"?
Каждая КНФ задает булеву функцию. Эта булева функция может быть: тождественным нулем ($0$ при всех значениях переменных), тождественной единицой ($1$ при всех значениях переменных) и ни тем ни тем (при каких-то значениях переменной $0$, при каких-то $1$). Задача 3SAT: существует ли набор значений, на которых функция, заданная данной 3-КНФ, равна $1$? (или, что то же самое, является ли функция, заданная данной 3-КНФ, тождественным нулем, или нет)
Как видите, слово "противоречивость" нигде в формулировке не используется. Если вы хотите о ней рассуждать - нужно сначала определить, что оно значит.

[Dmitriy40]

CherkasovMY в сообщении #1236391 писал(а):

Этот пример не имеет доказательной силы, т.к. любое непротиворечивое логическое выражение при любом наборе значений переменных должно принимать значение либо истина, либо ложь.

Ещё как имеет. Это пример когда выражение принимает значение истина. При всех остальных значениях выражение принимает значение ложь. Никакого третьего значения (противоречие) выражение не принимает, это вы что-то себе навыдумывали. Ваше противоречие всего лишь может означать что при некоторых комбинациях одних переменных выражение перестаёт зависеть от некоторых других переменных - и это вполне нормально.