A | Б | В | Г | Д | Е | Ж | З | И | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ь | Ъ | Ы | Э | Ю | Я |
Алгебра (M;Ω) - множество М вместе с заданной на нем системой операций Ω = (φ1, φ2,...,φn) . Ω называется сигнатурой алгебры, а M носителем
Алгебра множеств (алгебра Кантора) на множестве Е - алгебра {В(Е);
,
, ┐),
т.е алгебра на булеане В(Е) с операциями объединения, пересечения и дополнения
Ассоциативная бинарная операция-операция j, если она обладает свойством (aφb)φc = аφ(bφc)
Б
Базис - полная система функций алгебры логики, с помощью которой любая функция алгебры логики может быть представлена супер-позицией исходных функций
Бинарное (двуместное) отношение - Множество пар (a,b)R
M1
M2,
обозначение - R(a,b) или aRb элементы а и b находятся в отношении R
Булеан В(Е) - множество всех подмножеств множества Е
Булева алгебра - алгебра (Р2; v, ^, ┐), т.е. алгебра над множеством логических функций с операциями дизъюнкции, конъюнкции и отрицания
Булева функция (логическая функция, функция алгебры логики) -
функция Z = f(X1,X2,...,Хn), где X1,X2,...,Хn, Z -логические переменные, т.е.
переменные, принимающие значения из множества
В = {0,1}
В
Выборка объемa k из n элементов, или (n, k)-выборка - набор (множество или кортеж) элементов (хi1, хi2, ..., xik), составленный из элементов множества X - (х1 x2,...,хn)
Высказывание - некоторое предложение, о котором можно утверждать, что оно истинно или ложно
Высказывание абсолютно истинно - если соответствующая ей логическая величина принимает значение x = 1 при любых условиях
Высказывание абсолютно ложно - если соответствующая ей логическая величина
принимает значение х = 0 при любых условиях
Д
Двойственная функция - для функции Z =f(X1,X2,...,Хn) - функция Z*= ┐f(┐X1,┐X2,...,┐Хn)
Двудольный граф - граф, множество вершин которого разбито на два
непересе-кающихся класса: V = V1 V2, а ребра связывают вершины только из
разных классов
Действительная переменная - переменная хi, при изменении которой изменяется значение функ-ции f(x1, xi,...,xn),
Декартово прямое произведение -
Дерево - связный граф без циклов, т.е. граф, все ребра которого ациклические. В любом конечном дереве число ребер на 1 меньше числа вершин (b - p = 1)
Дизъюнктивная нормальная фоpма (ДНФ) - дизъюнкция нескольких элементарных конъюнкций
Дизъюнктивный терм (макстерм) - терм, связывающий все переменные, представленные в прямой или инверсной форме, знаком дизъюнкции
Дизъюнкция (логическое сложение) - функция f7(x1, x2), которая истинна тогда, когда истинны или x1,или x2,или обе переменные
Замкнутый класс булевых функций - множество функций К , любая
суперпозиция которых принадлежит К, т.е. замыкание К совпадает с К
И
Игра двух лиц с открытой информацией -
игра представляет собой:
- множество ситуаций
Н = {Нi} (среди них - начальная си- туация Н0);
- правила игры, определяющие возможные переходы из
одной ситуации в другую: для
каждой ситуации Hi определено множество Тi ситуаций, в которые
можно перейти ходом одного из игроков;
подмножество
заключительных ситуаций - для них множество Ti пустое; каждой из
этих ситуаций приписан один из символов
А или В, называемых результатом игры (возможен вариант: один
из трех символов А, В, О)
К
Класс L линейных функций - функции вида Xi1i2
...
Xik σ
Класс S самодвойственных функций - т.е. функций таких, что =f(X1,X2,...,Хn)=f*(X1,X2,...,Хn)
Класс М монотонных функций - функции такие, что если Х ≤ Y , то f(X) ≤ f(Y)
Класс Т0 - класс функций, сохраняющих 0, т.е. функций, для которых f(0,0,...,0)=0
Класс Т1 - класс функций, сохраняющих 1, т.е. функций, для которых f(1,1,...,1)=1
Классы эквивалентности бинарного отношения R на множестве М - система подмножеств (разбиение) множества M такая, что 1) любые два элемента из одного класса эквивалентны; 2) любые два элемента из разных классов не эквивалентны
Код Фано - близкий к оптимальному префиксный код для алфавита с заданным распределением частоты букв, который строится диxoтомическим процессом
Кодовое расстояние - для произвольного двоичного кода V={v0,
v1,...,vm-1} величина d(V) =
d(vi ,vj
) , где vi,
vj - кодовые слова
кодирование множества G r-ичное - произвольное отображение множества G в множество слов в алфавите Вr = {0, 1,..., r-1 ),где r > 2 (в частности, при r = 2 -двоичное кодирование)
Коммутативная бинарная операция - операция φ, если она обладает свойством aφb = bφа
Контур (соотв. цикл) - путь (соотв. цепь), у которого начальная вершина совпадает с конечной
Конъюнктивный терм (минтерм) - терм, связывающий переменные, представленные в прямой или инверсной форме, знаком конъюнкции
Конъюнкция (логическое умножение) - функция f1(x1, x2), которая истинна только тогда, когда и x1, и x2 истинны
Критерий полноты системы булевых функций (теорема Поста) - Система полна в том и только в том случае, если для каждого из классов T0,T1,S,L,M в системе существует функция, не принадлежащая этому классу
куб единичный (булев) n-мерный - представление множества наборов - n-мерных булевых векторов точками n-мерного пространства с координатами 0 и 1, соответствующими компонентами векторов, причем ребрами связаны точки, различающиеся ровно в одной компоненте
Линейно упорядоченное множество М - множество, на котором задано отношение порядка, причем любые два элемента множества M сравнимы
Логическая (булева) переменная - такая величина x, которая может принимать только два значения: x = {0,1}.
Логическая функция (функция алгебры логики - ФАЛ) - функция f(x1, x2,...,xn), принимающая значение, равное нулю или единице на
наборе логических переменных x1,x2,...,xn
M
Матрица инцидентности графа с b вершинами и p ребрами - прямоугольная матрица А =|aij| c b строками и p столбцами, строки которой соответствуют вершинам графа, а столбцы - ребрам, причем для неориентированного графа элемент матрицы aij равен 1, если вершина vi и ребро ej инцидентны, и равен 0 в противном случае. Для ориентированного графа аij =-1 , если vi является началом дуги ej, и аij = +1, если vj - конец дуги ej. Петле соответствует элемент, равный 2
Матрица соседства (смежности) вершин графа с b вершинами - квадратная матрица В=|bij|, размерности b, строки и столбцы которой соответствуют вершинам графа; неотрица-тельный элемент bij равен числу ребер, идущих из вершины vi в вершину vj
Минимальная форма представления функции алгебры логики (ФАЛ) - форма представления функции алгебры логики, которая содержит минимальное количество термов и переменных в термах (т. е. ми-нимальная форма не допускает никаких упрощений)
Многочлен Жегалкина - сумма по модулю 2 нескольких различных
конъюнкций переменных и, возможно, константы 1
H
Неориентированный граф (соотв. ориентированный граф, или орграф) -
система G = (V,Е,Г), состоящая из множества элементов V = {v}, называемых вершинами графа,
множества элементов Е = {с}, называемых ребрами, и
отображения Г: Е V2, ставящего в
соответствие каждому элементу е
Е неупо-рядоченную (соотв.
упорядоченную) пару элементов v1,v2
V, называемых концами ребра е
Нормальная дизъюнктивная форма (НДФ) - объединение термов, включающее минтермы переменного ранга
Нормальная конъюнктивная форма (НКФ) - объединение термов, включающее в себя макстермы
разных рангов
O
Оптимальное кодирование - для источника, который в случайном порядке последовательно порождает буквы алфавита А = {а0,
a1,..., am-1} с распределением вероятностей Р = {р0,
p1,..., pm-1}
(Pi > 0,), кодирование с минимальным средним числом
двоичных цифр, приходящихся на одну букву алфавита А при побуквенном кодировании
Остов графа - подграф D, содержащий все вершины графа G и являющийся деревом. Относительно остова D все ребра подграфа G \ D называются хордами
Отношение строгого порядка - бинарное отношение, являющееся антирефлексивным, антисимметричным и транзитивным
Отношение эквивалентности - бинарное отношение, являющееся рефлексивным, симметричные и транзитивным
Ошибки при передаче информации - различия между передаваемым по каналу
связи и принятым на приемнике сообощением: результат преобразования слова при
передаче, являющийся комбинацией замещения, удаления, вставки одного или
нескольких символов и арифметиче-ских ошибок
П
Параллельно-последовательная сеть - сеть, полученная из однореберных сетей в результате конечного числа параллельных и последовательных соединений. Класс параллельно-последовательных сетей (сокращенно П-сетей) определяется индуктивно: (1) однореберная сеть есть П-сеть, (2) если S1 и S2 - П-сети, то S1 ∙ S2 и S1 v V2 -тоже П-сети. Характеристическое свойство П-сетей: они не содержат мостиков
Перестановки из n элементов или n-перестановки - (n, n)-размещения без повторений
Побуквенное кодирование слов (сообщений) - кодирование
(или
)
слов в алфавите А - {аi}, при котором каждому слову
ai1, ai2, ..., aik
ставится в соответствие слово
vi1,vi2, ...,vik
в двоичном алфавите В = {0, 1}, где символы алфавита А кодируются двоичными
словами ( vi есть образ буквы ai)
Полиномиальный коэффициент - коэффициент при произведении xb1 xb2...
xbr в разложении полинома (x1 + x2 +...+ хr)n по
степеням переменных, равный , где
b1 + b2 +...+ br = n.
Частный случай при r = 2 - биномиальные коэффициенты
Полный граф - граф без кратных ребер (и иногда без петель), в котором две любые вершины соединены ориентированным или неори-ентированным ребром. Полный неориентированный граф без петель Кb с b вершинами содержит C2b = b (b - 1) / 2 ребер
(k,l)-полюсник - сеть с (k + l) полюсами, разбитыми на два класса: k входных и l выходных полюсов. (1, 1)-полюсник называется двухполюсной сетью
Поток в cети - пара (f, ω), где ω - некоторая ориентация всех неориентированных ребер сети, a f(e) - заданная на множестве всех ребер функция с неотрицательными значениями, не превосходящая пропускных способностей ребер с(е), и такая, что в каждой внутренней вершине сумма значений потока по ребрам, входящим в вершину, равна сумме значений потока по ребрам, исходящим из вершины
Префиксный код - код V = {vi}, в котором никакое слово vk не
является началом никакого слова vi, j k. Префиксность является достаточным условием
разделимости
Принцип Дирихле (принцип ящиков) - комбинаторное соотношение: если в m ящиках находятся (m + 1) или больше камней, то хотя бы в одном из ящиков больше одного камня
Путь [v0, vn] из вершины v0 в вершину vn -
последовательность вершин и ребер графа G
v0e1 v1e2
... vn-1 envn
если Г(ki) =(vi-1,vi)
для k = 1, 2,..,n. Вершина v0
называется началом, а vn - концом пути; число n называется длиной
пути
P
Разбиение множества U - Система непустых подмножеств {Aa} множества U такая, что их объединение равно U (полнота разбиения), а все попарные пересечения - пусты (чистота разбиения). Сами Aa называются классами, или блоками разбиения
Разложение булевой функции по переменной - представление функции Z =f(X1,X2,...,Хn) в виде ØX1^ f(0,X2,...,Хn)ÚX1 ^ f(1,X2,...,Хn)
(n,k)-размещение с повторениями, или размещение с повторениями из n элементов по k упорядоченная (n, k)-выборка, в которой элементы могут по-вторяться
(n,k)-размещение без повторений, или разме-щение без повторений из n элементов по k - упорядоченная выборка, в которой элементы попарно различны
Ранг терма r - Количество переменных, входящих в данный терм
Расстояние на множестве вершин связного неориентированного графа - для произвольной пары вершин (v1, v2) - минимальное число ребер d(v1,v2) в цепи, связывающей v1 и v2
Расстояние Хемминга - число d(X, Y) несовпадающих компонент для двоичных векторов X и Y
Реализация графа - представление графа в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве или на плоскости, ребрам - отрезки кривых, связы-вающие соответствующие точки, не проходящие через выде-ленные точки, отличные от их концов и попарно не пересекающиеся во внутренних точках
Рефлексивное (соответственно, антирефлексивное) отношение -
Бинарное отношение, обладающее свойством a: aRa (сответственно
a : a┐Ra )
C
Связный граф - граф, имеющий ровно одну компоненту связности, т.е. любые две его вершины связаны цепью
Сечение в сети - множество ребер, блокирующее все цепи из as в bs. При его удалении сеть становится несвязной, причем полюсы as и bs попадают в разные компоненты связности
Симметричное (соответственно, антисимметричное) отношение -
бинарное отношение, обладающее свойством a,b:
aRb
bra (соответственно
a,b: если а
b, то aRb
b┐Ra)
Совершенная дизъюнктивная нормальная форма (СДНФ) -
представление функции
Z=f(X1,X2,...,Хn) в виде
дизъюнкции всех элементарных конъюнкций, соответствующих наборам значений (X1,X2,...,Хn) на которых Z = 1 :
Z = | v | Х1σ1× X2σ2 ×...× Хnσn |
f(σ1,σ2,...,σn)=1 |
Сочетание без повторений (соотв. с повторениями) - неупорядоченная (n, k)-выборка без повторений (соотв. с повторениями), (n, k)-сочетание без повторений - это k-элементное подмножество n-элементного множества
Сравнимые (несравнимые) элементы - a,b сравнимы (соответственно, несравнимы) по отношению порядка R, если выполняется хотя бы одно (соответственно, не выполняется ни одного) из отношений aRb или bra
Степень s(α) вершины α - для графа без петель - число ребер в звезде Zα. Сумма степе-ней всех вершин графа равна удвоенному числу ребер
Стратегия f игрока А - некоторое соответствие f(Hi) = H'i
Ti,
назначающее для ка-ждой ситуации Нi в которой может оказаться игрок А, один определенный ход.
Аналогично определяется стратегия игро-ка В
Сумма по модулю 2 - функция двух переменных, равная 0, если значения аргументов совпадают, и 1 - в противном случае
Суперпозиция функций -
Функция, полученная из системы функций f, f1, f2,...,fk некоторой
подстановкой функций f1, f2,...,fk во
внешнюю функцию f
вместо переменных и переименованиями переменных
T
Табличное представление булевых функций - для функции Z = f(X1,X2,...,Хn) - таблица из 2n строк n - мерных булевых векторов в алфавитном порядке, каждому из которых сопоставлены 0 или 1
Теорема Форда-Фалкерсона о максимальном потоке - максимальная величина потока Rmax через сеть S равна минимальной из пропускных способностей cmin ее простых сечений
Теорема Эйлера о четном графе - для того чтобы в конечном связном графе существовал простой, т.е. не самопересекающийся по ребрам цикл, содержащий все ребра графа (такой цикл называется эйлеровым циклом), необходимо и достаточно, чтобы все вершины графа имели четную степень
Теоремы о выигрышной (соотв. беспроигрышной) стратегии - если игра не допускает ничейного исхода, то для одного из игроков существует выигрышная стратегия; в игре, допускающей ничейный исход, хотя бы один из игро-ков обладает беспроигрышной стратегией
Транзитивное отношение -
бинарное отношение, обладающее свойством a,b,c: (aRb
^ brc)
aRc
Треугольник Паскаля - треугольная числовая таблица, n-я строка которой
состоит из (n + 1) коэффициентов бинома (х + у)n: С0n,
C1n,..., Сnn.
Каждое число строки, кроме крайних, равных единице, равно сумме двух
ближайших чисел, находящихся над ним в предыдущем ряду
Ф
Фиктивная переменная - переменная xi, при изменении которой значение функции f(x1, xi,...,xn), не изменяется
Формулы алгебры логики (пропозициональные формулы) - формулы, построенные из знаков переменных, булевых констант 0,1 и знаков функциональных операций по следующим правилам:
Функционально полная система функций -
система, замыкание которой составляет
Р2 - множество
всех логических функций
X
Характеристическая функция множества МU -
отображение
: U
В = {0,1} , ставящее в соответствие элементам множества М
единицу, а элементам дополнения ┐М -ноль
Ц
Цепь - последовательность вершин и ребер, образующая путь в соотнесенном неориентированном графе
Цикломатическое число графа -
для графа G с p ребрами, b вершинами и k связными
компонентами пространство базисов циклов имеет размерность v(G) = р - b + k; в частности, для
связного графа v = р - b + 1
Ч
Частично упорядоченное множество -
множество, на котором задано отношение порядка,
причем допускаются несравнимые пары элементов
Э
Эквивалентные (равносильные) формулы - формулы, представляющие одну и ту же функцию
Элементарная конъюнкция, соответствующая набору - ~σ =(σ1,σ2,...,σn) - конъюнкция Х1σ1 ^ X2σ2 ^... ^Хnσn где Х1=X, X0=X
A | Б | В | Г | Д | Е | Ж | З | И | К | Л | М | Н | О | П | Р | С | Т | У | Ф | Х | Ц | Ч | Ш | Щ | Ь | Ъ | Ы | Э | Ю | Я |