Вопросы к зачету часть2 (Вопросы к зачету (ответы))

Полнота систем логических функций 1

17. Реализация булевых функций формулами. Примеры полных систем. 2

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

19. Классы функций: Т0 – сохранения нуля; Т1 - сохранения единицы 2

20. S - самодвойственные функции. 3

21.М - монотонные функции. 4

22.L - линейные функции. 4

Критерий полноты. 5

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

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

25. Доказательство утверждения о нелинейной функции. 5

26. Доказательство критерия о полноте класса функций. 6

Вопросы полноты. 7

Параметры булевых функций. 7

27. Понятие действительного многочлена двоичной функции. Примеры для функций от двух переменных. 7

28. Доказательство теоремы об однозначном представлении двоичной функции в виде действительного многочлена. 8

29. Понятие вероятностной функции двоичной функции. 8

30. Доказательство теоремы о равенстве значений вероятностной функции со значением действительного многочлена от вероятностей р₁,р₂,…,р_n. 10

Спектральное разложение двоичных функций. 12

31. Доказательство ортогональности функций { (-1)^(а,х), аⁿ 12

32. Доказательство теоремы о представлении двоичной функции рядом Фурье.Представление булевых и псевдобулевых функций через базисы линейных пространств. 12

Представление булевых и псевдобулевых функций через базисы линейных пространств. 13

33. Понятие псевдобулевой функции. Базис функций {f_a: f_a(b)=_a,b, aⁿ. 13

34. Базис функций - конъюнкций + константа 1. 13

35. Доказательство утверждений об однозначном представлении псевдобулевой функии в виде аналога СДНФ. 13

36. Доказательство утверждений об однозначном представлении псевдобулевой функии в виде аналога многочлена Жегалкина. 13

37. Характеры группы ⁿ. 13

38. Доказательство теоремы об ортогональности характеров. 13

39. Ряд Фурье псевдобулевой функции. 13

40. Выражение коэффициентов Фурье через веса функций. 13

Статистическая структура двоичной функции. 18

41. Понятие статистического аналога двоичной функции. 18

42. Понятие статистической структуры двоичной функции. 18

43. Доказательство связей значений коэффициентов Фурье двоичной функции со значениями ее статистической структуры. 19

44. Методы вычисления статистической структуры двоичной функции. 19

45. Доказательство теоремы о связи статистической структуры двоичной функции со статистическими структурами ее подфункций 19

Понятие К-равновероятности двоичной функции. 20

46. Понятие К-равновероятности двоичной функции. 20

47. Формулировка критерия К-равновероятности двоичной функции (связь с коэффициентами стат. структуры). Доказательстсво необходимости условий. 21

48. Формулировка критерия К-равновероятности двоичной функции (связь с коэффициентами стат. структуры). Доказательство достаточности условий. 21

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

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

17. Реализация булевых функций формулами. Примеры полных систем.

Примеры полных систем. В §1.1 было введено понятие формулы над базисом и функции, реализуемой формулой. Если базис обладает тем свойством, что любая логическая функция может быть реализована формулой над , его будем называть полным, а в противном случае – неполным.

Мы видели, что произвольная логическая функция, тождественно не равная 0, представима в виде с.д.н.ф., являющейся формулой в базисе {&, ,-}. Поскольку тождественный нуль может быть реализован как x& , то базис {&, ,-} является полным.

Функция выражается через & и отрицание

Поэтому она может быть устранена и базис {&, } также оказывается полным. Аналогично, из соотношения

вытекает полнота базиса { , }.

Полным является и базис, состоящий из одной функции

,

называемой штрихом Шеффера. Действительно, в этом базисе могут быть выражены отрицание

и конъюнкция

,

после чего остается сослаться на полноту базиса {&, }. Аналогично можно доказать полноту базиса, состоящего из одной функции

,

носящей название стрелка Пирса.

Еще один пример полного базиса можно привести на основе представления в виде полинома Жегалкина. Это базис {&, ,0,1}. Поскольку 0 = 1 1, то базис {&, ,1} также полон. В то же время, как будет следовать из дальнейшего, “близкий” к нему базис {&, ,0} уже полным не является. Содержание данного параграфа составляет выяснение условий, необходимых и достаточных для полноты базиса.

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

Замкнутые классы. Пусть имеются логические функции g( , ..., ) и , ..., . Будем считать, что функции , ..., зависят от одних и тех же аргументов , ..., , (этого можно достигнуть, добавив, при необходимости, к аргументам некоторых из функций фиктивные аргументы). Функцию

h( ,…, )=g( ( ,…, ),…, ( ,…, )) (1.8)

будем называть суперпозицией функций g и ,..., . Рассмотрим некоторый класс А логических функций. Класс А назовем замкнутым, если для всяких функций g( , ..., ) и , ..., из А их суперпозиция g( , ..., ) содержится в А. Приведем некоторые важные примеры замкнутых классов.

19. Классы функций: Т0 – сохранения нуля; Т1 - сохранения единицы.

Класс сохранения нуля. Он содержит все логические функции f( ,…, ) такие, что f (0, ... ..., 0) = 0. Класс включает, например, функции 0, х, & , , ,а функции 1, , , ~ ему не принадлежат. Для доказательства замкнутости рассмотрим суперпозицию (1.8) функций g и , ..., из . Поскольку

h(0,…,0)=g( (0,…,0),…, (0,…,0))=g(0,…,0)=0,

то h содержится в .

Класс сохранения единицы. Он состоит из всех логических функций f( ,…, ) таких, что f(1, ..., 1) = 1. Класс включает, например, функции 1,х, & , , , ~ и не содержит функций 0, , . Замкнутость класса устанавливается аналогично замкнутости .

20. S - самодвойственные функции.

Класс S самодвойственных функций. Двойственной к логической функции f( ,…, ) называется функция

( ,…, )= ( ,..., ).

Легко видеть, что = f. Если функция f задана формулой в базисе {0, 1,х, , &, ), то из приведенного в § 1.1 способа написания формулы для функции f вытекает следующее правило. Для того чтобы получить формулу, реализующую функцию , достаточно заменить все операции на &, все операции & на , а все константы — противоположными константами. Отсюда, в частности, следует, что функции & и двойственны друг другу, а каждая из функций х и двойственна себе.

Функцию f( ,…, ) назовем самодвойственной, если

f( ,…, )= ( ,…, ).

Взяв отрицание от обеих частей и воспользовавшись определением двойственности, получаем следующее свойство самодвойственных функций:

( ,…, ) = f( ,…, ). (1.9)

Примером самодвойственной функции является . Действительно, согласно приведенному выше правилу

( ) = ( ) ( ) ( )

= ( ) ( ) = .

Самодвойственность функции легко устанавливается по ее таблице: столбец значений функции обладает тем свойством, что значения, равностоящие от его середины,

Таблица 1.4

противоположны (см. табл. 1.4, задающую функцию ) .

Для доказательства замкнутости класса S самодвойственных функций рассмотрим суперпозицию (1.8) функций из S. С учетом (1.9) имеем ( ,…, )= = ( ( ,…, ),…, ( ,…, )) = ( ( ,…, ),…, ( ,…, ))=g( ( ,…, ),…, ( ,…, ))=h( ,…, )

и, следовательно, h принадлежит S.

21.М - монотонные функции.

Класс М монотонных функций. Будем говорить, что двоичный набор предшествует двоичному набору , и записывать , если имеют место покомпонентные неравенства . Легко видеть, что предшествование является отношением частичного порядка.