XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 3
Текст из файла (страница 3)
элементов замкнутого полукольца 3.2 — итерация (замыкание) элемента а замкнутого полукольца (или полукольца с итерацией) 3.2  — двухэлементнзя булеза алгебра (то же, что полукольцо Б) 3.4 А= (А, Й, П) — алгебраическая система с носителем А, сигнатурой, состоящей из множества операций Й и множества отношений П 4.1 а' А = (А, Й) — алгебра с носителем А и сигнатурой (множеством операций) Й 4.1 К+ — полукольцо (И+, шш, +, +со, 0) (полукольцо неотрицательных действительных чисел вместе с +со с операциями взятия наименьшего элемента и сложения) 3.1 8я — полукольцо (2~, О, й, о, А) (полукольцо всех подмножеств множества А) 3.1 Ял — полукольцо (2~" ~, Ц ~, И, Ыл) (полукольцо всех бинарных отношений на множестве А) 3.1 Лà — полукольцо (1Че, +,, О, 1) (полукольцо неотрица тельных целых чисел с обычными операциями сложения и умножения) 3.1 8( ь) — полукольцо ([а, Ь[ С Ж, шах, шш, а, Ь) (полукольцо чисел из отрезка числовой прямой с операциями взятия максимума и минимума из двух чисел) 3.1 Ма$г(8) — множество всех матриц с элементами из полукольца8 33 М„(8) — полукольцо квадратных матриц порядка и с элементами из полукольца 8 3.3 7ӄ— полукольцо всех делителей натурального числа и 3.4 18 ОСНОВНЫЕ ОБОЗНАЧЕНИЯ А= (А, П) — модель с носителем А и сигнатурой (множеством отношений) П 4.1 [В)п — замыкание множества В по операциям сигнатуры й (й-замыкание множества В) 4.2 Ь: А -+  — гомоморфизм Ь алгебраической системы А в ал- гебраическую систему В 4.4 — ядро гомоморфизма Ь одной алгебраической системы в другую 4.4 — гомоморфный образ алгебраической системы А (относительно гомоморфизма Ь) 4.4 — символ изоморфизма алгебраических систем 4.4 — фактор-система алгебраической системы А по конгруэнции р 4.3 — вершина и соединена ребром с вершиной е в неориентированном графе С (имя графа часто опускается) 6.1 Кег Л Ь(А) А/р чалом и и концом е (имя графа часто опускается) 6.1 и~=~'а э — нз вершины и (неориентированного графа С) достижима вершина е (имя графа часто опускается) 5.1 п~+ е псяв е М=,'" 9 — существует цепь ненулевой длины, соединяющая вершины и и е (неориентированного графа) 5.1 — существует цепь длины и, соединяющая вершины и и е (неориентированного графа) 5.1 — из вершины и (некоторого ориентированного грэ фа) достижима вершина е 5.1 и =ь+ е — существует путь ненулевой длины из вершины и в вершину е (в ориентированном графе) 5.1 и -+О е — существует дуга в ориентированном графе С с на- — степень вершины э (в неориентированном или ориентированном графе) 5.1 й5(е) 65+(е) — полустепень исхода вершины е (в ориентированном графе) 5.1 й5 (о) — полустепень захода вершины е (в ориентированном графе) 5.1 — множество всех таких вершин и (ориентированн- Г(е) го или неориентированного графа), что и -~ е (для ориентированного графа) или и не (для неориенти- рованного графа) 5.1 Г ~(е) — множество всех таких вершин и (ориентированного графа), что и -+ е 5.1 список смежности вершины е (в неориентированном или ориентированном графе) 5.2 А[э] Ы(е), п(е), Це) — глубина, высота и уровень соответственно узла е дерева 5.3 Ьт — высота дерева Т 5.3 С1 = бз — графы 01 и бз изоморфны 5.7 С вЂ” дополнение графа 0 5.Т У' — множество всех слов в алфавите У 7.1 множество всех непустых слов в алфавите У Т.1 множество всех слов длины и в алфавите У 7.1 Л вЂ” пустое слово 7.1 я(1) — 1-я буква слова х 7.1 х(1)я(2)...
х(й) — побуквенная запись слова я 7.1 (и, х, е) — вхождение слова х в слово р = пяе 7.1 и С е — слово и входит в слово э 7.1 Ь| Ьз — соединение (конкатенация) языков Ь| и Ьг 7.1 и ~" ю — существует путь длины и из вершины и в вершину е (в ориентированном графе) 5.1 2О ОСНОВНЫЕ ОБОЗНА ЧЕНИЯ итерация языка Ь 7.1 позитивная итерация языка Ь 7.1 Е(У) и-~~3 7Об полукольцо всех языков в алфавите У 7.1 правило вывода (продукция) в грамматике 7.2 цепочка б непосредственно выводима в грамматике С из цепочки 'у (имя грамматики часто опускается) 7.2 у1-рб цепочка б непосредственно выводима в грамматике 6 из цепочки у применением правила р Т.2 цепочка б выводима в грамматике С из цепочки у (имя грамматики часто опускается) 7.2 существует вывод ненулевой длины цепочки б в грамматике С из цепочки у (имя грамматики часто опускается) 7.2 существует вывод длины и цепочки 6 в грамматике С из цепочки у (имя грамматики часто опускаетсл) 7.2 7~об И(У) — полукольцо регулярных языков в алфавите У 7.4 (и+ р) — сумма регулярных выражений 7.4 (а,9) — произведение регулярных выражений Т.4 итерация и позитивная итерация регулярного выражения соответственно 7.4 д — ~ г из состояния д конечного автомата возможен переход в состояние г по символу (или пустой цепочке) а Т5 запись команды конечного автомата (по символу или пустой цепочке а разрешен переход из состояния д в состояние г) Т.5 а ~ Д ~ ~3з ~...
~ Д, — запись множества правил грамматики с одной и той же левой частью а 7.2 21 д =~* г — цепочка я читается на некотором пути из состояния д в состояние г конечного автомата 7.5 ЦМ) — язык конечного автомата М Т.5 Ы вЂ” символ эквивалентности конечных автоматов 7.5 даЯ ~ г у — запись команды МП-автомата (из состояния 4 с верхним символом в магазине Я по входному символу или пустой цепочке а разрешен переход в состояние г с заменой символа Я цепочкой у) 8.4 ~м, 1-м,1-+м, ~-в~ — отношения непосредственной выводимости, выводимости, выводимости за ненулевое число шагов и выводимости за и шагов соответственно на множестве конфигураций МП-автомата М 8.4 ЦМ) — язык МП-автомата М 8.4 о(Ы ~,..., Ь„) — суперпозиция (подстановка) языков Ь|, ..., Ьп в язык Ь 8.5 А Д Х~Хз...
Х в — упорядоченное дерево, корень которого помечен символом А, а листья имеют метки Х~, ..., Х„, 8.1 А ). Х~Хг...Х~в — куст упорядоченного дерева„корень которого помечен символом А, а листья имеют метки Х, ..., Х,„8.1 22 ОСНОВНЫЕ ОБОЗКА ЧЕНИЯ Буквы латинского алфавита Представлен наиболее употребительный (но не единственный) вариант проюношения (в частности, вместо „йот" иногда говорят „жи").
Буквы греческого алфавита Наряду с указанным проюношением также говорят „лямбда", „мю" и „ню". 1. МНОЖ:ЕСТВА И ОТНОШЕНИЯ 1.1. Множества Элементы теории множеств изложены в [Ц. Напомним здесь основные понятия и обозначения. Понятие множества является исходным не определяемым строго понятием'. Приведем здесь определение множества (точнее, пояснение идеи множества), принадлежащее Г. Кантору'*: еПод многообразием или множеством я понимаю вообще все многое, которое возможно мыслить как единое, т.е.
такую совокупность определенных элементов, которая посредством одного закона может быть соединена в одно целое". Множества будем, как правило, обозначать большими буквами латинского алфавита, а их элементы — малыми, хотя иногда от этого соглашения придется отступать, так как элементами некоторого множества могут быть другие множества. Тот факт, что элемент а принадлежит множеству А, записывается в виде а е А. В математике мы имеем дело с самыми различными множествами. Для элементов этих множеств мы используем два основных вида обозначений: константы и переменные. Индивнднал нонсгпанта (или просто нонспзанта) с областью значений А обозначает фиксированный элемент множества А.
Таковы, например, обозначения (записи в опреде- 'Это имеет место в так называемой „наивной" теории множеств. В современной математической литературе фигурируют различные построения теории множеств, в которых понятие множества строго определяется посредством набора аксиом (аксиоматические теории множеств), но при этом используются уже другие неопределимые понятия.
В рамках курса дискретной математики нам достаточно ограничиться „наивным" подходом. "1'. Кантор (1845-1918) — немецкий математик, основатель теорни множеств. 24 1. МНОЖЕСТВА И ОТНОШЕНИЯ ленной системе счисления) действительных чисел: 0; 2; 7,34. Для двух констант а и Ь с областью значений А будем писать а = Ь, понимая под этим совпадение обозначаемых ими элементов множества А. Индивидное переменное (или просто переменное) с областью значений А обозначает проювольный, заранее не определенный элемент множества А. При этом говорят, что переменное х пробегает множество А или переменное х принимает проювольные значения на множестве А.
Можно фиксировать значение переменного х, записав х = а, где а — константа с той же областью значений, что и х. В этом случае говорят, что вместо переменного х подставлено его конкретное значение а, или произведена подстановка а вместо х, или переменное х приняло значение а. Равенство переменных х = у понимается так: всякий раз, когда переменное х принимает проювольное значение а, переменное р принимает то же самое значение а, и наоборот.
Таким образом, равные переменные „синхронно" принимают всегда одни и те же значения. Обычно константы и переменные, область значений которых есть некоторое числовое множество (1], а именно одно из множеств М, У, © 1к и С, называют соответственно натуральными, целыми (или целочисленными), рациональными, действительными и комплексными константами и переменными. В курсе дискретной математики мы будем испольэовать различные константы и переменные, область значений которых не всегда является числовым множеством. Для сокращения записи мы будем пользоваться логической символикой (1], позволяющей коротко, наподобие формул, записывать высказывания. Понятие высказывания не определяется.
Указывается только, что всякое высказывание может быть истинным или ложным (разумеется, не одновременно!). Для образования из уже имеющихся высказываний новых высказываний используются следующие логические операции (или логические связки). 1.1. Миохества 25 1. Дизьюнкцил Ч: высказывание Р Ч Я (читается: „Р или Я") истинно тогда и только тогда, когда истинно хотя бы одно из высказываний Р и Я. 2. Конъюнкция Л: высказывание РЛЯ (читается: „Р и Я") истинно тогда и только тогда, когда истинны оба высказывания Р и Я. 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
