ВУЗ:
Составители:
Рубрика:
7
Таблица 4
х
1
х
2
х
3
1
x
21
xx ∨
x
1
&x
3
(
21
xx ∨
)→(x
1
&x
3
)
0 0 0 1 1 0 0
0 0 1 1 1 0 0
0 1 0 1 1 0 0
0 1 1 1 1 0 0
1 0 0 0 0 0 1
1 0 1 0 0 1 1
1 1 0 0 1 0 0
1 1 1 0 1 1 1
1.4. Законы и теоремы булевой алгебры
Формулы, представляющие одну и ту же функцию называются эквивалентными
или
равносильными (обозначаются =).
Основные законы булевой алгебры.
1. Ассоциативность конъюнкции и дизъюнкции (сочетательный закон):
а)
x
1
⋅(x
2
⋅x
3
)=(x
1
⋅x
2
)⋅x
3
=x
1
⋅x
2
⋅x
3
, б) x
1
∨(x
2
∨x
3
)=(x
1
∨x
2
)∨x
3
=x
1
∨x
2
∨x
3
.
2. Коммутативность конъюнкции и дизъюнкции (переместительный закон):
а)
x
1
⋅x
2
=x
2
⋅x
1
, б) x
1
∨x
2
=x
2
∨x
1
.
3. Дистрибутивность (распределительный закон):
а)
x
1
⋅(x
2
∨x
3
)=x
1
⋅x
2
∨ x
1
⋅x
3
, б) x
1
∨(x
2
⋅x
3
)=(x
1
∨x
2
)⋅(x
1
∨x
3
).
4. Идемпотентность
(правило повторения):
а)
x⋅x=x, б) x∨x=x.
5. Закон двойного отрицания:
.
x
x
=
6. Свойства констант 0 и 1:
а)
x⋅1=x, б) x⋅0=0, в) x∨1=1,
г) x∨0=x, д) ⎯0=1, е) ⎯1=0.
7. Теорема двойственности (правила де Моргана):
а)
2121
xxxx ∨=⋅ , б)
2121
xxxx ⋅=∨ .
8. Закон противоречия: x⋅
х
=0.
9. Закон исключённого третьего: x∨
x
=1.
Все эти равенства остаются справедливыми при подстановке вместо переменных
любых логических функций и, следовательно, любых формул, представляющих эти
функции. Наряду с основными соотношениями для упрощения формул часто
используются следующие правила:
1. Правила поглощения:
а) x
1
∨x
1
⋅x
2
=x
1
, б) x
1
⋅(x
1
∨x
2
)=x
1
.
2. Правила склеивания:
а) x
1
⋅x
2
∨x
1
⋅
2
х =x
1
б) x
1
∨
1
x ⋅x
2
=x
1
∨x
2
.
3. Правило обобщенного склеивания:
x
1
⋅x
3
∨x
2
⋅
3
x ∨x
1
⋅x
2
=x
1
⋅x
3
∨x
2
⋅
3
x .
Пример. Упростить булевы формулы:
а) f(x
1
, x
2
, x
3
)=x
1
∨x
1
x
3
∨
1
xx
2
x
3
∨x
2
3
x =x
1
∨
1
xx
2
x
3
∨x
2
3
x = x
1
∨x
2
x
3
∨x
2
3
x =
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
