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

UptoLike

ВУЗ: 

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

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

Рубрика: 

()
()
(
)
()
(
)
1
1
,..., 1
,..., 1
n
n
n
n
f
f
x
σ
σσ
σσ
=
=
∨=
11
11 1
,..., ... ...
n
nn
fx x x x x
σ
σσ
∗
=∨∨=∨∧∧
()
()
()
(
)
11
1
1
11
,..., 0
,..., 0
... ...
nn
n
n
nn
f
f
x
xx
σσ
σσ
σσ
σσ
=
=
=∨∨=∨∧∧x∨
.
При построении СКНФ имеет место следующее
Правило нуля. Рассматриваются только те наборы аргументов, на которых функция
1
,..
()
.,
n
f
x
набора в СКНФ делается заготовка
сомножите
x
принимает значение 0; для каждого такого
ля
()
1
... ...
in
x
xx∨∨∨∨
. Если в данном наборе аргументов
0
i
x ≠
, то над перемен-
ной
i
x
в загото еле навешивается отрицание: вленном сомножит
(
)
1
... ...
ni
x
x∨∨x∨∨
.
Пример 14. Построим СКНФ для импликации: (, )
f
xy x y
=
→ . Импликация
з
прини-
мает начение 0 на одном наборе:
(1, 0) 1f
=
.
0x
и то по правилу нул получаем 0y = , я
Так как в этом наборе
(, )
f
xy x y
=
∨ .
xyx→=∨
Итак,
y
— искомая СКНФ для импликации (см. тождество 13 таблицы 3).
Замкнутые классы
Выше было показано (см. лева функция реализуется через
изъюнкцию, конъюнкцию и отрицание. Есть ли (и если есть, то какие) другие системы бу-
левы ф
Замыкание системы булевых функций
Пусть
теорему 3), что любая бу
д
ункций, обладающих тем свойством, что посредством функций системы можно выра-
зить все другие функции? Ответу на поставленный вопрос и посвящены дальнейшие рас-
смотрения.
{
}
1
,...,
k
Ff f=
— некоторая система булевых функций
in
f
P∈
.
Определение системы
F
называется множество
[]
F
, реализ над
F :
. Замыканием всех булевых
функций уемых формулами
[
]
{
[
]
}
: funcFf∈ Φ =
.
Пример 15.
n
FfP=
{
}
{
}
,
x
xx=⎡⎤
⎣⎦
. Действительно, применяя отрицание к самому себе, будем
иметь
xx=
. Таким висимости от четности числа символов отрицания в форму-
ут получаться бо
образом, в за
ле буд функции ли
x
, либо
x
.
ер 16.
{
Прим
}
{
}
1
... : 1, 2,...
k
xy x x k∧=∧∧ =⎡⎤
⎣⎦
. Действительно, в силу идемпотентно-
сти конъюнкции
x
xx∧=
, а в силу коммутативности и ассоциативности при любом нату-
м
k
(
11111
...
kk kkkk
рально
... ...
)()
1
x
x xx
−− −
∧ ∧ ∧ ∧
.
Замечани
xxxxx∧ = ∧∧ ∧ = ∧
е. Если при некотором
k
0
k
x
=
, то
k
x
1
... 0x
∧
∧=
и
1x =
. Поэтому никакая
формула
k
над системой
{
}
x
y∧
не реализует отрицание
x
: 
               f ( x1 ,..., xn ) =          ∧
                                     f ∗ (σ1 ,...,σ n ) = 1
                                                              (x
                                                               1
                                                                   σ1
                                                                                      )
                                                                        ∨ ... ∨ xnσ n =
                                                                                                (
                                                                                                     ∧ ) (x
                                                                                              f σ1 ,...,σ n = 1
                                                                                                                        σ1
                                                                                                                        1               )
                                                                                                                             ∨ ... ∨ xnσ n =

                        =
                             (
                                  ∧ ) (x
                            f σ 1 ,...,σ n = 0
                                                     1
                                                      σ1
                                                           ∨ ... ∨ xnσ n =  )             ∧
                                                                                  f (σ 1 ,...,σ n ) = 0
                                                                                                          (x
                                                                                                           1
                                                                                                               σ1
                                                                                                                                 )
                                                                                                                    ∨ ... ∨ xnσ n .


          При построении СКНФ имеет место следующее
          Правило нуля. Рассматриваются только те наборы аргументов, на которых функция
f ( x1 ,..., xn ) принимает значение 0; для каждого такого набора в СКНФ делается заготовка
сомножителя ( x1 ∨ ... ∨ xi ∨ ... ∨ xn ) . Если в данном наборе аргументов xi ≠ 0 , то над перемен-
ной xi в заготовленном сомножителе навешивается отрицание: ( x1 ∨ ... ∨ xi ∨ ... ∨ xn ) .
       Пример 14. Построим СКНФ для импликации: f ( x, y ) = x → y . Импликация прини-
мает значение 0 на одном наборе:
                                       f (1, 0) = 1 .

Так как в этом наборе x ≠ 0 и y = 0 , то по правилу нуля получаем

                                                               f ( x, y ) = x ∨ y .

Итак, x → y = x ∨ y — искомая СКНФ для импликации (см. тождество 13 таблицы 3).


                                                       Замкнутые классы
       Выше было показано (см. теорему 3), что любая булева функция реализуется через
дизъюнкцию, конъюнкцию и отрицание. Есть ли (и если есть, то какие) другие системы бу-
левы функций, обладающих тем свойством, что посредством функций системы можно выра-
зить все другие функции? Ответу на поставленный вопрос и посвящены дальнейшие рас-
смотрения.


                                   Замыкание системы булевых функций

       Пусть F = { f1 ,..., f k } — некоторая система булевых функций fi ∈ Pn .
       Определение. Замыканием системы F называется множество                                                                         [F ]   всех булевых
функций, реализуемых формулами над F :

                                              [ F ] = { f ∈ Pn :                funcΦ [ F ] = f            }.
      Пример 15. ⎡⎣{ x }⎤⎦ = { x, x } . Действительно, применяя отрицание к самому себе, будем
иметь x = x . Таким образом, в зависимости от четности числа символов отрицания в форму-
ле будут получаться функции либо x , либо x .
      Пример 16. ⎡⎣{ x ∧ y}⎤⎦ = { x1 ∧ ... ∧ xk : k = 1, 2,...} . Действительно, в силу идемпотентно-
сти конъюнкции x ∧ x = x , а в силу коммутативности и ассоциативности при любом нату-
ральном k xk ∧ ( x1 ∧ ... ∧ xk −1 ) = ( x1 ∧ ... ∧ xk −1 ) ∧ xk = x1 ∧ ... ∧ xk −1 ∧ xk .
       Замечание. Если при некотором k xk = 0 , то x1 ∧ ... ∧ xk = 0 и xk = 1 . Поэтому никакая
формула над системой { x ∧ y} не реализует отрицание x :

Страницы