Основы алгебры логики (часть 3)
Минимизация булевых функций. Основные понятия и определения. Геометрический метод. Метод Квайна. Метод Квайна ‑ Мак-Класки. Метод Блейка – Порецкого. Метод диаграмм Вейча. Метод карт Карно. Метод неопределенных коэффициентов. Минимизация конъюнктивных нормальных форм. Метод Петрика. Минимизация частично определенных булевых функций. Минимизация систем булевых функций.
Задачу упрощения булевых функций обычно формулируют в классе …
а) ДНФ
б) КНФ
в) БНФ
Имеется ДНФ булевой функции f(x1,x2, …,xn):
f(x1,x2, …,xn) =K1
K2
…
Ks,
где Ki (i = 1, 2, …,s) – элементарная конъюнкция. Числоsэлементарных конъюнкций называют …
а) длиной ДНФ
б) рангом ДНФ
в) термом ДНФ
ДНФ булевой функции f(x1,x2, …,xn) называют … , если она содержит наименьшее числоsэлементарных конъюнкций по сравнению с другими ДНФ этой же функции.
а) кратчайшей
б) сокращенной
в) тупиковой
г) минимальной
В элементарной конъюнкции
K =x1σ1x2σ2 ··· xσr
число rпеременных в конъюнкцииK называют ее …
а) длиной
б) рангом
в) термом
ДНФ, представленную в виде
f(x1,x2, …,xn) =K1
K2
…
Ks,
можно охарактеризовать также числом
R = r1+r2+…+rs,
которое называют …
а) суммарной длиной
б) суммарным рангом
в) суммарным термом
ДНФ булевой функции f(x1,x2, …,xn) называют … , если ей соответствует наименьший суммарный рангRпо сравнению с другими ДНФ этой же функции.
а) кратчайшей
б) сокращенной
в) тупиковой
г) минимальной
Соотношения
,
называют …
а) законами неполного склеивания
б) законами полного склеивания
в) законами поглощения
г) законами де Моргана
Соотношения
,
называют …
а) законами неполного склеивания
б) законами полного склеивания
в) законами поглощения
г) законами де Моргана
Соотношения
,
,
,
называют …
а) законами неполного склеивания
б) законами полного склеивания
в) законами поглощения
г) законами де Моргана
Законы неполного склеивания, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций, заданы соотношениями …
а)
б)
в)
г)
Законы полного склеивания, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций, заданы соотношениями …
а)
б)
в)
г)
Законы поглощения, используемые при минимизации элементарных конъюнкций или элементарных дизъюнкций, заданы соотношениями …
а)
,
б)
,
в)
,
г)
д)
е)
Булева функция g(x1,x2, …,xn) называется импликантой функцииf(x1,x2, …,xn), если …
а) функция g(x1,x2, …,xn) = 0 на тех же наборах, на которыхf(x1,x2, …,xn) = 0
б) для любого набора, на котором g(x1,x2, …,xn) = 1, справедливоf(x1, x2, …, xn) = 1
в) функция g(x1,x2, …,xn) содержит наименьшее число элементарных конъюнкций, чем функцияf(x1,x2, …,xn)
Если функция f(x1,x2, …,xn) и функцииgi(x1,x2, …,xn) заданы таблицей истинности:
|
x3x2x1 |
f |
g1 |
g2 |
g3 |
g4 |
g5 |
g6 |
g7 |
|
000 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
001 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
010 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
011 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
100 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
101 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
110 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
111 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
то импликантами функции f(x1,x2, …,xn) являются …
а) g1(x1,x2, …,xn)
б) g2(x1,x2, …,xn)
в) g3(x1,x2, …,xn)
г) g4(x1,x2, …,xn)
д) g5(x1,x2, …,xn)
е) g6(x1,x2, …,xn)
ж) g7(x1,x2, …,xn)
Имеется элементарная конъюнкция
K =x1σ1x2σ2 ··· xσr .
Конъюнкцию, полученную из K удалением некоторых переменных, называют …
а) собственной частью
б) термом
в) импликантой
г) простой импликантой
Собственными частями конъюнкции
являются конъюнкции …
а)
,
б)
,
в)
,
г)
д)
е)
Элементарная конъюнкция
K =x1σ1x2σ2 ··· xσr
называется … булевой функции f(x1,x2, …,xn), еслиK является импликантой функцииf(x1,x2, …,xn) и никакая собственная частьK не является импликантойf(x1,x2, …,xn).
а) конституентой
б) простой импликантой
в) простым термом
Дизъюнкция всех простых импликант функции f(x1,x2, …,xn) называется … этой функции.
а) сокращенной ДНФ
б) кратчайшей ДНФ
в) совершенной ДНФ
г) тупиковой ДНФ
Дизъюнкция совокупности простых импликант функции f(x1,x2, …,xn) такая, что удаление из нее любой импликанты приводит к отсутствию покрытия дизъюнкций оставшихся импликант всех единиц функции, называют … функцииf(x1,x2, …,xn).
а) сокращенной ДНФ
б) кратчайшей ДНФ
в) совершенной ДНФ
г) тупиковой ДНФ
Любая минимальная ДНФ булевой функции f(x1,x2, …,xn) является …
а) сокращенной ДНФ
б) кратчайшей ДНФ
в) совершенной ДНФ
г) тупиковой ДНФ
Общая схема минимизации булевых функций включает следующие этапы:
а) построение сокращенной ДНФ
б) нахождение тупиковой ДНФ
в) построение совершенной ДНФ
г) нахождение минимальной ДНФ
д) построение совершенной КНФ
Все методы построения сокращенной ДНФ основаны на выполнении правил …
а) склеивания
б) поглощения
в) дизъюнкции
г) конъюнкции
д) отрицания
В геометрическом методе минимизации для булевой функции f(x1,x2,x3) конституенте единицы соответствует …
а) вершина единичного куба
б) ребро единичного куба
в) грань единичного куба
В методе Квайна – Мак-Класки минимизации булевой функции f(x1,x2,x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) разбиение на группы имеет вид …
а)
|
0000 |
1-я группа |
|
1000 |
2-я группа |
|
0110 1100 |
3-я группа |
|
0111 1101 1110 |
4-я группа |
|
1111 |
5-я группа |
б)
|
0000 |
1-я группа |
|
0001 |
2-я группа |
|
0101 1100 |
3-я группа |
|
0111 1101 1011 |
4-я группа |
|
1111 |
5-я группа |
в)
|
0000 |
1-я группа |
|
0010 1000 |
2-я группа |
|
0110 1100 |
3-я группа |
|
0111 1101 1011 |
4-я группа |
В методе Квайна – Мак-Класки минимизации булевой функции f(x1,x2,x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) в результате склеивания соседних конституент получают таблицу …
а)
|
0000* |
х000 |
1-я группа |
|
1000* |
1х00 |
2-я группа |
|
0110* 1100* |
011х х110 11х0 110х |
3-я группа |
|
0111* 1101* 1110* |
х111 11х1 111х |
4-я группа |
|
1111* |
| |
б)
|
0000* |
000х |
1-я группа |
|
0001* |
0х01 |
2-я группа |
|
0101* 1100* |
х101 110х |
3-я группа |
|
0111* 1101* 1011* |
х111 11х1 1х11 |
4-я группа |
|
1111* |
| |
в)
|
0000* |
00х0 х000 |
1-я группа |
|
0010* 1000* |
0х10 1х00 |
2-я группа |
|
0110* 1100* |
011х 110х |
3-я группа |
|
0111* 1101* 1011 |
| |
В методе Квайна – Мак-Класки минимизации булевой функции f(x1,x2,x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) в результате склеивания соседних конституент получают таблицу …
|
х000 |
| |
|
1х00 |
| |
|
011х* х110* 11х0* 110х* |
х11х 11хх |
1-я группа |
|
х111* 11х1* 111х* |
| |
которой соответствует сокращенная ДНФ …
а)
б)
в)
В методе минимизации Квайна и Квайна – Мак-Класки для получения минимальной ДНФ строится импликантная матрица. Для булевой функции f(x1,x2,x3, x4) = (0, 6, 7, 8, 12, 13, 14, 15) после этапа построения сокращенной ДНФ импликантная матрица имеет вид:
|
Простые импликанты |
Конституенты единицы | |||||||
|
0000 |
1000 |
0110 |
1100 |
0111 |
1101 |
1110 |
1111 | |
|
|
х |
|
|
|
|
|
|
|
|
|
|
х |
|
х |
|
|
|
|
|
|
|
|
х |
|
х |
|
х |
х |
|
|
|
|
|
х |
|
х |
х |
х |
В этом случае минимальная ДНФ …
а)
б)
в)
Метод Блейка-Порецкого позволяет строить сокращенную ДНФ булевой функции f(x1,x2, …,xn), если она задана …
а) произвольной ДНФ
б) совершенной ДНФ
в) совершенной КНФ
г) совершенной БНФ
Задана импликантная матрица булевой функции f(x1,x2,x3, x4) по методу Петрика.
|
yi |
Простые импликанты |
Конституенты единицы | |||||
|
0001 |
0011 |
0101 |
0111 |
1110 |
1111 | ||
|
y1 |
|
х |
х |
х |
х |
|
|
|
y2 |
|
|
|
|
х |
|
х |
|
y3 |
|
|
|
|
|
х |
х |
Определенная по этому методу минимальная ДНФ …
а)
б)
в)
Для нахождения по методу Петрика минимальной ДНФ булевой функции f(x1,x2,x3, x4), представленной импликантной матрицей, каждой простой импликанте поставлена в соответствие булева переменнаяyi. Конъюнкции элементарных дизъюнкций, построенные по правилам метода Петрика, имеют вид
и определяют …
а) 5 тупиковых ДНФ
б) 7 тупиковых ДНФ
в) 4 тупиковых ДНФ
Если сокращенная ДНФ булевой функции f(x1,x2, …,xn) не содержит отрицаний переменных, то …
а) она является единственной минимальной формой этой функции
б) импликантную матрицу не строят
в) минимальную ДНФ определяют методом Петрика
Сокращенная ДНФ монотонной булевой функции f(x1,x2, …,xn) …
а) не содержит отрицаний переменных
б) является единственной минимальной формой этой функции
в) не требует построения импликантной матрицы
г) требует применения метода Петрика для определения минимальной ДНФ
Диаграмма Вейча для функции двух переменных имеет вид …
а)
|
|
0 |
1 |
y |
|
0 |
|
|
|
|
1 |
|
|
|
|
x |
|
|
|
б)
|
|
0 |
1 |
y |
|
0 |
|
|
|
|
1 |
|
|
|
|
x |
|
|
|
в)
|
|
0 |
1 |
y |
|
0 |
|
|
|
|
1 |
|
|
|
|
x |
|
|
|
Сокращенная ДНФ булевой функции, представленной на карте Карно
|
|
00 |
01 |
11 |
10 |
x3x4 |
|
00 |
1 |
1 |
|
1 |
|
|
01 |
|
1 |
1 |
|
|
|
11 |
|
1 |
1 |
|
|
|
10 |
1 |
1 |
|
1 |
|
|
x1x2 |
|
|
|
|
|
имеет вид …
а)
б)
в)
Алгоритм поиска минимальной ДНФ частично определенной булевой функции f(x1,x2, …,xn) включает следующие действия …
а) найти сокращенную ДНФ функции доопределением единицами f(x1,x2, …,xn) на всех неопределенных наборах
б) найти сокращенную ДНФ функции доопределением нулями f(x1,x2, …,xn) на всех неопределенных наборах
в) выбрать минимальную ДНФ по импликантной матрице с полностью определенными единичными наборами
в) выбрать минимальную ДНФ по импликантной матрице с учетом полностью определенных и доопределенных единичных наборов
Сокращенная ДНФ частично определенной булевой функции, представленной на карте Карно
|
|
0 |
1 |
x2 |
|
0 |
- |
1 |
|
|
1 |
1 |
0 |
|
|
x1 |
|
|
|
имеет вид …
а)
б)
в)
