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

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

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

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

В этой формуле присутствуют элементарные конъюнкции второго ряда (в ВТ называемые минтермами).

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

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

2. СКНФ – совершенная конъюнктивная нормальная форма, такая форма, в которой нет одинаковых сомножителей и все сомножители содержат одни и те же переменные, причем каждая переменная только 1 раз включает знак вхождения под знак отрицания.

Логическая функция n аргументов не равная тождественно 1 реализуется однозначно СКНФ.

Замечания.

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

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

Система булевых функций называется полной, если любая булева функция может быть

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

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

Элементарные булевы функции (дизъюнкция, конъюнкция и т.д.) в булевых функциях выполняют задание аналогичное элементарным функциям (x, x², sin, log, и т.п.) в классической математике при изучении анализа.

Определение: булевы функции (функции алгебры логики)

Пусть - исходный алфавит переменных (аргументов). Рассмотрим функции (при ), аргументы которых определены на множестве и такие, что , когда (i = 1, 2, …, n) эти функции называются функциями алгебры логики или булевыми функциями (Джордж Буль (1815-1864)).

Другое определение.

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