Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-equiv-in-3knf — различия между версиями

Версия 02:08, 26 декабря 2014

Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.

@@ Строка 1: / Строка 1: @@
-<big>Цыганова Светлана, 974гр.</big>
 Выразите логическое отношение эквивалентности в виде 3-КНФ формулы.
-<latex>
+[[Category:Решенные задачи]]
-\textbf{Решение}
-Отношение эквивалентности $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 &          1         &         1         &      1\\
-& 1 &          1         &         0         &      0\\
-& 0 &          0         &         1         &      0\\
-& 1 &          1         &         1         &      1\\
-\hline
-\end{tabular}
-Все получается.
-</latex>
-[[Category:На проверку]]
+<!--Вообще-то, решения уже есть-->