37. Podstawowe prawa algebry Boole'a.

B=<B,+,*,~,0,1>

Algebra Boole'a posługuje się jedynie dwiema możliwymi cyframi. Przyjęło się zapisywać

je jako 0 i 1. Można też wyobrazić je sobie jako dwa przeciwne stany - prawda (ang. true) i fałsz (ang. false). Na tych dwóch dostępnych liczbach definiuje się kilka podstawowych działań:

- negacja - jest to działanie jednoargumentowe oznaczane symbolem ~. Dla

dwuwartościowego systemu zanegowanie wartości powoduje jej zamianę na wartość przeciwną, czyli drugą spośród dwóch możliwych:

x ~x

0 1

1 0

Negacja nazywana bywa też przeczeniem lub dopełnieniem, a jej słownym odpowiednikiem jest słowo „nie”.

Operatory negacji:

_

~ ' a

- koniunkcja - koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy gdy dla zdań

p i q, oba zdania p, q są prawdziwe.

x y x AND y

0 0 0

0 1 0

1 0 0

1 1 1

Koniunkcja bywa też nazywana iloczynem, a odpowiadającym jej słowem jest „i”.

Operatory iloczynu:

* ^

- alternatywa - alternatywa zdań jest prawdziwa, wtedy i tylko wtedy gdy dla zdań p i q, co najmniej jedno ze zdań p lub q jest prawdziwe.

x y x OR y

0 0 0

0 1 1

1 0 1

1 1 1

Alternatywa bywa też nazywana sumą, a odpowiadającym jej słowem jest „lub”.

Operatory sumy:

+ v

- różnica symetryczna - różnicę symetryczną uznaje się za prawdziwą, wtedy i tylko wtedy gdy dla zdań p i q, zdanie p jest prawdziwe i q jest fałszywe, lub zdanie p jest fałszywe i q jest prawdziwe.

x y x XOR y

0 0 0

0 1 1

1 0 1

1 1 0

Przyjmuje się, że priorytet powyższych działań określa, że działanie dopełnienia ma pierwszeństwo przed iloczynem, zaś działanie iloczynu ma pierwszeństwo przed działaniem sumy.

Aksjomaty:

Prawa identyczności (własności stałych):

x+0=x;

x*1=x

Prawa dopełnienia:

x+(~x)=1;

x*(~x)=0

Prawa przemienności:

x+y=y+x;

x*y=y*x

Prawa łączności:

x+(y+z)=(x+y)+z;

x*(y*z)=(x*y)*z

Prawa rozdzielności:

x*(y+z)=x*y + x*z;

x+(y*z)=x+y * x+z

Wynikają z nich:

Prawa idempotentności:

x  x=x;

x  x=x

Drugie prawa identyczności

x  1=1;

x  0=0

Prawa pochłaniania

x  (x  y)=x;

x  (x  y)=x

Prawo inwolucji

(x')'=x

W każdej algebrze Boole'a spełnione są też:

• Prawa De Morgana

(x  y)' = x'  y';

(x  y)' = x'  y'

• Zasada dualności

Każde prawdziwe twierdzenie dotyczące algebry Boole'a, w którym występują tylko trzy działania: , , ' pozostanie prawdziwe, jeśli zamienimy wszędzie  na  i  na  zachowując działanie ' jako niezmienione oraz zamieniając 0 na 1 i 1 na 0 jeśli występują.

- koniunkcja

- alternatywa

- zaprzeczenie

- implikacja

- równoważność

Przykłady:

f(x1,x2)=x1+(x1*~x2)

x1 | x2 | f

0 | 0 | 0

0 | 1 | 0

1 | 0 | 1

1 | 1 | 1

f(x,y,z)=(x+~y)*z=xyz + x~yz + ~x~yz = xyz + ~yz

---