Наверх

Словарь

 


A Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я

 

A

Алгебра (M;Ω) - множество М вместе с заданной на нем системой операций Ω = (φ1, φ2,...,φn) . Ω  называется сигнатурой алгебры, а M носителем

Алгебра множеств (алгебра Кантора) на множестве Е - алгебра {В(Е); , , ┐), т.е алгебра на булеане В(Е) с операциями объединения, пересечения и дополнения

Ассоциативная бинарная операция-операция j, если она обладает свойством (aφb)φc = аφ(bφc)

Б

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

Бинарное (двуместное) отношение - Множество пар (a,b)RM1M2, обозначение - 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), где аА, bВ;
  2. для n множеств А1, А2,...,Аn: произведение А1 А2...Аn - множество всех векторов (а1, а2,...,аn), где аiА1,  (т.е а1А1, а2А2,...,аnAn);  Аn - n-я степень множества А:  (АА...А - n-раз)  

Дерево - связный граф без циклов, т.е. граф, все ребра которого ациклические. В любом конечном дереве число ребер на 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,v2V, называемых концами ребра е

Нормальная дизъюнктивная форма (НДФ) - объединение термов, включающее минтермы переменного ранга

Нормальная конъюнктивная форма (НКФ) - объединение термов, включающее в себя макстермы разных рангов

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
f12,...,σ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 и знаков функциональных операций по следующим правилам:

  1. 0, 1 - формулы;
  2. X,Y,Z и т.д. - формулы;
  3. если F и G - формулы, то - ┐F и (F ° G) - формулы, где ° - знак некоторой бинарной функциональной операции; F и G  называются подформулами

Функционально полная система функций - система, замыкание которой составляет Р2 - множество всех логических функций

X

Характеристическая функция множества МU - отображение : UВ = {0,1} , ставящее в соответствие элементам множества М единицу, а элементам дополнения ┐М -ноль

Ц

Цепь - последовательность вершин и ребер, образующая путь в соотнесенном неориентированном графе

Цикломатическое число графа - для графа G с p ребрами, b вершинами и k связными компонентами пространство базисов циклов имеет размерность v(G) = р - b + k; в частности, для связного графа v = р - b + 1

Ч

Частично упорядоченное множество - множество, на котором задано отношение порядка, причем допускаются несравнимые пары элементов

Э

Эквивалентные (равносильные) формулы - формулы, представляющие одну и ту же функцию

Элементарная конъюнкция, соответствующая набору - ~σ =(σ12,...,σn) - конъюнкция Х1σ1 ^ X2σ2 ^... ^Хnσn где Х1=X, X0=X

 


A Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я