Skip to main content
LibreTexts - Ukrayinska

B.6: Відносини та функції

  • Page ID
    52748
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Коли ми визначили набір об'єктів (наприклад, натуральні числа або приємні терміни) індуктивно, ми також можемо визначити відносини на цих об'єктах шляхом індукції. Наприклад, розгляньте наступну ідею: приємний термін\(t_1\) є субтерміном приємного терміна,\(t_2\) якщо він зустрічається як його частина. Давайте використаємо для нього символ:\(t_1 \sqsubseteq t_2\). Кожен приємний термін є підтерміном самого себе, звичайно:\(t \sqsubseteq t\). Ми можемо дати індуктивне визначення цього співвідношення наступним чином:

    Визначення\(\PageIndex{1}\)

    Відношення приємного терміна,\(t_1\) що є субтерміном\(t_2\)\(t_1 \sqsubseteq t_2\), визначається індукцією\(t_2\) наступним чином:

    1. Якщо\(t_2\) буква, то\(t_1 \sqsubseteq t_2\) iff\(t_1 = t_2\).

    2. Якщо\(t_2\) є\([s_1 \circ s_2]\), то\(t_1 \sqsubseteq t_2\) iff\(t = t_2\)\(t_1 \sqsubseteq s_1\), або\(t_1 \sqsubseteq s_2\).

    Це визначення, наприклад, скаже нам про це\(\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]\). Для (2) говорить, що\(\mathrm{a} \sqsubseteq [\mathrm{b} \circ \mathrm{a}]\) iff\(\mathrm{a} = [\mathrm{b} \circ \mathrm{a}]\), або\(\mathrm{a} \sqsubseteq b\), або\(\mathrm{a} \sqsubseteq \mathrm{a}\). Перші два є помилковими:\(\mathrm{a}\) явно не ідентичні\([\mathrm{b} \circ \mathrm{a}]\), і по (1),\(\mathrm{a} \sqsubseteq \mathrm{b}\) iff\(\mathrm{a} = \mathrm{b}\), що також є помилковим. Однак також по (1),\(\mathrm{a} \sqsubseteq \mathrm{a}\) iff\(\mathrm{a} = \mathrm{a}\), що вірно.

    Важливо зазначити, що успіх цього визначення залежить від факту, який ми ще не довели: кожен приємний термін\(t\) - це або сама по собі буква, або є однозначно визначені приємні терміни\(s_1\) і\(s_2\) такі, що \(t = [s_1 \circ s_2]\). «Однозначно визначається» тут означає, що якщо\(t = [s_1 \circ s_2]\) це не також\(= [r_1 \circ r_2]\) з\(s_1 \neq r_1\) або\(s_2 \neq r_2\). Якби це було так, то пункт (2) може вступити в конфлікт з самим собою: читання,\(t_2\) як\([s_1 \circ s_2]\) ми могли б отримати\(t_1 \sqsubseteq t_2\), але якщо ми читаємо,\(t_2\) як\([r_1 \circ r_2]\) ми можемо отримати не\(t_1 \sqsubseteq t_2\). Перш ніж ми доведемо, що цього не може статися, давайте розглянемо приклад, де це може статися.

    Визначення\(\PageIndex{2}\)

    Визначте бездужкові терміни індуктивно

    1. Кожна буква - це термін без дужки.

    2. Якщо\(s_1\) і\(s_2\) є бездужковими термінами, то\(s_1 \circ s_2\) це термін без дужки.

    3. Ніщо інше не є бездужним терміном.

    Терміни без брекеток є, наприклад,\(\mathrm{a}\),\(\mathrm{b} \circ \mathrm{d}\),\(\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}\). Тепер, якби ми визначили «підтермін» для термінів без дужки так, як ми зробили вище, другий пункт буде читати

    Якщо\(t_2 = s_1 \circ s_2\), то\(t_1 \sqsubseteq t_2\) iff\(t_1 = t_2\)\(t_1 \sqsubseteq s_1\), або\(t_1 \sqsubseteq s_2\).

    Тепер\(\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}\) має форму\(s_1 \circ s_2\) з

    \[s_1  = \mathrm{b} \quad\text{ and }\quad  s_2  = \mathrm{a} \circ \mathrm{b}.\nonumber\]

    Він також має форму\(r_1 \circ r_2\) з

    \[r_1  = \mathrm{b} \circ \mathrm{a} \quad\text{ and }\quad r_2 = \mathrm{b}.\nonumber\]

    Тепер\(\mathrm{a} \circ \mathrm{b}\) є субтерміном\(\mathrm{b} \circ \mathrm{a} \circ \mathrm{b}\)? Відповідь - так, якщо ми йдемо до першого читання, і ні, якщо ми йдемо за другим.

    Властивість, що так, як хороший термін будується з інших приємних термінів є унікальним називається унікальною читаністю. Оскільки індуктивні визначення відносин для таких індуктивно визначених об'єктів є важливими, ми маємо довести, що вони мають місце.

    Пропозиція\(\PageIndex{1}\)

    Припустимо,\(t\) це хороший термін. Тоді або\(t\) є лист сам по собі, або є однозначно визначені приємні терміни\(s_1\),\(s_2\) такі, що\(t = [s_1 \circ s_2]\).

    Доказ. Якщо\(t\) це лист сам по собі, умова виконується. Так що припустимо, що\(t\) це не лист сам по собі. Ми можемо сказати з індуктивного визначення, що потім\(t\) повинні бути форми\([s_1 \circ s_2]\) для деяких приємних термінів\(s_1\) і\(s_2\). Залишається показати, що ці однозначно визначаються, тобто якщо\(t = [r_1 \circ r_2]\), то\(s_1 = r_1\) і\(s_2 = r_2\).

    Так припустимо,\(t = [s_1 \circ s_2]\) а також\(t = [r_1 \circ r_2]\) для приємних умов\(s_1\)\(s_2\),\(r_1\),,\(r_2\). Ми повинні показати, що\(s_1 = r_1\) і\(s_2 = r_2\). По-перше,\(s_1\) і\(r_1\) повинен бути ідентичним, бо в іншому випадку один є правильним початковим відрізком іншого. Але за пропозицією B.5.2, це неможливо, якщо\(s_1\) і обидва\(r_1\) приємні умови. Але якщо\(s_1 = r_1\), то явно теж\(s_2 = r_2\). ◻

    Ми також можемо визначити функції індуктивно: наприклад, ми можемо визначити функцію,\(f\) яка відображає будь-який приємний термін на максимальну глибину вкладеного\([\dots]\) в нього наступним чином:

    Визначення\(\PageIndex{3}\)

    Глибина приємного терміна визначається\(f(t)\) індуктивно наступним чином:\[f(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(f(s), f(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

    Наприклад\[\begin{aligned} f([\mathrm{a} \circ \mathrm{b}]) & = \max(f(\mathrm{a}),f(\mathrm{b})) + 1 = \\ &= \max(0, 0) + 1 = 1, \text{ and}\\ f([[\mathrm{a} \circ \mathrm{b}] \circ \mathrm{c}]) & = \max(f([\mathrm{a} \circ \mathrm{b}]), f(\mathrm{c})) + 1 = \\ & = \max(1,0) + 1 = 2.\end{aligned}\]

    Тут, звичайно, ми припускаємо, що\(s_1\) an\(s_2\) є хорошими термінами, і використовуємо той факт, що кожен приємний термін є або буквою, або формою\([s_1 \circ s_2]\). Знову ж таки важливо, що вона може бути такої форми тільки одним способом. Щоб зрозуміти, чому, знову розглянемо терміни без дужки, які ми визначили раніше. Відповідним «визначенням» було б:

    \[g(t) = \begin{cases} 0 & \text{ if $t$ is a letter}\\ \max(g(s), g(s')) + 1 & \text{ if $t = [s_1 \circ s_2]$.} \end{cases}\nonumber\]

    Тепер розглянемо бездужковий термін\(\mathrm{a} \circ \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}\). Його можна прочитати більш ніж одним способом, наприклад, як\(s_1 \circ s_2\) з

    \[s_1 = \mathrm{a} \quad\text{ and }\quad s_2 = \mathrm{b} \circ \mathrm{c} \circ \mathrm{d}, \nonumber\]

    або як\(r_1 \circ r_2\) з

    \[r_1 = \mathrm{a} \circ b \quad\text{ and }\quad r_2 = \mathrm{c} \circ \mathrm{d}.\nonumber\]

    Обчислення\(g\) відповідно до першого способу читання це дало б

    \ [\ почати {вирівняний} г (s_1\ circ s_2) & =\ max (g (\ mathrm {a}), g (\ mathrm {b}\ circ\ mathrm {c}\ circ\ mathrm {d}) + 1 =\\
    & =\ max (0,2) + 1 = 3\ кінець {вирівняний}\]

    тоді як згідно з іншим читанням ми отримуємо

    \ [\ почати {вирівняний} g (r_1\ circ r_2) & =\ max (g (\ mathrm {a}\ circ\ mathrm {b}), g (\ mathrm {c}\ circ\ mathrm {d}) + 1=\\
    & =\ max (1,1) + 1 = 2\ кінець {вирівняний}\]

    Але функція завжди повинна давати унікальне значення; тому наше «визначення» взагалі\(g\) не визначає функцію.

    Проблема\(\PageIndex{1}\)

    Дайте індуктивне визначення функції\(l\), де\(l(t)\) - кількість символів у приємному терміні\(t\).

    Проблема\(\PageIndex{2}\)

    Доведіть структурною індукцією на приємних умовах\(t\), що\(f(t) < l(t)\) (де\(l(t)\) кількість символів в\(t\) і\(f(t)\) є глибиною,\(t\) як визначено у визначенні\(\PageIndex{3}\)).