дискретка. Булева функция функция от булевых переменных, принимающая одно из двух возможных значений
 Скачать 16.58 Kb.
|
|
Булева функция - функция от булевых переменных, принимающая одно из двух возможных значений. Тупиковая ДНФ булевой функции - равносильная ей дизъюнкция простых импликант, ни одну из которых нельзя отбросить. Система булевых функций называется полной, если любую булеву функцию можно выразить через них, т.е. любая булева функция представима суперпозицей функций данного семейства Перестановка - выборка, где важен порядок. Полиномиальный коэффициент - Cn = n!/(r1! * r2! * ... * rk!) Используется для подсчёта перестановок и числа разбиений множества. Псевдограф - граф, в котором допускаются петли. Произведение графов - бинарная операция на графах. V = p1 * p2; X = p1 * q2 + p2 * q1; Центроид графа - вершина, которая имеет наименьший вес, т.е. P(v) = min P(w), w(- V Гамильтонов граф - граф, содержащий гамилтонов цикл, который в свою очередь представляет собой замкнутый гамильтонов путь, т.е. простой путь, проходящий через каждую вершину графа ровно 1 раз. Хроматическое число графа - минимальное число цветов x(G), достаточных для вершинной раскраски графа. Конъюнкти́вная норма́льная фо́рма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Дизъюнкти́вная норма́льная фо́рма (ДНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Штрих Шеффера - x|y или же HE(x&y) Совершенная КНФ - КНФ, удовлетворяющая следующим условиям: 1). в ней нет одинаковых элементарных дизъюнкций 2). в каждой дизъюнкции нет одинаковых пропозициональных переменных 3). каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв. Булева функция называется монотонной, если с возрастанием набора значений переменных(по неравенству Парето), значения функции не убывает. Примеры: x&y. Не монотонная функция: x|y Правило суммы: 1). если объект А можно выбрать n способами, а объект B другими m способами, то объект AvB можно выбрать n + m способами. 2). число элементов объединения пересекающихся конечных множеств А и В равно сумме числа элементов этих множест. Остов графа - подграф данного графа, содержащий все его вершины и являющийся деревом. Матрица инцидентности графа - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа. Столбцы матрицы соответствуют ребрам, строки - вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром. Граф связный, если он содержит ровно одну компоненту свзяности, т.е. между любой парой вершин этого графа существует как минимум один путь. Неориентированное дерево - конечный связный граф с выделенной вершиной(корнем) без циклов. Эйлеров цикл - эйлеров путь, являющийся циклом, т.е. замкнутый путь. Эйлеров путь - путь, проходящий по всем рёбрам графа ровно 1 раз. Граф планарный, если его можно изобразить на плоскости без пересечения его рёбер. |