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 ] 

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



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

Сейчас этот форум просматривают: Geen


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

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