Kurs Układy Logiczne – #2 – Algebra Boole'a, zmienne i funkcje logiczne

[Gieneq]

Spis treści

#1 – Wstęp i podział układów

Algebra Boole’a ciąg dalszy

W tej części kursu przyjrzymy się algebrze Boole’a ale tym razem pod kątem bardziej zaawansowanych zadań. Na początek krótka powtórka z kursu Techniki Cyfrowej.

W algebrze Boole’a posługujemy się wyłącznie dwiema wartościami:

• 1 = logiczna jedynka = stan wysoki = prawda,
• 0 = logiczne zero = stan niski = fałsz.

Choć są to tylko 2 wartości to możliwych operacji jakie przy ich pomocy da się wykonać całkiem sporo.

W przypadku układów logicznych 1 i 0 są wartościami jakie może przechować pojedynczy bit, ale także odnosi się to do sygnału jaki występuje na linii.

Podobnie jak w zwykłej algebrze, w algebrze Boole’a można zdefiniować pewną zmienną, np. x, która może przyjmować wartości: 1 lub 0. Na tych zmiennych również można wykonywać pewne operacje. Później zmienne te będą utożsamiane z sygnałami jakie wchodzą lub wychodzą z/do bloków logicznych (reprezentujące fizyczne połączenia) więc dobrze się z nimi zaznajomić.

Aksjomaty algebry Boole’a

Na początek warto wymienić aksjomaty (czyli niepodważalne prawdy) jakimi rządzi się algebra Boole’a. Zmienne nazwane x, y oraz z, które użyte są w przykładach, mogą przyjmować dowolne wartości (1 lub 0):

Kreska nad zmienną oznacza negację, czyli jeżeli x ma wartość 0 to x z kreską (pisane też ~x) przyjmie wartość 1 i odwrotnie. Bardziej czytelny zapis jest z kreskami lecz z racji ograniczeń środowiska w treści spotkamy falkę/tyldę ~.

Większość aksjomatów jest oczywista, ale ostatni może nie być taki prosty. Podobny wzór można spotkać na lekcjach matematyki w szkole, ale jego wynik jest zdecydowanie inny. Czy zatem aksjomat ten jest niepoprawny? Wszystko jest dobrze, trzeba tylko wziąć pod uwagę fakt, że w algebrze Boole’a dysponujemy jedynie wartościami 1 i 0. Spróbujmy jednak wyprowadzić tę zależność stosując inne aksjomaty:

Jak widać wzór się jednak zgadza i przy okazji pojawiła się ciekawa zależność x² = x zwana tożsamością. Takich wzorów jest więcej i zebrane zostały na ilustracji:

Znowu widać, że większość tożsamości jest w miarę oczywista, ale ostatnia wygląda podejrzanie. Czy gdyby po obu stronach pozbyć się x to czy okaże się że ~x*y to y? Sprawdźmy to:

Jak widać dla wartoś ci x = 1 i y = 1 element ~x*y nie przyjął wartości y (ale ostatecznie wynik zgodny jest ze wzorem). Dzieje się tak, gdyż skreślenie powtarzających się elementów (które wydaje się tu intuicyjne) jest skrótem myślowym oznaczającym odejmowanie. Co prawda występuje ono w zwykłej algebrze, a czy w algebrze Boola też? No właśnie…

W tym przypadku wzór przekształcono idąc od prawej strony, a czy macie pomysł na wyprowadzenie zaczynając od lewej? Podzielcie się rozwiązaniem w komentarzu.

Robiąc więcej przykładów szybko dojdziemy do pewnych typowych sytuacji, w których przydatne okażą się następujące wzory:

Wśród nich znajdują się najczęściej spotykane – prawa de Morgana oraz to co już udało się nam zauważyć przy wyprowadzaniu poprzedniej zależności, tzw. reguły pochłaniania. Nie są to żadne nowości, są to tylko zależności wynikające z fundamentalnych praw logiki – aksjomatów. Przykładowo regułę pochłaniania numer 17 użyto przy udowadnianiu posługując się „trikiem” mnożąc zmienną przez niezmiennik mnożenia 1.

Funkcje logiczne

Podobnie jak w zwykłej algebrze, w algebrze Bloole’a również można wprowadzić pojęcie funkcji. Różnica polega na tym jakie otrzymuje argumenty – będą to zmienne boolowskie przyjmujące tylko 2 wartości. Funkcje są podstawą dalszych rozważań zatem warto poświęcić im uwagę.

Na początek przyjrzyjmy się prostej funkcji sumującej 2 zmienne:

Jak widać funkcja nazwana f przyjmuje za argumenty 2 zmienne: x oraz y. Zaś wzór (zależność którą opisuje, pewna logika) zdefiniowana jest po prawej stornie. Czyli wszystko tak samo jak w przypadku zwykłych funkcji algebraicznych i zmiennych, z tym że musimy pamiętać, że zarówno argumenty jak i wynik funkcji zawierają się w zbiorze 2 wartości: {0, 1}.

Opis funkcji podając wzór (jak ma to miejsce wyżej) nie jest jedyną metodą. Inny sposób często pojawiający się w temacie układów cyfrowych to postać dana tabelą nazywaną tabelą prawdy.

Tabela ta zawiera w sobie wszystkie możliwe kombinacje argumentów i wyznaczone dla nich wyniki funkcji. Przykładowo, dla wzoru na sumę logiczną podanego wyżej tabela prawdy wygląda następująco:

Dodatkowo w tabeli rozpisano operację dodawania aby podkreślić pewien fakt, który szczególnie widać w ostatnim wierszu. Ale czy nie jest to błąd? Jak to 1+1 = 1? Warto przypomnieć sobie co w logice oznacza dodawanie a co mnożenie.

• suma (x + y) to tak zwana alternatywa, słowne „lub” czyli logiczne OR – jeden z warunków (lub oba) muszą być prawdziwe aby wynik był prawdziwy,
• mnożenie (x * y) to tak zwany iloczyn, słowne „i” (tu już nie kojarzy się z jakąś możliwością wyboru) oznacza logiczne AND – oba warunki muszą być prawdziwe aby wynik był prawdziwy.

Czyli 1 + 1 inaczej odczytane jako: „prawda lub prawda” daje w wyniku 1 czyli „prawdę”, nieprawdaż? Poza tym w zbiorze możliwych rozwiązań {0, 1}, które bardziej pasuje?

Dla czytelników zaprzyjaźnionych z techniką komputerową i systemem binarnym może to być skandal, gdyż suma 2 liczb binarnych o wartości 1 powinna dać w przypadku rejestru długości 1 (czyli 1 bitowej komórki pamięci) wartość 0 i 1 na bicie przeniesienia. Jest to jednak inny rodzaj operacji dodawania.

W językach programowania, na przykład w C++, uwzględnione są 2 rodzaje operacji: suma i iloczyn arytmetyczne oznaczone znakami + i * oraz suma i iloczyn bitowy (logiczne) oznaczone znakami | i &. Przykładowo 2 liczby o wartości 1 zależnie od operacji sumy arytmetycznej i bitowej przyjmą 2 różne wartości:

int x = 0b1; // DEC 1
int y = 0b1; // DEC 1
int artmSum = x + y; // 0b10 DEC 2
int bitSum = x | y; // 0b01 DEC 1

Jak zatem widzimy w logice Boole’a może dochodzić w pewnym stopniu do utraty informacji – przechodząc z funkcji danej wzorem, na tabelę został utracony pewien szczegół. Gdyby chcieć odtworzyć funkcję daną tabelą prawdy to otrzymany wzór niekoniecznie może pokrywać się z tym danym na początku. Zjawisko to jest podstawą operacji minimalizacji funkcji logicznych co zostanie omówione nieco dalej.

Zajmijmy się innym przykładem – funkcja XOR. Jeżeli opisać ją słownie to ma ona zwrócić 1 tylko wtedy, gdy na wejściu x albo na wejściu y jest 1. Słowo „albo” jest tu istotne, gdyż wyklucza ono możliwość wyboru obu opcji (słowo „lub” dałoby tu większą swobodę wyboru).

Wzór funkcji XOR wygląda następująco:

Prześledźmy teraz jej działanie przy pomocy tabeli prawdy:

Widać wyraźnie, gdy tylko jeden z argumentów ma wartość 1 to XOR zwraca 1.

Ciekawe, że można spotkać nieco inną postać tej funkcji. Do tego tematu wrócimy w kolejnych częściach kursu, ale teraz w ramach ćwiczenia spróbujmy przekształcić wzór funkcji tak by zamienić iloczyny na sumy i odwrotnie.

Do tego zadania idealnie nadadzą się prawa de Morgana. Aby móc je jednak zastosować potrzeba posłużyć się pewnym trikiem, który opisano w tożsamości 13 – podwójna negacja nie wpływa na wartość. Zatem zacznijmy od podwójnego zanegowania obu iloczynów:

Następnie stosując oba prawa de Morgana przekształcono wzory tak by pozbyć się jednych z dodanych negacji oraz aby pośrodku znalazł się iloczyn:

Trik z podwójną negacją może wprowadzić zamieszanie, ale otwiera on zupełnie nowe możliwości. Na początek potraktowano w ten sposób oba iloczyny, tak by uzyskać typowe sytuacje opisane wzorami 15 i 16. Następnie po zastosowaniu elementarnych przekształceń jeszcze raz zastosowano prawa de Morgana aby pozbyć się wspólnej negacji i gotowe!

Metoda możliwe, że nie jest najszybsza. Jeżeli udało się Wam dojść do wyniku inną drogą to podzielcie się tym w komentarzach. Niemniej widać wyraźnie, że istnieje inna forma wzoru, który daje te same wyniki (można sprawdzić w tabeli). Widać też że sumy zostały zamienione z iloczynami i odwrotnie... czy istnieje jakiś związek, a co za tym idzie sformalizowana metoda? Tak istnieje, ale o tym później. Teraz przyjrzyjmy się nieco bardziej rozbudowanym funkcjom z 2 i 3 argumentami i spróbujmy coś w nich uprościć.

Upraszczanie funkcji

Czasem zachodzi potrzeba uproszczenia rozbudowanego wzoru funkcji logicznej. Kilka z takich „trików” przedstawiono już wcześniej przy podawaniu wzorów i tożsamości algebry Boole’a.

Na ten moment w ramach ćwiczeń zajmijmy się uproszczeniem kolejnych przykładów. W zwykłej algebrze wyniki można sprawdzić podstawiając dane do wzorów, spisując wyniki w tabelce lub sporządzając wykres. W algebrze Boole’a dobrym sposobem na sprawdzenie poprawności jest tabela prawdy.

Cel upraszczania

Warto wspomnieć o tym co jest celem upraszczania, bo dla jednego wyznacznikiem prostego wyrażenia może być brak negacji w wyrażeniu, dla innego brak nawiasów. Tu podczas upraszczania najważniejsze jest zmniejszenie liczby zmiennych w składnikach, a także zmniejszenie liczby składników. Innymi słowy im mniej sum i iloczynów tym lepiej. Najlepiej też, aby unikać zagłębień i uzyskać jednej z dwóch postaci:

• sumy iloczynów,
• iloczynu sum.

Jest to istotne ponieważ mniejsza liczba sum i iloczynów sprawi, że finalny układ realizujący funkcję logiczną będzie miał w swojej konstrukcji mniej bramek logicznych, a co za tym idzie będzie tańszy. Jak do fizycznego układu mają się sumy i iloczyny zostanie wyjaśnione później.

Przykład 1

Na początek przeanalizujmy następujący przykład:

Tam gdzie widać jakąś większą negację można próbować zastosować jedno z praw de Morgana. W tym przypadku był to strzał w dziesiątkę! Nad ~x i y dodajemy podwójną negację i podstawiamy:

Pozostaje reguła sklejania (nr 19) i w tych 3 szybkich krokach rozbudowane wyrażenie logiczne sprowadziliśmy do prostej postaci. Okazało się też, że wynik, choć początkowo mocno związany ze zmienną y wcale od niej nie zależy!

Przykład 2

Przejdźmy teraz do kolejnego przykładu, nieco bardziej zawiłego i tym razem z 3 zmiennymi:

Jak się za to zabrać? Są tu 2 drogi: mozolna i sprytna. Sprytne podejście pozwala na zredukowanie tego potworka w 2 ruchach przy pomocy jednej zależności (podpowiem znajdzie się ona w 3 grupie wzorów). Potraktujmy to jako pracę domową, tu zaś przejdźmy dłuższą drogą wykorzystując inne zależności.

Zacznijmy od bardzo sugestywnej negacji, aż prosi się o zastosowanie praw de Morgana (tu uwaga prawa te można zastosować do więcej niż 2 składników):

Faktycznie dało się coś uzyskać… mamy teraz sporo mnożeń i jedną sumę, nie jest dużo lepiej ale nie mamy tej brzydkiej negacji.

Widać wciąż większe negacje, może kolejne zastosowanie praw de Morgana pomoże:

Teraz można by spróbować wymnożyć każdy z każdym i wynik gotowy. Ale da to sumę 13 składników – jedna źle postawiona kreska i mamy błędny wynik, a w logice Boola’a odpowiedzi są tylko dobra albo zła („albo” czytaj XOR).

To może jednak nabierzmy trochę sprytu i skorzystajmy z aksjomatu numer 8, musimy tylko przesunąć jeden z nawiasów – pamiętamy, że w algebrze Boole’a mnożenie jest przemienne:

Zaczyna to wyglądać  obiecująco. Co więcej jeżeli przyjrzymy się, to można zauważyć po raz kolejny ten sam sposób postępowania – jeżeli wyrażenia w żółtych ramkach potraktuje się jak zmienne logiczne to znowu można zastosować aksjomat 8.

W sytuacjach, gdy nie wiemy czy coś pasuje do wzoru, warto wprowadzić tymczasową zmienną zastępującą większe wyrażenie logiczne lub uporządkować zmienne stawiając nawiasy.

Takie mnożenie nie stanowi problemu, po jego rozwinięciu pozostaje suma: 0 + 0 więc wyrażenie ulega sporemu uproszczeniu do postaci, gdzie wystarczy użyć regułę pochłaniania i gotowe:

Nie znając na pamięć reguły pochłaniania można zastosować trik z niezmiennikiem mnożenia.

Jak widać poszliśmy drogą nieco okrężną, ale czegoś się nauczyliśmy. Jak można zauważy w sytuacji, gdzie użyliśmy aksjomat 8 można było spróbować zastosować go dla 3 składników, gdyż w każdym występowała zmienna ~z. Sprawdźmy jak by to wyglądało, gdybyśmy od razu podstawili do wzoru dla 3 składników:

Jak widać zgadza się!

Dla chętnych można sprawdzić tabelami prawdy poprawność tego uproszczenia dla wejściowego wzoru i tego uzyskanego po uproszczeniu. Uzyskana tabela będzie jednak większa od poprzednich, zatem warto wspomnieć jak tworzyć tabele dla więcej niż 2 zmiennych.

Dygresja o tworzeniu tabel

Skąd mam wiedzieć jak dużo miejsca potrzebuję na narysowanie tabeli prawdy? Zadanie to wyznaczenie liczby wierszy tabeli w zależności od liczby zmiennych logicznych.

Wiemy, że dla 2 zmiennych mamy 4 wiersze. Jak to wyznaczyć? Przyda się tu nieco kombinatoryki i zadanie to staje się proste. Dysponując 2 zmiennymi pada pytanie: „Ile różnych wartości przyjmuje pierwsza zmienna?” Odpowiedź to moc zbioru {0, 1} czyli liczba elementów = 2. Teraz to samo pytanie dla drugiej zmiennej i odpowiedź ta sama czyli 2. Gdyby mieć 3 i kolejną zmienną odpowiedź to dalej 2.

To teraz wzór: liczba możliwych kombinacji to iloczyn tego co wyznaczyliśmy powyżej, czyli liczby możliwych wartości jakie przyjmuje każda zmienna. Jak widać mamy same 2 zatem wzór upraszcza się do postaci (wynik funkcji f w tabelach nie jest istotny):

Widać zatem że przy 4 zmiennych trzeba się już sporo napracować. Pozostaje jeszcze pytanie jak sprawnie uzupełniać możliwe zmienne, tak by dokładnie pokryć wszystkie kombinacje? Tu również jest konkretna metoda:

W tabeli zaznaczono kolorami 0 i 1. Wypełnianie zaczynamy od pierwszego wiersza samych zer. Następnie przechodzimy do skrajnej, prawej kolumny (na ilustracji zmienna z) i idziemy w dół na przemian pisząc 1 i 0.

Następnie przechodzimy do kolumny po lewej stronie (zmienna y), dopełniamy zera żeby były 2 i znowu na zmianę 1 i 0 ale tym razem ze skokiem co 2. W kolejnej kolumnie (zmienna x) uzupełniamy zera ale tym razem do 4 i resztę 1 i 0 znowu ze skokiem ale 4. I tak dalej… dla 4 zmiennych skrajna lewa kolumna będzie mieć skok co 8, dla 5 zmiennych skrajna lewa będzie mieć skok co 16, itd.

Co prawda w konstrukcję tabeli o więcej niż 4 zmiennych raczej nie wejdziemy, ale warto pamiętać o tej metodzie. W dalszych częściach kursu okaże się bardzo praktyczna przy nauce kodu Grey’a.

Przykład 3

Na tym koniec dygresji, wracamy do ostatniego przykładu:

Tym razem nie wygląda tak strasznie, nie ma żadnych zagłębień w wielokrotne negacje, same sumy, iloczyny, nie takie trudne, co prawda 3 zmienne ale wygląda obiecująco.

To może spróbujmy użyć aksjomat 7:

Coś się zmieniło, po prawej stornie widzimy wzór na XOR, ale co dalej?

To może reguła sklejania numer 19? Też ciężko… aby skleić parę musi w niej być wyraźnie widoczna część zmiennych prostych i zanegowanych, a tu każdy iloczyn ma zupełnie różne składniki.

Można kontynuować podchodzenie do tego przykładu, ale rozwiązanie niestety jest takie jak sam przykład. Innymi słowy tego nie da się uprościć. Jak to możliwe?

Wynika to z faktu, że zmienne te nie są ze sobą w żaden sposób powiązane, zilustrujemy to w kolejnych częściach kursu posługując się tablicami Karnough. Na ten moment zwróćmy jeszcze uwagę na próbę poradzenia sobie z tym przykładem przy pomocy reguł sklejania.

Reguły sklejania w upraszczaniu

Jeżeli spojrzymy na reguły sklejania z tabelki to można zauważyć ich siłę w procesie upraszczania:

W każdej z nich kompletnie zredukowana zostaje jedna zmienna, a czy nie jest to celem upraszczania, który podano na wstępie? Zatem sklejanie jest podstawową metodą minimalizacji czy też upraszczania, wymaga jednak pewnych warunków.

Jak zauważyliśmy w przykładzie 3, żaden składnik nie nadawał się do podstawienia do wzoru. Dzieje się tak gdyż konieczne jest wyróżnienie zmiennych w postaci prostej i zanegowanej. O ile dla 2 zmiennych znalezienie pary gdzie występuje jakiś x i y oraz ~y nie jest trudne, to co gdy mamy więcej zmiennych? Przeanalizujmy kolejny przykład:

To samo co w przykładzie 3? Nie, nie – różnica jest w drugim składniku – doszła tam negacja. Jedna negacja, a już można coś skleić:

Faktycznie działa, pozbyliśmy się z. To pytanie: jak ułożyć negacje, żeby dało się usunąć z drugiej pary z? Może tak:

Dodając negację nad zmienną y udało się otworzyć drogę na drugą redukcję i zmienna z zniknęła po uproszczeniu.

Widzimy zatem, że aby zmienna kompletnie zniknęła z wyrażenia, muszą zajść pewne szczególne warunki. Jak widzieliśmy wcześniej, gdy są tylko 2 zmienne potrzeba aby usuwana zmienna wystąpiła 1 raz w postaci prostej i 1 raz w postaci zanegowanej. Tutaj musiała być 2 razy w postaci prostej i 2 razy w postaci zanegowanej, przy czym w składnikach musiały wystąpić pary tych samych iloczynów.

Podobne zjawisko można zaobserwować przy minimalizacji iloczynu sum.

Zatem widzimy, że są sytuacje, gdzie jedna czy dwie negacje mogą zadecydować o tym czy da się uprościć wyrażenie czy też nie. Obserwacja ta, jest podstawą działania wspomnianej metody tablic Karnough.

Podsumowanie

Gratulacje! Przebrnąłeś przez sporą porcję czegoś na kształt matematyki. Choć w logice boolowskiej zmienne przyjmują tylko 2 wartości to i tak można się w nich nieźle pogubić.

W ramach pracy domowej dobrze jest spróbować usunąć zmienną y, a następnie x z ostatniego przykładu. Obserwacja tego jak powinny być ułożone negacje będzie pomocna w kolejnej części, w której poruszona zostanie bardzo istotna kwestia – jak w praktyce wyglądają funkcje logiczne i jakie przełożenie na rzeczywistość ma minimalizacja funkcji logicznych.

Dodatki

Do pobrania plakat z najważniejszymi informacjami z tej części kursu w formacie PNG i PDF.

kurs_uklady_logiczne_plakat_logika_boolea.pdf

Edytowano Marzec 28, 2021 przez Gieneq

[cd2dot0]

Co prawda artykuł jest sprzed 3,5 roku, ale ponieważ wciąż nie doczekał się rozwiązań zadań domowych (a powinien, bo jest napisany bardzo solidnie), to poniżej przedstawiam swoje własne rozwiązania:

1. Wyprowadzenie wzoru x + (~x)y = x + y od lewej strony:
2. Zamiana sumy iloczynów na iloczyn sum dla funkcji XOR(x,y) w inny sposób:
3. Rozwiązanie przykładu nr 2 w krótszy sposób:
4. Usunięcie zmiennej x oraz zmiennej y poprzez dodanie odpowiednich negacji (zaznaczone strzałkami) do wyrażenia z przykładu nr 3:

[Krysom]

Dnia 19.02.2024 o 21:35, cd2dot0 napisał:

Co prawda artykuł jest sprzed 3,5 roku, ale ponieważ wciąż nie doczekał się rozwiązań zadań domowych (a powinien, bo jest napisany bardzo solidnie), to poniżej przedstawiam swoje własne rozwiązania:

1. Wyprowadzenie wzoru x + (~x)y = x + y od lewej strony:
2. Zamiana sumy iloczynów na iloczyn sum dla funkcji XOR(x,y) w inny sposób:
3. Rozwiązanie przykładu nr 2 w krótszy sposób:
4. Usunięcie zmiennej x oraz zmiennej y poprzez dodanie odpowiednich negacji (zaznaczone strzałkami) do wyrażenia z przykładu nr 3:

Metoda wyprowadzenia wzoru jest jasna i zrozumiała. Wykorzystanie praw de Morgana i tabeli prawdy XOR sprawia, że jest ona dostępna dla osób na każdym poziomie umiejętności.