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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Легко видеть, что над некоторой данной системой одна функция может иметь множе-
ство ра
ми (тождественными), если
они ре
зличных реализаций. В связи с этим введем следующее
Определение. Две формулы называются равносильны
ализуют одну и ту же функцию. При этом пару равносильных формул, связанных
знáком равенства называют тождеством:
12
Φ
=Φ
,
если
1
f
unc fΦ=
и
2
f
unc f
Φ
=
.
Пример 5 а основани примера получаем тождество
. Н и предыдущего
x
yxyxy
⊕
⊕
=
∨ .
Имеют место следующие основные булевы тождества:
Таблица 3
Замечание. Операции и на множестве
1.
aaa∨=
aaa
∧
=
2. ∨abba∨=
abba
=∧
3.
(() )
abc abc∨∨=∨∨
(
)
(
)
abc abc
∧
∧=∧∧
4.
()
ab aa∧∨=
(
)
ab aa∨∧=
5.
()()
(
)
abc ab ac∨∧=∨∧∨
(
)
(
)
(
)
abc ab ac
∧
∨=∧∨∧
6.
11a ∨=
00a
∧
=
7.
0aa∨=
1aa
∧
=
8.
aa=
01
=
9.
abab∧=∨ abab∨=∧
10.
1aa∨=
0aa
∧
=
11.
/ab ab=
abab↓=∨
12.
abab⊕≡=
ababab≡= ∨
13.
a bab→=∨
(
)
(
)
abbaa→→ b≡
=
14.
abba⊕⊕=
(
)
(
)
ccab ab
⊕
⊕⊕=
⊕
15.
0aa⊕ =
1aa⊕
=
16. 0aa⊕ =
1aa⊕
=
∨
∧
{
}
2
0, 1E =
, для которых выполняются
первые 3 аю естве алге пять свойств таблицы зад т на этом множ браическую структуру или,
проще, алгебру. Дополненная следующими пятью свойствами вместе с операцией
¬
эта ал-
гебраическая структура превращается в булеву алгебру
2
;,,E ∨∧¬
, называемую т кже ал-
геброй логики.
Подставл
а
яя вместо
и любые булевы функции, а значит, любые реализующие
их фор ч а
a
,
b
c
мулы, становится ясно, то ксиомы алгебры логики (первые десять свойств таблицы
3) выполнены и в алгебре
;,,
n
P ∨∧¬
. Эта алгебра называется алгеброй булевых функций.
Принцип двойственности 
       Легко видеть, что над некоторой данной системой одна функция может иметь множе-
ство различных реализаций. В связи с этим введем следующее
       Определение. Две формулы называются равносильными (тождественными), если
они реализуют одну и ту же функцию. При этом пару равносильных формул, связанных
знáком равенства называют тождеством:

                                                   Φ1 = Φ 2 ,
если funcΦ1 = f и funcΦ 2 = f .
      Пример 5. На основании предыдущего примера получаем тождество

                                             xy ⊕ x ⊕ y = x ∨ y .

      Имеют место следующие основные булевы тождества:

                                                                                        Таблица 3
             1. a ∨ a = a                                a∧a =a
             2. a ∨ b = b ∨ a                            a∧b = b∧a
             3. a ∨ ( b ∨ c ) = ( a ∨ b ) ∨ c            a ∧ (b ∧ c ) = ( a ∧ b ) ∧ c
             4. ( a ∧ b ) ∨ a = a                       (a ∨ b) ∧ a = a
             5. a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c )   a ∧ (b ∨ c ) = ( a ∧ b) ∨ ( a ∧ c )
             6.   a ∨1 = 1                               a∧0 = 0
             7.   a∨0= a                                 a ∧1 = a
             8.   a =a                                   0 =1
             9.   a ∧b = a∨b                             a∨b = a ∧b
            10.   a ∨ a =1                               a∧a =0
            11.   a / b = ab                             a ↓b = a∨b
            12.   a ≡ b = a⊕b                           a ≡ b = ab ∨ a b
            13.   a →b = a ∨b                           ( a → b )( b → a ) = a ≡ b
            14. a ⊕ b = b ⊕ a                            a ⊕ (b ⊕ c ) = ( a ⊕ b ) ⊕ c
            15. a ⊕ a = 0                                a ⊕ a =1
            16. a ⊕ 0 = a                                a ⊕1 = a

      Замечание. Операции ∨ и ∧ на множестве E2 = {0, 1} , для которых выполняются
первые пять свойств таблицы 3 задают на этом множестве алгебраическую структуру или,
проще, алгебру. Дополненная следующими пятью свойствами вместе с операцией ¬ эта ал-
гебраическая структура превращается в булеву алгебру E2 ; ∨, ∧, ¬ , называемую также ал-
геброй логики.
      Подставляя вместо a , b и c любые булевы функции, а значит, любые реализующие
их формулы, становится ясно, что аксиомы алгебры логики (первые десять свойств таблицы
3) выполнены и в алгебре Pn ; ∨ , ∧, ¬ . Эта алгебра называется алгеброй булевых функций.




                                    Принцип двойственности

Страницы