Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Определение. Система функций алгебры логики A  P₂ называется базисом (в P₂), если

1. [A] = P₂;

2. f  A ([A \ {f}]  P₂).

Теорема 13. Максимальное число функций в базисе алгебры логики равно 4.

Доказательство. 1) Докажем, что из любой полной системы можно выделить полную подсистему, содержащую не более четырёх функций. Действительно, если A — полная система ([A] = P₂), то согласно теореме Поста в ней существуют пять функций f₀  T₀, f₁  T₁, f_S  S,
f_M  M, f_L  L. По теореме Поста система функций {f₀, f₁, f_S, f_M, f_L} полна. Рассмотрим функцию f₀ (x₁, …, x_n)  T₀ (f₀ (0, 0, …, 0) = 1). Возможны два случая:

1. f₀ (1, 1, …, 1) = 1  f₀  S  [f₀, f₁, f_L, f_M] = P₂ и система
   {f₀, f₁, f_L, f_M} полна.

2. f₀ (1, 1, …, 1) = 0  f₀  M, T₁  [f₀, f_L, f_S] = P₂ и система {f₀, f_L, f_S} полна.

2) Покажем, что существует базис алгебры логики из четырёх функций. Действительно, рассмотрим систему функций

{0, 1, x · y, x  y  z}.

Эта система функций полная, так как 0  T₁, S, 1  T₀, x · y  L,
x  y  z  M (0  0  1 = 1, 0  1  1 = 0). Однако, любая её подсистема не полна:

{0, 1, x · y}  M

{0, 1, x  y  z}  L

{0, xy, x  y  z}  T₀

{1, xy, x  y  z}  T₁.

Теорема доказана.

§13. Теорема о предполных классах

1 . Предполные классы.

Определение. Пусть A  P₂. A называется предполным классом, если

1. [A]  P₂;

2. fP₂ ( fA  [A{f}] = P₂).

Теорема 14. В P₂ предполными являются лишь следующие 5 классов: T₀, T₁, S, L, M.

Доказательство. 1) Покажем сначала, что ни один из этих пяти классов не содержится в другом. Для этого достаточно для каждого из пяти вышеперечисленных классов указать четыре функции, принадлежащие данному классу, но не принадлежащие остальным четырем:

	T0	T1	L	M	S
T0		0	xy	x  y	0
T1	1		xy	x  y  1	1
L	1	0		x  y	0
M	1	0	xy		0
S			xy  yz  zx

2) Докажем, что все классы — T₀, T₁, S, L, M являются предполными. Действительно, пусть N  {T₀ , T₁ , L, M , S} и f  N. Тогда система N  {f} не содержится ни в одном из пяти классов Поста (так как N не содержится в четырёх из них, а f не содержится в N). Следовательно, система N  {f} — полная и N — предполный класс.

3) Пусть A — предполный класс. Тогда [A]  P₂   N{T₀, T₁, L, M, S}: A  N. Если A  N, то  f ( f  N, f  A):

A  {f}  N  [A  {f}]  P₂.

Полученное противоречие завершает доказательство.

2 . Результаты Поста.

1. В P₂ существует ровно счётное число замкнутых классов.

2. В любом замкнутом классе существует конечный базис.

§14. k-значные функции. Теорема о существовании конечной полной системы в множестве k-значных функций

1°. k-значные функции. Будем рассматривать конечный алфавит E_k = {0, 1, 2, …, k – 1}. Функцией k-значной логики назовём отображение вида f (x₁, x₂, …, x_n): .

Некоторые функции k-значной логики.

1. Константы 0, 1, 2, …, k – 1 (всего — k);

2. Тождественная функция f (x) = x;

3. Отрицания: f (x) = = x + 1 (mod k) — отрицание Поста,
   f (x) = ~ x = (k – 1) – x — отрицание Лукасевича;

4. Сложение по модулю k: f (x, y) = x + y (mod k);

5. Умножение по модулю k: f (x, y) = xy (mod k);

6. Максимум: max (x, y);

7. Минимум: min (x, y);

8. .

Теорема 15. Система

{0, 1, …, k – 1, max (x, y), min (x, y), J₀ (x), J₁ (x), …, J_{k – 1} (x)}

полна в P_k.

Доказательство. Утверждается, что для любой функции
f (x₁, …, x_n)  P_k справедливо представление

.

Действительно, для любого набора рассмотрим значение правой части: если существует такое i , что σ_i  α_i, то и весь минимум станет равным нулю. Таким образом, правая часть станет равна

,

а учитывая то, что в P_k

J_a (a) = k – 1,

получим, что правая часть равна просто . Теорема доказана.

Замечание.

min (x₁, x₂, x₃) = min (x₁, min (x₂, x₃));

min (x₁, x₂, …, x_n) = min (x₁, min (x₂, … ,x_n)).

Аналогично определяется функция максимума от n переменных.

2°. Особенности k-значной логики.

1. В P_k существует континуум замкнутых классов (при k  3).

2. В P_k существуют замкнутые классы с бесконечным базисом (при k  3).

3. В P_k существуют замкнутые классы, не имеющие базиса (при
   k  3).

Глава II. Основы теории графов

§15. Основные понятия теории графов. Изоморфизм графов. Связность

Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение:
G = (V, E).

В дальнейшем будем рассматривать конечные графы, то есть графы с конечным множеством элементов и конечным семейством пар.

Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то граф называется неориентированным, а пары называются рёбрами. Если же элементы из E рассматривать как упорядоченные, то граф ориентированный, а пары — дуги.

Определение 3. Пара вида (a, a) называется петлёй, если пара
(a, b) встречается в семействе E несколько раз, то она называется кратным ребром (кратной дугой).

Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом.

Определение 5. Две вершины графа называются смежными, если они соединены ребром.

Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину.

Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентных данной вершине. Для псевдографа полагают учитывать петлю дважды.

Утверждение 1. В любом графе (псевдографе) справедливо следующее соотношение: , где p — число вершин, а q — число рёбер.

Доказательство. Когда мы считаем степень одной вершины, мы считаем все рёбра, выходящие из неё. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу рёбер. Утверждение доказано.

Определение 8. Пусть множество вершин графа V = {v₁, v₂, …, v_p}. Тогда матрицей смежности этого графа назовём матрицу A = ||a_ij||, где a_ij = 1, если вершины v_i и v_j смежны (2, 3, … для мультиграфа или псевдографа) и 0 в противном случае, a_ii при этом равно числу петель в вершине v_i.

Определение 9. Два графа (или псевдографа) G₁ = (V₁, E₁) и
G₂ = (V₂, E₂) называются изоморфными, если существуют два взаимно однозначных отображения φ₁: V₁  V₂ и φ₂: E₁  E₂ такие, что для любых двух вершин u и v графа G₁ справедливо φ₂ (u, v) =
= (φ₁ (u), φ₁ (v)).

Определение 10 (изоморфизм графов без петель и кратных рёбер). Два графа G₁ = (V₁, E₁) и G₂ = (V₂, E₂) называются изоморфными, если существует взаимно однозначное отображение φ₁: V₁  V₂ такое, что (u, v)  E₁  (φ (u), φ (v))  E₂.

Определение 11. Граф G₁ = (V₁, E₁) называется подграфом графа G = (V, E), если

V₁  V, E₁  E.

Определение 12. Путём в графе G = (V, E) называется любая последовательность вида

v₀, (v₀, v₁), v₁, (v₁, v₂), …, v_{n – 1}, (v_{n – 1}, v_n), v_n.

Число n в данных обозначениях называется длиной пути.

Определение 13. Цепью называется путь, в котором нет повторяющихся рёбер.

Определение 14. Простой цепью называется путь без повторения вершин.

Утверждение 2. Пусть в G = (V, E) v₁  v₂ и пусть P — путь из v₁ в v₂. Тогда в P можно выделить подпуть из v₁ в v₂, являющийся простой цепью.

Доказательство. Пусть данный путь — не простая цепь. Тогда в нём повторяется некоторая вершина v, то есть он имеет вид:
P₁ = v₀C₁vC₂vC₃v₂. Тогда он содержит подпуть P₂ = v₀C₁vC₃v₂. Если в P₂ повторяется некоторая вершина, то аналогично удалим ещё кусок и так далее. Процесс должен закончиться, так как P₁ — конечный путь. Утверждение доказано.

Определение 15. Путь называется замкнутым, если v₀ = v_n.

Определение 16. Путь называется циклом, если он замкнут, и рёбра в нём не повторяются.

Характеристики

Список файлов лекций