Файл: С. Д. Данилова С. С. Михайлова УланУдэ 2022дискретнаяматематика.pdf

164
2.8. Исследование системы функций на полноту
Методические указания к выполнению задания
Задание. Для данных двух функций выяснить вопрос об их принадлежности к классам
Поста. Является ли система из этих функций функционально полной; если да, то в каком смысле – слабом или сильном? При нахождении полиномов Жегалкина использовать для каждой функции разные методы.
При выполнении задания необходимо пользоваться следующим понятиями и мето- дами.
Классами Поста называются следующие классы:
(
)


0 2
|
0,
, 0 0
T
f
P
f
=

=
;
(
)


1 2
|
1,
,1 1
T
f
P
f
=

=
;
(
)


2 1
0 1 1
|
,...,
n
n n
L
f
P
f x
x
x
x



=

=

 
;
(
)
(
)


2 1
1
|
,...,
,...,
n
n
S
f
P
f x
x
f x
x
=

=
;
( )
( )


2
|
M
f
P
f
f
   


=

 
 

Система функций

называется функционально полной системой, если любая логи- ческая функция может быть представлена формулой над

, т. е. являться суперпозицией функций из системы

П е р в а я т е о р е м а о ф у н к ц и о н а л ь н о й п о л н о т е :
Для того чтобы система логических функций была функционально полной в слабом
смысле, необходимо и достаточно, чтобы она содержала:
1 ) хотя бы одну немонотонную функцию;
2 ) хотя бы одну нелинейную функцию.
В т о р а я т е о р е м а о ф у н к ц и о н а л ь н о й п о л н о т е :
Для того чтобы система функций была функционально полной в сильном смысле, необходимо и достаточно, чтобы она содержала:
1 )
хотя бы одну немонотонную функцию;
2 ) хотя бы одну нелинейную функцию;
3 ) хотя бы одну несамодвойственную функцию;
4 )
хотя бы одну функцию, не сохраняющую 0;
5 )
хотя бы одну функцию, не сохраняющую 1.

165
Метод нахождения полинома Жегалкина по формуле:
????(????
1
, ????
2
, … , ????
????
) = ∑
(????
1
⨁ ????
1
) ⋅ (????
2
⨁ ????
2
) ⋅ … ⋅ (????
????
⨁ ????
????
)
(????
1
,????
2
,…,????
????
)
????(????
1
,????
2
,…,????
????
)=1
.
В формуле раскрываем скобки и упрощаем выражение с помощью соотношений:
????(????⨁????) = ????????⨁????????, ????⨁1 = ????̅, ????⨁0 = ????, ????⨁???? = 0.
Метод неопределенных коэффициентов нахождения полинома Жегалкина. Метод ос- нован на таблице истинности логической функции. В общем виде полином Жегалкина функции n переменных имеет вид:
(
)
1 0
1 1
2 2
2 1
2 1
,
,
n
n
n
P x
x
K
K
K




−
−
=
   
 

Нужно найти неизвестные коэффициенты
0 1
2 2 1
, ,
, ,
n
  

−
. Составляем уравнение для каждого набора значений переменных, что даст систему из
2
n
уравнений с
2
n
неиз- вестными, которая имеет единственное решение. Решив систему, находим коэффициенты полинома.
Пример выполнения задания
Даны логические функции:
????(????, ????, ????) = (1100 0111);
????(????, ????, ????) = (1001 0010).
Для функций ????(????, ????, ????) и ????(????, ????, ????) выяснить вопрос об их принадлежности к классам
Поста ????
0
, ????
1
, ????, ????, ????. Является ли система функций {????, ????} функционально полной; если да,
то в каком смысле – слабом или сильном?
При нахождении полинома Жегалкина для функций ???? и ???? использовать два разных метода.

166
Решение.
Построим развернутую таблицу функций:
????
????
????
????(????, ????, ????) ????(????, ????, ????)
0 0
0 1
1 0
0 1
1 0
0 1
0 0
0 0
1 1
0 1
1 0
0 0
0 1
0 1
1 0
1 1
0 1
1 1
1 1
1 0
Проверим функции на принадлежность классу ????
0
:
????(0,0,0) = 1 ⟹ ???? ∉ ????
0
; ????(0,0,0) = 1 ⟹ ???? ∉ ????
0
Проверим функции на принадлежность классу ????
1
:
????(1,1,1) = 1 ⟹ ???? ∈ ????
1
; ????(1,1,1) = 0 ⟹ ???? ∉ ????
1
Проверим функции на принадлежность классу ????:
(0,0,0) ≼ (0,1,0), но ????(0,0,0) > ????(0,1,0) ⟹ ???? ∉ ????;
(0,0,0) ≼ (0,0,1), но ????(0,0,0) > ????(0,0,1) ⟹ ???? ∉ ????.
Проверим функции на принадлежность классу ????: на противоположных наборах (0,0,0) и (1,1,1): ????(0,0,0) = ????(1,1,1) ⟹ ???? ∉ ????; на противоположных наборах (0,1,0) и (1,0,1): ????(0,1,0) = ????(1,0,1) ⟹ ???? ∉ ????;
Проверим функции на принадлежность классу ????.
Найдем полином Жегалкина функции ????(????, ????, ????), исходя из формулы:
????(????, ????, ????) =
∑
(???? ⨁ ????
1
) ⋅ (???? ⨁ ????
2
) ⋅ (???? ⨁ ????
3
).
(????
1
,????
2
,????
3
)
????(????
1
,????
2
,????
3
)=1

167
Получим:
????(????, ????, ????) = ∑ (???? ⨁ ????
1
) ⋅ (???? ⨁ ????
2
) ⋅ (???? ⨁ ????
3
) =
(0,0,0)
(0,0,1)
(1,0,1)
(1,1,0)
(1,1,1)
= ((????⨁1)(????⨁1)(????⨁1)) ⨁ ((????⨁1)(????⨁1)(????⨁0)) ⨁ ((????⨁0)(????⨁1)(????⨁0))⨁
⨁ ((????⨁0)(????⨁0)(????⨁1))⨁ ((????⨁0)(????⨁0)(????⨁0)) =
= ???????????? ⨁ ???????? ⨁ ???? ⨁ ???? ⨁ 1.
Таким образом, имеем полином Жегалкина функции ????(????, ????, ????):
????(????, ????, ????) = ???????????? ⨁ ???????? ⨁ ???? ⨁ ???? ⨁ 1 ⟹ ???? ∉ ????.
Найдем полином Жегалкина функции ????(????, ????, ????) по методу неопределенных коэффи- циентов. В общем виде полином Жегалкина функции трех переменных имеет вид:
????(????, ????, ????) = ????
0
⨁ ????
1
???? ⨁ ????
2
???? ⨁ ????
3
???? ⨁ ????
4
???????? ⨁ ????
5
???????? ⨁ ????
6
???????? ⨁ ????
7
????????????.
Составляем систему уравнений:
{
????(0,0,0) = 1 = ????
0
????(0,0,1) = 0 = ????
0
⨁ ????
3
????(0,1,0) = 0 = ????
0
⨁ ????
2
????(0,1,1) = 1 = ????
0
⨁ ????
2
⨁ ????
3
⨁ ????
6
????(1,0,0) = 0 = ????
0
⨁ ????
1
????(1,0,1) = 0 = ????
0
⨁ ????
1
⨁ ????
3
⨁ ????
5
????(1,1,0) = 1 = ????
0
⨁ ????
1
⨁ ????
2
⨁ ????
4
????(1,1,1) = 0 = ????
0
⨁ ????
1
⨁ ????
2
⨁ ????
3
⨁ ????
4
⨁ ????
5
⨁ ????
6
⨁ ????
7
Решение этой системы дает:
????
0
= 1, ????
1
= 1, ????
2
= 1, ????
3
= 1, ????
4
= 0, ????
5
= 1, ????
6
= 0, ????
7
= 1.
Подставляя полученные коэффициенты в общую формулу, получим полином Жегал- кина:
????(????, ????, ????) = 1 ⨁ ???? ⨁ ???? ⨁ ???? ⨁ ???????? ⨁ ???????????? ⟹ ???? ∉ ????.

168
Таким образом, для системы {????, ????} получим таблицу:
????
0
????
1
????
????
????
????
–
+
–
–
–
????
–
–
–
–
–
Таблица наглядно показывает, что система функций {????, ????} – функционально полная система.
Варианты индивидуальных заданий:
№
????
????
№
????
????
1
(1100 0111)
(1101 1000)
16
(0010 0100)
(1000 1110)
2
(1110 1010)
(0011 0101)
17
(1101 1110)
(1011 0011)
3
(0100 1101)
(1100 1110)
18
(1101 0000)
(1101 0100)
4
(1111 0100)
(1001 0110)
19
(1100 0001)
(1101 1110)
5
(0110 1001)
(1101 0100)
20
(1001 1000)
(1110 1000)
6
(1000 0010)
(0000 1101)
21
(1011 0011)
(1100 0110)
7
(1011 1101)
(1100 0100)
22
(1000 1100)
(0011 1010)
8
(1111 1010)
(0101 1111)
23
(0001 0110)
(1111 0010)
9
(1000 0001)
(1101 1010)
24
(1100 1110)
(1000 0001)
10
(1101 1100)
(0001 1010)
25
(1100 0011)
(1101 1100)
11
(0010 0000)
(1100 1000)
26
(1001 1110)
(0101 0100)
12
(1001 0000)
(1000 0011)
27
(0111 1010)
(1011 1010)
13
(0111 1110)
(1101 0000)
28
(1101 0000)
(1110 1001)
14
(1110 0000)
(1011 0011)
29
(1111 0111)
(1011 1100)
15
(1110 1111)
(1100 0010)
30
(1000 1100)
(1001 1)

169
3. Теория графов
Исследование графов
Методические указания к выполнению задания
Задание. Для данного неориентированного графа выполните:
1. Постройте ориентированный граф, задав направленность всем ребрам графа.
2. Описать неориентированные и ориентированный графы разными способами: а) формально; б) матрицей смежности; в) матрицей инцидентности; г) списком ребер (дуг); д) структурой смежности;
3. Преобразуйте во взвешенный граф, задав веса вершинам и ребрам.
4. Определить метрические характеристики графа: а) степени вершин; б) матрицу весов по вершинам; в) матрицу весов по ребрам; г) длину пути, расстояния между вершинами, эксцентриситет вершин, радиус графа, диаметр графа, центр графа, периферийную вершину, передаточное число, медиану графа; д) число вершинной и реберной связности; е) хроматическое число; ж) плотность графа; з) вершинное число независимости; и) число паросочетания (реберное) число независимости; к) число реберного покрытия.
При выполнении задания необходимо пользоваться следующим понятиями и мето- дами:
1. Неориентированным графом или просто графом называется пара множеств
???? = (????, ????), где ???? – непустое конечное множество вершин, а ????  ????
2
– множество ребер.
2. Если ребра графа имеют направленность, то граф называется ориентированным графом или просто орграфом. При этом ребра называются дугами.
3. Матрица смежности
????(????????) неориентированного графа ???? = (????, ????), |????| = ????:
 
1,
если
,
0,
в противном случае
i
j
ij
v v
E
a



= 

4. Матрица смежности ориентированного графа:

170
(
)
1,
если
,
0,
в противном случае
i
j
ij
v v
E
a



= 

5.
Матрица инцидентности ????(????????) неориентированного графа ???? = (????, ????), |????| = ????,
|????| = ????:
1,
если инцидентно
0,
в противном случае
i
j
ij
e
v
b

= 

6.
Матрица инцидентности ориентированного графа:
1,
если выходит из
1,
если входит в
0, в противном случае
i
j
ij
i
j
e
v
b
e
v
+


= −


7.
Список ребер графа – это представление графа двумя массивами ???? =
(????
1
, ????
2
, … , ????
????
, ????
2
, … , ????
????
) и ???? = (????
1
, ????, … , ????
????
), в которых каждый элемент есть метка вершины графа: i-е ребро графа выходит из вершины ????
????
и входит в вершину
????
????
. Данное представление позволяет легко описать петли и кратные ребра.
8.
Структура смежности ???? состоит из списков смежности вершин графа ????
1
, ????
2
, … , ????
????
Элементами списка смежности являются вершины, которые смежны вершине ????
????
Структуры смежности могут быть реализованы массивом из ???? линейно связанных списков. Хранение же списков смежности на сцепленной памяти желательно в алгоритмах, в основе которых лежат операции добавления и удаления вершин из списков. Таким обра- зом, граф можем представить как пару множеств:
(
) 



(
)
1 1
,
,
,
,
,
,
n
n
v
v
G
V S
v
v
L
L
=
=
9.
В неориентированном графе число ребер, инцидентных вершине ???? – степень вер- шины ????: ????(????).
10. В ориентированном графе количество дуг, исходящих из вершины
???? – полусте- пень исхода: ????
−
(????), а количество дуг, входящих в вершину ????, – полустепень захода: ????
+
(????).
11. Взвешенный граф может быть представлен матрицей весов
????, элементы которого
– веса ребер. Веса несуществующих ребер полагают равными  или 0 в зависимости от приложений. Заметим, что матрица весов является обобщением матрицы смежности.
12. Вершинно-взвешенный граф может быть представлен массивом весов вершин графа.
13. Вес любого маршрута (пути)
???? связного графа называется длиной этого пути ????(????).
14. Минимальная длина между двумя вершинами
???? и ???? называется расстоянием
????(????, ????). Путь, который реализует расстояние графа, называется кратчайшим.

171 15. Эксцентриситетом вершины
???? называется максимальное из расстояний от вер- шины ???? до остальных вершин графа:
16. Радиусом графа называется минимальный из эксцентриситетов вершин:

.
17. Диаметром графа называется максимальный из эксцентриситетов вершин:
.
18. Центром графа называется такая вершина
????, у которой эксцентриситет равен ра- диусу графа:
19. Периферийной вершиной графа называется та, у которой эксцентриситет равен диаметру графа:
Очевидно, что центров графа и периферийных вершин у графа может быть несколько.
20. Передаточным числом вершины
???? взвешенного графа называется величина:
21. Медианой графа называется такая вершина
????*, у которой передаточное число ми- нимально:
22. Минимальное число вершин, удаление которых делает граф несвязным, называ- ется числом вершинной связности графа ????(????).
23. Минимальное число ребер, удаление которых делает граф несвязным, называется числом реберной связностью графа ????(????) .
24. Если обозначить через
????(????) минимальную степень вершины в графе, то имеет ме- сто следующее неравенство:
????(????) ≤ ????(????) ≤ ????(????).
( )
( )


,
max
,
j V j v
e v
r v j


=
( )
( )
 
min
v V
Rad G
e v

=
( )
( )
 
max
v V
Diam G
e v

=
( )
( )
e v
Rad G
=
( )
( )
e v
Diam G
=
( )
( )
,
j
j V
s v
w r v j

=


( )
( )
 
*
min
v V
s v
s v

=

172 25. Наименьшее число красок, необходимое для правильной раскраски графа, назы- вается хроматическим числом, обозначим ????(????).
26. Плотностью графа
????(????) называется наибольшее число вершин полного подграфа графа ????.
27. Множество попарно несмежных вершин графа называется независимым множе- ством. Числом независимости ????(????) называется мощность наибольшего независимого мно- жества.
28. Множество попарно несмежных ребер графа называется паросочетанием или не- зависимым множеством ребер.
29. Паросочетание называется максимальным, если оно не содержится в паросочета- нии с большим числом ребер.
30. Паросочетание называется наибольшим, если число ребер в нем наибольшее среди всех паросочетаний графа. Число ребер в наибольшем паросочетании называется чис- лом паросочетания и обозначается ????(????) .
31. Реберным покрытием графа называется такое подмножество ребер графа, которое покрывает все вершины графа.
32. Реберное покрытие графа называется минимальным, если в нем не содержится покрытий с меньшим числом ребер.
33. Реберное покрытие графа называется наименьшим, если число ребер в нем наименьшее среди всех покрытий. Число ребер в наименьшем реберном покрытии графа называется числом реберного покрытия и обозначается ????(????).
Пример выполнения задания
1. Даны неориентированный и ориентированный графы:
????
1
????
2 2. Способы задания графов:
а) формальное описание: