Есть ли какое-нибудь выражение булевой алгебры, которое нельзя поместить в 3SAT?

Question

Это кажется мне довольно очевидным. Нет, но я мог бы оставить особый случай.Как я вижу, 1SAT (только один литерал в предложении) и 2SAT могут быть легко преобразованы в 3SAT.Любое предложение с более чем 3 литерами было доказано, что оно может быть преобразовано в 3SAT.Поэтому, возможно, вопрос следует задать так: можно ли поместить всю булеву алгебру в SAT?или мы можем определить булеву алгебру только с этими операторами?И ИЛИ И НЕ

Answer 1

Нет, нет.

Я не буду приводить полное доказательство, но вот основная идея: запишите данную формулу в нормальной форме, то есть, соединение дизъюнкций. Используйте индукцию по числу переменных в выражении. Выберите самое длинное подвыражение с n + 1 переменными, введите новую переменную для некоторой части подвыражения, чтобы оставить выражение из n переменных, добавьте ограничения для новой переменной в формулу, повторите процедуру столько раз, сколько необходимо для получения формулы где самое длинное подвыражение имеет n переменных.