Informatyka studia dzienne - WMI, WMID, UAM, Uniwersytet im. Adama Mickiewicza w Poznaniu

1:W-LOG-1/071107/0

Posted by Crs in Wykłady, ... | 11.07.2007 - 08:15

Zajęcia prowadził: dr hab. Maciej Kandulski

ALGEBRY BOOLE’A

Algebra Boolea
Dualność w algebrach Boole’a

- George Boole (1815-1864)

______________________________________________________________________

Def.
Algebrą nazywamy zbiór wraz z działaniem/działaniami i elementami wyróżnionymi.

Ważne jest to, iż każde działanie w algebrze musi być w uniwersum (przestrzeni (zbiorze) wszystkich elementów), czyli każdy argument działania musi zawierać się w uniwersum, ale także jego wynik musi należeć do tego uniwersum. Czyli działanie musi być działaniem wewnętrznym.

Rożnicą jest działanie na uniwersum - tylko argumenty muszą należeć do tego uniwersum.

Przykład:

Dodawanie jest określone “w zbiorze” liczb rzeczywistych. Obojętnie jakie argumenty wybierzemy (należące oczywiście do zbioru liczb rzeczywistych) wynik działania będzie także zawierał sie w tym zbiorze.

Natomiast działanie “na zbiorze” ładnie opisuje odejmowanie w zbiorze liczb naturalnych. Istnieją takie liczby a i b należące do zbioru liczb naturalnych, których różnica nie będzie liczbą naturalną. Wystarczy, że a > b przy zapisie różnicy a-b, wynik będzie ujemny, zatem nie należący do zbioru liczb naturalnych.

Def.
Algebrą Boole’a nazywamy algebrę postaci:

$\mathcal{A}\ = \ (A, \cap , \cup , \prime , 0,1)$

gdzie (to są tylko symbole, a ni np. jedynka i zero):

$\mathcal{A}$ lub $\mathbb{A}$ - nazwa algebry (Tak naprawdę można używać każdej wariacji litery, oznaczającej uniwersum, równie dobrze mógłbym tu zastosować A z 10 kreskami na górze. Zapis jest mało ważny)

$A$ - uniwersum (przestrzeń,zbiór)

$\cap,\ \cup$ - działania dwuargumentowe (nie mylić ze znanymi ze zbiorów znakami iloczynu i sumy zbiorów!)

$\prime$ - działanie jednoargumentowe elementu zawierającego się w A

$0,1$ - wyróżnione elementy zbioru A.

Dodatkowo, muszą być spełnione warunki $\forall x,y,z \in A$

(B0)
$1\neq 0$
(Czyli inaczej, wyróżnione elementy nie mogą być sobie równe)

(B1)
$(x \cup y)\cup z \ = \ x\cup(y \cup z)$
$(x \cap y)\cap z \ = \ x\cap(y \cap z)$
Prawo łączności.

(B2)
$x \cup y \ =\ y \cup x$
$x \cap y \ =\ y \cap x$
Przemienność

(B3)
$x \cup ( y \cap z) = (x \cup y) \cap (x \cup z)$
$x \cap (y \cup z) \ =\ (x \cap y) \cup (x \cap z)$
Rozdzielność
- zauważyć należy różnicę miedzy algebraiczną rozdzielnością. Nie ma rozdzielności sumy względem mnożenia, natomiast w algebrach Boole’a jest!

(B4)
$x \cup 0 \ =\ x$
$x \cap 1 \ =\ x$
Prawo dla 0 i 1.

(B5)
$x \cup x\prime \ =\ 1$
$x \cap x\prime \ =\ 0$
Prawo dopełnienia. Identyczne jak dla zbiorów.

- Na mocy (B0) każda algebra Boole’a zawiera co najmniej dwa elementy.

Przykłady:

$\ B_2=(\{0 , 1\},\vee,\wedge,\neg,0,1)$ $\ B_2=(\{0 , 1\},\vee,\wedge,\neg,0,1)$

Działania $\vee,\wedge,\neg$ $\vee,\wedge,\neg$ traktować należy podobnie do zwyczajnej alternatywy, koniunkcji i negacji w klasycznym rachunku zdań. Mamy zatem:

Dla działania oznaczonego znakiem negacji:
$$$ \begin{array}{ccc}x & x' \\ 1 & 0 \\ 0 & 1$ $$$ \begin{array}{ccc}x & x' \\ 1 & 0 \\ 0 & 1$ >/p>

Dla pozostałych działań:
$$$ \begin{array}{cccc}x & y & x \vee y & x \wedge y \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0$ $$$ \begin{array}{cccc}x & y & x \vee y & x \wedge y \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0$

Przyjmując naturalny porządek w zbiorze {0,1} (Dlaczego tak jest, zostanie omówione później i dokładnie wyjaśnione) mamy:

$\ x \vee y = max(x,y)$ $\ x \vee y = max(x,y)$

$\ x \wedge y = min(x,y)$ $\ x \wedge y = min(x,y)$

Bezpośrednio z tabelki lub z określeń max/min mamy:
$$$ \begin{array}{ccccc} x&\vee&1&=&1 \\ x&\vee&0&=&x \\ x&\wedge&0&=&0 \\ x &\wedge&1&=&x$ $$$ \begin{array}{ccccc} x&\vee&1&=&1 \\ x&\vee&0&=&x \\ x&\wedge&0&=&0 \\ x &\wedge&1&=&x$

Drugim przykładem algebry Boole’a jest algebra wszystkich podzbiorów zadanego zbioru $\ \emptyset \not= U$ $\ \emptyset \not= U$ (niepustego U)

Oznaczamy go zapisem:
$\ \mathbb{P}(U)$ $\ \mathbb{P}(U)$

Uniwersum algebry $\ \mathbb{P}(U)$ jest zbiór potęgowy zbioru U, to jest zbiór $\ \mathbb{P}(U)=\{x:x \in U \}$

Przykład, dla rozjaśnienia:
$\ U=\{a,b,c\}$ $\ U=\{a,b,c\}$

Zatem:
$\ \mathbb{P}(U)=(\{a,b,c\},\{a,b\},\{a,c\},\{b,c\},\{a\},\{b\},\{c\},\{\emptyset\})$ $\ \mathbb{P}(U)=(\{a,b,c\},\{a,b\},\{a,c\},\{b,c\},\{a\},\{b\},\{c\},\{\emptyset\})$

Można zauważyć, ze są to wszystkie podzbiory zbioru {a,b,c}, stąd, jeśli U jest skończonym zbiorem i ma n elementów, to:

$\ \mathbb{P}(U)=2^n$ $\ \mathbb{P}(U)=2^n$

______________________________________________________________________

Dualność w algebrach Boole’a:

Niech P będzie pewną równością w algebrach Boole’a. Równość powstającą z P poprzez:
-zamianę każdego wystąpienia iloczynu na sumę
-zamianę każdego wystąpienia sumy na iloczyn
-zamianę 0 na 1
-zamianę 1 na 0
nazywamy równością dualną do P i oznaczamy $\ P^d$ $\ P^d$

Zasada dualności w algebrach Boole’a:

Jeśli równość P jest prawdziwa we wszystkich algebrach Boole’a, to $\ P^d$ jest także prawdziwa we wszystkich algebrach Boole’a.
Oznacza to mniej więcej tyle, ze o ile łatwiej jest dowodzić równość dualną do zadanej równości, możemy to zrobić, przez co udowodnimy pierwszą równość. Bądź odwrotnie ;D

Do poznanych wcześniej zasad (B0)-(B5), można zatem dołożyć następne (które wynikają poprzez dualność/podstawianie z tych pierwszych, zatem nie trzeba sprawdzać zawsze wszystkich warunków, wystarczy B0-B5.) Więc:

(B6)

$\ x \vee x = x , x \wedge x = x$ $\ x \vee x = x , x \wedge x = x$

Dowód:
(Przeprowadzany tylko w jedną stronę, warto zauważyć, ze wszystkie równania są dualne ; ) Na górnych indeksach zaznaczam zasady, których używam do pokazania dowodu )

$\ x^{B_4}=x \vee 0^{B_5} = x \vee (x \wedge x')^{B_3} = (x \vee x) \wedge (x \vee x)^{B_5}=(x \vee x) \wedge 1^{B_4}=x \vee x$ $\ x^{B_4}=x \vee 0^{B_5} = x \vee (x \wedge x')^{B_3} = (x \vee x) \wedge (x \vee x)^{B_5}=(x \vee x) \wedge 1^{B_4}=x \vee x$

(B7)

$\ x \vee 1 = 1 , x \wedge 0 = 0$ $\ x \vee 1 = 1 , x \wedge 0 = 0$

Dowód:
$\ x \vee 1^{B_5}= x \vee ( x \vee x')^{B_1} = (x \vee x) \vee x'^{B_6}=x \vee x'^{B_5}=1$ $\ x \vee 1^{B_5}= x \vee ( x \vee x')^{B_1} = (x \vee x) \vee x'^{B_6}=x \vee x'^{B_5}=1$

(B8)

$\ x \vee (x \wedge y) = x , x \wedge (x \vee y) = y$ $\ x \vee (x \wedge y) = x , x \wedge (x \vee y) = y$

Dowód:
$\ x \vee (x \wedge y)^{B_4}= ( x \wedge 1 ) \vee (x \wedge y)^{B_3} = x \wedge (x \vee y)^{B_7}=x \wedge (y \vee 1 )^{B_7}=x \wedge 1 = x$ $\ x \vee (x \wedge y)^{B_4}= ( x \wedge 1 ) \vee (x \wedge y)^{B_3} = x \wedge (x \vee y)^{B_7}=x \wedge (y \vee 1 )^{B_7}=x \wedge 1 = x$

(B9)

$\ x \vee y = y <=> x \wedge y =x$ $\ x \vee y = y <=> x \wedge y =x$

Dowód:
Zakładamy, że lewa strona równoważności jest prawdziwa, zatem:

$\ x \wedge y = x \wedge (x \vee y )^{B8}=x$ $\ x \wedge y = x \wedge (x \vee y )^{B8}=x$

W prawą stronę analogicznie:
$\ x \vee y = (x \wedge y ) \vee y = y \vee (y \wedge x)^{B_8}=y$ $\ x \vee y = (x \wedge y ) \vee y = y \vee (y \wedge x)^{B_8}=y$