Быстрый поиск

Реферат: Синтез комбинацонных схем и конечных автоматов, сети Петри

сделать следующее:

а) представить F1 и F2 в виде СДНФ.

б) минимизировать (по количеству переменных в ДНФ) F1 с

помощью карт Карно, F2 – методом Квайна-МакКласки.

в) реализовать в виде комбинационной схемы на логических элементах F1 – в базисе И – НЕ, F2 – в базисе ИЛИ – НЕ, предварительно приведя F1 и F2 к соответствующим базисам.

gi и zi вычислять по выражениям:

(1.1.3)

(1.1.4)

при g0 = A, z0 = B . Параметр изменять от 1 до тех пор, пока не будет получено 9 различных значений gi и zi.

1.2 Теоретические сведения.

Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами:

а) Для A, B, C S

1) , (замкнутость);

2) (коммутативные законы);

3) (ассоциативные законы);

4) (дистрибутивные законы);

5) (свойства идемпотентности);

6) в том и только том случае, если

(свойство совместимости);

7) S содержит элементы 1 и 0 такие, что для всякого элемента

;

8) для каждого элемента A класс S содержит элемент Ã (дополнение элемента A, часто обозначаемое символами Ā или 1- A ) такой, что

, .

В каждой булевой алгебре

(законы поглощения),

(законы склеивания),

(двойственность, законы де Моргана).

Если даны n булевых переменных X1, X2,…, Xn, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение

(1.2.1)

В каждой булевой алгебре существует ровно различных булевых функций n переменных.

Система булевых функций называется полной (базисом), если любая функция может быть представлена в виде суперпозиции функций выбраной системы.

Под критерим минимизации (упрощения) булевых функций будем понимать достижение минимума букв в записи функции.

Введём понятие многомерного куба.

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции y=ƒ(x1,x2,…,xn) есть объединение Ks(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через x.

1.3 Расчёты и полученные результаты.

По варианту задания находим gi и zi:

i	gi	zi
0	5	0
1	1	6
2	8	2
3	5	9
4	13	6
5	11	14
6	4	12
7	3	5
8	13	4
9	13	14
10	8	14
11	9	9
12	5	10
13	7	6

Неповторяющиеся значения gi: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения zi: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F1 получаем выражение

, (1.3.1)

для F2:

. (1.3.2)

Для минимизации первой функции применяем метод карт Карно.

Карта Карно – прямоугольник с 2n клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений).

Проставляя единицы в соответствующих клетках, выбираем затем минимальную из всех возможных комбинацию покрытий. Применим карту Карно к заданной функции:

x3x4

00 01 11 10