ДМ проблемы построения минимальных ДНФ
ДНФ –дизъюнкция элементарных конъюнкций, т.е.D=k1Úk2Ú…Úkm, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). Минимальная ДНФ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон.
Тривиальный алгоритм построения минимальной и кратчайшей ДНФ ф-ии f(x1…xn): построить все возможные ДНФ, используя x1…xn и Øx1…Øxn, упорядочить их от простых к сложным, и, начиная с простых, проверять, реализует ли ДНФ ф-ию f.
Число разл-х ДНФ, построенных на n-переменных=
Геометр. интерпретация задачи: имеем единичный n-мерный куб. Bn- мн-во его Вршин. (a1..an). Любой ф-ии f можно поставить в соотв. мн-во NfÌBn– подмн-во вершин куба: Nf={(a1..an): f(a1..an)=1}
Пусть k– произв. элементарная конъ. ранга r. Мн-во NkÌBn наз‑ся интервалом ранга r, если оно соотв. конъ k:
, зн-ия остальных переменных – произвольные.
Пр1.: Þ Nk={(101)}; Пр2.: k=y Þ N={(010)(011)(110)(111)}
Пусть f задана в виде ДНФ: f= k1Úk2Ú…Úkm. Т.о. с каждой ДНФ ф-ии f связано некоторое покрытие мн-ва Nf интервалами
. Справедливо и обратное: каждое покрытие мн‑ва Nf интервалами
определяет некоторую ДНФ, реал-ую данную ф-ию.
Пусть rj – ранг коньюнкции kj.
- число вхождений переменных во всей ДНФ. Построение ДНФ сводится к построению покрытия Nf интервалами
, при котором вел‑на r минимальна. Построение кратчайшей ДНФ сводится к отысканию покрытия с минимальным числом интервалов.
Пр.:
4. ДМ Схемы из функциональных элементов в базисе {И, ИЛИ, НЕ}. Задача построения схем из функциональных элементов и подходы к её решению. Примеры.
E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн‑ия ф-ии f на любом наборе переменных принадлежат E2
Функциональный элемент с n упорядоченными входами и одним выходом:
При подаче на входы любой комбинации двоичных сигналов, на выходе также возникает сигнал. Каждый вход – аргумент функции. Выход – булева функция от аргументов. Из функциональных элементов можно строить по правилам их соединения схемы. Возможные соединения функциональных элементов соответствуют булевым функциям и их суперпозициям. |
Полный набор булевых функций, который используется для построения схем в какой-нибудь задаче, называют базисом из функциональных элементов. Базис называют полным, если с его помощью можно реализовать любую булеву функцию в виде схемы. Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.
Пример полного базиса:
![]() | ![]() | ![]() |
коньюнктор | дизъюнктор | инвертор |
Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно 1. найти минимальную ДНФ; 2. для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.
Пр.: сумматор n-разрядных двоичных чисел. Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида
X = XnXn-1…X1, Y = YnYn-1…Y1, Z = x+y = Zn+1Zn…Z1
X+Y – сумма чисел
Для решения такой задачи вводим qi – единица переноса из одного разряда в другой.
Формулы сумматора
Zi = Xi + Yi + Qi – сумма по модулю 2
Qi+1 = XiYi V XiQi V QiYi
5. ДМ Вычислимые функции. Машина Тьюринга. Тезис Тьюрингаhttp://www.smolensk.ru/user/sgma/MMORPH/N-6-html/EMEL-1/emel-1.htm
Алгоритм - это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) искомого результата.
Машина Тьюринга - абстрактный автомат, состоит из бесконечной ленты, разбитой на ячейки, головки машины (ГМ), которая в любой дискретный момент времени t = 0, 1, 2, ..., T может образовать только одну ячейку, и управляющего головкой устройства (УУ). В каждую ячейку можно записать только один символ, а все различные символы образуют конечный алфавит машины X={ х0…хm}. Символ х0 считается пустым. Головка машины всегда расположена над текущей ячейкой ленты и может выполнять команды читать символ в текущей обозреваемой ячейке, писать символ в текущую обозреваемую ячейку. Все различные состояния машины (или состояния головки машины в каждый момент времени работы автомата, за такт ее работы), образуют некоторое конечное множество внутренних состояний автомата S={s0…sn}. В каждый такт работы МТ, ГМ считывает символ из обозреваемой ячейки, затем изменяет свое текущее состояние на новое (целиком определяемое прочтенным символом и текущим состоянием) и реализует очередную команду УУ в которой указано, какой нужно символ записать и в какую ячейку ГМ нужно переместиться (или же остаться на месте). До начала работы машины, некоторые ячейки ленты нужно заполнить символами из Х и машина выводится из состояния s0.
Можно построить (модель) универсальную машину Тьюринга, способную выполнять работу любой машины Тьюринга, точнее, подражать работе любой другой машины Тьюринга.
Тезис Тьюринга: любой алгоритм можно реализовать с помощью МТ
Функция f(a1, a2, ..., an)ÎX называется вычислимой, если существует такая МТ P, что
1) работа P(a1, a2, ..., an) останавливается тогда и только тогда, когда (a1, a2, ..., an) принадлежит области определения f;
2) если (a1, a2, ..., an) принадлежит области определения f; то в заключительной конфигурации в исходной ячейке находится такое значение b, что f(a1, a2, ..., an) = b.