Минимизация сложных высказываний.

Существует несколько способов минимизации сложных высказываний. Рассмотрим самые распространенные:

· метод Квайна;

· карты Вейча;

· минимизирующие карты.

 

Метод Квайна.

 

Алгоритм метода Квайна включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. СДНФ приводится к сокращенной ДНФ (СкДНФ). При получении СкДНФ используются следующие формулы равносильности:

а) Формула склеивания

б) Формула неполного склеивания

в) Формула поглощения

Применяя все возможные процедуры склеивания, СДНФ приводится к СкДНФ.

3. Минимальная форма формулы (МДНФ ) получается на основе импликантной матрицы путем нахождения минимального покрытия этой матрицы. Импликанта – это элементарная конъюнкция СкДНФ. Конституента единицы – это элементарная конъюнкция СДНФ. Импликантная матрица – это матрица импликант и констиуент единиц. (столбцы - конституенты единицы, строки – импликанты). МДНФ может быть несколько.

 

ПРИМЕР.

Необходимо найти МДНФ формулы:

1 2 3 4 5 6

Осуществляем всевозможные склеивания

1-2

1-4

2-3

3-6

4-5

5-6

СкДНФ имеет вид:

Составляем импликантную матрицу

	+	+
	+			+
		+	+
			+			+
				+	+
					+	+

 

По данной импликантной матрице можно выбрать следующие МДНФ

 

Метод минимизирующих карт.

Алгоритм метода минимизирующих карт включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. Составляется таблица всевозможных сочетаний переменных.

3. Из таблицы вычеркиваются те строки, которые не содержат конституенты СДНФ. Конъюнкции этих строк вычеркиваются в других строках.

4. В каждой строке оставляются конъюнкции с минимальным количеством переменных.

5. Из каждой строки выбирается олна конъюнкция и составляется ДНФ.

6. Из построенных ДНФ выбирается минимальная.

 

ПРИМЕР

 

Дана СДНФ

 

							*
							*

* - помечены строки, не содержащие конституенты СДНФ.

После соответствующих преобразований получаем следующую таблицу

 

							*
							*

 

После всевозможного перебора остаются следующие МДНФ:

 

Метод минимизации с помощью карт Вейча.

 

Алгоритм метода карт Вейча включает в себя следующие этапы:

1. Любая формула приводится к СДНФ.

2. Составляется карта Вейча. Карта Вейча – это таблица всех возможных комбинаций значений переменных. В соответствующие ячейки заносятся единицы, соответствующие конституентам СДНФ.

3. Единицы, стоящие по вертикали и горизонтали, объединяются (по 2, по 4. по 8 и т.д.). Объединение единиц соответствует операциям склеивания и поглощения. Иначе говоря, формируются максимальные подкубы.

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

5. Выше полученные конъюнкции составляют МДНФ.

 

Карты Вейча удобны при поиске МДНФ функций двух, трех и четырех переменных.

n=2

СДНФ=

 

1

 

МДНФ=

 

n=3

СДНФ=

 

 

1

 

МДНФ=

n=4

 

СДНФ=

 

	1	1

 

МДНФ=

 

Булевые функции и их свойства.

 

Булевой функцией называется функция n переменных, которая принимает значение 1 или 0, а так же ее аргументы тоже принимают значение 1 или 0.

Булевая функция имеет следующие свойства:

1. Свойство сохранения нуля . Булевая функция сохраняет нуль, если функция при нулевых значениях аргумента принимает значение нуль.

2. Свойство сохранения единицы . Булевая функция сохраняет единицу, если функция при единичных значениях аргумента принимает значение единица.

 

ПРИМЕР

Логическая операция – дизъюнкция обладает и свойством сохранения нуля (), и свойством сохранения единицы ()

 

3. Линейность . Функция является линейной, если её можно представить в виде:

где - булевая переменная

ПРИМЕР

 

Эквивалентность является линейной функцией:

 

4. Монотонность . Функция является монотонной, если для любых произвольных наборов a и b выполняются следующие неравенства:

5. Самодвойственность . Функция называется самодвойственной, если она равна двойственной ей функции.

Двойственной функцией называется функция:

Тогда свойство самодвойственности может представлено:

ПРИМЕР

 

Отрицание является самодвойственной функцией: