Hardprob/Maximum Renamable Horn Subformula - История изменений

StasFomin: Массовая правка: замена \in на ∈

2023-04-17T18:00:31Z

Массовая правка: замена \in на ∈

StasFomin: Массовая правка: замена \cup на ∪

2023-04-17T11:39:43Z

Массовая правка: замена \cup на ∪

StasFomin в 11:07, 17 апреля 2023

2023-04-17T11:07:21Z

StasFomin: Новая страница: « * Набор булевых переменных U, коллекция C ск…»

2023-04-13T23:54:26Z

Новая страница: « * Набор булевых переменных U, коллекция C ск…»

Новая страница

* Набор булевых переменных U, коллекция C скобок-конъюнкций не больше чем из трех литералов.
* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] C' от C, т.е. подмножество C'⊆ C, т.к. здесь существует подмножество <m>S
\subseteq U</m>, таких переменных, что перестановка литералов в <m>S \cup \bar{S}</m> делает C' хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
* Максимизировать размер подформулы, т.е. |C'|.

----
{{hard-problem-on-lab17|{{PAGENAME}}}}




----

{{ViggoCode|node240}}





[[Категория:ClassicHardProblems]]

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор булевых переменных <em>U</em>, коллекция <em>C</em> скобок-конъюнкций не больше чем из трех литералов.
-* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <em>S ⊆ U</em>, таких переменных, что перестановка литералов в <m>S ∪ \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
+* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <em>S ⊆ U</em>, таких переменных, что перестановка литералов в <m>S ∪ \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u ∈  S\}</m>.
 * Максимизировать размер подформулы, т.е. <em>|C'|</em>.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор булевых переменных <em>U</em>, коллекция <em>C</em> скобок-конъюнкций не больше чем из трех литералов.
-* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <em>S ⊆ U</em>, таких переменных, что перестановка литералов в <m>S \cup \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
+* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <em>S ⊆ U</em>, таких переменных, что перестановка литералов в <m>S ∪ \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
 * Максимизировать размер подформулы, т.е. <em>|C'|</em>.

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 * Набор булевых переменных <em>U</em>, коллекция <em>C</em> скобок-конъюнкций не больше чем из трех литералов.
-* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <m>S
+* Найти [https://en.wikipedia.org/wiki/Horn-satisfiability переименовываемую хорнову подформулу] <em>C'</em> от <em>C</em>, т.е. подмножество <em>C'⊆ C</em>, т.к. здесь существует подмножество <em>S ⊆ U</em>, таких переменных, что перестановка литералов в <m>S \cup \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
-\subseteq U</m>, таких переменных, что перестановка литералов в <m>S \cup \bar{S}</m> делает <em>C'</em> хорновой булевой формулы, где <m>\bar{S} = \{\bar{u} \mid u \in S\}</m>.
 * Максимизировать размер подформулы, т.е. <em>|C'|</em>.