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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Пусть
1
( ,..., )
nn
f
xxP
∈
— булева функция.
ление. ФункцОпреде ия
11
( ,..., ) ( ,..., )
nn
fx x fx x
∗
=
,
азывается двойственной к функциин
f
. Из определения видно, что двойственность инволю-
тивна:
f
f
∗∗
= , то есть свойство двойственности взаимно.
Для еделения значений двойственной функции опр
f
∗
используют следующее
Правило. Значения двойственной функции
f
∗
можно получить из значений функции
f
переписыванием последних в обратном порядке дновременным их инвертированием.
Пример 6. Пусть (, )
с о
f
xy x y=∨ — дизъюнкция. Тогда ( , ) ( 0111 )fxy= и, применяя
правил
=
о 1, находим
(fx
∗
, что соответствует кон ), ) ( 0001 )y ъюнкции: (,
f
xy x y=∧. Та-
ким образом,
()
∗
y
∗
∨
xy=∧
.
Таблица 4
f
0
x
∧
y
x
⊕ y
x
∨
y
x
y↓
x
≡
y x
x
/
x
y
1
f
∗
1
x
∨
y x y
≡
x
∧
y
/
x
y
x
⊕
y
x
x
x
y↓
0
Определение. Функция называется самодвойственной, если
f
f
∗
=
.
Пример 7. Самодвойственными являются тождественная функция и отрицание (см.
таблицу 4):
(01) (01)
x
x
∗∗
=== и (10) (10)
x
x
∗∗
=
==.
Пример 8. Самодвойственной является функция голосования:
(, ,)
f
xyz xy xz yz=∨∨
.
Действ
=
. Примительно, составляя таблицу для этой функции, имеем
( , ,fxyz
е-
) (0001 0111)
няя правило 1, находим
( , , ) (0001 0111) ( , , )
f
xyz f xyz
∗
==.
Теорема 1. Если функция
1
( ,..., )
n
f
xx
реализована формулой
()
11 1
( ,..., ),..., ( ,..., )
nn n
x
xxx
ϕϕ ϕ
,
то формула
()
11 1
( ,..., ),..., ( ,..., )
nn n
x
xx
ϕϕ ϕ
∗∗ ∗
x
реализует функцию
1
( ,..., )
n
f
xx
∗
.
Доказательство.
(
)
11 11 1
( ,..., ) ( ,..., ) ( ,..., ),..., ( ,..., )
nn nn
fxx fxx xx xx
ϕϕ ϕ
∗
==
n
=
()
(
)
11 1 1 1 1
( ,..., ),..., ( ,..., ) ( ,..., ),..., ( ,..., )
nn n nn n
xx xx xx xx
ϕϕ ϕ ϕϕ ϕ
∗∗
== =
()
11 1
( ,..., ),..., ( ,..., )
nn n
x
xx
ϕϕ ϕ
∗∗ ∗
= x
.
з доказанной теоремы немедленно вытекает И
       Пусть f ( x1 ,..., xn ) ∈ Pn — булева функция.
       Определение. Функция
                                           f ∗ ( x1 ,..., xn ) = f ( x1 ,..., xn ) ,

называется двойственной к функции f . Из определения видно, что двойственность инволю-
тивна: f ∗∗ = f , то есть свойство двойственности взаимно.
      Для определения значений двойственной функции f ∗ используют следующее
      Правило. Значения двойственной функции f ∗ можно получить из значений функции
 f переписыванием последних в обратном порядке с одновременным их инвертированием.
      Пример 6. Пусть f ( x, y ) = x ∨ y — дизъюнкция. Тогда f ( x, y ) = ( 0111 ) и, применяя
правило 1, находим f ∗ ( x, y ) = ( 0001 ) , что соответствует конъюнкции: f ∗ ( x, y ) = x ∧ y . Та-
ким образом, ( x ∨ y ) = x ∧ y .
                           ∗




                                                                                                        Таблица 4
                      f        0     x ∧y x ⊕ y x ∨ y                 x↓ y          x≡y x           x   x/ y 1
                      f∗       1     x ∨ y x ≡ y x ∧y                 x/ y          x⊕ y x          x   x↓ y 0

       Определение. Функция называется самодвойственной, если

                                                                f∗ = f .

      Пример 7. Самодвойственными являются тождественная функция и отрицание (см.
таблицу 4):
                     x∗ = (01)∗ = (01) = x и x ∗ = (10)∗ = (10) = x .

      Пример 8. Самодвойственной является функция голосования: f ( x, y, z ) = xy ∨ xz ∨ yz .
Действительно, составляя таблицу для этой функции, имеем f ( x, y, z ) = (0001 0111) . Приме-
няя правило 1, находим f ∗ ( x, y, z ) = (0001 0111) = f ( x, y, z ) .

       Теорема 1. Если функция f ( x1 ,..., xn ) реализована формулой

                                            ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) ) ,
то формула
                                            ϕ ∗ (ϕ1∗ ( x1 ,..., xn ),..., ϕn∗ ( x1 ,..., xn ) )
реализует функцию
                                                            f ∗ ( x1 ,..., xn ) .
Доказательство.
                       f ∗ ( x1 ,..., xn ) = f ( x1 ,..., xn ) = ϕ (ϕ1 ( x1 ,..., xn ),..., ϕ n ( x1 ,..., xn ) ) =

                                                                          (
                 = ϕ (ϕ1 ( x1 ,..., xn ),..., ϕn ( x1 ,..., xn ) ) = ϕ ϕ1∗ ( x1 ,..., xn ),..., ϕn∗ ( x1 ,..., xn ) = )
                                          = ϕ ∗ (ϕ1∗ ( x1 ,..., xn ),..., ϕn∗ ( x1 ,..., xn ) ) .

Из доказанной теоремы немедленно вытекает

Страницы