Оглавление
Переключательные функции............................................................................	2
Основные понятия и определения ...............................................................	2
1.1. Переключательные функции одного и двух аргументов....................	4
1.2.2. Переключательные функции двух аргументов. Существует
шестнадцать различных переключательных функций двух
аргументов, каждая из которых определена на четырех наборах. Эти
функции представлены в табл. 1.4. ..........................................................	4
1.3. Представление переключательной функции в виде многочленов. .......	7
1.4. Пять классов переключательных функций. Теорема о
функциональной полноте................................................................................	12
Линейные..........................................................................................................	16
1.5. Функционально полные системы логических функций.......................	17
2. МИНИМИЗАЦИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ.....................	24
2.1. Вхождение функции в функцию. Импликанты................................	24
2.2. Теорема Квайна.....................................................................................	27
2.3. Метод импликантных матриц .............................................................	29
2.4. Метод испытания импликант..............................................................	33
2.5. Минимизация переключательных функций с помощью диаграмм
Вейча.............................................................................................................	35
2.6. Второй метод получения минимальных КНФ...................................	41
2.7. Минимизация неполностью определенных переключательных
функций ........................................................................................................	44
1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ ГРАФОВ........	50
2. ТИПЫ ГРАФОВ.......................................................................................	57
3. МАТРИЦЫ ГРАФОВ..............................................................................	60
4.ОПЕРАЦИИ НА ГРАФАХ.....................................................................	66
5. СВЯЗНЫЕ ГРАФЫ. КОМПОНЕНТА СВЯЗНОСТИ..........................	79
6. ДЕРЕВЬЯ И ИХ СВОЙСТВА ................................................................	85
Алгоритм построения минимального каркаса......................................	91
Обоснование алгоритма..........................................................................	92
7. ЭЙЛЕРОВЫ ЦЕПИ И ЦИКЛЫ..............................................................	93
Алгоритм построения эйлерова цикла ..................................................	95
Обоснование алгоритма..........................................................................	96
8.НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ..........................	97
Алгоритм Флойда ........................................................................................	99
ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ...........................................................	102

1

Переключательные функции

Основные понятия и определения

Будем рассматривать только функции конечного числа аргументов. Рассмотрим множество векторов Xˆ ={<x1, … , xn>}, координаты ко-

торых могут принимать лишь два значения - 0 или 1. Тогда множество Xˆ состоит из 2n различных векторов. Сопоставим каждому вектору из Xˆ символы 0 или 1, т.е. произведем однозначное отображение множества X на множество Y = {0,1}.

Определение 1.1.1. Функцией алгебры логики, или переключатель-

ной функцией, называется функция, дающая однозначное отображение Xˆ в Y [1].

Из этого определения следует, что функция f(x1, … ,xn) называется переключательной, если она, так же как и ее аргументы, может принимать только значения из двухбуквенного алфавита, например, 0 и 1.

Поскольку аргументы переключательной функции могут принимать только два значения, то область определения любой переключательной функции конечна. Совокупность значений аргументов называется набором и обозначается a1, …, ai, …, an, где ai равно 0 или 1 (i = 1, …, n). Каждый набор может быть представлен n–разрядным двоичным числом, а количество двоичных n–разрядных чисел равно 2n. Поэтому любая переклю-

чательная функция может быть определена на 2n наборах.

Например, переключательные функции двух аргументов определены на четырех наборах (00, 01, 10, 11), а переключательные функции трех аргументов – на восьми. Таким образом, переключательная функция может быть задана таблицей, в которой перечислены все возможные значения аргументов функции (наборы) и соответствующие этим наборам значения функции. Такая таблица называется таблицей истинности переключательной функции. Пример переключательной функции трех аргументов приведен в табл. 1.1.

Таблица 1.1 Таблица значений переключательной функции

x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
f(x1,x2,x3)	0	0	1	1	1	0	1	0

Каждому набору аргументов можно приписать номер, равный двоичному числу, соответствующему данному набору:

0,0,0,0,0 — нулевой набор;

0,0,0,0,1 — первый набор;

2

. . . . . . . . . . . . . . . . . . . . . . .

1,1,1,1,1 — тридцать первый набор.

Набор, содержащий все единицы (1,1, …, 1), называют единичным набором.

Переключательная функция n аргументов определена на 2n наборах, на которых она может принимать значения 0 или 1. Поэтому в соответствие каждой переключательной функции можно поставить 2n-разрядное

двоичное число. Количество 2n-разрядных двоичных чисел равно 22n . Та-

ким образом, число различных переключательных функций n аргументов

конечно и равно 22n .

Припишем каждой переключательной функции номер, равный двоичному числу, образованному значениями переключательной функции на всех наборах. Этот номер записывается слева направо, начиная со значения функции на нулевом наборе. Например, двоичное число, образованное значениями функции из табл. 1.1, 00111010(2), равно 58 в десятичной системе счисления и функцию можно обозначить следующим образом:

f(x1,x2,x3) = f58(x1,x2,x3).

Пример 1.1. Составить таблицу истинности для переключательной функции номер 23805 четырех аргументов.

Решение. Переключательная функция четырех аргументов определяется на 24 = 16 наборах (табл. 1.2) . Для получения значений функций представим число 23805 в двоичной системе счисления: 23805(10) = = 101110011111101(2). Полученное двоичное число имеет 15 двоичных разрядов, и для представления переключательной функции необходимо дополнить полученный код до 16-разрядного: 0101110011111101.

Таблица 1.2 Таблица переключательной функции f23805(x1,x2,x3,x4)

x1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
x2	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
x3	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
x4	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
f23805(x1,x2,x3,x4)	0	1	0	1	1	1	0	0	1	1	1	1	1	1	0	1

Определение 1.1.2.Если две переключательные функции f(x1, …, xn)

и φ(x1, …, xn) одного и того же числа аргументов принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f и φ называются равными.

Факт равенства функций f и φ записывается так:

f(x1, …, xn) = φ(x1, …, xn).

Определение 1.1.3. Переключательная функция f(x1, …xi-1,xi,xi+1, …, xn) существенно зависит от аргумента xi, если имеет место соотношение

3

f(x1, …xi-1, 0, xi+1, …, xn) ≠f(x1, …xi-1, 1, xi+1, …, xn).

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

1.1. Переключательные функции одного и двух аргументов

1.2.1.Переключательные функции одного аргумента.

Существует четыре переключательные функции одного аргумента, которые приведены в табл. 1.3.

				Таблица 1.3
	Переключательные функции одного аргумента
x	0	1	Условное обозначение	Название функции
f(x)
f0(x)	0	0	0	Константа нуль
f1(x)	0	1	x	Переменная x
f2(x)	1	0	x	Инверсия x
f3(x)	1	1	1	Константа единица

Функция f0(x) тождественно равна нулю. Она называется константой нуль и обозначается f0(x)=0.

Функция f1(x) повторяет значения аргумента и поэтому тождественно равна переменной x.

Функция f2(x) принимает значения, противоположные значениям аргумента: если x=0, то f2(x)=1; если x=1, то f2(x)=0. Эту функцию называют инверсией x или отрицанием x и вводят для нее специальное обозначение

f2(x)= x .

Функция f3(x) тождественно равна единице. Она называется кон-

стантой единица и обозначается f3(x)=1.

1.2.2. Переключательные функции двух аргументов. Существует шестнадцать различных переключательных функций двух аргументов, каждая из которых определена на четырех наборах. Эти функции представлены в табл. 1.4.

В число шестнадцати переключательных функций входят функции, рассмотренные в п.1.2.1:

f0(x,y)	= 0	— константа нуль;
f15(x,y)	= 1	— константа единица;
f3(x,y)	= x	—переменная x;
f5(x,y)	= y	—переменная y;
f12(x,y)	= x	—инверсия x;

4

		f10(x,y)			= y —инверсия y;
						Таблица 1.4
					Переключательные функции двух аргументов
x	0	0	1	1	Название функции	Обозначе-
y	0	1	0	1		ние
f0(x,y)	0	0	0	0	Константа нуль		0
f1(x,y)	0	0	0	1	Произведение (конъюнкция)	x·y; x y;x&y
f2(x,y)	0	0	1	0	Функция запрета по y	x	y
f3(x,y)	0	0	1	1	Переменная x		x
f4(x,y)	0	1	0	0	Функция запрета по x	y	x
f5(x,y)	0	1	0	1	Переменная y		y
f6(x,y)	0	1	1	0	Сумма по модулю 2 (логическая неравнозначность)	x y
f7(x,y)	0	1	1	1	Логическое сложение (дизъюнкция)	x+y; x y
f8(x,y)	1	0	0	0	Операция Пирса (стрелка Пирса)	x↓y
f9(x,y)	1	0	0	1	Эквивалентность (логическая равнозначность)	x~y
f10(x,y)	1	0	1	0	Инверсия y		y
f11(x,y)	1	0	1	1	Импликация от y к x	y→x
f12(x,y)	1	1	0	0	Инверсия x		x
f13(x,y)	1	1	0	1	Импликация от x к y	x→y
f14(x,y)	1	1	1	0	Операция Шеффера (штрих Шеффера)	x y
f15(x,y)	1	1	1	1	Константа единица		1

Рассмотрим некоторые переключательные функции двух аргументов. Функция f1(x,y) называется конъюнкцией, или логическим умножением. Таблица истинности этой функции совпадает с таблицей умножения двух одноразрядных двоичных чисел. Можно ввести функцию n аргументов, соответствующую произведению n одноразрядных двоичных чисел. Такая переключательная функция равна единице тогда и только тогда, когда все ее аргументы равны единице. Для конъюнкции справедливы сле-

дующие соотношения:

x 0 = 0; x 1 = x; x x = x;

x y = y x; x x = 0.

Функция f7(x,y) называется дизъюнкцией или логическим сложением. Эта функция равна нулю только в том случае, когда все ее аргументы равны нулю. Можно ввести функцию n аргументов, соответствующую логическому сложению n одноразрядных двоичных чисел. Такая переключа-

5

тельная функция равна нулю тогда и только тогда, когда все ее аргументы равны нулю. Для конъюнкции справедливы следующие соотношения:

x 0 = x; x 1 = 1; x x = x;

x y = y x; x x = 1.

Таблица истинности функции f6(x,y) совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю два. Можно ввести функцию n аргументов, соответствующую сумме по модулю два n одноразрядных двоичных чисел. Такая переключательная функция определяется следующим условием: она равна единице, если число аргументов, равных единице, нечетно, и равна нулю, если число таких аргументов четно. Приведем некоторые соотношения для суммы по модулю два:

x 0 = x; x 1 = x ; x x = 0;

x x x = x; x y = y x.

Рассмотренные шестнадцать функций двух аргументов (будем называть их элементарными) позволяют строить новые переключательные функции следующим образом:

•путем перенумерации аргументов;

•путем подстановки в функцию новых функций вместо аргументов. Функцию, полученную из функций f1, f2, …, fk путем применения

(возможно многократного) этих двух правил, будем называть суперпозицией функций f1, f2, …, fk. Например, имея элементарные функции инверсии, конъюнкции, дизъюнкции, импликации, запрета, сложения по модулю два, можно составить новую переключательную функцию:

f (x,y,z) = (( x y) z) ((y→z) x).

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

Пример 2.1. Представить в виде таблицы функцию f (x,y,z) = (( x y) z) ((y→z) x).

Решение. Функцию f (x,y,z) будем представлять последовательно, записывая в столбцы табл. 1.5 промежуточные результаты, получаемые после выполнения каждой операции:

6