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

[Dmitriy40]

Да ведь без композиций не построить (не выразить) почти ни одну функцию, не входящую в базис. Пример: в базисе $\neg\wedge$ (И-НЕ) без композиций невыразимы ни $\wedge$, ни $\vee$, ни $\neg\vee$ (ИЛИ-НЕ), ни $\oplus$, ни любая функция трёх и более аргументов. Ровно как и в базисе сложений без композиций невыразимо $a+b+c+d$. Ну и зачем оно тогда?!

[Someone]

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

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

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

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

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

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

-- Вс апр 15, 2018 11:17:01 --

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

Да ведь без композиций не построить (не выразить) почти ни одну функцию, не входящую в базис.

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

[Dmitriy40]

Согласен, святое. Но вот именно она, композиция, и выделяет единственный сигнал из множества аналогичных (один бит из кучи).
Ну и мне так и непонятно почему определив операцию над (битовым) вектором как единым объектом Вы исключаете операции над (произвольными) элементами вектора. Да, можно к примеру умножение матриц использовать строго как операцию над матрицами, но можно ведь и расписать в терминах операций над элементами матриц. Т.е. операцию над вектором выразить через операции над элементами вектора.

[arseniiv]

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

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

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

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

Это хорошо, но как это меняет, что булевы функции определяются как операции именно на $\mathbb Z_2^1$? По крайней мере, в контексте выразимости одной булевой функции через набор других я видел всегда только это.

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

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

Почему, нет. Это делают проекции. Хотя они тоже автоматически входят.

[Dmitriy40]

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

Почему, нет. Это делают проекции. Хотя они тоже автоматически входят.

Спасибо, я очевидно не силён в теории, потому ошибаюсь с терминами и рассуждаю в конкретике.

[Someone]

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

операции именно на $\mathbb Z_2^1$

Почему именно $\mathbb Z_2$? Кто мешает рассмотреть, например, булеву алгебру открыто-замкнутых множеств какого-нибудь нульмерного компакта? Например, канторова совершенного множества. И зачем вообще привязываться к конкретной булевой алгебре? Интересно доказать в общем виде, что ни в какой булевой алгебре невозможно смоделировать сколько-нибудь существенный отрезок натурального ряда. Я выше объяснял, как это сделать. А в $\mathbb Z_2$ тем более невозможно смоделировать сложение.

Да, кстати. Если Вы думаете, что $\mathbb Z_2$ — единственная булева алгебра, которая встречается в математической логике, то ошибаетесь. Например, если задана формальная теория, то определяется булева алгебра формул этой теории. В общем случае она вовсе не сводится к $\mathbb Z_2$.

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

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

Ну так сложение натуральных чисел — не булева функция.

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

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

Композиция — это последовательное применение операций. Когда результаты выполнения одних операций служат аргументами (операндами) других операций.

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

Это делают проекции. Хотя они тоже автоматически входят.

Проекции не являются логическими операциями. В булевой алгебре нет проекций.

[Dmitriy40]

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

Композиция — это последовательное применение операций. Когда результаты выполнения одних операций служат аргументами (операндами) других операций.

Я этому и не возражал и не менял смысл. Объясните почему недопустима композиция двух операций: $f_1=a_1 \vee (\neg a_3)$ (логическое ИЛИ первого элемента вектора и результата логической операции логическое НЕ третьего элемента вектора)? Где здесь противоречие с булевой алгеброй? Почему она должна быть определена лишь на векторах и при этом неразложима на битовые операции? Только потому что Вы произвольно ограничили множество допустимых аргументов логических операций лишь векторами как едиными неделимыми объектами?
Простите, но в моём понимании это надстройка над булевой алгеброй, её расширение на другие объекты, как умножение матриц надстройка над умножением скалярных переменных.
Сразу прошу прощения за неакадемичность/неформальность терминов.

[arseniiv]

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

Спасибо, я очевидно не силён в теории, потому ошибаюсь с терминами и рассуждаю в конкретике.

Тогда на всякий случай приведу пример, вдруг вам будет интересно. Скажем, выражаем мы эквивалентность через $\neg,\vee,\wedge$: $f(x_1,x_2) = x_1\wedge x_2\vee\neg x_1\wedge\neg x_2$. В безаргументной записи это будет так: $f = {\vee}\circ({\wedge},{\wedge}\circ({\neg}\circ\pi_1^1,{\neg}\circ\pi_2^1))$, где проекции $\pi_m^n(x_1,\ldots,x_n) = x_m$, а композиция $(f\circ(g_1,\ldots,g_n))(\vec x) = f(g_1(\vec x),\ldots,g_n(\vec x))$.

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

Почему именно $\mathbb Z_2$? Кто мешает рассмотреть, например, булеву алгебру открыто-замкнутых множеств какого-нибудь нульмерного компакта? Например, канторова совершенного множества. И зачем вообще привязываться к конкретной булевой алгебре?

Ну, наверно, потому что выразимость булевых функций уже понимают так, как понимают, и с цифровой электроникой принято связывать именно такое. Не знаю. Аргументов лучше у меня нет.

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

Да, кстати. Если Вы думаете, что $\mathbb Z_2$ — единственная булева алгебра, которая встречается в математической логике, то ошибаетесь. Например, если задана формальная теория, то определяется булева алгебра формул этой теории. В общем случае она вовсе не сводится к $\mathbb Z_2$.

Нет, не думаю, эта алгебра мне известна.

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

Ну так сложение натуральных чисел — не булева функция.

Но раз мы говорим о числах, имея радом биекцию $0..(2^n-1)\to\mathbb Z_2^n$, мы можем рассматривать $n$ булевых функций от битов обоих аргументов.

А если взять произвольную бесконечную булеву алгебру $B$, мы в любом случае не сможем сопоставить её элементы натуральным числам как-то красиво.

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

Проекции не являются логическими операциями. В булевой алгебре нет проекций.

Не совсем понял, что утверждается, потому уточню, что я сам имел в виду: понятно, что булева алгебра — это алгебраическая структура с операциями $\wedge,\vee,\neg$ и больше никакими. Но когда обсуждается выразимость (по-моему, вообще любых функций через любые), нельзя обойтись одной только композицией. Иначе говоря, пусть есть множество каких-то базовых функций $\mathcal B$. Определим $\bar{\mathcal B}$ как наименьшее по включению множество, для которого верны условия
(1) $\mathcal B\subset\bar{\mathcal B}$;
(2) если $f,g_1,\ldots,g_n\in\bar{\mathcal B}$ и композиция $h = f\circ(g_1,\ldots,g_n)$ имеет смысл, то $h\in\bar{\mathcal B}$.
Тогда называть $\bar{\mathcal B}$ множеством функций, выразимых с помощью базовых, ещё рано, оно узковато. Выразить импликацию через $\neg,\wedge,\vee$ в таком смысле не получится. Проекции нужны.

[mihaild]

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

Объясните почему недопустима композиция двух операций: $f_1=a_1 \vee (\neg a_3)$

Во-первых, это композиция трех операций: $\vee(get_1(a), get_3(a))$.

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

Почему она должна быть определена лишь на векторах и при этом неразложима на битовые операции?

Потому что это определение булевой алгебры: множество, на котором определены две операции $\vee, \wedge, \neg$ и выделены константы $0,1$ с определенными свойствами.

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

Да, можно к примеру умножение матриц использовать строго как операцию над матрицами, но можно ведь и расписать в терминах операций над элементами матриц.

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

Вообще, я всё еще не понимаю, о чем спор. Есть, например, определение булевых схем - и все согласны, что функция $\mathbb{Z}_2^n \times \mathbb{Z}_2^n \to \mathbb{Z}_2^{n+1}$, вычисляющая сумму аргументов, записанных как двоичные числа, вычисляется некоторой несложной схемой.
Есть определение булевой алгебры, и несложно доказывается, что сложение натуральных чисел ни в каком разумном смысле булевой алгеброй не описывается.

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

Выразить импликацию через $\neg,\wedge,\vee$ в таком смысле не получится.

А что такое импликация на булевой алгебре? Чем стандартное $a\to b = b \vee \neg a$ не устраивает?

[Dmitriy40]

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

Вообще, я всё еще не понимаю, о чем спор.

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

[arseniiv]

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

А что такое импликация на булевой алгебре? Чем стандартное $a\to b = b \vee \neg a$ не устраивает?

Ну, в данном случае импликация конкретно на $\mathbb Z_2$.

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

Чем стандартное $a\to b = b \vee \neg a$ не устраивает?

Устраивает. Я совсем не против определять выразимость этим способом, как существование терма от интересующего набора переменных и символов, соответствующих базовым функциям, но в таком случае как-то не очень хорошо, по-моему, говорить о композициях (терм составляется из подтермов, строго говоря, аппликацией). Или мы говорим о композиции функций в контексте определения $\bar{\mathcal B}$ выше, тогда одних композиций для выражения импликации ${\vee}\circ(\pi^1_2,{\neg}\circ\pi^1_1)$ не хватает (и для других её выражений тоже).

Dmitriy40
Корень (или его часть) проблемы может быть в том, что булева функция оказывается не гомоморфизмом булевых алгебр (как можно было бы хотеть) или, например, операцией на произвольной булевой алгебре, а операцией на конкретной булевой алгебре $\mathbb Z_2$ — куда более узким понятием. (1)

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

* Или расширим определение и будем рассматривать как одну, на вопросах выразимости это никак не скажется, хотя путаницы из-за (1) может добавить.

-- Пн апр 16, 2018 01:11:16 --

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

Вообще, я всё еще не понимаю, о чем спор. Есть, например, определение булевых схем - и все согласны, что функция $\mathbb{Z}_2^n \times \mathbb{Z}_2^n \to \mathbb{Z}_2^{n+1}$, вычисляющая сумму аргументов, записанных как двоичные числа, вычисляется некоторой несложной схемой.
Есть определение булевой алгебры, и несложно доказывается, что сложение натуральных чисел ни в каком разумном смысле булевой алгеброй не описывается.

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

-- Пн апр 16, 2018 01:15:01 --

Непонятно написал.

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

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

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

[Someone]

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

в случае вырожденной булевой алгебры из одного элемента

Нет такой булевой алгебры. По определению требуется существование различных "нуля" и "единицы".

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

и двухэлементной булевой алгебры

Вот она-то как раз и называется вырожденной. (Д. А. Владимиров. Булевы алгебры. "Наука", Москва, 1969. Глава I, § 2.)

[arseniiv]

Ой.

(Я согласен как угодно, но из определения «булева алгебра — это ограниченная дистрибутивная решётка с дополнением» неравенство границ не следует. Кроме того, с таким ограничением булеан пустого множества не будет булевой алгеброй, тогда как булеан любого другого будет, и это как-то неестественно.)

[Someone]

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

Я согласен как угодно, но из определения «булева алгебра — это ограниченная дистрибутивная решётка с дополнением» неравенство границ не следует.

Согласен.

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

Кроме того, с таким ограничением булеан пустого множества не будет булевой алгеброй, тогда как булеан любого другого будет, и это как-то неестественно.

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

[arseniiv]

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