![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Из способа построения карты с симметричным расположением аргументов ясно, что каждая клетка функции с аргументами имеет
соседних клеток, т.е. тех клеток, с которыми можно производить склеивание.
![]() ![]() | ![]() | ![]() ![]() | ![]() | |||||
![]() |
| * |
x5
x4 x4
x3 x3
![]() |
| ![]() | ![]() | ||||||||||||||
x2 ![]() | ![]() ![]() |
![]() ![]() | ![]() | ![]() | ![]() | ![]() |
![]() ![]() | ||||||||||
![]() ![]() | * | ![]() | ![]() | ![]() | ![]()
![]() | ||||||||||||
![]() | ![]() |
![]() | |||||||||||||||
x1 | x1 |
Клетки, расположенные симметрично относительно осей, являются соседними, т.е. их можно склеить. Правило симметрии не распространяется на другие методы.
В карте проставляются только значения функции, равные 1, нули не записывают. Можно склеивать , где
, клеток, т.е. полные строки, полные столбцы, проходящие через карту, полукарту, четверть карты и т.д.
При склеивании клеток выпадает
переменных, т.е. останется
переменных.
Нетрудно заметить, что простые импликанты соответствуют максимальным областям карты, т.е. таким, которые нельзя увеличить. Рассмотрим примеры.
![]() | ![]() | ![]() | ![]() | |||||||||
![]() | ![]() | ![]() | ![]() | ![]() ![]() | ![]() | |||||||
11 | 12 | ![]() | 12 | |||||||||
![]() | 13 | 14 | ![]() | 13 | 14 | |||||||
![]() | ![]() | 15 | ![]() | ![]() | 15 | ![]() | ||||||
![]() | 17 | ![]() | ![]() | 18 | ||||||||
![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ||||||||||
![]() | ![]() | ![]() | ![]() | ![]() ![]() | ![]() | |||||||
![]() | ![]() | 12 | 13 | ![]() | ![]() | ![]() | ||||||
![]() | 15 | 13 | 14 | |||||||||
![]() | ![]() | 16 | ![]() | ![]() | ![]() | |||||||
![]() | 17 | 18 | 19 | ![]() | 15 | 16 | ||||||
![]() | ![]() |
![]() | ![]() | ![]() | ![]() | |||||||||
![]() | ![]() | ![]() ![]() | ![]() | ![]() | ![]() ![]() | ![]() | ||||||
![]() | 11 | 12 | 13 | 14 | 11 | 12 | 13 | |||||
![]() | 16 | 17 | ![]() | ![]() | 14 | |||||||
![]() | ![]() | 18 | ![]() | 110 | ![]() | 15 | ![]() | |||||
![]() | 111 | 112 | ![]() | 16 | 17 | 18 | ||||||
![]() | ![]() |
Обратите внимание, что в последней карте нет смысла объединять клетки 1, 3, 6, 8, ибо оставшиеся клетки приходится объединять с ними же.
x 5 x 5
![]() | ![]() | ![]() | x 4 | ||||||||||||||||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||||||||||||
![]() ![]() | ![]() | ![]() | ![]() | ![]() | |||||||||||||||
![]() | ![]() | ![]() | |||||||||||||||||
![]() | ![]() | ![]() ![]() | ![]() | ![]() | |||||||||||||||
![]() | ![]() | ||||||||||||||||||
![]() | ![]() |
x 5 x 5
![]() | x 4 | ![]() | x 4 | ||||||||||||||||
![]() | ![]() | x 3 | ![]() | ![]() | ![]() | x 3 | |||||||||||||
![]() ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | |||||||||||||
![]() | ![]() | ||||||||||||||||||
![]() | ![]() | ||||||||||||||||||
![]() | ![]() |
x 5 x 5
![]() | x 4 | ![]() ![]() | ![]() | ![]() | ![]() | x 4 | |||||||||||||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() ![]() | ![]() | ![]() | ![]() | |||||||||
![]() | ![]() | ![]() | |||||||||||||||||
![]() | ![]() | ||||||||||||||||||
![]() ![]() | ![]() | ![]() | |||||||||||||||||
![]() | ![]() ![]() | ![]() | ![]() | ||||||||||||||||
![]() | ![]() ![]() |
x 5 x 5
![]() | x 4 | ![]() | x 4 | |||||||||||||||||
![]() | ![]() | x 3 | ![]() ![]() | ![]() | ![]() | ![]() | ![]() | |||||||||||||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() ![]() | ![]() | |||||||||||||
![]() | ![]() | |||||||||||||||||||
![]() | ||||||||||||||||||||
![]() | ![]() | |||||||||||||||||||
![]() | ![]() | ![]() | ![]() |
7 абсолютно минимальные представления
Задача о нахождении такого аналитического представления ФАЛ, при котором число букв в представлении минимально в классе ДНФ, может быть решена с использованием скобочного представления ФАЛ.
Определение 7-1. Q представляет собой минимальное представление для функции f, если не существует в базисе {-, &, } представления более минимального, чем Q, каким бы способом ни получилось это выражение.
Дальнейшая минимизация МДНФ за счет вынесения за скобки является практически наиболее подходящим приемом получения абсолютно минимального представления ФАЛ в классе ДНФ.
Пример 1-7. Для функции
найдена МДНФ вида: .
Если вынести за скобки x 1, то получим абсолютно минимальное представление: .
Замечание 1-4. Отметим, что МДНФ зачастую не дает абсолютно минимального представления. В ряде случаев МКНФ оказывается “меньше” МДНФ. Поэтому для получения абсолютно минимальных представлений ФАЛ необходимо из них выбрать наименьшее.
Методы получения МКНФ двойственны методам получения МДНФ.
ГЛАВА 2.ПРЕОБРАЗОВАНИЯ И МИНИМИЗАЦИЯ В БАЗИСЕ СОСТОЯЩЕМ ИЗ ФУНКЦИИ ВЕББА ИЛИ ИЗ ФУНКЦИИ ШЕФФЕРА. [†]
Проблема минимизации ФАЛ может быть сформирована и для случая любого другого базиса. Функции Вебба (Пирса) и Шеффера образуют базисы, состоящие только из одной функции. Будем называть такие базисы монофункциональными.
В последнее время возник большой интерес к моно-функциональным базисам. Поэтому рассмотрим их более подробно. Оба базиса обладают одинаковыми свойствами, поэтому рассмотрим задачу минимизации ФАЛ лишь для одного из них – базиса из функции Вебба. Для упрощения записи в дальнейшем будем использовать знак (стрелка Пирса) взамен знака для обозначения функции Вебба (о).
Все сказанное о базисе Вебба практически без всяких изменений может быть использовано и для базиса, состоящего из функции Шеффера.
По аналогии с двуместными, введем с помощью таблицы n -местные функции Вебба и Шеффера:
x 1 | x 2 | x3 | . | . | . | xn -1 | Xn | Wn | Sn |
. | . | . | |||||||
. | . | . | |||||||
. | . | . | |||||||
- | - | - | - | - | - | - | - | - | - |
- | - | - | - | - | - | - | - | - | - |
. | . | . | |||||||
. | . | . | |||||||
. | . | . |
При n =2 из этой таблицы получаются двухместные функции Вебба и Шеффера, а при n =1 обе функции вырождаются в функцию отрицания. Поэтому в дальнейшем будем вместо и x / x писать соответственно
.
Для введенных функций справедлив переместительный закон и несправедлив сочетательный закон.
Справедливы следующие соотношения:
|
При раскрытии скобок получим:
|
Заметим, что если l или m равны единице, то эти соотношения выразятся несколько иначе. Например, при l =1:
(2-3)
Наконец, приведем соотношения, показывающие связь между многоместными функциями Вебба и Шеффера и являющиеся аналогами формул де Моргана:
(2-4).
Справедливость всех вышеприведенных соотношений можно установить при помощи таблиц истинности ФАЛ.
В дальнейшем в основном будем рассматривать базис, построенный на основе многоместной функции Вебба.
Известно [11], что любую ФАЛ можно представить:
,
если выбрать -характеристические функции единицы для множества Т 0 номеров наборов, на которых функция f обращается в нуль:
Применяя последнее из соотношений (2-1), получаем одну из двух совершенных нормальных форм в базисе Вебба:
(2-5)
Если использовать характеристические функции единицы для множества T 1 номеров наборов, на которых функция f обращается в единицу, то получится другая совершенная нормальная форма. Она проще предыдущей, если у функции в таблице истинности нулей больше, чем единиц:
(2-6)
Для получения аналогичных нормальных форм в базисе Шеффера можно использовать характеристические функции нуля.
Перейдем теперь к аналитическому выражению характеристических функций единицы в базисе Вебба. Для любой характеристической функции единицы в базисе {-, &, } может быть получено выражение через конституенту единицы:
Если применить последнее из соотношений (2-1), то
(2-7)
и мы можем написать, что
и получить выражение для характеристической функции единицы:
(2-8)
при условии, что
.
Теперь мы можем сформулировать алгоритм перехода от табличного задания функции к ее записи в виде совершенной нормальной формы вбазисе n -местной функции Вебба вида, например, (2-5):
1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.
2. Выписать термы типа (2-8), соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как нуль, он вписывается без изменения. Если же
входит в данный набор как единица, то вписывается его отрицание.
3. Все полученные выражения характеристических функций объединяются k -местной операцией Вебба, где k – количество нулей заданной функции.
Пример 2-1. Построить совершенную нормальную форму вида (2-5) для следующей таблично заданной функции:
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
в соответствии с алгоритмом получаем:
Дата публикования: 2015-02-22; Прочитано: 378 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!