Файл: Учебнометодический комплекс по дисциплине Дискретная математика Основная образовательная программа 010800 Механика и математическое моделирование.pdf

---

---

Глава 4. Алгебра логики
4.1. Функции алгебры логики
Определение. Функция


2 2
1
,...,
,
E
x
x
x
f
n

n
i
E
x
i
,
1
,
2



, где


1
,
0 2

E
, называется функцией алгебры логики или булевой функцией.
Упорядоченный набор


n
x
x
x
,...,
,
2 1
является элементом прямого произведения множества
2
E на себя, взятого n раз:


 
n
n
n
E
E
E
E
x
x
x
2 2
2 2
2 1
,...,
,







 


 

По теореме о мощности прямого произведения множеств:
 
n
n
n
E
E
2 2
2


Всякая булева функция n переменных может быть задана таблицей, в левой части которой перечислены все
n
2 наборов значений переменных, а в правой – значения функции на этих наборах:














1
,
1
,
1
,...,
1
,
1 0
,
0
,
1
,...,
0
,
0 1
,
1
,
0
,...,
0
,
0 0
,
1
,
0
,...,
0
,
0 1
,
0
,
0
,...,
0
,
0 0
,
0
,
0
,...,
0
,
0 1
1 1
1 1
0 0
0 0
0 1
1 0
0 0
0 1
0 0
0 1
0 0
0 0
0 0
0 0
0 2
,...,
,
2 1
1 2
1
f
f
f
f
f
f
x
x
x
f
x
x
x
x
x
n
n
n
n
i










Для удобства употребляют стандартное расположение наборов, которое соответствует двоичному представлению чисел от 0 до
1 2 
n
Каждая функция


n
x
x
x
f
,...,
,
2 1
определяет отображение на
2
E :
2 2
2 2
E
E
E
E
n






 


 

Обозначим множество всех булевых функций от любого числа переменных через
2
P , множество всех булевых функций, зависящих от n переменных, через
 
n
P
2
:
 




n
x
x
x
f
n
P
,...,
,
2 1
2

Теорема. Число булевых функций, зависящих от
n переменных равно
 
 
n
n
p
n
P
2 2
2 2



4.2.
Существенные и фиктивные переменные.
Исключение и введение фиктивных переменных. Равенство функций
Определение. Функция


n
i
i
i
x
x
x
x
x
f
,...,
,
,
,...,
1 1
1


существенно зависит от переменной
i
x , если существует такой набор значений
n
i
i




,...,
,
,...,
1 1
1


переменных
n
i
i
x
x
x
x
,...,
,
,...,
1 1
1


, что




n
i
i
n
i
i
f
f








,...,
,
1
,
,...,
,...,
,
0
,
,...,
1 1
1 1
1 1





В этом случае переменная
i
x называется существенной. Если переменная
i
x не является существенной, то она называется несущественной или фиктивной.
Определение. Переменная
i
x называется фиктивной, если для любого набора значений
n
i
i




,...,
,
,...,
1 1
1


переменных
n
i
i
x
x
x
x
,...,
,
,...,
1 1
1






n
i
i
n
i
i
f
f








,...,
,
1
,
,...,
,...,
,
0
,
,...,
1 1
1 1
1 1





Пусть для функции


n
x
x
x
f
,...,
,
2 1
переменная
i
x является фиктивной. Тогда ее можно исключить и перейти к булевой функции
g
, у которой
1

n
переменная.
Для этого в таблице функции


n
x
x
x
f
,...,
,
2 1
вычеркиваем все строки, соответствующие
1

i
x
(или
0

i
x
) и столбец для аргумента
i
x . Полученная таблица будет определять функцию
g
от
1

n
переменной.
Определение. Функция
g
называется функцией, полученной из функции
f исключением фиктивной переменной
i
x .
Определение. Функция
f называется функцией, полученной из функции
g
введением фиктивной переменной
i
x .
Определение. Если одна функция получена из другой исключением или введением фиктивной переменной, то они называются равными:
g
f 
Существуют два типа функций, которые не имеют существенных переменных:
0 1

f
и
1 2

f
Замечание. Если среди значений функции число 0 (1) нечетно, то фиктивных переменных нет. Обратное не верно.
Пример. Функция


y
x
f
,
задана таблицей. Определить, существенными или фиктивными переменными являются x и
y
x
y


y
x
f
,
0 0
0 0
1 1
1 0
0 1
1 1
Проверим, является ли существенной переменная x . То есть, по определению, нужно найти такое значение
2
 переменной
y
, при котором




2 2
,
1
,
0



f
f
. Сначала рассмотрим случай
0 2


:




0 0
,
1 0
,
0

 f
f
. То есть условие из определения существенной переменной не выполняется. При

1 2


:


 
1 1
,
1 1
,
0

 f
f
. Таким образом, при любом значении
2
 переменной
y
выполняется равенство




2 2
,
1
,
0



f
f
. Следовательно, по определению фиктивной переменной, переменная x является фиктивной.
Проверим переменную
y
. При
0 1


:




1
,
0 0
,
0
f
f

. Следовательно, переменная
y
- существенная.
Фиктивную переменную x можно удалить из таблицы функции


y
x
f
,
. Для этого вычеркнем из таблицы функции


y
x
f
,
3 и 4 строки, в которых
1

x
, и столбец с переменной x .
x
y


y
x
f
,
0 0
0
y
 
y
g
0 1
1

0 0
1 0
0 1
1 1
1 1
Функция
g
получена из функции
f исключением фиктивной переменной x .
4.3.Формулы алгебры логики. Реализация функций формулами. Суперпозиция
Элементарные булевы функции от одной переменной
 
x
f
:
 
x
x
f

- тождественная функция,
 
x
x
f

- отрицание x ,
 
0

x
f
- константа 0,
 
1

x
f
- константа 1.
Значения элементарных булевых функций от одной переменной приведены в таблице.
x x
x
0 1 0 0 1 0 1 1 1 0 0 1
Элементарные булевы функции от двух переменных


y
x
f
,
:


y
x
y
x
f


,
- дизъюнкция (логическое сложение),


y
x
y
x
f
&
,

- конъюнкция (логическое умножение),


y
x
y
x
f


,
- сложение по модулю 2,


y
x
y
x
f


,
- импликация (логическое следование),


y
x
y
x
f

,

- эквивалентность,


y
x
y
x
y
x
f
&
/
,


- штрих Шеффера,



y
x
y
x
y
x
f




,
- стрелка Пирса.
Значения элементарных булевых функций от одной переменной приведены в таблице.
x
y
y
x 
y
x &
y
x 
y
x 
y
x
y
x /
y
x 
0 0 0
0 0
1 1
1 1
0 1 1
0 1
1 0
1 0
1 0 1
0 1
0 0
1 0
1 1 1
1 0
1 1
0 0
Определение. Суперпозицией функций
m
f
f ,...,
1
называется функция
f , полученная с помощью подстановки этих функций друг в друга и переименованием переменных.
Формулой называется выражение, описывающее эту суперпозицию.
Если функция
f соответствует формуле A , то говорят, что формула A реализует функцию
f .
Каждой формуле алгебры логики соответствуют функции, причем различным формулам могут соответствовать равные функции.
Определение. Функции называются равными, если на всех наборах значений переменных функции принимают равные значения.
Определение. Формула
A эквивалентна формуле
B


B
A 
, если соответствующие им функции равны.
Пример.
Записать формулу и построить таблицу для функции








z
y
x
g
g
g
z
y
x
g
,
,
,
,
2 3
4

. Здесь введены следующие обозначения:


y
x
y
x
g


,
1
;


y
x
y
x
g
&
,
2

;


y
x
y
x
g


,
3
;
 
x
x
g

4
Решение. Формула для этой функции:

 

z
y
x
z
y
x
g


&
,
,
. Построим таблицу ее значений. x y z
y
x &


z
y
x

&


z
y
x

&
0 0 0 0 1
0 0 0 1 0 1
0 0 1 0 0 1
0 0 1 1 0 1
0 1 0 0 0 1
0 1 0 1 0 1
0 1 1 0 1 0
1 1 1 1 1 1
0
Среди значений функции число 1 нечетно, все ее переменные существенные.
4.4. Законы алгебры логики
1. Законы ассоциативности
1.1.




z
y
x
z
y
x
&
&
&
&


1.2.




z
y
x
z
y
x





1.3.




z
y
x
z
y
x





1.4.




z
y
x
z
y
x





1.5.




z
y
x
z
y
x





2. Законы коммутативности
2.1.
x
y
y
x
&
&

2.2.
x
y
y
x



2.3.
x
y
y
x



2.4.
x
y
y
x



2.5.
x
y
y
x



2.6.
x
y
y
x



3. Законы дистрибутивности
3.1.



 

z
y
z
x
z
y
x
&
&
&



3.2.



 

z
y
z
x
z
y
x




&
&
3.3.






z
y
z
x
z
y
x
&
&
&



4. Закон двойного отрицания
x
x 
5. Законы де Моргана
5.1.
y
x
y
x


&
5.2.
y
x
y
x
&


6. Свойства 0 и 1 6.1.
x
x
x

&
6.2.
0
&

x
x
6.3.
0 0
& 
x
6.4.
x
x

1
&
6.5.
x
x
x


6.6.
1

 x
x
6.7.
x
x

 0 6.8.
1 1 

x
6.9.
0

 x
x
6.10.
1

 x
x
6.11.
x
x

 0 6.12.
x
x

 1 6.13.
1


x
x
6.14.
0


x
x
6.15.
x
x

0

6.16.
x
x

1

6.17.
1

 x
x
6.18.
x
x
x


6.19.
x
x

 0 6.20.
1 1 

x
6.21.
1 0

 x
6.22.
x
x 

1 7. Выражение для эквивалентности
1






y
x
y
x
y
x
8. Выражение для сложения по модулю 2
y
x
y
x
y
x
&
& 


9. Выражения для импликации
9.1.
y
x
x
y
y
x





9.2.
x
y
y
x



9.3.


y
x
y
x
y
x
y
x







1
&
10.
10.1.

 
 

z
x
y
x
z
y
x




&
&
10.2.




z
y
x
z
y
x




&
11. Законы поглощения

11.1.
x
xy
x


11.2.


x
y
x
x


&
11.3.
y
x
y
x
x



11.4.
y
x
xy
x



11.5.


xy
y
x
x


&
11.6.


y
x
y
x
x


&
Для упрощения записи иногда опускают скобки. Если нет скобок, то очередность выполнения логических операций определяет следующий приоритет:
1.
2.
&
3.

4.

или
5.  .
4.5.
Функция, двойственная данной функции.
Самодвойственная функция. Теорема двойственности.
Принцип двойственности
Определение.
Функция




n
n
x
x
x
f
x
x
x
f
,...,
,
,...,
,
*
2 1
2 1

называется двойственной функцией к функции


n
x
x
x
f
,...,
,
2 1
Таблица для двойственной функции
*
f
при упорядоченном порядке наборов значений переменных получается из таблицы для функции


n
x
x
x
f
,...,
,
2 1
построением


n
x
x
x
f
,...,
,
2 1
(то есть заменой значений функции
f 0 на 1, 1 на
0) и переворачиванием столбца значений
f
Пример.
x y z


z
y
x
f
,
,


z
y
x
f
,
,




z
y
x
f
z
y
x
f
,
,
*
,
,

0 0 0 0 1
0 0 0 1 1 0
0 0 1 0 0 1
1 0 1 1 0 1
0 1 0 0 1 0
1 1 0 1 0 1
1 1 1 0 1 0
0 1 1 1 1 0
1
Определение. Если имеет место равенство




n
n
x
x
x
f
x
x
x
f
,...,
,
*
,...,
,
2 1
2 1

, то функция


n
x
x
x
f
,...,
,
2 1
называется самодвойственной.
Теорема двойственности. Если



 





m
mp
m
m
p
p
n
x
x
f
x
x
f
x
x
f
f
x
x
,...,
,...,
,...,
,
,...,
,...
1 2
21 2
1 11 1
1 2
1


, где
n
x
x ,...,
1
- различные переменные, входящие в наборы




m
mp
m
p
x
x
x
x
,...,
,...,
,...,
1 1
11 1
. Тогда




 





m
mp
m
m
p
p
n
x
x
f
x
x
f
x
x
f
f
x
x
,...,
,...,
,...,
,
,...,
*
,...
*
1
*
2 21
*
2 1
11
*
1 1
2 1


Принцип двойственности. Если формула


s
f
f
C
A
,...,
1

реализует функцию


n
x
x
f
,...,
1
, то формула


*
*
1
,...,
s
f
f
C
, то есть формула, полученная из A заменой функций
s
f
f ,...,
1
соответственно на
*
*
1
,...,
s
f
f
, реализует функцию


n
x
x
f
,...,
*
1
Эту формулу назовем формулой, двойственной к A , обозначим *
A .
Для формул над множеством


y
x
y
x
x
x
P


,
&
,
,
,
1
,
0
принцип двойственности может быть сформулирован следующим образом: для получения формулы
*
A , двойственной к формуле A , нужно в формуле A заменить 0 на 1, 1 на 0, x на
x ,
x
на
x
,
y
x & на
y
x 
и
y
x 
на
y
x & .
4.6. Разложение булевых функций по переменным.
СДНФ. СКНФ
Введем обозначение:



x
x
x


, где

- параметр, принимающий значение
0 или 1. Таким образом,









1
,
0
,
x
x
x
Другими словами,
x
x 
0
,
x
x 
1
Введем следующие обозначения:
s
i
s
i
x
x
x
x
&
&
&
2 1
1
&


,
1

s
s
i
s
i
x
x
x
x






2 1
1
,
1

s
Теорема о разложении функций по
m переменным. Каждую функцию алгебры логики


n
x
x
f
,...,
1
при любом m


n
m 

1
можно представить в следующем виде:




n
m
m
m
n
m
m
x
x
f
x
x
x
x
x
x
x
f
m
m
,...,
,
,...
&
,...,
,
,...
1 1
2 1
1 1
2 1
1











, где дизъюнкция берется по всевозможным наборам значений переменных
m
x
x ,...,
1
Следствие 1. Разложение по i -ой переменной






n
i
i
i
n
i
i
i
n
i
i
x
x
x
x
f
x
x
x
x
x
f
x
x
x
x
x
f
,...,
,
1
,
,...
&
,...,
,
0
,
,...
&
,...,
,
,...
1 1
1 1
1 1
1 1







Следствие 2. Разложение по всем
n переменным – совершенная
дизъюнктивная нормальная форма (СДНФ).




n
n
n
n
f
n
x
x
x
x
x
f







,...,
2 1
1 1
2 1
1
,...,
1



Теорема. Каждая функция алгебры логики может быть выражена в виде

суперпозиции функций отрицание, дизъюнкция, конъюнкция.
Записав СДНФ для функции
*
f
и применив к ней принцип двойственности, получим совершенную конъюнктивную нормальную форму (СКНФ):






n
n
n
n
f
n
x
x
x
x
x
f












,...,
2 1
1 1
2 1
0
,...,
1
&
Таким образом, в качестве средства для задания булевых функций наряду с таблицами можно использовать язык формул над множеством функций, состоящим из отрицания, конъюнкции и дизъюнкции.
4.7. Полнота системы функций. Замыкание множеств
Определение. Система функций


s
f
f
f
,...,
,
2 1
из
2
P называется полной, если любая булева функция может быть записана в виде суперпозиции функций этой системы.
Теорема, позволяющая сводить вопрос о полноте одних систем к вопросу о
полноте других систем. Пусть даны две системы функций из
2
P :


,...
,
2 1
f
f
R 
и


,...
,
2 1
g
g
S 
, относительно которых известно, что система
R полна, и каждая ее функция выражается в виде суперпозиции функций из
S
Тогда система
S
является полной.
Определение. Пусть M - некоторое подмножество булевых функций.
Замыканием M называется множество всех булевых функций, являющихся суперпозицией функций из M .
Обозначение:
 
M - замыкание M .
Определение. Класс (множество) M называется замкнутым, если замыкание
M равно M :
 
M
M 
Определение (второе определение полноты). M - полная система, если
 
2
P
M 
4.8. Замкнутые классы: Т0, Т1, S
Определение.
0
T - это класс всех булевых функций




2 2
1
,...,
,
P
x
x
x
f
n

, сохраняющих константу 0, то есть функций, для которых выполняется равенство


0 0
,...,
0
,
0

f
Определение.
1
T - это класс всех булевых функций




2 2
1
,...,
,
P
x
x
x
f
n

, сохраняющих константу 1, то есть функций, для которых выполняется равенство


1 1
,...,
1
,
1

f
Определение.
S
- класс всех самодвойственных функций.
Классы
0
T ,
1
T и
S
являются замкнутыми классами:
 
0 0
T
T

,
 
1 1
T
T 
,
 
S
S 

4.9. Класс монотонных функций
Введем обозначение:


n



,...,

1

,


n




,...,

1

,
 


n
f
f



,...,

1

Определение. Для двух наборов переменных


и


выполняется отношение предшествования




, если
i

i
i

 
Определение. Функция


n
x
x
f
,...,
1
называется монотонной, если



,


,




имеет место неравенство
 
 




f
f

M - класс всех монотонных функций. Класс M замкнут:
 
M
M 
4.10. Полином Жегалкина. Класс линейных функций.
Способы определения линейности функций
Определение. Полиномом Жегалкина от переменных
n
x
x
x
,...,
,
2 1
называется сумма по модулю 2 вида



s
s
s
i
i
i
i
i
i
i
i
x
x
a
2 1
1 2
1
. Коэффициент
0

j
a
или 1.
Слагаемых в этой сумме столько, сколько подмножеств


s
i
i ,...,
1
в множестве из
n чисел


n
,...,
2
,
1
, то есть
n
2 .
Число полиномов Жегалкина от переменных
n
x
x
x
,...,
,
2 1
равно
n
2 2
, то есть числу всех булевых функций от n переменных.
Полиномы Жегалкина от одной, двух и трех переменных имеют следующий вид:
 
0 1
a
x
a
x
ПЖ




0 2
1 12
,
a
y
a
x
a
xy
a
y
x
ПЖ






0 3
2 1
13 23 12 123
,
,
a
z
a
y
a
x
a
xz
a
yz
a
xy
a
xyz
a
z
y
x
ПЖ








Теорема Жегалкина. Каждая булева функция может быть выражена при помощи полинома Жегалкина, причем единственным образом.
Способы нахождения полинома Жегалкина:
1) законы алгебры логики;
2) СДНФ или СКНФ, где
y
x
xy
y
x




;
3) метод неопределенных коэффициентов.
Определение. Функция называется линейной, если ее можно представить в следующем виде:


0 2
2 1
1 1
,...,
a
x
a
x
a
x
a
x
x
f
n
n
n





Следствие. Функция будет линейной, если в полиноме Жегалкина нет конъюнкции.
4.11. Представление булевой функции в виде диаграммы
Для наглядности булеву функцию представляют в виде диаграммы.
Диаграммы для констант 0 и 1 приведены на рисунке 4.1.

или
Рис. 4.1.
Диаграмма для функции одной переменной
 
x
f
приведена на рисунке 4.2.
Значения переменной на диаграмме приведены в скобках. Слева приведены значения функции.
Рис. 4.2.
Диаграмма для функции двух переменных


y
x
f
,
приведена на рисунке 4.3.
Стрелками отмечено направление изменения (роста) соответствующих переменных.
Рис. 4.3.
Диаграмма для функции трех переменных


z
y
x
f
,
,
приведена на рисунке 4.4.

Рис. 4.4.
Правило определения монотонности по диаграмме. Функция является монотонной, если при прохождении диаграммы снизу вверх любыми путями не происходит нарушения монотонности.
Правило определения линейности по диаграмме. Чтобы определить линейность по диаграмме, необходимо сначала удалить все фиктивные переменные. Функция будет линейной, если на каждом ярусе значения одинаковые, а при переходе от яруса к ярусу значение меняется.
4.12. Критерий Поста полноты системы функций. Базис полной системы функций алгебры логики
Критерий полноты (теорема Поста). Для того, чтобы система функций была полной, необходимо и достаточно, чтобы она целиком не содержалась нив в одном из пяти замкнутых классов
0
T ,
1
T ,
S
, M , L .
Следствие 1. Всякий замкнутый класс
N
функций из
2
P такой, что он не совпадает с
2
P , содержится, по крайней мере, в одном из построенных классов.
Определение. Класс R функций из
2
P называется предполным, если R не является полным, а для любой функции
2
P
f 
класс
 
f
R 
является полным.
То есть предполный класс является замкнутым.
Следствие 2. В алгебре логики существует только пять предполных классов:
0
T ,
1
T ,
S
, M , L .
Теорема. Из всякой полной в
2
P системы функций P можно выделить полную подсистему, содержащую не более четырех функций.
Определение. Система функций


s
f
f ,...,
1
является базисом, если она полна, а всякая ее собственная система не полна.
Теорема. Любая полная система имеет базис, состоящий не более чем из

четырех функций.
Задачи.
4.1. Функции заданы таблицей.
Определить, какие переменные существенные, какие фиктивные. Удалить фиктивные переменные. Для каждой функции написать формулу, реализующую ее. а) x y f
1
f
2
f
3
f
4
б) x y z f
5
f
6
f
7 0 0 1 1 1 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 4.2. Построить таблицу значений функций а)


y
y
x


б)




z
y
y
x


&
4.3. Записать формулу и построить таблицу для функции а)










z
y
f
f
z
x
f
f
z
y
x
g
,
,
,
,
,
4 8
2 3
1

б)












y
x
f
z
f
z
y
f
f
f
z
y
x
g
,
,
,
,
,
,
1 2
3 8
5 2

здесь введены следующие обозначения:


y
x
y
x
f


,
1
;


y
x
y
x
f
&
,
2

;


y
x
y
x
f


,
3
;


y
x
y
x
f


,
4
;


y
x
y
x
f

,
5

;


y
x
y
x
f
/
,
6

;


y
x
y
x
f


,
7
;
 
x
x
f

8 4.4. Записать формулу и построить таблицу функции. Определить, какие переменные существенные, какие фиктивные. Фиктивные переменные удалить.
Значения функций см. в задаче 4 а)








y
x
f
z
f
f
z
y
x
g
,
,
,
,
3 4
8 1

б)












x
z
f
f
z
y
f
x
f
f
z
y
x
g
,
,
,
,
,
,
4 8
2 1
6 2

4.5. Алгебраическими преобразованиями упростить выражение а)
z
x
yz
xy
x



б)
yz
x
z
y
x
z
xy
xyz



4.6. Выразить
y
x 
через
&
и

4.7. Найти двойственные функции ко всем элементарным функциям.
4.8. Найти функции, двойственные данным функциям, используя принцип двойственности


y
z
y
x
f



1

 

z
x
y
x
f
|
2




 

y
x
z
x
f




3
z
y
x
f



4


z
y
x
f



5


y
x
z
f



6




x
z
y
x
f




7




x
z
y
x
f




8




x
z
y
x
f




9




z
x
y
x
f



|
10




y
z
y
x
f



|
11 4.9. Построить таблицу значений функций. Найти двойственные функции (по

таблице). Определить, принадлежат ли функции замкнутым классам
S
T
T
,
,
1 0
Найти СДНФ, СКНФ
z
xy
f


1


z
y
x
f

2




z
y
x
f
&
3




y
z
x
f



4


z
y
x
f
&
5




y
z
x
f



6 4.10. Заполнить таблицу для функций, используя диаграмму булевой функции.
Записать полином Жегалкина (МНК). x y z f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12 0 0 0 0 0 0 1 0 0 1 0 0 1 1
0 0 0 1 0 0 1 1 0 1 0 0 1 0 1
1 0 1 0 0 1 0 0 0 0 1 1 1 0 1
0 0 1 1 1 0 1 1 0 1 0 1 1 1 0
0 1 0 0 0 1 0 0 1 1 1 0 0 0 1
1 1 0 1 1 0 1 1 1 0 1 1 0 1 1
0 1 1 0 1 0 1 1 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 0 0 1 1 1 0 1
0
T
0
T
1
S
M
L
4.11. Дана система функций


5 4
3 2
1
,
,
,
,
f
f
f
f
f
. Построить таблицу функций
)
5
...,
,
1
(
,

i
f
i
. Определить:
?
,
,
,
,
1 0
L
M
S
T
T
f
i

(с доказательством!!!).
Заполнить таблицу Поста. Определить полноту системы функций по критерию Поста. Если система неполна, доопределить ее до полной системы одной функцией (зависящей не более, чем от двух переменных). Нельзя добавлять:
y
x
y
x

,
/
. Из полной системы выделить базисы

1   2   3   4   5   6

---

Глава 5. Теория графов
5.1. Способы задания графа. Орграф. Полный граф.
Дополнение графа. Надграф, подграф
Для описания строения различных систем, состоящих из взаимосвязанных элементов, часто используют графические системы, изображая элементы точками (кружками, прямоугольниками), а связи между ними – линиями, соединяющими точки. При этом получаются диаграммы вроде следующих:
В этих изображениях ни изображения точек, ни форма, ни длина линий не играют роли. Существенно лишь, какие пары точек соединены линиями. В частности, графы 6, 7, 8 изображают один и тот же граф, 3, 4, 5 – тоже.
Эти же структуры можно описать, не прибегая к графическому изображению.
Для этого требуется, например, перечислить пары связанных между собой элементов. Для графа 3: (A, B), (B, E), (B, C), (C, D), (B, D), (D, E). При этом порядок элементов парах не имеет значения: (A, B) = (B, A). Такие пары называются неупорядоченными. Этот перечень пар представляет собой граф.
Определение. Графом называется пара


E
V
G
,

, где
V
- непустое множество,


n
v
v
v
V
,...,
,
2 1

, E - некоторое множество неупорядоченных пар элементов
V
,




j
i
v
v
E
,

,
n
j
i
,
1
, 
Определение. Элементы множества
V
называются вершинами, элементы E - ребрами графа.
Определение. Если


E
v
u
x


,
, то вершины u и v называются смежными вершинами в графе
G
. В этом случае вершина u и ребро x - инцидентны, так же и как вершина v и ребро x .
Определение. Если два различных ребра
E
y
x

,
инцидентны одной и той же вершине, то они называются смежными.
Определение. Число вершин, смежных с данной вершиной u , называется степенью вершины u . Если степень вершины равна 0, то вершина называется изолированной. Если степень вершины равна 1, то вершина называется тупиковой.
Определение. Граф называется конечным, если множество
V
конечно.
Граф с
p
вершинами и
q
ребрами называется


q
p,
-граф.
(1,0)-граф – это тривиальный граф, изображается одной точкой.
Определение. Геометрическая интерпретация графа называется диаграммой.
Обычно граф представляют диаграммой и называют ее графом.

---

Определение. Граф называется помеченным или перенумерованным, если его вершины отличаются одна от другой какими-либо пометками.
Способы задания графа:
1. Определение графа:


E
V
G
,

2. Геометрическая интерпретация (диаграмма).
3. Матричный способ.

---