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

для каждого элемента 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.

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

По варианту задания находим 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

00 1 1

01 1 1 1

x1x2

11 1