Функции алгебры логики. Стасюк В.В. - 24 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

()
x
x
ϕ
=Случай 2. . Тогда . То есть формула (1) 0
ϕ
=
ϕ
реализует отрицание
x
. На основании
есамодвойственной фулеммы о н нкции подстановкой
x
и
x
в
f
T
∗
∗
построим формулу,
реализующую
0 или 1. Если 1, то требуемая константа ре изо В противном случае 1 ал вана.
()
ϕ
==001.
0
Реализация
проводится аналогично, только вместо функции
0
f
нужно использовать
1
f
.
Этап 2. На основании леммы о немонотонной функции п дстановкой
0, 1 и
о
x
в
f
T
≤
≤
∉
построим формулу, реализующую отрицание
x
.
Этап 3. На основании леммы о нелин йне ой функции подстановкой
0, 1,
x
и
x
в
LL
f
T∉
построим формулу, реализующую конъюнкцию.
а доказана. Теорем
Дана следующая система функций:
Пример 37.
( , , ) (0100 1011)fxyz= , ( , , ) (1101 0100)gxyz
=
.
Требуется:
помощью теоремы о функциональной полноте исследовать на полноту данную
сис
и/или конъюнкцию формулами над заданной системой.
Решение. 1. Исследуем принадлежность функций данной системы важнейшим замкну-
тым
Сохранение 0 и 1. Ясно, что
1. С
тему функций.
2. Реализовать отрицание
классам
0
T
,
1
T
,
T
∗
,
T
≤
и
L
T
.
0
f
T∈
,
1
f
T
∈
,
0
gT
∉
и
1
gT
∉
.
Самодвойственность. Строим двойственные функции:
(0010 1101)
f
f
∗
=≠ и (1101 0100)gg
∗
=
=
тсюда, О
f
T
∗
∉
и .
Монотонность. Так как
gT
∗
∈
(0,0,1) 1 0 (0,1,1)ff
=
>= и то (0, 0, 0) 1 0 (1, 1, 1)gg=> = ,
f
T
≤
∉
и
gT
≤
∉
.
Линейность. Построим многочлены Жегалкина для функций данной системы:
х у z
(, ,)
f
xyz
(, ,)gxyz
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0 1 0 0 1 0 1 1
1 1 0 1 0 1 0 0
1 1 0 1 1 1 0
0 1 1 0 0 1
1 0 1 0 1
1 1 1 1
0 0 0
0 0
0
0 1 1 1 1 1 0
1 0 0 0 0 1
1 0 0 0 1
1 0 0 1
1 0 1
1 1
0
тсюда, О
(, ,)
f
xyz yz x z=⊕⊕
,
(, ,) 1g x y z xy xz yz x y
=
⊕⊕⊕⊕⊕
и, следовательно,
L
f
T
∉
,
L
gT∉
.
Сведем полученные результаты исследования в таблицу принадлежности: 
Случай 2. ϕ (1) = 0 . Тогда ϕ ( x) = x . То есть формула ϕ реализует отрицание x . На основании
леммы о несамодвойственной функции подстановкой x и x в f∗ ∉ T∗ построим формулу,
реализующую 0 или 1. Если 1, то требуемая константа 1 реализована. В противном случае
ϕ ( 0) = 0 = 1 .
Реализация 0 проводится аналогично, только вместо функции f 0 нужно использовать f1 .
         Этап 2. На основании леммы о немонотонной функции подстановкой 0, 1 и x в f ≤ ∉ T≤
построим формулу, реализующую отрицание x .
         Этап 3. На основании леммы о нелинейной функции подстановкой 0, 1, x и x в
 f L ∉ TL построим формулу, реализующую конъюнкцию.
Теорема доказана.
         Пример 37. Дана следующая система функций:

                          f ( x, y, z ) = (0100 1011) , g ( x, y, z ) = (1101 0100) .
Требуется:
      1. С помощью теоремы о функциональной полноте исследовать на полноту данную
   систему функций.
      2. Реализовать отрицание и/или конъюнкцию формулами над заданной системой.

   Решение. 1. Исследуем принадлежность функций данной системы важнейшим замкну-
тым классам T0 , T1 , T∗ , T≤ и TL .

   Сохранение 0 и 1. Ясно, что f ∈ T0 , f ∈ T1 , g ∉ T0 и g ∉ T1 .

   Самодвойственность. Строим двойственные функции:

                            f ∗ = (0010 1101) ≠ f и g ∗ = (1101 0100) = g

Отсюда, f ∉ T∗ и g ∈ T∗ .

       Монотонность. Так как              f (0, 0,1) = 1 > 0 = f (0,1,1) и g (0, 0, 0) = 1 > 0 = g (1,1,1) , то
f ∉ T≤ и g ∉ T≤ .

       Линейность. Построим многочлены Жегалкина для функций данной системы:

                            х    у    z      f ( x, y , z )     g ( x, y , z )
                            0    0    0    01001011            11010100
                            0    0    1    1101110             0111110
                            0    1    0     011001              100001
                            0    1    1     10101               10001
                            1    0    0       1111               1001
                            1    0    1        000                 101
                            1    1    0          00                 11
                            1    1    1           0                  0

Отсюда, f ( x, y, z ) = yz ⊕ x ⊕ z , g ( x, y, z ) = xy ⊕ xz ⊕ yz ⊕ x ⊕ y ⊕ 1 и, следовательно, f ∉ TL ,
g ∉ TL .

       Сведем полученные результаты исследования в таблицу принадлежности:

Страницы