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

может лечить или оперировать больного, но он помогает врачу определиться с выбором направления лечения. Причем скорость реакции «врача-компьютера» и энциклопедические знания, зало­ женные в него человеком, делают его достойным помощником врача-человека. Но для работы с ним необходимо уметь правиль­ но задавать вопросы и находить адекватную форму ответа. 4.6. Минимизация булевых функций Если исключить невозможное, то, что останется, сколь бы невероятным оно ни было, должно быть истиной. А. Конан-Дойль Прежде не раз упоминалась возможность представления любой булевой функции в виде суперпозиции булевых функций одного и двух аргументов. Кроме того, хотелось, чтобы подобное разло­ жение включало в себя простейшие с точки зрения интуитивного понимания операции: отрицание, конъюнкцию и дизъюнкцию. Так, в подразд. 4.3 строгая дизъюнкция, импликация и эквива- ленция были выражены через эти три элементарные функции. Кро­ ме того, упоминалась двойственность конъюнкции и дизъюнкции. Подобное представление полезно, например, в электротехнике, где микросхема реализует одну из этих простейших операций. Да­ лее мы докажем, что любую булеву функцию можно выразить через отрицание (НЕ), конъюнкцию (И) и дизъюнкцию (ИЛИ), а пока будем считать, что функция уже эквивалентна компози­ ции этих трех функций. 4.6.1. Разложение функций по переменным. Нормальные формы Рассмотрим булевы функции, представленные в виде суперпо­ зиции элементарных функций И, ИЛИ, НЕ. Используя законы алгебры логики, можно заменить громоздкие булевы функции им равносильными, но более простыми. Такой процесс называется минимизацией булевых функций. Его проводят для упрощения слож­ ных логических выражений в программах, а также для того, что­ бы построенные на их основе функциональные схемы не содер­ жали лишних элементов. Минимизировать булевы функции надо, приводя их к так на­ зываемой нормальной форме. Существуют две разновидности нормальных форм —дизъюн­ ктивные (ДНФ) и конъюнктивные (КНФ). Введем определения. 170