Практическая часть.

1. Определить фиктивность аргументов ФАЛ, для которых составлены таблицы истинности

«Аналитическая запись фал» теоретическая часть

Рассмотрим методы перехода от табличного способа задания функции к аналитическому методу (в виде формул).

Дизъюнктивная нормальная форма (ДНФ).

Конъюнкция называется элементарной, если в ней каждая переменная встречается не более одного раз.

Дизъюнкция (сумма) элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Дизъюнктивная совершенная нормальная форма (ДСНФ).

Алгоритм перехода от табличного задания функции к дснф.

1. Выбрать в таблице все наборы аргументов, при которых функция обращается в 1 (множество Т₁).

2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как 1, он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если аргумент входит как 0, то в конъюнкцию вписывается его отрицание.

Множество Т1
	X	Y	Z	F(x,y,z)
	0	0	0	1
	0	0	1	1
	0	1	1	1
	1	0	0	1
	1	0	1	1
	1	1	0	1
	1	1	1	1

Выпишем ДНФ:

F(x, y, z) = 

Конъюнктивная нормальная форма (КНФ).

Дизъюнкция называется элементарной, если в ней каждая переменная встречается не более одного раз.

Конъюнкция (произведение) элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

Конъюнктивная совершенная нормальная форма (КСНФ).

Алгоритм перехода от табличного задания функции к кснф.

1. Выбрать в таблице все наборы аргументов, при которых функция обращается в 0 (множество Т₀).

2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит в данный набор как 0, он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если аргумент входит как 1, то в дизъюнкцию вписывается его отрицание.

Множество Т0
	X	Y	Z	F(x,y,z)
	0	0	0	0

Выпишем КНФ:

F(x, y, z) = ()

Практическая часть.

1. Определить ДНФ, ДСНФ, КНФ и КСНФ ФАЛ, для которых составлены таблицы истинности

«Аналитический метод минимизации фал и графический метод минимизации фал с помощью карт карно » теоретическая часть

Карты Карно – графический метод отображения булевых функций.

Это специальные таблицы, задающие ФАЛ. Они сформированы так, чтобы облегчить процесс склеивания. Карты Карно используются при n – 2, 3, 4, 5, 6, при n > 6 они практически не используются.

Основные принципы построения карт Карно:

В карте Карно две соседние клетки, помеченные символами 1, всегда соответствуют конъюнктивным членам ДНФ, отличающимися только одним сомножителем. Поэтому их можно слить. Причем отличающийся сомножитель при слиянии поглощается.

Процесс слияния и поглощения можно расширять разными способами:

Во-первых, следует учитывать, что противоположные края условны, т.е. клетки на противоположных краях можно объединять так же, как если бы они находились в средней части карты.

Во-вторых, можно сливать не только 2, но и 4, 8 и т.д. соседних клеток. При слиянии 2 клеток поглощается 1 переменная. При слиянии 4 клеток поглощается 2 переменные. При слиянии 8 клеток поглощается 3 переменные.

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

Среди всех маркированных клеток (т.е. клеток, соответствующих наборам переменных, на которых функция имеет значение 1) следует отыскать такие, которые совместно образуют наибольшую область размером 2, 4 или 8 клеток и окружить эту область контуром.

Необходимо выбрать дополнительные блоки маркированных клеток, которые имеют максимальный размер, причем количество таких блоков должно быть минимальным, но каждая маркированная клетка должна войти хотя бы в один блок. При оконтуривании групп разрешается одну и ту же маркированную клетку включать более чем в одну группу.

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

Например.

N = 2 N = 3

(X, Y) (X, Y, Z)

00	01	11	10			00	01	11	10
					0
				Х	1

N = 4

(X₁, X₂, X₃, X₄)

		00	01	11	10
	00
	01
	11
	10

Примеры минимизации:

		00	01	11	10
	0	1	1		1
Х	1				1

		00	01	11	10
	0	1			1
Х	1	1	1	1	1

		00	01	11	10
	00	1	1	1	1
	01	1	1	1	1
	11			1	1
	10			1	1

Пример. Минимизировать с помощью карта Карно функцию:

Для данной функции уже была составлена ДНФ:

F(x, y, z) = 

Построим карту Карно для заданной функции:

		00	01	11	10
	0	1	1	1
Х	1	1	1	1	1

Минимизируем ДНФ с помощью законов алгебры логики:

F(x, y, z) =  =

1 1 1 1

В процессе минимизации использовали:

1. Закон дополнения -

2. Правило вычеркивания - или

При минимизации ДНФ разными способами получили одинаковый результат.

Пример 2. Минимизировать на картах Карно функцию f(x₁, x₂, x₃, x₄), которая равна 1 на наборах с номерами: 0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 15

Построим двоичные наборы, на которых задана функция

№ набора	Наборы				f(x1, x2, x3, x4)
	Х1	Х2	Х3	Х4
0	0	0	0	0	1
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	1
6	0	1	1	0	1
7	0	1	1	1	1
8	1	0	0	0	1
9	1	0	0	1	1
11	1	0	1	1	1
15	1	1	1	1	1

Построим карту Карно для заданной функции:

		00	01	11	10
	00	1	1	1	1
	01	1		1	1
	11			1
	10	1	1	1

Таким образом,