-1

Пусть:

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

изменен 12 Сен '13 9:20

Я так понимаю, что функция, задаваемая этим выражением, является тождественной единицей (то есть, с логической точки зрения, речь идёт о тавтологии). Если брать за основу штрих Шеффера, то подойдёт отрицание конъюнкции $%x$% и $%\neg x$%, то есть двух операций достаточно. А от $%y$% и $%z$% функция зависит "фиктивно".

(11 Сен '13 21:07) falcao

Ничего не понял.

(12 Сен '13 9:14) Галактион

@Галактион: прежде всего, согласны ли Вы с тем, что при любых значениях переменных, указанное Вами предложение всегда равно 1? Если да, то рассматриваем выражение $%x|(x|x)$% с тем же свойством, где "палочка" означает штрих Шеффера.

(12 Сен '13 9:28) falcao

Я не согласен, что указанное мной предложение "$%x \lt y \wedge y \le z \rightarrow x \lt z$%" = 1 [даже иногда].

(12 Сен '13 9:35) Галактион

Если не говорить об уровне "формалистики", то Ваше предложение является тождественно истинным высказыванием. В этом смысле ему можно приписать логическое значение 1 из $%{\mathbb B}$%.

(12 Сен '13 12:06) falcao
  1. Я согласен, что достоверность предложения "$%x \lt y \wedge y \le z \rightarrow x \lt z$%" равна достоверности предложения "$%x | (x | x)$%", если во втором из указанных предложений под x следует понимать предложение и не следует понимать [булево] число.

  2. Я не согласен, что вычислительная сложность предложения "$%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)$%".

(12 Сен '13 20:45) Галактион

В обоих случаях сравниваются булевы функции. Под вычислительной сложностью в этих случаях можно понимать минимальное число элементов (из заданного множества), которое требуется для составления схемы. При таком толковании двух элементов достаточно, а одного -- мало. Если Вас такое определение не устраивает (что вполне возможно, так как определения даём мы сами), то предложите какое-то другое.

(12 Сен '13 22:37) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

$%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

изменен 14 Сен '13 9:27

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×107

задан
11 Сен '13 20:59

показан
1095 раз

обновлен
14 Сен '13 9:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru