2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 О соотношении математики и CS
Сообщение20.01.2017, 21:53 


11/08/16

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


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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 22:41 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 23:20 
Заслуженный участник
Аватара пользователя


19/12/10
1546
knizhnik в сообщении #1186229 писал(а):
Поправьте меня, если полные системы применяются где-то еще.

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 23:55 


11/08/16

312
whitefox в сообщении #1186244 писал(а):
Полные базисы в теории булевых функций.
А теория булевых функций где?

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 02:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
knizhnik в сообщении #1186250 писал(а):
А теория булевых функций где?

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 10:12 


11/08/16

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 11:55 
Заслуженный участник
Аватара пользователя


19/12/10
1546

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

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 13:50 


11/08/16

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 17:35 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
knizhnik в сообщении #1186325 писал(а):
А все остальное - это computer science.
Так теоретическая computer science это ж ветвь математики. Или наоборот... :roll:

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 11:10 
Заслуженный участник
Аватара пользователя


19/12/10
1546
knizhnik в сообщении #1186325 писал(а):
А все остальное - это computer science.
Правильно ли я понял, что с Вашей точки зрения теория функций над полем $\mathbb{R}$ это математика, а теория функций над полем $\mathbb{F}_2$ уже нет?

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 12:38 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
whitefox в сообщении #1186489 писал(а):
Правильно ли я понял…
Просто в
knizhnik в сообщении #1186325 писал(а):
computer science
столько математики, что саму
knizhnik в сообщении #1186325 писал(а):
computer science
надо искать с микроскопом, поэтому человек и воображает, что математика — это не математика, а
knizhnik в сообщении #1186325 писал(а):
все остальное.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 13:01 
Заслуженный участник
Аватара пользователя


06/10/08
6422
knizhnik в сообщении #1186325 писал(а):
Понятно. То есть как я и предполагал, математического содержания этой "науки" хватает лишь настолько, чтобы изобретать новые бесполезные аксиоматизации ИВ. А все остальное - это computer science.
Если хотите более математическое изложение, то есть книга D. Lau "Function Algebras on Finite Sets".

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 15:26 


11/08/16

312
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.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 16:24 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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}$ и свойств умножения получаем, что обе функции единичные. Откуда следует необратимость всех прочих функций.
А мы ни над каким базовым полем не получим поля, только кольцо.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 18:07 
Заслуженный участник
Аватара пользователя


19/12/10
1546
knizhnik в сообщении #1186556 писал(а):
whitefox в сообщении #1186489 писал(а):
Правильно ли я понял, что с Вашей точки зрения теория функций над полем $\mathbb{R}$ это математика, а теория функций над полем $\mathbb{F}_2$ уже нет?
Нет, неправильно.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group