 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Примеры использования теоремы Поста
|
|
1. Покажем, что система функций { f 1 = x 1 x 2, f 2 =0, f 3 =1, f 4 = x 1Å x 2Å x 3} полна в Р 2. Составим таблицу, которая называется критериальной:
| Т 0 | Т 1 | L | M | S | |
| x 1 x 2 | + | + | - | + | - |
| + | - | + | + | - | |
| - | + | + | + | - | |
| x 1Å x 2Å x 3 | + | + | + | - | + |
| x 1 x 2 x 3 | x 1Å x 2Å x 3 |
| 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 |
Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы, которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».
Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, { f 2, f 3, f 4}Ì L, { f 1, f 3, f 4}Ì T 1, { f 1, f 2, f 4}Ì T 0, { f 1, f 2, f 3}Ì M.
2. Мы знаем, что система { x 1| x 2} – полна в Р 2. Какова для нее критериальная таблица? x 1| x 2= 
= x 1 x 2Å1.
| Т 0 | Т 1 | L | M | S | |
| x 1| x 2 | - | - | - | - | - |
3. Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x 1 x 2, x 1Å x 2}.
| Т 0 | Т 1 | L | M | S | |
| + | - | + | + | - | |
| - | + | + | + | - | |
| x 1 x 2 | + | + | - | + | - |
| x 1Å x 2 | + | - | + | - | - |
Согласно критериальной таблице, полной является и система {1, x 1 x 2, x 1Å x 2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а 
равны 0, если члены х 
х 
... х 
, в полиноме отсутствуют.
4. Выясним, полна ли система 
. Составим критериальную таблицу, очевидно 
. Чтобы показать, что 
, достаточно найти одну функцию 
и 
. Возьмем 
, удовлетворяющую требуемым условиям. Если f 
S \ T 0, то f (0,..., 0) = 1, f (1,..., 1)=0, следовательно, f 
M, f T 1. Рассмотрим функцию h = x 1 x 2 
x 2 x 3 x 1 x 3=1, набор ее значений (11101000), h S \ T 0, но h L. Следовательно, критериальная таблица имеет вид:
| Т 0 | Т 1 | L | M | S | |
L  T 1
| - | + | + | - | - |
| S \ T 0 | - | - | - | + | - |
и А – полная система функций.
Определение. Система функций { f 1,..., fs,...} называется базисом в Р 2,если она полна в Р 2, но любая ее подсистема не будет полной. Например, система функций { x 1& x 2, 0, 1, x 1 x 2 x 3} – базис.
Дата публикования: 2014-10-20; Прочитано: 757 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
