Класс B будем называть замкнутым, если его замыкание совпадает с ним самим.

B = [B]

Теорема 1

Класс всех линейных функций замкнут.

Доказательство.

Пусть L – класс линейных функций (так и будем обозначать в дальнейшем).

L = {a₀+a₁x₁+a₂x₂+…+a_nx_n}

Подставим вместо переменной x в одну из функций функцию y такого же вида.

Получим

L = [L].

Утверждение (теорема 2)

Необходимое условие линейности.

Если функция линейна и не равна некоторой постоянной, то на половине своих наборов она равна 1.

Если в векторе значений функции число 0 и 1 различно, то функция обязательно нелинейна, а если число нулей совпадает с числом единиц, то эта функция может быть линейной, а может быть и нелинейной. В таком случае, чтобы это проверить, нужно выписать для нее многочлен Жегалкина.

Функция называется самодвойственной, если двойственная к ней функция является самой этой функцией. F* = F.

S – класс всех самодвойственных функций.

Класс S является функционально замкнутым.

Доказательство следует из принципа двойственности.

У самодвойственной функции на противоположных наборах противоположны значения.

Функция называется монотонной, если из условия следует, что f()f().

Теорема.

Класс M монотонных функций замкнут.

Свойство.

У монотонных функций сокращенная ДНФ не содержит отрицаний переменных, то есть все простые импликанты не содержат отрицаний.

Другие замкнутые классы

T₀ – константа 0 (класс функций, обращающихся на нулевом векторе в 0).

Т₁ – константа 1 (класс функций, обращающихся на единичном векторе в 1)

Теорема

Классы Т₀ и Т₁ функционально замкнуты.

Лемма о несамодвойственной функции.

Если функция несамодвойственна, то путем подстановки вместо аргументов переменной x или not(x) можно получить константу.

011 – нарушена самодвойственность

f(not(x),x,x) = const = 1 при любом x.

001 – нарушена самодвойственность

Если 0, то х с отрицанием, если 1, то без отрицания.

Доказательство _ _ _ _ _ _ _ _

F  S   : F*()  F()  F*() = F() F() = F()  F() = F()

(x) = {x₁^, x₂^2, … x_n^n}

(0) = {0^, 0^2, … 0^n}

Путем подстановки получаем, что (x) = const.

Лемма о немонотонной функции

Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).

000 

F(000) = 1 F(001) = 0

F(00X) = NOT(X)

F(100) = 1

F(110) = 0

100 < 110

F(1,x,0) = NOT(X)

Лемма о нелинейной функции

Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

___

F(x0y) = (xy)

Лекция 9

Доказательство леммы 3

F(x₁…x_n) = x₁x₂ (f1(x₁…x_n)) + x₁f₂(x₁…x_n) + x₂f₃(x₁…x_n) + f₄(x₁…x_n)

Вместо x₁…x_n ставим константы ₁…_n, такие, что

f1(₁…_n) = 1

1. A = B = 0

F(x₁x₂…₃…_n) = x₁x₂ + C = {x₁x₂, если с = 0 и NOT(x₁x₂, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

Теорема Поста.

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T₀, T₁.

1. Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).

Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то

[] = [B] = B

Но множество всех булевых функций, а B – не всех.

Получили противоречие.

Доказательство дано в виде алгоритма получения из системы основных элементарных булевых функций, образующих полную систему, значит и эта система будет полна.

Дано

{S, M, L, T₀, T₁}

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

1. Получение констант.

F1(00…0) = 1

1. F(111) = 1

2. F(111) = 0

F(xxxx) = 1

F2(111) = 0

1. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

1. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

Лекция 10

Функциональные элементы. Схемы

Ф

F

ункциональный элемент с n упорядоченными входами и одним выходом

.

При подаче на выходы любой комбинации двоичных сигналов, на выходе также возникает сигнал.

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).

Два и более входов можно отождествлять.

Возможные соединения функциональных элементов соответствуют булевым функциям и их суперпозициям.

Полный набор булевых функций, который мы будем использовать для построения логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из функциональных элементов.

Число функциональных переменных считаем сколь угодно большим.

Базис называется полным, если с его помощью можно реализовать любую булеву функцию в виде схемы.

Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.

Пример полного базиса.

&

V

- Конъюнктор

• Дизъюнктор

- Ин

__

вертор

Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно

1. Найти минимальную ДНФ.

2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.

Сумматор n-разрядных двоичных чисел

Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида

X = X_nX_n-1…X₁

Y = Y_nY_n-1…Y₁

Z = x+y = Z_n+1Z_n…Z₁

X+Y – сумма чисел.

Для решения такой задачи вводим q_i – единица переноса из одного разряда в другой.

Формулы сумматора

Z_i = X_i + Y_i + Q_i – сумма по модулю 2

Q_i+1 = X_iY_i V X_iQ_i V Q_iY_i

Лекция 11

Графы

Графом (G) будем называть тройку объектов (V, X, )

V – множество n вершин.

X – конечное множество ребер.

- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.

задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

V_j – начало ребра

V_k – его конец

x_i) = (V_j, V_k) – ребро инцидентно в вершине Vj и в вершине Vk.

Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.

Если на ребре x_i0

(x₀) = (V_j0, V_j0),

то ребро называется петлей.

Способы задания графов

1. Аналитический

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.

В конце выписываются все изолированные вершины.

1. Геометрический

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

1. С помощью матрицы инцидентности

A(m*n)

m = [V] – число вершин

n = [X}- число ребер

а) Неориентированные графы

A_ij = {0, если V_i не инцидентно x_j, 1, если V_i инцидентно x_j)

б) Орграфы

A_ij = {0, если V_i не инцидентно x_j, -1, если V_i - начало x_j, 1, если V_i - конец x_j)

Для петель нужны дополнительные предположения.

1. Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

Дальше все о неориентированных графах.

K1 – полный граф с одной вершиной

K2 – с двумя

K3 – с тремя

K4 – полный граф с четырьмя вершинами

K5 – полный пятивершинник

Граф называется двудольным, если множество вершин разбивается на 2 непересекающихся подмножества, такие, что ребра соединяют вершины из разных подмножеств.

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

Полный двудольный граф.

Маршруты, циклы, связности.