Как я могу преобразовать выражение CNF в 3-CNF?

Question

У меня есть такое выражение CNF, и я хочу изменить его на 3-CNF:

(a+b+c+d)(~a)(~b+d)(a+b+~d)

Кто-нибудь знает, как я могу это сделать?

Answer 1

3-CNF - это конъюнктивная нормальная форма, в которой все предложения имеют три или менее литералов. Чтобы получить такую ​​форму для вашего выражения, вы можете перевести выражение во вложенное логическое выражение, где все операторы (и, или) имеют два операнда:

t1a = (a+b)
t1b = (c+d)
t1 = t1a + t1b
t2 = (~a)
t3 = (~b+d)
t4a = (a+b)
t4 = t4a + ~d
t5a = t1 t2
t5b = t3 t4
t5 = t5a t5b

Вы можете напрямую перевести это вложенное выражение в набор предложений 3-CNF.

Минимизированное решение:

(~a)(~b + d)(b + ~d)(c + d)  

как предполагает Вольфрам, Альфа является 3-CNF вашего выражения, так как оно не содержит более длинных предложений.

Для небольших случаев вы можете заполнить таблицу истинности. Посмотрите на все строки с выводом 0 и найдите minterms, охватывающие все эти строки. Если вы затем инвертируете все литералы в minterms, у вас есть CNF, Если в предложениях содержится более 3 литералов, их можно разбить на два или более коротких предложения, введя промежуточные переменные. Широко используемая процедура для этого называется трансформацией Цейтина или Кодировкой Цейтина.