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

Таким образом, для описания булевой алгебры достаточно од­ ной функции. Другое дело, что стрелку Пирса и штрих Шеффера трудно интерпретировать в теории множеств и реализовать в виде элементарных логических схем через элементы И —НЕ и ИЛИ — НЕ, а формулы и логические схемы, составленные только из них, являются громоздкими. Вообще говоря, в алгебре логики доказано, что базис содер­ жит не более четырех функций. Хотя существует базис, который содержит ровно четыре функции и образует функционально пол­ ную систему: / ' = 0, / / = 1 , / 3' = х х ъ / / = х, ® х 2 Ф х3. Приведем примеры основных функционально полных систем булевых функций: и, или, не, которые лежат в основе алгебры высказываний или булевой алгебры, = ( / 7, / |0, / 4) = {v , л , и, не, S2 = ( /4, / 7) = {л, или, не, т.е. S 3 = ( / 4, / , 0) = {v , штрих Шеффера, S 4 = ( / 6) = { I }; стрелка Пирса, S5 = (f2) = {i}; сумма по модулю два, и, ( / 5, f i , fn) - {®, л , 1}; х,х2, не, S7 = ( / 3 , / 4) = {Х[х2, xj}; импликация, отрицание, S$ = ( f 9, f 4) = {->, - 1 }. Заметим, что полная система функций = ( / 7, / 10, f 4) будет избыточной. Действительно, удалив из него одну из функций / 7 или / , о и выразив их с помощью законов Де Моргана через / 10 и f 4 или f 7 и f 4 соответственно, можно получить новую функциональ­ но полную систему с базисом S3 или S2 соответственно. Рассматриваемая проблема представления логических функций заключается не только в выборе минимального базиса, но и в выборе формы наиболее экономичного представления этих функ­ ций. Так, совершенные дизъюнктивные и конъюнктивные нормаль­ ные формы (СДНФ и СКНФ) менее экономичны, чем некото­ рые из ДНФ и КНФ , хотя и обладают определенными достоин­ ствами, например дают однозначное представление логической функции. Поэтому одинаково важны обе встречные проблемы: с одной стороны, минимизация булевых функций, т.е. приведение к наиболее экономичному виду, и с другой стороны — придание им совершенного вида, важного в некоторых приложениях, на­ пример для получения выводов. Уточним, что минимальной называется такая форма представ­ ления логических функций, которая содержит минимальное ко­ личество термов и переменных в термах, а значит, минимальная форма предполагает завершение процесса упрощения. Можно построить различные формальные системы — алгеб­ ры — в зависимости от выбранных в качестве базисных логиче­ ских операций. 198