Функции от переменных 
со значениями из {0,1} обозначим 
.
Их всего 
Определение. В 
, 
называется существенной, если 
И фиктивной, если 
Операции над ф. а.л. – Добавление и удаление фиктивных переменных
Определение. Ф. а.л. называются равными, если они переводятся одна в другую добавлением или отбрасыванием фиктивных переменных.
Определение. Формула над F. (индуктивное определение)
- формула над F. (базис) Если каждый из объектов 
либо формула над F, либо переменная, то 
- формула над F. Определение. Две формулы называются эквивалентными, если они реализуют равные функции.
Значение формулы.
; 
на 1-м наборе 
Теорема.
Пусть 
-ф. а.л. Тогда 
(V берем по всевозможным 
)
Доказательство:
Берем
Два случая:
а) 
б) 
Частные случаи:
k=1 – разложение по переменной
k=n – совершенная д. н.ф. 
Следствие. Любую ф. а.л. можно представить в виде с. д.н. ф.
Билет 24. Схемы из функциональных элементов и простейшие алгоритмы их синтеза. Оценка сложности схем, получаемых по методу Шеннона.
Б = {
,
,
} - стандартный базис.
Определение. Ориентированный граф без контуров называется СФЭ в базисе Б, если каждая вершина нулевой степени захода (не входят дуги) помечена символом переменной, а любая другая (1 или 2 входа) символами &, V, 
. Схема реализует функцию, образующуюся на выходе.
Проблема синтеза СФЭ: по данной функции f построить схему 
, ее реализующую.
Алгоритмы синтеза.
1) По совершенной ДНФ.
Реализуем 
2) По реализации множества всех конъюнкций
Пусть 
- множество всех 
S – количество V в с. д. н.ф. 
3) Разложение по 1-ой переменной
Определение. Универсальный мн-к – СФЭ с n входами и s выходами и 
- выход (
выходов).
Утверждение. 
Доказательство (по индукции):
1) 
: 
2) Индукция: 
=
1)
2) 
их 
3) 
их 
4) 
их 
Теорема Шеннона.
Существует метод синтеза 
.
(
построена по методу 2)
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
