Forum ŚFiNiA Strona Główna Ś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.
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Techniczna algebra Boole'a

 
Napisz nowy temat   Odpowiedz do tematu    Forum ŚFiNiA Strona Główna -> Metodologia / Forum Kubusia
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
rafal3006
Opiekun Forum Kubusia



Dołączył: 30 Kwi 2006
Posty: 32228
Przeczytał: 33 tematy

Skąd: z innego Wszechświata
Płeć: Mężczyzna

PostWysł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
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum ŚFiNiA Strona Główna -> Metodologia / Forum Kubusia Wszystkie czasy w strefie CET (Europa)
Strona 1 z 1

 
Skocz do:  
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
Regulamin