 |
ŚFiNiA
ŚFiNiA - Światopoglądowe, Filozoficzne, Naukowe i Artystyczne forum - bez cenzury, regulamin promuje racjonalną i rzeczową dyskusję i ułatwia ucinanie demagogii. Forum założone przez Wuja Zbója.
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
rafal3006
Opiekun Forum Kubusia
Dołączył: 30 Kwi 2006
Posty: 35364
Przeczytał: 23 tematy
Skąd: z innego Wszechświata
Płeć: Mężczyzna
|
 Wysłany: Sob 12:02, 16 Sie 2008 Temat postu: Fundamenty algebry Boole'a - Elementarz |
|
|
Proste jest piękne
Aksjomat logików praktyków:
Jak logicznie myślimy, tak matematycznie zapisujemy. Mówimy „NIE” zapisujemy (~), mówimy „i” zapisujemy AND(*), mówimy “lub” zapisujemy OR(+), w implikacji mówimy “musi” zapisujemy ( =>), mówimy “może” zapisujemy (~>).
Fundamenty algebry Boole’a - Elementarz
Części:
Fundamenty algebry Boole'a - Elementarz
Fundamenty algebry Boole'a - Implikacja
Fundamenty algebry Boole'a - Logika człowieka
Autor: Kubuś
Kubuś - wirtualny, Internetowy Miś
W pracach nad teorią implikacji bezcennej pomocy udzielili Kubusiowi przyjaciele:
Irbisol (sfinia), Macjan (sfinia), Miki (sfinia), Rafał3006 (sfinia), WujZbój (sfinia)
Wielkie dzięki !
Szczególne podziękowania Wujowi Zbójowi za jego nieskończoną cierpliwość w dyskusjach z Kubusiem.
Spotkało się pięciu odpowiednich ludzi w odpowiednim miejscu i czasie, gdyby zabrakło któregokolwiek ogniwa ta teoria nie mogłaby zaistnieć.
To jest elementarz przy pomocy którego chciałbym poznać algebrę Boole’a, gdybym miał znowu 16 lat.
Kubuś
Spis treści:
1.0 Notacja
1.1 Jedynka i zero, najważniejsze cyfry w naszym Wszechświecie
2.0 Fundament algebry Boole’a
2.1 Definicja iloczynu logicznego
2.2 Definicja sumy logicznej
2.3 Definicja negacji
2.4 Najważniejsze twierdzenia algebry Boole’a
3.0 Logika dodatnia i ujemna
3.1 Fizyczne sposoby przejścia z logiki dodatniej na ujemną
4.0 Przejście z kodu zero-jedynkowego do równań w algebrze Boole’a
4.1 Przejście z tabel zero-jedynkowych do równań algebry Boole’a
5.0 Logika dodatnia i ujemna w implikacji
5.1 Obietnica
5.2 Groźba
5.3 Wykresy czasowe w algebrze Boole'a
6.0 Matematyczne operatory logiczne
6.1 Lista operatorów logicznych
6.2 Związek algebry Boole’a z rzeczywistością
6.3 Jak działają operatory logiczne
7.0 Tablice logiki
7.1 Tablica logiki dla operatorów OR, NOR, AND, NAND
7.2 Tablica logiki dla operatorów <=>, XOR, =>, ->, ~>, <-
Dodatek A
Dowodzenie twierdzeń implikacyjnych w algebrze Boole’a
Wstęp.
Sens implikacji w obietnicach i groźbach w języku mówionym to po prostu prawo do wręczenia nagrody przy nie spełnionym warunku nagrody (implikacja prosta = akt miłości) oraz prawo do darowania dowolnej kary przy spełnionym warunku kary (implikacja odwrotna = akt łaski). Myślę, że o wiele łatwiej jest nauczyć pięknej algebry Boole’a młodego człowieka który nic o niej nie wie, niż przekonać zawodowego logika że w temacie implikacji jest w błędzie. Dlatego właśnie teoria implikacji prostej i odwrotnej zaczyna się od zupełnego zera, czyli od fundamentów algebry Boole’a. Myślę, że wiedza w elementarzu przedstawiona jest w inny sposób niż to czynią podręczniki szkolne, mam nadzieją że prostszy i ciekawszy. Jest tu wiele nowości np. logika dodatnia i ujemna w algebrze Boole'a, odkrycie i nazwanie wszystkich 16 matematycznych operatorów logicznych ... Zachęcam do przeczytania elementarza zarówno początkujących jak i zawodowców.
1.0 Notacja
# - różne
* - symbol iloczynu logicznego (AND), w mowie potocznej spójnik 'i'
+ - symbol sumy logicznej (OR), w mowie potocznej spójnik "lub"
~ - przeczenie, negacja (NOT), w mowie potocznej przeczenie "nie"
~(...) - w mowie potocznej "nie może się zdarzyć że ...", "nie prawdą jest że ..."
Logika dodatnia:
1 = PRAWDA
0 = FAŁSZ
Y=A+B*C
A,B,C… - zmienne binarne (dwuwartościowe) mogąca przyjmować w osi czasu wyłącznie wartości 0 albo 1
Y - funkcja logiczna zmiennych binarnych mogąca przyjmować w osi czasu wyłącznie wartości 0 albo 1
1.1 Jedynka i zero, najważniejsze cyfry w naszym Wszechświecie
Wszyscy doskonale znamy algebrę dziesiętną. To że człowiek liczy w systemie dziesiętnym wynika z dziesięciu palców u obu rąk. Gdybyśmy mieli osiem palców z całą pewnością liczylibyśmy w systemie ósemkowym. Dawno temu co niektórzy liczyli w systemie dwunastkowym co wynikało z dziesięciu palców plus dwie nogi. Komputery liczą w systemie dwójkowym (binarnym) bo te cyfry najłatwiej zrealizować w praktyce np.
Sygnały TTL:
0 = 0-0,4V - logiczne zero odpowiada napięciu 0V do 0,4V
1 = 2,4-5V - logiczne jeden odpowiada napięciu 2,4V do 5V
Gdyby człowiek miał tyko jedną rękę z dwoma palcami to na pewno liczylibyśmy w systemie dwójkowym i mielibyśmy naturalny system liczenia identyczny jak w komputerach. Wszystkie systemy liczenia są absolutnie równoważne. Człowiek wpisuje z klawiatury np. mnożenie dwóch liczb dziesiętnych i otrzymuje wynik na ekranie w postaci liczby dziesiętnej. W rzeczywistości komputer zamienia wprowadzone liczby dziesiętne na odpowiadające im liczby binarne, wykonuje mnożenie którego wynikiem jest liczba binarna po czym zamienia wynik na liczbę dziesiętną. Laicy nie mają o tym zielonego pojęcia, ale tak to w rzeczywistości się dzieje.
Fundamentem naszego Wszechświata są dwie cyfry zero i jeden.
Zastosowanie 0 i 1 w algebrze dwójkowej jak wyżej to pryszcz w porównaniu z zastosowaniem zera i jedynki w logice. Tu cyfry zero i jeden nie mają konkurentów, są najważniejsze. Cały nasz Wszechświat jest binarny: dobro-zlo, prawda-fałsz, nagroda-kara, miłość-nienawiść, życie-śmierć ...
Logika to algebra Boole’a w której występują wyłącznie dwie cyfry.
1 = PRAWDA
0 = FAŁSZ
1 = dobro (stopniowanie dobra jest nieistotne, dobro zawsze pozostanie dobrem)
0 = zło (stopniowanie zła jest nieistotne, zło zawsze pozostanie złem)
Każdy musi podjąć decyzję czy coś jest dla niego dobrem czy złem jak wyżej (algebra Boole’a).
Aksjomat:
DOBRO = nie ZŁO (D=~Z)
ZŁO = nie DOBRO (Z=~D)
Nigdy nie może być:
DOBRO=ZŁO (D#Z)
Jeśli cokolwiek JA uważam za dobro, to zaprzeczenie tego faktu będzie dla mnie złem.
2.0 Fundament algebry Boole’a
Fundamentem algebry Boole’a są definicje iloczynu i sumy logicznej oraz definicja negacji plus definicje implikacji o czym będzie później. DNA wszelkich komputerów to zaledwie suma logiczna albo iloczyn logiczny plus definicja negacji. Dysponując zaledwie dwuwejściową bramką OR (suma logiczna) oraz inwerterem realizującym negację można zbudować każdy komputer.
2.1 Definicja iloczynu logicznego
Iloczyn logiczny n zmiennych binarnych równy jest jeden wtedy i tylko wtedy gdy każda ze zmiennych jest równa jeden.
Y = 1*1*1*1...*1 = 1
albo definicja równoważna.
Iloczyn logiczny n zmiennych binarnych równy jest zeru gdy którakolwiek ze zmiennych równa jest zero
Y = 1*0*1*1....*1 = 0
Używanie zer i jedynek w definicjach to średniowiecze, to pisanie programu komputerowego w kodzie maszynowym. Po wynalezieniu komputera człowiek błyskawicznie zorientował się, że pisanie programu w kodzie maszynowym to horror i natychmiast wynalazł język symboliczny. Fundamentalnym językiem symbolicznym każdego mikroprocesora jest język asemblera.
Zapis definicji iloczynu logicznego w postaci symbolicznej
Y = A1*A2*A3 ... *An
gdzie:
* - symbol iloczynu logicznego w algebrze Boole’a (spójnik „i” w języku mówionym ang. AND)
A1,A2..An - zmienne binarne wejściowe, mogące przyjmować w funkcji czasu wyłącznie wartości 0 albo 1
Y - funkcja logiczna np. wartość zdania
Jak widać mnożenie logiczne niczym nie różni się od mnożenia algebraicznego.
Przykład:
Jutro pójdę do kina i do teatru
Y=K*T - zapis matematyczny zdania
Tabela prawdy iloczynu logicznego dla dwóch zmiennych:
| Kod: | K T Y=K*T
0 0 =0
0 1 =0
1 0 =0
1 1 =1 |
gdzie:
K= 1 - pójdę do kina.
K= 0 - nie pójdę do kina
T=1 - pójdę do teatru
T=0 - nie pójdę to teatru
* - iloczyn logiczny, w języku mówionym spójnik „i” (ang. AND)
Y - abstrakcyjna zmienna binarna wyjściowa, niedostępna w wypowiadanym zdaniu.
Y=1 - dotrzymam słowa wtedy i tylko wtedy gdy jutro pójdę do kina i do teatru, co widać w tabeli prawdy.
Y=0 - w przeciwnym przypadku skłamię
2.2 Definicja sumy logicznej
Suma logiczna n zmiennych binarnych równa jest zeru wtedy i tylko wtedy gdy każda ze zmiennych równa jest zero
Y = 0+0+0+0....+0 = 0
albo definicja równoważna
Suma logiczna n zmiennych binarnych równa jest jeden gdy którakolwiek ze zmiennych jest równa jeden.
Y = 0+1+0+0 ... +0 = 1 - wystarczy że jedna zmienna jest równa jeden
Y = 1+1+1+1 ....+1 = 1 - mogą być nawet wszystkie zmienne równe jeden
Zapis definicji sumy logicznej w postaci symbolicznej
Y = A1+A2+A3 ... +An
gdzie:
+ - symbol sumy logicznej w algebrze Boole’a (spójnik „lub” a języku mówionym ang. OR)
A1,A2..An - zmienne binarne wejściowe, mogące przyjmować w funkcji czasu wyłącznie wartości 0 albo 1
Y - binarna zmienna wyjściowa np. wartość zdania
Jak widać suma logiczna różni się od sumy algebraicznej. Wystarczy, że którakolwiek ze zmiennych wejściowych równa jest jeden i już całe wyrażenie przyjmuje wartość 1.
Przykład:
Jutro pójdę do lina lub do teatru
Y=K+T - zapis matematyczny zdania
Tabela prawdy sumy logicznej dla dwóch zmiennych:
| Kod: | K T Y=K+T
0 0 =0
0 1 =1
1 0 =1
1 1 =1 |
gdzie:
K=1 - pójdę do kina.
K=0 - nie pójdę do kina
T=1 - pójdę do teatru
T=0 - nie pójdę to teatru
+ - suma logiczna, w języku mówionym spójnik „lub” (ang. OR)
Y - abstrakcyjna zmienna binarna wyjściowa, niedostępna w wypowiadanym zdaniu.
Y=1 - dotrzymam słowa wtedy i tylko wtedy gdy jutro pójdę do kina lub do teatru, co widać w tabeli prawdy.
Y=0 - w przeciwnym przypadku skłamię
2.3 Definicja negacji
W algebrze Boole’a dostępne są wyłącznie cyfry 0 i 1, stąd łatwo wydedukować definicję negacji.
1=~0
0=~1
Definicja negacji w zapisie symbolicznym, to funkcja logiczna realizowana przez negator (ang. inverter)
Y=~A
~ - symbol negacji (odpowiednik przeczenia NIE w języku mówionym)
A - zmienna binarna wejściowa
Y - zmienna binarna wyjściowa
W technice cyfrowej fizyczna realizacja negatora jest niesłychanie prosta. Negator to czarna skrzynka do której dochodzi sygnał wejściowy A, zaś wychodzi sygnał wyjściowy Y = ~A np. w standardzie TTL.
Jeśli zmienna wejściowa A=1 to wyjście Y=0, jeśli zmienna wejściowa A=0 to Y=1.
Tabela prawdy przeczenia:
Prawo podwójnego przeczenia
A = ~(~A)
Dowód:
Twierdzenia w algebrze Boole’a dowodzi się niezwykle prosto budując tabele zero-jedynkowe dla wszystkich możliwych przypadków.
| Kod: |
A ~A ~(~A)
0 1 0
1 0 1
|
Identyczność kolumn A i ~(~A) dowodzi prawdziwości twierdzenia czyli:
A=~(~A)
Przykład:
Jestem uczciwy
Jestem NIEuczciwy
NIE jestem NIEuczciwy = jestem uczciwy
~(~U)=U
Aksjomaty znane ludziom od tysiącleci:
Nagroda to brak kary (nie kara)
N=~K - zapis matematyczny
Kara to brak nagrody (nie nagroda)
K=~N
Jeśli cokolwiek JA uznam za karę to zaprzeczenie tego faktu będzie DLA MNIE nagrodą i odwrotnie.
Oczywistym jest że zachodzi:
N = ~K = ~(~N) = N - na podstawie prawa podwójnego przeczenia
Przyjmijmy:
N (nagroda) = czekolada
Nieprawdą jest, że nie dostałem czekolady = dostałem czekoladę
Identyczne aksjomaty obowiązują dla prawda-fałsz, dobro-zło ... itd.
2.4 Najważniejsze twierdzenia algebry Boole’a
* - operator iloczynu logicznego (spójnik „i” ang. AND)
+ - operator sumy logicznej (spójnik „lub” ang. OR)
Twierdzenia wynikające bezpośrednio z definicji iloczynu i sumy logicznej
A*1 = A
A*0 = 0
A+1 = 1
A+0 = A
A*A = A
A+A = A
Fundamentalne prawa algebry Boole’a
A*~A=0
A+~A=1
Dowód:
| Kod: |
A ~A A*~A A+~A
0 1 0 1
1 0 0 1
|
Widać, że powyższe prawa obowiązują dla dowolnej wartości zmiennej binarnej A, która z definicji może przyjmować wartości wyłącznie 0 albo 1.
A(A+B) = A + A*B = A
Dowód:
A(A+B) = A*A +A*B = A+A*B = A
A+A*B=A
Jeśli A=0 to A+A*B=0 bo: A=0 i A*B=0
Jeśli A=1 to A+A*B=1 bo: A=1 przy A*B dowolnym (def. sumy logicznej)
... niezależnie od B CND.
Dowód powyższego równania przy pomocy tabel zero-jedynkowych:
| Kod: |
A B A+B A(A+B) A*B A+A*B
0 0 0 0 0 0
0 1 1 0 0 0
1 0 1 1 0 1
1 1 1 1 1 1
|
Równość kolumn A, A(A+B) oraz A+A*B dowodzi poprawności twierdzenia.
W technice cyfrowej powyższe połączenie sygnałów to bezsens czyli zero pożytku i sensu.
Prawa de'Morgana
A+B = ~(~A * ~B) - prawo zamiany sumy logicznej na iloczyn logiczny
A*B = ~(~A + ~B) - prawo zamiany iloczynu logicznego na sumą logiczną
Dowód prawa de'Morgana przy pomocy tabeli zero-jedynkowej.
A+B = ~(~A * ~B)
| Kod: |
A B A+B ~A ~B ~A*~B ~(~A*~B)
0 0 0 1 1 1 0
0 1 1 1 0 0 1
1 0 1 0 1 0 1
1 1 1 0 0 0 1
|
Jak widać w dowodzie tym sprawdzamy czy zachodzi równość dla wszystkich możliwych kombinacji zmiennych A i B. Identyczność kolumn A+B oraz ~(~A*~B) dowodzi poprawności prawa.
Dowody twierdzeń w postaci tabel jak wyżej to klasyka w algebrze Boole’a, prosta i piękna … tyle że uciążliwa przy dużej ilości zmiennych.
3.0 Logika dodatnia i ujemna
W Wikipedii w temacie "logika ujemna" pisze o związku 0 i 1 z poziomami napięć. Przydatność takiego pojęcia w matematyce jest równa zeru absolutnemu - zapomnijmy o tym.
Dowolne wyrażenie w algebrze Boole’a może przyjmować w osi czasu wyłącznie wartości 0 albo 1
A+B(C*D) .....
gdzie:
A,B,C,D… - zmienne binarne przyjmujące w osi czasu wyłącznie wartości 0 albo 1
Wyrażeniu jak wyżej możemy przypisać abstrakcyjną funkcję logiczną Y (wyjście cyfrowe).
Fizycznie, dowolna funkcja logiczna Y:
Y=A+B(C*D) .....
Może przyjmować w osi czasu wyłącznie wartości 0 albo 1.
Po przepuszczeniu jej przez prościutki negator otrzymamy funkcję ~Y będącą lustrzanym odbiciem funkcji Y. Logika ujemna (~Y) to lustrzane odbicie logiki dodatniej.
Oczywiście zachodzi:
Y = ~(~Y)
O tym, że logika ujemna istnieje można się łatwo przekonać w technice cyfrowej obserwując wszystko na przyrządzie pomiarowym zwanym oscyloskopem.
Spójrzmy na prawa de’Morgana od tej właśnie strony.
Definicja iloczynu logicznego.
Y=A1*A2 ….*An = 1 - wtedy i tylko wtedy gdy wszystkie zmienne są równe jeden
Definicja sumy logicznej.
Y=A1+A2 ….+An = 0 - wtedy i tylko wtedy gdy wszystkie zmienne są równe zeru
Jeśli:
Y=A1*A2 ….*An = 1 - wtedy i tylko wtedy gdy wszystkie zmienne są równe jeden
to:
~Y= ~A1+~A2…+~An = 0 - bo wszystkie składniki sumy logicznej są równe 0.
Oczywistym jest że:
Jeśli Y=1 to ~Y=0
Jeśli A1=1 to ~A1=0 itd.
Z ostatniego równania mamy:
Y= ~(~Y) = ~(~A1+~A2…+~An) = ~(0) = 1 czyli:
A1*A2 ….*An = ~(~A1+~A2…+~An) - prawo de’Morgana dla iloczynu logicznego
To samo rozumowanie możemy przeprowadzić dla sumy logicznej.
Jeśli:
Y = A1+A2…+An = 0 - wtedy i tylko wtedy gdy wszystkie zmienne są równa zeru
to:
~Y = ~A1*~A2…*~An =1 - bo wszystkie składniki iloczynu logicznego są równe 1
W tym przypadku mamy;
Jeśli Y=0 to ~Y=1
Jeśli A1=0 to ~A1=1 itd.
Z ostatniego równania mamy:
Y = ~(~Y) = ~(~A1*~A2…*~An) = ~(1) = 0
czyli:
A1+A2…+An = ~(~A1*~A2…*~An) - prawo de’Morgana dla sumy logicznej
Definicja.
Dowolnemu wyrażeniu w algebrze Boole’a możemy przypisać abstrakcyjną funkcję logiczną Y przyjmującą w osi czasu wartości binarne w zależności od zmiennych wejściowych.
Logika dodatnia - funkcja logiczna (wyjście cyfrowe) jest niezanegowana (Y)
Logika ujemna - funkcja logiczna (wyjście cyfrowe) jest zanegowana (~Y)
Prawa de’Morgana mówią o związkach między logiką dodatnią a ujemną na dowolnie długiej funkcji logicznej z dowolnie pomieszanymi operatorami.
Y=A+(B*C)
przejście do logiki ujemnej
~Y = ~A * (~B + ~C) - totalna negacja wszystkich zmiennych i wymiana operatorów na przeciwne tzn. OR(+) na AND(*) i odwrotnie.
Powrót do logiki dodatniej możemy wykonać na dwa sposoby:
I.
Y=A+(B*C) - ponowna totalna negacja wszystkich zmiennych i wymiana operatorów
II.
Y = ~(~Y) = ~[~A * (~B + ~C)] - zanegowanie logiki ujemnej
Twierdzenie 3.0
Przejście z logiki dodatniej (Y) do logiki ujemnej (~Y) polega na zamianie wszystkich zmiennych na przeciwne oraz wszystkich operatorów na przeciwne czyli AND(*) na OR(+) i OR na AND. Domyślna kolejność wykonywania działań w logice ujemnej zmieni się na: nawiasy, OR, AND.
Logika dodatnia:
A.
Y=A+B(C+~D)+E*~F - logika dodatnia (Y)
Domyślna kolejność wykonywania działań w logice dodatniej: nawiasy, AND(*), OR(+).
Przejście do logiki ujemnej:
B.
~Y=~A*~B+(~C*D)*~E+F - logika ujemna (~Y)
Domyślna kolejność wykonywania działań w logice ujemnej: nawiasy, OR(+), AND(*)
Przejścia powrotnego do logiki dodatniej dokonujemy w identyczny sposób.
C.
Y=A+B(C+~D)+E*~F - logika dodatnia (Y)
Domyślna kolejność wykonywania działań w logice dodatniej: nawiasy, AND(*), OR(+).
Zmiana kolejności wykonywania działań w logice ujemnej jest oczywista bowiem przy przejściu z logiki dodatniej do ujemnej AND zamienia się w OR.
Dowód twierdzenia:
I.
Y=A+B(C+~D)+E*~F - funkcja zapisana w logice dodatniej (Y)
Uzupełniamy brakujące nawiasy i operatory.
II.
Y=A+(B*(C+~D))+(E*~F) - logika dodatnia (Y)
negujemy wszystkie zmienne i wymieniamy operatory na przeciwne.
III.
~Y=~A*(~B+(~C*D))*(~E+~F) - logika ujemna (~Y)
Zauważmy, że jeśli przyjmiemy domyślną kolejność wykonywania działań w logice ujemnej (~Y): nawiasy, OR, AND to zbędne stanie się dokładanie nawiasów. Przejście powrotne do logiki dodatniej wykonujemy w identyczny sposób tj. zamieniamy wszystkie zmienne i operatory na przeciwne.
IV.
Y=A+(B*(C+~D))+(E*~F) - logika dodatnia (Y)
Aby powrócić do funkcji pierwotnej I usuwamy dołożone nawiasy.
Y=A+B(C+~D)+E*~F - oryginał, logika dodatnia (Y)
Zauważmy, że w tej metodzie uzupełniamy nawiasy przy przejściu z logiki dodatniej na ujemną oraz usuwamy je przy przejściu powrotnym by dojść do oryginału. W sumie niepotrzebna syzyfowa praca bowiem o fakcie zapisania funkcji w logice ujemnej informuje precyzyjnie przeczenie przy jej nazwie (~Y).
Zauważmy, że prawo de’Morgana pozwala w prosty sposób zamienić operatory na przeciwne w dowolnym fragmencie nawet nieskończonej funkcji logicznej. Wystarczy dowolny fragment ciągu ująć w nawiasy, postawić przed nimi znak przeczenia ~, zaś w środku tych nawiasów zamienić wszystkie zmienne i operatory na przeciwne. W tym przypadku bezpieczniej będzie uzupełnić brakujące nawiasy domyślne, aby nie pogubić się w kolejności wykonywania działań.
3.1 Fizyczne sposoby przejścia z logiki dodatniej na ujemną
Wyobraźmy sobie, że dysponujemy fizyczną bramką OR (np. układ 7432) mającą dwa wejścia A i B oraz jedno wyjście Y.
Bramka ta realizuje funkcje logiczną:
Y = A + B
Najprostsze przejście do logiki ujemnej to zanegowanie wyjścia Y.
~Y = ~(A+B)
... czyli wystarczy dołożyć jeden prościutki negator na wyjściu Y i mamy dostępny sygnał ~Y.
Przejście równoważne na to negacja wszystkich sygnałów i wymiana operatorów na przeciwne czyli:
~Y = ~A*~B
W tym przypadku musimy użyć trzech negatorów, dwóch na wejściu do negacji sygnałów A i B, oraz jednego na wyjściu do negacji sygnału wyjściowego Y. W miejsce bramki OR należy użyć bramkę AND.
Jest jeszcze jeden sposób uzyskania funkcji ~Y, bardzo nietypowy, ale możliwy do realizacji ... to coś w rodzaju my jeździmy prawą strona a Anglicy lewą.
W powyższych równaniach zakładaliśmy następujące poziomy sygnałów logicznych w standardzie TTL.
0 = 0-0,4V - zero odpowiada napięciu 0 do 0,4 Volta
1 = 2,4-5V - jeden odpowiada napięciu 2,4 do 5 Volt
To co wyżej to sprawa czysto umowna np. umawiamy się, że w Polsce jeździmy prawą stroną.
Równie dobrze moglibyśmy przyjąć:
0 = 2,4-5V - zero odpowiada napięciu 2,4 do 5 Volt
1 = 0-0,4V - jeden odpowiada napięciu 0 do 0,4 Volta
Będziemy wówczas Anglikami czyli umawiamy się, że jeździmy lewą stroną.
Zauważmy, że przy tej notacji sygnały na naszej bramce OR (układ 7432) mamy zanegowane z definicji czyli w tym przypadku ten fizyczny układ scalony realizuje funkcję.
~Y = ~A + ~B - z definicji mamy logikę ujemną (Anglik)
Przejdźmy do logiki dodatniej negując wszystkie sygnały i operatory.
Y = A*B - logika dodatnia, fizyczny układ 7432 (Anglik)
Jak widać, każdy „Anglik” będzie święcie przekonany że fizyczny układ 7432 realizuje iloczyn logiczny. Tymczasem Polak z uporem maniaka będzie twierdził, że Anglik to głupek bo układ 7432 realizuje sumę logiczną.
Y=A+B - logika dodatnia, ten sam fizyczny układ 7432 (Polak) !
Z powyższego mamy logikę ujemną:
~Y = ~A * ~B - logika ujemna (Polak)
Zauważmy, że ten sam układ fizyczny widziany z różnych punktów odniesienia wygląda zupełnie inaczej, zarówno po stronie logiki dodatniej Y jak i logiki ujemnej ~Y.
Jeśli Anglik i Polak nie ustalą wspólnego punktu odniesienia czyli wspólnego standardu sygnałów to mogą się pozabijać ...
Z powyższego powodu w katalogu spotkamy zapis:
7432
Y = A + B - logika dodatnia
Dopisek logika dodatnia informuje, że stosuje się notację Polaka (umownie dodatnią). Anglik ma prawo twierdzić, że to jego logika jest logiką dodatnią a nasza ujemną. Jak widać wszystko zależy od punktu odniesienia, zaś dyskusja bez ustalenia wspólnego punktu odniesienia nie ma sensu.
Encyklopedyczna definicja logiki ujemnej dotyczy właśnie interpretacji sygnałów ... i jest bez sensu gdyż jej użyteczność w matematyce jest zerowa. Wszyscy producenci i wszyscy ludzie na ziemi stosują „logikę dodatnią” czyli polską. Nie ma obawy, że jeśli zamówimy gdziekolwiek bramkę OR to w rzeczywistości dostaniemy AND.
Logika ujemna w interpretacji punktu 3.0 jest natomiast bardzo użyteczna i tylko o takiej logice będziemy mówić.
4.0 Przejście z kodu zero-jedynkowego do równań w algebrze Boole’a
Wszyscy wiedzą jak udowodnić dowolne równanie w algebrze Boole’a np.
A+B = ~(~A*~B) - prawo de’Morgana
Trzeba po prostu rozpisać wszystkie możliwe kombinacje zmiennych A i B. W kolumnach wynikowych widać czy zachodzi tożsamość.
Wielu logików praktyków (tych od scalaków) ma problemy z przejściem odwrotnym czyli z tabel zero-jedynkowych do równań w algebrze Boole’a. Świadczy o tym sporo błędów w katalogach układów cyfrowych np.
Y=1 wtedy i tylko wtedy gdy A=1 i B=0 i C=0
W katalogu firmy Intel widnieje taka bzdura:
Y=A*B*C
National też popełnił błąd, zaś Texas zapisał poprawnie ale w logice ujemnej (na schemacie jest bramka AND a w zapisie funkcji występuje OR).
Poprawny zapis powyższego równania w logice dodatniej (wyjście Y bez negacji) wynika bezpośrednio z definicji iloczynu logicznego i wygląda tak:
Y=A*~B*~C
Definicja iloczynu logicznego:
Iloczyn logiczny n zmiennych binarnych równy jest jeden wtedy i tylko wtedy gdy każda składowa iloczynu jest równa jeden.
Zatem jeśli w zapisie słownym był warunek:
B=0 to do równania należy wstawić ~B=1 itd.
Zapiszmy to samo w logice ujemnej czyli wyjście Y zanegowane (~Y).
Y=1 <=> A=1 i B=0 i C=0
Zapis powyższej równoważności w logice ujemnej wygląda tak:
~Y=~A+B+C
co wynika bezpośrednio z definicji sumy logicznej:
Suma logiczna n zmiennych binarnych równa jest zeru wtedy i tylko wtedy gdy każda składowa sumy jest równa zeru.
Jeśli zatem w opisie słownym mamy:
Y=1 to do równania wstawiamy ~Y=0
A=1 to do równania wstawiamy ~A=0
zmienne B i C mają z założenia wartość zero więc je tylko przepisujemy.
Tym rozumowaniem odkryliśmy znowu prawa de’Morgana.
Zauważmy bowiem że:
Y= A*~B*~C
Y= ~(~Y) = ~(~A+B+C)
czyli:
A*~B*~C = ~(~A+B+C) - prawo de’Morgana
cnd
Zauważmy, że równanie:
Y=A*~B*~C
Określa warunek w którym wyjście Y przyjmuje wartość jeden. Ten warunek to:
Y=1 <=> A=1 i ~B=1 i ~C=1
czyli:
Y=1 <=> A=1 i B=0 i C=0
bo jeśli ~B=1 to B=0 itd.
W pozostałych kombinacjach zmiennych wejściowych A,B,C wyjście Y=0 .... bo przecież to algebra Boole’a.
Budowanie tabeli zero-jedynkowej dla udowodnienia prawa de’Morgana pozbawione jest zatem sensu. Możemy oczywiście to zrobić udowadniając powyższe prawo de’Morgana dla trzech zmiennych ... tyle że udowodniliśmy to w zdecydowanie prostszy sposób korzystając z definicji sumy i iloczynu logicznego.
4.1 Przejście z tabel zero-jedynkowych do równań algebry Boole’a
Weźmy tabelę zero-jedynkową implikacji zdefiniowaną jak niżej.
| Kod: |
p q r
0 0 1
0 1 1
1 0 0
1 1 1
|
Jak z takiej tabeli wyprowadzić równanie w algebrze Boole’a ?
Po prostu opisujemy słownie to co widzimy na obrazku.
Sposób I.
Najprościej opisać słowami linię trzecią dla kolumny r bo wtedy i tylko wtedy wyjście r=0.
r=0 <=> p=1 i q=0
Dalej postępujemy jak w punkcie 4.0 czyli sprowadzamy wszystko do jedynki bez zmiany operatorów albo do zera ze zmianą operatorów na przeciwne.
Sprowadzenie do jedynki:
~r = p * ~q
czyli:
r = ~(p* ~q) = ~p + q - prawo de’Morgana
To samo co wyżej można uzyskać bezpośrednio z tabeli zero-jedynkowej poprzez sprowadzenie wszystkich zmiennych do zera z zamianą AND na OR:
r = ~p + q
Sposób II.
Równoważne równanie uzyskamy opisując słownie kolumnę r dla wszystkich r=1 czyli:
r=1 <=> (p=0 i q=0) lub (p=0 i q=1) lub (p=1 i q=1)
Wygenerowanie z powyższego opisu słownego równania logicznego jest trywialne.
Sprowadzamy wszystkie zmienne do jedynki zachowując operatory czyli:
r = (~p * ~q) + (~p * q) + (p*q)
Zbudujmy tabele zero-jedynkową dla przypadku II.
| Kod: |
p q ~p ~q ~p*~q ~p*q p*q r= (~p * ~q) + (~p * q) + (p*q)
0 0 1 1 1 0 0 1
0 1 1 0 0 1 0 1
1 0 0 1 0 0 0 0
1 1 0 0 0 0 1 1
|
Doskonale widać, że kolumna r w powyższej tabeli jest identyczna jak w tabeli na wstępie rozdziału 4.1 co dowodzi tożsamości.
5.0 Logika dodatnia i ujemna w implikacji
Poniższe przykłady to implikacje o których będzie mowa później. W tym rozdziale potraktujemy je jako najzwyklejsze równoważności, badając warunki spełnienia lub nie spełnienia złożonych obietnic i gróźb. Warunki te będą potrzebne przy analizie złożonej implikacji, różniącej się od równoważności tym, że nadawca może darować karę przy spełnionym warunku kary w groźbie (akt łaski) jak również może wręczyć nagrodę przy nie spełnionym warunku nagrody w obietnicy (akt łaski).
Definicja obietnicy:
Jeśli dowolny warunek to nagroda
p=>q - Jeśli zajdzie p to musi zajść q (implikacja prosta)
Jeśli spełnię warunek nagrody to muszę dostać nagrodę, inaczej nadawca jest kłamcą. Nawet jeśli nie spełnię warunku nagrody to nadawca może wręczyć nagrodę i nie jest kłamcą (akt miłości)
Definicja groźby:
Jeśli dowolny warunek to kara
p~>q - Jeśli zajdzie p to może zajść q (implikacja odwrotna)
Jeśli spełnię warunek kary to nie muszę zostać ukarany, bo nadawca ma prawo darować dowolną karę i nie jest kłamcą (akt łaski)
5.1 Obietnica
We wszelkich obietnicach w logice dodatniej mamy odpowiedź kiedy dostaniemy nagrodę, zaś w logice ujemnej odpowiedź kiedy nie dostaniemy nagrody.
Obietnica wypowiedziana:
Jeśli posprzątasz pokój (P) i nie będziesz bił siostry (~B) dostaniesz czekoladę (C)
A:
P*~B=C - zapis naturalny, zapisujemy to co słyszymy
Przejdźmy z wypowiedzianym zdaniem do logiki ujemnej, aby rozstrzygnąć kiedy nie dostanę czekolady.
~(P*~B) = ~C (logika ujemna bo ~C)
Nie może się zdarzyć ~(...), że jeśli posprzątasz pokój (P) i nie będziesz bił siostry (~B) to nie dostaniesz czekolady (~C).
Przejście do logiki ujemnej poprzez negację zmiennych i wymianę operatorów na przeciwne w obietnicy wypowiedzianej A.
~P + B = ~C
Jeśli nie posprzątasz pokoju (~P) lub będziesz bił siostrę (B) to nie dostaniesz czekolady (~C).
Powyższym językiem mówionym posługują się wszyscy ludzie, to krystalicznie czysta algebra Boole’a. Rozważmy problem bardziej szczegółowo od strony matematycznej, zwracając szczególną uwagę na sens logiki dodatniej i ujemnej w obietnicach i groźbach.
C= P* ~B
Dostanę czekoladę, gdy posprzątam pokój i nie będę bił siostry
Zobaczmy w tabeli zero-jedynkowej kiedy dostaniemy czekoladę:
P=1 - sprzątanie pokoju
P=0 - nie posprzątanie pokoju
B=1 - bicie siostry
B=0 - nie bicie siostry
C=1 - czekolada, warunek nagrody spełniony
| Kod: |
P B ~P ~B C=P*~B ~C= ~P+B
1. 0 0 1 1 0 1
2. 0 1 1 0 0 1
3. 1 0 0 1 1 0
4. 1 1 0 0 0 1
|
Warunkiem koniecznym i wystarczającym do tworzenia równań w algebrze Boole’a z dowolnej tabeli zero-jedynkowej jest znajomość definicji sumy i iloczynu logicznego plus logiczne myślenie. Nic więcej nie jest potrzebne.
Definicja sumy logicznej:
Suma logiczna jest równa zeru wtedy i tylko wtedy gdy wszystkie składniki sumy są równe zeru.
Definicja iloczynu logicznego:
Iloczyn logiczny jest równy jeden wtedy i tylko wtedy gdy wszystkie składniki iloczynu są równe jeden
Z powyższej tabeli widać, że dostanę czekoladę (C - logika dodatnia) tylko w przypadku gdy posprzątam pokój i nie będę bił siostry (~B). Jedynki w kolumnie ~C (logika ujemna) informują nas kiedy czekolady nie dostaniemy.
Najprostsze równanie dla powyższej tabeli można utworzyć korzystając z linii 3.
W kolumnie wynikowej logiki dodatniej (C) mamy samotną jedynkę więc równanie jest trywialne.
C=P*~B - wszystkie trzy sygnały sprowadzamy do jedynki
Można też wszystkie trzy sygnały sprowadzić do zera stosując definicję sumy logicznej.
~C= ~P+B
Przechodzimy do logiki dodatniej czyli negujemy sygnały i zmieniamy operator OR na AND.
C=P*~B - mamy to samo CND.
Jedynka w kolumnie C informuje nas kiedy czekoladę dostaniemy.
C=P*~B
Dostanę czekoladę gdy posprzątam pokój i nie będę bił siostry
Jedynki w kolumnie ~C informują nas kiedy czekolady nie dostaniemy. Zauważmy, że ~C to nazwa tej kolumny. Dla tej kolumny najprostsze równanie uzyskamy także z linii 3, ale tym razem w kolumnie wynikowej mamy samotne zero. Ułóżmy równanie sprowadzając wszystkie sygnały do jedynki i korzystając z definicji iloczynu logicznego.
A.
~(~C)= P* ~B
czyli:
~C = ~(P*~B) = ~P+B - prawo de’Morgana
i tu kluczowe dla zrozumienia istoty logiki dodatniej i ujemnej pytanie.
Dlaczego w równaniu A nie skorzystano z prawa podwójnego przeczenia i nie zapisano tego tak.
C=P*~B ?!
Niby równoważne. Zauważmy jednak, że wylądowaliśmy w logice dodatniej i to równanie opisuje nam kiedy czekoladę dostaniemy czyli kolumnę po lewej stronie. W logice ujemnej interesuje nas zupełnie co innego. W logice ujemnej chodzi nam o przypadek kiedy czekolady nie dostaniemy czyli o funkcję ~C. To dwie zupełnie różne funkcje bo nigdy nie będzie:
C = ~C
.... gdyż wówczas algebra Boole’a leży w gruzach.
Zapis ~C nad kolumną z logiką ujemną to nazwa sygnału, której integralną częścią jest przeczenie NIE (~). Tego przeczenia nie wolno nam DOTYKAĆ bo wylądujemy w zupełnie innym punkcie odniesienia, w logice dodatniej ... a przecież nie o to nam chodzi.
Zapamiętajmy:
~C - to jest nazwa funkcji (logika ujemna bo ~C)
~(~C) - to jest nazwa jak wyżej zaprzeczona
~(~C)=C - a to jest błąd w zapisie, bo zmieniliśmy punkt odniesienia i wylądowaliśmy w logice dodatniej. Tego nie wolno robić, bo nazwa ~C to rzecz święta, jeśli analizujemy logikę ujemną.
Jak ktoś nie może się z tym pogodzić to niech po prostu zapisze nad kolumną z logiką ujemną
Y= ~P+B
gdzie oczywiście:
Y= ~C
Y - warunek kiedy czekolady nie dostaniemy (jedynki w tej kolumnie) ... i po bólu.
W katalogach układów cyfrowych jest cała masa nazw sygnałów z kreską nad nazwą (logika ujemna) i bez kreski nad nazwą (logika dodatnia). To jest bardzo ważna informacja, wspólny punkt odniesienia. Oczywistym jest, że przyjętych nazw nie wolno zmieniać w czasie przekształcania równań algebry Boole’a tzn. usuwać przeczeń będących integralną częścią nazwy sygnału bo wyjdzie z tego bełkot, dla nikogo nie zrozumiały. Poza tym regułą jest, że jeśli w nazwie sygnału jest kreska (logika ujemna) to sygnał bez kreski (logika dodatnia) jest fizycznie niedostępny.
Wróćmy do tematu czyli kolumny nie dostania czekolady (~C) w logice ujemnej.
~C = ~P+B
Czekolady nie dostanę, gdy nie posprzątam pokoju lub będę bił siostrę.
Jedynki w kolumnie ~C określają dokładnie wszystkie przypadki w których czekolady nie dostanę. Zapiszmy te linie w formie równań algebry Boole’a sprowadzając każdą linię do jedynek logicznych.
Nie dostanę czekolady gdy:
1.
~C= ~P*~B
nie posprzątam pokoju (~P) i nie będę bił siostry (~B)
2.
~C= ~P*B
nie posprzątam pokoju (~P) i będę bił siostrę (B)
4.
~C= P*B
posprzątam pokój (P) i będę bił siostrę (B)
gdzie:
~C - to integralna nazwa kolumny w logice ujemnej.
Oczywiście, czekolady nie dostanę gdy zajdzie którekolwiek zdarzenie czyli:
~C = ~P*~B + ~P*B + P*B
Jeśli zajdzie którekolwiek z powyższych zdarzeń to czekolady nie dostanę (~C) bo suma logiczna będzie miała wówczas wartość jeden (def. sumy logicznej).
5.2 Groźba
We wszelkich groźbach w logice dodatniej mamy odpowiedź kiedy poniesiemy karę, zaś w logice ujemnej odpowiedź kiedy tej kary unikniemy.
Groźba wypowiedziana:
Jeśli będziesz bił siostrę (B) lub nie posprzątasz pokoju (~P) dostaniesz lanie (L).
A:
B+ ~P = L
Przejdźmy z wypowiedzianym zdaniem do logiki ujemnej, aby rozstrzygnąć kiedy nie dostanę lania.
~(B+ ~P) = ~L
Nie może się zdarzyć ~(...), że jeśli będziesz bił siostrę (B) lub nie posprzątasz pokoju (~P) to nie dostaniesz lania (~L).
Przejście do logiki ujemnej poprzez negację zmiennych i wymianę operatorów na przeciwne w groźbie wypowiedzianej w równaniu A.
~B*P = ~L
Jeśli nie będziesz bił siostry (~B) i posprzątasz pokój (P) to nie dostaniesz lania (~L)
Powyższym językiem mówionym posługują się wszyscy ludzie, to krystalicznie czysta algebra Boole’a. Rozważmy problem bardziej szczegółowo od strony matematycznej, zwracając szczególną uwagę na sens logiki dodatniej i ujemnej.
Jeśli będziesz bił siostrę (B) lub nie posprzątasz pokoju (~P) dostaniesz lanie (L).
B+ ~P = L
Zobaczmy w tabeli zero-jedynkowej kiedy dostaniemy lanie:
B=1 - bicie siostry
B=0 - nie bicie siostry
P=1 - sprzątanie pokoju
P=0 - nie posprzątanie pokoju
L=1 - lanie, warunek kary spełniony
| Kod: |
B P ~B ~P L=B+~P ~L= ~B*P
1. 0 0 1 1 1 0
2. 0 1 1 0 0 1
3. 1 0 0 1 1 0
4. 1 1 0 0 1 0
|
Z tabeli tej widać, że nie dostanę lania (~L) tylko w przypadku gdy nie będę bił siostry (~B) i posprzątam pokój (P) - jedynka w kolumnie ~L. W przeciwnym przypadku dostanę lanie - jedynki w kolumnie L.
~L= ~B*P - tylko w tym przypadku lania nie dostanę (samotna jedynka w kolumnie ~L)
Negując logikę ujemną przechodzimy do logiki dodatniej:
~(~L)= ~(~B*P)
czyli:
L= ~(~B*P)
Nie może się zdarzyć ~(...), że jeśli nie będę bił siostry (~B) i posprzątam pokój (P) to dostanę lanie (L)
Zauważmy, że tym razem świadomie usunęliśmy przeczenie z nazwy sygnału ~L w logice ujemnej bo chodzi nam o przejście do logiki dodatniej czyli o odpowiedź na pytanie kiedy dostaniemy lanie (L).
L= ~(~B*P) = B+ ~P - prawo de’Morgana.
Dostanę lanie gdy będę bił siostrę lub nie posprzątam pokoju.
Równoważne do powyższego jest poniższe równanie wynikłe z jedynek w kolumnie L.
L= ~B*~P + B*~P + B*P - w tych przypadkach dostanę lanie (jedynki w kolumnie L=B+~P)
Jeśli zajdzie którekolwiek z powyższych zdarzeń to dostanę lanie (def. sumy logicznej)
Dostanę lanie gdy:
1.
~B*~P - nie będę bił siostry (~B) i nie posprzątam pokoju (~P)
3.
B*~P - będę bił siostrę (B) i nie posprzątam pokoju (~P)
4.
B*P - będę bił siostrę (B) i posprzątam pokój (P)
Poniżej na wykresach czasowych mamy dowód, że logika ujemna istnieje i jest lustrzanym odbiciem logiki dodatniej.
5.3 Wykresy czasowe w algebrze Boole'a
Wykresy czasowe w algebrze Boole'a to graficzne przedstawienie tabel zero-jedynkowych. Punktem odniesienia (osią liczbową) są tutaj wszystkie możliwe kombinacje sygnałów na wejściu oraz odpowiadający im stan na wyjściu. Wykresy czasowe są bezkonkurencyjne w opisie układów cyfrowych średniej skali integracji.
[link widoczny dla zalogowanych]
Rys. 5.3 Wykresy czasowe iloczynu logicznego i sumy logicznej
Wygodne dla rysowania wykresów czasowych definicje sumy i iloczynu logicznego są następujące.
Definicja iloczynu logicznego.
Wyjście Y przyjmuje wartość jeden wtedy i tylko wtedy gdy wszystkie zmienne na wejściu maja wartość jeden. W przeciwnym przypadku Y=0 ... bo to algebra Boole’a.
Definicja sumy logicznej.
Wyjście Y przyjmuje wartość zero wtedy i tylko wtedy gdy wszystkie zmienne na wejściu mają wartość zero. W przeciwnym przypadku Y=1 ... bo to algebra Boole’a.
Powyższy wykres czasowy w punktach 1 i 2 pokazuje wszystkie możliwe kombinacje zmiennych wejściowych A i B w funkcji czasu.
Wykres 3 to cytowana wyżej definicja iloczynu logicznego zaś wykres 5 to definicja sumy logicznej.
Wykres ~Y to negacja wyjścia iloczynu logicznego, zaś wykres ~Z to negacja wyjścia sumy logicznej. Zauważmy, że wykres ~Y jest lustrzanym odbiciem sygnału Y, zaś wykres ~Z jest lustrzanym odbiciem sygnału Z.
Sygnały ~Y i ~Z to logika ujemna na wyjściu układu cyfrowego. Jak widać, najprostszy sposób przejścia do logiki ujemnej na wyjściu to użycie prostego negatora negującego wyjście Y albo Z.
Zauważmy ciekawą rzecz w opisie sygnałów.
Y = A*B - logika dodatnia (Y)
~Y = ~(A*B) - logika ujemna (~Y) powstała poprzez użycie prościutkiego negatora
W opisie układów cyfrowych ten zapis jest powszechnie stosowany. Zapis ~Y oznacza tu nazwę oddzielnego wyjścia, na którym dostępny jest zanegowany sygnał cyfrowy Y. Oczywiście, mając w układzie cyfrowym dostępny tylko sygnał Y możemy go zanegować negatorem i otrzymamy sygnał ~Y.
Zauważmy, że w powyższym opisie wykresu czasowego nie możemy zastosować systemu:
Y = A*B - wyjście w logice dodatniej
Y = ~(A*B) - to samo wyjście na którym pojawia się logika ujemna.
... bo nawet początkujący matematyk to wyśmieje, gdyż z zapisu tego wynika bzdura:
A*B = ~(A*B)
Teoretycznie dopuszczalny jest taki zapis:
Y = A*B
X = ~(A*B)
tyle że to bez sensu bo wiadomo iż zachodzi:
X = ~Y - dodatkowa zmienna jest zbędna.
Punkt odniesienia.
Pani do Jasia w szkole.
Y=2
Napisz Jasiu czemu jest równe -Y
Jaś:
X=-2
Jasiu, nie pytałam cię czemu jest równe X, pytanie brzmiało czemu jest równe -Y
Jaś:
-Y=-2
Siadaj Jasiu, szóstka.
6.0 Matematyczne operatory logiczne
Efektem ubocznym walki z implikacją na www.sfinia.fora.pl (metodologia) jest odkrycie i nazwanie wszystkich operatorów matematycznych w algebrze Boole'a (jest ich 16 a nie jak niektórzy sądzą 8) oraz tablice logiki zdefiniowane dzięki odkryciu logiki ujemnej w algebrze Boole'a. W Wikipedii w temacie "logika ujemna" pisze o związku 0 i 1 z poziomami napięć. Przydatność takiego pojęcia w matematyce jest równa zeru absolutnemu - zapomnijmy o tym.
6.1 Lista operatorów logicznych
| Kod: | p q OR NOR AND NAND <=> XOR => -> ~> <- FILL NOP P NP Q NQ
0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1
0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0
1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
|
| Kod: | Logika dodatnia Logika ujemna
OR NOR
AND NAND
<=> XOR
=> ->
~> <-
FILL NOP
P NP
Q NQ
|
Jak to możliwe iż wszystkich operatorów jest 16 a nie 8 ?
Połowa z tych operatorów działa w logice dodatniej a druga połowa w logice ujemnej.
Co to jest logika ujemna ? ... widać w powyższych tabelach.
Każdy operator dodatni ma swego oponenta w postaci operatora ujemnego. Negując operator dodatni otrzymamy operator ujemny i odwrotnie. Iloczyn logiczny tych operatorów jest zawsze równy zeru (operator NOP), zaś suma logiczna zawsze równa 1 (operator FILL).
Jest to zgodne z fundamentem algebry Boole’a:
A*~A=0
A+~A=1
Same jedynki (FILL) to czysta pamięć mikroprocesora przed wpisaniem programu. Rozkaz NOP jest w każdym mikroprocesorze i oznacza NIC NIE RÓB - odpoczywaj. Jakby kto nie wiedział to w mikroprocesorze pracuje najprawdziwszy krasnoludek ...
Operatory logiczne w równaniach matematycznych:
OR = ~(~p*~q) = p + q - prawo de’Morgana
NOR = ~OR = ~p*~q = ~(p+q) - prawo de'Morgana (logika ujemna)
AND = p*q = ~(~p+~q) - prawo de'Morgana
NAND = ~AND = ~(p*q) = ~p+~q - prawo de'Morgana (logika ujemna)
<=> = (~p*~q)+(p*q)
XOR = ~(<=>) = ~p*q + p*~q (logika ujemna)
Operator implikacji prostej:
p=>q = ~p + q = ~(p*~q) - prawo de'Morgana
p->q = ~(p=>q) = p*~q = ~(~p + q) - prawo de'Morgana (logika ujemna)
Operator implikacji odwrotnej:
p~>q = p+~q = ~(~p*q) - prawo de'Morgana
p<-q = ~(p~>q) = ~p*q = ~(p+~q) - prawo de'Morgana (logika ujemna)
FILL = ~p*~q + ~p*q + p*~q + p*q = 1
NOP = ~FILL = ~(1) = 0 (logika ujemna)
P = p
NP = ~P = ~p (logika ujemna)
Q = q
NQ = ~Q = ~q (logika ujemna)
Za operatory dodatnie przyjąłem te operatory których człowiek używa w języku mówionym.
Operatory człowieka w języku mówionym są konsekwencją przyjęcia następującego standardu.
Logika dodatnia:
Y=1 = PRAWDA
Y=0 = FAŁSZ
Związek logiki dodatniej z logika ujemną:
Y= ~Z
Powyższy standard determinuje wygląd tablicy operatorów wyżej w taki a nie inny sposób.
Równie dobry jest standard poniższy.
Logika ujemna:
Z=0 = PRAWDA
Z=1 = FAŁSZ
Związek logiki ujemnej z logika dodatnią:
Z=~Y
Na szczęście nikt standardu w logice ujemnej nie używa bo technika cyfrowa rozwinęła się bardzo szybko w przeciwieństwie do np. języków mówionych. Która logika jest ujemna a która dodania to też sprawa czysto umowna.
6.2 Związek algebry Boole’a z rzeczywistością
Aby związać matematykę z rzeczywistością musimy przyjąć kolejny standard, wiążący cyfry binarne 0 i 1 z fizyką. Najpopularniejszym takim standardem jest standard TTL.
Cyfrowy standard TTL:
Y = 1 = 2,4-5,0V - logicznej jedynce odpowiadają napięcia 2,4-5,0V
Y= 0 = 0 - 0,4V - logicznemu zeru odpowiadają napięcia 0-0,4V
Y - rzeczywista zmienna cyfrowa mogąca przyjmować w osi czasu wyłącznie wartości 0 albo 1.
Taką zmienną można obejrzeć na przyrządzie pomiarowym zwanym oscyloskopem. Jeśli zanegujemy tą zmienną prościutkim negatorem to otrzymamy lustrzane odbicie zmiennej Y w osi czasu czyli znajdziemy się w logice ujemnej ~Y.
W algebrze Boole’a obowiązuje wyłącznie logika binarna, nie ma innych cyfr poza 0 i 1.
Jak zatem działają komputery ?
Zapis matematyczny dowolnej liczby w algebrze dziesiętnej:
An .... A2 A1 A0 = An*10**n + A2*10**2 + A1*10**1 + A0*10**0
UWAGA !
Tylko i wyłącznie w tym punkcie znaki * i + oznaczają co innego niż w całej publikacji (pkt.1.0)
* - symbol mnożenia algebraicznego
** - symbol potęgi
+ - symbol sumy algebraicznej
10**2 - oznacza 10 do potęgi drugiej
10**0 = 1 bo dowolna liczba do potęgi zerowej jest równa 1.
Gdzie cyfry dziesiętne mogą przyjmować jedną z wartości [0,1,2,3,4,5,6,7,8,9]
Przykład:
1985 = 1*10**3 + 9*10**2 + 8*10**1 + 5*10**0 = 1*1000 + 9*100 + 8*10 + 5*1 = 1985
Zapis matematyczny dowolnej liczby w algebrze Boole’a:
Bn...B2 B1 B0 = Bn*2**n ...+ B2*2**2 + B1*2**1 + B0*2**0
Gdzie cyfry binarne mogą przyjmować wyłącznie wartości 0 albo 1.
Przykład:
1101 = 1*2**3 + 1*2**2 + 0*2**1 + 1*2**0 = 1*8+1*4+0*2+1*1= 8+4+0+1=13 (dziesiętnie)
Sposób zamiany liczby binarnej na liczbę dziesiętną jest trywialny, widać go wyżej.
Liczba binarna 1101 odpowiada liczbie dziesiętnej 13. Liczbę taką czytamy jako „jeden, jeden, zero, jeden” bo inne cyfry poza zero i jeden nie występują w algebrze Boole’a.
Każdą liczbę zapisana w systemie binarnym można zapisać w systemie dziesiętnym i odwrotnie. Komputery pracują wyłącznie w systemie binarnym bo fizycznie najłatwiej jest zrealizować cyfry 0 i 1. Jeśli zadamy komputerowi np. mnożenie dwóch liczb dziesiętnych to pracujący w nim krasnoludek zamienia liczbę dziesiętną na binarną, wykonuje mnożenie w systemie binarnym po czym zamienia wynik na liczbę dziesiętną i wyświetla go na ekranie.
Fizycznie liczbę binarną można sobie przedstawić jako uporządkowany zbiór przewodów na których mogą występować wyłącznie stany 0 albo 1 np. w standardzie TTL jak wyżej. W każdym mikroprocesorze występuje magistrala adresowa (liczba n-bitowa) do adresowania komórek pamięci oraz magistrala danych służąca do przesyłania danych między pamięcią a mikroprocesorem. Interpretacji różnych liczb binarnych jest bardzo dużo np. każdy znak wciśnięty na klawiaturze ma swój odpowiednik w liczbie binarnej, każdy punkt na ekranie monitora opisany jest przez zestaw liczb binarnych itd.
6.3 Jak działają operatory logiczne
To poważna sprawa, myślę iż potrzebna tu będzie pomoc moich przyjaciół ... krasnoludków.
Wyobraźmy sobie czarne pudełko z dwoma wyłącznikami lampek, jeden wyłącznik ma na imię p a drugi q. Przełączniki wyglądają jak te najzwyklejsze od lampek nocnych z napisem 1 = włącz i 0 = wyłącz.
Zapalane światełka widzi zarówno człowiek jak i pracujący w środku krasnoludek. Oczywiście nie widzimy ani krasnoludka ani jego przełącznika którym zapala swoją lampkę. Widzimy wyłącznie lampkę krasnoludka.
Zaobserwujmy pracę krasnoludka pracującego zgodnie z tabelą prawdy operatora NOR.
| Kod: | p q NOR
1 1 0
1 0 0
0 1 0
0 0 1 |
Ustawmy na przełącznikach p i q pierwszą linię powyższej tabeli prawdy. Jak widzimy lampka krasnoludka zgaszona. Podobną sytuację mamy w liniach 2 i 3.
Ustawiamy z niepokojem linię 4 i co widzimy ?
Jest - świeci się !
To jest dowód na istnienie krasnoludków w naszym Wszechświecie !
7.0 Tablice logiki
Wypełnimy tablice logiki tylko dla następujących operatorów:
OR, NOR, AND, NAND, <=>, XOR, =>, ->, ~>, <-
Uzupełnienie tablicy dla pozostałych operatorów pozostawiam czytelnikowi.
7.1 Tablica logiki dla operatorów OR, NOR, AND, NAND
| Kod: |
Logika dodatnia Y Logika ujemna ~Y Związek logik
OR NOR
Y=A+B ~Y = A NOR B A+B = ~(A NOR B)
Prawo de'Morgana Prawo de'Morgana
~Y = ~A*~B Y = ~A NAND ~B ~(~A*~B) = ~A NAND ~B
Związek krzyżowy OR-NOR
A+B = ~A NAND ~B
~A*~B = A NOR B
AND NAND
Y=A*B ~Y = A NAND B A*B = ~(A NAND B)
Prawo de'Morgana Prawo de'Morgana
~Y = ~A + ~B Y = ~A NOR ~B ~(~A+~B) = ~A NOR ~B
Związek krzyżowy AND-NAND
A*B = ~A NOR ~B
~A+~B = A NAND B
|
Powyższa tabela obowiązuje zarówno dla logiki dodatniej jak i ujemnej, bo nie ma w niej powiązań z kodem maszynowym czyli z zerami i jedynkami. Człowiek przyzwyczaił się do logiki dodatniej i niech tak zostanie. Logika ujemna jest jednak możliwą i równoprawną logiką. Gdybyśmy w niniejszym elementarzu zamienili zera z jedynkami w wynikach operatorów matematycznych to otrzymalibyśmy jego wersję dla logiki ujemnej.
7.2 Tablica logiki dla operatorów <=>, XOR, =>, ->, ~>, <-
Poniższe operatory omówione będą w części II elementarza.
| Kod: | Logika dodatnia Y Logika ujemna ~Y Związek logik
<=> XOR <=> = ~XOR
XOR = ~(<=>)
p<=>q=~p<=>~q p XOR q= ~p XOR ~q
p<=>q=(p=>q)*(p~>q) p XOR q=(p->q)+(p<-q)
p~>q = q=>p
p<=>q=(p=>q)*(q=>p)
=> ->
p=>q p->q p=>q = ~(p->q)
p->q = ~(p=>q)
Prawo Kubusia Prawo Kubusia
p=>q = ~p ~> ~q p->q = ~p <- ~q
~> <-
p~>q p<-q p~>q = ~(p<-q)
p<-q = ~(p~>q)
Prawo Kubusia Prawo Kubusia
p~>q = ~p => ~q p<-q = ~p -> ~q
|
Dodatek A
Dowodzenie twierdzeń implikacyjnych w algebrze Boole’a
Definicja implikacji prostej:
| Kod: | Def.1
p q p=>q
1 1 1
1 0 0
0 0 1
0 1 1 |
Z pierwszych dwóch linii widać definicję słowną implikacji prostej.
p=>q
Jeśli zajdzie p to musi zajść q
p musi być warunkiem wystarczającym dla q, bo wynik drugiej linii jest twardym fałszem.
=> - operator implikacji prostej, spójnik „musi” => między p i q
Przykład:
Jeśli liczba jest podzielna przez 8 to jest podzielna przez 2
P8=>P2
p=P8
q=P2
Definicja implikacji odwrotnej:
| Kod: | Def.2
p q p~>q p<=q
1 1 1 1
1 0 1 1
0 0 1 1
0 1 0 0 |
Z pierwszych dwóch linii widać słowną definicję implikacji odwrotnej
p~>q
Jeśli zajdzie p to może zajść q
p~>q
LUB
Jeśli zajdzie p to może zajść ~q
p~>~q
Druga linia wynika z pierwszej (bo q+~q=1) zatem jest zbędna w słownej definicji.
p~>q
Jeśli zajdzie p to może zajść q
p musi być warunkiem koniecznym dla q, inaczej pierwsza linia p~>q jest twardym fałszem.
~> - operator implikacji odwrotnej, spójnik „może” ~> między p i q
Jeśli p jest warunkiem koniecznym dla q to zajście ~p gwarantuje zajście ~q. Mówi o tym trzecia i czwarta linia definicji implikacji odwrotnej.
Przykład:
Jeśli liczba jest podzielna przez 2 to może być podzielna przez 8
P2~>P8
p=P2
q=P8
Zauważmy, że w def.2 matematycznie zachodzi:
p~>q = p<=q
gdzie:
<= - operator implikacji odwrotnej, spójnik „może” czytany tylko i wyłącznie przeciwnie do strzałki
Musi zachodzić zgodność kierunkowa wektorów o czym będzie dalej.
Porównajmy:
P2~>P8 = P2<=P8 - dobrze, o ile wektor <= jest czytamy przeciwnie do strzałki jako spójnik „może”
P2~>P8 = P2=>P8 - ewidentny błąd matematyczny, bo tu spójnik => oznacza „musi”
Z powyższego powodu konieczne jest wprowadzenie nowego operatora matematycznego „może”, inaczej mamy piekło.
Z powyższych tabel def.1 i def.2 widać że:
p=>q # p~>q
czyli:
P8=>P2 # P2~>P8
Implikacja jest wektorem kierunkowym, gdzie obowiązują inne reguły dowodzenia twierdzeń matematycznych niż w „ślepych” operatorach AND i OR.
Przykład:
Jeśli liczba jest podzielna przez 8 to jest podzielna przez 2
P8=>P2
p=P8
q=P2
p=>q
W dzisiejszej logice nie wiedzieć czemu wyróżniona jest jedynie słuszna, definicja implikacji prostej czyli p i q jest na stałe przywiązane do tej właśnie implikacji. Po takim głupim manewrze (choć dozwolonym) mamy implikację odwrotną w tej postaci.
Jeśli liczba jest podzielna przez 2 to może być podzielna przez 8
P2~>P8
q=P2
p=P8
q~>p
Oczywiście jest to sprzeczne z naturalną logiką człowieka gdzie po „Jeśli..” mamy zawsze poprzednik p, zaś po „to…” mamy zawsze następnik q.
Głupia (choć dozwolona) definicja implikacji odwrotnej z jedynie słusznym punktem odniesienia p=>q.
| Kod: | Def.3
q p q~>p
1 1 1
1 0 1
0 0 1
0 1 0 |
Dla ustalonego sztywno p i q poprzez jedynie słuszną, komunistyczną definicję implikacji prostej p=>q mamy:
| Kod: | Tabela 1
p q p=>q p<~q
1 1 1 1
1 0 0 0
0 0 1 1
0 1 1 1 |
Oczywiście:
p<~q = q~>p
Pozornie otrzymujemy dowód idiotyzmu:
p=>q = q~>p
bo ostatnie dwie kolumny są identyczne, czyli dla sztywnych:
p=P8
q=P2
P8=>P2 = P2~>P8 !?
Zauważmy jednak, że wektor p=>q tworzyliśmy z lewa do prawa, zaś wektor q~>p z prawa do lewa, czyli nastąpiła zmiana kierunku będąca przyczyną powyższego idiotyzmu.
Poprawny dowód w algebrze Boole’a, oczywiście obalający ten idiotyzm będzie wyglądał tak.
| Kod: | Tabela 2
p q p=>q q p q~>p p q p<~q
1 1 1 1 1 1 1 1 1
1 0 0 1 0 1 0 1 1
0 0 1 0 0 1 0 0 1
0 1 1 0 1 0 1 0 0 |
Jak widać poprzednik i następnik w implikacjach p=>q i q~>p musi mieć na wejściu identyczne matryce zero-jedynkowe. Kierunek wektora musi być zawsze z lewej do prawej.
Oczywiście zachodzi:
p=>q # q~>p
co widać na załączonym obrazku.
W ostatnich trzech kolumnach pokazano jedyny dozwolony chwyt. Zamieniamy kolumny p i q oraz kierunek wektora na z prawej do lewej.
Zasady dowodzenia twierdzeń implikacyjnych:
W czasie dowodzenia dowolnego twierdzenia implikacyjnego nie wolno zmienić wyłącznie kierunku wektora bez zamiany kolumn lub zamienić kolumny bez zmiany kierunku wektora !
To co wyżej to typowy błąd matematyczny popełniany przez wszystkich przy dowodzeniu praw kontrapozycji.
Prawo kontrapozycji:
p=>q = ~q=>~p
„Dowód”:
| Kod: | Tabela 3
p q p=>q ~q ~p ~q=>~p
1 1 1 0 0 1
1 0 0 1 0 0
0 0 1 1 1 1
0 1 1 0 1 1 |
Jak widać kolumny p=>q i ~q=>~p są identyczne zatem prawo kontrapozycji jest „poprawne”.
To co wyżej to typowy błąd czysto matematyczny bowiem zamienione zostały kolumny ~p i ~q bez zmiany kierunku wektora.
| Kod: | Tabela 4
p q p=>q ~p ~q ~p<=~q
1 1 1 0 0 1
1 0 0 0 1 0
0 0 1 1 1 1
0 1 1 1 0 1 |
Oczywiście:
~p<=~q = ~q=>~p
Tu z kolei kolumny ~p i ~q są w porządku, jednak zmieniono kierunek ostatniego wektora.
Dowód iż prawo kontrapozycji jest błędne w implikacji jest trywialny.
| Kod: | Tabela 5
p q p=>q q p q~>p ~q ~p ~q=>~p
1 1 1 1 1 1 0 0 1
1 0 0 1 0 1 0 1 1
0 0 1 0 0 1 1 1 1
0 1 1 0 1 0 1 0 0 |
Przy tworzeniu powyższej tabeli wykorzystano doświadczenia nabyte w tabeli 1 i tabeli 2.
Jeśli liczba jest podzielna przez 8 to na pewno jest podzielna przez 2
P8=>P2
p=P8
q=P2
Jeśli liczba jest podzielna przez 2 to może być podzielna przez 8
P2~>P8
q=P2
p=P8
Tu nie wolno użyć spójnika „musi” bo wtedy mamy nonsens:
Jeśli liczba jest podzielna przez 2 to musi być podzielna przez 8
P2=>P8 - oczywisty fałsz dla „musi”
Jak widać, kolumny p=>q i ~q=>~p są różne zatem prawo kontrapozycji w implikacji jest błędne. Zauważmy, że p i q z pierwszych dwóch kolumn jest z zupełnie innej bajki niż p i q w końcowym ~q=>~p.
W tabeli wyżej doskonale widać jedno z praw Kubusia:
q~>p = ~q=>~p
Wniosek końcowy.
Znane człowiekowi prawa kontrapozycji:
p=>q = ~q=>~p - tu punktem odniesienia jest jedynie słuszne, komunistyczne p=>q
q=>p = ~p=>~q - tu punktem odniesienia jest jedynie słuszne, kapitalistyczne q=>p
są poprawne tylko i wyłącznie w równoważności, nieczułej ani na zamianę kolumn, ani też na zmianę kierunku wektora.
Równoważność, to pewne wynikanie w dwie strony:
p<=>q = (p=>q)*(q=>p)
Kwadrat logiczny równoważności:
| Kod: | p=>q q=>p
~p=>~q ~q=>~p |
W równoważności zachodzą tożsamości we wszystkich możliwych kierunkach: w poziomie, w pionie i po przekątnych (prawa kontrapozycji)
Jeśli w implikacji p=>q zamienimy p i q miejscami to otrzymamy implikację odwrotną q~>p.
Ostatnio zmieniony przez rafal3006 dnia Pon 12:27, 12 Sty 2009, w całości zmieniany 28 razy
|
|
| Powrót do góry |
|
 |
|
|
|
|
|
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
|
fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Szukaj
Użytkownicy
Grupy
Galerie
Rejestracja
Zaloguj się, by sprawdzić wiadomości
Zaloguj
