г) Функции n переменных. Алгебра исчисления высказываний

Подобно тому как в рассмотренном примере совершенная нормальная дизъюнктивная форма (1.13) определяла функцию, для которой была возможна и более короткая запись (1.11), и в иных случаях также возможны более короткие и удобные записи функций, чем с помощью совершенной дизъюнктивной нормальной формы. Иначе говоря, не только в рассмотренном примере, но и в иных случаях могут быть установлены тождества, подобные тождеству (1.14).

До сих пор для доказательства того или иного тождества, устанавливаемого в области функций одного, двух или более независимых переменных, мы проверяли предполагаемое тождество подстановкой всех возможных значений независимых перемейных. Этот способ имеет два существенных недостатка. Во-первых, он не дает возможности получать новые тождества и в этом смысле является пассивным и, во-вторых, его трудоемкость резко возрастает с ростом количества независимых переменных.

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

такую систему правил, обычно называемую алгеброй логики или алгеброй Буля, образуют следующие тождества:

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

Участвующие в этой алгебре операции ИЛИ и И имеют много общего с операциями сложения и умножения обычной алгебры. Относительно этих операций имеют силу первый и второй переместительные законы (тождества (1.24)), первый и второй сочетательные законы (тождества ). Но в отличие от обычной алгебры здесь действует не один, а два распределительных закона (тождества ). По сравнению с обычной алгеброй «приведение подобных членов» или «умножение переменной самой на себя» осуществляется здесь согласно тождествам (1.19), без появления каких бы то ни было коэффициентов или показателей степени.

Применяя приведенную систему тождеств, мы получаем возможность чисто аналитическим путем решать разнообразные задачи, причем для некоторых из них могут быть указаны регулярные методы. Так, например, функцию, заданную любым аналитическим выражением, можно непосредственно преобразовать к нормальной дизъюнктивной форме. Методику такого приведения рассмотрим на примере.

Пример. Пусть исследуемая функция задана в форме

Прежде всего необходимо исключить символы и Применяя тождества (1.17) и (1.18), получаем

Далее нужно избавиться от тех знаков отрицания, которые относятся не к одной какой-нибудь независимой переменной, а к целому комплексу. Для этого применяются тождества (1.23). В нашем случае, применяя попутно также и тождество (1.16), имеем

Теперь для получения нормальной дизъюнктивной формы достаточно выражение в фигурных скобках развернуть в соответствии с тождеством (1.26, а). При этом, применяя попутно (1.16) и (1.19, а), получим

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

Таким образом,

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

Полученная нормальная форма (1.32) не является совершенной из-за того, что во втором дизъюнктивном члене встречаются не все независимые переменные: в нем нет .

Легко видеть, что имеет место тождество

Заменяя в исходной нормальной форме (1.32) второй дизъюнктивный член двумя тождественными ему дизъюнктивными членами, получаем

— совершенную нормальную дизъюнктивную форму записи заданной функции.

Конечно, если бы в результате таких преобразований мы пришли к выражению, содержащему несколько одинаковых дизъюнктивных членов, то в окончательной записи мы сохранили бы лишь один член.

Приведение к нормальной конъюнктивной форме отличается от рассмотренного приема приведения к нормальной дизъюнктивной форме лишь на последнем этапе, где вместо развертывания выражения, полученного на предыдущих этапах, в соответствии с тождеством (1.26, а) применяется второй распределительный закон — тождество .

При приведении к совершенной нормальной конъюнктивной форме также сначала приводят функцию к какой-нибудь нормальной конъюнктивной форме, а затем поступают так, как будет показано на примере.

Пример. Пусть функция трех независимых переменных, приведенная к нормальной конъюнктивной форме, имеет вид

Для того чтобы эту нормальную форму сделать совершенной, обратимся к очевидным тождествам

Пользуясь этими тождествами, получим

совершенную нормальную конъюнктивную форму представления исходной функции.

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

Если же функция задана таблицей и по ней описанным приемом может быть однозначно выписана совершенная нормальная дизъюнктивная форма, то, подвергая затем эту форму тождественным преобразованиям, можно для той же функции определить иные формы аналитической записи. В таких условиях возникают разнообразные задачи определения наиболее выгодной с какой-нибудь точки зрения формы записи заданной функции.