AlgebraBoole'a.pdf

(123 KB) Pobierz
Materiał dydatyczny pomocniczy do wykładu Informatyka
Materiał dydaktyczny pomocniczy do wykładu Informatyka
Uwagi o algebrze Boole'a
Def. 1. (algebra Boole'a).
Algebrą Boole'a
B
=
[
A
, ∨
∧
,
,
'
,
O
,
I
]
nazywamy zbiór A z dwoma działaniami
( ∧ , dwiema stałymi ( O , I ) i jednym działaniem jedno-
argumentowym ' , taki że dla każdego
)
yx ∈
,
,
z
A
spełnione są następujące równości :
L1.
x
∧ ,
x
x
x
∨
x
=
x
(idempotentność)
L2.
x
∧
y
=
y
∧
x
,
x
∨
y
=
y
∨
x
(przemienność)
L3.
x
∧
(
y
∧
z
)
=
(
x
∧
y
)
∧
z
x
∨
(
y
∨
z
)
=
(
x
∨
y
)
∨
z
(łączność)
L4.
x
∧
(
x
∨
y
)
=
x
,
x
∨
(
x
∧
y
)
=
x
(pochłanianie)
L5.
x
∧
[
y
∨
(
x
∧
z
)]
=
(
x
∧
y
)
∨
(
x
∧
z
)
,
x
∨
[
y
∧
(
x
∨
z
)]
=
(
x
∨
y
)
∧
(
x
∨
z
)
(modularność)
L6.
x
∧
(
y
∨
z
)
=
(
x
∧
y
)
∨
(
x
∧
z
)
,
x
∨
(
y
∧
z
)
=
(
x
∨
y
)
∧
(
x
∨
z
)
(rozdzielność)
L7.
x
∧
O
=
O
,
x
∨
O
=
x
x
∧
I
=
x
,
x
∨
I
=
I
( łasności stałych)
L8.
x
∧
x
'
=
O
,
x
∨
x
'
=
I
(uzupełnienie)
L9.
(
x =
'
)'
x
(inwolucja)
L10.
(
x
∧
y
)'
=
x
'
∨
y
'
(
x
∨
y
)'
=
x
'
∨
y
'
(prawa de Morgana)
0 ∧ i
są działaniami wyznaczającymi odpowiednio mniejszy i większy element z dwóch danych,
a działanie ' wyznacza element przeciwny do danego.
B
=
[
0 ∨
,
∧
,
,
'
,
1
nazywamy zbiór { gdzie
∨
Mamy więc
0 =
∧
1
0
0 =
∨
1
1
0 =
∧
0
0
,
0 =
∨
0
0
1 =
∧
1
1
,
1 =
∨
1
1
1 =
Operator dwuargumentowy nazywamy operatorem koniunkcji (iloczynu logicznego), a
wyrażenie x y nazywamy iloczynem logicznym elementów x i y , operator dwuargumentowy
0 = ,
'
1
0
∧
∧
dwuargumentowymi
Def. (dwuelementowa algebra Boole'a)
Dwuelementową algebrą Boole'a { }
∨ operatorem alternatywy (sumy logicznej), a wyrażenie x y sumą logiczną elementów x i
y . Operator jednoargumentowy ' nazywamy operatorem negacją, a wyrażenie x ' negacją
elementu x .
∨
Tab. 1 Tabela prawdy dla iloczynu logicznego, sumy logicznej i negacji
x
y
x y
∧
x ∨ y
x '
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
1
1
1
1
0
Def. (wielomian boolowski)
Wielomianem boolowskim nazywamy dowolne wyrażenie, które można otrzymać
poprzez rekurencyjne zastosowanie działań ∧ , i ' do pewnego zbioru symboli
.
∨
x
1
, 2
,...,
x
n
Każdy wielomian boolowski definiuje funkcję na dowolnej
algebrze Boole'a B . Wartości funkcji F mogą być wyliczane poprzez wstawianie elementów z
F
(
x
1
,
x
2
,...,
x
n
)
F
:
B
n →
B
B do wielomianu.
Przykład. Funkcja boolowska dwóch zmiennych.
=
Każda ze zmiennych może przybrać wartość 0 lub wartość 1. Wstawiając wszystkie
możliwe kombinacje zmiennych do i stosując konieczne własności spośród L1-L8,
otrzymamy wartości funkcji . Przykładowo, gdy wstawimy wartości
F
1
(
x
1
,
x
2
)
x
1
∧
x
' 2
∨
x
1
∧
x
2
x
1 , x
2
x
1 , x
2
F
F
x
1
= x
0 2
=
0
, i
uwzględniając negację otrzymujemy
0 ∧ 1 1 0=0 0=0.
∨ ∧ ∨
Tab. 2. Tabela prawdy (tabela wartości) funkcji .
F
x
x
F
1
(
x
1
,
x
2
)
0
0
0
0
1
1
1
0
1
1
1
0
W teorii układów cyfrowych do zapisu funkcji boolowskich zwanych także funkcjami
logicznymi, stosuje się zamiast operatora ∨ operator +, a operator ∧ jest pomijany w zapisie
iloczynu zmiennych. Aby zaznaczyć negację stosuje się poziomą kreskę nad zmienną która
ma być zanegowana. Tak więc przy zastosowaniu tej konwencji funkcję
F
1
(
x
1
,
x
2
)
można
zapisać w sposób następujący:
F
1
(
x
1
,
x
2
)
=
x
1
x
2
+
x
1
x
2
x
4464245.001.png 4464245.002.png 4464245.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin