Сложение и другие арифметические операции

[mihaild]

Ну вот эти "тупо провода" - это и есть выделяющие элементы. Важно, что функций $\bigvee_n, \bigwedge_n: \mathbb{Z}_2^n \to \matbb{Z}_2$ и $\neg: \mathbb{Z}_2 \to \mathbb{Z}_2$ нам недостаточно.

[Dmitriy40]

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

[arseniiv]

Возьмём, допустим, однобитный сумматор с тремя входами $A,B,C$ и выходами $S',C'$ ($C'$ — перенос в старший разряд, $C$ — перенос из предыдущего). Он реализуется как $S = A\oplus B\oplus C, C' = A\wedge B\vee A\wedge C\vee B\wedge C$. Пока проблем никаких нет. Скомпонуем теперь несколько таких сумматоров $(S,C') = s(A,B,C)$: пусть есть входы $A_1,B_1,\ldots,A_n,B_n$ и выходы $S_1,\ldots,S_n,C_{n+1}$, и пусть $(S_i,C_{i+1}) = s(A_i,B_i,C_i)$, где $C_1 = 0$. Каждый из выходов всё так же остаётся выразим булевой функцией входов, как можно убедиться подстановками.

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

[beroal]

Извините, но цифровая электроника к теме совсем не относится.

[Someone]

Я уточняю. Логические операции — это операции на некоторой булевой алгебре. Причём, не какие угодно, какие можно придумать, а вполне определённые: дизъюнкция, конъюнкция, отрицание (и всё, что через них можно определить).
Поэтому берём булеву алгебру $\mathbb Z_2^n$ со стандартными поразрядными логическими операциями и пытаемся реализовать прибавление единицы. Мне одному кажется очевидным, что, располагая только поразрядными операциями, нельзя реализовать перенос в другой разряд?

Более общая постановка. Имеется абстрактная булева алгебра. Можно ли вложить в неё модель натурального ряда так, чтобы операция прибавления единицы выражалась через операции в булевой алгебре? Наводящий вопрос: сколько элементов содержит булева алгебра с двумя образующими?

[Dmitriy40]

Someone
Простите, а может ли произвольная логическая функция $F_i, i \in 1..n$ зависеть не только исключительно от $i$-х аргументов, но и от каких-нибудь ещё (например $i-1, i+1, 2i$)? Если нет и конструкции типа $F_i=A_i \vee B_{i-1}$ недопустимы из-за несовпадения индексов, то да, засада. Только почему не может то?
А если может, то перенос получается по вышеприведённой формуле: $C_i=A_i \wedge B_i \vee (A_i \vee B_i) \wedge C_{i-1}, C_0=0, i=1..n$. Для любого конечного $n$ её можно расписать и без индексов, просто получится очень длинно. Но ничего кроме логических функций ($\wedge, \vee$) не понадобится.

[Someone]

Dmitriy40 в сообщении #1304013 писал(а):

Простите, а может ли произвольная логическая функция $F_i, i \in 1..n$ зависеть не только исключительно от $i$-х аргументов, но и от каких-нибудь ещё (например $i-1, i+1, 2i$)? Если нет и конструкции типа $F_i=A_i \vee B_{i-1}$ недопустимы из-за несовпадения индексов, то да, засада. Только почему не может то?

Никогда не видел логических команд, которые были бы не поразрядными. Для реализации сумматора нужен доступ к отдельным разрядам и возможность их комбинировать достаточно нетривиальным образом.

Рассмотрите абстрактную постановку, в которой никакие разряды вообще не упоминаются.

[Dmitriy40]

Даже распишу, вместе с суммами, для $n=3$:
$C_1=A_1 \wedge B_1$, $S_1=A_1 \oplus B_1$
$C_2=A_2 \wedge B_2 \vee (A_2 \vee B_2) \wedge (A_1 \wedge B_1)$, $S_2=A_2 \oplus B_2 \oplus (A_1 \wedge B_1)$
$C_3=A_3 \wedge B_3 \vee (A_3 \vee B_3) \wedge (A_2 \wedge B_2 \vee (A_2 \vee B_2) \wedge (A_1 \wedge B_1))$, $S_3=A_3 \oplus B_3 \oplus (A_2 \wedge B_2 \vee (A_2 \vee B_2) \wedge (A_1 \wedge B_1))$
И так далее (надеюсь не опечатался). Не вижу никакой проблемы в выражении ни переносов, ни сумм.

Someone в сообщении #1304019 писал(а):

Никогда не видел логических команд, которые были бы не поразрядными.

Логические команды очевидным образом не привязаны к разрядам, они могут зависеть от любых имеющихся переменных (например разрядов чисел). Тогда уж и перемножение матриц запрещайте, там ведь тоже в результирующей матрице индексы матриц аргументов вперемешку. Впечатление что и Вы и другие путаете понятия разряда числа и понятие бита (битовой переменной). И я не понимаю что мешает задавать логические функции на всём имеющемся множестве переменных, вне зависимости к каким числам или разрядам они относятся. И почему Вы насильно хотите ограничить например сложение векторов только и исключительно покомпонентным сложением, без перекрёстных зависимостей между компонентами с разными индексами (да, это не будет сложением векторов, но это будет допустимой математической операцией, в частности логической).
Насчёт абстрактной постановки это не ко мне. Возьмите три вектора $A, B, C$ одинакового размера $n$ и определите на них операцию $C_i=A_i \vee B_i \wedge B_{i-1}, B_0=1, i=1..n$. Это по Вашему не логическая операция? А по моему вполне себе логическая операция.

[arseniiv]

Someone в сообщении #1304005 писал(а):

Я уточняю. Логические операции — это операции на некоторой булевой алгебре. Причём, не какие угодно, какие можно придумать, а вполне определённые: дизъюнкция, конъюнкция, отрицание (и всё, что через них можно определить).
Поэтому берём булеву алгебру $\mathbb Z_2^n$ со стандартными поразрядными логическими операциями и пытаемся реализовать прибавление единицы. Мне одному кажется очевидным, что, располагая только поразрядными операциями, нельзя реализовать перенос в другой разряд?

С такой постановкой не одному вам, но почему брать такую постановку? Операции отдельными байтами вполне встречаются в процессорах — часто используются флаговые регистры, отдельные биты которых устанавливаются при вычислениях и могут быть проверены выполнением какой-то инструкции. Остаётся только растащить элементы $\mathbb Z_2^n$ на отдельные биты и рассматривать функции от них.

Это может выглядеть малоосмысленно, но рассматривать булевы функции такой сложности в разработке электроники, кажется, в любом случае бесполезно — там уже и задержка начинает сказываться, и прочие физические нюансы типа взаимовлияния компонентов. Так что слова о выразимости остаются большей частью достоянием теории — есть она и есть, а пользы даёт немного, если сравнить с гипотетическим вариантом, когда её бы не было.

(Моё дилетантское понимание, процессоров не делал.)

[Dmitriy40]

Так, я извиняюсь, кажется дошло в чём путаница.
Есть логический базис (к примеру И-НЕ), есть порязрядные логические операции (которые именно что не зависят от других разрядов в отличии от произвольной логической функции) и есть реализуемость произвольной логической функции в логическом базисе. Поразрядные логические операции так и называются потому что не зависят от прочих разрядов. И в них разумеется переносы не выражаются. Но это узкое подмножество всех логических операций! Тем не менее любые логические функции полностью описываются в терминах логического базиса.
А изначально про поразрядность речи не было, сказано было просто "логические функции", не ограничивая их только поразрядными. Соответственно и утверждения mihaild там дальше тоже неверны, т.к. под произвольными логическими функциями неявно подразумевались лишь исключительно поразрядные.

[arseniiv]

Да, поразрядные булевы операции, имеющиеся часто в процессорах, не должны быть связаны с упоминаемой выразимостью. Зачем им?

Вообще в длине этого обсуждения очевидно виноват начавший его Chifu, невнятно описавший утверждение. Я как раз следующим постом тогда и намекнул на это, но вышло что вышло, и, самое главное, без малейшего его участия. Зачем опровергать в деталях смутно сформулированные предложения, честно говоря, не знаю — не лучше ли подождать, захочет ли их автор их очертить яснее, или стоит лучше воспринимать пост как мысли вслух.

[Someone]

Dmitriy40 в сообщении #1304023 писал(а):

но это будет допустимой математической операцией, в частности логической

Ещё раз: рассмотрите абстрактную постановку задачи, в которой никакие разряды вообще не упоминаются:

Someone в сообщении #1304005 писал(а):

Имеется абстрактная булева алгебра. Можно ли вложить в неё модель натурального ряда так, чтобы операция прибавления единицы выражалась через операции в булевой алгебре? Наводящий вопрос: сколько элементов содержит булева алгебра с двумя образующими?

Предположим, что мы каким-то образом вложили начальный отрезок натурального ряда из $M$ элементов в булеву алгебру так, что в пределах этого отрезка сумма $a+b$ выражается какой-то логической функцией $f(a,b)$, определяемой, естественно, через логические операции $\vee$, $\wedge$, $\neg$. Пусть натуральным числам $0$ и $1$ соответствуют элементы булевой алгебры $o$ и $e$. Тогда все элементы $a_0=o$, $a_1=f(a_0,e)$, $a_2=f(a_1,e)$, $a_3=f(a_2,e)$,… принадлежат булевой подалгебре, порождённой двумя элементами $o$ и $e$, и, следовательно, весь наш отрезок натурального ряда вложен в эту подалгебру.

arseniiv в сообщении #1304026 писал(а):

С такой постановкой не одному вам, но почему брать такую постановку? Операции отдельными байтами вполне встречаются в процессорах — часто используются флаговые регистры, отдельные биты которых устанавливаются при вычислениях и могут быть проверены выполнением какой-то инструкции. Остаётся только растащить элементы $\mathbb Z_2^n$ на отдельные биты и рассматривать функции от них.

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

[Dmitriy40]

Someone в сообщении #1304032 писал(а):

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

Простите, а что вообще есть в булевой алгебре кроме битов и логических операций? И почему нельзя более сложные вещи формально преобразовать к этим типам (битам и логическим операциям над битами)? Откуда в булевой алгебре вылезает понятие разрядности или неэквивалентности битов между собой? Я как бы считал что в логическую функцию можно включить любой из имеющихся битов, вне зависимости кому и чему он якобы "принадлежит". Или в булевой алгебре и битов нету?
Ну или по другому, мне казалось в булевой алгебре задаются правила преобразования вектора состояния из начального (предыдущего) состояние в следующее (конечное). А вектор состояния - просто упорядоченная куча битов, вектор, массив. И на числа или разряды он делится лишь нами при интерпретации хранящейся в нём информации, но никоим образом не правилами самой булевой алгебры. Соответственно любая логическая функция может использовать в аргументе любой бит из этого вектора состояния. Почему нет то?!
Да, я не понимаю почему запись "$...=A_2$" означает какую-то "операцию выбора бита", а запись "$C_3=...$" какую-то "операцию вставки бита". По моему это просто запись аргумента и результата логической операции.

[arseniiv]

Someone
Но зачем рассматривать именно булеву алгебру $\mathbb Z_2^n$ для $n\ne1$? Кто к этому принуждает?

-- Сб апр 14, 2018 02:28:08 --

Dmitriy40 в сообщении #1304040 писал(а):

Простите, а что вообще есть в булевой алгебре кроме битов и логических операций?

Ну, формально, алгебра с носителем из двух элементов не самая главная из всех булевых. Просто так вышло, что в практических кругах лишь о ней известно, что она булева, а про остальные не задумываются. На самом же деле возможны даже булевы алгебры, не изоморфные никакой степени $(\mathbb Z_2)^A$ для произвольного множества $A$. Впрочем, эти-то в нашем контексте совсем не у дел, как и остальные бесконечные.

Хотя, кстати, булевы функции вроде бы определяются всё равно только как функции $\mathbb Z_2^n\to\mathbb Z_2$.

[mihaild]

mihaild в сообщении #1303874 писал(а):

Тут нужно уточнить, что мы понимаем под "чисто логическими операциями"

Можно рассматривать булеву алгебру (как решётку с дополнительной операцией $\neg$). Что и предлагает Someone.
Можно взять стандартные логические функции и разрешить устраивать их композицию, и считать что либо на вход нам подается просто $2n$ аргументов, задающих биты, и мы просто объявляем, что некоторые из результатов функций идут на выход, либо что у нас дополнительно есть функции, выделяющие из $n$-битной строки определенные биты, и у нас есть функция, которая из $n$ бит делает одну $n$-битовую строку - и из всего этого можно просто явно выразить функцию из пары $n$-битных строк в $n+1$-битную.

Это неинтересные технические вопросы, но нужно всё же зафиксировать определения прежде чем что-то обсуждать.
(при условии, что тут вообще нужно что-то обсуждать, в чем я сомневаюсь)