4.5. Свойства некоторых часто используемых логических функций
Операция (функция) Шеффера задается следующим соотношением:
Для этой функции справедливы следующие соотношения:
Для функции Шеффера свойство коммутативности справедливо лишь для случая двух переменных: х1 | x2 = х2 | x1.
Для большего числа переменных свойство коммутативности несправедливо.
Свойство дистрибутивности для функции Шеффера не применимо ни при каком числе переменных.
На основании свойств функции Шеффера можно получить формулы преобразования для функций И, ИЛИ, НЕ:
Операция (стрелка) Пирса задается следующим соотношением:
Для этой функции справедливы выражения:
На основании этих свойств можно показать, что для функции Пирса справедливо только свойство коммутативности: х ¯ y = y ¯ х.
Функции И, ИЛИ, НЕ можно выразить через функцию Пирса следующим образом:
Функция сумма по модулю 2 (логическая неравнозначность) может быть выражена следующим образом:
Для функции сумма по модулю 2 справедливы аксиомы:
Для этой функции справедливы следующие свойства:
1. Cвойство коммутативности (переместительный закон) –
2. Cвойство ассоциативности (сочетательный закон) –
3. Свойство дистрибутивности (распределительный закон) –
На основании приведенных аксиом и свойств можно указать правила преобразования функций И, ИЛИ, НЕ через сумму по модулю 2 и обратно:
Техническая задача синтеза логических схем полностью эквивалентна математической задаче представления заданной логической функции через логические функции выбранной функционально полной системы.
Любая логическая функция выражается через исходные функции неоднозначно. Поэтому следует искать такую форму представления логической функции, которая соответствует наиболее простой принципиальной логической схеме с учётом используемой функционально полной системы (набора) логических элементов.
При решении этой задачи удобно вначале найти представление заданной логической функции в некоторой исходной канонической форме, а затем, используя систему формальных правил, преобразовать исходную форму так, чтобы она соответствовала наиболее простой логической схеме с учётом выбранной функционально полной системы логических функций. Набольшее распространение получили две канонические формы представления логических функций:
· совершенная дизъюнктивная нормальная форма;
· совершенная конъюнктивная нормальная форма.