2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Предпочтительное определение функции в курсе логики
Сообщение28.03.2010, 00:52 


31/01/09
96
Москва, мехмат МГУ, МИЭТ
Моя исходная посылка: определения должны быть такими, чтобы их было удобнее использовать; в частности, формулировки теорем должны получаться как можно проще и иметь меньше оговорок. Когда я читал новую книгу Gallier, Discrete Mathematics: Some Notes, я обратил внимание, что он вводит как основное определение частично определённую функцию (то есть функция $f: X \to Y$ у него не обязательно всюду определена на $X$). Что это даёт (например):

1) Большая симметричность.
2) Обратная функция есть у любого вложения, а не только у биекций.
3) $|X| \leq |Y|$ тогда и только тогда, когда есть сюръекция из $Y$ в $X$ (не нужно оговорки, что $X$ непусто).
4) Ближе к функциям в программировании, вычисление которых может зациклиться. В частности, мы можем сказать, что любая чистая (то есть не имеющая побочных эффектов, не обращающаяся к внешнему состоянию и т.д.) функция на языке программирования вычисляет какую-то математическую функцию.
5) Когда дойдём до общерекурсивных функций, не придётся оговариваться, что это не "настоящие" функции, а частично определённые.

Какие есть причины предпочитать традиционное определение? Какие формулировки ухудшаются?

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение29.03.2010, 11:12 
Заслуженный участник


10/08/09
599
Alexey Romanov в сообщении #303420 писал(а):
1) Большая симметричность.

Симметричность дают бинарные отношения. Функции для того и созданы, чтобы быть НЕсимметричными.
Alexey Romanov в сообщении #303420 писал(а):
2) Обратная функция есть у любого вложения, а не только у биекций.

Что вы понимаете под "обратной" функцией? По-моему, функция $g$ является обратной к функции $f$, если как $f\cdot g$, так и $g\cdot f$ являются тождественными функциями. В вашем случае это, очевидно, не так.
Alexey Romanov в сообщении #303420 писал(а):
Ближе к функциям в программировании, вычисление которых может зациклиться.

В программировании как раз гораздо удобнее рассматривать не частично определённые функции, а непрерывные функции из домена в домен. Не нужно волноваться на тему "определена ли функция в этой точке" - да, определена, но её значение может быть равно (_|_). Это означает, что мы по-прежнему можем, например, подставлять это значение в какие-либо формулы, и т.п.
Alexey Romanov в сообщении #303420 писал(а):
Когда дойдём до общерекурсивных функций, не придётся оговариваться, что это не "настоящие" функции, а частично определённые.
Какие есть причины предпочитать традиционное определение? Какие формулировки ухудшаются?

Да почти все. На каждом шагу придётся спотыкаться и оговаривать "всюду определённая".

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение31.03.2010, 08:12 
Экс-модератор


17/06/06
5004
 i  Переношу в вопросы преподавания.
:wink:

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение31.03.2010, 12:40 


31/01/09
96
Москва, мехмат МГУ, МИЭТ

(Оффтоп)

AD в сообщении #304788 писал(а):
 i  Переношу в вопросы преподавания.
:wink:

Спасибо, об этом подфоруме не знал.


-- Ср мар 31, 2010 13:05:32 --

migmit в сообщении #303904 писал(а):
Симметричность дают бинарные отношения. Функции для того и созданы, чтобы быть НЕсимметричными.

Полной симметричности тут и не будет. Но в общем, согласен :-)
migmit в сообщении #303904 писал(а):
Что вы понимаете под "обратной" функцией? По-моему, функция $g$ является обратной к функции $f$, если как $f\cdot g$, так и $g\cdot f$ являются тождественными функциями. В вашем случае это, очевидно, не так.

Да, согласен.
migmit в сообщении #303904 писал(а):
В программировании как раз гораздо удобнее рассматривать не частично определённые функции, а непрерывные функции из домена в домен. Не нужно волноваться на тему "определена ли функция в этой точке" - да, определена, но её значение может быть равно (_|_). Это означает, что мы по-прежнему можем, например, подставлять это значение в какие-либо формулы, и т.п.

В логике это даёт свои проблемы. См., например, свободную логику, "Adapting Calculational Logic to the Undefined", и т.д.
migmit в сообщении #303904 писал(а):
Да почти все. На каждом шагу придётся спотыкаться и оговаривать "всюду определённая".

Вот мне и интересно, насколько "на каждом шагу".

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 09:14 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
На самом деле все эти "спотыкания" есть следствия неудачности русского языка. В англоязычной литературе используют термин "computable function" для вычислимой функции, возможно, не всюду определённой, и термин "total computable function" для всюду определённой вычислимой функции. Английскому языку в этом плане повезло: прилагательное "total" короткое и легко произносится, в отличие от русского "всюду определённая".

Если изучать теорию алгоритмов, то есть темы, где функции, в основном, всюду определены, а есть темы, где они, в основном, частичные. Какую терминологию не задай, в одном из случаев "спотыкания" неизбежны: либо в первой группе тем к каждой функции придётся прибавлять "всюду определённая", либо во второй группе тем придётся всё время говорить "частичная". Выход простой: в начале лекции (главы в книжке) делается заявление: сегодня мы под "функцией" будем понимать всюду определённую/частичную функцию, если термин "функция" будет использоваться в другом смысле, то это будет оговорено отдельно. И дальше шпаришь, не спотыкаясь :-)

P. S. Частичная функция есть всюду определённая функция на своей области определения :-)

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 09:34 
Заслуженный участник


11/05/08
32166
Профессор Снэйп в сообщении #305841 писал(а):
Английскому языку в этом плане повезло: прилагательное "total" короткое и легко произносится, в отличие от русского "всюду определённая".

А почему не заменить слово "total" на, скажем, столь же короткое слово "вполне"? (я не в теме, потому и спрашиваю, сильно не пинайте)

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 10:13 


31/01/09
96
Москва, мехмат МГУ, МИЭТ
ewert в сообщении #305845 писал(а):
А почему не заменить слово "total" на, скажем, столь же короткое слово "вполне"?

То есть вместо "f -- всюду определённая функция из $\mathbb N$ в $\mathbb N$" Вы предлагаете говорить "f -- вполне функция из $\mathbb N$ в $\mathbb N$"? Хм. А вот "f -- полная функция из $\mathbb N$ в $\mathbb N$" звучит, по-моему, прилично.

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 10:30 
Заслуженный участник


11/05/08
32166
Там совсем не та пара.

Речь шла о том, что "computable function" -- это, дескать, "вычислимая функция".

Ну а тогда "total computable function" -- это... ну, допустим, "вполне вычислимая функция", почему бы и нет?...

Ну или, скажем, "абсолютно вычислимая функция" (я просто перебираю возможные более-менее синонимы к слову "total").

(если, конечно, эти термины ещё не заняты; я просто не в курсе)

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 11:47 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
В данном контексте, наверное, можно говорить "всюду вычислимая функция".

Вообще все эти вопросы, касающиеся терминологии, слегка надуманы :?

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 12:10 
Заслуженный участник


09/08/09
3438
С.Петербург
Профессор Снэйп в сообщении #305879 писал(а):
В данном контексте, наверное, можно говорить "всюду вычислимая функция".
+1
В английском языке в названии total computable function прилагательное total относится, скорее, к function, чем к computable. Другими словами, дословный перевод -- "всюду определенная вычислимая функция".

(Оффтоп)

Забавнее получилось при переводе с английского с обще-рекурсивными и частично-рекурсивными функциями. В оригинале они называются "general recursive function" (общая рекурсивная функция) и "partial recursive function" (частичная рекурсивная функция). Каким образом при переводе прилагательные "общая" (всюду определенная) и "частичная" (не всюду определенная) отклеились от слова "функция" и приклеились к слову "рекурсивная" остается загадкой. В результате некоторых (*смотрится в зеркало*) долгое время мучил вопрос: чем частичная рекурсия отличается от общей.

 Профиль  
                  
 
 Re: Предпочтительное определение функции в курсе логики
Сообщение03.04.2010, 12:14 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Maslov в сообщении #305889 писал(а):
В английском языке в названии total computable function прилагательное total относится, скорее, к function, чем к computable. Другими словами, дословный перевод -- "всюду определенная вычислимая функция".

В точности так. "Total function" --- всюду определённая функция.

Maslov в сообщении #305889 писал(а):
Забавнее получилось при переводе с английского с обще-рекурсивными и частично-рекурсивными функциями. В оригинале они называются "general recursive function" (общая рекурсивная функция) и "partial recursive function" (частичная рекурсивная функция). Каким образом при переводе прилагательные "общая" (всюду определенная) и "частичная" (не всюду определенная) отклеились от слова "функция" и приклеились к слову "рекурсивная" остается загадкой. В результате некоторых (*смотрится в зеркало*) долгое время мучил вопрос: чем частичная рекурсия отличается от общей.

Ага! А ещё сейчас многие студенты не понимают разницы между "рекурсивной функцией" и "общерекурсивной функцией". К сожалению, в некоторых учебниках эти вещи перепутаны :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

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



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

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


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

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