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

[photon]

epros в сообщении #1303564 писал(а):

(из-за троеточия).

ОК, а если тогда говорить, что не существует такой пары $(b, N)$, где $b > 1, N >1$, что $a = \sum\limits_{i=1}^N {b}$ - это можно считать формулой арифметики?

[arseniiv]

Введение $\sum$-нотации усложняет язык ещё сильнее, чем введение умножения.

[Qlin]

photon, нельзя.

[photon]

Ну и ладно - нельзя так нельзя.

[Someone]

Chifu в сообщении #1302900 писал(а):

Если уж на то пошло, то на универсальном компьютере все вычисления выполняются через два состояния и логический базис.

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

[Dmitriy40]

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

Кроме логических операций, там ещё используются операции "выделение заданного бита"

Если подразумевается мультиплексор, то он тоже реализуется чисто логической схемой. Как и демультиплексор.

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

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

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

[mihaild]

Тут нужно уточнить, что мы понимаем под "чисто логическими операциями" и скажем "сложением чисел".
Например, сложение $n$-разрядных чисел определим так: на вход два $n$-разрядных числа, на выходе одно $n+1$-разрядное.
Теперь вопрос - что такое "логические операции"? Если побитовые - то так сделать не получится, т.к. они все сохраняют разрядность. Если принимающие на вход $1$ бит - то так не получится, т.к. нужны еще какие-то операции, этот бит из входа выделяющие.

[epros]

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

что такое "логические операции"

Обычно конъюнкция и дизъюнкция (с любым количеством аргументов) и отрицание. Схема $n$-битного сложения на них действительно реализуется довольно просто.

[mihaild]

epros в сообщении #1303877 писал(а):

Обычно конъюнкция и дизъюнкция (с любым количеством аргументов) и отрицание. Схема $n$-битного сложения на них действительно реализуется довольно просто.

Не реализуется: $i$-й бит выхода зависит только от $i$-х битов аргумента, а для сложения это неверно.

[epros]

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

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

$i$-й бит выхода зависит только от $i$-х битов аргумента

Такого условия нет. Биты переноса формируются из других разрядов.

[mihaild]

Так, выше бред написал. Но всё равно, у нас на входе две $n$-битных строки. Чтобы сделать с ними что-то интересное, нужно уметь выделять из них биты, и потом еще склеить выходы в одну строку.
(хотя не очень понимаю, о чем обсуждение; определение булевых схем известно, и спорить о том, есть ли там на "неформальном уровне" что-то кроме логических операций, не очень интересно)

[epros]

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

нужно уметь выделять из них биты, и потом еще склеить выходы в одну строку

Непонятно в чём проблема. "Выделять биты" - это значит, что на входы какого-то $i$-того логического элемента подаются строго какие-то $j$-тые биты слагаемых. А "склеить в строку" означает, что $k$-тый бит суммы берётся с выхода какого-то $l$-того логического элемента. Вообще, это жёстко зашитая схема. После подачи чего-то на входы (в биты слагаемых) получаем что-то на выходе (в битах суммы).

[mihaild]

Ну вот проблема в том, что нам на вход дают что-то из $\mathbb{Z}_2^n$, логические элементы выдают что-то из $\mathbb{Z}_2$, на вход хотят что-то из $\mathbb{Z}_2^k$, а на выходе схемы нам вообще нужно что-то из $\mathbb{Z}_2^{n+1}$. И кроме собственно логических элементов нужно что-то, склеивающее несколько битов в одну строчку, либо наоборот выделяющее определенный бит.

[Ivan_B]

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

На самом деле это ходячее заблуждение.

Реализовать можно абсолютно любую операцию. Хоть корень: у Вас есть $n$ бит, которые являются представлением числа. Вы хотите получить $n$ бит, которые будут представлением корня из этого числа. Далее нужно рассматривать каждый бит результата как функцию всех $n$ бит представления исходного числа. Затем получается $n$ функций, каждую из которых можно записать используя только логические операции (например, записать ДНФ и разложить ее в нужный базис) Другой вопрос, что так никто не будет делать из-за того, что функции будут огромными.
Для извлечения корня скорее будет использован какой-то алгоритм. Но и тут можно обойтись только логическими функциями. Для реализации алгоритма нужно построить автомат, для хранения состояния которого нужна память. Память можно тоже реализовать с использованием только логических функций и бесконечной рекурсии, которая на практике получают соединением выхода со входом. В компьютере все можно реализовать с использованием логических операций, но так делают не всегда из-за существование альтернативных методов достижения того же результата.

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

[Dmitriy40]

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

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

Поясните что это такие за операции "склеивания бит" и "выделения бит"? Да ещё и "в строчку"?
Если выделение постоянно, то оно реализуется тупо проводом (для каждого бита) между триггерами хранения чисел. Если переменно (зависит от каких-то логических сигналов) - реализуется мультиплексором, который тоже состоит только из логических элементов.
Склеивание бит реализуются аналогично, или тупо проводами, или демультиплексором только из логических элементов.
Преобразование числа из $n$ битов в $n+1$ битов реализуется $n$ проводами и подачей на $n+1$ вход логического 0 (провод к выводу питания) для беззнаковых чисел или соединением входа $n+1$ с выходом $n$ для знаковых чисел в дополнительном коде.
Ничего кроме логических элементов (и проводов, и одной константы 0 или 1 без разницы - которую обычно реализуют тупо проводом к выводу питания) не нужно.
PS. Надеюсь Вы не забыли в формулах возможность соединения одного выхода логического элемента со многими входами логических элементов.

Add.
Вообще представление чисел как строк символов или битов или неких математических значений - находится поверх аппаратной реализации. Аппаратно есть лишь логические элементы, провода и константа (0 или 1 без разницы). Всё. Если из логических элементов сформирован некий массив триггеров, то что за числа в нём находятся - лишь соглашение, интерпретация, аппаратно никак не отражённая. Даже в разные моменты времени можно считать что там или одно число, или два, или 100500 (если триггеров достаточное количество). Например положительные числа в дополнительном коде и беззнаковые числа на уровне аппаратуры абсолютно идентичны, неразличимы, мы их можем различить лишь по соглашению/договорённости.
Потому совершенно непонятно что за операции вставки/склейки и выделения битов тут придумали.