Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 58 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
104
В силу критерия Поста для полноты системы F=
{
}
,...,
21
ff необхо -
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «-».
Система (множество) булевых функций называется базисом , если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
Для выделения базиса из полной системы функций
{
}
,...,,
321
fffF
=
нужно упорядочить по числу функций множество подсистем системы F:
{
}
{
}
{
}
{
}
....,,,,...,,,
312121
ffffff
и , начиная с первой, исследовать их на полноту . Первая из полных в этой
последовательности подсистем будет базисом .
Пример. Исследовать полноту системы функций
{
}
zxyyxyF →↓⊕= ;; 1 и , если она полна, выделить из нее базис.
Решение. Пусть 1
1
⊕
=
yf , zxyf
→
=
2
, yxf ↓=
3
.
Составим таблицы истинности для заданных функций:
Исследуем функцию zxyf
→
=
2
на принадлежность классам
0
T ,
1
T
,
S
,
,
L
.:
,
02
Tf
∉
т.к.
(
)
;, 100
2
=
f ,
12
Tf
∈
т.к.
(
)
;, 111
2
=
f
12
Sf
∉
, т .к. на противоположных наборах (000) и (111) функция
принимает одинаковое значение, равное 1.
12
Mf
∉
, т.к. есть предшествующие наборы, например (000)
≤
(110),
на которых
(
)
1000
2
=
,,f ,
(
)
0011
2
=
,,f , где неравенство 1
≤
0 ложное,
12
Lf
∉
,т.к.
()
.& 11
2
⊕⊕=⊕==∨=∨=→= xyxyzzxyzxyzxyzxyzxyf
Аналогично исследуем функции
1
f и
3
f на принадлежность классам
.,,,,
11110
LMSTT
Заполним таблицу
y
y
1
1
f
0 1 1 0
1 0 1 1
x y z xy
2
f
0 0 0 0 1
0 0 1 0 1
0 1 0 0 1
0 1 1 0 1
1 0 0 0 1
1 0 1 0 1
1 1 0 1 0
1 1 1 1 1
x y
y
x
∨
3
f
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
1
2
3
                                           104
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
      В силу критерия Поста для полноты системы F= {f 1 , f 2 ,...} необхо-
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «-».
      Система (множество) булевых функций называется базисом, если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
              1                               2                                 3

   y      y       1    f1            x    y       z   xy   f2        x      y       x∨y      f3
   0      1       1    0             0    0       0   0    1
   1      0       1    1             0    0       1   0    1         0      0        0       1
                                     0    1       0   0    1         0      1        1       0
                                     0    1       1   0    1         1      0        1       0
                                     1    0       0   0    1         1      1        1       0
                                     1    0       1   0    1
                                     1    1       0   1    0
                                     1    1       1   1    1

      Для выделения базиса из полной системы функций F ={f 1 , f 2 , f 3 ,...}
нужно упорядочить по числу функций множество подсистем системы F:
                      {f 1 }, {f 2 }, ...,{f 1 , f 2 }{
                                                      , f1 , f 3 }, ... .
и, начиная с первой, исследовать их на полноту. Первая из полных в этой
последовательности подсистем будет базисом.

    Пример.         Исследовать        полноту     системы        функций
F ={y ⊕ 1; x ↓ y; xy → z} и, если она полна, выделить из нее базис.
        Решение. Пусть f 1 = y ⊕ 1 , f 2 = xy → z , f 3 = x ↓ y .
        Составим таблицы истинности для заданных функций:
        Исследуем функцию f 2 =xy → z на принадлежность классам T0 ,
T1 , S , M , L .:
         f 2 ∉T0 , т.к. f 2 (0,0 ) =1; f 2 ∈T1 , т.к. f 2 (1,1) =1;
         f 2 ∉ S 1 , т.к. на противоположных наборах (000) и (111) функция
принимает одинаковое значение, равное 1.
         f 2 ∉M 1 , т.к. есть предшествующие наборы, например (000) ≤(110),
на которых f 2 (0,0,0 ) =1 , f 2 (1,1,0 =0 ),где неравенство 1 ≤0 ложное,
f 2 ∉L1 ,т.к. f 2 = xy → z = xy ∨ z = xy ∨ z = xy & z = xy (z ⊕ 1) = xyz ⊕ xy ⊕ 1.
         Аналогично исследуем функции f 1 и f 3 на принадлежность классам
T0 , T1 , S 1 , M 1 , L1 .
         Заполним таблицу

Страницы