Термины 2 Flashcards

24-47

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Импликанта

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Метод Квайна

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Макстерм

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

13
Q

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

A

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

14
Q

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

A

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

15
Q

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

A

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

16
Q

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

A

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

17
Q

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

A

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

18
Q

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

A

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

19
Q

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

A

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

20
Q

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

A

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

21
Тождественно ложный предикат
предикат, ложный для всех возможных значений переменных.
22
Тождественно истинный предикат
предикат, истинный для всех возможных значений переменных.
23
Выполнимый предикат
предикат, который истиннен хотя бы для одного значения переменных.
24
n-местный предикат
предикат, зависящий от п переменных.
25
Логические операции над предикатами
отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция