Функционально полные системы функций.
Запишем таблицу функций 1-й перем.:
x | y1 | y2 | y3 | y4 |
y1 – функция константы О ;
y2 – переменная х ;
y3 – отриц. переменная х ;
y4 – конст-ты 1.
Для алгебры с двузначной логикой составим аналогичную таблицу всех возможных функций.
х1 | х2 | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 |
Некоторые из этих функций встречались ранее :
F1(x1, x2) = x1 * x2 - дизъюнкция
F6(x1, x2) = x1 Å x2 - слож. по модулю 2
F7(x1, x2) = x1 x2 - конъюкция
Сведем в таблицу :
Функция | Название | Предназначение |
F0 | конст-та 0 | Æ |
F1 | конъюкция | Логич. умнож. х1х2 |
F2 | отрицание по х2 | х1 ![]() |
F3 | повт-ль х1 | х1 |
F4 | запрещение по х1 | ![]() |
F5 | повт-ль х2 | х 2 |
F6 | сумма по mod 2 | х1Åх2 |
F7 | дизъюнкция | логич. сложен. х1 ![]() |
F8 | стрелка Пирса | х1 ¯ х2 |
F9 | эквив-ти | х1 ~х2 |
F10 | отрицание х2 | ![]() |
F11 | импликация по х2 | х2®x1 |
F12 | отрицание х1 | ![]() |
F13 | импликация по х1 | x1 ® х2 |
F14 | отр. конъюкции | ![]() ![]() |
F15 | конст-та 1 |
Функционально-полной системой алгебры Буля – набор функций Рк, с помощью которых может быть выраженна любая функция из Рк.
Тривиальной функционально-полной системой является весь набор функций из Рк.
Базисом алгебры Буля называется функционально-полная система, которая перестает быть таковой при выбрасывании из неё любой функции.
Примером алгебры с функционально-полной системой, но не являющейся базисом является функция вида :
А = < M, , &, - >
На основании законов де Моргана из неё можно получить алгебры с базисами.
А1 = < M, , - > , А2 = < M, &, - >
Принцип нахождения функционально-полных систем и базисов для Рк .
Будем искать такой набор из Рк, с помощью которого можно представить функции дезъюнкции, конъюкции, отрицания, а следовательно и все остальные функции. Для изучения свойств пространства Р2 , т. е. Функция от двух переменных, представим все функции с помощью операций дезъюнкции, конъюкции и отрицания.
F1 = х1*х2 |
F2 = х1* ![]() |
F4 = ![]() |
F6 = х1Åх2 = ![]() ![]() ![]() |
F7 = х1 ![]() |
![]() ![]() ![]() ![]() ![]() ![]() |
![]() ![]() ![]() ![]() |
F10 = ![]() |
F11 = ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
F12 = ![]() |
F13 = 1
2
1х2
х1х2 =
1
х2
F14 = 1
2
1х2
х1
2 =
1
2 =
1
2
Для каждой из перечисленных функций существует двух ходовой логический элемент.
Изобразим эти элементы.
F1 = x1x2 F2 = x1 2 F4 =
1x2
x1 x1 x1
x2 & y1 x2 & y2 x2 & y4
F6 = х1Åх2 F7 = х1
х2 F8 =
1
2
x1 x1 x1
x2 y6 x2 1 y7 x2 1 y8
F9 = х1Åх2 F10 =
2 F11 = x1
2
x1 x1 x1
x2 y9 x2 1 y10 x2 1 y11
F12 = 1 F13 =
1
х2 F14 =
1
2
x1 x1 x1
x2 1 y12 x2 1 y13 x2 & y14
На основании этих элементов можно синтезировать любую логическую функцию.
f(х1,х2,х3) = х1х2х3
1х2
х1
2
1
2
3
02 07
x1 00 1
x2 01 & 03 04 12
04 05 09 1
x3 02 & 06 & 08 09 1 14 f
00 1 07 &
05 10 10
01 01 & 11 1
1 00
& 11
06
Реализуем функцию вида f(х1,х2,х3):
![]() | |||||
![]() | ![]() |
f(х1,х2,х3) = х1 2х3 &
1х3
x1 00 04
x2 01 & 03 04 1 06
x3 02 & 04
& 08 1 f 09
05 07
& 05 05 1
![]() | ![]() |
f(х1,х2,х3) = х1 2х3
1х3 =
1
х2
3
x1
3
x1 00 00
x2 01 00 1 03 03 1 05
x3 02 01
04 1 06
08
02 00 1 10 f
02 1 04 04 1 07 1 09
СВОЙСТВА БУЛЕВЫХ ФУНКЦИЙ.
Функциональным классом называется множество всех функций, обладающих определенным свойством.
Функциональный класс замкнутый,если суперпозиция этого класса принадлежит этому же классу.
Например, класс функций, полученных с помощью дизъюнкции аргументов замкнут.
y(x1,x2) = x1 x2 ,где x2(z1,z2) = z1
z2
y(x1,x2(z1,z2)) = y(x1,z1,z2) = x1 z1
z2
Перечислим некоторые свойства. Для булевой функции определим понятие набора.
Набор – фиксируемое значение аргументов функции d, t d = {0110}
Между различными наборами установим соотн. сравнения:
d1 > d2 , если любой элемент набора d1 ³ соответственно элементу из набора d2
d1 = (11010)
d2 = (01010) Þ d1 > d2
t1 = (01001)
t2 = (10100) Þ 2 набора несравнимы
d = (d1, d2, …,dn)
t = (t1, t2, …,tn) наборы знач. перем. знач. и считается d > t , если di > ti
ТЕОРЕМА.
Если булева функция может быть представлена в нормальной дизъюктивной форме без отрицания, то эта функция монотонна.
ДОКАЗАТЕЛЬСТВО.
Возьмем произвольные значения d и t, причем d £ t. В этом случае условию теоремы удовлетворяют следующие возможности:
у( d ) = 0 , у ( t ) = 0
у( d ) = 0 , у ( t ) = 1
у( d ) = 1 , у ( t ) = 1
Откуда следует, что для доказательства теоремы достаточно доказать следующее утверждение:
если d £ t, то у ( d ) = 1 у ( t ) = 1
Докажем это утверждение.
Если у( d ) = 1, то всегда найдется интервал, для которого выполняется следующее условие:
xj1, xj2 … xjk|d = 1, где dj1 = dj2 = djk = 1
j - номер набора перем.без отрицания, тогда
tj1 = tj2 = tjk = 1 Þ xj1, xj2 … xjk|t = 1
значит у( t ) = 1
Следствием теоремы является замкнутость класса монотонных функций.
Например:
y(х1,х2,х3) = х1х2 х1х3
х2х3 , где х2(z1,z2) = z1
z2
тогда: y(x1,x2(z1,z2)x3) = x1(z1 z2)
x1x3
x3(z1
z2) =
= x1z1 x2z2
x1x3
x3z1
x3z2
Так как результирующая функция не содержит отрицания, то она является монотонной.