01 2 01 (775933)
Текст из файла
-
Методы минимизации нормальных дизъюнктивных и конъюнктивных форм
Очень часто, если не в большинстве случаев, работа конкретного устройства описывается с помощью неполностью определенной функции, так как некоторые комбинации входных сигналов не подаются или являются запрещенными.
Определение. Неполностью определенной функцией является такая переключательная функция, значения которой на некоторых наборах аргументов могут быть произвольными (т.е. равными "0" или "1").
Определение. Пусть функция f(x1,x2,...xn) не определена на "р" наборах аргументов. Тогда полностью определенную функцию 
(x1,x2,...xn) будем считать эквивалентной к f(x1,x2,...xn), если ее значения на тех наборах, на которых f(x1,x2,...xn) определена, совпадают.
Очевидно, существует 2р различных функций, эквивалентных f(x1,x2,...xn).
Задача минимизации f(x1,x2,...xn) состоит в выборе такой эквивалентной (x1,x2,...xn), которая имеет простейшую форму.
Введем две вспомогательные эквивалентные функции 0(x1,x2,...xn), 1(x1,x2,...xn), которые принимают на запрещенных наборах аргументов значения 0 и 1 соответственно.
ТЕОРЕМА. МДНФ неполностью определенной f(x1,x2,...xn) совпадает с дизъюнкцией самых коротких импликант 1(x1,x2,...xn), которые совместно накрывают все конституенты единицы 0(x1,x2,...xn), и ни одна из которых не является лишней.
Пример:
Пусть задана f(x1,x2,...xn) в виде следующей таблицы:
| f(x1,x2,...xn) | 1 | - | - | - | 0 | 1 | 0 | 0 | 1 | 0 | - | 0 | 1 | - | - | 1 |
| Числовые эквиваленты наборов | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Тогда
0(x1x2x3x4) = 0 
5 8 12 15 = x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 = 0000 0101 1000 1100 1111,
а
1(x1x2x3x4) = 0 1 2 3 5 8 10 12 13 14 15 = 0000 0001 0010 0011 0101 1000 1010 1100 1101 1110 1111
Найдем простые импликанты 1(x1x2x3x4)
| Конституенты единицы | Отметки о склейке | Импликанты | Отметки о склейке | Импликанты |
| 0000 | * | 000- 00-0 -000 | * | 00- - 00- - -0-0 |
| 0001 0010 1000 | * | * | ||
| * | * | |||
| * | 00-1 0-01 001- -010 1-00 | * | ||
| 0011 0101 1010 1100 | * | - | ||
| * | * | 1- -0 | ||
| * | * | |||
| * | * | |||
| 1101 1110 | * | -101 1-10 110- 11-0 | - | |
| * | ||||
| * | - | 11- - | ||
| - | ||||
| 1111 | * | 111- | * |
Простые импликанты 1(x1x2x3x4)
1(x1x2x3x4) = 0-01 -101 110- 11-0 00- - -0-0 1- -0 11- -
Построим импликантную матрицу.
| Конституенты единицы | 0000 | 0101 | 1000 | 1100 | 1111 |
| Простые импликанты | |||||
| 0-01 | + | ||||
| -101 | + | ||||
| 110- | + | ||||
| 11-0 | + | ||||
| 00-- | + | ||||
| -0-0 | + | + | |||
| 1--0 | + | + | |||
| 11-- | + | + |
Выполним оптимальное покрытие конституент единицы 0 простыми импликантами 1 и получаем минимальную форму функции f(x1x2 x3 x4)
f1min(x1x2 x3 x4) = 11- - -0-0 -101 = x1x2 x2x4 x2x3x4
f2min(x1x2 x3 x4) = 11- - -0-0 0-01 = x1x2 x2x4 x1x3x4
Минимизация с помощью диаграмм Вейча неполностью определенных функций в наглядной и удобной форме позволяет отыскать минимальные формы.
Пример:
Рассмотрим функцию f(x1x2 x3 x4) и найдем ее минимальную форму. Заполнить диаграмму Вейча по следующим правилам: в клетки диаграммы поставим единицы, которые соответствуют конституентам единицы, нули – для отсутствующих конституент и символ неопределенности – "*" (звездочка) – в остальные.
Видно, что в клетки для конституент: x1x2x3x4, x1x2x3x4, x1x2x3x4 целесообразно "поставить" единицы вместо символов неопределенности, так как в этом случае образуется правильная конфигурация 2-го ранга, которая покрывается произведением x2x3.
Аналогично и в клетку x1x2x3x4 нужно "поставить" единицу.
Итак, fmin(x1x2 x3 x4) = x2x3 x1x4 x3x4 x1x2.
Замечание. Все, что было сказано относительно минимизации функции, представленной в СДНФ или ДНФ справедливо для функции, заданной в СКНФ или КНФ.
В этом случае необходимо отыскивать правильные конфигурации, образованные нулями.
Синтез переключательных функций в одноэлементном базисе
Операция (стрелка) Пирса
f8(x1,x2)
| x1 | 0 | 0 | 1 | 1 |
| x2 | 0 | 1 | 0 | 1 |
| f8 | 1 | 0 | 0 | 0 |
Эту функцию можем представить, записав по "единицам":
f8(x1,x2) = x1x2 = x1
x2
или
x1 x2 = x1x2
На основе принципа суперпозиции:
f(x1,x2,...xn) = x1 x2 x3 . . . xn = x1x2x3 . . .xn
Применяя правило де Моргана:
x1 x2 x3 . . . xn = x1x2x3 . . .xn = x1 x2 x3 . . . xn
или:
x1 x2 x3 . . . xn = x1 x2 x3 . . . xn
т.е.
x1 x2 x3 . . . xn = x1 x2 x3 . . . xn
Рассмотрим некоторые соотношения для операции Пирса:
x x = xx = x
x1 x2 = x1x2 = x2x1 = x2 x1
x1 x2 x3 = (x1x2) x3 = x1x2x3 
x1 (x2x3),
т.е. операция Пирса не обладает свойством ассоциативности
x1 x2 x3 = (x1 x2) x3 = x1 (x2 x3)
x1 x2 x3 x4 = (x1 x2) (x3 x4)
При этом порядок выполнения операций в формулах, где есть операции Пирса такой:
-
раскрываются скобки
-
выполняются операции инверсии
-
выполняются операции Пирса
Синтез логических функций в базисе Пирса удобно производить, имея запись функции в КНФ.
Допустим, что ФАЛ задана в конъюктивной форме
f = Q1Q2Q3 . . . Qn
Подставим член Qi в виде:
Qi = (xr xp xq . . . xw xf xe . . . xz)
Возьмем двойное отрицание от обеих частей этого равенства, применив правило де Моргана
Qi = (xr xp xq . . . xw xf xe . . . xz) = (xr * xp * xq * . . . xw * xf * xe * . . . * xz)
Применяя соотношение, полученное на основе принципа суперпозиции:
Qi = (xr xp xq . . . xw xf xe . . . xz)
Или, применяя это преобразование к исходной форме, получим:
f = Q1 Q2 Q3 . . . Qn
Итак: чтобы от КНФ перейти к базису Пирса и инверсии необходимо:
-
заменить операции дизъюнкции операциями Пирса
-
заменить операции конъюнкции операциями Пирса
-
заключить в скобки все те группы букв, которые соответсвуют конъюнктивным членам.
Пример:
f(x1x2 x3) = (x1 x2 x3) (x1 x4) (x2 x4) = (x1 x2 x3) (x1 x4) (x2 x4)
Замечание. Так как в этих произведениях число букв не увеличивается, и если исходная форма функции была минимальной, то вновь полученная также будет минимальной (в действительности дело обстоит сложнее, поскольку мы рассматриваем не базис " ", а другой, то есть " " и "-" - операцию Пирса и инверсию).
Принципиально можно избавиться от отрицаний, применив соотношение: xi = xi xi, но тогда нельзя будет утверждать, что полученная форма будет минимальной!
Операция штрих Шеффера
| x1 | 0 | 0 | 1 | 1 |
| x2 | 0 | 1 | 0 | 1 |
| f14 | 1 | 1 | 1 | 0 |
Заметим, что эта функция дуальна по отношению к f8, поэтому все свойства являются по существу дуально вытекающими из рассмотренных.
f14 (x1,x2) = x1 x2 (запись функций по нулям)
x1 | x2 = x1 x2 = x1 x2 = x1x2 = x1 x2
на основе принципа суперпозиции:
x1 | x2 | . . . | xn = x1x2...xn
Рассмотрим некоторые эквивалентности:
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
