Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-equiv-in-3knf — различия между версиями
Материал из DISCOPAL
Tsyganova (обсуждение | вклад) |
Tsyganova (обсуждение | вклад) |
||
Строка 7: | Строка 7: | ||
Отношение эквивалентности $A \Leftrightarrow B$ записывается следующей 3-КНФ формулой: $(\overline{A}\vee B)\wedge(A\vee\overline{B})$ | Отношение эквивалентности $A \Leftrightarrow B$ записывается следующей 3-КНФ формулой: $(\overline{A}\vee B)\wedge(A\vee\overline{B})$ | ||
+ | |||
+ | Построим таблицу для проверки: | ||
+ | |||
+ | \begin{tabular}{|l|l|l|l|l|} | ||
+ | \hline | ||
+ | A & B & \overline{A}\vee B & A\vee\overline{B} & A \Leftrightarrow B \\ | ||
+ | \hline | ||
+ | 0 & 0 & 1 & 1 & 1\\ | ||
+ | 0 & 1 & 1 & 0 & 0\\ | ||
+ | 1 & 0 & 0 & 1 & 0\\ | ||
+ | 1 & 1 & 1 & 1 & 1\\ | ||
+ | \hline | ||
+ | \end{tabular} | ||
+ | |||
+ | Все получается. | ||
</latex> | </latex> | ||
[[Category:На проверку]] | [[Category:На проверку]] |
Версия 17:07, 1 декабря 2014
Цыганова Светлана, 974гр.
Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.