|
Пусть: 1) $%\mathbb{B}$% - множество булевых чисел, то есть $%\mathbb{B} = \{0, \ 1\}$%, 2) операция $%\times : \mathbb{B}^2 \mapsto \mathbb{B}$% такова, что $%0 \times 0 = 0 \ \wedge \ 0 \times 1 = 0 \ \wedge \ 1 \times 0 = 0 \ \wedge \ 1 \times 1 = 1 $%, 3) операция $%\oplus' : \mathbb{B}^2 \mapsto \mathbb{B}$% такова, что $%0 \oplus' 0 = 0 \ \wedge \ 0 \oplus' 1 = 1 \ \wedge \ 1 \oplus' 0 = 1 \ \wedge \ 1 \oplus' 1 = 1 $%, 4) операция $%\neg : \mathbb{B} \mapsto \mathbb{B}$% такова, что $%\neg 0 = 1 \ \wedge \ \neg 1 = 0$%, 5) $%\{x, y\} \subseteq \mathbb{B}$%, 6) $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \ \rightarrow \ (x \lt y \ \leftrightarrow \ \neg x \times y = 1) \ \wedge \ (x \le y \ \leftrightarrow \ \neg x \oplus' y = 1))$%. Вопрос: Чему равна вычислительная сложность предложения $%x \lt y \wedge y \le z \rightarrow x \lt z$%? задан 11 Сен '13 20:59 
Галактион
показано 5 из 7
показать еще 2
|
|
$%1.$% По моему мнению, выч. сложность сложносочинённого предложения "$%x \lt y \wedge y \le z$%" не больше, чем выч. сложность сложноподчинённого предложения "$%x \lt y \wedge y \le z \rightarrow x \lt z$%". $%2.$% Найдём выч. сложность "$%x \lt y \wedge y \le z$%", предполагая, что $%\{x, y, z\} \subseteq \mathbb{B} \wedge \mathbb{B} = \{0, \ 1\}$%. $%2.1.1$% Если $%\downarrow$% - стрелка Пирса, тогда $$x \lt y \wedge y \le z \ \Leftrightarrow (x \lt y \downarrow x \lt y) \downarrow (y \le z \downarrow y \le z)$$ $%2.1.2$% Если операция "$%\downarrow$%" включена в список базисных операций, тогда вычислительная сложность предложения "$%x \lt y \wedge y \le z$%" не меньше, чем три логические операции "$%\downarrow$%". $%2.2.1$% Если $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \rightarrow (x \lt y \leftrightarrow \neg x \times y = 1) \wedge (x \le y \leftrightarrow \neg x \oplus' y = 1))$%, тогда $$x \lt y \wedge y \le z \Leftrightarrow (\neg x \times y = 1 \downarrow \neg x \times y = 1) \downarrow (\neg y \oplus' z = 1 \downarrow \neg y \oplus' z = 1)$$ $%2.2.2$% Если операция "$%=$%" также включена в список базисных операций, тогда вычислительная сложность предложения "$%x \lt y \wedge y \le z$%" не меньше, чем семь базисных операций, включая три логические операции "$%\downarrow$%" и четыре операции сравнения"$%=$%". $%2.3.1$% Если $%\forall x \forall y (\{x, y\} \subseteq \mathbb{B} \rightarrow \neg x \times y = ((x \Diamond x) \Diamond (x \Diamond x)) \Diamond (y \Diamond y) \wedge \neg x \oplus' y = ((x \Diamond x) \Diamond y) \Diamond ((x \Diamond x) \Diamond y))$%, тогда $%x \lt y \wedge y \le z \Leftrightarrow (((x \Diamond x) \Diamond (x \Diamond x)) \Diamond (y \Diamond y) = 1 \downarrow ((x \Diamond x) \Diamond (x \Diamond x)) \Diamond (y \Diamond y) = 1)$% $% \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \downarrow (((y \Diamond y) \Diamond z) \Diamond ((y \Diamond y) \Diamond z) = 1 \downarrow ((y \Diamond y) \Diamond z) \Diamond ((y \Diamond y) \Diamond z) = 1)$% $%2.3.2$% Если битовая операция "$%\Diamond$%" также включена в список базисных операций, тогда вычислительная сложность предложения "$%x \lt y \wedge y \le z$%" не меньше, чем двадцать семь базисных операций, включая три [бинарные] логические операции "$%\downarrow$%", четыре [бинарные] операции сравнения "$%=$%" и двадцать [бинарных] битовых операций "$%\Diamond$%". $%2.4.1$% Если принять, что выч. сложность предложения "$%x \lt y \wedge y \le z$%" равна указанным 27 базисным операциям, тогда придётся принять, что выч. сложность предложения "$%x \lt y \wedge x \le y$%" тоже равна указанным 27 базисным операциям, хотя во втором из указанных предложений упоминается двоица переменных $%(x, y)$% из множества $%\mathbb{B}^2$%, а в первом - троица переменных $%(x, y, z)$% из множества $%\mathbb{B}^3$%. отвечен 13 Сен '13 2:42
Галактион |
Я так понимаю, что функция, задаваемая этим выражением, является тождественной единицей (то есть, с логической точки зрения, речь идёт о тавтологии). Если брать за основу штрих Шеффера, то подойдёт отрицание конъюнкции $%x$% и $%\neg x$%, то есть двух операций достаточно. А от $%y$% и $%z$% функция зависит "фиктивно".
Ничего не понял.
@Галактион: прежде всего, согласны ли Вы с тем, что при любых значениях переменных, указанное Вами предложение всегда равно 1? Если да, то рассматриваем выражение $%x|(x|x)$% с тем же свойством, где "палочка" означает штрих Шеффера.
Я не согласен, что указанное мной предложение "$%x \lt y \wedge y \le z \rightarrow x \lt z$%" = 1 [даже иногда].
Если не говорить об уровне "формалистики", то Ваше предложение является тождественно истинным высказыванием. В этом смысле ему можно приписать логическое значение 1 из $%{\mathbb B}$%.
Я согласен, что достоверность предложения "$%x \lt y \wedge y \le z \rightarrow x \lt z$%" равна достоверности предложения "$%x | (x | x)$%", если во втором из указанных предложений под x следует понимать предложение и не следует понимать [булево] число.
Я не согласен, что вычислительная сложность предложения "$%x \lt y \wedge y \le z \rightarrow x \lt z$%" равна вычислительной сложности предложения "$%x | (x | x)$%".
P.S. Также я не согласен, что длина предложения "$%x < y \wedge y \le z \rightarrow x \lt z$%" равна длине предложения "$%x | (x | x)$%".
В обоих случаях сравниваются булевы функции. Под вычислительной сложностью в этих случаях можно понимать минимальное число элементов (из заданного множества), которое требуется для составления схемы. При таком толковании двух элементов достаточно, а одного -- мало. Если Вас такое определение не устраивает (что вполне возможно, так как определения даём мы сами), то предложите какое-то другое.