- •Аннотация
- •Задание к курсовой работе
- •Содержание Задание 1.Определить мднф логической функции устройства.
- •Составить таблицу соответствия (истинности) функции.
- •Перевести логическую функцию от табличной к аналитической форме в виде дснф
- •1.1 Составить таблицу соответствия (истинности) функции. Составим таблицу истинности для заданной функции f(x1,x2,x3,x4).
- •1.2 Перевести логическую функцию от табличной к аналитической форме в виде дснф.
- •1.3 Найти мднф различными методами.
- •1.3.1 Метод эквивалентных преобразований.
- •1.3.2 Метод Квайна
- •Метод Квайна-Маккласки
- •Метод карт Карно.
- •1.3.5 Метод неопределенных коэффициентов
- •1.3.6 Методом Блейка – Порецкого
- •2.1 Схема алгоритма для метода Квайна
- •2.2 Схема алгоритма для метода Петрика
- •4. Синтез схемы для дснф и мднф в базиса Буля.
- •5. Синтез схемы в базисе Буля, Пирса и Шеффера
1.3.6 Методом Блейка – Порецкого
Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:
Ax v B/x = Ax v B/x v AB,
справедливость которой легко доказать. Действительно,
Ax = Ax v ABx; B/x = B/x v AB/x.
Следовательно,
Ах v В/х = Ах v АВх v В/х v АВ/х = Ах V В/х V АВ.
В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f
Булева функция f задана произвольной ДНФ.
f = /x1/x2 v x1/x2/x3 v x1x2.
Найти методом Блейка - Порецкого сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент заданной ДНФ допускают обобщенное склеивание по переменной х1. В результате склеивания имеем:
/x1/x2 v x1/x2/x3 = /x1/x2 v x1/x2/x3 v /x2/x3.
Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х1, так и по х2. После склеивания по x1 имеем:
/x1/x2 v x1x2 = /x1/x2 v x1x2 v /x2x2 = /x1/x2 v x1x2.
После склеивания по x2 имеем:
/x1/x2 v x1x2 = /x1/x2 v x1x2 v /x1x1 = /x1/x2 v x1x2.
Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х2. После склеивания получаем:
x1/x2/x3 v x1x2 = x1/x2/x3 v x1x2 v x1x3.
Выполнив последнее обобщенное склеивание, приходим к ДНФ:
f = /x1/x2 v x1/x2/x3 v /x2/x3 v x1x2 v x1/x3.
После выполнения поглощений получаем:
f = /x1/x2 v /x2/x3 v x1x2 v x1/x3.
Попытки дальнейшего применения операции обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции f. Далее задача поиска минимальной ДНФ решается с помощью импликантной матрицы точно так же, как в методе Квайна."
Задание 2.
2.1 Схема алгоритма для метода Квайна
-
Начало.
-
Ввести матрицу ДСНФ исходной функции.
-
Проверить на склеиваемость i-ю (i=1,m-1: где m – количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.
-
Формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.
-
Перейти к пункту 2.
-
Строку, которая не склеилась ни с одной другой строкой записать в конечный массив.
-
Перейти к пункту 2.
-
Вывод полученной матрицы.
-
Конец.
Логическая схема алгоритма в нотации Ляпунова
1 1
VHV1Z1V2V3V4VK
VH – начало.
V1 – ввести матрицу ДСНФ исходной функции.
V2 – формировать массив простых импликант, предварительно пометив символом ‘*’ ту переменную, по которой данные строки склеиваются.
V3 – строку, которая не склеилась ни с одной другой строкой записать в конечный массив.
V4 – вывод полученной матрицы.
Z1 – если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.
VK – конец.
Граф-схема алгоритма.
V1
V2
V3
V4
0
Описание машинных процедур
Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);
Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве . Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на ‘*’. Все полученные результаты заносятся в массив REZ.
Все остальные функции и процедуры программы связаны с действиями над массивами, то есть не имеют непосредственного отношения к данному методу нахождения МДНФ. Поэтому нет смысла их описывать.