Файл: Дискретная математика.pdf

Скачать файл (1,69Мб)

Заказать решение

ВУЗ: Томский государственный университет систем управления и радиоэлектроники

Категория: Учебное пособие

Дисциплина: Дискретная математика

Добавлен: 28.11.2018

Просмотров: 7067

Скачиваний: 35

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ГЛОССАРИЙ

Биекция — это отображение, которое является одновременно и сюръективным,

и инъективным. При биективном отображении каждому элементу одного множе-
ства соответствует ровно один элемент другого множества, при этом определено
обратное отображение, которое обладает тем же свойством. Поэтому биективное
отображение называют ещё взаимно-однозначным отображением (соответствием),
одно-однозначным отображением.

Бихроматический граф — граф, у которого

(G) = 2, где χ(G) — хроматическое

число графа G.

Изоморфизм графов G

, U

) и H = (V

, U

) — это биекция между множе-

ствами вершин графов f ∶ V

Ð→ V

такая, что любые две вершины u и v графа G

смежны тогда и только тогда, когда вершины f (u) и f (v) смежны в графе H.

Импликанта. Булева функция g

, . . ., x

) является импликантой булевой функ-

ции f

, . . ., x

), если для любого набора переменных, на котором g = 1, справед-

ливо f

= 1.

Инъективность. Функция называется инъективной (или, коротко, инъекция),

если каждому элементу множества X сопоставлен один и только один элемент
множества Y.

K-хроматический граф. Граф G называется k-хроматическим, если

(G) = k.

Конечный граф — это граф G

(X,U), у которого количество его вершин ∣X∣

конечно.

Конъ ´

юнкция — логическая операция по своему применению максимально при-

ближенная к союзу «и». Синонимы: лог´ическое «И», лог´ическое умнож´ение, ино-
гда просто «И ». Конъюнкция может быть бинарной логической операцией, то есть
иметь два операнда, тернарной операцией, то есть иметь три операнда, или n-ар-
ной операцией, то есть иметь n операндов. В записи, по аналогии с умножением
в алгебре, знак логического умножения в конъюнкции может быть пропущен: ab.

Метрика — функция, определяющая расстояние в метрическом пространстве.

Метр´ическое простр´анство — множество, в котором определено расстояние

между любой парой элементов.

Глоссарий

Минтерм — булева функция, принимающая истинное значение лишь при одной-

единственной комбинации. Последовательность составления формы СНДФ: по
строке таблицы истинности составляют логическое выражение, которое являет-
ся произведением (конъюнкция) всех входных переменных с отрицанием или без
него. Эти элементарные произведения, в которых содержатся все переменные, на-
зываются конституентами или минтермами. Минтермы составляются только для
тех строчек таблицы истинности, в которых выходная переменная принимает зна-
чения логической единицы (или логического нуля).

Паросочетание — двудольный граф, в котором всякие два ребра не являются

смежными.

Плотный граф — это полный граф, у которого при каждой вершине имеется

петля.

Полный граф — это граф, у которого любые две вершины соединены ребром.

Пустой граф — это граф G

(X,U), состоящий только из изолированных вер-

шин, т. е. граф, не содержащий ни одного ребра

(∣U∣ = 0).

Сложная система — это собирательное название систем, состоящих из боль-

шого числа взаимосвязанных элементов.

Сюръективность. Функция f называется сюръективной (или, коротко, сюръ-

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

Т´ождество (в математике) — равенство, выполняющееся на всём множестве

значений входящих в него переменных (равенство, верное при любых значениях
переменных).

Функция. В самом общем виде, функция — это «закон», по которому каждому

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

Хроматическое число графа G — минимальное число цветов, в которые мож-

но раскрасить вершины G так, чтобы концы любого ребра имели разные цвета.
Обозначается

(G).

Элементарное произведение — конъюнкт, в который любая переменная входит

не более одного раза.