Алгебры логики

3.3.1. Минимизация ФАЛ с помощью матрицы Карно

Матрица Карно представляет собой своеобразную таблицу истинности ФАЛ, которая разбита на клетки. Количество клеток матрицы равно 2 n , где n – число аргументов ФАЛ. Столбцы и строки матрицы обозначаются наборами аргументов. Каждая клетка матрицы соответствует конституэнте единицы ФАЛ (двоичному числу). Двоичное число клетки состоит из набора аргументов строки и столбца. Матрица Карно для ФАЛ, зависящей от двух аргументов, представлена в виде таблицы 3.3., от трех аргументов таблицей 3.4. и от четырех аргументов таблицей 3.5.

Таблица 3.3.

Таблица 3.5.

х 3 х 4 х 1 х 2
	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

Клетки матриц (таблицы 3.3., 3.4. и 3.5.) пронумерованы десятичными эквивалентами двоичных чисел клеток. Рядом расположенные клетки матриц, как по горизонтали, так и по вертикали, содержат соседние двоичные числа. Кроме этого соседние двоичные числа находятся во всех столбцах верхней и нижней строк, так же как во всех строках крайних столбцов.

Процесс минимизации ФАЛ с помощью матрицы Карно основан на законе склеивания соседних двоичных чисел. Можно склеивать двоичные числа рядом расположенных клеток, но рекомендуется склеивать наборы аргументов, которыми обозначены строки и столбцы матриц. Рассмотрим склеивание двоичных чисел клеток первого столбца матрицы (табл. 3.5.).

Клетки 0 и 4, соответственно двоичные числа 0000 и 0100, результат склеивания 0-00.

Клетки 8 и 12, двоичные числа 1000 и 1100, результат 1-00. Полученные импликанты склеиваются между собой, т.к. тире стоит в одном и том же разряде и двоичные числа импликант являются соседними, окончательный результат - - 00.

Клетки 8 и 12

Таким образом, если склеиваются все двоичные числа одного столбца, то пропадают те разряды, которыми обозначены строки. Аналогично, если будут склеиваться все двоичные числа одной строки, например 4, 5, 7, 6, то пропадают все разряды, которыми обозначены столбцы, т.е. результат будет следующий 01- -.

Если будут склеиваться двоичные числа только двух любых клеток, то прочерк ставиться вместо того разряда двоичных чисел строки или столбца, который изменится при переходе клеток из одной строчки в другую (или из одного столбца в другой). Например, склеиваются числа клеток 5 и 13, получим результат -101, или клеток 7 и 6 результат 011-.

При склеивании двоичных чисел восьми рядом расположенных клеток пропадает три переменные, например для клеток 3, 7, 15, 11, 2, 6, 14, 10 пропадают переменные х 1 , х 2 , х 3 . Переменные х 1 , х 2 пропадают потому, что склеиваются все клетки столбцов, а х 3 потому, что последние два столбца склеиваются между собой.

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

Известно, что для каждой ФАЛ имеет место количество наборов аргументов 2 n , где n – число аргументов от которых зависит функция или логическое выражение.

Наборы аргументов делятся на три вида

1. Наборы аргументов, на которых функция равна единице, называются рабочими.

2. Наборы аргументов, на которых функция равна нулю, называются запрещенными.

3. Наборы аргументов, на которых функция может быть равна или единице, или нулю, называются безразличными.

Если заданная ФАЛ не имеет безразличных наборов, то она может быть представлена в буквенном выражении в виде СДНФ. При наличии в заданной ФАЛ безразличных наборов, ее представление может иметь следующую форму.

где – десятичные эквиваленты рабочих наборов,

– десятичные эквиваленты запрещенных наборов.

Наборы аргументов, которых нет среди рабочих и запрещенных, будут безразличными.

Пример 3.3. Минимизировать заданную ФАЛ в виде СДНФ с помощью матрицы Карно .

Следовательно, функция задана только рабочими наборами. Остальные будут запрещенными. Функция зависит только от трех аргументов. Строим матрицу Карно и в ее клетках, которые соответствуют рабочим наборам ставим единицы, а в остальных клетках ставим нули.

Таблица 3.5.

х 2 х 3 х 1
	0

Для минимизации клетки матрицы, в которых стоят единицы, объединяются в контуры. В контур могут включаться две клетки, четыре или все восемь. В данном примере в контур включены четыре рядом расположенные клетки одной строки. Импликантой заданного контура будет 1 - -. Результат минимизации следующий , т.е. произошло сокращение заданной функции в СДНФ на 11 букв.

Пример 3.4. Минимизировать логическое выражение, заданное рабочими и запрещенными наборами с помощью матрицы Карно.

Строим матрицу Карно на четыре переменных и заполним клетки единицами и нулями соответственно для рабочих и запрещенных наборов.

Таблица 3.6.

х 3 х 4 х 1 х 2	00
			(1)
	(1)		(1)

При объединении клеток с единицами в контуры желательно, чтобы в каждый контур включалось наибольшее число клеток из максимально возможного. Для этого клетки некоторых безразличных наборов используем как клетки рабочих наборов, подставив в них единицы в скобках. В результате получим три контура, содержащие по 4 клетки. В обобщенном коде контура, включающего в себя все клетки одной строки, пропадают переменные х 2 х 3 (10 - -). В обобщенном коде контура, включающего все клетки одного столбца пропадают переменные х 1 х 2 (- - 11) и для контура, содержащего по две клетки двух строк пропадают переменные х 2 (при переходе в контуре из одной строки в другую) и х 3 (при переходе из одного столбца в другой). В результате получим минимальную ДНФ в следующем виде

Возможные варианты объединения клеток матрицы Карно в контуры показаны на рисунке 3.4.

х 3 х 4 х 1 х 2

А = 0 - 0 -

З = - 0 - 0

Н

Б = 1 - 1 -

К = - - - 1

В = - - 0 0

Л = - 1 - -

Г = 1 0 - -

М = - - - 0

Д = - 0 0 1

Н = - 0 - -

Е = - 0 1 -

Ж = - 1 - 1

Рис. 3.1. Возможные варианты объединения клеток матрицы Карно в контуры

3.3.2. Минимизация функций алгебры логики с помощью матрицы на пять переменных

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

В матрице на пять переменных (таблица 3.7.) строкам соответствуют наборы переменных х 1 х 2 х 3 , а столбцам наборы переменных х 4 х 5 . Каждой клетке матрицы соответствует пятиразрядное двоичное число. В клетках матрицы (табл. 3.7.) проставлены десятичные эквиваленты соответствующих двоичных чисел.

Таблица 3.7.

х 4 х 5 х 1 х 2 х 3

Минимизация ФАЛ с помощью матрицы на пять переменных заключается в объединении клеток с рабочими наборами (включая при необходимости и клетки с безразличными наборами) в контуры и получении для этих контуров соответствующих им обобщенных кодов.

Особенность здесь заключается в том, что в столбцах матрицы на пять переменных объединять по четыре клетки в контуры можно только или четыре клетки сверху, или четыре клетки внизу, или четыре клетки посередине. Например, для последнего столбца матрицы контуры могут состоять из клеток 2, 6, 14, 10, или 26, 30, 22, 18 или 14, 10, 26, 30.

Пример 3.6. Минимизировать с помощью матрицы на пять переменных следующее логическое выражение

Строим матрицу на пять переменных и заполняем клетки рабочих наборов единицами, запрещенных – нулями.

Объединяем в контуры клетки с рабочими наборами, включая в них необходимые клетки безразличных наборов. Для каждого контура определяем обобщенных код.

Таблица 3.8.

х 4 х 5 х 1 х 2 х 3
	(1)	(1)	(1)
	(1)
	(1)	(1)
		(1)	(1)
	(1)		(1)
			(1)
	(1)		(1)

Получаем минимальную ДНФ

Контрольные вопросы

1. Дать определение сокращенной ДНФ.

2. Что представляет собой тупиковая ДНФ?

3. Как выбирается минимальная ДНФ из тупиковых ДНФ?

4. Для чего используется импликантная таблица и как она строится?

5. Пояснить аналитический способ минимизации ФАЛ Квайна-Мак-Класски.

6. Как строится матрица Карно на три и четыре переменных?

7. Минимизировать аналитическим способом следующие логические выражения, заданные только рабочими наборами

8. Минимизировать с помощью матрицы Карно логические выражения, заданные рабочими и запрещенными наборами

Похожая информация.

Все логические функции задаются либо в виде формулы, либо в виде таблицы значений. Иногда бывает нужно определить простейшую форму записи этой функции с минимальным количеством элементарных логических функций И, ИЛИ, НЕ для удобства работы. Для этого используются все рассмотренные операции начиная с №4 и методы Квайна и Вейча.

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

Метод Вейча (карты Карно)

В этом методе для изображения функции n переменных рисуется специальная таблица, которая содержит 2 n клеток. В каждой клетке ставится соответствие одному из наборов n переменных. В клетке записывается значение, принимаемое функцией при этом наборе аргументов. Все клетки, соответствующие наборам содержащие некоторую переменную без знака инверсии образуют область из 2 n -1 клеток. Эта область называется областью данной переменной (например, область переменной х). Остальные клетки образуют область этой инверсной переменной. Возможные наборы аргументов распределены по клеткам таким образом, чтобы границы областей всех переменных и их инверсии были четки, а принадлежность любой клетки к той или иной область зрительно легко выявлялась.

1) Функция одной переменной:

2) Функция двух переменных:

3) Диаграмма для дизъюнкции:

4) Диаграмма для конъюнкции:

5) Для трех аргументов:

6) Для четырех аргументов:

Можно минимизировать заданное логическое выражение, объединив в группы стоящие рядом единицы и при этом исключать ту переменную, которая переходит из прямого в инверсное состояние. Объединять можно не только по вертикали и горизонтали, но и по краям, так как в общем случае карта Карно образует тор. Пример:

б)

Работа по теме

МЕТОДЫ МИНИМИЗАЦИИ
ЛОГИЧЕСКИХ ФУНКЦИЙ

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

Содержание

Введение

Люди, далекие от техники, часто смотрят на ЭВМ и другие цифровые электронные устройства как на нечто таинственное и непостижимое. Тем не менее, все эти устройства работают в строгом соответствии с четкими логическими законами. Знание и понимание этих законов помогает в общении с компьютером и другими цифровыми устройствами.

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

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

Упрощенная функция будет содержать меньше операций и комбинаций аргументов, а значит и схема, реализующая функцию, будет содержать меньше элементов, т.е. будет дешевле и надежнее .

В связи с этим минимизация логических функций особенно актуальна.

Целью работы является изучение методов минимизации функций алгебры логики.

Объектом работы стал процесс минимизации логических функций.

Предмет исследования – методы минимизации логических функций и методика преподавания этой темы в профильных классах.

Задачи исследования:

изучить основные элементы математической логики;

исследовать методы минимизации логических функций;

подобрать задачи для самостоятельной работы;

решить описанными методами подобранные задачи.

Работа состоит из введения, двух разделов, заключения и списка использованной литературы.

Во введении обосновывается актуальность темы, определяется цель и задачи исследования.

В первом разделе рассматриваются логические основы функционирования ЭВМ.

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

В заключении подводятся общие итоги исследования.

Логические основы функционирования ЭВМ

Элементы математической логики

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

Вычислительные машины всех поколений состояли и состоят из логических элементов и элементов памяти, принимающих два значения (бита) 0 и 1. Вся обработка информации в ЭВМ всех ее логических блоков, логических схем и устройств опиралась и будет опираться на законы и принципы математической логики .

Логика (от древнегреческого logos, означающего «слово, мысль, понятие, рассуждение, закон») – это древнейшая наука, изучающая правильность суждений, рассуждений и доказательств.

Математическая логика – это математическая дисциплина, изучающая технику доказательств .

Основоположником математической логики является великий немецкий математик Готфрид Вильгельм Лейбниц (1646 – 1716 гг.). Он выдвинул идею о применении в логике математической символики и построении логических исчислений, поставил задачу логического обоснования математики, сыграл важную роль в истории создания электронно-вычислительных машин: предложил использовать для целей вычислительной математики бинарную систему счисления. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, – которая в отличие от обычной алгебры оперирует не числами, а высказываниями. В честь Д.Буля логические переменные в языке программирования «Паскаль» впоследствии назвали булевскими.

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

Высказывание – это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет; это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками) .

Различные логические выражения (высказывания) могут принимать только два значения: «истинно» или «ложно». Каждая логическая переменная может принимать только одно значение. Существуют разные варианты обозначения истинности и ложности:

Истина

И

True

T

1

Ложь

Л

False

F

0

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

Рассмотрим логические операции, с помощью которых можно записать любое логическое выражение.

Самой простой логической операцией является операция НЕ (по-другому ее часто называют отрицанием, дополнением или инверсией и обозначают ). Результат отрицания всегда противоположен значению аргумента. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица «не» или слова «неверно, что».

Таким образом, отрицанием некоторого высказывания называется такое высказывание, которое истинно, когда ложно, и ложно, когда истинно .

Логическая операция НЕ является унарной, т.е. имеет всего один операнд. Определение отрицания может быть записано с помощью так называемой таблицы истинности, в которой указано, указано, какие значения истинности (1, 0) принимает отрицание в зависимости от значений истинности исходного высказывания :

1

0

0

1

Логическое И (логическое умножение или конъюнкция) – это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложное выражение ложно. Конъюнкцию высказываний и обозначают: , а иногда пишут просто . Высказывания в составе конъюнкции соединены союзом «и». Определение конъюнкции может быть записано в виде таблицы истинности, в которой для каждого из четырех возможных наборов значений исходных высказываний и задается соответствующее значение конъюнкции :

1

1

1

1

0

0

0

1

0

0

0

0

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: конъюнкция А 1 & A 2 & A 3 &...& A N истинна тогда и только тогда, когда истинны все высказывания А 1 , A 2 , A 3 , ...A N (а, следовательно, ложна, когда ложно хотя бы одно из этих высказываний) .

Логическое ИЛИ (логическое сложение или дизъюнкция) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выражения ложны. Дизъюнкцию высказываний и мы обозначим символом и будем читать: или . Определение дизъюнкции может быть записано в виде таблицы истинности:

1

1

1

1

0

1

0

1

1

0

0

0

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число составляющих: дизъюнкция А 1 А 2 А 3 ... А N истинна тогда и только тогда, когда истинно хотя бы одно из высказываний А 1 , А 2 , А 3 , ..., А N (а следовательно, ложна, когда ложны все эти высказывания).

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

Логическое следование (импликация) – это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием ( ), а второе ( ) является следствием. Обозначим импликацию символом и запись « » будем читать: «Из следует ».

Запишем это определение в виде таблицы истинности:

1

1

1

1

0

0

0

1

1

0

0

1

Высказывание «Если , то » с логической точки зрения имеет тот же смысл, что и высказывание «неверно, что истинно и ложно». Это означает, что функцию импликации можно заменить комбинацией двух функций (отрицания и конъюнкции).

Логическое тождество (эквиваленция) – это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность. Обозначают эквиваленцию символом и запись « » читают « эквивалентно », или « равносильно », или « , если и только если », « тогда и только тогда, если ». Определение эквиваленции может быть записано в виде таблицы истинности:

1

1

1

1

0

0

0

1

0

0

0

1

Логические функции и их преобразование

Логическая функция – это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1 .

Каждая логическая функция может быть задана большим количеством различных по виду функций. Но даже любую достаточно сложную логическую функцию можно реализовать, имея относительно простой набор базовых логических операций. Наиболее известный базис – это набор функций «и», «или», «не».

Для операций конъюнкции, дизъюнкции и инверсии определены законы, позволяющие производить тождественные (равносильные) преобразования логических выражений :

;

.

Основываясь на законах, можно выполнять упрощение сложных логических выражений.

Исходными, из соображений удобства последующих преобразований, приняты следующие две канонические формы представления функций: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).

Прежде чем перейти к СДНФ и СКНФ введем некоторые понятия.

Элементарной конъюнкцией называется конъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые .

Элементарной дизъюнкцией называется дизъюнкция нескольких переменных, взятых с отрицанием или без отрицания, причём среди переменных могут быть одинаковые .

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

Например, выражение является ДНФ.

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

Например, выражение является КНФ.

Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .

Например, выражение является ДНФ, но не является СДНФ; выражение является СДНФ.

Совершенной КНФ (СКНФ) называется КНФ, в которой нет равных элементарных дизъюнкций, и все они содержат одни и те же переменные, причём каждую переменную только один раз (возможно с отрицанием) .

Например, выражение .

Приведу алгоритмы переходов от одной формы к другой. Естественно, что в конкретных случаях (при определенном творческом подходе) применение алгоритмов бывает более трудоемким, чем простые преобразования, использующие конкретный вид данной формы :

переход от произвольного задания функции к ДНФ

Этот переход сводится к опусканию общих для нескольких переменных инверсий, раскрытию скобок и объединению, если они возникают, одинаковых членов с использованием законов:

Например:

переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения. Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Второй способ перехода от ДНФ к КНФ – использование дистрибутивного закона:

переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения):

переход от КНФ к СКНФ

Этот переход осуществляется способом, аналогичным предыдущему: если в простой дизъюнкции не хватает какой-то переменной, например, z , то добавляем в нее выражение (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:

переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z , то умножаем неполную конъюнкцию на выражение вида , после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). Например:

Для получения СДНФ и СКНФ из таблиц истинности необходимо выполнить следующие 4 пункта алгоритма :

СДНФ

СКНФ

Конструирование СДНФ и СКНФ начинается с таблицы истинности.

Отметим те строки таблицы, выходы которых равны

1

0

Выписываем для каждой отмеченной строки комбинацию переменных через знак

конъюнкция (&)

дизъюнкция (V)

Знаки операции отрицания расставляем следующим образом:

если переменная равна 1, то запишем саму эту переменную, если же она равна 0, то запишем ее отрицание.

если переменная равна 0, то запишем саму эту переменную, если же она равна 1, то запишем ее отрицание.

Все полученные выражения связываем операцией

дизъюнкции

конъюнкции

Получив СДНФ или СКНФ, можно составить электронную схему, реализующую данную логическую функцию. Для ее постороения требуется 3 логических элемента :

инвертор

конъюнктор

дизъюнктор

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

Минимизация логических функций

Как отмечалось в предыдущей главе, логическая функция может быть представлена в виде таблицы истинности или в виде СДНФ (совершенной дизъюнктивной нормальной формы) или СКНФ (совершенной конъюнктивной нормальной формы) и может быть использована для получения логической схемы устройства. Однако полученная логическая схема, как правило, не будет оптимальна. Поэтому важным этапом синтеза логических схем является минимизация логических функций.

Минимизацией называется преобразование логических функций с целью упрощения их аналитического представления.

Существуют два направления минимизации:

Кратчайшая форма записи (при этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ);

Получение минимальной формы записи (получение минимального числа символов для записи всей функции сразу).

Но следует учесть, что ни один из способов минимизации не универсален.

Для минимизации функций алгебры логики был разработан ряд методов:

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

метод минимизации логических функций при помощи карт Карно;

метод Квайна-Мак-Класки;

метод Блейка-Порецкого;

метод Петрика и другие.

Остановимся более подробно на первых двух методах.

Метод непосредственных преобразований логических функций

Одним из простых методов минимизации является метод непосредственных преобразований, который осуществляется с использованием основных теорем алгебры логики .

При применении данного метода:

Записываются СДНФ логических функций,

Форма преобразуется и упрощается с использованием аксиом алгебры логики, при этом, в частности, выявляются в исходном СДНФ соседние термы (члены), в которых есть по одной не совпадающей переменной.

По отношению к соседним термам применяется закон склейки.

Термы, образованные при склеивании называются импликантами.

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

Полученная в результате минимизации функция называется тупиковой.

Пусть дана функция

Минимизируем ее описанным выше методом. Для этого добавим еще одно слагаемое и воспользуемся законами склеивания .

Получили минимальную функцию

Рассмотренный метод минимизации путем непосредственных преобразований достаточно прост, особенно при небольшом числе переменных. Недостатком метода является то, что он не указывает строго формализованный путь минимизации. При большом числе переменных минтермы могут группироваться по-разному, в результате чего можно получить различные упрощенные формы заданной функции. При этом нельзя быть уверенным в том, что какая-то из этих форм является минимальной. Возможно, что получена одна из тупиковых форм, которая больше не упрощается, не являясь при этом минимальной.

Метод минимизации логических функций при помощи карт Карно

Карта Карно или карта (диаграмма) Вейча – графический способ минимизации функций алгебры логики.

Карты Карно удобны при небольшом числе переменных.

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

На рис. 1 представлены карты Вейча для двух, трех и четырех переменных соответственно .

рис. 1

Расположение групп переменных x не имеет значения, необходимо лишь, чтобы каждая клетка отличалась от любой соседней лишь на одну переменную. Согласно принятой форме построения карт соседними также считаются клетки первой и последней строк, клетки первого и последнего столбцов. Число клеток карты равно числу возможных комбинаций значений переменных (термов) и в каждую клетку записывается значение логической функции, соответствующее данному набору переменных. Если какая-то из возможных комбинаций присутствует в совершенной дизъюнктивной нормальной форме (СДНФ) записи функции, то в соответствующей клетке карты Карно ставится «1». Если какого-то терма в полученной функции нет, то в соответствующей клетке карты Карно ставится «0» .

Например, рассмотренная в предыдущем примере функция

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

рис. 2

В карте Карно логические 1 , записанные в соседних клетках, обозначают, что соответствующие этим 1 конъюнкции (произведения) отличаются лишь по одной переменной, которые дополняют друг друга и их можно опустить.

Так в первой строке карты Карно (см. рис. 2 б) переменная х , встречается в комбинации с х 1 и х 2 , которые дополняют друг друга:

Таким образом, группируя две соседние клетки в верхней строке (контур на рис. 2 б), можно исключить одну переменную – х 1 .

Аналогично, группируя две соседние клетки в левом столбце (контур на рис. 2 б) и исключая отличающиеся переменные, получим упрощенное выражение – х 2 .

Полученные упрощенные выражения объединяют с помощью операции ИЛИ.

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

Допускается также иметь несколько групп перекрывающихся клеток, как в только что рассмотренном примере.

Группироваться могут также клетки первой и последней строк, первого и последнего столбцов, т. е. карту допускается сворачивать в цилиндр как по вертикальной, так и по горизонтальной оси.

Для исключения n переменных общее число группируемых клеток должно быть равно 2 n . Так, для исключения одной переменной требуется объединить две соседние клетки, а для исключения трех переменных уже требуется объединить восемь соседних клеток .

Таким образом, для того чтобы получить минимизированную логическую функцию, необходимо сгруппировать все соседние клетки карты Карно, содержащие 1, а затем объединить полученные группы с помощью операции ИЛИ. Клетки, содержащие 1, которые не удалось объединить с другими клетками, образуют в минимизированной логической функции самостоятельные члены, каждый из которых содержит все переменные .

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

Так, карта Вейча для логической функции

приведена на рисунке 3.

рис. 3

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

Упрощенное выражение логической функции имеет вид

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

Рассмотрим пример минимизации логической функции

Карта Карно для этой функции представлена на рисунке 4:

рис. 4

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

В верхнем контуре можно исключить две переменные (х 2 и х 4 ) и после этого в нем остается член . Упрощенное булево выражение логической функции имеет вид

Рассмотрим минимизацию логической функции, карта Вейча которой представлена на рис. 5.

рис. 5

Булево выражение этой функции имеет вид

Четыре угловые клетки можно объединить в одну группу. Это объединение позволяет исключить две переменные (х 1 и х 2 ) и получить член .

Две единицы из первой строки можно объединить с двумя единицами из нижней строки, получить группу из четырех ячеек, которая позволяет исключить две переменные (х 1 и х 3 ) и получить член .

Наконец, единственную оставшуюся единицу (из второй строки и последнего столбца) можно объединить с клеткой, находящейся над ней, и это позволит исключить одну переменную (х 4 ) и получить член .

Таким образом, мы получим минимизированную логическую функцию

Метод карт Карно (диаграмм Вейча), по существу, упрощает нахождение склеиваемых конъюнкций в СДНФ исходной логической функции.

Минимизация функций алгебры логики описанными методами

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

Упростить, используя карты Карно для функции 2 переменных:

Карта Карно (диаграмма Вейча) для этой функции будет иметь вид:

В первой строке можно исключить переменную х 2 и получить упрощенное выражение х 1 .

Во втором столбце можно исключить переменную х 1

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

В первом столбце можно исключить переменную х 1 и получить упрощенное выражение х 2 .

Во второй строке можно исключить переменную и получить упрощенное выражение .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

Упростить, используя карты Карно для функции 3 переменных:

Диаграмма Вейча для этой функции будет иметь вид:

х 3 и получить упрощенное выражение .

х 3 и получить упрощенное выражение .

В последнем столбце можно исключить переменную х 1 и получить упрощенное выражение .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

Диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение и переменную х 2 и получить упрощенное выражение .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

Нами был найден и второй способ минимизации данной функции.

Тогда диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение .

В первой строке остается выражение .

Полученные выражения соединим операцией ИЛИ.

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

Очевидно, что полученная функция не является минимальной, поэтому воспользуемся методом непосредственных преобразований логических функций. Вынесем за скобки переменную х 1 и для выражения в скобках применим правило свертки. Получили тот же результат, что и в первом случае.

Это значит, что соседние клетки можно группировать разными способами, главное, не забывать основное правило: для исключения n переменных общее число группируемых клеток должно быть равно 2 n .

Диаграмма Вейча для этой функции будет иметь вид:

первой строке можно исключить переменную х 3 и получить упрощенное выражение .

0 1 0 0

О втором столбце можно исключить переменную х 1 .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

Диаграмма Вейча для этой функции будет иметь вид:

В первой строке можно исключить переменную х 3 и получить упрощенное выражение .

Во второй строке можно исключить переменную х 3 и получить упрощенное выражение .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

Диаграмма Вейча для этой функции будет иметь вид:

В первом и последнем столбце можно исключить переменные х 1 и х 2 и получить упрощенное выражение .

Во второй строке можно исключить переменную х 2 и получить упрощенное выражение . О .

Полученные упрощенные выражения соединим операцией ИЛИ.

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

В данной главе были представлены функции двух, трех и четырех переменных, которые минимизировались с помощью диаграмм Вейча. Мною были наглядно продемонстированы и описаны особенности применения данного метода минимизации на различных функциях, в том числе и в совокупности с методом непосредственного преобразования функций алгебры логики.

Заключение

Представленная работа посвящена методам минимизации функций алгебры логики. В процессе работы были:

1. изучены основные элементы математической логики;

   исследованы методы минимизации логических функций;

   подобраны задачи для самостоятельной работы;

   решены описанными методами подобранные задачи.

Мною было подробно рассмотрено 2 метода минимизации логических функций:

метод непосредственных преобразований логических функций, осуществляемый с использованием теорем алгебры логики;

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

Первый метод получил широкое распространение даже в школьных учебниках информатики (например, учебники 10-11 класса Н. Угриновича , Л. Щауцуковой ), поскольку является одним из простых методов упрощения функций алгебры логики. Задания, представленные в учебниках указанных авторов, достаточно разнообразны:

упростить логическую формулу с помощью законов алгебры логики;

по заданной функции построить логическую схему;

упростить переключательную схему;

доказать с помощью таблицы истинности логическое выражение;

построить для данной функции таблицу истинности.

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

Данная тема имеет практическое значение в микроэлектронике. Кроме того, ЕГЭ по информатике и ИКТ содержит некоторое количество заданий, связанных с алгеброй логики, которые мы разделили на 4 группы .

Первая группа – это задания, требующие указать логическое выражение, равносильное данному.

Вторая группа – задания на нахождение фрагментов таблиц истинности, соответствующих данному выражению.

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

И четвертая группа – это задания на определение структурной формулы, соответствующей данной логической схеме.

Заданий конкретно касающихся минимизации логических функций мне не встретилось, но имеющиеся в тестах задания требуют достаточно глубоких знаний в области алгебры логики.

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

Список литературы

Гаврюкова Г. А. Логика в информатике [Электронный ресурс]. – Режим доступа: окт. 2010).

Ивин А. А. Логика: Учебное пособие. – 2-е изд. – М.: Знание, 1998. – 233 с.

Игошин В. И. Математическая логика и теория алгоритмов: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Академия, 2008. – 448 с.

Информатика и ИКТ. Подготовка к ЕГЭ-2009. Вступительные испытания. / Под ред. Ф. Ф. Лысенко. – Ростов н/Д: Легион-М, 2009. – 208 с.

Информатика: Учебник / Б. В. Соболь [и др.]. – 3-е изд., доп. и перераб. – Ростов н/Д: Феникс, 2007. – 446 с.

Информатика: Учебное пособие / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – 3-е изд. – М.: Академия, 2004. – 848 с.

Калабеков Б. А. Цифровые устройства и микропроцессорные системы: Учебник для техникумов связи. – М.: Горячая линия – Телеком, 2000. – 336 с.

Каймин В. А. Информатика: Учебник. – 2-е изд., перераб. и доп. – М.: ИНФРА-М, 2001. – 272 с.

Коваленко А. А, Петропавловский М. Д. Основы микроэлектроники: Учебное пособие. – М.: Академия, 2006. – 240 с.

Львовский М. Б. Методическое пособие по информатике для учащихся 9-11 классов, изучающих IBM PC [Электронный ресурс]. – Режим доступа: сент. 2010).

Математические основы информатики. Элективный курс: Учебное пособие / Е. В. Андреева, Л. Л. Босова, И. Н. Фалина. – М.: БИНОМ. Лаборатория знаний, 2005. – 328 с.

Минимизация логических функций [Электронный ресурс]. – Режим доступа: авг. 2010).

Основы микроэлектроники: Учебное пособие для вузов / Н. А. Аваев, Ю. Е. Наумов, В. Т. Фролкин. – М.: Радио и связь, 1991. – 288 с.: ил.

Практикум по информатике и информационным технологиям / Н. Д. Угринович, Л. Л. Босова, Н. И. Михайлова. – 2-е изд., испр. – М.: БИНОМ. Лаборатория знаний, 2004. – 394 с.

Прикладная математика: Пособие / И. Н. Ревчук, В. К. Пчельник. – Гродно: ГрГУ им. Я. Купалы, 2007. – 128 с.

Рабкин Е. Л., Фарфоровская Ю. Б. Дискретная математика: булевы функции и элементы теории графов: Методические указания и контрольные задания [Электронный ресурс]. – Режим доступа: 7 авг. 2010).

Савельев А. Я. Основы информатики: Учебник для вузов. – М.: МГТУ им. Н. Э. Баумана, 2001. – 328 с., ил.

Степаненко И. П. Основы микроэлектроники: Учебное пособие для вузов. – 2-е изд., перераб. и доп. – М.: Лаборатория Базовых Знаний, 2001. – 488 с.

Теория и методика обучения информатике: Учебник / [М. П. Лапчик, И. Г. Семакин, Е. К. Хеннер, М. И. Рагулина и др.]; под ред. М. П. Лапчика. – М.: Академия, 2008. – 592 с.

Угринович Н. В. Информатика и ИКТ. 10 класс. Профильный уровень. – 3-е изд., испр. – М.: Бином. Лаборатория знаний, 2008. – 387 с.

Угринович Н. В. Информатика и информационные технологии: Учебник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2003. – 512 с.

Шауцукова Л. З. Информатика 10 – 11. – М.: Просвещение, 2004. – 420 с.

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

В основе методов минимизации лежит операция склеивания (алгоритм объединения соседний двоичных чисел):

где А - элементарная конъюнкция.

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

Минимальной дизъюнктивной нормальной формой (МДНФ) булевой функции называется ДНФ, содержащая наименьшее число букв (по отношению ко всем другим ДНФ, представляющим заданную булеву функцию).

Минимизировать функции, то есть находить наиболее простое выражение для исходной функции можно различными методами. Все они практически различаются лишь на первом этапе - этапе получения сокращенной ДНФ. Следует отметить, что, к сожалению, поиск МДНФ всегда связан с некоторым перебором решений. Рассмотрим некоторые из них.

Минимизация сложных логических выражений с помощью матрицы Карно

Дли реализации алгоритма объединения необходимо из всей совокупности обязательных конституентов в совершенной дизъюнктивной нормальной форме функции алгебры логики отыскать соседние. Для отыскания соседних конституентов используются матрицы Карно, решетка соседних чисел, таблицы соседних конституентов.

Матрицы Карно целесообразно использовать для минимизации ФАЛ на наборах из 2,3,4,5 и 6 переменных. Номера столбцов в матрицах Карно образуют младшие разряды, а номера строк - старшие разряды наборов. Номера клеток составляются из номеров строк и столбцов и соответствуют наборам переменных.

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

Таблица 1. Матрица Карно

Столбцы и строки в этой матрице обозначены двоичными соседними числами: 00-0I-II-I0. Поэтому номера смежных по горизонтали и вертикали клеток, а также крайних в строках и столбцах клеток являются соседними числами, например:

клетки с номерами и;

клетки с номерами;

клетки с номерами;

клетки с номерами.

Для минимизации функции алгебры логики, заданной в совершенной дизъюнктивной нормальной форме, с помощью матрицы Карно необходимо: подготовить матрицу Карно, вписав в клетки, соответствующие обязательным конституентам, единицы, объединить клетки с единицами в «подкубы», записать минимизированную функции алгебры логики в дизъюнктивной нормальной форме.

В «подкубы» объединяются:

• - две клетки с номерами, являющимися соседними числами, при этом исключается одна переменная;
• - четыре клетки (строка, столбец, квадрат, угловые клетки), при этом исключается две переменные;
• - восемь клеток (две соседних или крайних строки (столбца)), при этом исключается три переменные.

Для обеспечения исключения возможно большего количества переменных размеры «подкубов» должны быть как можно больше, а число их как можно меньше. С этой целью можно одну и ту же клетку с единицей использовать несколько раз, включая в различные «подкубы». Число слагаемых в минимизированной функции алгебры логики равно числу подкубов и клеток с единицами, не объединенных в подкубы.

Пусть необходимо минимизировать следующую функцию алгебры логики:

Матрица Карно, заполненная в соответствии с этой формулой, может быть представлена в виде таблицы 2:

Таблица 2. Матрица Карно

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

Метод Квайна

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

На первом этапе выполняется переход от функции, заданной в форме ДНФ, к сокращенной ДНФ. Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью. Для доказательства достаточно показать, что произвольная простая импликанта р = xi1 xi2 ... xin может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания):

по всем недостающим переменным x ik , ..., xim исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта.

В результате выполнения склеивания получается конъюнкция n-1 ранга, а конъюнкции остаются в исходном выражении и участвуют в сравнении с другими членами СДНФ. Таким образом, удается снизить ранг термов.

Склеивание и поглощение выполняются до тех пор, пока имеются члены, не участвовавшие в попарном сравнении. Термы, подвергшиеся операции склеивания, отмечаются. Неотмеченные термы представляют собой простые импликанты и включаются в сокращенную ДНФ. Все отмеченные конъюнкции ранга n-1 подвергаются вновь операции склеивания до получения термов n-2 ранга и так далее до тех пор, пока количество неотмеченных конъюнкций больше 2. В результате выполнения первого этапа получена сокращенная ДНФ.

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

Для формирования тупиковых ДНФ строится импликантная таблица (матрица), строки которой отмечаются простыми импликантами сокращенной ДНФ, а столбцы конститутиентами единицы исходной СДНФ. В строке напротив каждой простой импликанты ставится метка под теми наборами (конститутиентами единицы), на которых она принимает значение 1. Соответствующие конститутиенты поглощаются (покрываются) данной простой импликантой.

Из общего числа простых импликант необходимо отобрать их минимальное число, исключив лишние. Формирование тупиковых форм и выбор минимального покрытия начинается с выявления обязательных простых импликант, то есть таких, которые (и только они) покрывают некоторый исходный набор. Рассмотрим на примере минимизации логической функции:

f СДНФ = V (1,2,5,6,7)=x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

1 2 3 4 5

Выполним операцию склеивания:

• 1 - 3 (x1 ) x2 x3 1
• 2 - 4 (x1 ) x2 x3 2
• 3 - 5 (x2 ) x1 x3 3
• 4 - 5 (x3 ) x1 x2 4

В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.

f сокр СДНФ =x2 x3 + x2 x3 + x1 x3 + x1 x2

Для выявления обязательных простых импликант и фрормирования на их основе минимального покрытия строится импликантная таблица (таблица 3). В строках импликантгой таблицы записываются простые импликанты, а в столбцах конституэнты единицы. Звездочка ставится если простая импликанта покрывает контитуэнту.

Таблица 3. Импликантная таблица

	x 1 x2 x3	X 1 x2 x3	x 1 x2 x3	x 1 x2 x3	x 1 x2 x3

Простые импликанты являются обязательными так как только они покрывают конституэнтыи включаются в минимальное покрытие. Остается одна непокрытая конституэнта x1 x2 x3 которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм.

Метод Блейка - Порецкого

Метод позволяет получать сокращенную ДНФ булевой функции f из ее произвольной ДНФ. Базируется на применении формулы обобщенного склеивания:

справедливость которой легко доказать. Действительно,

Следовательно,

В основу метода положено следующее утверждение: если в произвольной ДНФ булевой функции f произвести все возможные oбобщенные склеивания, а затем выполнить все поглощения, то в результате получится сокращенная ДНФ функции f.

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

Необходимо используя метод Блейка - Порецкого получить сокращенную ДНФ функции f. Проводим обобщенные склеивания. Легко видеть, что первый и второй элемент исходной ДНФ допускают обобщенное склеивание по переменной х 1 . В результате склеивания получим:

Первый и третий элемент исходной ДНФ допускают обобщенное склеивание как по переменной х 1 , так и по х2 . После склеивания по x1 имеем:

После склеивания по x 2 имеем:

Второй и третий элемент ДНФ допускают обобщенное склеивание по переменной х 2 . После склеивания получаем:

Выполнив последнее обобщенное склеивание, приходим к ДНФ:

После выполнения поглощений получаем:

Попытки дальнейшего применения операции обобщенного склеивания и поглощения не дают результата. Следовательно, получена сокращенная ДНФ функции f. Далее задача поиска минимальной ДНФ решается с помощью импликантной матрицы точно так же, как в методе Квайна.

Минимизация не полностью определенных ФАЛ

Если при синтезе логической схемы, реализующей некоторую ФАЛ n переменных, окажется, что некоторые наборы из общего числа 2n никогда не смогут появиться на входах схемы, то данная логическая функция не определена на этих наборах. Тогда 2n наборов переменных можно подразделить на три группы: наборы, на которых функция принимает единичное значение L, нулевое значение D и группа наборов, на которых функция не определена N (неопределенные наборы). ФАЛ, содержащая неопределенные наборы, называется неполностью или частично определенной. Неопределенные наборы могут быть использованы для улучшения качества минимизации. При этом неопределенные наборы (при минимизации, например, картами Вейча, Карно) могут участвовать в образовании контуров как с единичными, так и с нулевыми наборами. Это приводит к формированию более простой минимизированной логической функции.

Универсальным методом минимизации является использование законов и соотношений алгебры логики, которые позволяют проводить минимизацию ФАЛ при любом числе переменных.