Спирина, М.С. Дискретная математика

результата видим, что эта же булева функция может быть задана другой схемой, содержащей всего три элемента (рис. 4.8, б). Потребность в минимизации булевых функций возникает как при синтезе логических схем (в целях экономии), так и при реше­ нии логических задач для поиска минимального числа перемен­ ных и связок между ними. При решении логических задач ответ удобнее представлять или в СДНФ, или в виде КНФ. Если резуль­ тат должен быть представлен в виде условного предложения (им­ пликации), то переход к ней возможен из дизъюнкции. 4.6.3. Карты Карно Минимизировать нормальные формы можно различными спо­ собами: методом каскадов, с помощью карт Карно и другими. Минимальная нормальная форма получается из совершенной конъюнктивной дизъюнктивной нормальной формы удалением некоторых эле­ ментарных дизъюнкции . Тупиковой нормальной формой назы- конъюнкции КНФ вается д Д ф . из которой нельзя удалить ни одной элементарной Так, чтобы сохранить неизменной заданную булеву дизъюнкции функцию. Для представления булевой функции в таком виде не­ обходимо сначала представить ее в совершенном виде и только затем минимизировать до минимальной из всех тупиковых форм. Карты Карно являются одним из наиболее удобных способов минимизации. Они впервые появились в одной из статей Мориса Карно в 1953 г. Это специальные таблицы, дающие возможность упростить процесс поиска минимальной формы булева выраже­ ния с помощью графического представления для я < 6. Они имеют вид прямоугольника, разделенного на 2" клеток, в каждой из ко­ торых — двоичный л-мерный набор значений функции F h 3 таб­ лицы истинности. Для л = 2 карта Карно имеет вид таблицы, состоящей из 22 = 4 клеток. или Логическая функция F на карте Карно представлена совокупно­ стью клеток, заполненных единицами (1) или пустотами (0), если известны ее значения при всем наборе аргументов, т.е. известна 00 10 01 11 *i * 1 * 2 * 1 * 2 * i * 2 * 1 * 2 180