Основные способы задания двоичных функций (стр. 3 )

Показать, что - Шефферова функция, т. е. - полная система, т. е. . Выразить и формулами над К.

Решение:

, но не

.

Чтобы выяснить вопрос о принадлежности классу , представим многочленом Жегалкина:

Итак, все условия теоремы 3.3.1 выполнены. Следовательно -полная система, т. е. - Шефферова функция. Теперь решим вторую часть примера. Так как , то очевидно , .

Лекция №4.

§4.1. Псевдобулевы функции.

Пусть Р - произвольное поле. Элементы будем рассматривать как нуль и единицу поля .

Определение 4.1.1. Псевдобулевой функцией от переменных, или -местной псевдобулевой функцией, над полем Р при называется любое отображение в Р. Нуль-местными псевдобулевыми функциями над Р называются все элементы поля Р.

Множество всех пседобулевых функций от переменных над полем Р обозначим через . В частности, при класс совпадает с классом булевых функций . В других случаях эти классы различны и если условиться, псевдобулеву функцию со значением из считать булевой, то : .

Множество функций относительно естественным образом определяемых операций сложения функций и умножения функций на элементы из Р образуют линейное пространство над полем Р.

Рассмотрим систему функций:

(4.1.2)

,где -символ Кронекера, т. е. :

Утверждение 4.1.3. Система функций (4.1.2) является базисом пространства .

Доказательство. Очевидно, что система (4.1.2) – линейно независимая система. Далее пусть - произвольная функция из . Тогда очевидно, что :

(4.1.4)

Отсюда следует, что (4.1.2) – базис пространства .

Замечание 4.1.5. Если , то - булева функция и разложение (4.1.4) функции совпадает с разложением, полученным заменой в её СДНФ операции на .

Замечание 4.1.6. Если , то система функций :

(4.1.7)

является базисом пространства . Это следует из теоремы 2.2.4 об однозначном представлении булевых функций многочленами Жегалкина. В этом случае представление функции многочленом Жегалкина есть (4.1.7).

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

1.  Непростым является вопрос об описании базисов пространства ;

2.  Если даже имеется система функций являющаяся базисом пространства, то в общем случае сложным является вопрос о нахождении коэффициентов в разложении булевой функции по указанному базису.

Замечание 4.1.9. В решении вопроса об описании базисов пространства иногда оказывается полезным переход от пространства к пространству векторов-столбцов длинны над полем Р. Сопоставим каждой функции вектор столбец значений этой функции. В итоге получаем отображение пространства в пространство . Нетрудно видеть, что есть изоморфизм пространств, а поэтому система функций является базисом пространства тогда и только тогда, когда матрица является невырожденной.

§ 4.2. Функции к-значной логики.

Пусть , где .

Определение 4.2.1. Функцией k-значной логики, или k-значной функцией, от переменных при называется произвольное отображение k-значными функциями от 0 переменных называются функции - константы 0,1,…,к-1.

Обозначим через и множества всех k-значных функций и k-значных функций от переменных.

При изучении k-значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, аналогичным образом определяются равенство функций, существенные и несущественные переменные, функции от переменных, тождественно равны константам 0,1,…,к-1, подфункции и т. д.

Так как множество конечно, то k-значную функцию от переменных можно задать таблицей её значений на всех наборах (или векторах) из . При этом условимся записывать их в порядке возрастания как числа в конечной системе исчисления. Непосредственно из табличного значения видно, что различных k-значных функций равно . При табличное задание k-значных функций практически еще более трудно осуществимо.

В связи с этим важным вопросом является вопрос о разработке аналитических способов k-значных функций.

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

Используя операции сложения и умножения, а так же элементарные функции

можно получить представление k-значной функции сходное с совершенной дизъюнктивной нормальной формой для случая .

(4.2.2)

Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания :

.

Для k-значных функций, как и в двоичном случае, можно ввести понятия операции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной системы функций и. т.д. Приведем примеры полных систем k-значных функций.

1.  Из представления (4.2.2) следует, что полной является система функций

2.  Так как в разложении (4.2.2) операцию сложения можно заменить на дизъюнкцию( выбор максимума), то полной является также система функций

3.  Наряду с разложением (4.2.2) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции , где . Отсюда следует, что полной является система функций .

4.  Система функций является полной системой функций.

Доказательство. С помощью суперпозиции из функции легко получить функции . Из них получим константу , а поэтому все функции константы . Теперь нетрудно получить функции :

.

Как следует из примера 3, остается построить функцию , т. е. Для этого сначала построим функции

Теперь из них можно получить функции и .

5.  Аналогично функции Шеффера в k-значной логике является функция Вебба , которая одна образует систему, т. е. система является????????

Доказательство. Используя при имеем . Далее получаем :

А так как . Отсюда имеем, что - полная система функций.

Утверждение 4.2.3. Все k-значные функции представляются многочленами над в том и только том случае, когда к- простое число, т. е. -поле.

(без доказательства).

Утверждение 4.2.4. (критерий полноты- Критерий?????Слунецкого??).

Пусть система k-значных функций K содержит се функции одной переменной, причем . Тогда для полноты системы К необходимо и достаточно, чтобы К содержала функцию, существенно зависящую по меньшей мере от двух переменных и принимающую все значений из .

Лекция №5

5.1 Минимизация двоичных функции.

Пусть двоичная функция f представлена в виде ДНФ:

(5.1.1)

Определение 5.1.2: Сложностью представления (5.1.1) булевой функции f называется число операций «» и «» в записи (5.1.1).

Замечание 5.1.3: Операции «отрицания» в определении 5.1.2 не учитываются.

Определение 5.1.4: Задача минимизации для функции f заключается в нахождении заданий функции f в виде ДНФ, у которых сложности минимальны. Такие ДНФ называются минимальными (МДНФ).

Определение 5.1.5: Импликантами двоичной функции f называются элементарные конъюнкции, входящие во всевозможные ДНФ функции f. Импликанта функции f называется простой, если все элементарные конъюнкции, полученные из неё удалением некоторых переменных, не являются импликантами функции f.

Утверждение 5.1.6: Пусть . Следующие утверждения эквивалентны:

1)  является импликантой функции f;

2)  ;

3)  .

Доказательство: Покажем эквивалентность первых двух утверждений. Если – импликанта и – та ДНФ, в которую входит , например, , то

.

Обратно, если – некоторая ДНФ, то в силу тождества конъюнкцию можно дописать в качестве (k+1)-ой импликанты в эту ДНФ не нарушая равносильности.

Эквивалентность утверждений 2 и 3 следует из тождеств:

,

.

Утверждение доказано.

Утверждение 5.1.7: В минимальной ДНФ функции f () все импликанты являются простыми.

Доказательство: Пусть - минимальная ДНФ функции f. Предположим, что импликанта не простая. Тогда её можно представить в виде произведения двух элементарных конъюнкций от разных переменных, одна из которых, например, также является импликантой функции f. Согласно утверждению 5.1.6:

, или иначе

.

Таким образом, получено противоречие с минимальностью исходной ДНФ.

Утверждение доказано.

Из этого утверждения вытекает, что задачу минимизации в классе ДНФ можно решать в два этапа.

1-ый этап: Находят все простые импликанты функции f. Дизъюнкция всех простых импликант функции f называется сокращённой ДНФ этой функции.

Замечание 5.1.8: Сокращённая ДНФ функции f действительно является ДНФ для f, поскольку, повторяя доказательство утверждения 5.1.7 можно в произвольной ДНФ функции f заменить все импликанты на простые.

2-ой этап: Находят все такие ДНФ функции f, состоящие из простых импликант, из которых нельзя удалить ни одной импликанты. Такие ДНФ называются тупиковыми или несократимыми. Подсчитав сложности тупиковых ДНФ, можно выбрать из них ТДНФ с минимальной сложностью, которая и есть МДНФ.

5.2 Геометрическая интерпретация минимизации ДНФ.

Зададим двоичную функцию на n-мерном двоичном кубе. Как было отмечено ранее, при таком задании элементарным конъюнкциям ранга k соответствуют такие множества вершин, графы связности которых имеют вид (k-n)-мерных кубов. Поскольку дизъюнкции элементарных конъюнкций соответствует объединение множеств вершин таких подкубов, то каждой ДНФ функции f соответствует некоторое покрытие множества Mf единичных вершин функции f (области истинности) подмножествами, имеющими в качестве графов связности подкубы. Простым импликантам функции f будут соответствовать подкубы максимальных размерностей, покрывающие вершины из Mf.

Соответственно, первая задача (1-ый этап) решается перечислением всех максимальных подкубов, содержащихся в графе связности множества Mf.

Вторая задача (2-ой этап) заключается в нахождении минимальных (по числу подкубов) покрытий множества Mf максимальными подкубами.

Рассмотрим пример. Пусть двоичная функция f (x1, x2, x3, x4) имеет геометрическое задание, изображённое на рис. 5.2.1:

Граф связности такой функции имеет вид: