2.3.4. Подстановки и замены

Если в формулу F входит переменная х, то этот факт обозначается так: F(...x...).

Соответственно запись F(...G..) обозначает, что в формулу F входит подформула G. Можно вместо x и G подставить другую формулу или переменную.

Если подстановка производится вместо всех вхождений заменяемой переменной (или подформулы), то результат подстановки обозначается так:

F(...x...){G//x}.

Если же подстановка производится вместо некоторых вхождений (в том числе вместо одного), то результат подстановки обозначается так:

F(...G₁...){G₂/G₁}.

Пример 1. Замена всех вхождений переменной х

xv¬x{y^z//x} = (y^z)v¬(y^z).

2. Замена всех вхождений подформулы:

xvyvz{¬x//yvz} = xv¬x.

3. Замена первого вхождения переменной:

xv¬x{y/x} = yv¬x.

4. Замена первого вхождения подформулы:

xvyvz{¬x/yvz} = xv¬x.

Правило подстановки: если в равносильных формулах вместо всех вхождений некоторой переменной х подставить одну и ту же формулу, то получатся равносильные формулы:

.

2.3.5. Принцип двойственности

Понятие двойственных функций

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

Определение 1. Функция f⁺(x₁, ...,x_n), двойственная к функции f(x₁, ...,x_n), определяется равенством:

f⁺(x₁, ...,x_n) = .

Из определения видно, что двойственность инволютивна: f⁺⁺ = f.

Определение 2. Функция, равносильная своей двойственной, т.е. такая, что

f(x₁, ...,x_n) = f⁺(x₁, ...,x_n) = ,

называется самодвойственной.

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

f	1	0	x1vx2	x1^x2	x
f*	0	1	x1^x2	x1vx2	x

Пример 1.

Пример 2. Тождественная функция и отрицание самодвойственны, а дизъюнкция и конъюнкция – нет.

Теорема. Если функция φ(х_1­...х_n) реализована формулой

f(f₁(x₁, ...,x_n), ..., f_n(x₁, ...,x_n)), то формула реализует функцию φ^*(х_1­...х_n).

Доказательство. φ^*(х_1­...х_n) = =

=

= =

= = .

Теорема (Принцип двойственности).

Пусть F = {f₁, ..., f_m}. Положим F^* = {f₁^*, ..., f_m^*}.

Тогда, если формула F над базисом F реализует функцию f, то формула F* над базисом F* полученная из формулы F заменой функций f на двойственные функции f^*, реализует функцию f*:

funcF[F]=f => funcF*[F*] = f*, где F*[F*] = F[F]{f_i*//f_i}

Короче: Функция, двойственная суперпозиции некоторых функций, равносильна соответствующей суперпозиции двойственных функций.

Следствие: F₁ = F₂ => F₁* = F₂*.

Пример: Из по принципу двойственности сразу имеем .

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

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

Примеры.

A. Дать определение несамодвойственной функции.

Функция является несамодвойственной, если существует такой набор , что .

B. Дана произвольная несамодвойственная функция. Отождествить у нее переменные так, чтобы получилась несамодвойственная функция от возможно меньшего числа переменных. Каким может быть это число?

Пусть f(x₁, ..., x_n) – несамодвойственная функция, тогда для набора имеем

. (*)

Разобьем переменные (x₁, ..., x_n) на две группы:

1) сюда включим те переменные x_i, для которых .

2) сюда – остальные переменные (для которых 0).

Отождествим между собой переменные первой группы (переименуем их в у₁), а так же переменные второй группы (переименуем их в у₂).

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

Очевидно, что

и =

Поэтому, в силу (*), отсюда следует, что

,

а значит, - несамодвойственная функция.

Может оказаться, что дальнейшее отождествление переменных с сохранением несамодвойственности невозможно.

Например, ху – несамодвойственная функция, а единственно возможное отождествление переменных приводит к самодвойственной функции х.

C. Доказать, что из произвольной несамодвойственной функции и отрицания суперпозицией можно получить константы 0 и 1.

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

.

Тогда рассмотрим функцию . Эта функция является суперпозицией и . Так как , то . Отождествим у переменные х и у: . Имеем , т.е. . Подставляя эту координату в , получим другую константу. Таким образом, представлены в виде суперпозиции и обе константы 1 и 0.

Эти задачи используются в последствии при доказательстве теоремы Поста.