 |
Элементарные функции алгебры логики
|
|
|
|
ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ
Обозначения: E 2={0,1}; Е 
= E 2´ E 2´...´ E 2 – прямое произведение n сомножителей; (x 
,.., xn)Î E 2, | E 2| – мощность E 2, | E 2|=2, тогда | Е 
|=2 n.
Определение 1. Функцией алгебры логики называется закон, осуществляющий отображение Е 
E 2, причем отображение всюду определено и функционально.
Так как множество Е 
конечно, то задать отображение Е Þ E 2, означает задать множество наборов из Е и для каждого набора указать его образ в Е 2.
Пример 1. Пусть n =2, тогда Е 
={(0 0),(0 1),(1 0),(1 1)}, отображение Е Þ E 2 задано, например, так: (0 0) Þ0; (0 1) Þ1; (1 0) Þ1; (1 1) Þ1.
| x 1 x 2 | f 0 | f 1 | f 2 | f 3 | f 4 | f 5 | f 6 | f 7 | f 8 | f 9 | f 10 | f 11 | f 12 | f 13 | f 14 | f 15 |
| 0 0 0 1 1 0 1 1 |
Некоторые из этих функций носят специальные названия и играют такую же роль, как элементарные функции в анализе, поэтому называются элементарными функциями алгебры логики. Перечислим их.
1) f 1(x 1, x 2) = (x 1& x 2), читается «конъюнкция х 1 и х 2», иногда вместо знака & употребляют знак 
или вообще его опускают, пишут (х 1 х 2). (х 1& х 2) совпадает с обычным произведением х 1 х 2 и совпадает с min(x 1, x 2). Эту операцию называют также логическим умножением.
2) f 6(x 1, x 2) = (x 1Å x 2) – сложение х 1 и х 2 по модулю два, иногда пишут (х 1+ х 2) mod 2.
3) f 7(x 1, x 2) = (x 1Ú x 2), читается «х 1 дизъюнкция х 2», она совпадает с max(x 1, x 2), ее называют логическим сложением.
4) f 8(x 1, x 2) = (x 1 
x 2), читается «х 1 стрелка Пирса х 2» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.
5) f 9(x 1, x 2) = (x 1~ x 2), читается «х 1 эквивалентно х 2».
6) f 13(x 1, x 2) =(x 1 
x 2), читается «х 1 импликация х 2», иногда обозначается (х1Éх2), т. е. х1 влечет х2.
7) f 14(x 1, x 2) = (x 1| x 2), читается «х 1 штрих Шеффера х 2», она является отрицанием конъюнкции.
|
|
|
Рассмотрим функции f (x 1... xn), где (x 1... xn)Î Е 
, тогда число наборов (x 1... xn),где функция f (x 1... xn) должна быть задана, равно | Е |=2 n. Обозначим множество всех функций двузначной алгебры логики Р 2. Обозначим через Р 2(n) число функций, зависящих от n переменных. Очевидно, Р 2(n)=22 n.
Определение 3. Функция f (x 1,..., xi –1, xi, xi +1,..., xn) существенно зависит от хi, если существуют такие значения a 1,... ai –1, ai +1,... an переменных x 1,... xi –1, xi +1,... xn, что f (a 1,... ai –1, 0, ai +1... an)¹ f (a1... ai –1, 1, ai +1... an). Тогда переменная хi называется существенной переменной. В противном случае хi называется фиктивной переменной.
Определение 1. Пусть М Ì P 2, тогда:
1) каждая функция f (x 1,..., x n)Î M называется формулой над M;
2) пусть g (x 1,..., xm)Î M, G 1,..., Gm – либо переменные, либо формулы над M. Тогда выражение g (G 1... Gn) – формула над M.
Формулы будем обозначать заглавными буквами: N [ f 1,..., fs ], имея в виду функции, участвовавшие в построении формулы, или N (х 1,..., xk) имея в виду переменные, вошедшие в формулу. Gi – формулы, участвовавшие в построении g (G 1,..., Gn), называются подформулами.
Пример 1. Пусть N ={(x 1& x 2),(x 1Ú x 2),(` x)}, тогда ((х 1& х 2)Ú х 3) – формула над N.
Сопоставим каждой формуле N (x 1,..., xn) функцию f (x 1,..., xn)Î P 2. Сопоставление будем производить в соответствии с индуктивным определением формулы.
1) Пусть N (x 1,..., xn)= f (x 1,..., xn), тогда формуле N (x 1,..., xn) сопоставим функцию f (x 1,..., xn).
2) Пусть N (x 1,..., xn)= g (G 1,..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fi Î P 2, либо переменная хi, которую можно считать тождественной функцией. Таким образом, каждой формуле Gi сопоставлена функция fi (
), причем:{ 
}Í{ x 1,..., x n}, т.к. в формуле N (x 1,..., xn) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x 1,..., xn), причем какие-то переменные могут быть фиктивными. Тогда N (x 1,..., xn) = g (G 1,..., Gm) = g (f 1(x 1,..., xn),..., fm (x 1,.., xn)). Сопоставим этой формуле функцию h (x 1,..., xn) следующим образом: пусть (a 1,..., an) – произвольный набор переменных (x 1,..., xn). Вычислим значение каждой функции fi на этом наборе, пусть f (a 1,..., an)= bi, затем найдем значение функции g (x 1,..., xm) на наборе (b 1,..., bm) и положим h (a 1,..., an) = g (b 1,..., bm) = g (f 1(a 1,..., an),..., fm (a 1,..., an)). Так как каждое fi (x 1,..., xn) есть функция, то на любом наборе (a 1,..., an) она определяется однозначно, g (x 1,..., xm) – тоже функция, следовательно, на наборе (b 1,..., bn) она определяется однозначно, где h (x 1,..., xn) есть функция, определенная на любом наборе (a 1,..., an).
|
|
|
Множество всех формул над M обозначим через < M >.
|
|
|
