Кроссворд (математическая логика, теория алгоритмов)

[Heart-Shaped Glasses]

Хочу поделиться с форумчанами кроссвордом, составленным старостой моей группы и преподавателем, который вёл у нас дисциплины "Математическая логика" и "Теория алгоритмов". Думаю, многим будет интересно и приятно его решить (как это было мне). Если кто-то хочет распечатать, то вот ссылка на прямое скачивание файла.



По горизонтали 1. Множество, состоящее из предикатных символов, функциональных символов и предметных констант. 8. Повествовательное предложение, которое однозначно характеризуется как истинное или ложное. 10. Характеристика систем правил заключения, при которой каждое из правил этой системы не является производным правилом в системе, полученной удалением этого правила из списка всех правил системы. 12. Имя Тьюринга. 13. Отображение непустого множества во множество $\{\text{И, Л}\}$. 15. Язык, с помощью которого происходит изучение языка-объекта и на котором формулируются и доказываются утверждения об этом языке-объекте. 16. Если каждому элементу непустого множества $A$ определённым образом поставлен в соответствие единственный элемент непустого множества $B$, то говорят, что задана ____. 18. Откуда по правилу удаления отрицания следует «всё, что угодно». 22. К доказательству её непротиворечивости сводится непротиворечивость всех разделов математики. 27. Высказывание вида «$A$ и $B$». 31. Отображение множества $A$ во множество $B$, при котором различные элементы множества $B$ имеют различные образы в B. 32. Американский математик и логик, доказавший теорему о несуществовании алгоритма, позволяющего по любой формуле языка чистой логики предикатов выяснить, является ли она общезначимой. 35. Как называются следующие конструкции математического языка: $\pi$, $x+5$? 36. Черта алгоритма, при которой исходными данными, промежуточными и окончательными результатами могут служить только конечные объекты, которые потенциально могут быть целиком и полностью построены, а также закодированы с помощью конечного числа символов в виде слов в некотором алфавите. 38. Слово вида $a_iq_j \rightarrow a_s\text{Д}q_t$, где $a_i, a_s$ – буквы алфавита машины, $q_j, q_t$ – состояния машины ($j\neq0$), а $\text{Д}\in\{\text{Л, П, Н}\}$. 39. Так называются законы логики $A\&A\equiv A$ и $A\vee A\equiv A$. 41. Немецкий математик, который разработал программу по спасению математики, в частности теории множеств, после открытия парадоксов. 42. Слово, состоящее из единиц (палок). 43. Выражение, не содержащее переменных. 45. Содержательный смысл первой аксиомы формальной арифметики (Ar1) $x_1=x_2\supset (x_1=x_3\supset x_2=x_3)$. 47. Правило, схема заключений, сохраняющая отношение выводимости в системе естественного вывода. 48. Свойство формальной теории обладать алгоритмом, позволяющим определить по данной формуле, выводима она из множества аксиом данной теории или нет.

По вертикали 2. Исходное утверждение математической теории. 3. Формула, принимающая значение «истина» при любом истинностном значении входящих в неё пропозициональных переменных. 4. Логик, доказавший непротиворечивость арифметики. 5. Утверждение, имеющее доказательство в рамках рассматриваемой теории. 6. Отображение множества $A$ в множество $B$, при котором для любого элемента множества $B$ существует прообраз из множества $A$. 7. Высказывание вида «$A$ или $B$». 9. Предположение, выдвигаемое для решения конкретной задачи. 11. Отношение, которое можно трактовать как взаимную заменяемость объектов. 14. Точное предписание, задающее некоторый вычислительный процесс, начинающийся с произвольных исходных данных из некоторой фиксированной совокупности (возможных исходных данных) и направленный на получение искомого результата, полностью определяемого этими исходными данными. 17. Раздел логики, изучающий значение слов формального языка; иначе говоря, раздел логики, изучающий интерпретации формальных языков. 19. Обоснование истинности суждения по правилам логики. 20. Характеристика системы естественного вывода, которая заключается в существовании формулы, выводимой в данной системе вместе со своим отрицанием. 21. Задаётся алфавитом (исходными символами) и правилами построения осмысленных выражений - формул. 23. Свойство бинарного отношения на множестве, при котором каждый элемент этого множества находится в данном отношении с самим собой. 24. Формулы, принимающие одинаковые истинностные значения при любых значениях входящих в них переменных. 25. (В ЯЛВ) Алгебраическая система, содержащая непустое множество, бинарные и унарную операции на этом множестве и некоторый элемент этого множества. 26. Свойство отношения $\rho$, при котором для любых множеств формул $\text{Г}$ и$\text{Г'}$ и любой формулы $F$, таких что $\text{Г}\rho F$ и $\text{Г}\subseteq \text{Г'}$, выполняется $\text{Г'}\rho F$. 28. Совокупность философских и математических взглядов, при которых отвергаются, например, абстракция актуальной бесконечности и аксиома выбора. 29. Древнегреческий мыслитель, основатель логики; сформулировал важное правило логического вывода - modus ponens. 30. Характеристика множества, обобщающая понятие количества элементов этого множества. 33. Осмысленная конструкция языка логики предикатов 34. Сюръекция множества натуральных чисел на непустое множество. 37. В математической логике – описание и изучение формальной аксиоматической теории как чисто знаковой системы. 40. Итальянский математик, известный как автор системы аксиом неформальной арифметики. 44. Мощность множества всех трансцендентных чисел. 46. Отображение множества всех пропозициональных переменных во множество $\{\text{И, Л}\}$.