Термины 2

Question 1

Теорема разложения для ДНФ

Answer 1

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

Question 2

Минимальная ДНФ

Answer 2

ДНФ, которое содержит минимальное количество конъюнкций и дизъюнкций

Question 3

Сокраценная ДНФ

Answer 3

Это ДНФ, полученная после всех склеиваний и поглощений из СДНФ

Question 4

Импликанта

Answer 4

Всякую функцию ϕ будем называть импликантой функции f, если все минтермы функции ϕ входят в множество минтермов функции f.

Question 5

Метод Квайна

Answer 5

метод минимизации булевых функций, основанный на нахождении простых импликант

Question 6

Метод Петрика

Answer 6

метод минимизации ДНФ, основанный на покрытии таблицы истиности

Question 7

Макстерм

Answer 7

это дизъюнкция всех переменных или их отрицаний.

Question 8

Совершенная КНФ

Answer 8

это КНФ, где каждый набор ложности переменных соответствует одному макстерму.

Question 9

Теорема разложения для КНФ

Answer 9

Любую булеву функцию можно представить в виде конъюнкции макстермов, соответствующих строкам таблицы истинности, где функция равна 0.

Question 9

Минимальная КНΦ

Answer 9

это КНФ, содержащая минимально возможное количество макстермов.

Question 9

Сокращенная КНФ

Answer 9

это форма КНФ, где убраны избыточные переменные

Question 9

Понятие функциональной полноты

Answer 9

набор логических операций, из которых можно выразить любую булеву функцию.

Question 9

Самодвойственные функции

Answer 9

это функции, где результат функции от отрицания аргументов равен отрицанию результата функции.

Question 10

Линейные функции

Answer 10

это функции, которые могут быть выражены с помощью операции сложения по модулю 2

Question 11

Монотонные функции

Answer 11

это функции, которые не уменьшают значения при изменении входных переменных с 0 на 1.

Question 12

Функции, сохраняющие единицу

Answer 12

Булева функция сохраняет единицу, если на единичном наборе значений аргументов она принимает единичное значение. Если f(1…1) = 1.

Question 13

Функции, сохраняющие нуль

Answer 13

Булева функция сохраняет нуль, если на нулевом наборе она принимает нулевое значение. Нулевой набор состоит из n нулей, где n – число аргументов булевой функции. Если f(0…0) = 0.

Question 14

Теорема Поста о функциональной полноте

Answer 14

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

Question 15

Синтез комбинационных схем

Answer 15

процесс создания логических схем, реализующих заданную булеву функцию.

Question 16

Одноместный предикат

Answer 16

Одноместным предикатом P(x) называется произвольная функция одной переменной x, значениями которой являются высказывания об объектах, представляющих значения аргумента.

Question 17

Предметная область предиката

Answer 17

Предметная область (область определения) предиката – это множество M, на котором определен предикат

Question 18

Предметные переменные

Answer 18

Предметные переменные – это элементы множества M, на котором определен предикат

Question 19

Область истинности предиката

Answer 19

Областью истинности предиката P(x), заданного на множестве M, называется совокупность всех x из M, при которых данный предикат обращается в истинное высказывание.

Question 20

Алгебра Жегалкина

Answer 20

это представление булевых функций в виде многочленов по модулю 2.

Question 21

Тождественно ложный предикат

Answer 21

предикат, ложный для всех возможных значений переменных.

Question 22

Тождественно истинный предикат

Answer 22

предикат, истинный для всех возможных значений переменных.

Question 23

Выполнимый предикат

Answer 23

предикат, который истиннен хотя бы для одного значения переменных.

Question 24

n-местный предикат

Answer 24

предикат, зависящий от п переменных.

Question 25

Логические операции над предикатами

Answer 25

отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция