|
Ś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: 35965
Przeczytał: 15 tematów
Skąd: z innego Wszechświata Płeć: Mężczyzna
|
Wysłany: Wto 15:49, 18 Wrz 2012 Temat postu: Techniczna algebra Boole'a |
|
|
Techniczna algebra Boole’a
Widziana oczami inżyniera i jej związki z naturalną logiką człowieka.
W projektowaniu złożonych automatów cyfrowych dobrzy fachowcy posługują się naturalną logiką człowieka w 100% zgodną z algebrą Boole’a w totalnej izolacji od idiotycznych zer i jedynek - dowód, urządzenia zaprojektowane w ten sposób działają znakomicie.
W naturalnej logice człowieka, czyli w poprawnej interpretacji tabel zero-jedynkowych, spójniki „lub”(+) i „i”(*) nie są kompletnymi operatorami logicznymi opisanymi wszystkimi czteroma liniami tabeli zero-jedynkowej, co udowodnimy w tym artykule, w sposób czysto matematyczny.
1.0 Techniczna algebra Boole’a
Klasyczny Rachunek Zdań, to w wersji technicznej wyłącznie rachunek zero-jedynkowy plus funkcje logiczne, gdzie 0 i 1 nie mają żadnych znaczeń typu:
1 = prawda
0 = fałsz
zdanie prawdziwe/fałszywe, kwantyfikatory etc.
Na studiach technicznych nawet nie padają nazwy KRZ czy KRZiP.
W technice mamy do czynienia z algebrą Boole’a której fundamentem jest rachunek zero-jedynkowy.
W technicznej algebrze Boole’a znaczki „+”, „*”, są kompletnymi operatorami logicznymi, co jest błędem czysto matematycznym, ale nieszkodliwym, co zobaczymy za chwilę.
W technicznej algebrze Boole’a interesują nas wyłącznie operatory OR i AND oraz zaledwie trzy znaczki:
„~” - negacja
„+” - spójnik logiczny „lub” z naturalnej logiki człowieka
„*” - spójnik logiczny „i” z naturalnej logiki człowieka
W tym podręczniku omówimy rozszerzoną (nieznacznie) techniczną algebrę Boole’a pokazując jej związek z naturalną logiką człowieka.
W algebrze Boole’a występują tylko i wyłacznie dwie cyferki 0 i 1 gdzie matematycznie zachodzi:
1 = ~0
0 = ~1
gdzie:
„~” - symbol przeczenia, „NIE” w mowie potocznej
Nigdy nie może być:
1=0
Aksjomatyka technicznej algebry Boole’a:
Aksjomatyka technicznej algebry Boole’a to wszystkie możliwe, dwuargumentowe definicje operatorów logiczny których jest zaledwie 16, plus banalne zasady posługiwania się rachunkiem zero-jedynkowym.
Aksjomatyka algebry Kubusia to po prostu wszystkie możliwe zero-jedynkowe definicje operatorów logicznych, znane ludziom od ponad 100 lat.
Kod: |
p q OR NOR AND NAND <=> XOR => N(=>) ~> N(~>) ~~> N(~~>) P NP Q NQ
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1
0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0
0 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1
|
Kod: |
Logika dodatnia Logika ujemna
OR NOR
AND NAND
<=> XOR
=> N(=>)
~> N(~>)
~~> N(~~>)
P NP
Q NQ
|
Wszystkich możliwych operatorów logicznych dwuargumentowych jest 16. Za operatory dodatnie przyjęto te, które człowiek używa w naturalnym języku mówionym.
Operator ujemny to zanegowany operator dodatni, co doskonale widać w powyższej tabeli.
Kod: |
Definicje operatorów ujemnych:
pNORq = ~(p+q)
pNANDq = ~(p*q)
pXORq = ~(p<=>q)
pN(=>)q = ~(p=>q)
pN(~>)q = ~(p~>q)
p~~>q = ~(p~~>q)
pNPq = ~(pPq)
pNQq = ~(pQq)
|
W języku mówionym operatory ujemne nie są używane, ponieważ łatwo je zastąpić operatorami dodatnimi plus negacją co widać w powyższej tabeli.
Koniec!
Na studiach technicznych nikt nie schodzi z aksjomatyką poniżej tego poziomu … i komputery działają.
1.1Rachunek zero-jedynkowy
W rachunku zero-jedynkowym występują wyłącznie dwie cyferki 0 i 1.
Fundament rachunku zero-jedynkowego.
1#0
0#1
gdzie:
# - różne
Nigdy nie może być:
1=0
0=1
Definicja negacji:
1=~0
~1=0
Gdzie:
~ - negacja o definicji jak wyżej, w mowie potocznej słówko „NIE”.
Zmienna binarna:
Zmienna binarna to zmienna mogąca w osi czasu przybierać wyłącznie wartości 0 albo 1.
Przykłady zmiennych binarnych:
p, q, r
Prawo podwójnego przeczenia:
p = ~(~p)
Dowód metodą zero-jedynkową:
Kod: |
p ~p ~(~p)
1 0 =1
0 1 =0
|
Zmienną p ustawiamy na wszystkie możliwe wartości jakie ta zmienna może przyjąć, czyli 0 albo 1. Po dwukrotnym skorzystaniu z definicji negacji kolumny pierwsza i ostatnia są tożsame co jest dowodem poprawności prawa podwójnego przeczenia.
Funkcja logiczna:
Funkcja logiczna to odpowiedź układu na wszystkie możliwe kombinacje zer i jedynek na wejściach p i q.
Przykład funkcji logicznej:
Y=p+q
Tabela zero-jedynkowa dla tej funkcji:
Kod: |
p q Y=p+q
A: 1 1 =1
B: 1 0 =1
C: 0 1 =1
D: 0 0 =0
1 2 3
|
Y=p+q
Gdzie:
+ - spójnik „lub” z naturalnej logiki człowieka o definicji
Y=p+q
Y=1 <=> p=1 lub q=1
W naturalnej logice człowieka znaczek „+” definiuje wyłącznie pierwsze trzy linie ABC123.
Całą tabelę opisuje jednak jednoznacznie, bo to jest dwuelementowa algebra Boole’a, zatem linie nie opisane znaczkiem „+” musza przyjąć w wyniku 0.
Linie w definicji funkcji logicznej możemy dowolnie przestawiać, to bez znaczenia.
Dowód ścisłe matematyczny iż znaczek „+” definiuje wyłącznie trzy pierwsze linie za chwilę.
Funkcja logiczna Y (operator logiczny) to całość, czyli na wejściu bramki logicznej muszą występować zmienne binarne p i q mogące w osi czasu przyjmować dowolne wartości, 0 albo 1.
Bramka logiczna:
Bramka logiczna to fizyczna realizacja funkcji logicznej o dowolnej liczbie wejść i tylko jednym wyjściu, zwykle oznaczanym dużą literą Y.
Funkcja logiczna może być jednocześnie operatorem logicznym, jak w przypadku wyżej, ale nie musi.
Zawsze zachodzi tożsamość:
Funkcja logiczna = bramka logiczna
Przykład:
Y=p*~q + r
Dla dwóch zmiennych p i q zachodzi:
Funkcja logiczna = bramka logiczna = operator logiczny
Przykład:
Y= p*q + p*~q + ~p*q
W podstawach logiki ograniczamy się do funkcji logicznej dwóch zmiennych wejściowych p i q.
Zachodzi wówczas:
Funkcja logiczna = bramka logiczna = operator logiczny
Nie są funkcją logiczną pojedyncze linie z powyższej tabeli.
Kod: |
p q Y=p+q
A: 1 1 =1
1 2 3
|
Nie jest funkcją logiczną dowolny fragment z powyższej tabeli:
Kod: |
p q Y=p+q
1 1 =1
1 0 =1
0 1 =1
|
Tożsamość funkcji logicznych:
Funkcje logiczne są tożsame wtedy i tylko wtedy gdy na wszystkie możliwe kombinacje zero-jedynkowe zmiennych binarnych na wejściu dają identyczne odpowiedzi na wyjściu.
Przykład:
p+q = p*q + p*~q + ~p*q
Łatwo sprawdzić, że tabele zero-jedynkowe po obu stronach znaku tożsamości są identyczne, co jest dowodem zachodzącej tożsamości.
Fizycznie, można powyższą tożsamość sprawdzić w laboratorium techniki cyfrowej. Po zbudowaniu układów cyfrowych po lewej i prawej stronie znaku tożsamości, łączymy wyjścia. Brak dymu i smrodu jest dowodem zachodzącej tożsamości matematycznej.
Definicja rachunku zero-jedynkowego:
Rachunek zero-jedynkowy to poszukiwanie wszelkich możliwych tożsamych funkcji logicznych.
Najważniejsze prawa rachunku zero-jedynkowego w operatorach OR i AND to:
Prawa de’Morgana.
p+q = ~(~p*~q)
p*q = ~(~p+~q)
1.2 Czarodziejska sztuczka
Udajmy się do laboratorium układów cyfrowych.
Bierzemy do ręki układ scalony SN7432.
W katalogu to jest bramka OR opisana następująco:
Kod: |
p q Y=p+q
A: 1 1 =1
B: 1 0 =1
C: 0 1 =1
D: 0 0 =0
1 2 3
|
Zdejmujemy tabelę prawdy, wszystko się zgadza to jest definicja operatora OR.
W równaniu opisującym tabelę wyżej mamy:
Y=p+q
Gdzie wedle dzisiejszej logiki znaczek „+” to kompletny operator logiczny zdefiniowany wszystkimi czteroma liniami tabeli zero-jedynkowej.
Dokładamy na wejścia p i q i wyjście Y negatory, czyli nasze równanie logiczne przyjmuje postać:
~Y=~p+~q
i ponownie zdejmujemy tabelę prawdy.
Kod: |
p q Y=p*q
A: 1 1 =1
B: 1 0 =0
C: 0 1 =0
D: 0 0 =0
1 2 3
|
Wniosek:
Operator OR nie jest tworem jednorodnym, musi zawierać w sobie także zero-jedynkową definicję operatora AND, inaczej czarodziejska sztuczka jak wyżej nie byłaby możliwa.
Za chwilę rozszyfrujemy te czary.
Metodykę dowodzenia praw logicznych metodą rachunku zero-jedynkowego poznamy na przykładzie praw de’Morgana.
1.3 I Prawo de’Morgana
I Prawo de’Morgana:
p+q = ~(~p*~q)
Na początek zróbmy kluczową sztuczkę:
Y = p+q = ~(~p*~q)
stąd:
Y=p+q
Y=~(~p*~q)
Dowolną tożsamość logiczną wolno nam zanegować stronami.
Drugą linię negujemy stronami:
~Y = ~[~(~p*~q)]
~Y=~p*~q
bo prawo podwójnego przeczenia:
~[~(x)] = x
stąd końcowa postać prawa de’Morgana w układzie równań logicznych:
Y=p+q
~Y=~p*~q
Doskonale widać, że do opisu przypadku:
~p*~q
w dowodzie zero-jedynkowym prawa de’Morgana musimy użyć zanegowanej funkcji logicznej Y, czyli ~Y.
Definicja operatora OR:
Kod: |
p q Y=p+q
A: 1 1 =1
B: 1 0 =1
C: 0 1 =1
D: 0 0 =0
1 2 3
|
Gdzie:
„+” - spójnik „lub” z naturalnej logiki człowieka o definicji wyłącznie w obszarze ABC123
Y=p+q
Y=1 <=> p=1 lub q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Definicja operatora AND:
Kod: |
p q Y=p*q
A: 1 1 =1
B: 1 0 =0
C: 0 1 =0
D: 0 0 =0
1 2 3
|
Gdzie:
„*” - spójnik „i” z naturalnej logiki człowieka o definicji wyłącznie w linii A123.
Y=p*q
Y=1 <=> p=1 i q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Dowód zero-jedynkowy I prawa de’Morgana:
Kod: |
p q Y=p+q ~p ~q ~Y=~p*~q Y=~(~p*~q)
A: 1 1 =1 0 0 =0 =1
B: 1 0 =1 0 1 =0 =1
C: 0 1 =1 1 0 =0 =1
D: 0 0 =0 1 1 =1 =0
1 2 3 4 5 6 7
|
Kolumny ABCD3 i ABCD7 są tożsame, co jest dowodem formalnym prawa de’Morgana:
Y = p+q = ~(~p*~q)
Prawo de’Morgana mówi nam, że dowolną bramkę logiczną OR możemy zastąpić bramką AND negując w niej wejścia p i q oraz wyjście Y.
Komentarz:
Obszar ABCD123 to definicja operatora OR
Kolumna ABCD4 (~p) to zanegowana kolumna ABCD1 (p)
Kolumna ABCD5 (~q) to zanegowana kolumna ABCD2 (q)
Jak generujemy odpowiedzi na wyjściu ~Y?
Bierzemy dowolną kombinację ~p i ~q z obszaru ABCD45 i sprawdzamy w operatorze AND jej odpowiedź na wyjściu.
Przykłady:
1.
B45 = [0,1]
Z definicji operatora AND(*) odczytujemy dla tej kombinacji odpowiedź na wyjściu:
~Y=0
2.
D45 = [1,1]
W operatorze AND(*) odczytujemy:
~Y=1
Kolumna ABCD7 (Y) to zanegowana kolumna ABCD6 (~Y).
Definicja logiki ujemnej i dodatniej w operatorach OR i AND:
Funkcja logiczna Y jest zapisana w logice dodatniej gdy jest niezaprzeczona (Y).
Funkcja logiczna Y zapisana jest w logice ujemnej gdy jest zaprzeczona (~Y).
Prawo de’Morgana w układzie równań logicznych:
A: Y=p+q
B: ~Y=~p*~q
Oczywiście zachodzi tu prawo podwójnego przeczenia:
Y = ~(~Y)
Podstawiając A i B mamy prawo de’Morgana dla spójnika „lub”(+):
p+q = ~(~p*~q)
Prawo przejścia do logiki przeciwnej:
Negujemy zmienne i wymieniamy spójniki na przeciwne
A: Y=p+q(r+~s)
B: Y = p+[q*(r+~s)]
C: ~Y = ~p*[~q+(~r*s)]
Algorytm Wuja Zbója:
B: Uzupełniamy brakujące nawiasy i spójniki
C: Negujemy zmienne i wymieniamy spójniki na przeciwne, „lub”(+) na „i”(*) i odwrotnie.
Zauważmy wyżej, że prawo de’Morgana w dwóch postaciach:
A.
Prawo de’Morgana w jednym równaniu logicznym:
Y = p+q = ~(~p*~q)
B.
Prawo de’Morgana w układzie równań logicznych
Y = p+q
~Y = ~p*~q
Świetnie opisuje naturalną logikę człowieka.
Przykład przedszkolaka:
W.
Jutro pójdę do kina lub do teatru
Y=K+T
Matematycznie oznacza to:
W.
Dotrzymam słowa (Y=1) wtedy i tylko wtedy gdy jutro pójdę do kina (K=1) lub do teatru (T=1)
Y=K+T
Y=1 <=> K=1 lub T=1
… a kiedy skłamię?
Przejście ze zdaniem A do logiki ujemnej poprzez negację zmiennych i wymianę spójników na przeciwne.
~Y=~K*~T
U.
Skłamię (~Y=1) wtedy i tylko wtedy gdy jutro nie pójdę do kina (~K=1) i nie pójdę do teatru (~T=1)
~Y=~K*~T
~Y =1 <=> ~K=1 i ~T=1
Czytamy!
Prawdą jest (=1), że skłamię (~Y) wtedy i tylko wtedy gdy jutro nie pójdę do kina (~K=1) i nie pójdę do teatru (~T=1)
Prawo de’Morgana:
Y = K+T = ~(~K*~T)
Nie może się zdarzyć ~(…), że jutro nie pójdę do kina (~K=1) i nie pójdę do teatru (~T=1)
1.4 II Prawo de’Morgana:
II Prawo de’Morgana
p*q = ~(~p+~q)
Na początek zróbmy kluczową sztuczkę:
Y = p*q = ~(~p+~q)
stąd:
Y=p*q
Y=~(~p+~q)
Dowolną tożsamość logiczną wolno nam zanegować stronami.
Druga linię negujemy stronami:
~Y = ~[~(~p+~q)]
~Y=~p+~q
bo prawo podwójnego przeczenia:
~[~(x)] = x
stąd końcowa postać prawa de’Morgana w układzie równań logicznych:
Y=p*q
~Y=~p+~q
Doskonale widać, że do opisu przypadku:
~p+~q
w prawie de’Morgana musimy użyć zanegowanej funkcji logicznej Y, czyli ~Y.
Definicja operatora AND:
Kod: |
p q Y=p*q
A: 1 1 =1
B: 1 0 =0
C: 0 1 =0
D: 0 0 =0
1 2 3
|
Gdzie:
„*” - spójnik „i” z naturalnej logiki człowieka o definicji wyłącznie w linii A123.
Y=p*q
Y=1 <=> p=1 i q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Definicja operatora OR:
Kod: |
p q Y=p+q
A: 1 1 =1
B: 1 0 =1
C: 0 1 =1
D: 0 0 =0
1 2 3
|
Gdzie:
„+” - spójnik „lub” z naturalnej logiki człowieka o definicji wyłącznie w obszarze ABC123
Y=p+q
Y=1 <=> p=1 lub q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Dowód zero-jedynkowy II prawa de’Morgana:
Kod: |
p q Y=p*q ~p ~q ~Y=~p+~q Y=~(~p+~q)
A: 1 1 =1 0 0 =0 =1
B: 1 0 =0 0 1 =1 =0
C: 0 1 =0 1 0 =1 =0
D: 0 0 =0 1 1 =1 =0
1 2 3 4 5 6 7
|
Kolumny ABCD3 i ABCD7 są tożsame, co jest dowodem formalnym prawa de’Morgana:
Y = p*q = ~(~p+~q)
Prawo de’Morgana mówi nam, że dowolną bramkę logiczną AND możemy zastąpić bramką OR negując w niej wejścia p i q oraz wyjście Y.
Komentarz:
Obszar ABCD123 to definicja operatora OR
Kolumna ABCD4 (~p) to zanegowana kolumna ABCD1 (p)
Kolumna ABCD5 (~q) to zanegowana kolumna ABCD2 (q)
Jak generujemy odpowiedzi na wyjściu ~Y?
Bierzemy dowolną kombinację ~p i ~q z obszaru ABCD45 i sprawdzamy w operatorze OR jej odpowiedź na wyjściu.
Przykłady:
1.
B45 = [0,1]
Z definicji operatora OR odczytujemy dla tej kombinacji odpowiedź na wyjściu:
~Y=1
2.
A45 = [0,0]
W operatorze OR odczytujemy:
~Y=0
Zauważmy wyżej że prawo de’Morgana w dwóch postaciach:
A.
Prawo de’Morgana w jednym równaniu logicznym:
Y = p*q = ~(~p+~q)
B.
Prawo de’Morgana w układzie równań logicznych
Y = p*q
~Y = ~p+~q
Świetnie opisuje naturalną logikę człowieka.
Przykład przedszkolaka:
W.
Jutro pójdę do kina i do teatru
Y=K*T
Matematycznie oznacza to:
W.
Dotrzymam słowa (Y=1) wtedy i tylko wtedy gdy jutro pójdę do kina (K=1) i do teatru (T=1)
Y=K*T
Y=1 <=> K=1 i T=1
… a kiedy skłamię?
Przejście ze zdaniem A do logiki ujemnej poprzez negację zmiennych i wymianę spójników na przeciwne.
~Y=~K+~T
U.
Skłamię (~Y=1) wtedy i tylko wtedy gdy jutro nie pójdę do kina (~K=1) lub nie pójdę do teatru (~T=1)
~Y=~K+~T
~Y =1 <=> ~K=1 lub ~T=1
Czytamy!
Prawdą jest (=1), że skłamię (~Y) wtedy i tylko wtedy gdy jutro nie pójdę do kina (~K=1) lub nie pójdę do teatru (~T=1)
Prawo de’Morgana:
Y = K*T = ~(~K+~T)
Nie może się zdarzyć ~(…), że jutro nie pójdę do kina (~K=1) lub nie pójdę do teatru (~T=1)
1.5 Najważniejszy dowód w logice matematycznej
Twierdzenie:
Spójniki logiczne z naturalnej logiki człowieka „lub”(+) oraz „i”(*) nie są operatorami logicznymi
Operator OR
Definicja operatora OR:
Kod: |
p q Y=p+q
A: 1 1 =1
B: 1 0 =1
C: 0 1 =1
D: 0 0 =0
1 2 3
|
Gdzie:
„+” - spójnik „lub” z naturalnej logiki człowieka o definicji wyłącznie w obszarze ABC123
Y=p+q
Y=1 <=> p=1 lub q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Prawo de’Morgana dla spójnika „lub”(+) w dwóch postaciach:
A.
Prawo de’Morgana w jednym równaniu:
Y = p+q = ~(~p*~q)
B.
Prawo de’Morgana w układzie równań logicznych:
Y=p+q
~Y=~p*~q
Z prawa de’Morgana wynika, że wyłącznie negując wszystkie zmienne musimy otrzymać definicję operatora AND.
A.
Y = p+q = ~(~p*~q)
Negujemy wyłącznie zmienne wejściowe p i q:
y = (~p)+(~q) = ~[(~(~p) * ~(~q)]
Prawo podwójnego przeczenia:
p=~(~p)
stąd:
y = ~p+~q = ~(p*q)
Negujemy funkcje logiczną Y (wyjście bramki y):
~y = ~(~p+~q) = p*q
Ostatnie równanie to oczywiście pełna definicja operatora AND o którym za chwilę.
Dokładnie to samo musimy uzyskać dla prawa de’Morgana zapisanego w układzie równań logicznych:
A: Y=p+q
B: ~Y=~p*~q
Negujemy wszystkie zmienne otrzymując operator AND:
C: ~y=~p+~q
D: y=p*q
Układ równań C i D to oczywiście pełna definicja operatora AND.
Kluczowy dowód:
Jeśli w równaniu opisującym powyższy operator OR znaczek „+” jest kompletnym operatorem, opisuje wszystkie cztery linie, to zgodnie z prawem de’Morgana negując wszystkie zmienne musimy otrzymać definicję operatora AND.
Mamy opis tabeli wyżej w równaniu algebry Boole’a:
A: Y = p+q
Negujemy wszystkie zmienne:
C: ~Y=~p+~q
To oczywiście nie jest definicja operatora AND!
Z równania A otrzymaliśmy C, brakuje B i D.
Równanie C to jedynie połówka operatora AND.
cnd
Operator AND
Definicja operatora AND:
Kod: |
p q Y=p*q
A: 1 1 =1
B: 1 0 =0
C: 0 1 =0
D: 0 0 =0
1 2 3
|
Gdzie:
„*” - spójnik „i” z naturalnej logiki człowieka o definicji wyłącznie w linii A123.
Y=p*q
Y=1 <=> p=1 i q=1
To jest dwuelementowa algebra Boole’a zatem w pozostałych liniach musi być w wyniku 0.
Prawo de’Morgana dla spójnika „i”(*) w dwóch postaciach:
A.
Prawo de’Morgana w jednym równaniu:
Y = p*q = ~(~p+~q)
B.
Prawo de’Morgana w układzie równań logicznych:
Y=p*q
~Y=~p+~q
Z prawa de’Morgana wynika, że wyłącznie negując wszystkie zmienne otrzymujemy definicję operatora OR.
A.
Y = p*q = ~(~p+~q)
Negujemy wyłącznie zmienne wejściowe p i q:
y = (~p)*(~q) = ~[(~(~p) +~(~q)]
Prawo podwójnego przeczenia:
p=~(~p)
stąd:
y = ~p*~q = ~(p+q)
Negujemy funkcje logiczną Y (wyjście bramki y):
~y = ~(~p*~q) = p+q
Ostatnie równanie to oczywiście pełna definicja operatora OR o którym było wyżej.
Dokładnie to samo musimy uzyskać dla prawa de’Morgana zapisanego w układzie równań logicznych:
A: Y=p*q
B: ~Y=~p+~q
Negujemy wszystkie zmienne otrzymując operator OR:
C: ~y=~p*~q
D: y=p+q
Układ równań C i D to oczywiście pełna definicja operatora OR.
Kluczowy dowód:
Jeśli w równaniu opisującym powyższy operator AND znaczek „*” jest kompletnym operatorem, opisuje wszystkie cztery linie, to zgodnie z prawem de’Morgana negując wszystkie zmienne musimy otrzymać definicję operatora OR.
Mamy opis tabeli wyżej w równaniu algebry Boole’a:
A: Y = p*q
Negujemy wszystkie zmienne:
C: ~Y=~p*~q
To oczywiście nie jest definicja operatora OR!
Z równania A otrzymaliśmy C, brakuje B i D.
Równanie C to jedynie połówka operatora AND.
cnd
1.6 Równanie ogólne dla operatorów OR i AND
Operator OR ## Operator AND
p+q = ~(~p*~q) ## p*q = ~(~p+~q)
gdzie:
## - różne na mocy definicji
Tabele zero-jedynkowe po obu stronach znaku ## możemy generować na nieskończenie wiele sposobów, ale znak ## pozostanie na wieki, nie da się go usunąć, na mocy definicji.
Przykład:
Definicja operatora NAND:
Kod: |
p q Y=pNANDq | Y=p*q
1 1 =0 | =1
1 0 =1 | =0
0 1 =1 | =0
0 0 =1 | =0
|
Doskonale widać że:
Y = pNANDq = ~(p*q)
stąd:
p*q = ~(pNANDq)
Definicja operatora NOR:
Kod: |
p q Y=pNORq | Y=p+q
1 1 =0 | =1
1 0 =0 | =1
0 1 =0 | =1
0 0 =1 | =0
|
Doskonale widać że:
Y = pNORq = ~(p+q)
stąd:
p+q = ~(pNORq)
Równanie ogólne dla operatorów OR i AND dalej będzie tu świętością:
Operator OR ## operator AND
p+q = ~(pNORq) ## p*q = ~(pNANDq)
gdzie:
## - różne na mocy definicji
Operatorów NOR i NAND nikt nie używa bezpośrednio w żadnym języku świata, bo nasz mózg to nie głupek, doskonale widzi że można je trywialnie zastąpić operatorami OR i AND.
Przykład:
Y = pNORq = ~(p+q) = ~p*~q - prawo de’Morgana
Nikt nie zrozumie zdania:
A.
Jutro pójdę do kina NOR do teatru
Y=K NOR T
Każdy zrozumie zdanie równoważne:
B.
Jutro nie pójdę do kina i nie pójdę do teatru
Y = ~K*~T
C.
Jutro nie pójdę ani do kina, ani do teatru
Zdania B i C są matematycznie tożsame.
Nie ma w logice spójnika „ani … ani” jak to jest w niektórych opracowaniach.
Znaczenie „ani” w różnych kontekstach jest różne, ale to tylko „urozmaicenie” fundamentu B a nie nowy spójnik logiczny!
Oczywiście dla NAND i NOR zachodzą prawa de’Morgana:
Y= pNORq
Przejście do logiki przeciwnej poprzez negacje zmiennych i wymianę spójników
~Y = ~pNAND~q
Związek logiki dodatniej i ujemnej:
Y=~(~Y)
stąd prawo de’Morgana dla operatorów NOR i NAND:
pNORq = ~(~pNAND~q)
Dowód zero-jedynkowy:
Kod: |
p q Y=pNORq ~p ~q ~Y=~pNAND~q Y=~(~pNAND~q)
A: 1 1 =0 0 0 =1 =0
B: 1 0 =0 0 1 =1 =0
C: 0 1 =0 1 0 =1 =0
D: 0 0 =1 1 1 =0 =1
1 2 3 4 5 6 7
|
Kolumny ABCD3 i ABCD7 są identyczne, co jest dowodem formalnym poprawności prawa de’Morgana dla operatorów NOR i NAND.
pNORq = ~(~pNAND~q)
cnd
Jak powstała powyższa tabela?
Obszar ABCD123 to definicja operatora NOR.
Kolumna ABCD4 (~p) to zanegowana kolumna ABCD1 (p)
Kolumna ABCD5 (~q) to zanegowana kolumna ABCD2 (q)
Jak generujemy kolumnę ABCD6 (~Y)?
Bierzemy dowolną kombinację ~p i ~q z obszaru ABCD45 i sprawdzamy w operatorze NAND jej odpowiedź na wyjściu.
Przykłady:
1.
B45 = [0,1]
Z definicji operatora NAND odczytujemy dla tej kombinacji odpowiedź na wyjściu:
~Y=1
2.
D45 = [1,1]
W operatorze NAND odczytujemy:
~Y=0
Mam nadzieję, że wszyscy załapali technikę dowodów matematycznych metodą rachunku zero-jedynkowego.
|
|
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
|