ДМ проблемы построения минимальных ДНФ

ДНФ –дизъюнкция элементарных конъюнкций, т.е.D=k₁Úk₂Ú…Úk_m, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). Минимальная ДНФ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон.

Тривиальный алгоритм построения минимальной и кратчайшей ДНФ ф-ии f(x₁…x_n): построить все возможные ДНФ, используя x₁…x_n и Øx₁…Øx_n, упорядочить их от простых к сложным, и, начиная с простых, проверять, реализует ли ДНФ ф-ию f.

Число разл-х ДНФ, построенных на n-переменных=

Геометр. интерпретация задачи: имеем единичный n-мерный куб. Bⁿ- мн-во его Вршин. (a₁..a_n). Любой ф-ии f можно поставить в соотв. мн-во N_fÌB_n– подмн-во вершин куба: Nf={(a₁..a_n): f(a₁..a_n)=1}

Пусть k– произв. элементарная конъ. ранга r. Мн-во N_kÌB_n наз­­‑ся интервалом ранга r, если оно соотв. конъ k:
, зн-ия остальных переменных – произвольные.

Пр1.: Þ N_k={(101)}; Пр2.: k=y Þ N={(010)(011)(110)(111)}

Пусть f задана в виде ДНФ: f= k₁Úk₂Ú…Úk_m. Т.о. с каждой ДНФ ф-ии f связано некоторое покрытие мн-ва N_f интервалами . Справедливо и обратное: каждое покрытие мн‑ва N_{f интервалами} определяет некоторую ДНФ, реал-ую данную ф-ию.

Пусть r_j – ранг коньюнкции k_j. - число вхождений переменных во всей ДНФ. Построение ДНФ сводится к построению покрытия N_f интервалами , при котором вел‑на r минимальна. Построение кратчайшей ДНФ сводится к отысканию покрытия с минимальным числом интервалов.

Пр.:

 

4. ДМ Схемы из функциональных элементов в базисе {И, ИЛИ, НЕ}. Задача построения схем из функциональных элементов и подходы к её решению. Примеры.

E²={0,1}; f(x₁,…,x_n)- ф-ия алгебра логики, если переменные x₁,…, x_n определены на E² и зн‑ия ф-ии f на любом наборе переменных принадлежат E²

Функциональный элемент с n упорядоченными входами и одним выходом:

При подаче на входы любой комбинации двоичных сигналов, на выходе также возникает сигнал. Каждый вход – аргумент функции. Выход – булева функция от аргументов. Из функциональных элементов можно строить по правилам их соединения схемы. Возможные соединения функциональных элементов соответствуют булевым функциям и их суперпозициям.

Полный набор булевых функций, который используется для построения схем в какой-нибудь задаче, называют базисом из функциональных элементов. Базис называют полным, если с его помощью можно реализовать любую булеву функцию в виде схемы. Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.

Пример полного базиса:

 

коньюнктор

дизъюнктор

инвертор

Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно 1. найти минимальную ДНФ; 2. для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.

Пр.: сумматор n-разрядных двоичных чисел. Составить элементы с 2n входами и n+1 выходом, реализующих сложение n-разрядных двоичных чисел вида

X = X_nX_n-1…X₁, Y = Y_nY_n-1…Y₁, Z = x+y = Z_n+1Z_n…Z₁
X+Y – сумма чисел

Для решения такой задачи вводим qi – единица переноса из одного разряда в другой.

Формулы сумматора
Z_i = X_i + Y_i + Q_i – сумма по модулю 2
Q_i+1 = X_iY_i V X_iQ_i V Q_iY_i

5. ДМ Вычислимые функции. Машина Тьюринга. Тезис Тьюринга http://www.smolensk.ru/user/sgma/MMORPH/N-6-html/EMEL-1/emel-1.htm

Алгоритм - это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) искомого результата.

Машина Тьюринга - абстрактный автомат, состоит из бесконечной ленты, разбитой на ячейки, головки машины (ГМ), которая в любой дискретный момент времени t = 0, 1, 2,..., T может образовать только одну ячейку, и управляющего головкой устройства (УУ). В каждую ячейку можно записать только один символ, а все различные символы образуют конечный алфавит машины X={ х_0…х_m}. Символ х₀ считается пустым. Головка машины всегда расположена над текущей ячейкой ленты и может выполнять команды читать символ в текущей обозреваемой ячейке, писать символ в текущую обозреваемую ячейку. Все различные состояния машины (или состояния головки машины в каждый момент времени работы автомата, за такт ее работы), образуют некоторое конечное множество внутренних состояний автомата S={s₀…s_n}. В каждый такт работы МТ, ГМ считывает символ из обозреваемой ячейки, затем изменяет свое текущее состояние на новое (целиком определяемое прочтенным символом и текущим состоянием) и реализует очередную команду УУ в которой указано, какой нужно символ записать и в какую ячейку ГМ нужно переместиться (или же остаться на месте). До начала работы машины, некоторые ячейки ленты нужно заполнить символами из Х и машина выводится из состояния s₀.

Можно построить (модель) универсальную машину Тьюринга, способную выполнять работу любой машины Тьюринга, точнее, подражать работе любой другой машины Тьюринга.

Тезис Тьюринга: любой алгоритм можно реализовать с помощью МТ

Функция f(a₁, a₂,..., a_n)ÎX называется вычислимой, если существует такая МТ P, что
1) работа P(a₁, a₂,..., a_n) останавливается тогда и только тогда, когда (a₁, a₂,..., a_n) принадлежит области определения f;

2) если (a₁, a₂,..., a_n) принадлежит области определения f; то в заключительной конфигурации в исходной ячейке находится такое значение b, что f(a₁, a₂,..., a_n) = b.