Дискретная математика. Булевы константы и вектора. (Лекция 3)

Нажмите для полного просмотра!

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №2

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №3

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №4

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №5

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №6

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №7

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №8

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №9

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №10

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №11

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №12

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №13

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №14

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №15

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №16

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №17

Дискретная математика. Булевы константы и вектора. (Лекция 3), слайд №18

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Дискретная математика. Булевы константы и вектора. (Лекция 3). Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дискретная математика Лекция 3. Булевы константы и вектора

Слайд 2

Описание слайда:

Булевы константы Булевыми константами называются символы: 0 и 1. Символы 0 и 1 могут интерпретироваться как числа: ноль и единица, знаки: минус и плюс, потенциалы: низкий и высокий, высказывания: ложь и истина, и многое другое. Булевым множеством B называется множество булевых констант, т.е. B = { 0, 1 }.

Слайд 3

Описание слайда:

Булев вектор Булев вектор — это последовательность конечного числа булевых констант, называемых компонентами булева вектора. Договоримся обозначать булевы векторы греческими буквами, а компоненты вектора — латинскими с указанием номеров компонент. Примеры.  = a1 a2 ... an = 010101,  =b1b2 ... bn=11110000. Длиной булева вектора назовем количество его компонент, а весом вектора — количество компонент, равных единице. Пример. Длина булева вектора  = 101010 равна шести, а вес — трем.

Слайд 4

Описание слайда:

Теорема о числе булевых векторов Теорема. Число различных булевых векторов длины n равно 2n . Доказательство (методом математической индукции по длине булева вектора). База индукции. При n = 1 утверждение выполняется (число различных булевых векторов длины 1 равно двум: это 0 и 1). Предположение. Пусть число различных булевых векторов длины n равно 2n . Вывод. К булевым векторам длины n добавим n +1- ю компоненту, присвоив ей сперва значение 0 (получим 2n векторов длины n +1), затем — значение 1 (получим еще 2n векторов длины n +1), т.е. всего 2n + 2n = 2n+1 различных векторов длины n +1. ЧТД.

Слайд 5

Описание слайда:

Представление булевыми векторами подмножеств

Слайд 6

Описание слайда:

Пара булевых векторов Рассмотрим булевы векторы  = a1 a2 ... an и  = b1 b2 ... bn . Говорят, что булевы векторы  и  ортогональны по i‑й компоненте, если ai  bi . Пример. Булевы векторы  = 1010 и  = 1000 ортогональны по 3-й компоненте. Расстоянием между булевыми векторами (расстоянием по Хэммингу) называют число ортогональных компонент в данной паре векторов. Пример. Расстояние по Хэммингу между булевыми векторами  = 1010 и  = 1001 равно двум. Булевы векторы называются соседними (соседями), если они ортогональны по одной и только одной компоненте. Пример. Булевы векторы  = 1010 и  = 1000 соседние. Булевы векторы называются противоположными (антиподами), если они ортогональны по всем компонентам, т.е. расстояние по Хэммингу между булевыми векторами равно их длине. Пример. Булевы векторы  = 1010 и  = 0101 противоположные.

Слайд 7

Описание слайда:

Пара булевых векторов

Слайд 8

Описание слайда:

Булево пространство и способы его представления Булевым пространством B n размерности 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 (коды столбцов).

Слайд 9

Описание слайда:

Пример матрицы Грея Пусть n = 5 . На левой матрице показан процесс построения кодов столбцов. Выделенная клетка задает булев вектор 10011. Договоримся изображать коды условно: 1 – черточкой, 0 – ее отсутствием. Такой код более нагляден и быстрее рисуется. Код Грея обладает свойством симметрии. Места смены значений компонент называются осями симметрии компонент. Каждая ось имеет свою зону симметрии, т.е. область, на которую распространяется ее действие: зоной симметрии осей младших компонент строк и столбцов (в примере: первой и третьей) является вся матрица; зонами симметрии осей следующих компонент (в примере: второй и четвертой) являются половины матрицы; и так далее (с каждым разом размер зоны уменьшается в два раза).

Слайд 10

Описание слайда:

Интервал в булевом пространстве

Слайд 11

Описание слайда:

Крайние случаи. Мощность интервала Крайние случаи: I (010, 010) = 010, границы интервала совпадают, он состоит из одного булева вектора, ранг r = 3, размерность s = 0; 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.

Слайд 12

Описание слайда:

Алгоритм распознавания интервала

Слайд 13

Описание слайда:

Соседние интервалы Интервалы 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 по первой компоненте).

Слайд 14

Описание слайда:

Способы представления интервалов Мы уже пользовались тремя способами представления интервалов. 1) Границами интервала. 2) Явным перечислением всех векторов, образующих интервал. 3) Троичным вектором. 4) Матрица Грея. Булево пространство представляется матрицей, а все булевы векторы (клетки), образующие интервал, выделяются. Чтобы нарисовать интервал, достаточно отметить все строки и все столбцы, коды которых совпадают с заданным интервалом по внешним компонентам — на их пересечении и будет лежать интервал. Пример. I = - 0-10 : отмечаем строки, в кодах которых вторая компонента равна 0 (верхняя и нижняя строки), и столбцы, в кодах которых четвертая компонента равна1, а пятая — 0 (два средних столбца ), — на их пересечении и лежит заданный интервал.

Слайд 15

Описание слайда:

Алгоритм распознавания интервала на матрице Грея Шаг 1: если количество клеток заданного множества A не является целой степень (c) двойки, то A — не интервал, идем на шаг 3. Шаг 2: если множество клеток (A) лежит симметрично относительно c осей симметрии, т.е. его можно “разрезать” осями симметрии на половины, затем каждую половину на четвертины, затем любую четвертину на осьмушки и так далее до тех пор, пока множество A не “разрежется” на отдельные клетки, то A — интервал, идем на шаг 3. иначе A — не интервал. Шаг 3: конец.

Слайд 16

Описание слайда:

Примеры На левой матрице интервал I = -0 - - 1 (8 клеток и 3 оси симметрии) , на правой - не интервал (4 клетки, но одна ось симметрии). Частные случаи Очевидно, что интервалами являются следующие множества: каждая отдельная клетка, любая пара симметричных клеток, в том числе, рядом лежащих, любая строка и любой столбец, любая пара симметричных строк или столбцов, в том числе, рядом лежащих, любой “квадрат” размером 22, любая половина или четвертина матрицы, четверка клеток, лежащих в углах матрицы.