7. Применение операций объединения, пересечения конечное число раз. Доказательство дистрибутивности и принципа двойственности методом математической индукции.
ЕСТЬ ДОКАЗАТЕЛЬСТВА?
8.Применение операций объединения, пересечения бесконечное число раз. Доказательство дистрибутивности и принципа двойственности для этого случая.
ЕСТЬ ДОКАЗАТЕЛЬСТВА?
9. Разбиение множества, покрытие множества, примеры в математике и информатике.
Представление заданного множества в виде объединения системы множеств, не имеющих попарно общих точек, называется разбиением. Таким образом, если есть множество A, такое что A = UiBi, где для любых Bi и Bj, Bi & Bj = пустому множеству, то система {Bi} есть разбиение множества A (рис. 12).
Очевидно, что множества могут обладать различными разбиениями.
Любое множество подмножеств множества
A, объединение которых есть множество
A, называется покрытием множества A.
Следовательно, если есть множество A,
такое что
,
то система {Bi} есть покрытие множества
A (рис. 10).
Таким образом, разбиение есть частный случай покрытия, т.е. это покрытие, в котором множества Bi не пересекаются.
КАКИЕ МОГУТ БЫТЬ ПРИМЕРЫ?
10.Определение слова, подслова, префикса, суффикса, собственного подслова, собственного префикса и суффикса, их свойства. Равенства слов, операции приписывания, свойства операции приписывания.
Слово определяется следующим образом:
- любая буква есть слово;
- если A - слово и В - слово, то AВ - также слово; (рис. 14)
- пустое слово (слово, не содержащее букв) есть также слово.
ПодсловомсловаDназывается такое словоB, для которого существуют словаAиC:ABC=D.
Слово B называется началом слова A (или его префиксом), если существует слово С, такое что A=BC.
Слово C называется концом слова A (или его суффиксом), если существует слово B, такое что A = BC.
Слово С есть собственное подсловослова A, если существуют такие слова B и D, что A имеет вид BCD и хотя бы одно B или D не пусто. Например, слово "вид" есть подслово слова "очевидно".
Говорят, что A - собственное начало (или собственный префикс) слова B, если A - начало B и A не равно B. Соответственно, A - собственный конец (илисобственный суффикс) слова B, если A - конец B и A не равно B.
Если два слова A и В построены из одинаковых букв, расположенных в одинаковом порядке, то в дальнейшем, мы будем говорить, что слова A и В графически равны. Так, слова "апшжэбк" и “апшжэбк" графически равны.
Таким образом, слова строятся с помощью операции приписывания, т.е. к слову A приписывается справа слово B. Операцию приписывания также называют конкатенацией.
1) Операция приписывания не коммутативна
2) Операция приписывания ассоциативны
3) Если слова A, B и C таковы, что AC = BC, то A = B.
4) Если слова A, B и C таковы, что CA = CB, то A = B.
Последние два свойства называют также правилами сокращения.
11.Определение кода и основные теоремы о кодах.
Теорема о двухбуквенном коде.
Любой конечный алфавит П={a1,a2,…an} может быть закодирован с помощью кода записанного в алфавите {0,1}
Доказательство: an= {(0…0)1}, где (0…0)=n
Заданное отображение является биекцией. Ч.т.д.
Какие ещё есть теоремы?