Математическая логика и теория алгоритмов. Стенюшкина В.А. - 11 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

).∧∧(∨)∧∧(∨)∧∧(∨)∧∧(
321
32
1
3
2
1
3
21
xxxxxxxxxxxx
);xxx()xxx()xxx()xxx(
3
213
2
132
1321
∨∨∧∨∨∧∨∨∧∨∨
Взяв отрицание от обеих частей (2.3) и проведя тождественные преобра-
зования, получим:
f(x
1
,…x
n
)=
∧
(
δ
1,…,
δ
n)
(f(
δ
1,…,
δ
n)
∨
x
1
δ
1
∨
…x
n
δ
n
) (2.4)
Если f(x
1
,…, x
n
) ≢ 1, то справедливо тождество:
)x...x()x,...,x(f
n
n
n
),...,(
n
δ
δ
=δδ
∨∨∧≡
1
1
1
0)
n
д,...,
1
f(д
1
(2.5)
Выражение в правой части (2.5) является совершенной конъюнктивной
нормальной формой. Существование совершенной конъюнктивной нормальной
формы доказано. Единственность также имеет место. Теорема дает способы по-
строения совершенной нормальной формы.
Пример –Пусть булева функция y=f(x
1
,x
2
,x
3
) задана таблицей 1.5.
Таблица 1.5
x
1
x
2
x
3
0 0 0 0
0 0 1 1
0 1 0 1
1 1 1 1
0 0 1 1
0 1 0 1
Y 0 1 1 0 1 0 0 1
Тогда СДНФ и СКНФ – имеют соответственно вид:
Следствие Любая булева функция выразима через функции:
,
∧
,
∨
.
Функциональная полнота
Система функций называется полной в некотором множестве, если лю-
бая функция этого множества может быть представлена суперпозицией функ-
ций из указанной системы.
Примеры полных систем в множестве булевых функций:
1
)
,
∧
,
∨;
2)
,
∧;
3)
,
∨;
4)↓;
5)
⁄
.
Две последние системы содержат по одной функции, которые называю-
тся соответственно Стрелка Пирса и Штрих Шеффера. Имеют место равенства: 
      Взяв отрицание от обеих частей (2.3) и проведя тождественные преобра-
зования, получим:

      f(x1,…xn)= ∧ (δ1,…,δn) (f(δ1,…,δn)∨ x1δ1∨…xnδn)                                           (2.4)

      Если f(x1,…, xn) ≢ 1, то справедливо тождество:

                                                                      δ                δn
       f ( x1 ,..., x n ) ≡ ∧ ( δ                                 ( x1 1 ∨ ... ∨ x n        )      (2.5)
                                1 ,...,δ n ) f(д1 ,...,дn ) = 0



      Выражение в правой части (2.5) является совершенной конъюнктивной
нормальной формой. Существование совершенной конъюнктивной нормальной
формы доказано. Единственность также имеет место. Теорема дает способы по-
строения совершенной нормальной формы.
      Пример –Пусть булева функция y=f(x1,x2,x3) задана таблицей 1.5.

      Таблица 1.5

      x1                                            0000                                         1111
      x2                                            0011                                         0011
      x3                                            0101                                         0101
      Y                                             0110                                         1001

      Тогда СДНФ и СКНФ – имеют соответственно вид:
                ( x1 ∨ x2 ∨ x3 ) ∧ ( x1 ∨ x 2 ∨ x 3 ) ∧ ( x1 ∨ x2 ∨ x 3 ) ∧ ( x1 ∨ x 2 ∨ x3 );
                  ( x 1 ∧ x 2 ∧ x 3 ) ∨ ( x 1 ∧ x 2 ∧ x 3 ) ∨ ( x1 ∧ x 2 ∧ x 3 ) ∨ ( x1 ∧ x 2 ∧ x 3 ).

      Следствие Любая булева функция выразима через функции:  , ∧, ∨.

      Функциональная полнота

       Система функций называется полной в некотором множестве, если лю-
бая функция этого множества может быть представлена суперпозицией функ-
ций из указанной системы.
       Примеры полных систем в множестве булевых функций:
       1) , ∧, ∨;
       2)  , ∧;
       3) , ∨;
       4)↓;
       5) ⁄.
       Две последние системы содержат по одной функции, которые называю-
тся соответственно Стрелка Пирса и Штрих Шеффера. Имеют место равенства:

Страницы