О соотношении математики и CS

[knizhnik]

Deggial: оффтоп выделен из этой темы

Да, я так и понял сразу, что это просто случайность.

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

Кстати, можно аксиоматизировать логику высказываний одной аксиомой

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

[arseniiv]

(Оффтоп)

Ну, мало ли. Одного интереса, насколько минимальными средствами можно обойтись, недостаточно?

[whitefox]

knizhnik в сообщении #1186229 писал(а):

Поправьте меня, если полные системы применяются где-то еще.

Полные базисы в теории булевых функций. Также используются и неполные базисы, например $\vee$ и $\wedge,$ составляют базис монотонных функций.

[knizhnik]

whitefox в сообщении #1186244 писал(а):

Полные базисы в теории булевых функций.

А теория булевых функций где?

[whitefox]

knizhnik в сообщении #1186250 писал(а):

А теория булевых функций где?

Полагаете, что теория булевых функций принадлежит исчислению высказываний? Если да, то как это согласуется с Вашим утверждением:

knizhnik в сообщении #1186223 писал(а):

в исчислении высказываний нетавтологий нет

?

[knizhnik]

whitefox, нет, я интересуюсь, где в математике применяется теория булевых функций.

[whitefox]

• В дискретной математике, например, Яблонский С.В. Введение в дискретную математику.
• В теории сложности вычислений, например, Д. Севидж Сложность вычислений.
• В теории кодирования, например, Логачёв О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии.

Не говоря уже о повсеместном практическом применении — вся современная цифровая техника создана не без их участия.

PS В 4-ом томе Искусства программирования. Д. Кнута есть интересный раздел о булевых функциях.

[knizhnik]

Понятно. То есть как я и предполагал, математического содержания этой "науки" хватает лишь настолько, чтобы изобретать новые бесполезные аксиоматизации ИВ. А все остальное - это computer science.

[Nemiroff]

knizhnik в сообщении #1186325 писал(а):

А все остальное - это computer science.

Так теоретическая computer science это ж ветвь математики. Или наоборот...

[whitefox]

knizhnik в сообщении #1186325 писал(а):

А все остальное - это computer science.

Правильно ли я понял, что с Вашей точки зрения теория функций над полем $\mathbb{R}$ это математика, а теория функций над полем $\mathbb{F}_2$ уже нет?

А что с функциями над другими конечными полями? И, вообще, с функциями над полями ненулевой характеристики? Где именно проходит грань между математикой и не математикой?

[Someone]

whitefox в сообщении #1186489 писал(а):

Правильно ли я понял…

Просто в

knizhnik в сообщении #1186325 писал(а):

computer science

столько математики, что саму

knizhnik в сообщении #1186325 писал(а):

computer science

надо искать с микроскопом, поэтому человек и воображает, что математика — это не математика, а

knizhnik в сообщении #1186325 писал(а):

все остальное.

[Xaositect]

knizhnik в сообщении #1186325 писал(а):

Понятно. То есть как я и предполагал, математического содержания этой "науки" хватает лишь настолько, чтобы изобретать новые бесполезные аксиоматизации ИВ. А все остальное - это computer science.

Если хотите более математическое изложение, то есть книга D. Lau "Function Algebras on Finite Sets".

[knizhnik]

Xaositect, спасибо за книгу. Это похоже на довольно мощный учебник по комбинаторике. Правда он имеет слабое отношение к тому, о чем говорит whitefox.

whitefox в сообщении #1186489 писал(а):

Правильно ли я понял, что с Вашей точки зрения теория функций над полем $\mathbb{R}$ это математика, а теория функций над полем $\mathbb{F}_2$ уже нет?

Нет, неправильно. Но система функций над полем $\mathbb{F}_2$ - это вообще нечто странное и неприятное. В частности, если речь только о функциях одной определенной арности, то с естественно заданными операциями мы не получаем поля. Из равенства $f(x_1, \ldots , x_n) \wedge f^{-1}(x_1, \ldots , x_n)=\mathbf{1}$ и свойств умножения получаем, что обе функции единичные. Откуда следует необратимость всех прочих функций.

whitefox в сообщении #1186489 писал(а):

А что с функциями над другими конечными полями?

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

whitefox в сообщении #1186489 писал(а):

И, вообще, с функциями над полями ненулевой характеристики?

А здесь все еще хуже. Ведь раньше мы имели дело только с конечными полями и операциями. Значит можно было просчитать все операции на компьютере или поручить ручную проверку алгебраических свойств системы каким-нибудь computer_scientist_ам. Для бесконечных (да к тому же несчетных) систем такой подход уже не сработает.

whitefox в сообщении #1186489 писал(а):

Где именно проходит грань между математикой и не математикой?

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

[Xaositect]

knizhnik в сообщении #1186556 писал(а):

Xaositect, спасибо за книгу. Это похоже на довольно мощный учебник по комбинаторике. Правда он имеет слабое отношение к тому, о чем говорит whitefox.

От мэйнстримной комбинаторики это далеко. Это прямое развитие идей о системах булевых функций на конечные множества - если система неполная, то она порождает какой-то клон, эти клоны, как говорит нам алгебра, образуют решетку. А дальше идет рассмотрение этих клонов и этой решетки. В библиографии можно увидеть кучу ссылок на советских кибернетиков (то бишь computer science).

knizhnik в сообщении #1186556 писал(а):

Нет, неправильно. Но система функций над полем $\mathbb{F}_2$ - это вообще нечто странное и неприятное. В частности, если речь только о функциях одной определенной арности, то с естественно заданными операциями мы не получаем поля. Из равенства $f(x_1, \ldots , x_n) \wedge f^{-1}(x_1, \ldots , x_n)=\mathbf{1}$ и свойств умножения получаем, что обе функции единичные. Откуда следует необратимость всех прочих функций.

А мы ни над каким базовым полем не получим поля, только кольцо.

[whitefox]

knizhnik в сообщении #1186556 писал(а):

whitefox в сообщении #1186489 писал(а):

Правильно ли я понял, что с Вашей точки зрения теория функций над полем $\mathbb{R}$ это математика, а теория функций над полем $\mathbb{F}_2$ уже нет?

Нет, неправильно.

То есть теория булевых функций это, всё-таки, математика. Ну и славно.