Замкнутые классы логических функций

 

Рассмотрим множество А логических функций, обладающих некоторым свойством. Пусть G(Y₁,Y₂,...,Y_k)ÎA и F_i(X₁,X₂,...,X_n)ÎA, i =1,2,..., k. Произведем суперпозицию функций G и F:

G[F₁(X₁,...,X_n),...,F_k(X₁,...,X_n)] = H(X₁,...,X_n)

Если H(X₁,...,X_n)ÎA, то А называется замкнутым классом логических функций по отношению к рассматриваемому свойству.

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

1. Свойство сохранять нуль. Это свойство заключается в следующем: F(0,..,0)=0. Например, X₁X₂, X₁+X₂, X₁ Å X₂.

Примеры функций, не обладающих свойством сохранять нуль: X₁®X₂, X₁~X₂, X₁/X₂. Докажем замкнутость класса функций, сохраняющих нуль.

Пусть G(0,...,0)=0 и F_i(0,...,0)=0. Тогда G[F₁(X₁,...,X_n),...,F_k(X₁,...,X_n)] = = G[(0,...,0),...,F_k(0,...,0)]=G(0,...,0)=0, т.е. H(0,...,0)=0. Что и требовалось доказать.

2. Свойство сохранять единицу. Это свойство заключается в следующем: F(1,...,1)=1.

Например, X₁X₂, X₁+X₂, X₁®X₂.

Примеры функций, не обладающих этим свойством: X₁ Å X₂, X₁/X₂.

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

3. Самодвойственность. Введем сначала понятие двойственности. Пусть задана функция F(X₁,X₂,...,X_n). Двойственной по отношению к функции F называется функция F*, определяемая следующим образом:

F*(X₁,X₂,...,X_n)= ( ₁, ₂,..., _n).

Например, F = X + Y, тогда F*= .

Самодвойственной функцией называется такая функция, для которой справедливо равенство:

F(X₁,X₂,...,X_n)= ( ₁, ₂,..., _n).

Применив операцию отрицания к левой и правой частям последнего равенства, получим:

(X₁,X₂,...,X_n) = F( ₁, ₂,..., _n).

Пример самодвойственной функции:

F=X₁X₂+X₁X₃+X₂X₃.

Действительно,

Доказательство замкнутости класса самодвойственных функций.

Пусть (Y₁,..., Y_n) и (X₁,..., X_n)= ( ₁,..., _n). Произведем суперпозицию функций G и F_i: [F₁(X₁,..., X_n),..., F_k(X₁,..., X_n)] = G[ (X₁,..., X_n),..., (X₁,..., X_n)] = G[F₁( ₁,..., _n),...,F_к( ₁,..., _n)] = H( ₁,..., _n),

т.е. (X₁,...,X_n) = H( ₁,..., _n).

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

Если значение каждого аргумента одного набора больше или равно значению того же аргумента второго набора, то говорят, что первый набор не меньше второго. При этом предполагается, что 0 ³ 0; 1 ³ 0; 1 ³ 1.

Например, (1,1,0,1) ³ (0,1,0,1). Не всякие наборы являются сравнимыми. Например, наборы (0,1) и (1,0) или (0,1,0,1) и (1,0,1) несравнимы.

Логическая функция называется монотонной, если при любом возрастании набора значение этой функции не убывает. При этом рассматриваются только сравнимые наборы. Примеры монотонных функций: XY, X+Y, Примеры функций, не обладающих свойством монотонности: X~Y, X®Y, XÅY. Докажем, что по свойству монотонности функции образуют замкнутый класс.

Пусть функции G(Y₁,..., Y_n) и F_i(X₁,..., X_n) - монотонные. Произведем суперпозицию функций G и F:

G[F₁(X₁,..., X_n),..., F_k(X₁,..., X_n)] = H(X₁,..., X_n)

Найдем значения функций F_i и функции G на некотором наборе X₁,..., X_n, а затем увеличим этот набор. Так как функции F_i монотонные, то их значения либо увеличатся, либо останутся без изменения. Так как функция G монотонная, то ее значение либо увеличится, либо останется без изменения. Из этого следует, что значение функции Н при увеличении набора либо увеличится, либо останется без изменения, т.е. функция H тоже является монотонной, что и требовалось доказать.

5. Линейность. Логическая функция называется линейной, если она может быть представлена полиномом первой степени, т.е. записана в виде F(X₁,X₂,..., X_n) = A₀ Å

Å A₁X₁ Å A₂X₂ Å... Å A_nX_n,

где A₀, A₁,..., A_n - коэффициенты, равные нулю или единице.

Примеры линейных функций: X Å Y, X ~Y = 1 Å X Å Y..

Покажем, что по свойству линейности функции образуют замкнутый класс. Пусть функции G(Y₁,..., Y_k) и F_i(X₁,..., X_n)- линейные. Представим их в виде линейных полиномов:

G = A₀ Å A₁Y₁ Å A₂Y₂ Å... Å A_kY_k,

F_i = B_0i Å B_1i Å B_2i Å... Å B_niX_n.

Подставив функции F_i вместо аргументов Y_i в функцию G получим выражение, в котором постоянные коэффициенты A_i умножаются на линейные функции. При этом получатся снова линейные функции. Приведя подобные члены, получим функцию H(X₁,..., X_n) в виде линейного полинома.

Из этого следует, что по свойству линейности функции образуют замкнутый класс.

Рассмотрим пример. ; F₁=X₁ÅX₂ÅX₃; F₂=X₂ÅX₃; F₃=1ÅX₃. Произведем суперпозицию функций G и F_i:

G=1ÅX₁ÅX₂ÅX₃ÅX₂ÅX₃Å1ÅX₃=X₁ÅX₃.

 

­­­­­­ 3.7. Функционально полные системы