Занятие 5

1. Задать таблицей, вектором, графиком и картой Карно булеву функцию:

а) ; б) .

2. Какие аргументы являются существенными, а какие – фиктивными для функции:

а) (0011 1100); б) (0000 0101);

в) (1010 1111 0000 1010)?

3. Подобрать формулу к булевой функции, заданной вектором

а) (0011 1100 0011 1100); б) (0100 0100 0111 0111).

4. Расставить всеми возможными способами скобки в формуле

а) ¬ ; б) .

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

а) ; б) .

6. Получить вектор суперпозиции:

а) , где f = (1011), g = (1001);

б) , где f = (0011), g = (0100).

7. Решить систему булевых уравнений:

а) б)

8. Сколько разных булевых функций от n аргументов удовлетворяют равенству:

а) ;

б) ?

Занятие 6

1. Для указанной функции написать СДНФ:

а) f = (0110 1011); б) f = (0100 1110).

2. Для указанной функции написать СКНФ:

а) f = (1001 0100); б) f = (1110 0011).

3. Упростив формулу, найти эквивалентную ей ДНФ и КНФ:

а) ; б) .

4. На единичном кубе и карте Карно изобразить множество N_f для функций:

а) , , , ;

б) , , .

5. С помощью карты Карно минимизировать ДНФ и КНФ для функции:

а) (0101 0100); б) (1110 0010 0011 0000);

в) (1011 1100); г) (0001 0001 0011 0011).

6. Найти полином Жегалкина для функции:

а) (0110 1011); б) ;

в) (1010 0101 1111 0000); г) .

7. Каким классам принадлежит функция

а) f = (0110 0110); б) f = (1001 0110);

в) f = (0011 0011 0111 0111)?

8. Можно ли функцию f выразить формулой через функции g и h, если

а) f = (0101 1100), g = (0101), h = (1100);

б) f = (0110), g = (0011), h = (0101)?

Занятие 7

1. Доопределить функцию f так, чтобы она была несамодвойственной

а) f = (01*01*01); б) f = (1*001*10).

2. Показать, что данная функция несамодвойственна, и получить из неё константу

а) ;

б)

3. Доопределить функцию f  так, чтобы она была монотонна

а) f = (001* 0***); б) f = (010* ****).

4. Показать, что функция из задания №2 немонотонна, и получить из неё отрицание.

5. Показать, что функция из задания №2 нелинейна, и получить из неё конъюнкцию или дизъюнкцию.

6. Полна ли система функций

а) ; б) ;

в) {(1100), (1001)}; г) {(10), (0110)}?

7. Найти число функций от n аргументов во множестве

а) ; б) ;

в) .

8. Используя минимальную ДНФ или КНФ, построить СФЭ для булевой функции:

а) (0000 1110 0000 1110); б) (0010 0010 0111 0111).

Занятие 8

1. Построить схему со свойством префикса (суффикса) в трехбуквенном кодирующем алфавите {a,b,c} с длинами кодовых слов:

а) 1,1,2,2,3,3,3; б) 1,2,2,2,2,2,3,3.

Существует ли однозначно декодируемая схема с теми же длинами кодовых слов в двухбуквенном алфавите?

2. Даны длины кодовых слов:

а) 1,1,2,2,2,3,3,3; б) 1,1,1,2,2,2,3,3,3.

Каково должно быть минимально возможное количество букв в кодирующем алфавите, чтобы схема была однозначно декодируемой?

3. Будет ли однозначно декодируемой схема Σ:

а) {ab, dc, a, bcadd, ca};

б) {ddac, dd, cddab, a, cddd, b};

в) {a, ab, acbb, abb, bbacc};

г) {ab, bb, ca, cba, abb, bac, aabc, cabba}?

Если нет, то найти слово, которое декодируется неоднозначно. Чему равен параметр N_Σ из теоремы Маркова?

4. В двухбуквенном кодирующем алфавите {0,1} и трехбуквенном алфавите {a,b,c} построить код Хаффмана, если заданы частоты букв исходного алфавита:

а) 0.4, 0.4, 0.1, 0.03, 0.03, 0.02, 0.02;

б) 0.6, 0.1, 0.09, 0.08, 0.07, 0.06.

Какова средняя длина кодового слова полученных схем? Какая была бы длина кодовых слов при равномерном кодировании в том же алфавите?

5. Двоичный код задан характеристической функцией

а) ; б) .

Найти его мощность и кодовое расстояние.