Полиномиальные сводимости и 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-КНФ формулы.