algebra boola

[ Pobierz całość w formacie PDF ]
Sławomir Kulesza
Technika cyfrowa
Opis układów cyfrowych
Wykład dla studentów III roku Informatyki
Wersja 2.0, 10/10/2011
Rachunek zdań
Zdanie logiczne – każde zdanie, któremu można
przyporzadkować wartość logiczną (T/F).
Funktory logiczne – spójniki łączące zdania logiczne.
koniunkcja
alternatywa
implikacja
negacja
równoważność
p q p
∧
q
p
∨
q
p
⇒
q
p
⇔
q
∼
p
0 0
0
0
1
1
1
0 1
0
1
1
0
1
1 0
0
1
0
0
0
1 1
1
1
1
1
0
 Algebra Boole'a
Zerojedynkowa algebra sygnałów binarnych:
<{0, 1},
∨, ∧, ∼,
0, 1>:
- zdefiniowane działania zeroargumentowe: 0, 1
- zdefiniowane działanie jednoargumentowe: NOT
- zdefiniowane działania dwuargumentowe: OR, AND
- element neutralny sumy: 0
- element neutralny iloczynu: 1
Prawa algebry Boole'a
x
∨
x = x
x
∧
x = x
Idempotentność
x
∨
y = y
∨
x
x
∧
y = y
∧
x
Przemienność
x
∨
(y
∨
z) = (x
∨
y)
∨
z
x
∧
(y
∧
z) = (x
∧
y)
∧
z
Łączność
Rozdzielność
x
∨
(y
∧
z) = (x
∨
y)
∧
(x
∨
z) x
∧
(y
∨
z) = (x
∧
y)
∨
(x
∧
z)
Pochłanianie
x
∨
(x
∧
y) = x
x
∧
(x
∨
y) = x
x
∨
0 = x
x
∧
1 = x
Element neutralny
x
∨
1 = 1
x
∧
0 = 0
Element stały
Negacja
x
∨
∼
x = 1
x
∧
∼
x = 0
xx
Podwójna negacja
∼(∼) =
xy xy
∼( ∧ ) = ∼ ∨ ∼
xy xy
Prawa de Morgana
∼( ∨ ) = ∼ ∧ ∼
 Zasada dualności
W obrębie danego prawa wzory są dualnie
równoważne: każdy związek można otrzymać
z drugiego poprzez zamianę operatorów koniunkcji
i alternatywy oraz stałych 0 i 1.
[ Pobierz całość w formacie PDF ]