alekseev дискретная математика 2012

7)f x1 x2 x4 x1 x2 x3 x4 ;

8)f x1 x2 x3 x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3 x4 x1x2 .

7)~f 10 0 1 110 ;

8)~ f 1 0 110 .

~n

6.29.Найти число функций f (x ) , принадлежащих множеству А:

6.30.Доказать, что L T0 T1 L S T0 L S T1 L S T0 T1.

6.31.Доказать, что L T1 T0 S .

6.32.Доказать, что множество A не пусто:

1)A LT1 (T0 S) ;

2)A LT0 (T1 S) ;

3)A LS (T1 T0 ) .

~n

6.33.Какие функции можно получить из функции f (x ) путем

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

6.35.Выяснить, полна ли система функций. Если полна, то проиллюстрировать поэтапное доказательство теоремы Поста, т. е. получить через суперпозицию функций из этой системы константы, отрицание и конъюнкцию.

1)x yz , x( y z) , xy yz ;

2)(xy xz) yz , x y , x xy , x y ;

3)xy xz yz , xy z , (xy xz) y z ;

4)xy xz , xy z , x y ;

5)xz x y yz , (x y xz) yz , x yz xz ;

6)x xz , xz x y , x y , x y ;

7)x y , x y , x y , 0 .

6.36.Выяснить, полна ли система A функций, заданных векторами своих

значений:

1)A f1 0110 , f2 1100 0011 , f3 1001 0110 ;

2)A f1 0111 , f2 01011010 , f3 01111111 ;

3)A f1 0111 , f2 10010110 ;

4)A f1 0101 , f2 11101000 , f3 01101001 ;

5)A f1 1001 , f2 11101000 ;

6)A f1 11 , f2 0111 , f3 00110111 ;

7)A f1 10 , f2 00110111 .

6.37.Из полной системы функций A выделить всевозможные базисы:

1)A 1, x, x y x y , x y x y yz xz ;

2)A 0, x y, x y, x y xz ;

3)A 0,1, x y z, x y xz yz, x y z, x y ;

52

4)A x y, x y, x y z, x y, x y ;

5)A x y x z, x, x y, 0, x yz .

1)f S M , g L S , f g 1;

2)f T0 L , g S , f g 1;

3)f T 0 T1 , g M T1, f g 1 ;

4)f SL T0 , g M T0 , f g 1?

6.40.Привести примеры базисов, содержащих одну, две, три и четыре функции.

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

6.42.Найти все функции Шеффера от двух переменных.

6.43.Доказать, что если f T0 T1 S , то f – функция Шеффера.

6.44.Сколько существует функций Шеффера от n переменных?

6.45.Верно ли, что если f L S M , то f полна?

6.46.Опровергнуть, что

1)если f (T0 T1) S , то f L M ;

2)если f T0 T1 M , то f – функция Шеффера;

3)если f T0 S M , то f L T1 S M ;

4)если f L S M , то f – функция Шеффера.

6.47.Выяснить, полна ли система функций A? В случае положительного ответа, привести пример полной системы функций из множества A.

1)A P2 (T0 T1 L S M ) ;

2)A (M T0) (L S) ;

53

3)A S M L M ;

4)A L T0 T1 S T0 T1 ;

5)A L T1 S M ;

6)A L T1 S T0 ;

7)A (M T0) (S L) .

6.48.Пусть f , g, h – попарно различные функции, существенно зависящие от двух переменных. Будет ли полной система функций x, f , g, h ?

6.49.Доказать, что имеют место следующие включения:

6.50. Проверить, что если U P2 (множество всех функций алгебры логики), то на диаграмме Венна для системы замкнутых классов T0 , T1, S, M, L пустыми будут в точности те клетки, которые в табл. 3 помечены символом .

54

9)f x y , g xy xz yz ;

10)f x y , g xy xz yz .

55

7. Элементы теории кодирования

где vi A - элементарный код, соответствующий букве bi B ( i 1, n ).

Тогда каждому слову языка bi1 bi2 ... bim ставится в соответствие кодовое слово,

определяемое по правилу:

fv ( bi1 bi2 ...bim ) fv (bi1 ) fv (bi2 )... fv (bim ) vi1 vi2 ...vim .

Схема алфавитного кодирования fv задает код V v1, v2 ,..., vn , представляющий собой упорядоченное множество элементарных кодовых слов

длина элементарного кода vi , называется спектром длин кода V .

К основным требованиям, предъявляемым к алфавитному кодированию, относится прежде всего взаимная однозначность кодирующего отображения

56

fv . Код V называется взаимно однозначным или однозначно декодируемым,

если различным сообщениям языка соответствуют различные кодовые слова. Если слово имеет вид 1 2 , тогда подслово 1 называется префиксом,

а 2 − суффиксом слова .

Префикс (суффикс) слова называется собственным, если он отличен от пустого слова и от самого слова .

Схема алфавитного кодирования fv обладает свойством префикса, если для любых i и j (1 i, j n, i j) слово vi не является префиксом слова v j .

Алфавитное кодирование, схема которого обладает свойством префикса, называется префиксным.

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

Префиксность кода является достаточным условием его взаимной однозначности.

Для всякого однозначно декодируемого кода V в q -буквенном алфавите длины элементарных кодов di | vi | (i 1, n) удовлетворяют неравенству

n

Мак-Миллана: q di 1.

i 1

Неравенство Мак-Миллана является необходимым условием взаимной однозначности кода, но не достаточным.

Пусть набор натуральных чисел d1, d2 , , dn удовлетворяет неравенству

n

Мак-Миллана q di 1, тогда существует префиксный код V v1, v2 ,..., vn

i1

вq -буквенном алфавите со спектром длин d V d1, d2 ,..., dn .

Для всякого однозначно декодируемого кода V в q -буквенном алфавите со спектром длин d V d1, d2 ,..., dn существует префиксный код с тем же набором длин элементарных кодов и в том же кодирующем алфавите.

57

Стоимость кода V определяет среднюю длину его элементарного кода и показывает, во сколько раз увеличивается средняя длина слова при кодировании сообщений кодом V .

Алфавитный код V o называется оптимальным, если

является ли слово кодом некоторого сообщения. В случае положительного ответа, выяснить является ли кодом ровно одного сообщения.

7.2.Выяснить, обладает ли код V свойством префикса:

1)V = {0, 10, 11, 1110};

2)V = {01, 11, 10, 001};

3)V = {1001, 000, 001, 0110, 010, 1000, 0111};

4)V = {110, 011, 1011, 0100, 11011};

5)V = {02, 2, 11, 012, 102, 011, 0121};

6)V = {12, 22, 0011, 101, 0100, 20, 2100};

7)V = {0, 10, …, 1n0 , …};

58

8)V = {0, 10, …, 10n , …}.

7.3.Выяснить, обладает ли схема алфавитного кодирования:

а 111,в 10101,г 010,л 001,о 000,с 110

свойством префикса. Справедливо ли неравенство Мак-Миллана для спектра длин заданного кода? С помощью кода, задаваемого схемой,

1)закодируйте слово слава;

2)закодируйте слово голоса;

3)декодируйте слово 110001000010;

4)декодируйте слово 10101000001000110;

5)декодируйте слово 01000000100010101111.

7.4.Выбрать максимальное по числу элементов подмножество B множества A с условием, что двоичные разложения наименьшей длины чисел из B представляют собой префиксный код:

1)A = {1, 5, 6, 7, 12, 13, 17};

2)A = {1, 3, 6, 8, 10, 13, 19, 33, 37};

3)A = {2, 6, 7, 9, 12, 15, 18, 35, 36, 37};

4)A = {2, 3, 7, 8, 11, 12, 13, 14};

5)A = {1, 2, 5, 8, 9, 10, 13, 15};

6)A = {3, 5, 6, 9, 10, 13, 17};

7)A = {1, 2, 5, 8, 9, 12, 13, 14};

8)A = {5, 6, 7, 8, 9, 10, 11, 12, 13};

9)A = {4, 6, 7, 10, 13, 15, 20, 23, 25};

10)A = {5, 7, 9, 10, 12, 14, 17, 23, 24}.

7.5.С помощью неравенства Мак-Миллана выяснить, может ли набор чисел L быть набором длин элементарных кодовых слов двоичного взаимно однозначного кода:

59

7.7.Для заданного распределения вероятностей P с помощью алгоритма Хаффмана построить оптимальный двоичный код:

1)P = (0,2; 0,4; 0,2; 0,2);

2)P = (0,1; 0,1; 0,7; 0,1);

3)P = (0,2; 0,2; 0,2; 0,2; 0,2);

4)P = (0,08; 0,03; 0,09; 0,1; 0,5; 0,2);

5)P = (0,3; 0,4; 0,06; 0,08; 0,04; 0,04; 0,04; 0,04);

6)P = (0,3; 0,3; 0,03; 0,03; 0,03; 0,03; 0,03; 0,01; 0,2; 0,04);

7)P = (0,06; 0,06; 0,06; 0,06; 0,06; 0,3; 0,2; 0,1; 0,1);

8)P = (0,1; 0,2; 0,4; 0,05; 0,05; 0,05; 0,05; 0,05; 0,05);

9)P = (0,25; 0,15; 0,05; 0,1; 0,2; 0,1; 0,05);

10)P = (0,11; 0,08; 0,01; 015; 0,25; 0,21; 0,09; 0,1).

7.8.Выяснить, является ли код оптимальным для распределения вероятностей

P = (0,15; 0,25; 0,05; 0,01; 0,09; 0,25; 0,15; 0,05):

1)V = (001; 010; 10; 11; 101; 011; 0110; 00);

2)V = (0000, 001; 1001; 10010; 0111; 111, 0010, 1110);

3)V = (000; 001; 010; 011; 100; 101; 110; 111);

4)V = (100; 00; 11110; 11111; 1110; 01; 101; 110);

5)V = (000; 01; 1110; 11111; 110; 10; 001; 11110);

6)V = (000; 10; 0111; 01111; 011; 01; 100; 11111);

7)V = (01; 02; 10; 12; 20; 21; 22; 00).

60