при чтении книги по теории схем программ возникают вопросы

[IHmG]

кажется не очень понимаю текст в книге

в главе, которая обозначена как краткое математическое предисловие есть раздел функции и графы и там текст

Введем некоторые соглашения об обозначениях элементов теории множеств и логики...

Декартовым произведением A_1$\times$A_2$\times$... $\times$ A_n множеств $A_1, A_2,... A_n$ называется множество {$(a_1,a_2,...a_n)|a_1\in A_1, a_2\in A_2 ..., a_n\in A_n $}, а $A^n$ обозначает A_1$\times$A_2$\times$... $\times$ A_n (n раз)

Произведение и пересечение множеств это ведь одно и тоже понятие? грубо говоря если на графике изобразить $y=2$ и $y = 4$ и смотреть фигуры которые под графиком... то декартовым произведением будет фигура, ограниченная y=2... или например если в треугольник вписать окружность ... то именно окружность и будет декартовым произведением множеств точек ... я правильно понимаю?

Функцией, отображающей множество X во множество Y (обозначение F:X->Y), называется множество F $\subseteq X \times Y$ такое, что для любых пар $(x,y) \in F$ и $(x' y') \in F$ из $x=x'$ следует, что $y=y'$

Что означает символ $\subseteq$ ? и зачем там декартово произведение множеств X и Y?

[Xaositect]

IHmG в сообщении #1028060 писал(а):

Произведение и пересечение множеств это ведь одно и тоже понятие?

Нет. Произведение, как там написано - это множество наборов. Например, если взять отрезки $[0,1]$ и $[0,2]$, то их произведением будет множество пар $\{(x, y) | x\in [0,1], y\in [0,2]\}$, то есть прямоугольник с вершинами $(0,0)$, $(1,0)$, $(0,2)$, $(1,2)$.

IHmG в сообщении #1028060 писал(а):

Что означает символ $\subseteq$ ?

Подмножество.

IHmG в сообщении #1028060 писал(а):

и зачем там декартово произведение множеств X и Y?

Чтобы функция была множеством пар.

Настоятельно рекомендую Вам для начала разобраться с языком теории множеств, например, по брошюрке Верещагин, Шень "Начала теории множеств" (есть тут: http://www.mccme.ru/free-books/), разделы 1.1-1.4, 1.7, 2.1, остальное по желанию.

[ИСН]

Книга с тем же успехом могла быть об управлении полётом драконов; очень ли это важная информация?
Произведение и пересечение - это одно понятие в другой сказке; вернее, там пересечение было матерью произведения, которая родила его, а потом съела. В этой сказке они понятия совершенно разные. Математика состоит из таких сказок. Понятий миллион, слов не хватает. Слова используются по несколько раз. Надо всегда помнить, в какой сказке находишься.

[IHmG]

Xaositect в сообщении #1028064 писал(а):

Настоятельно рекомендую Вам для начала разобраться с языком теории множеств, например, по брошюрке Верещагин, Шень "Начала теории множеств" (есть тут: http://www.mccme.ru/free-books/), разделы 1.1-1.4, 1.7, 2.1, остальное по желанию.

Спасибо, книжку начал смотреть... пока дошел до понятия симметрической разности ... она точно уйдет в закладки + в распечатку, чтобы в транспорте с карандашом читать... помню, что язык этот не понимал в том числе когда пытался читать теорию по матану у Кудрявцев ... как в предисловии кстати и сказано ;)

Пока задача стоит понять теориюпо др предмету и к сожалению просто времени на всю заслуживающую внимание математику нет... учусь заочно, сам подошел к преподавателю и он посоветовал книжку, которую сейчас и пытаюсь читать... но сильно вязну. Пока прочтение с целью бегло ознакомиться с содержанием. Эта книжка сама по себе дополнительный материал, никто в группе его не изучает :) Брошюрка Верещагина - отличный справочник для чтения параграфа, спасибо огромное :) Кстати, понял, что симовол обозначает не просто подмножество, а собственное подмножество... хотя это наверное и не существенно

-- 17.06.2015, 15:57 --

ИСН в сообщении #1028066 писал(а):

Книга с тем же успехом могла быть об управлении полётом драконов; очень ли это важная информация?
Произведение и пересечение - это одно понятие в другой сказке; вернее, там пересечение было матерью произведения, которая родила его, а потом съела. В этой сказке они понятия совершенно разные. Математика состоит из таких сказок. Понятий миллион, слов не хватает. Слова используются по несколько раз. Надо всегда помнить, в какой сказке находишься.

сказка... как-то по-доброму... иногда математика становится содержанием снов-кошмаров... когда просыпаешься с холодным потом Но местами очень даже интересно

-- 17.06.2015, 16:04 --

Xaositect в сообщении #1028064 писал(а):

Чтобы функция была множеством пар.

ага! вроде становится понятней... последняя часть определения ... можно понимать, что

Цитата:

при $x=x'$, следует, что $y=y'$

как раз и говорит о том, что отображение будет единственным... то есть что 2 пары просто совпадают... правильно?

[whitefox]

IHmG в сообщении #1028078 писал(а):

Кстати, понял, что симовол обозначает не просто подмножество, а собственное подмножество... хотя это наверное и не существенно

Если Вы о $\subseteq,$ то это именно "подмножество", не обязательно "собственное". Смотрите, например, Википедию.

[IHmG]

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

IHmG в сообщении #1028078 писал(а):

Кстати, понял, что симовол обозначает не просто подмножество, а собственное подмножество... хотя это наверное и не существенно

Если Вы о $\subseteq,$ то это именно "подмножество", не обязательно "собственное". Смотрите, например, Википедию.

век живи - век учись! не заметил черточки перечеркивающей нижнюю часть символа :) спасибо за исправление!

[Xaositect]

На всякий случай: есть две системы обозначений. В одной произвольное подмножество обозначается $\subseteq$, а собственное - $\subset$. В другой произвольное подмножество обозначается $\subset$, собственное - $\subsetneq$.

[IHmG]

В книге есть раздел "вычислимость и разрешимость"

Там как раз описывается машина Тьюринга

Цитата:

Машина Тьюринга Т задет словарную функцию над некоторым алфавитом V и представляет собой описание машины - набор (F,Q,$q_0$,#,I) - и правило функционирования, общее для всех машин, где

V - алфавит машины
Q - конечное непустое множество символов, называемых состояниями машины (Q $\cap V = \varnothing$)
$q_0$ - выделенный элемент множества Q, называемый начальным состоянием
# - специальный пустой символ, не принадлежащий ни V, ни Q
I - программа машины

а до этого определение как раз

n-местной словарной функцией над алфавитом V называют n-местную функцию над $V^*$, т.е. функцию из $V^*\times V^*\times ... V^*\times $ (n раз) в $V^*$, где

$V^*$ - множество всех слов в алфавите V

так как словарная функция - это декартовое произведение... значит это какое-то пространство, грубо говоря составленное уже не из пар... и из векторов, где элементами вектора являются слова

я правильно понимаю?

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

[iifat]

IHmG в сообщении #1028131 писал(а):

пространство, грубо говоря составленное уже не из пар

Из пар, из пар. Только первый элемент пары состоит из $n$ элементов (называется это кортеж, если вам не лень запоминать новое слово). Только вряд ли это можно называть пространством.

[IHmG]

iifat в сообщении #1028135 писал(а):

IHmG в сообщении #1028131 писал(а):

пространство, грубо говоря составленное уже не из пар

Из пар, из пар. Только первый элемент пары состоит из $n$ элементов (называется это кортеж, если вам не лень запоминать новое слово). Только вряд ли это можно называть пространством.

Спасибо. Слово запоминающееся :)

А где можно посмотреть точное определение слова 'кортеж'? Просто любопытно... тут в теме мне уже говорили, что в математике есть разные сказки... и в разных сказках одними и теме же словами разные вещи называют.

-- 18.06.2015, 16:19 --

Xaositect в сообщении #1028064 писал(а):

Настоятельно рекомендую Вам для начала разобраться с языком теории множеств, например, по брошюрке Верещагин, Шень "Начала теории множеств" (есть тут: http://www.mccme.ru/free-books/), разделы 1.1-1.4, 1.7, 2.1, остальное по желанию.

обещаю, что прочту :)
спасибо за рекомендацию

[IHmG]

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

В книге есть раздел Определение рекурсивной схемы (РС)

Цитата:

В базисе РС нет множества операторов, вместо него - множество логических выражений и множество термов.

помню когда пытался освоить Lisp именно этот факт меня больше всего выбивал из равновесия... ладно когда рекурсивная функция - только один из возможных способов вычисления ... а вот когда она становится единственным способом вычисления в языке программирования

а теперь оказывается еще больше! эта же рекурсия используется как метод формализации понятия вычислимой функции

и вот видимо что-то фундаментальное в голове надо поломать, чтобы начать воспринимать последующее изложение в книге! Вопрос в том, что именно... какой именно пробел в знаниях теперь мне мешает? я лет 10 занимался обычным процедурным программированием... может ноги из профессии? %)

Цитата:

Простые термы определяются также, как термы-выражения в стандартных схемах программ. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида $F^{(n)}(\tau_1,\tau_2,...\tau_n)$, где $\tau_1,\tau_2,...\tau_n$ - простые термы, $F^{(n)}$ - определяемый функциональный символ.

логическое выражение - слово вида $p^{(n)}(\tau_1,\tau_2,...\tau_n)$, где $p^{(n)}$ - предикатный символ, а $\tau_1,\tau_2,...\tau_n$ - базовые термы

Терм - это простой терм, или условный терм, т.е. слово вида if $\pi$ then $\tau_1$ else $\tau_2$, где $\pi$ - логическое выражение, $\tau_1, \tau_2$ - простые термы, называемые соответственно левой и правой альтернативой

неужели эти все определения нужно обязательно запоминать? вроде когда вчитаешься более-менее понятно... но вот даже интересно... если с одной стороны есть стандартные схемы и они формализуют понятие вычислимой функции, с другой стороны есть рекурсивные схемы, которые занимаются тем же самым (уже подход Черча - Клини)... значит любую программу можно переписать на Lisp ?

Простите за оффтоп

[ИСН]

IHmG в сообщении #1028470 писал(а):

значит любую программу можно переписать на Lisp ?

Любую программу можно переписать на любом Turing-complete языке.

[iifat]

IHmG в сообщении #1028444 писал(а):

А где можно посмотреть точное определение слова 'кортеж'?

Ну, кортеж из двух элементов, сиречь пара, определяется в уже вам рекомендованном Верещагине, Шене. Корреж из $n$ элементов — ну, можно и самому. Да и где-нить там, рядом должно таки присутствовать.

[IHmG]

про упорядоченную пару в разделе функция видел... но там вроде про кортеж ничего не было... однако каюсь ... не всю методичку прочел %) поиск по pdf через ctrl+F термина кортеж у Верещагина результата не дал :)

[iifat]

Виноват. Неправильно вас понял.
Где можно найти определение термина «кортеж» — не помню. Где-то видел.