Лекция № 5. Основные вопросы, рассматриваемые на лекции

Тема: СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ

Основные вопросы, рассматриваемые на лекции:

1. Совершенная дизъюнктивная нормальная форма

2. Совершенная конъюнктивная нормальная форма

3. Теорема о существовании и построении СДНФ

4. Теорема о существовании и построении СКНФ

Краткое содержание лекционного материала

Дизъюнктивная (конъюнктивная) нормальная форма от n переменных p ₁, …, p_n называется совершенной, если ее конъюнкты (дизъюнкты) не повторяются и в каждом конъюнкте (дизъюнкте) содержится ровно один литерал от переменных p ₁,…, p_n. Обозначение: СДНФ (СКНФ).

Каждая СДНФ (СКНФ) от n переменных содержит не более 2 ⁿ попарно различных конъюнктивных (дизъюнктивных) одночленов.

Формула B называется СДНФ (СКНФ) формулы A, если A º B и B есть СДНФ (СКНФ). Для каждой формулы A, отличной от противоречия (тавтологии), существует СДНФ A (СКНФ A).

СДНФ от n переменных p ₁, …, p_n формулы A (содержащей переменные p ₁, …, p_n) можно найти, используя таблицу истинности для A.

В таблице истинности выделим строки с A º1, и по-новому их перечислим: 1,2,…, m, где 1£ m £2 ⁿ. Через h_ij мы обозначим значение истинности в i -й строке переменной p_j, а через (p_ij)* обозначим переменную p_j (отрицание переменной Ø p_j), если h_ij =1 (соответственно, h_ij =0), где i =1,…, n, j =1,…, m.

Лемма 1. (p_ij)*º1 равносильно p_j = h_ij для всех i =1,…, n, j =1,…, m.

Доказательство. Если h_ij =1, то (p_ij)*º p_j, p_j º1, откуда (p_ij)*º1, p_j º h_ij.

Если h_ij =0, то (p_ij)*ºØ p_j, p_j º0, откуда, вновь, (p_ij)*ºØ0º1, p_j º h_ij. ÿ

Теорема 1. Если формула A не противоречие, то существует СДНФ A.

Доказательство. Если A не противоречие, то найдется хотя бы одна строка с номером m, где 1£ m £2 ⁿ. Используя также лемму 1, получим следующую цепочку эквивалентных предложений (для краткости вместо слова «эквивалентно» пишем знак ~):

.

Значит, ((p ₁₁)*Ù…Ù(p _{1 n} )*)Ú…Ú((p_{m 1})*Ù…Ù(p_mn)*) есть СДНФ A.

Напомним, что: Ø A º B равносильно A ºØ B.

Теорема 2. Если формула A не тавтология, то существует СКНФ A.

Доказательство. Если A не тавтология, то Ø A не противоречие. Применим к Ø A теорему 1: Ø A º((p ₁₁)*Ù…Ù(p _{1 n} )*)Ú…Ú((p_{m 1})*Ù…Ù(p_mn)*) (литералы (p _{1 n} )* выбираются из строк, в которых Ø A º1, т.е. A º0).

Через (Ø p_ij)* обозначим переменную p_j (отрицание переменной Ø p_j), если (p_ij)* есть Ø p_j (соответственно, (p_ij)* есть p_j), где i =1,…, n, j =1,…, m.

Легко увидеть, что Ø(p_ij)*º(Ø p_ij)*.

Применим законы де Моргана и получим СКНФ A:

A ºØ[((p ₁₁)*Ù…Ù(p _{1 n} )*)Ú…Ú((p_{m 1})*Ù…Ù(p_mn)*))]º

ºØ((p ₁₁)*Ù…Ù(p _{1 n} )*)Ù…ÙØ((p_{m 1})*Ù…Ù(p_mn)*)º

º(Ø(p ₁₁)*Ú…ÚØ(p _{1 n} )*)Ù…Ù(Ø(p_{m 1})*Ú…ÚØ(p_mn)*)º

º((Ø p ₁₁)*Ú…Ú(Ø p _{1 n} )*)Ù…Ù((Ø p_{m 1})*Ú…Ú(Ø p_mn)*).