Примеры использования теоремы Поста

1. Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = x1Åx2Åx3} полна в Р2. Составим таблицу, которая называется критериальной :

  Т0 Т1 L M S
x1x2 + + - + -
+ - + + -
- + + + -
x1Åx2Åx3 + + + - +
x1 x2 x3 x1Åx2Åx3
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4}ÌL, {f1, f3, f4}ÌT1, {f1, f2, f4}ÌT0, {f1, f2, f3}ÌM.

2. Мы знаем, что система {x1|x2} – полна в Р2. Какова для нее критериальная таблица? x1|x2= Примеры использования теоремы Поста - №1 - открытая онлайн библиотека = x1x2Å1.

  Т0 Т1 L M S
x1|x2 - - - - -

3. Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}.

  Т0 Т1 L M S
+ - + + -
- + + + -
x1x2 + + - + -
x1Åx2 + - + - -

Согласно критериальной таблице, полной является и система {1, x1x2, x1Åx2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а Примеры использования теоремы Поста - №2 - открытая онлайн библиотека равны 0, если члены х Примеры использования теоремы Поста - №3 - открытая онлайн библиотека х Примеры использования теоремы Поста - №4 - открытая онлайн библиотека ...х Примеры использования теоремы Поста - №5 - открытая онлайн библиотека , в полиноме отсутствуют.

4. Выясним, полна ли система Примеры использования теоремы Поста - №6 - открытая онлайн библиотека . Составим критериальную таблицу, очевидно Примеры использования теоремы Поста - №7 - открытая онлайн библиотека . Чтобы показать, что Примеры использования теоремы Поста - №8 - открытая онлайн библиотека , достаточно найти одну функцию Примеры использования теоремы Поста - №9 - открытая онлайн библиотека и Примеры использования теоремы Поста - №10 - открытая онлайн библиотека . Возьмем Примеры использования теоремы Поста - №11 - открытая онлайн библиотека , удовлетворяющую требуемым условиям. Если f Примеры использования теоремы Поста - №12 - открытая онлайн библиотека S\T0, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, f Примеры использования теоремы Поста - №13 - открытая онлайн библиотека M, f Примеры использования теоремы Поста - №13 - открытая онлайн библиотека T1. Рассмотрим функцию h = x1x2 Примеры использования теоремы Поста - №15 - открытая онлайн библиотека x2x3 Примеры использования теоремы Поста - №15 - открытая онлайн библиотека x1x3=1, набор ее значений (11101000), h Примеры использования теоремы Поста - №12 - открытая онлайн библиотека S\T0, но h Примеры использования теоремы Поста - №13 - открытая онлайн библиотека L. Следовательно, критериальная таблица имеет вид:

  Т0 Т1 L M S
L Примеры использования теоремы Поста - №19 - открытая онлайн библиотека T1 - + + - -
S\T0 - - - + -

и А – полная система функций.

Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1 Примеры использования теоремы Поста - №15 - открытая онлайн библиотека x2 Примеры использования теоремы Поста - №15 - открытая онлайн библиотека x3} – базис.

Контрольная работа

Вариант I

1. Составить таблицу истинности для булевой функции:

Примеры использования теоремы Поста - №22 - открытая онлайн библиотека

2. Составить СДНФ и СКНФ для:

Примеры использования теоремы Поста - №23 - открытая онлайн библиотека

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

Примеры использования теоремы Поста - №24 - открытая онлайн библиотека

4. Определить является ли следующая система функций полной {0,1,x, Примеры использования теоремы Поста - №25 - открытая онлайн библиотека }

5. Дана формула Примеры использования теоремы Поста - №26 - открытая онлайн библиотека . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)

Вариант II

1. Составить таблицу истинности для булевой функции:

Примеры использования теоремы Поста - №27 - открытая онлайн библиотека

2. Составить СДНФ и СКНФ для:

Примеры использования теоремы Поста - №28 - открытая онлайн библиотека

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

Примеры использования теоремы Поста - №29 - открытая онлайн библиотека

4. Определить является ли следующая система функций полной

Примеры использования теоремы Поста - №30 - открытая онлайн библиотека

5. Дана формула Примеры использования теоремы Поста - №31 - открытая онлайн библиотека . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)