1. Установите, какие из данных формул являются ДНФ, СДНФ, КНФ, СКНФ формул с переменными X, Y, Z.
а) ; б) ; в) ; г) ; д) ; е) .
2. Приведите следующие формулы к СДНФ с помощью равносильных преобразований:
а) ; б) ; в) ; г) ; д) .
3. Приведите следующие формулы к СКНФ с помощью равносильных преобразований:
а) ; б) ; в) ; г) ; д) .
4. Установите, какие из данных формул являются тавтологиями, приведя их к КНФ:
а) ; б) ; в) ; г) .
5. С помощью эквивалентных преобразований приведите формулу к ДНФ, СДНФ, КНФ, СКНФ. Результаты проверить с помощью таблиц истинности.
1) .
2)
3) .
4)
5) .
6) .
6. Для данной ФАЛ f(x1, x2, x3) найти её СДНФ, ДНФ, СКНФ, КНФ,
принимающей значение 1 на наборах:
1) 0,4,5. 2) 0,4,6,7.
Сделать проверку с помощью таблиц истинности.
7. Для данной ФАЛ f(x1, x2, x3, x4) найти её СДНФ, ДНФ, СКНФ, КНФ,
принимающей значение 1 на наборах:
1) 3,8,9,10,12,13,15.
2) 0,5,8,9,10,12,13,15.
3) 0,8,10,11,13,15.
4) 1,2,3,12,13,14,15.
5) 2,3,7,8,10,11,12,15.
6) 0,4,6,7,8,10,13,15.
7) 0,4,5,7,8,10,11,13,15.
8) 0,4,5,6,7,14,15.
9) 2,4,7,9,10,14,15.
10) 0,3,7,8,9,10,11,12,15.
11) 0,2,3,5,11,12,15.
12) 0,2,4,7,8,10,13,15.
13) 0,3,6,8,9,12,13,15.
14) 2,4,7,9,1011,13,15.
Сделать проверку с помощью таблиц истинности.
Тема 4. Минимизация булевых функций в классе ДНФ. Метод минимизирующих карт
Известно, что упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные логические законы. Существуют и другие способы минимизации ФАЛ.
Один из способов графического представления булевых функций от небольшого числа переменных – карты Карно. Их разновидность – карты Вейча, которые строят как развёртки кубов на плоскости. При этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба. Карты заполняются так же, как и таблица истинности: значение 1 указывается в клетке, соответствующей набору на котором функция имеет значение 1. Значение 0 обычно на картах не отражается.
Диаграммы минимизации позволяют избавиться от неточностей и существенно облегчить процесс упрощения структурных формул.
Диаграмма минимизации для формулы с n- переменными содержит 2n клеток, каждая из которых предназначена для одной из простых конъюнкций.
Соседними считаются клетки, имеющие общую сторону, а также соответствующие клетки правого и левого столбцов, верхней и нижней строк.
Конъюнкции в соседних клетках должны отличатся лишь появлением или исчезновением знака инверсии над одной из переменных, а соответствующие им наборы переменных – одной цифрой.
Входные переменные разносятся по строкам и столбцам, повторяясь столько раз, сколько существует различных сочетаний их двоичных значений.
При использовании диаграмм нет необходимости выписывать по таблице истинности достаточно громоздкую СДНФ структурной формулы. Достаточно занести в клетки единицы, соответствующие наборам переменных, при которых функция имеет значение 1. Если занесённые единицы образуют прямоугольник из 2n (2, 4, 8, 16, …) клеток, то логическая сумма соответствующих им простых конъюнкций может быть автоматически заменена укороченной конъюнкцией, содержащей лишь те переменные, значения которых одинаковы для всех клеток данного прямоугольника. Прямоугольники с единицами обводятся контурами, которые могут соединять любые соседние клетки с единицами и перекрываться.
Искомая минимизированная формула – сумма укороченных конъюнкций контуров, охватывающих все без исключения единицы.
Пример 4.1. Функцию, заданную в СДНФ, минимизировать с помощью карты Карно:
.
Решение. Составим таблицу истинности:
№
А
В
f
В\А
Составим карту Карно:
Найдём укороченные конъюнкции контуров, охватывающих все без исключения единицы:
