Дискретная математика. Сергиевская И.М. - 10 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

10
принадлежности булевой функции классу L осуществляется
путем построения полинома Жегалкина. Здесь
)(
2
nP
– мно-
жество всех булевых функций
n переменных.
Функциональная полнота.
Система булевых функций называется функционально
полной, если любая булева функция представляется супер-
позицией (сложной функцией) функций данной системы.
Теорема Поста. Система булевых функций функ-
ционально полна, если она не содержится целиком ни в одном
из пяти замкнутых классов.
Для проверки функциональной полноты системы буле-
вых функций строится так называемая таблица Поста, в которой
отмечается принадлежность функций замкнутым классам. Если
в каждом столбце таблицы Поста есть хотя бы один минус,
система
полна, в противном случае – нет.
Пример. Проверить функциональную полноту системы булевых
функций
{}
1,, yxyxA
∧
⊕= .
Проверим принадлежность замкнутым классам функции
yxyxf ⊕
=
),(. Построим таблицу истинности данной функции.
x
y
yx
⊕
0 0 0
0 1 1
1 0 1
1 1 0
0)0,0(
=
f , следовательно
0
),( Tyxf
∈
.
0)1,1(
=
f , следовательно
1
),( Tyxf
∉
.
=
)0,0(f )1,1(f , следовательно, Syxf
∉
),(.
)1,1(01)0,1(
ff =>
=
, следовательно, Myxf
∉
),(.
Функция представляет собой полином Жегалкина первой
степени, следовательно,
Lyxf
∈
),(. 
принадлежности булевой функции классу L осуществляется
путем построения полинома Жегалкина. Здесь P2 (n) – мно-
жество всех булевых функций n переменных.

Функциональная полнота.
           Система булевых функций называется функционально
полной, если любая булева функция представляется супер-
позицией (сложной функцией) функций данной системы.
            Теорема Поста. Система булевых функций функ-
ционально полна, если она не содержится целиком ни в одном
из пяти замкнутых классов.
            Для проверки функциональной полноты системы буле-
вых функций строится так называемая таблица Поста, в которой
отмечается принадлежность функций замкнутым классам. Если
в каждом столбце таблицы Поста есть хотя бы один минус,
система полна, в противном случае – нет.
Пример. Проверить функциональную полноту системы булевых
функций A = {x ⊕ y, x ∧ y,1} .
           Проверим принадлежность замкнутым классам функции
 f ( x, y ) = x ⊕ y . Построим таблицу истинности данной функции.
        x          y          x⊕ y
        0          0            0
        0          1            1
        1          0            1
        1          1            0
 f (0,0) = 0 , следовательно f ( x, y ) ∈ T0 .
 f (1,1) = 0 , следовательно f ( x, y ) ∉ T1 .
 f (0,0) = f (1,1) , следовательно, f ( x, y ) ∉ S .
 f (1,0) = 1 > 0 = f (1,1) , следовательно, f ( x, y ) ∉ M .
Функция представляет собой полином Жегалкина первой
степени, следовательно, f ( x, y ) ∈ L .


                               10

Страницы