Пусть:

1.1) $%\mathbb{B}$% - множество булевых чисел, то есть $$\mathbb{B} = \{0, 1\}$$, 1.2) $%\mathbb{N}$% - множество натуральных чисел, причём $$0 \in \mathbb{N} \wedge (\{n, x\} \subseteq \mathbb{N} \wedge x = X_n...X_1X_0 \wedge \forall_{j \in \{0, 1, ..., n\}} (X_j \in \mathbb{B}) \rightarrow x=0X_n...X_1X_0)$$ 2.1) операция $%\otimes : \mathbb{N}^2 \mapsto \mathbb{N}$% такова, что $$0\otimes0=0 \wedge 0\otimes1=0 \wedge 1\otimes0=0 \wedge 1\otimes1=1$$ 2.2.1) операция $%\oplus : \mathbb{N}^2 \mapsto \mathbb{N}$% такова, что $$0\oplus0=0 \wedge 0\oplus1=1 \wedge 1\oplus0=1 \wedge 1\oplus1=0$$ 2.2.2) операция $%\oplus' : \mathbb{N}^2 \mapsto \mathbb{N}$% такова, что $$0\oplus'0=0 \wedge 0\oplus'1=1 \wedge 1\oplus'0=1 \wedge 1\oplus'1=1$$ 3) операция $%\neg : \mathbb{N} \mapsto \mathbb{N}$% такова, что $$\neg0=1 \wedge \neg1=0$$

Верно ли следующее высказывание:

$%\begin {cases} \{n, x, y, z, w\} \subseteq \mathbb{N} \wedge x \geq y \\ \begin {cases} x = X_n...X_2X_1X_0 \\ y = Y_n...Y_2Y_1Y_0 \\ z = Z_n...Z_2Z_1Z_0 \\ w = W_n...W_2W_1W_0 \\ \forall_{j \in \{0, 1, ..., n\}} (\{X_j, Y_j, Z_j, W_j\} \subseteq \mathbb{B}) \end {cases} \\ \begin {cases} W_0 = 0 \\ \forall_{j \in \{1, ..., n\}} (W_j = (\neg X_{j-1} \otimes Y_{j-1}) \oplus' (\neg X_{j-1} \otimes W_{j-1}) \oplus' (Y_{j-1} \otimes W_{j-1})) \\ \forall_{j \in \{0, ..., n\}} (Z_j = X_j \oplus Y_j \oplus W_j) \end {cases} \end {cases} \rightarrow z = x - y \ ?$%

Примечание 1 (Пример бинарной арифметической операции)

$%\begin {cases} \{n, x, y, z, w\} \subseteq \mathbb{N} \\ \begin {cases} x = X_n...X_2X_1X_0 = 0X_n...X_2X_1X_0 \\ y = Y_n...Y_2Y_1Y_0 = 0Y_n...Y_2Y_1Y_0 \\ z = Z_{n+1}Z_n...Z_2Z_1Z_0 \\ w = W_{n+1}W_n...W_2W_1W_0 \\ \forall_{j \in \{0, 1, ..., n\}} (\{X_j, Y_j, Z_j, W_j\} \subseteq \mathbb{B})\wedge \{Z_{n+1}, W_{n+1}\} \subseteq \mathbb{B} \end {cases} \\ \begin {cases} \{W_0, X_{n+1}, Y_{n+1}\} \subseteq \{0\} \\ \forall_{j \in \{1, ..., n+1\}} (W_j = (X_{j-1} \otimes Y_{j-1}) \oplus' (X_{j-1} \otimes W_{j-1}) \oplus' (Y_{j-1} \otimes W_{j-1})) \\ \forall_{j \in \{0, ..., n+1\}} (Z_j = X_j \oplus Y_j \oplus W_j) \end {cases} \end {cases} \Rightarrow z = x + y$%

Примечание 2 (Пример бинарной побитовой операции)

$%\begin {cases} \{n, x, y, z\} \subseteq \mathbb{N}\\ \begin {cases} x = X_n...X_2X_1X_0 \\ y = Y_n...Y_2Y_1Y_0 \\ z = Z_n...Z_2Z_1Z_0 \\ \forall_{j \in \{0, 1, ..., n\}} (\{X_j, Y_j, Z_j\} \subseteq \mathbb{B}) \end {cases} \\ \forall_{j \in \{0, 1, ..., n\}} (Z_j = X_j \otimes Y_j) \end {cases} \Rightarrow z = x \wedge_b y$%

Примечание 3 (Пример унарной побитовой операции)

$%\begin {cases} \{n, x, y\} \subseteq \mathbb{N}\\ \begin {cases} x = X_n...X_2X_1X_0 \\ y = Y_n...Y_2Y_1Y_0 \\ \forall_{j \in \{0, 1, ..., n\}} (\{X_j, Y_j\} \subseteq \mathbb{B}) \end {cases} \\ \forall_{j \in \{0, 1, ..., n\}} (Y_j = \neg X_j) \end {cases} \Rightarrow y = \neg_b(x)$%

задан 7 Сен '13 13:32

изменен 8 Сен '13 8:25

10|600 символов нужно символов осталось
0

И зачем Вам понадобилось переопределять уже определенные до Вас понятия? Здесь все знают, что такое булевы числа, натуральные числа, двоичная запись числа, логические (побитовые) операции умножения, сложения по модулю 2, сложения и отрицания. Вот несколько причин, почему не стоило этого делать:

  • судя по пункту 1.2, речь идет скорее не о натуральных, а о целых неотрицательных числах
  • полагаю, в пункте 1.2 стоит уточнить, что $%\forall_{j\in\{0,1,...,n\}}X_j\in\mathbb{B}$%
  • в данной записи не понятно, что такое $%X_n...X_2X_1X_0$%. я то догадался, что это цифры числа $%x$% в двоичной СС, но из записи это никак не следует. если уж и пытаетесь всё формализировать, то делайте это до конца!
  • раз Вы сами определили понятие натурального числа, значит Вы отказываетесь от традиционного понимания данного понятия. значит, используемые Вами операции $%\gt$% и $%-$% ничего не означают, пока Вы сами их не определите. пока Вы этого не сделаете, сам вопрос не имеет никакого смысла

Если же понимать операции $%\gt$% и $%-$% в привычном смысле, то ответ: да, высказывание верно. Изложенные Вами формулы верны и соответствуют методу вычитания в столбик, где $%W_j$% - т.н. "занимаемые" цифры (разряды).

ссылка

отвечен 7 Сен '13 15:03

Учёл Ваше замечание о пункте 1.2.

(7 Сен '13 19:02) Галактион
10|600 символов нужно символов осталось
0

Судя по всему, это верно. Я проверял так: смысл переменной $%W_j$% -- осуществлён ли "заём" из $%j$%-го разряда. Тогда смотрим, в каком случае не происходит этого "заёма". Если $%X_{j-1}=1$%, то в предпоследней формуле первые два дизъюнктивных члена обнуляются, и всё зависит от последнего. Который равен нулю, если либо вычитается ноль (это $%Y_{j-1}$%), либо вычитается единица, но при этом из данного разряда не было "заёма" (то есть $%W_{j-1}=0$%).

Несколько непонятно только Ваше стремление вводить новые обозначения. Логические связки и без того не имеют единого стандарта обозначения, и если речь идёт об обычной дизъюнкции, то зачем нужен значок $%\oplus'$%? Кроме того, если брать за основу конъюнкцию, обозначая её одним из принятых способов, то отпадает необходимость заново всё описывать.

Вообще-то одна из причин может быть такая: обозначения для логических операций могут "конфликтовать" с обозначениями, которые присутствуют в формулах логики предикатов, которыми Вы пользуетесь на уровне "метаязыка". Но я бы просто описывал всё словами, а не формулами, потому что так понятнее. Здесь ведь вся полезная информация содержится в двух последних формулах, а всё остальное -- это "оболочка".

ссылка

отвечен 7 Сен '13 15:57

  1. Спасибо.

  2. Мне не нравится путать высказывания (например, высказывание "$%0 \oplus' 1 = 1$%" с высказыванием "$%0 \oplus' 0 = 1 \lor 0 \oplus' 0 = 0$%").

(7 Сен '13 18:59) Галактион

Я на это как раз и подумал. Но здесь есть, мне кажется, более удобный выход из положения: операции обозначать "традиционно", а связки между высказываниями -- в виде and, or, not. Тогда всё станет "читабельнее": $%0\vee0=1$% or $%0\vee0=0$%.

(7 Сен '13 20:01) falcao
  1. Я ввел обозначения $%\otimes, \ \oplus$% и $%\oplus'$% потому, что мне понравилась Ваша идея о "наследуемости" арифметических свойств в цепочке $%\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$%.

  2. Я не сомневаюсь, что арифметические операции + и x на множестве натуральных чисел [нетривиально] наследуют свойства арифметических операций на множестве булевых чисел.

  3. Я не возражаю, чтобы русские и/или украинские математики проявили "политическую волю", а именно договорились об обозначениях для арифметических и логических операций.

(7 Сен '13 20:24) Галактион
  1. Обозначение $%\otimes$% можно заменить обозначением $%\times$%, потому что $%\forall_{(x, y) \in \mathbb{B}^2}\forall_{(u, v) \in \mathbb{N}^2} ((x, y) = (u, v) \rightarrow x \otimes y = u \times v)$%

  2. В алгебре высказываний идут от исходных операций $%\wedge$% (логическое "и"), $%\vee$% (логическое "или"), $%\neg$% (логическое "не") к производной операции $%\veebar$% (логическое бинарное "либо"). В булевой арифметике следует идти от операций $%\otimes$% и $%\oplus$% к операции $%\oplus'$%, т. к. $%\forall_{\{x, y\} \subseteq \mathbb{B}} (x \oplus' y = x \oplus y \oplus (x \otimes y))$%

(7 Сен '13 21:37) Галактион
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×150

задан
7 Сен '13 13:32

показан
830 раз

обновлен
8 Сен '13 8:25

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

по почте:

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

по RSS:

Ответы

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

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