praktikum-4
.pdfРязанский государственный радиотехнический университет
Кафедра высшей математики
Дистанционный курс
«Дискретная математика»
Практикум – 4
Полные системы функций
Разработчик курса Елкина Наталья Викторовна, старший преподаватель кафедры ВМ
2
Задача 1. Какую нужно сделать подстановку на места переменных в немонотонной функции f xyz xy , чтобы получить отрицание x ?
Решение.
Заданная функция f xyz xy не является монотонной, так как для сравнимых наборов 0,1, 0 1,1, 0 выполняется f 0,1, 0 1 f 1,1, 0 0 .
Используя доказательство теоремы о немонотонной функ-
x |
y |
z |
||
|
0 |
1 |
0 |
|
ции, составим матрицу |
, в первой строке которой |
|||
|
1 |
1 |
0 |
|
|
|
|||
содержатся переменные, во второй и третьей – наборы, для которых не выполняется условие монотонности. Произведем подстановку на места переменных следующим образом: на места
0
переменных, под которыми стоит столбец подставим
1
1
функцию x , под которыми стоит столбец – функцию 1, под
1
|
0 |
|
– функцию 0 ,. В результате полу- |
которыми стоит столбец |
|
|
|
|
0 |
|
|
|
|
|
чим функцию одной переменной x f x,1, 0 , причем
0 f 0,1, 0 1 и 1 f 1,1, 0 0 , то есть x x . От-
рицание получено.
Задача 2. Определить, какие из |
переменных функции |
~ |
x , а какие на x с тем, |
f x 10110110 следует заменить на |
|
чтобы получить константу. |
|
Решение.
~
Если составить полную таблицу значений функции f x ,
Практикум-4 |
Елкина Н. В. |
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
x, y, z |
000 |
001 |
010 |
011 |
100 |
101 |
110 |
111 |
f |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
то можно заметить, что она не является самодвойственной. Например, для противоположных наборов 0,1, 0 и 1, 0,1 вы-
полняется |
f 0,1, 0 f 1, 0,1 1 . |
|
|
|
|
Используя доказательство теоремы о несамодвойственной |
|||||
|
x |
y |
z |
||
|
|
0 |
1 |
0 |
|
функции, |
составим матрицу |
, в первой строке кото- |
|||
|
|
1 |
0 |
1 |
|
|
|
|
|||
рой содержатся переменные, во второй и третьей – наборы, для которых не выполняется условие самодвойственности. Произведем подстановку следующим образом: на места переменных,
0
под которыми стоит столбец подставим функцию x , под
1
|
1 |
|
которыми стоит столбец |
– функцию x . В результате полу- |
|
|
|
|
|
0 |
|
чим функцию одной переменной x f x, x, x , |
причем |
|
0 f 0,1,0 f 1, 0,1 1 1, то есть x 1. |
Констан- |
|
та получена. |
|
|
Задача 3. Подставляя на места переменных нелинейной |
||
~ |
|
|
функции f x 01100111 какие-либо функции из множества |
||
0,1, x, y , получить хотя бы одну из функций xy , xy , |
x | y . |
|
Решение. |
|
|
|
Данную функцию зададим полиномом Жегалкина, напри- |
|||
мер, по формуле |
f x, y, z |
x 1 y |
2 z 3 , в ре- |
|
~ |
~ |
|
|
: f 1 |
||
зультате получим |
f x, y, z xyz y z (проверьте это само- |
||
стоятельно).
Практикум-4 |
Елкина Н. В. |
4
Используя доказательство теоремы о нелинейной функции,
выполним |
подстановку z 1, чтобы |
получить нелинейную |
||
функцию первых двух переменных |
f x, y,1 xy y 1. |
|||
Далее |
выполнив |
преобразование |
f x, y,1 y x 1 1, |
|
подставим |
вместо x |
функцию |
x x 1, тогда получим |
|
f x, y,1 xy 1 xy x | y , что и требовалось.
Задача 4. Полна ли данная система функций?
а) N1 xy, x y, x y, xy yz xz ;
б) N2 xy, x y, x y z 1 . в) N3 x yz .
Решение.
Чтобы проверить систему функций на полноту, нужно составить таблицу Поста для всей системы, в которой знак «плюс» ставится в случае принадлежности некоторой функции к определенному классу функций, в противном случае – знак «минус». Если в каждом столбце таблицы Поста будет содержаться хотя бы один знак «минус», то данная система функций полна.
а) Можно отметить, что все функции данной системы сохраняют ноль, то есть принадлежат классу C3 , так как
0 0 0 , 0 0 0 , 0 0 0 , 0 0 0 0 0 0 0 .
Поэтому по теореме о полноте система функций N1 не полна.
б) Составим полные таблицы значений заданных функций.
|
|
|
x, y |
|
|
0 0 |
0 1 |
1 0 |
1 1 |
|
|
|
||||
|
|
f1 xy |
|
|
0 |
|
0 |
|
0 |
|
1 |
|
|
|
||
|
f2 x y |
|
0 |
|
1 |
|
1 |
|
1 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x, y, z |
|
000 |
001 |
|
010 |
|
011 |
|
100 |
|
101 |
|
110 |
111 |
||
f3 x y z 1 |
|
1 |
0 |
|
|
0 |
|
1 |
|
0 |
|
1 |
|
1 |
0 |
|
Практикум-4 |
Елкина Н. В. |
5
Исследуем принадлежность каждой заданной функции системы N2 к классам Поста.
|
|
f1 xy . |
|
|
|
|
|
|
(1,1) |
|
|
|
|
|
|
|
|
|
|
||
f1 0, 0 0 , то есть |
f1 C3 . |
|
|
(1,0) |
(0,1) |
|||||
f1 1,1 1, то есть |
f1 C2 . |
|
|
|||||||
0,1 |
|
|
|
|||||||
Для противоположных наборов |
и |
(0,0) |
|
|||||||
1, 0 выполняется f1 0,1 f1 1, 0 , |
|
|
|
|
||||||
поэтому |
|
|
||||||||
f1 D3 . |
|
|
|
|
|
|
|
|
|
|
Из чертежа двумерного куба видно, что |
f1 A1 . |
|
||||||||
Так как |
f1 содержит произведение переменных в полиноме |
|||||||||
Жегалкина xy , то f1 L1 . |
|
|
|
|
|
|||||
|
Самостоятельно исследуйте функцию |
f2 x y . |
||||||||
|
f3 x y z 1. |
|
|
|
|
|
||||
f3 |
0, |
1, то есть |
f3 C3 . |
|
|
|
|
|
||
f3 |
1,1,1 0 , то есть |
f3 C2 . |
|
|
|
|
|
|||
f3 * x y z 1 * |
|
|
|
|||||||
x y z 1 x y z 1 1 |
|
|||||||||
x 1 y 1 z 1 x y z 1 f3 , |
то есть |
f3 D3 . |
|
|||||||
Так как |
1,1, 0 1,1,1 , но f3 1,1, 0 1 f3 1,1,1 0 , |
то |
||||||||
f3 A1 . |
|
|
|
|
|
|
|
|
|
|
Так как |
f3 не содержит произведение переменных в поли- |
|||||||||
номе Жегалкина x y z 1, то f3 L1 .
Занесем все полученные в результате исследования данные в таблицу Поста для системы N2 .
Практикум-4 |
Елкина Н. В. |
6
|
|
|
|
|
|
|
|
C3 |
|
C2 |
|
|
|
|
|
D3 |
|
|
A1 |
|
|
|
|
|
L1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
f1 xy |
|
|
+ |
|
+ |
|
|
|
|
|
|
- |
|
|
+ |
|
|
|
|
|
- |
|
||||||||||
|
f2 x y |
|
|
+ |
|
+ |
|
|
|
|
|
|
- |
|
|
+ |
|
|
|
|
|
- |
|
||||||||||
|
f3 x y z 1 |
|
- |
|
- |
|
|
|
|
|
|
+ |
|
|
- |
|
|
|
|
|
+ |
|
|||||||||||
|
Так как в каждом столбце таблицы Поста содержится хотя |
||||||||||||||||||||||||||||||||
бы один знак «минус», то система функций N2 |
|
полна. |
|
|
|
|
|
|
|||||||||||||||||||||||||
|
в) Исследуем функцию f x yz , но предварительно со- |
||||||||||||||||||||||||||||||||
ставим полную таблицу значений этой функции. |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
x, y, z |
|
|
000 |
|
|
001 |
|
010 |
|
|
|
011 |
|
|
100 |
|
|
101 |
|
|
110 |
|
|
111 |
|
|||||||
|
f x yz |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
|
|
0 |
|
|
1 |
|
|
|
0 |
|
0 |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
f 0, 0, 0 1, то есть |
f C3 . |
|
f 1,1,1 0 , |
то есть |
f C2 . |
|||||||||||||||||||||||||||
|
Для противоположных наборов 0,1, 0 и 1, 0,1 выполня- |
||||||||||||||||||||||||||||||||
ется f 0,1, 0 f 1, 0,1 , то есть |
f D3 . |
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
Так как 1, 0,1 1,1,1 , но |
|
f 1, 0,1 1 f 1,1,1 0 , то |
||||||||||||||||||||||||||||||
|
f A1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Полином Жегалкина для функции |
|
f x yz |
|
имеет вид |
||||||||||||||||||||||||||||
|
f xyz xz x 1 (проверьте это самостоятельно), |
|
поэтому |
||||||||||||||||||||||||||||||
|
f L1 . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Составим таблицу Поста для системы функций N3 . |
|
|
|
|||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
C3 |
|
C2 |
|
|
|
|
|
D3 |
|
|
A1 |
|
|
|
|
|
L1 |
|
|||||||
|
f x yz |
|
|
- |
|
- |
|
|
|
|
|
|
- |
|
|
- |
|
|
|
|
|
- |
|
||||||||||
|
Так как в каждом столбце таблицы Поста есть знак «минус», |
||||||||||||||||||||||||||||||||
то система N3 |
полна. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
Практикум-4 |
Елкина Н. В. |
7
Определение. Функция f , образующая полную систему, называется шефферовской функцией.
|
Можно доказать, что если |
f C3 C2 |
D3 , то |
f является |
|||||||||||||||||||||||
шефферовской функцией. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
Задача 5. Доопределить функцию до шефферовской. |
||||||||||||||||||||||||||
|
x, y, z |
|
|
|
000 |
|
|
001 |
|
|
010 |
|
|
011 |
|
|
100 |
|
|
101 |
|
|
110 |
|
|
111 |
|
|
f |
|
0 |
|
1 |
|
|
|
0 |
|
1 |
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение.
Чтобы функция была шефферовской, она должна образовывать полную систему, то есть быть несамодвойственной, немонотонной, нелинейной, не сохранять 0 и 1.
Так как f не должна сохранять 0 и 1, то f 0, 0, 0 1 и f 1,1,1 0 . Но в силу этого не выполняются свойства 1 и 2 для монотонных функций 1, поэтому f A1 .
Так как f должна быть несамодвойственной, то для противоположных наборов 0,1,1 и 1, 0, 0 , а также 0, 0,1 и 1,1, 0
должно не выполняться условие самодвойственности, то есть |
|
f 0,1,1 f 1, 0, 0 0 или |
f 0, 0,1 f 1,1, 0 0 . Пусть вы- |
полняются оба эти равенства.
Все полученные значения занесем в полную таблицу значений исходной функции (розовым цветом отмечены доопределенные значения).
|
x, y, z |
|
|
000 |
|
|
001 |
|
|
010 |
|
|
011 |
|
|
100 |
|
|
101 |
|
|
110 |
|
|
111 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
f |
|
|
1 |
|
0 |
|
1 |
|
|
0 |
|
0 |
|
1 |
|
|
0 |
|
|
0 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
~ |
|
~ |
|
~ |
|
~ |
|
|
1. Если f 0 |
1 |
1. 2. |
Если f 1 |
0 |
0 . |
||||
|
, то f x |
, то f x |
Практикум-4 |
Елкина Н. В. |
8
Проверим полученную функцию на линейность, для этого составим полином Жегалкина и получим f xyz x z 1
(проверьте это самостоятельно). Очевидно, что f L1 .
В итоге полученная функция f xyz x z 1 является шефферовской.
Задача 6. Являются ли заданные системы базисами в P2 ?
а) N1 x y z, x y, 1 ;
б) N2 xy z, xy z, xy z .
Решение.
Система функций N будет базисом, если она полна, а после удаления из нее какой-либо функции полнота нарушается.
|
а) Проверим полноту системы функций |
|
N1 , для этого со- |
||||||||||||||
ставим для нее таблицу Поста (сделайте это самостоятельно). |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C3 |
|
|
C2 |
|
D3 |
|
A1 |
|
L1 |
||||
|
f1 x y z |
|
|
+ |
|
|
- |
|
|
+ |
|
|
- |
|
|
+ |
|
|
f2 x y |
|
|
+ |
|
|
+ |
|
|
- |
|
|
+ |
|
|
- |
|
|
f3 1 |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
- |
|
|
+ |
|
|
- |
|
|
+ |
|
|
+ |
|
|
|
Так как в каждом столбце таблицы Поста содержится хотя |
||||||||||||||||
бы один знак «минус», то система функций N1 полна. |
|
|
|
||||||||||||||
|
Если из системы |
N1 удалить функцию |
f1 x y z , то в |
||||||||||||||
оставшейся системе не будет немонотонной функции и функции, не сохраняющей 1, поэтому полученная система функций не будет полной.
Если из системы N1 удалить функцию f2 x y , то в ос-
тавшейся системе не будет нелинейной функции, поэтому полученная система функций не будет полной.
Практикум-4 |
Елкина Н. В. |
9
Если из системы N1 удалить функцию f3 1, то в остав-
шейся системе не будет функции, не сохраняющей 0, поэтому полученная система функций не будет полной.
В итоге получили, что заданная система функций N1 является базисом.
|
б) Проверим полноту системы функций |
|
N2 , для этого со- |
||||||||||||||
ставим для нее таблицу Поста (сделайте это самостоятельно). |
|||||||||||||||||
|
|
|
|
C3 |
|
|
C2 |
|
D3 |
|
A1 |
|
L1 |
||||
|
f1 xy z |
|
|
+ |
|
|
+ |
|
|
- |
|
|
+ |
|
|
- |
|
|
f2 xy z |
|
|
+ |
|
|
- |
|
|
- |
|
|
- |
|
|
- |
|
|
f3 xy z |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
- |
|
|
+ |
|
|
- |
|
|
- |
|
|
- |
|
|
|
Очевидно, что система функций N2 полна. |
|
|
|
|||||||||||||
|
Если из системы |
N2 удалить функцию |
|
f1 xy z , то ос- |
|||||||||||||
тавшаяся система все равно останется полной, так как в каждом столбце будет хотя бы один знак «минус».
Но после удаления из системы N2 функции f2 xy z оставшаяся система не будет содержать функцию, не сохра-
няющую 1. |
А после удаления |
из системы N2 функции |
f3 xy z |
оставшаяся система не будет содержать функцию, |
|
не сохраняющую 0. |
|
|
Поэтому исходная система N2 |
не является базисом, но сис- |
|
тема функций f2 xy z, f3 xy z будет базисом.
Практикум-4 |
Елкина Н. В. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
Задача 7. Из полной в |
P2 системы |
N f1, |
f2 , |
f3, f4 , |
||||||||||||
где |
f1 x y , |
f2 |
xy z , |
f3 x y z 1, |
||||||||||||||
|
f4 xy yz xz , выделить всевозможные базисы. |
|
|
|
||||||||||||||
|
|
Решение. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
Составим таблицу Поста для системы функций N . |
|
|
|
|||||||||||||
|
|
|
|
|
C3 |
|
C2 |
|
D3 |
|
A1 |
|
L1 |
|||||
|
|
f1 x y |
|
|
+ |
|
|
- |
|
|
- |
|
|
- |
|
|
+ |
|
|
|
f2 xy z |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
+ |
|
|
- |
|
|
- |
|
|
- |
|
|
- |
|
|
|
f3 x y z 1 |
|
|
- |
|
|
|
|
+ |
|
|
- |
|
|
|
|||
|
|
|
|
|
- |
|
|
|
|
|
|
+ |
|
|||||
|
f4 xy yz xz |
|
|
+ |
|
|
+ |
|
|
+ |
|
|
+ |
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
По таблице составим КНФ K , в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве слагаемых символы тех функций, которые не принадлежат классу, соответствующий столбцу, то есть те, которые
имеют знак «минус». |
|
|
|
||||
В данном случае: |
|
|
|
||||
K f3 f1 f2 f3 |
f1 f2 f1 f2 f3 |
f2 f4 |
|||||
|
|
|
|
f2 f3 f1 f3 f4 . |
|
||
|
|
|
|||||
|
|
|
|
||||
|
|
|
|
|
|
|
|
Значит, из данной системы N можно выделить два базиса: |
|||||||
|
|
B1 f2 , |
f3 и B2 f1, f3, |
f4 , |
|||
где |
|
f1 x y , |
|
f2 xy z , |
f3 x y z 1, |
||
f4 xy yz xz . |
|
|
|
|
|
||
Практикум-4 |
Елкина Н. В. |