Термины 2 Flashcards
24-47
Теорема разложения для ДНФ
Любую булеву функцию можно представить в виде дизъюнкции минтермов, соответствующих строкам таблицы истинности, где функция равна 1.
Минимальная ДНФ
ДНФ, которое содержит минимальное количество конъюнкций и дизъюнкций
Сокраценная ДНФ
Это ДНФ, полученная после всех склеиваний и поглощений из СДНФ
Импликанта
Всякую функцию ϕ будем называть импликантой функции f, если все минтермы функции ϕ входят в множество минтермов функции f.
Метод Квайна
метод минимизации булевых функций, основанный на нахождении простых импликант
Метод Петрика
метод минимизации ДНФ, основанный на покрытии таблицы истиности
Макстерм
это дизъюнкция всех переменных или их отрицаний.
Совершенная КНФ
это КНФ, где каждый набор ложности переменных соответствует одному макстерму.
Теорема разложения для КНФ
Любую булеву функцию можно представить в виде конъюнкции макстермов, соответствующих строкам таблицы истинности, где функция равна 0.
Минимальная КНΦ
это КНФ, содержащая минимально возможное количество макстермов.
Сокращенная КНФ
это форма КНФ, где убраны избыточные переменные
Понятие функциональной полноты
набор логических операций, из которых можно выразить любую булеву функцию.
Самодвойственные функции
это функции, где результат функции от отрицания аргументов равен отрицанию результата функции.
Линейные функции
это функции, которые могут быть выражены с помощью операции сложения по модулю 2
Монотонные функции
это функции, которые не уменьшают значения при изменении входных переменных с 0 на 1.
Функции, сохраняющие единицу
Булева функция сохраняет единицу, если на единичном наборе значений аргументов она принимает единичное значение. Если f(1…1) = 1.
Функции, сохраняющие нуль
Булева функция сохраняет нуль, если на нулевом наборе она принимает нулевое значение. Нулевой набор состоит из n нулей, где n – число аргументов булевой функции. Если f(0…0) = 0.
Теорема Поста о функциональной полноте
Система булевых функций называется функционально полной, если она содержит хотя бы одну нелинейную функцию, хотя бы одну немонотонную, хотя бы одну не самодвойственную, хотя бы одну, не сохраняющую единицу, и хотя бы одну, не сохраняющую нуль.
Синтез комбинационных схем
процесс создания логических схем, реализующих заданную булеву функцию.
Одноместный предикат
Одноместным предикатом P(x) называется произвольная функция одной переменной x, значениями которой являются высказывания об объектах, представляющих значения аргумента.
Предметная область предиката
Предметная область (область определения) предиката – это множество M, на котором определен предикат
Предметные переменные
Предметные переменные – это элементы множества M, на котором определен предикат
Область истинности предиката
Областью истинности предиката P(x), заданного на множестве M, называется совокупность всех x из M, при которых данный предикат обращается в истинное высказывание.
Алгебра Жегалкина
это представление булевых функций в виде многочленов по модулю 2.
Тождественно ложный предикат
предикат, ложный для всех возможных значений переменных.
Тождественно истинный предикат
предикат, истинный для всех возможных значений переменных.
Выполнимый предикат
предикат, который истиннен хотя бы для одного значения переменных.
n-местный предикат
предикат, зависящий от п переменных.
Логические операции над предикатами
отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция
