в) Функции n переменных. Конъюнктивные и дизъюнктивные нормальные формы

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

определяется значениями трех независимых переменных.

Для функции независимых переменных может быть составлена характеризующая ее таблица. Для заполнения ее поочередно рассматриваются все возможные сочетания значений (т. е. все точки -мерного логического двоичного пространства с соответствующими номерами k) и определяются значения у в этих точках. Так, например, в случае функции (1.11) в точке , т. е. при , имеем . Подсчитывая так же у для всех значений заполняем таблицу функции (1.11) (см. табл. 1.11).

таблица 1.11.

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

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

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

принимающие значения 1 только в точках с номерами , т. е. во всех тех точках, где в табл. .

Функция принимает значение 0 тогда и только тогда, когда в остальных же случаях у . Так как «остальными случаями» являются точки , то это значит, что функция

в точности соответствует исходной табл. 1.11. Аналитическое выражение для функции, заданной табл. 1.11, мы получили не в форме выражения (1.11), а в некоторой иной «стандартной» форме.

Несмотря на заметное внешнее различие между (1.11) и , оба эти выражения соответствуют одной и той же функции, определенной таблицей 1.11, то есть имеет место тождество

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

Таблица 1.12

Обратим внимание на какой-либо столбец, для которого , и, выписав конъюнкцию всех независимых переменных , проставим знак отрицания над теми из них, которые в рассматриваемом столбце таблицы имеют значение 0. Составив такие конъюнкции для всех столбцов, где соединим их знаками дизъюнкций.

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

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

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

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

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

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

Это свойство является непосредственным следствием тождеств (1.8).

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

Продемонстрируем важное значение введенных понятий на примерах решения двух задач.

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

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

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

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

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

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

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

где равно 0 или 1 в зависимости того, входит ли соответствующая независимая переменная в рассматриваемую конъюнктивную скобку со знаком отрицания или без него.