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

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

Версия 15:49, 20 мая 2020

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