Утверждение о соседних интервалах

Два соседних интервала ранга r (размерности s) не пересекаются, а их объединение образует интервал ранга r -1 (размерности s +1).

Доказательство. Соседние интервалы I₁ и I₂ не пересекаются, как так их ортогональная компонента во всех векторах одного интервала равна 0, а в векторах другого равна 1. Мощность объединения таких интервалов равна сумме их мощностей: / I / = / I₁ È I₂ / = / I₁ / + / I₂ / = 2^s + 2^s = 2^s+1, т.е. она оказывается целой степенью двойки (s+1-й). Количество компонент в векторах множества I , претендующих быть внутренними, тоже равно s +1, так как к s внутренним компонентам интервалов I₁ и I₂ добавляется еще одна, ортогональная, компонента. Это равенство означает, согласно рассмотренному ранее алгоритму, что множество I образует интервал размерности s +1 (ранга r -1, так как r + s = n ).

Определение.Операцию объединения двух интервалов I₁ и I₂, соседних по i – й компоненте, назовем склеиванием интервалов i-ой компоненте, а результат их склеивания I = I₁ È I₂ - расширением каждого из интервалов I₁ и I₂ по i – й компоненте.

Пример.Соседние интервалы ранга 3 склеивания, образуя интервал I = 0 - - -1 ранга 2 (он является расширением интервалов I₁ и I₂ по третьей компоненте).

Очевидно, что на матрице в коде Грея соседние по i-й компоненте интервалы располагаются симметрично относительно оси симметрии этой компоненты.

6. Алгоритм распознавания интервала, заданного перечислением векторов.

Задано множество A булевых векторов длины n. Требуется определить, образует ли множество A интервал и, если образует, найти его границы: a, b.

Шаг 1: если мощность множества A не является целой степенью двойки, т.е. |A| ¹ 2^c, где c — целое, то A — не интервал, идем на конец.

Шаг 2: Считаем число s несовпадающих компонент в векторах множества A, т.е. число компонент, претендующих быть внутренними; Если s ¹ c, то A - не интервал, идем на конец; иначе A - интервал, s - его размерность, r=n-s - ранг;

Шаг 3: Находим границы интервала a и b Вектор минимального веса (из всех векторов множества A) является наименьшим элементом интервала (a), а вектор максимального веса — его наибольшим элементом (b), т.е. a и b - границы интервала.

Конец.

Примеры.

А = {010, 011, 001}: множество не образует интервал, так как его мощность, равная 3, целой степенью двойки не является.

А = {010, 011, 001}: множество не образует интервал – мощность является целой степенью двойки, но показатель степени c = 2 не совпадает с количеством компонент s = 3, претендующих быть внутренними (это первая, третья и четвертая компоненты).

А = {010, 011, 001,000}: множество образует интервал, так как его мощность является целой степенью двойки (c=2), и эта степень совпадает с количеством компонент s=2, претендующих быть внутренними (это вторая и третья компоненты). Границы интервала: a = 000, b = 011.

7. Распознавание интервалов на матрице в коде Грея. Типы интервалов.

Начало:задана матрица Грея с отмеченными клетками, которые образуют множество А.

Шаг 1:Если число клеток множества А не являются целой степенью двойки, т.е. |А|¹2^с, то А – не интервал, идем на конец.

Шаг 2:Если множество А лежит симметрично относительно осей симметрии скомпонент (его можно «разрезрезать» осями на симметричные половины, затем четвертины на симметричные осьмушки и так далее до тех пор, пока множество А не «разрежется» на отдельные клетки), то А – интервал, идем на конец, иначе А не интервал.

Конец.

Примеры.

На левой матрице задан интервал – 0 - - 1 (8 клеток и оси симметрии трех компонент), на правой – не интервал (4 клетки и ось симметрии лишь одной компоненты).

Очевидно, что интервалами являются следующие множества:

- каждая отдельная клетка,

- любая пара симметричных клеток, в том числе радом лежащих,

- любая строка и любой столбец,

- любая пара симметричных строк и столбцов, в том числе рядом лежащих,

- любой «квадрат» размером 2x2,

- любая половина или четвертина матрицы,

- четверка клеток, лежащих в углах матицы,

- и не только они.

Определение. Интервал I_max(f) назовем максимальным для булевой функции f (x₁, x₂, ..., x_n), если он является допустимым для этой функции и не существует другого допустимого интервала I (f), такого что I_max(f) Ì I(f), другими словами, если после расширения интервала по любой компоненте он становится не допустимым.

Пример. I₁ (f) = - 1 1 — максимальный интервал,

I₂ (f) = 1 1 1— не максимальный.

8. Булева функция, способы ее задания.

· Определение 1.Функцию f (x₁, x₂, ... , x_n) называют булевой, если каждый ее аргумент есть булева переменная и сама функция — булева переменная.

· Определение 2.Функцию f (x₁, x₂, ... , x_n) называют булевой, если она сама и ее аргументы принимают значения 0 или 1.

· Определение 3.Булевой функцией f (x₁, x₂, ... , x_n) называют однозначное отображение булева пространства Bⁿ в булево множество B, т.е. f: Bⁿ® B.

Пример. Рассмотрим булеву функцию двух аргументов, принимающую на наборах 01 и 10 значение 0, а на наборах 00 и 11 значение 1.

Способы задания булевых функций

1) Таблицей истинности.Так называется таблица, состоящая из двух частей: в левой части пересчитываются все наборы значений аргументов (булевы векторы пространства Bⁿ) в естественном порядке, т.е. по возрастанию значений чисел, представляемых этими векторами, а в первой части – значений булевой функции на соответствующих наборах.

Теорема о числе булевых функций.Число различных булевых функций, зависящих от n переменных, равно .

2) Характеристическими множествами.Так называются два множества:

M¹ (f), состоящее из всех наборов, на которых функция принимает значение 1, и M⁰ ( f ) — из всех наборов, на которых функция принимает значение 0, т.е.

M¹ (f) = {a Î B ⁿ : f (a) = 1}, M⁰ (f) = {a Î B ⁿ : f (a) = 0}.

3) Вектором значений функции:j(f) = f(0,0, ... ,0) f(0,0, ... ,1) ... f(1,1, ... ,1).

4) Матрицей Грея.Булево пространство задается матрицей Грея и наборами, на которых булева функция f(x₁, x₂, ... , x_n) принимает значение 1, отмечаются и называются точками.

Пример.

5) Интервальный способ задания.Булева функция f(x₁, x₂, ... , x_n) задается множеством интервалов I_f={I₁,I₂,…,I_k}, объединение которых образует характеристическое множество M¹(f) .

Пример: [Мажоритарная] функция может быть задана достаточным множеством I_f={I₁,I₂,I₃} интервалов:

Здесь интервалы представлены троичными векторами и изображены на матрице Грея. В отличие от предыдущих, интервальный способ задания функций многовариантен.

6) Формулами. Пример.

9. Существенные и фиктивные переменные. Алгоритмы выявления и удаления фиктивной переменной.

Булева функция f(x₁, x₂, ... , x_i , ... , x_n) существенно зависит от переменной x_i, если выполняется условие:

f (x₁, x₂, ... , x_{i -1}, 0 , x_i+1, ... , x_n) ¹ f (x₁, x₂, ... , x_{i -1}, 1 , x_i+1, ... , x_n).

В этом случае также говорят, что переменная x_i существенная, в противном случае ее называют фиктивной переменной.

Пример. Рассмотрим булеву функцию f (x₁, x₂, x₃) и исследуем ее переменные x₁ и x₃. Из таблиц истинности видно, что переменная x₁ булевой функции f (x₁, x₂, x₃) существенная, так как f (0, x₂, x₃) ¹ f (1, x₂, x₃). Переменная x₃ фиктивная, так как f (x₁, x₂, 0) = f (x₁, x₂, 1).

Не нашли, что искали? Воспользуйтесь поиском по сайту: