Podstawy algebry Boole'a:

Algebra Boole'a jest "narzędziem" matematycznym służącym m.in. do opisu, analizy i syntezy układów logicznych. Stanowi ona uogólnienie rachunku zdań i algebry zbiorów uznając jedno i drugie tylko za szczególne przypadki ogólniejszej teorii. Również szczególnym przypadkiem algebry Boole'a jest binarna algebra Boole'a.
    Dla zdefiniowania każdej algebry potrzebne jest określenie pewnego zbioru, działań w tym zbiorze (operacji) , elementów wyróżnionych w tym zbiorze oraz zespołu aksjomatów i twierdzeń.

Binarna algebra Boole'a:

Binarną algebrę Bool'a tworzą:    - zbiór dwuelementowy {0,1}
                                                           - wyróżnione elementy tego zbioru - 0 i 1 - (czyli oba są wyróżnione}
                                                           - dwa działania (operacje, funktory) - suma logiczna (+) oraz iloczyn logiczny (*)
                                                           - zestaw aksjomatów 1-5 oraz 1'-5'
                                                           - wynikający z aksjomatów zestaw twierdzeń 1 - 7 oraz 1' - 7' i 8

definicja sumy logicznej i iloczynu logicznego

Aksjomaty:

Aksjomaty dualne:

Twierdzenia:

Twierdzenia dualne:

Twierdzenie nr.6 to bardzo przydatne Prawo de Morgana, zaś twierdzenie nr.2 to tzw. Prawo Pochłaniania.
Aksjomaty dualne tworzy się poprzez zamianę w aksjomatach 1-5   '0' na '1', '1' na '0', oraz znaku 'mnożenia' na 'dodawanie'.

Związek algebry Boole'a z rachunkiem zdań i algebrą zbiorów:

Funkcja boolowska i sposoby jej określania

Funkcję boolowską m zmiennych x₁, x₂, x₃, ... , x_m , gdzie x_i należy do zbioru {0,1} nazywamy takie odwzorowanie, które wariacjom zero-jedynkowym zmiennych x₁, x₂, x₃, ... , x_m przyporządkowuje wartość funkcji (oznaczoną y) równą 0, bądź 1, co można symbolicznie zapisać:

y=f(x₁, x₂, x₃, ... , x_m)

lub

f:{0,1}x{0,1}x{0,1}x … x{0,1}
{0,1}

np. Funkcja boolowska jednej zmiennej


    
     drut


    
     negator


    
     stałe zera


    
     stałe jedynki

Sposoby określania funkcji boolowskiej:

1)  Tabela prawdy dla funkcji boolowskiej m zmiennych ma m+1 kolumn i 2^m wierszy. Kolumny są opisane zmiennymi
x₁, x₂, x₃... , x_m oraz symbolem y przeznaczonym na wartość funkcji. W kolejnych wierszach tabeli prawdy piszemy aż do wyczerpania możliwe zestawy (wariacje) zero-jedynkowe zmiennych boolowskich - stąd liczba wierszy równa 2^m. Dla ułatwienia kolejne wiersze numerujemy dziesiętnie od 0 do 15 (31). Liczbę kolumn tabeli prawdy można rozszerzyć, gdy w jednej tabeli chcemy przedstawić kilka funkcji tych samych zmiennych.

dla m zmiennych wejściowych jest 2m wierszy, które opisujemy liczbami dziesiętnymi od 0 do(2m-1)

2)  Zapis numeryczny (uproszczony) funkcji boolowskiej to wyszczególnienie w postaci zbioru liczb dziesiętnych poprzedzonych znakiem
(bądź
- dualny sposób zapisu), a będących numerami tych wierszy tabeli prawdy, w których funkcja boolowska przyjmuje wartość 1 (bądź odpowiednio 0).
y=
(..., ..., ..., ...) x₁, x₂, x₃
W zapisie ważne jest wskazanie starszeństwa bitów , co też uczyniono pisząc kolejno od najstarszego(od lewej) do najmłodszego x₁, x₂, x₃ u dołu, aby uniknąć niejednoznaczności, bowiem co innego znaczyłaby kolejność
x₃, x₂, x₁.

3)  Dekompozycja Szannona (funkcja residualna, funkcja resztowa, podfunkcja boolowska )
Każdą funkcję boolowską można zapisać w postaci :


lub krócej:

, gdzie x_i - dowolna zmienna.

SYSTEM FUNKCJONALNIE PEŁNY (SFP)

- podzbiór funkcji boolowskich (w szczególności jedna) za pomocą którego można wyrazić wszystkie teoretycznie możliwe funkcje boolowskie.
Z definicji binarnej algebry Boole'a wynika, że podstawowym SFP jest zespół funkcji "+", "-", "*", tak więc można zapisać, że :
SFP={suma logiczna, iloczyn logiczny, negacja}
Gdyby powyższe przeanalizować uważniej okazałoby się, że wystarczą dwie funkcje, i tak:
SFP={suma logiczna, negacja}
SFP={iloczyn logiczny, negacja}.
Wystarczy bowiem zastosować Prawa de Morgana (T6, T6'), które pozwalają wyrażać negację iloczynu jako sumę negacji, bądź negację sumy jako iloczyn negacji.

Powstaje jednak pytanie - jakie inne zespoły funkcji (funktorów), szczególnie dwuargumentowych tworzą SFP ? Odpowiedź pozornie wydaje się mieć aspekt czysto teoretyczny, ma jednak ogromne znaczenie praktyczne. Jeśli bowiem okazałoby się, że istnieje np. funkcja dwuargumentowa, za pomocą której można wyrazić dowolną funkcję wielu zmiennych, to wystarczyłoby produkować element realizujący technicznie funkcję tworzącą SFP, a wówczas każdy układ logiczny można by skonstruować jako odpowiednie "złożenie" tego typu elementów.

Spośród 16 funkcji boolowskich dwóch zmiennych na szczególną uwagę zasługują:
- funkcja Sheffera zwana kreską Sheffera    

- funkcja Peirce'a zwana strzałką Pierce'a    


Każda z tych funkcji z osobna tworzy SFP.
Technicznym odpowiednikiem kreski Sheffera jest produkowany element (bramka) typu NAND (Not - And czyli negacja iloczynu), natomiast odpowiednikiem strzałki Pierce'a jest element (bramka) NOR (Not - Or, czyli negacja sumy)

Oprócz tak ważnych funkcji dwóch zmiennych jak omawiane wyżej istotne znaczenie w praktyce, choć nie tworzą samodzielnie SFP, mają różnica symetryczna (suma modulo 2, alternatywa wyłączająca, EXOR, XOR), oznaczana symbolem
oraz równoważność oznaczana symbolem
, a zdefiniowane poniżej :

Zależności pomiędzy powyższymi funkcjami :

Z powyższych określeń wynikają także inne własności funkcji.

Zauważyć można, że suma modulo 2 pełnić może rolę detektora przeciwnych sygnałów.

Minimalizacja funkcji boolowskich Kanoniczna postać sumy -KPS- (iloczynu -KPI-) jest jedynie przejściową formą zapisu funkcji boolowskiej. Ze względów czysto technicznych wskazane jest otrzymanie takiej postaci formuły boolowskiej, aby zawierała możliwie jak najmniejszą liczbę składników sumy, o jak najmniejszej liczbie czynników tworzących dany składnik (KPS). Dla KPI postępujemy analogicznie - tzn. możliwie jak najmniejszą liczbę czynników iloczynu o jak najmniejszej liczbie składników, tworzących dany czynnik. 1.  Metoda przekształceń formalnych algebraicznych: gdzie zapis KPS bądź KPI poddaje się przekształceniom zgodnym z aksjomatami i twierdzeniami algebry Boole'a. Przykład : Grupowanie składników, wyłączanie przed nawias części wspólnych : Na mocy aksjomatu 5 (patrz wykład nr2): otrzymujemy : Z kolei na mocy dualnego aksjomatu 4' możemy zapisać: Otrzymaliśmy zatem formułę dwuskładnikową o dwóch czynnikach każdy, podczas gdy pierwotna miała cztery składniki o trzech czynnikach każdy. Gdyby założyć, że mamy do dyspozycji w realizacji technicznej elementy wykonujące operację sumy, iloczynu i negacji, wówczas oczywiście realizacja techniczna formuły uproszczonej byłaby tańsza, jeśliby przyjąć, że cena układu zależy od liczby elementów, jak i liczby połączeń między nimi. 2.  Algorytmiczna metoda siatek Karnaugha: W algorytmicznej metodzie siatek Karnaugha stosuje się tzw. regułę sklejania :                                          gdzie A jest dowolną formułą boolowską      Reguła sklejania pozwala dla dwóch iloczynowych członów różniących się negacją zmiennej x, wyrugować tę zmienną jako nieistotną. Sklejane człony można nazwać sąsiednimi. Zasadniczą trudnością w procesie sklejania jest wyszukanie sąsiednich członów, inaczej mówiąc - znalezienie jedynek(zer) sąsiednich, ponieważ dany składnik reprezentuje zawsze jakąś jedynkę(zero) funkcji. W metodzie siatek Karnaugha problem sąsiedztwa jest rozwiązywany przez odpowiednie narysowanie tabeli prawdy, zwanych tutaj siatkami Karnaugha. Są one skonstruowane tak, że różniącym się tylko o negację jednej zmiennej pełnym iloczynem(sumom) przyporządkowuje się leżące obok siebie pola siatki, w które wpisuje się wartości funkcji. Każdemu wierszowi zwykłej tabeli prawdy odpowiada tu jedna kratka w siatce Karnaugha. Efekt "sąsiedztwa" jest tu zapewniony dzięki odpowiedniemu opisaniu wierszy i kolumn siatki kodem Gray'a. Podstawową własnością siatek Karnaugha jest prosta identyfikacja iloczynów (sum) , które podlegają sklejaniu, bowiem jedynkom(zerom) w kratkach przylegających do siebie bokami lub symetrycznie względem dowolnej zaznaczonej osi symetrii odpowiadają sąsiednie składniki KPS (czynniki KPI). Siatka Karnaugha dla 2 zmiennych: Siatka Karnaugha dla 3 zmiennych: Siatka Karnaugha dla 4 zmiennych: Siatka Karnaugha dla 5 zmiennych: Poszczególnym kratkom siatki można przypisać dziesiętne odpowiedniki binarnym słowom opisującym tę kratkę. Oczywiście istnieje pełna dowolność w podziale zmiennych na te, które opisują kolumny i te, które opisują wiersze. Pamiętać jednak trzeba, że wówczas zmieniają się liczby dziesiętne opisujące kratki, bowiem jest to konsekwencja zmiany kolejności bitów w słowie, np. z (x1 x2 x3 x4 x5) na (x5 x4 x3 x2 x1). Zasada mnemotechniczna polega na wpisywaniu liczb dziesiętnych do kratek siatki Karnaugha dla czterech zmiennych. Grupie 2^K jedynek (zer) funkcji, z których każda jest sąsiednia w stosunku do K innych jedynek (zer) tej grupy w siatce Karnaugha, można przyporządkować iloczyn (sumę), w którym(ej) wyrugowano K zmiennych. Wynika stąd praktyczny wniosek, że po wpisaniu do siatki Karnaugha jedynek (zer) funkcji, powinniśmy wyszukiwać w niej grupy jedynek (zer) o liczności 2, 4, 8, 16, 32, zaznaczając je obwiednią i dążąc do tego, aby to były grupy jak najbardziej liczne, ponieważ w ten sposób ruguje się większą liczbę zmiennych. Przykłady tworzenia grup sąsiednich kratek w siatce Karnaugha dla trzech zmiennych. Wyszukując grupy sąsiednie w sensie reguły sklejania należy pamiętać o sąsiedztwie prawej i lewej krawędzi siatek oraz górnej i dolnej krawędzi. Z tego powodu godnym uwagi jest poniższy rysunek : Ten sposób jest bardzo często pomijany przy tworzeniu grup jedynek (zer). Inne przykłady tworzenia grup sąsiednich kratek w siatce Karnaugha dla czterech zmiennych. Grupy jedynek (zer) opisujemy iloczynem (sumą) tylko tych zmiennych, bądź ich negacji, których wartość nie ulega zmianie przy opisie kratek tworzących grupę, stosując przy tym regułę, że w iloczynie (sumie) występować powinna zmienna xi bez negacji, jeśli przy opisie kratek tworzących grupę przyjmuje ona wartość 1 (0), bądź z negacją, gdy przyjmuje wartość 0 (1). Przykład tworzenia grupy mającej osiem kratek w siatce Karnaugha dla pięciu zmiennych. ALGORYTM POSTĘPOWANIA :

1.  Wpisać jedynki funkcji boolowskich do siatki Karnaugha, utworzonej dla odpowiedniej liczby zmiennych. 2.  Zakreślamy obwiednią grupy jedynek(zer), przestrzegając poniższych zasad : - grupa musi zawierać liczbę jedynek (zer) będącą potęgą liczby 2, - geometrycznie jest kwadratem bądź prostokątem, - zakreślamy grupy jedynek(zer) według reguł sąsiedztwa, tj. symetrycznie względem krawędzi siatki, bądź osi symetrii, - dążymy do tego by uzyskać jak najmniejszą liczbę grup, o jak najwyższej liczności jedynek(zer), - grupy mogą nachodzić na siebie, ale nie mogą zawierać się jedna w drugiej, - każda jedynka(zero) funkcji musi wchodzić w skład co najmniej jednej grupy w szczególności jeśli nie ma sąsiadów musi być opisana iloczynem pełnym, 3.  Uzyskanie w punkcie drugim grupy jedynek należy opisać odpowiednimi iloczynami(sumami); do iloczynu(sumy) wchodzą te zmienne, które nie zmieniają swojej wartości w opisie grupy, tzn. biorąc xi , gdy zmienna ta w opisie kratek tworzących grupę przyjmuje wartość równą 1 (0), bądź biorąc negację zmiennej xi , gdy zmienna ta przyjmuje wartość 0 (1). 4.  Uzyskane iloczyny (sumy) należy zsumować (przemnożyć), otrzymując w ten sposób normalną postać sum- NPS (normalną postać iloczynu- NPI). Uwaga - Bardzo często może się zdarzyć, że istnieje kilka równoważnych minimalnych postaci danej funkcji boolowskiej.

Funkcja boolowska nie w pełni określona - funkcja, która nie dla każdego zestawu argumentów posiada określoną wartość. Nie w każdym wierszu tabeli prawdy wpisano wartość 0, 1, czyli wpisano symbol obojętny {- , O , * }. Kratkom tym przypisujemy bądź wartość równą 1, gdy chcemy kratkę włączyć do tworzonej grupy, bądź 0, gdy nie chcemy jej włączać do grupy jedynek (dla KPI - odwrotnie). Decydując się na zaliczenie (bądź nie) kratki ze znakiem O do grupy mamy na uwadze to, by minimalizacja była jak najbardziej efektywna. Tak więc dowolność w traktowaniu symboli O sprzyja zawsze celom minimalizacji.

Układy kombinacyjne Układem kombinacyjnym (bez pamięci) nazywamy układ logiczny, w którym stan wyjść zależy tylko i wyłącznie od stanu wejść, co można przedstawić : gdzie : yj - wyjście układu; j= 1, 2, 3, ... , n xi - wejście układu; i= 1, 2, 3, ... , m - funkcja boolowska opisująca zachowanie j-tego wyjścia, zwana FUNKCJĄ WYJŚĆ. Ponieważ rzeczywiste układy fizyczne wnoszą opóźnienie, więc "odpowiedź" na wyjściach układu kombinacyjnego następuje po charakterystycznej dla danego wyjścia yj chwili w stosunku do momentu zmiany informacji wejściowej, co ostatecznie można przedstawić : Układy kombinacyjne konstruuje się używając typowych elementów kombinacyjnych, zwanych bramkami (GATES). Podstawowe bramki logiczne.

	AND (i) iloczyn
	OR (lub) suma
	NAND (nie i) negacja iloczynu
	NOR (nie lub) negacja sumy
	NOT (nie) negacja
	EXOR (suma modulo 2, suma wyłączająca, różnica symetryczna)

Układ kombinacyjny realizuje określoną formułę boolowską, poprzez ściśle określoną kompozycję składowych elementów, tj. bramek łączonych z zasadą, że wyjście bramki można połączyć z wejściami innych bramek. Nie wolno łączyć ze sobą wyjść bramek, poza tym w tej klasie układów nie wolno przy łączeniu dopuszczać do powstawania pętli, tzn. od każdego wejścia musi prowadzić droga do wyjścia. Błędne przypadki połączeń bramek. W układach kombinacyjnych do niektórych bramek dochodzą tylko sygnały z wejść układu, część bramek z kolei wytwarza sygnały przekazywane na wyjścia układu, a inna część bramek może pośredniczyć w połączeniach między wyżej wymienionymi grupami bramek. Uwagi te dotyczą układów bardziej złożonych o strukturze warstwowej. Celem stawianym w tym wykładzie jest uzyskanie odpowiedzi na dwa pytania: - jakie funkcje boolowskie są realizowane na wyjściach układu kombinacyjnego, gdy struktura, czyli sieć połączeń bramek   jest dana ? (ANALIZA) - jaka powinna być struktura układu kombinacyjnego, aby na swoich wyjściach realizował on zadane funkcje boolowskie ?   (SYNTEZA) SYNTEZA UKŁADÓW KOMBINACYJNYCH METODY ANALIZY UKŁADÓW KOMBINACYJNYCH 1.  "Symulacja układu kombinacyjnego na papierze" Zapisujemy na schemacie logicznym zestaw wartości binarnych na wejściach układu. Zgodnie ze strukturą połączeń pomiędzy bramkami i zasadą działania bramek określamy wyjścia poszczególnych bramek, posuwając się na schemacie logicznym od strony wejść do wyjść układu. Po określeniu stanu wyjść bramek stanowiących wyjścia układu wpisujemy ich stan w wierszu o odpowiednim numerze tabeli prawdy mającej 2^m wierszy i (m + n) kolumn ( m - liczba wejść, n - liczba wyjść ) Powyższą procedurę powtarzamy dla kolejnych zestawów wartości binarnych na wejściach aż do jej wyczerpania, tj. gdy wejściom układu przypiszemy wartości 11...1. Następnie znajdujemy formułę boolowską na podstawie otrzymanej tabeli prawdy. Jest to jednak metoda uciążliwa wymaga bowiem 2^m kroków. 2.  Metoda analityczna polega na tym, że na wyjściach bramek posuwając się od strony wejść układu na schemacie, zapisujemy zgodnie z zasadami działań bramek formuły boolowskie zależne od zmiennych, jakie wynikają ze schematu połączeń. Jeśli bramkami są bramki typu NAND i NOR, to stosując prawa de Morgana doprowadzimy formuły boolowskie do postaci sum iloczynów lub iloczynu sum. Następnie wystarczy sporządzić tabelę prawdy. Przykładowe zadanie projektowe: 1. Specyfikacja: Zaprojektować układ sterujący pracą grzejników G1 i G2. Sposób sterowania tymi grzejnikami jest uzależniony od temperatury(T) ustalanej za pomocą termometru kontaktowego według poniższych reguł : 2.  Tworzenie tabeli prawdy: Na podstawie opisu słownego sporządzamy tabelę prawdy układu kombinacyjnego, wcześniej ustalając niezbędną liczbę wejść i wyjść układu, jeśli nie wynika ona jednoznacznie z treści zadania. W tabeli prawdy na ogół kierujemy się zasadą, że sytuacjom z opisu słownego takim, gdzie jest mowa np. o "włączonym przycisku", "wysokim poziomie napięcia na czujniku", "zapalonej żarówce" bądź "włączonym silniku" przypisujemy jedynkę logiczną (u nas włączone grzejniki). Należy jednak uważnie rozstrzygnąć, czy z konieczności użycia dodatkowych bramek NOT, nie byłoby bardziej wskazane przypisanie "włączonemu przyciskowi" stanu zera logicznego. W technicznej realizacji jest nam bowiem obojętne, czy w stanie spoczynku przycisk jest podłączony do plusa czy do masy urządzenia, natomiast realizacja logiczna może się uprościć. Wynika stąd, że nie zawsze "warunki działania" musimy kojarzyć z jedynką logiczną, a "warunki nie działania " z zerem logicznym. W tym przykładzie stan pracy grzejników oznaczymy jako jedynkę logiczną. 3. Minimalizacja funkcji boolowskiej: Na podstawie tabeli prawdy określamy po przeniesieniu wartości funkcji do siatki Karnaugha, minimalną formułę(y) opisującą(e) układ. kreski w tabeli prawdy oznaczają dowolność wstawienia 0 bądź 1 Ponieważ zmienne x1 i x3 zmieniają swoją wartość w opisie grupy, nie zostają zatem uwzględnione podczas minimalnego zapisu funkcji boolowskiej (y1). Tym razem zostały stworzone dwie grupy. Zasada powstania pierwszego składnika sumy jest analogiczna jak w przypadku wyjścia y1. Druga część sumy pozbawiona została zmiennej x3 ze względu na zmianę swojej wartości (osiąga zarówno "0" jak i "1"), zaś zmienna x1 ulega negacji ponieważ grupa mieści się w kolumnie, gdzie przyjmuje ona wartość "0". Zmienna x2 jest afirmowana, ponieważ jest jedynką logiczną. 4.  Rysowanie schematu logicznego: Jest to ostatni etap syntezy, w którym w oparciu o otrzymaną funkcję(e) boolowską(skie) rysujemy schemat logiczny, czyli sieć połączeń między elementarnymi bramkami, dbając przy tym o pewną jednorodność rozwiązania, tzn. aby cały układ był skonstruowany w miarę możliwości z jednego typu bramek.

Synteza niekoniecznie musi zaczynać się od opisu słownego, a może w niektórych przypadkach zaczynać się od tabeli prawdy, a nawet w prostych przypadkach od formuły boolowskiej. Bywa i tak, że na podstwie opisu słownego można bezpośrednio napisać formułę boolowską, omijając tym samym etap tworzenia tabeli prawdy, np. polecenie "włącz silnik Y, gdy przycisk x1 jest włączony lub przycis x2 jest wyłączony i przycisk x3 jest włączony" jest równoważne formule :

---