С2.МОИ.План занятий (с теорией и задачами)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

имени Н. Э. БАУМАНА

Факультет ¾Информатика и системы управления¿

Кафедра ИУ8 ¾Информационная безопасность¿

Жуков Д. А.

План семинарских занятий

по курсу ¾Информатика¿

(2 семестр)

Москва 2009

Семинары 1–2

Элементы геометрии булева куба

Двоичный набор. Вес и номер набора. Расстояние между наборами. Аксиомы метрики. Метрика Хемминга и её свойства. Соседние и противоположные наборы.

Булев куб как метрическое пространство. Число наборов в нём, его изображение на плоскости. Слой номера k. Число наборов в слое {0, 1}nk . Шар Br(α˜) и сфера Sr(α˜) радиуса r с центром α˜ в кубе размерности n, число наборов в них. Грань (подкуб) размерности l в кубе размерности n.

Задачи

1.Привести пример слоя, являющегося сферой.

2.Найти число пар соседних наборов в кубе размерности n.

3.Найти число пар соседних наборов из слоёв с номерами k и k + 1 в кубе размерности n.

4.В кубе размерности n найти число всех k-мерных граней.

5.Сколько различных k-мерных граней проходит через данную точку α˜ {0, 1}n?

6.Найти число наборов веса w в сфере Sr(α˜) {0, 1}n, если известны размерность n, радиус r

ивес центра сферы a = kα˜k.

7.Доказать, что расстояние между двумя произвольными точками сферы чётно.

8.Сколько точек может лежать в пересечении двух различных сфер единичного радиуса в кубе размерности n?

9.В кубе размерности n дана сфера радиуса r. Найти число неупорядоченных пар точек на сфере, расстояние между которыми равно d.

Найти число наборов из пересечения двух сфер 1 r и 2 r ˜ в кубе размерно-

10. S = S 1 (α˜) S = S 2 (β)

˜

сти n. Например, α˜ = 111110000000000, β = 111111111110000, r1 = 8, r2 = 4.

11 . Код Грея. Предложить какой-нибудь алгоритм, выписывающий все двоичные наборы длины n так, чтобы любые два выписанных подряд набора были соседними.

наборов.

13. Доказать, что булев куб {0, 1}n является линейным векторным пространством над полем Z2.

14 . Найти в кубе {0, 1}n число всех а) одномерных подпространств; б) двумерных подпространств; в) k-мерных подпространств; г) k-мерных подпространств, проходящих через фиксированную вершину.

где d(xi, xj) расстояние Хемминга между xi и xj.

1

Семинары 3–4

Элементы геометрии булева куба 2

Сравнимые и несравнимые двоичные наборы.

Расстояние между множествами в метрическом пространстве.

Задачи

1. Привести пример пары противоположных сравнимых наборов. Привести пример сферы, в которой каждый набор сравним с её центром.

наборов сравнимо с набором и несравнимо с набором ˜?

α˜ β

5. Дана сфера S = Sr(α˜), α˜ = 111110000000. Найти число наборов из сферы S, сравнимых с её центром. Рассмотреть случаи r = 4 и r = 10.

Сколько существует пар наборов , ˜ в кубе размерности , таких, что ˜ и 6 ˜?

6. α˜ β n α˜ 6 β α˜ = β

7. Найти количество двоичных наборов α˜ = (α1, . . . , αn), таких, что α1 + . . . + αn = 1 mod 2.

8. Верно ли, что всякое множество A {0, 1}n, содержащее не менее n + 2 наборов, содержит пару несравнимых наборов?

9 . Множество двоичных наборов A из куба {0, 1}n называется цепью, если любые два набора из множества A сравнимы, и антицепью, если любые два набора из A несравнимы.

a)Найти в кубе {0, 1}n число цепей длины n + 1.

b)Найти в {0, 1}n число цепей длины n+1, проходящих через фиксированную вершину веса k.

c)Показать, что произвольная цепь и произвольная антицепь имеют не более одной общей

вершины.

В кубе размерности даны две сферы R и R ˜ . Известны их центры , ˜ и радиусы

10 . n S 1 (α˜) S 2 (β) α˜ β

R1, R2. Определить, какое число наборов из пересечения сфер имеет вес k.

В кубе размерности даны две сферы 1 R и 2 R ˜ . Расстояние между

11. n S = S 1 (α˜) S = S 2 (β)

их центрами равно d. Чему равно расстояние между сферами? Какое число пар точек из сфер S1 и S2 лежит на крачайшем расстоянии друг от друга? Рассмотреть три случая для центров

˜

α˜ = 11111000000000000000, β = 11111111111111110000:

13 . Представить n-мерный булев куб при n = 2m −1, m > 1, как объединение непересекающихся шаров единичного радиуса. Доказать, что при всех иных n такое представление невозможно.

2

Семинары 5–6

Функции алгебры логики

Булевы функции и способы их задания: таблица истинности, вектор значений, помеченный булев куб. Значение функции на наборе.

Основные булевы функции: константы 0 и 1, отрицание, конъюнкция, дизъюнкция, импликация, сумма по модулю 2 (исключающее или), эквивалентность, штрих Шеффера, стрелка Пирса. Формула над множеством связок { , &, , →, , , |, ↓}. Функция, реализуемая формулой. Подформула. Правила Де Моргана.

Вес функции. Равновесные (уравновешенные) функции. Существенные и фиктивные переменные. Равенство функций. Тождественные функции. Двойственная к функции f функция f . Самодвойственная функция, свойство её вектора значений.

Элементарная конъюнкция и элементарная дизъюнкция, отвечающие набору σ˜. Нормальные формы булевой функции: совершенная дизъюнктивная (СДНФ) и совершенная конъюнктивная (СКНФ).

Задачи

1.Найти существенные и фиктивные переменные у функций f = (1011101100100010) и g = (0101101001011010).

2.Какие из связок &, , →, , , |, ↓ обладают свойствами коммутативности и ассоциативности?

3.Найти вектор значений функции f, заданной формулой. Указать её вес и вектор двойственной функции. Выписать СДНФ и СКНФ для f и f . Выяснить, какие переменные существенные, какие

фиктивные.

а) ((x1 → x2) → x2x3) → (x1 → (x2 → x3))

б) ((x1x2) ↓ (x2 x3)) | (x2 → (x1 x3))

в) ((x1 x2 x3) x1x3) | (x1 (x2 ↓ x3))

г) ( x1x2x3 → (x2 x3)) ↓ (x2 (x1 x3))

д) (x1 ↓ x3) → ((x2 → x4) ↓ (x1 | x3))

4.Доказать, что (f ) = f для всякой f.

5.Доказать, что всякая самодвойственная функция равновесна.

6.Пусть xi существенная переменная функции f(x1, . . . , xn). Доказать, что xi существенная переменная функции f .

7.Принцип двойственности. Записать какую-нибудь формулу, реализующую функцию f , не находя вектора её значений, если f = (x1x2 x3)(x2 (x1 | x3)).

8.Доказать, что если функция f имеет k фиктивных аргументов, то её вес kfk делится на 2k, и что обратное утверждение неверно.

9 . Найти число функций от n переменных, среди которых ровно k существенных.

3

Семинары 7–8

Функции алгебры логики

Булевы функции и способы их задания: таблица истинности, вектор значений, помеченный булев куб. Значение функции на наборе.

Основные булевы функции: константы 0 и 1, отрицание, конъюнкция, дизъюнкция, импликация, сумма по модулю 2 (исключающее или), эквивалентность, штрих Шеффера, стрелка Пирса. Формула над множеством связок { , &, , →, , , |, ↓}. Функция, реализуемая формулой. Подформула. Правила Де Моргана.

Вес функции. Равновесные (уравновешенные) функции. Существенные и фиктивные переменные. Равенство функций. Тождественные функции. Двойственная к функции f функция f . Самодвойственная функция, свойство её вектора значений.

Элементарная конъюнкция и элементарная дизъюнкция, отвечающие набору σ˜. Нормальные формы булевой функции: совершенная дизъюнктивная (СДНФ) и совершенная конъюнктивная (СКНФ).

Алгебраическая нормальная форма булевой функции (АНФ, полином Жегалкина). Теорема Жегалкина. Алгоритмы нахождения АНФ: метод алгебраических преобразований и метод неопределённых коэффициентов.

Задачи

1. Найти существенные и фиктивные переменные у функций f = (1011101100100010) и g = (0101101001011010).

2.Какие из связок &, , →, , , |, ↓ обладают свойствами коммутативности и ассоциативности?

3.Найти вектор значений функции f, заданной формулой. Указать её вес и вектор двойственной функции. Выписать СДНФ, СКНФ и АНФ для f и f . Выяснить, какие переменные существенные,

какие фиктивные.

а) ((x1 → x2) → x2x3) → (x1 → (x2 → x3))

б) ((x1x2) ↓ (x2 x3)) | (x2 → (x1 x3))

в) ((x1 x2 x3) x1x3) | (x1 (x2 ↓ x3))

г) ( x1x2x3 → (x2 x3)) ↓ (x2 (x1 x3))

д) (x1 ↓ x3) → ((x2 → x4) ↓ (x1 | x3))

4.Доказать, что (f ) = f для всякой f.

5.Доказать, что всякая самодвойственная функция равновесна.

6.Пусть xi существенная переменная функции f(x1, . . . , xn). Доказать, что xi существенная переменная функции f .

7.Принцип двойственности. Записать какую-нибудь формулу, реализующую функцию f , не находя вектора её значений, если f = (x1x2 x3)(x2 (x1 | x3)).

8.Доказать, что если функция f имеет k фиктивных аргументов, то её вес kfk делится на 2k,

ичто обратное утверждение неверно.

9.Решить систему

x y z = xy,

((y → z) → (x → z)) → (y → z) = 0.

4

Семинары 9–10

Формулы и нормальные формы

Подфункция булевой функции. Степень функции. Линейные функции.

Определение формулы (суперпозиции) над множеством булевых функций. Подформула. Операция замыкания множества булевых функций и её свойства. Замкнутый класс. Полнота.

Задачи

1.Найти полиномы всех основных (элементарных) двуместных функций.

2.Пусть f = (10111010), g = (01110010), h = (11110101). Найти АНФ этих функций и двойственных к ним.

3.Найти АНФ(f) и АНФ(f ) для всех функций f из задачи 3 семинара 4.

4.Доказать, что всякая линейная функция либо является константой, либо является равновесной. Привести пример нелинейной равновесной функции.

5.Найти степень функции f = (01000010) не вычисляя её АНФ.

6.Функции f, g и h представлены векторами значений (см. задачу 2). Вычислить функции, заданные следующими формулами над системой {f, g, h} и найти их АНФ:

а) f(x2, x3, x1),

б) f(x1, g(x1, x2, x3), x3),

в) f(x3, g(x1, x2, x1), h(x1, x2, x3)),

г) g(h(x1, x2, x3), h(x3, x2, x1), f(x1, x2, x3)), д) g(x2, h(x1, x1, x1), f(x1, x2, g(x1, x2, x1))).

7. Найти количество всех функций степени 3 из P2(n), n > 3.

8. Найти [A], если а) A = {x, xy}, б) A = {x, x y}, в) A = {x | y}, г) A = {1, x y}, д)

A = {1, x y, xy}, е) A = {x ↓ y}, ё) A = {x → y, x y}, ж) A = {x → y, x}.

9.Является ли множество A = {f P2 : deg f 6 2} замкнутым классом? [A] =?

10 . Подсчитать число наборов α˜ = (α1, . . . , αn), для которых f(α˜) = 1, если f = ((. . . ((x1 → x2) → x3) → . . .) → xn).

11 . Подсчитать число наборов, для которых f(α˜) = 1, если f = x1x2 x2x3 . . . xn−1xn.

12.Является ли функция f1 подфункцией функции f2, если f1 = x3, f2 = ((x1 → x2) x3) x3.

13.Доказать, что если f(x1, . . . , xn) существенно зависит от всех переменных x1, . . . , xn, то для любого k, 1 6 k 6 n, найдётся подфункция функции f, существенно зависящая ровно от k переменных.

14.Доказать, что переменная является существенной для булевой функции, тогда и только тогда, когда она входит в её полином Жегалкина.

15.Функция называется симметрической, если она не меняется при любой перестановке своих аргументов. Найти число n-местных симметрических функций. Является ли множество всех симметрических булевых функций замкнутым классом? Почему?

16 . Доказать, что всякая функция f = f(x1, x2, x3) трёх аргументов получается из некоторой симметрической функции g = g(x1, x2, . . . , x7) семи аргументов отождествлением переменных функции g.

17 . Пусть B произвольный шар радиуса k в кубе размерности n. Доказать, что всякая булева функция f : {0, 1}n 7→ 0{, 1} степени не более k однозначно определяется своими значениями на шаре B. Например, пусть известно, что f = (1*101101**0*0*10) и deg f = 2. Найти вектор значений f и её АНФ.

5

Семинары 11–12

Основные замкнутые классы булевых функций

Классы T0, T1, S, L, M. Их замкнутость относительно операции суперпозиции. Способы определения принадлежности функции основным замкнутым классам. Леммы о несамодвойственной, немонотонной и нелинейной функциях.

Задачи

1.Доказать по определению, что каждое из множеств T0, T1, S, L и M замкнуто.

2.Все функции из задачи 3 семинара 3 и двойственные к ним проверить на принадлежность основным замкнутым классам.

3.Покажите, что пересечение любых замкнутых классов всегда замкнуто. Например, [L ∩ S] = L ∩ S.

4.Является ли множество L M замкнутым классом? Верно ли, что [L M] = P2?

5.Проверить равенства: [M1 M2] = [M1] [M2] и [M1 ∩ M2] = [M1] ∩ [M2], где M1, M2 P2

произвольные подмножества.

6.Привести пример двух замкнутых классов, объединение которых также является замкнутым классом.

7.Какое из равенств верно: L ∩ S ∩ T0 = L ∩ S ∩ T1 = L ∩ T0 ∩ T1 ?

8.Покажите, что всякая линейная функция либо сохраняет константу, либо является самодвойственной, то есть L T0 T1 S. Приведите пример функции из множества T0 T1 S, которая не является линейной.

9. Доказать, что M T0 T1.

10.Показать, что двойственная к монотонной функция также монотонна.

11.Верно ли утверждение: функция f принадлежит множеству (T0 T1) \ L тогда и только тогда, когда этому множеству принадлежит двойственная функция f ?

12.Найти количество n-местных функций из множеств T0, T1, S и L. Найти число монотонных функций от двух, трёх и четырёх аргументов.

13.Найти мощность множеств L \ M(n) и L 4 T1(n).

14.Показать, что число одночленов в АНФ каждой монотонной функции нечётно.

15 . Набор α˜ {0, 1}n называется нижней единицей монотонной функции f(x1, . . . , xn), если

значно восстанавливается по множеству своих нижних единиц. (Например, найти вектор значений функции f, если 0100 и 1010 её нижние единицы.)

16 . Пусть f n-местная функция, принимающая значение 1 на наборе веса k тогда и только тогда, когда k 6= 0 mod 3. Найти число слагаемых в АНФ(f).

17 . Пусть A B S и [A {1}] = [B {1}]. Доказать, что [A] = [B]. 18 . Пусть A P2(n), причём |A| > 22n−1. Докажите, что [A] = P2.

19. Доказать, что f L тогда и только тогда, когда f меняет значение на любой паре соседних по существенной компоненте наборов.

20 . Перечислить все существующие таблицы принадлежности булевых функций основным замкнутым классам (например, не существует такой функции f P2, что f / T0, f / T1, f S, f L и f M).

21 . Сколько существует n-местных монотонных функций веса 2n − 8 ?

22 . Доказать, что log2 |M(n)| > Cn/n 2 при чётном n.

23 . Доказать, что |M(n)| 6 |M(n − 1)|2.

6

Семинары 13–14

Теорема Поста

Полнота системы функций в P2. Базис. Критерий полноты системы функций алгебры логики в P2 (¾малая¿ теорема Поста). Шефферовы функции.

Предполный класс. Замкнутость предполных классов. Представление о ¾большой¿ теореме Поста.

Задачи

1. Перечислить все замкнутые классы одноместных функций. Можно ли представить P2 в виде объединения двух непересекающихся замкнутых классов? А трёх?

2. Является ли система функций полной в P2 (если нет, то дополнить её до базиса): а) {x, x y, 0}, б) {x, x y, 1}, в) {x, x y, 1}, г) {x, x y, xy}, д) {x y, x → y, 0}, е) {xy xz yz, x}, ё) {xy xz yz}, ж) {x y z, x}, з) {(x → y) → z}, и) {(x ↓ y) ↓ z}.

3. Доказать, что теоретико-множественные операции разности \ и симметрической разности 4 двух множеств не выражаются через пересечение ∩ и объединение . Можно ли выразить разность через симметрическую разность и обратно?

4. Принадлежит ли функция f замыканию множества A:

а) f = x → y, A = {x, x y, x y z, 0, 1},

б) f = x y, A = {x, x y z, xy yz xz},

в) f = x y, A = {x y z, x y z},

г) f = xy, A = {x y, x y},

д) f = (01010111), A = {0, 1, xy, x y}.

5.Выразима ли x y через x → y? А наоборот?

6.Показать, что функция f шефферова тогда и только тогда, когда f не сохраняет константы

инесамодвойственная.

7.Доказать, что функция f шефферова тогда и только тогда, когда f шефферова. Вывести отсюда, что число n-местных шефферовых функций всегда чётно.

8.Найти число шефферовых функций n аргументов.

9.С помощью суперпозиции из функции f можно получить константы 0 и 1. Верно ли, что fшефферова?

10.Доказать, что из любой шефферовой функции, которая существенно зависит от n > 3 переменных, можно переименованием и отождествлением переменных получить одну из функций x | y, x ↓ y.

11.Пусть функция f монотонна и существенно зависит от не менее чем двух переменных. Доказать, что система {0, f} является полной в P2. Всегда ли функция f шефферова?

12.Пусть функция f монотонна и имеет ровно две нижних единицы. Верно ли, что функция f

шефферова?

13.Проанализировав доказательство теоремы Поста, докажите, что всякий базис в P2 состоит не более чем из четырёх функций. Приведите примеры базисов в P2, состоящих из одной, двух, трёх и четырёх функций.

14 . Привести примеры базисов в замкнутых классах T0, T1, S, L и M.

15 . Привести примеры базисов в замкнутых классах T0, T1, S, L и M, состоящих из одной, двух, трёх и четырёх функций. Если привести пример какого-нибудь базиса не удаётся, то доказать его отсутствие.

16 . Указать базисы замкнутых классов A ∩ B, где A, B всевозможные пары множеств T0,

T1, S, L, M.

7

Семинары 15–16

Контактные схемы. Схемы из функциональных элементов.

Контактная схема. Схема из функциональных элементов (СФЭ). Функция, реализуемая схемой. Сложность контактной схемы. Сложность и глубина СФЭ.

Минимальная схема. Сложность функции. Функция Шеннона.

Основные методы синтеза. Метод каскадов и метод Шеннона. Различные оценки функции Шеннона.

Задачи

1. Построить методом каскадов контактную схему для функции

а) (x (xy z)) yz,

б) (x y)(z xw) x(z w),

в) f = ((. . . ((x1 → x2) → x3) → . . .) → xn) → x1, г) f = x1 x2 . . . xn,

д) f(x1, . . . , xn) = 1 x1 + x2 + . . . + xn = 0 mod 3, е) f(x1, . . . , xn) = 1 x1 + x2 + . . . + xn = 0 mod 6,

ж) f(x1, . . . , x2n) = 1 x1 + . . . + xn = 0 mod 3 и xn+1 + . . . + x2n = 0 mod 2.

2. Построить методом каскадов контактную схему для функции f и доказать её минимальность.

f(x1, . . . , xn) = 1 x1 = x2 = . . . = xn

3.Верно ли, что функции f и f всегда имеют одинаковую сложность при реализации контактными схемами?

4.Пусть A P2 и g A : g A. Доказать, что f P2 : LA(f) = LA(f ).

5.Привести пример такого множества A 6= A и такой функции f, что LA(f) 6= LA(f ).

6.Найти сложность реализации функции в данном базисе функциональных элементов (предъявить вычисляющую функцию схему и доказать её минимальность):

7.Доказать, что

а) L{&, }(x1 . . . xn) = 2n, б) L{ , }(x1& . . . &xn) = 2n.

8. Пусть A некоторое полное в P2 множество. Найти LA(P2(n)) минимальную сложность реализации одной схемой всех 22n функций от переменных x1, . . . , xn.

9. В базисе P2(2) построить схему сумматор двух n-разрядных чисел (у этой схемы 2n входов, на которые подаются разряды слагаемых, и (n + 1) выход, на которых появляются вычисленные разряды их суммы). Сложность сумматора должна быть линейна по n.

10 . Построить сумматор из предыдущей задачи так, чтобы его сложность не превышала c1n, а глубина c2 log2 n, где c1, c2 некоторые не зависящие от n константы.

8