КНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
}}
 
}}
 
Пример КНФ:
 
Пример КНФ:
<tex>f(x,y) = (x \lor y) \land (y \lor \neg z)</tex>
+
<tex>f(x,y) = (x \lor y) \land (y \lor \overline{z})</tex>
  
 
{{Определение
 
{{Определение
Строка 14: Строка 14:
 
}}
 
}}
 
Пример СКНФ:
 
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg y \lor z) \land (x\lor y \lor \neg z)</tex>
+
<tex>f(x,y,z) = (x \lor \overline{y} \lor z) \land (x\lor y \lor \overline{z})</tex>
  
 
{{Теорема
 
{{Теорема
Строка 20: Строка 20:
 
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
 
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
 
|proof =  
 
|proof =  
Поскольку инверсия функции <tex>\neg f(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg f(\vec x)</tex> можно записать следующим образом:
+
Поскольку инверсия функции <tex>\overline{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\overline{f}(\vec x)</tex> можно записать следующим образом:
 +
<tex> \overline{f}(\vec x) = \bigvee\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) </tex>
  
 +
Найдём инверсию левой и правой части выражения:
 +
<tex> f(\vec x) = \overline{\bigvee\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})} </tex>
 +
 +
Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
 +
<tex> f(\vec x) = \bigwedge\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\overline{\sigma_{1}}} \vee x_{2}^{\overline{\sigma_{2}}} \vee ... \vee x_{n}^{\overline{\sigma_{n}}}) </tex>
 +
 +
Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
 
}}
 
}}
 
==Алгоритм построения СКНФ по таблице истинности==
 
==Алгоритм построения СКНФ по таблице истинности==
Строка 29: Строка 37:
  
 
==Примеры СКНФ для некоторых функций==
 
==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg x \lor y) \land (x \lor \neg y) \land (\neg x \lor \neg y)</tex>
+
Стрелка Пирса: <tex> x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})</tex>
  
Медиана трёх: <tex>f(x,y,z) = ( x \lor y \lor z) \land (\neg x \lor y \lor z) \land (x \lor \neg y \lor z) \land ( x \lor y \lor \neg z)</tex>
+
Медиана трёх: <tex>f(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})</tex>

Версия 04:41, 17 декабря 2010

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

Пример КНФ: [math]f(x,y) = (x \lor y) \land (y \lor \overline{z})[/math]


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

Пример СКНФ: [math]f(x,y,z) = (x \lor \overline{y} \lor z) \land (x\lor y \lor \overline{z})[/math]

Теорема:
Для любой булевой функции [math]f(\vec{x})[/math], не равной тождественной единице, существует СКНФ, ее задающая.
Доказательство:
[math]\triangleright[/math]

Поскольку инверсия функции [math]\overline{f}(\vec x)[/math] равна единице на тех наборах, на которых [math]f(\vec x)[/math] равна нулю, то СДНФ для [math]\overline{f}(\vec x)[/math] можно записать следующим образом: [math] \overline{f}(\vec x) = \bigvee\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) [/math]

Найдём инверсию левой и правой части выражения: [math] f(\vec x) = \overline{\bigvee\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})} [/math]

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем: [math] f(\vec x) = \bigwedge\limits_{f(\sigma_{1}, \sigma_{2}, ... ,\sigma_{n}) = 0} (x_{1}^{\overline{\sigma_{1}}} \vee x_{2}^{\overline{\sigma_{2}}} \vee ... \vee x_{n}^{\overline{\sigma_{n}}}) [/math]

Последнее выражение и является СКНФ. Так как СКНФ получена из СДНФ, которая может быть посторена для любой функции, то теорема доказана.
[math]\triangleleft[/math]

Алгоритм построения СКНФ по таблице истинности

  • В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
  • В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
  • Полученные дизъюнкции связываем операциями конъюнкции

Примеры СКНФ для некоторых функций

Стрелка Пирса: [math] x \downarrow y = (\overline{x} \lor y) \land (x \lor \overline{y}) \land (\overline{x} \lor \overline{y})[/math]

Медиана трёх: [math]f(x,y,z) = ( x \lor y \lor z) \land (\overline{x} \lor y \lor z) \land (x \lor \overline{y} \lor z) \land ( x \lor y \lor \overline{z})[/math]