Способы задания булевых функций

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:06, 9 января 2015.

Аналитический метод

К аналитическому методу относится помтроение ДНФ, КНФ и АНФ.

ДНФ

Какую схему можно построить по ДНФ?

Пример

Функция от 3х переменных:

Схема в общем виде для ДНФ:

Bf-1.PNG


В худшем случае:


В лучшем случае:

(если не нужен инвертор)

При реализации б.ф. от 3х переменных: 7 - "1", 1 - "0" 3 инвертора, 7 конъюнкторов, 1 дизъюнктор.

КНФ

Если используется КНФ 1 И, множество дизъюнкций.

По быстродействию:

В худшем случае 7 "0", 1 "1" 7 ИЛИ, 1 И

В лучшем случае

Схемы идентичны с точки зрения быстродействия.

При построении ДНФ - основной элемент "1", КНФ - "0" получим полиномиальную схему.

Карты Карно

Существуют для любого количества переменных.

Последовательности должны отличаться на одну единицу.

Способ построения последовательностей

Karno 1.png
000
001
011
010
110
111
101
100

Отличие ровно на 1 бит (отличие в старшем бите; склеили ???)

Карта Карно от 5ти переменных

Karno 2.png
\ 00 01 11 10
000
001 x x
011 x x
010 x x
110 x x
111 x x
101 x x
100

x: отличия в значении x_0 (011, 111) - т.е. отличия в 1м разряде покрытие.

Правила проверки симметричности покрытий (в многомерных Картах Карно): фигура симметрична относительно всех осей симметрии (необходимое условие)ю

АНФ (Полином Жегалкина)

Bf-4.PNG

В худшем случае:

В лучшем случае:

XOR: 1 элемент (8ми входовый)

AND: 4 элемента - 3 элемента AND (2х входовый), 1 элемент 3AND (3х входовый) количество элементов в худшем случае (в случае ДНФ) - 11 штук.


Минусы :
  1. В предыдущей схеме использовались однотипные элементы, а здесь - 2х входовые, 3х входовые и т.д. (особенности реализации)

Самый простой вариант - синтез с помощью этих схем (2 базиса: И, ИЛИ, НЕ; , И).

Если надо синтезировать Штрих Шеффера и Стрелку Пирса:

схема модифицируется в базисе И-НЕ (т.е.присутствует только эти однотипные элементы; их количество не изменяется). ИЛИ-НЕ - не ее основе раскрываем КНФ.

И-НЕ присутствует в худшем случае в базисе И-НЕ:

Для минимизации схем необходимо рассматривать все эти случаи. Если функциональный базис не полный, то б.ф., возможно, можно реализовать.

Либо можно перебирать различные схемные решения для того, чтобы найти оптимальное решение.