Матеріал з Ukrainian Logical Encyclopedia

Версія 22:35, 29 травня 2010 (переглянути вихідний код) Logic (обговорення | внесок) (Створена сторінка: '''Алфаві́т''') ← Попереднє редагування		Версія 18:02, 7 липня 2010 (переглянути вихідний код) Ярослав Кохан (обговорення | внесок) Наступне редагування →
Рядок 1:		Рядок 1:
-	'''Алфаві́т'''	+	'''Алфаві́т''' — непорожня [[множина]] попарно розрізненних [[символ]]ів. Елементи алфавіту називаються його [[буква]]ми. Скінченні послідовності [[інскрипція|записів]] букв даного алфавіту називаються [[слово|словами]] в цьому алфавіті. Множина всіх слів у деякому алфавіті називається [[формальна мова|формальною мовою]] із цим алфавітом.
		+
		+	Неформально висловлюючись, алфавіт є сукупністю вихідних знаків, з яких вибудовуються всі виражальні засоби, належні мові, заснованій на даному алфавіті.
		+
		+	Поняття алфавіту є одним із основних понять теорії формальних мов, котра, у свою чергу, лежить в основі [[синтаксис|логічного синтаксису]].
		+
		+	==Термінологія і походження==
		+	''англ.'' — alphabet<br>
		+	''рос.'' — алфави́т
		+
		+	Слово &laquo;алфавіт&raquo; походить з грецької мови, де має форму αλφάβητο; утворене від назв двох перших букв грецького алфавіту — букви α (&laquo;альфа&raquo;) і β (&laquo;віта&raquo; в новогрецькій мові).
		+
		+	==Означення==
		+	Слово &laquo;алфавіт&raquo; — термін. '''''Означення''''': алфавітом називають будь-яку непорожню множину попарно розрізненних символів.
		+
		+	==Властивості алфавітів та відношення між ними==
		+	===Алфавітні слова===
		+	Практично завжди букви алфавіту перелічують не у випадковій послідовності, а в деякій фіксованій. Таку фіксовану послідовність називають ''алфавітним словом''; саме її завчають у школах у випадку алфавітів природних мов. Оскільки всяке алфавітне слово вичерпно характеризує відповідний алфавіт, розгляд алфавітів завжди можна замінити на розгляд алфавітних слів. Однак, оскільки порядок букв у алфавітному слові несуттєвий з точки зору властивостей алфавіту, таку заміну не проводять, а самі алфавіти вивчають лише з точністю до рівноскладеності (складеності з однакових букв).
		+
		+	===Класифікація символів алфавітів===
		+	''Див.: [[буква]]''.
		+
		+	===Відношення між алфавітами===
		+	Нехай A, B — алфавіти, і A &#8838; B. В такому разі A називається ''підалфавітом'' або ''звуженням'' алфавіту B, а B, відповідно, називається ''надалфавітом'' або ''розширенням'' алфавіту A.
		+
		+	===Найпростіші алфавіти===
		+	Найпростішими серед алфавітів є однобуквові. Слова в таких алфавітах відрізняються одне від одного тільки довжиною (кількістю букв), а тому можуть використовуватися для представлення довжини слів у будь-яких алфівітах. Як правило, для такої мети обирають алфавіт, єдиною буквою якого є вертикальна паличка  ‘|’; математики-конструктивісти часом ототожнюють слова в такому алфавіті —  Λ, ‘|’, ‘||’, ‘|||’, ... — з натуральними [[число|числами]]. В однобуквових алфавітах можна записувати лише окремі [[вираз]]и (слова), але не [[текст]]и, оскільки для формування останніх потрібен окремий символ (пробіл), який би відділяв слова одне від одного, в той час як в однобуквових алфавітах є лише одна буква, і вона вживається для формування самих слів.
		+
		+	Для формулювання текстів потрібен не менш як двобуквовий алфавіт. В загальному випадку одна із його букв має слугувати пробілом; однак, в деяких спеціальних випадках можна обійтися без пробілу. Так, для представлення натуральних чисел можна використати двобуквовий алфавіт, напр.: {1, 2}, в якому ці числа записуватимуться у вигляді послідовностей, в котрих за записом першої букви ‘1’ ітиме послідовність будь-якої натуральної кількості записів букв ‘2’; відтак, ці слова матимуть вигляд ‘1’, ‘12’, ‘122’, ‘1222’ і&nbsp;т.&nbsp;д. Їх можна писати, не розділяючи, оскільки початок кожного з них однозначно визначений буквою  ‘1’.
		+
		+	===Представлення алфавітів===
		+	Алфавіти бувають скінченними і нескінченними. Іноді поняття алфавіту звужують до поняття скінченної множини символів, проте, часто буває зручно нескінченні запаси символів також називати алфавітами; так, множини змінних у будь-якій мові нескінченні, і такі множини нерідко розглядаються як окремі алфавіти змінних. Наприклад, кажуть: {{початок цитати}}розглянемо нескінченний список символів ''a'', ''b'', ''c'', ''a''<sub><small>1</small></sub>, ''b''<sub><small>1</small></sub>, ''c''<sub><small>1</small></sub>, ..., які називатимемо вільними індивідними змінними...{{кінець цитати}}
		+	Оскільки ж неможливо окремо задати нескінченну кількість букв, елементи нескінченних алфавітів представляють словами деяких інших — скінченних — алфавітів. Така процедура називається [[кодування]]м нескінченного алфавіту у скінченному. Кодувати можна і скінченні алфавіти. Найпростішими алфавітами, в яких можна закодувати будь-який інший алфавіт, є двобуквові алфавіти.
		+
		+	=Джерела=
		+	# ''Карри&nbsp;Х.'' Основания математической логики. Пер. с англ. – М.: Мир, 1969. – 568&nbsp;с.
		+	# ''Мальцев&nbsp;А.&nbsp;И.'' Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392&nbsp;с.
		+	# ''Марков&nbsp;А.&nbsp;А., Нагорный&nbsp;Н.&nbsp;М.'' Теория алгорифмов. – М.: Наука, 1984. – 432&nbsp;с.
		+	# ''Смальян&nbsp;Р.'' Теория формальных систем. Пер. с англ. – М.: Наука, 1981. – 208&nbsp;с.

---

Версія 18:02, 7 липня 2010

Алфаві́т — непорожня множина попарно розрізненних символів. Елементи алфавіту називаються його буквами. Скінченні послідовності записів букв даного алфавіту називаються словами в цьому алфавіті. Множина всіх слів у деякому алфавіті називається формальною мовою із цим алфавітом.

Неформально висловлюючись, алфавіт є сукупністю вихідних знаків, з яких вибудовуються всі виражальні засоби, належні мові, заснованій на даному алфавіті.

Поняття алфавіту є одним із основних понять теорії формальних мов, котра, у свою чергу, лежить в основі логічного синтаксису.

Зміст 1 Термінологія і походження 2 Означення 3 Властивості алфавітів та відношення між ними 3.1 Алфавітні слова 3.2 Класифікація символів алфавітів 3.3 Відношення між алфавітами 3.4 Найпростіші алфавіти 3.5 Представлення алфавітів 4 Джерела

Термінологія і походження

англ. — alphabet
рос. — алфави́т

Слово «алфавіт» походить з грецької мови, де має форму αλφάβητο; утворене від назв двох перших букв грецького алфавіту — букви α («альфа») і β («віта» в новогрецькій мові).

Означення

Слово «алфавіт» — термін. Означення: алфавітом називають будь-яку непорожню множину попарно розрізненних символів.

Властивості алфавітів та відношення між ними

Алфавітні слова

Практично завжди букви алфавіту перелічують не у випадковій послідовності, а в деякій фіксованій. Таку фіксовану послідовність називають алфавітним словом; саме її завчають у школах у випадку алфавітів природних мов. Оскільки всяке алфавітне слово вичерпно характеризує відповідний алфавіт, розгляд алфавітів завжди можна замінити на розгляд алфавітних слів. Однак, оскільки порядок букв у алфавітному слові несуттєвий з точки зору властивостей алфавіту, таку заміну не проводять, а самі алфавіти вивчають лише з точністю до рівноскладеності (складеності з однакових букв).

Класифікація символів алфавітів

Див.: буква.

Відношення між алфавітами

Нехай A, B — алфавіти, і A ⊆ B. В такому разі A називається підалфавітом або звуженням алфавіту B, а B, відповідно, називається надалфавітом або розширенням алфавіту A.

Найпростіші алфавіти

Найпростішими серед алфавітів є однобуквові. Слова в таких алфавітах відрізняються одне від одного тільки довжиною (кількістю букв), а тому можуть використовуватися для представлення довжини слів у будь-яких алфівітах. Як правило, для такої мети обирають алфавіт, єдиною буквою якого є вертикальна паличка ‘|’; математики-конструктивісти часом ототожнюють слова в такому алфавіті — Λ, ‘|’, ‘||’, ‘|||’, ... — з натуральними числами. В однобуквових алфавітах можна записувати лише окремі вирази (слова), але не тексти, оскільки для формування останніх потрібен окремий символ (пробіл), який би відділяв слова одне від одного, в той час як в однобуквових алфавітах є лише одна буква, і вона вживається для формування самих слів.

Для формулювання текстів потрібен не менш як двобуквовий алфавіт. В загальному випадку одна із його букв має слугувати пробілом; однак, в деяких спеціальних випадках можна обійтися без пробілу. Так, для представлення натуральних чисел можна використати двобуквовий алфавіт, напр.: {1, 2}, в якому ці числа записуватимуться у вигляді послідовностей, в котрих за записом першої букви ‘1’ ітиме послідовність будь-якої натуральної кількості записів букв ‘2’; відтак, ці слова матимуть вигляд ‘1’, ‘12’, ‘122’, ‘1222’ і т. д. Їх можна писати, не розділяючи, оскільки початок кожного з них однозначно визначений буквою ‘1’.

Представлення алфавітів

Алфавіти бувають скінченними і нескінченними. Іноді поняття алфавіту звужують до поняття скінченної множини символів, проте, часто буває зручно нескінченні запаси символів також називати алфавітами; так, множини змінних у будь-якій мові нескінченні, і такі множини нерідко розглядаються як окремі алфавіти змінних. Наприклад, кажуть:

розглянемо нескінченний список символів a, b, c, a₁, b₁, c₁, ..., які називатимемо вільними індивідними змінними...

Оскільки ж неможливо окремо задати нескінченну кількість букв, елементи нескінченних алфавітів представляють словами деяких інших — скінченних — алфавітів. Така процедура називається кодуванням нескінченного алфавіту у скінченному. Кодувати можна і скінченні алфавіти. Найпростішими алфавітами, в яких можна закодувати будь-який інший алфавіт, є двобуквові алфавіти.

Джерела

1. Карри Х. Основания математической логики. Пер. с англ. – М.: Мир, 1969. – 568 с.
2. Мальцев А. И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392 с.
3. Марков А. А., Нагорный Н. М. Теория алгорифмов. – М.: Наука, 1984. – 432 с.
4. Смальян Р. Теория формальных систем. Пер. с англ. – М.: Наука, 1981. – 208 с.