Содержание
- 2. Булевы константы Булевыми константами называются символы: 0 и 1. Символы 0 и 1 могут интерпретироваться как
- 3. Булев вектор Булев вектор — это последовательность конечного числа булевых констант, называемых компонентами булева вектора. Договоримся
- 4. Теорема о числе булевых векторов Теорема. Число различных булевых векторов длины n равно 2n . Доказательство
- 5. Представление булевыми векторами подмножеств
- 6. Пара булевых векторов Рассмотрим булевы векторы α = a1 a2 ... an и β = b1
- 7. Пара булевых векторов
- 8. Булево пространство и способы его представления Булевым пространством B n размерности n называется множество всех булевых
- 9. Пример матрицы Грея Пусть n = 5 . На левой матрице показан процесс построения кодов столбцов.
- 10. Интервал в булевом пространстве
- 11. Крайние случаи. Мощность интервала Крайние случаи: I (010, 010) = 010, границы интервала совпадают, он состоит
- 12. Алгоритм распознавания интервала
- 13. Соседние интервалы Интервалы I1, I2 называют соседними интервалами (соседями), если они совпадают по номерам внешних компонент,
- 14. Способы представления интервалов Мы уже пользовались тремя способами представления интервалов. 1) Границами интервала. 2) Явным перечислением
- 15. Алгоритм распознавания интервала на матрице Грея Шаг 1: если количество клеток заданного множества A не является
- 16. Примеры На левой матрице интервал I = -0 - - 1 (8 клеток и 3 оси
- 17. Задачи
- 19. Скачать презентацию
Булевы константы
Булевыми константами называются символы: 0 и 1.
Символы 0 и 1 могут интерпретироваться
Булевы константы
Булевыми константами называются символы: 0 и 1.
Символы 0 и 1 могут интерпретироваться
Булевым множеством B называется множество булевых констант, т.е. B = { 0, 1 }.
Булев вектор
Булев вектор — это последовательность конечного числа булевых констант, называемых
Булев вектор
Булев вектор — это последовательность конечного числа булевых констант, называемых
Договоримся обозначать булевы векторы греческими буквами, а компоненты вектора — латинскими с указанием номеров компонент.
Примеры. α = a1 a2 ... an = 010101, β =b1b2 ... bn=11110000.
Длиной булева вектора назовем количество его компонент, а весом вектора — количество компонент, равных единице.
Пример. Длина булева вектора α = 101010 равна шести, а вес — трем.
Теорема о числе булевых векторов
Теорема. Число различных булевых векторов длины n
Теорема о числе булевых векторов
Теорема. Число различных булевых векторов длины n
Доказательство (методом математической индукции по длине булева вектора).
База индукции. При n = 1 утверждение выполняется (число различных булевых векторов длины 1 равно двум: это 0 и 1).
Предположение. Пусть число различных булевых векторов длины n равно 2n .
Вывод. К булевым векторам длины n добавим n +1- ю компоненту, присвоив ей сперва значение 0 (получим 2n векторов длины n +1), затем — значение 1 (получим еще 2n векторов длины n +1), т.е. всего 2n + 2n = 2n+1 различных векторов длины n +1. ЧТД.
Представление булевыми векторами подмножеств
Представление булевыми векторами подмножеств
Пара булевых векторов
Рассмотрим булевы векторы α = a1 a2 ... an и
Пара булевых векторов
Рассмотрим булевы векторы α = a1 a2 ... an и
Говорят, что булевы векторы α и β ортогональны по i‑й компоненте, если ai ≠ bi .
Пример. Булевы векторы α = 1010 и β = 1000 ортогональны по 3-й компоненте.
Расстоянием между булевыми векторами (расстоянием по Хэммингу) называют число ортогональных компонент в данной паре векторов.
Пример. Расстояние по Хэммингу между булевыми векторами α = 1010 и β = 1001 равно двум.
Булевы векторы называются соседними (соседями), если они ортогональны по одной и только одной компоненте.
Пример. Булевы векторы α = 1010 и β = 1000 соседние.
Булевы векторы называются противоположными (антиподами), если они ортогональны по всем компонентам, т.е. расстояние по Хэммингу между булевыми векторами равно их длине.
Пример. Булевы векторы α = 1010 и β = 0101 противоположные.
Пара булевых векторов
Пара булевых векторов
Булево пространство и способы его представления
Булевым пространством B n размерности n называется
Булево пространство и способы его представления
Булевым пространством B n размерности n называется
Примеры. B 1 = {0,1} = B , B 2 = {00,01,10,11}.
Способы представления:
1) Явным перечислением векторов.
Пример. B 3 = {000, 001, 010, 011, 100, 101, 110, 111}.
2) Матрицей в коде Грея. Булево пространство размерности n представляется матрицей, состоящей из 2a строк и 2b столбцов, где a и b — целые числа, такие что a + b = n. Строкам матрицы поставлены в соответствие булевы векторы длины a (их называют кодами строк), а столбцам — булевы векторы длины b (коды столбцов).
Пример матрицы Грея
Пусть n = 5 . На левой матрице показан процесс построения
Пример матрицы Грея
Пусть n = 5 . На левой матрице показан процесс построения
Договоримся изображать коды условно: 1 – черточкой, 0 – ее отсутствием. Такой код более нагляден и быстрее рисуется.
Код Грея обладает свойством симметрии. Места смены значений компонент называются осями симметрии компонент.
Каждая ось имеет свою зону симметрии, т.е. область, на которую распространяется ее действие:
зоной симметрии осей младших компонент строк и столбцов (в примере: первой и третьей) является вся матрица;
зонами симметрии осей следующих компонент (в примере: второй и четвертой) являются половины матрицы;
и так далее (с каждым разом размер зоны уменьшается в два раза).
Интервал в булевом пространстве
Интервал в булевом пространстве
Крайние случаи. Мощность интервала
Крайние случаи:
I (010, 010) = 010, границы интервала совпадают, он
Крайние случаи. Мощность интервала
Крайние случаи:
I (010, 010) = 010, границы интервала совпадают, он
I (000, 111) = - - - , интервал — все булево пространство B 3, ранг r = 0, размерность s = 3.
Утверждение о мощности интервала. Мощность интервала размерности s равна 2s.
Доказательство. Так как интервал состоит из булевых векторов со всевозможными комбинациями нулей и единиц во внутренних компонентах, а внутренние компоненты образуют булев вектор длины s, то число таких векторов равно 2s.
Примеры. Мощность интервала -0- = {000, 001, 100, 101} равна 22 = 4, интервала1-1 = {101, 111 } равна 21 = 2, интервала 101 равна 20 = 1.
Алгоритм распознавания интервала
Алгоритм распознавания интервала
Соседние интервалы
Интервалы I1, I2 называют соседними интервалами (соседями), если они совпадают
Соседние интервалы
Интервалы I1, I2 называют соседними интервалами (соседями), если они совпадают
Примеры. Интервалы I1 = 11- и I2 = 01- — соседи (по первой компоненте); интервалы I1 = 01- и I2 = 10- — не соседи (различаются по двум внешним компонентам); интервалы I1 = 01- и I2 = 1-0 — не соседи (различаются по номерам внешних компонент).
Утверждение о соседних интервалах. Два соседних интервала ранга r (размерности s) не пересекаются, но, объединяясь, образуют интервал ранга r-1 (размерности s+1).
Операцию объединения двух интервалов I1 и I2, соседних по i-й компоненте, назовем склеиванием интервалов, а результат их склеивания (I = I1 ∪ I2) — расширением интервалов I1 и I2 по i-й компоненте.
Пример. Соседние интервалы I1 = 11-, I2 = 01- ранга 2 склеиваются, образуя интервал I = -1- ранга 1 (он является расширением интервалов I1 и I2 по первой компоненте).
Способы представления интервалов
Мы уже пользовались тремя способами представления интервалов.
1) Границами интервала.
2)
Способы представления интервалов
Мы уже пользовались тремя способами представления интервалов.
1) Границами интервала.
2)
3) Троичным вектором.
4) Матрица Грея.
Булево пространство представляется матрицей, а все булевы векторы (клетки), образующие интервал, выделяются.
Чтобы нарисовать интервал, достаточно отметить все строки и все столбцы, коды которых совпадают с заданным интервалом по внешним компонентам — на их пересечении и будет лежать интервал.
Пример. I = - 0-10 : отмечаем строки, в кодах которых вторая компонента равна 0 (верхняя и нижняя строки), и столбцы, в кодах которых четвертая компонента равна1, а пятая — 0 (два средних столбца ), — на их пересечении и лежит заданный интервал.
Алгоритм распознавания интервала на матрице Грея
Шаг 1: если количество клеток заданного
Алгоритм распознавания интервала на матрице Грея
Шаг 1: если количество клеток заданного
Шаг 2: если множество клеток (A) лежит симметрично относительно c осей симметрии, т.е. его можно “разрезать” осями симметрии на половины, затем каждую половину на четвертины, затем любую четвертину на осьмушки и так далее до тех пор, пока множество A не “разрежется” на отдельные клетки, то A — интервал, идем на шаг 3. иначе A — не интервал.
Шаг 3: конец.
Примеры
На левой матрице интервал I = -0 - - 1 (8 клеток и 3
Примеры
На левой матрице интервал I = -0 - - 1 (8 клеток и 3
Частные случаи
Очевидно, что интервалами являются следующие множества:
каждая отдельная клетка,
любая пара симметричных клеток, в том числе, рядом лежащих,
любая строка и любой столбец,
любая пара симметричных строк или столбцов, в том числе, рядом лежащих,
любой “квадрат” размером 2×2,
любая половина или четвертина матрицы,
четверка клеток, лежащих в углах матрицы.
Задачи
Задачи