Изучение функций в курсе математики (стр. 2 из 4)
Задание 5. Заданы номера наборов аргументов, на которых булева функция принимает значение, равное единице. Необходимо:
· Записать булеву функцию в СДНФ и СКНФ;
· Минимизировать функцию с помощью минимизационной карты;
· Построить алгоритм Куайна.
· Выяснить к каким функционально-замкнутым классам принадлежит булева функция;
·
f (x1,x2,x3,x4)=1010010010110011
Решение
1. Запишем СДНФ и СКНФ булевой функции.
СДНФ(1):№ 0,2,5,8,10,11,14,15
f =
1 2 
3 
4 
1 
2 
3 
4 
1 
2 3 4 
1 
2 3 
4 
1 2 
3 4 1 2 3 4 
1 2 3 4 
1 2 3 4
СКНФ(0):№ 1,3,4,6,7,9,12,13
f = (
1 
2 3 
4) ( 
1 2 3 4) ( 1 
2 
3 4) ( 1 
2 
3 4) ( 
1 2 3 4) ( 1 2 3 
4) ( 1 
2 3 
4) ( 1 2 
3 
4)2. Строим минимизационную карту и пошагово выполняем алгоритм.
Шаг1.
| № | x1 | x2 | x3 | x4 | x1x2 | x1x3 | x1x4 | x2x3 | x2x4 | x3x4 | x1x2x3 | x1x2x4 | x1x3x4 | x2x3x4 | x1x2x3x4 | f |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 0 | 2 | 2 | 2 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 3 | 3 | 3 | 0 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 2 | 2 | 0 | 2 | 2 | 0 | 4 | 4 | 0 |
| 5 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 5 | 5 | 1 |
| 6 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 3 | 2 | 2 | 3 | 2 | 2 | 6 | 6 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 0 |
| 8 | 1 | 0 | 0 | 0 | 2 | 2 | 2 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 8 | 1 |
| 9 | 1 | 0 | 0 | 1 | 2 | 2 | 3 | 0 | 1 | 1 | 4 | 5 | 5 | 1 | 9 | 0 |
| 10 | 1 | 0 | 1 | 0 | 2 | 3 | 2 | 1 | 0 | 2 | 5 | 4 | 6 | 2 | 10 | 1 |
| 11 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 1 | 1 | 3 | 5 | 5 | 7 | 3 | 11 | 1 |
| 12 | 1 | 1 | 0 | 0 | 3 | 2 | 2 | 2 | 2 | 0 | 6 | 6 | 4 | 4 | 12 | 0 |
| 13 | 1 | 1 | 0 | 1 | 3 | 2 | 3 | 2 | 3 | 1 | 6 | 7 | 5 | 5 | 13 | 0 |
| 14 | 1 | 1 | 1 | 0 | 3 | 3 | 2 | 3 | 2 | 2 | 7 | 6 | 6 | 6 | 14 | 1 |
| 15 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 15 | 1 |
Шаг 2. Вычеркиваем строки, в которых функция обращается в нуль.
Шаг 3. В каждом столбце из сохранившихся чисел вычеркиваем те, равные которым уже вычеркнуты в этом столбце на предыдущем шаге.
Шаг 4. В сохранившихся строках выбираем «значения» наименьших по числу множителей конъюнкций (включая и конъюнкции с одним множителем – переменные) и обводим их.
Шаг 5. Если в одном столбце обведено несколько одинаковых чисел, то вычеркиваем все, кроме одного.
Результирующая таблица имеет вид:
| № | x1 | x2 | x3 | x4 | x1x2 | x1x3 | x1x4 | x2x3 | x2x4 | x3x4 | x1x2x3 | x1x2x4 | x1x3x4 | x2x3x4 | x1x2x3x4 | f |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 2 | 1 | 0 | 2 | 2 | 2 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 3 | 1 | 1 | 3 | 3 | 3 | 0 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 2 | 2 | 0 | 2 | 2 | 0 | 4 | 4 | 0 |
| 5 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 5 | 5 | 1 |
| 6 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 3 | 2 | 2 | 3 | 2 | 2 | 6 | 6 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 0 |
| 8 | 1 | 0 | 0 | 0 | 2 | 2 | 2 | 0 | 0 | 0 | 4 | 4 | 4 | 0 | 8 | 1 |
| 9 | 1 | 0 | 0 | 1 | 2 | 2 | 3 | 0 | 1 | 1 | 4 | 5 | 5 | 1 | 9 | 0 |
| 10 | 1 | 0 | 1 | 0 | 2 | 3 | 2 | 1 | 0 | 2 | 5 | 4 | 6 | 2 | 10 | 1 |
| 11 | 1 | 0 | 1 | 1 | 2 | 3 | 3 | 1 | 1 | 3 | 5 | 5 | 7 | 3 | 11 | 1 |
| 12 | 1 | 1 | 0 | 0 | 3 | 2 | 2 | 2 | 2 | 0 | 6 | 6 | 4 | 4 | 12 | 0 |
| 13 | 1 | 1 | 0 | 1 | 3 | 2 | 3 | 2 | 3 | 1 | 6 | 7 | 5 | 5 | 13 | 0 |
| 14 | 1 | 1 | 1 | 0 | 3 | 3 | 2 | 3 | 2 | 2 | 7 | 6 | 6 | 6 | 14 | 1 |
| 15 | 1 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 7 | 7 | 7 | 7 | 15 | 1 |
Шаг 6. Сокращенная ДНФ имеет вид