|
Ś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: 35967
Przeczytał: 15 tematów
Skąd: z innego Wszechświata Płeć: Mężczyzna
|
Wysłany: Sob 20:35, 16 Mar 2013 Temat postu: Algebra Boole'a dla matematyków |
|
|
Wstęp:
Fundamentem sprzętowej (hardware) realizacji dowolnego komputera jest algebra Boole’a.
Język asemblera dowolnego procesora (software), to w 100% ta sama algebra Boole’a, to fundament wszelkich innych języków programowania stworzonych przez człowieka.
Oczywiście sprzęt bez oprogramowania to tylko kupa złomu.
Hardware i software, mimo wspólnego fundamentu jakim jest algebra Boole’a to światy zupełnie rozłączne.
Jeśli piszemy program komputerowy realizujący funkcje logiczną:
Y=~(~p+~q)
to nie możemy zrealizować tej funkcji w bramkach logicznych i tak zbudowanego układu wstawić do programu komputerowego. Programowa realizacja powyższego układu to kilka linijek programu napisanego w języku asemblera, natomiast sprzętowa to bramka OR plus trzy negatory.
W dzisiejszej logice sprzętowa algebra Boole’a jest poprawna, natomiast symboliczna algebra Boole’a (asembler) totalnie nie istnieje.
Definicja języka asemblera:
Asembler to logika (program) totalnie symboliczna izolowana od idiotycznych zer i jedynek.
Definicja symbolicznej algebry Boole’a (język asemblera):
Język asemblera w algebrze Boole’a to opis dowolnej linii tabeli zero-jedynkowej równaniem algebry Boole’a, tabele zero-jedynkowe operatorów logicznych automatycznie są tu zbędne.
W dniu dzisiejszym jest to wśród Ziemian wiedza tajemna, zupełnie nie znana. Dzisiejsza logika matematyczna to epoka kamienna, czyli operowanie bezwzględnymi zerami i jedynkami, kodem maszynowym logiki. W przełożeniu na świat komputerów odpowiada to pisaniu programu bezpośrednio w kodzie maszynowym, przed poznaniem języka asemblera. Problem w tym, że człowiek pisał programy w zerach i jedynkach przez mgnienie oka po czym natychmiast wynalazł symboliczny język asemblera i całe mnóstwo języków wysokiego poziomu.
Proponuję zatem podział logiki na następujące działy:
1.
Algebra Boole’a to sprzętowa algebra Boole’a w dzisiejszym jej rozumieniu
2.
Algebra Kubusia to symboliczna algebra Boole’a izolowana od bezwzględnych zer i jedynek (język asemblera)
Algebra Kubusia honoruje wszelkie prawa algebry Boole’a ponieważ algebra Boole’a jest podzbiorem algebry Kubusia. Co ciekawe, wszelkie prawa algebry Kubusia, mimo iż spójniki logiczne są tu fundamentalnie czym innym (nie są operatorami), są poprawne także w sprzętowej algebrze Boole’a!
Spis treści:
1.0 Notacja
2.0 Aksjomatyka algebry Boole’a
3.0 Operatory jednoargumentowe
4.0 Sprzętowa algebra Boole’a
4.1 Rachunek zero-jedynkowy
4.2 Minimalny zestaw operatorów w algebrze Boole’a
1.0 Notacja
Znaczenie znaczków w algebrze Boole’a:
„~” - operator negacji
„+” - operator OR
„*” - operator AND
„=> - operator implikacji prostej =>
“~>” - operator implikacji odwrotnej ~>
<=> - operator równoważności
Definicje najważniejszych operatorów logicznych wyrażone operatorami OR(+) i AND(*):
1.
OR:
Y=p+q
2.
NOR:
Y=~(p+q)
3.
AND:
Y=p*q
4.
NAND:
Y=~(p*q)
5.
Implikacja prosta =>:
p=>q = ~p+q
6.
Implikacja odwrotna ~>:
p~>q = p+~q
7.
Równoważność <=>:
p<=>q = p*q + ~p*~q
8.
XOR:
pXORq = p*~q + ~p*q
2.0 Aksjomatyka algebry Boole’a
Aksjomat to powszechna zgodność w postrzeganiu rzeczywistości.
1.
Fundament algebry Boole’a:
0 # 1
gdzie:
# - rożne
Nigdy nie może być:
0 = 1
2.
Definicja zmiennej binarnej:
Zmienna binarna to zmienna mogąca przyjmować w osi czasu wyłącznie dwie wartości 0 albo 1
3.
Definicja funkcji logicznej:
Funkcja logiczna n-zmiennych binarnych (wyjście Y) to odpowiedź układu na wszystkie możliwe kombinacje (wartościowania) zmiennych wejściowych.
Zwyczajowo funkcje logiczną oznaczamy literą Y.
Przykład funkcji logicznej:
Y = p+q*(r+~s)
4.
Definicja operatora logicznego:
Operator logiczny to dwuargumentowa funkcja logiczna
Cechy operatora logicznego:
Przy dwóch argumentach możliwe są wyłącznie cztery wartościowania zmiennych wejściowych p i q.
Kod: |
p q Y=?
1 1 =x
1 0 =x
0 1 =x
0 0 =x
|
5.
Na mocy definicji funkcji logicznej możliwe jest 16 różnych operatorów logicznych:
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
|
W technice:
Operator logiczny = bramka logiczna
Najważniejszymi operatorami w logice są operatory OR i AND oraz operator negacji NP.
2.1 Aksjomaty wynikające z operatorów OR i AND
Definicja operatora OR:
Kod: |
p q Y=p+q
1 1 =1
1 0 =1
0 1 =1
0 0 =0
|
Aksjomaty wynikające z definicji operatora OR:
1+1=1
1+0=1
0+1=1
0+0=0
Definicja operatora AND:
Kod: |
p q Y=p*q
1 1 =1
1 0 =0
0 1 =0
0 0 =0
|
Aksjomaty wynikające z definicji operatora AND:
1*1=1
1*0=0
0*1=0
0*0=0
Koniec.
To jest kompletna aksjomatyka algebry Boole’a.
3.0 Operatory jednoargumentowe
Operator transmisji
W tabeli wszystkich możliwych operatorów logicznych mamy dwa tożsame operatory transmisji:
pPq, pQq
Definicja operatora transmisji:
Kod: |
p q Y=pPq
1 1 =1
1 0 =1
0 1 =0
0 0 =0
|
Doskonale widać, że wyjście Y zależy wyłącznie od zmiennej wejściowej p, zmienna q jest kompletnie bez znaczenia, zatem powyższy operator to w rzeczywistości operator jednoargumentowy.
Kod: |
p Y=pP=p
1 =1
1 =1
0 =0
0 =0
|
Stąd mamy definicję operatora transmisji:
Y=p
Tabela prawdy operatora transmisji (definicja):
Operator negacji
W tabeli wszystkich możliwych operatorów logicznych mamy dwa tożsame operatory negacji:
pNPq, pNQq
Definicja operatora negacji:
Kod: |
p q Y=pNPq
1 1 =0
1 0 =0
0 1 =1
0 0 =1
|
Doskonale widać, że wyjście Y zależy wyłącznie od zmiennej wejściowej p, zmienna q jest kompletnie bez znaczenia, zatem powyższy operator to w rzeczywistości operator jednoargumentowy.
Kod: |
p Y=pNP=~p
1 =0
1 =0
0 =1
0 =1
|
Stąd mamy definicję operatora negacji:
Y=~p
Tabela prawdy operatora negacji (definicja):
Gdzie:
„~” - symbol negacji
Prawo podwójnego przeczenia:
p = ~(~p)
Dowód formalny:
Kod: |
p ~p p=~(~p)
1 0 1
0 1 0
1 2 3
|
Powyższą tabelkę wypełniono na mocy definicji negatora.
Tożsamość kolumn 1 i 3 jest dowodem formalnym powyższego prawa algebry Boole’a.
Prawo algebry Boole’a:
Prawo algebry Boole’a to identyczna odpowiedź dwóch różnych fizycznie układów na te same wartościowania na wejściach układu. Układy takie są matematycznie tożsame.
Dowolny operator logiczny może być zbudowany na nieskończenie wiele sposobów, jednak jeśli na ten sam zestaw wymuszeń na wejściach p i q otrzymamy identyczne odpowiedzi na wyjściu Y, to te realizacje są matematycznie tożsame.
Przykład:
Y=p+q
Prawo algebry Boole’a:
q = q*(q+x)
gdzie:
x - dowolna funkcja logiczna, nawet nieskończona
stąd:
Y = p+q*(q+x) = p+q
To jest najprostsza realizacja operatora OR na nieskończenie wiele sposobów.
Pierwsze prawo algebry Boole’a właśnie poznaliśmy:
p=~(~p)
Przykład z języka mówionego:
Jestem uczciwy
U
Nie jestem uczciwy
~U
Nieprawdą jest ~(…) ze jestem nieuczciwy
~(~U) = U
4.0 Sprzętowa algebra Boole’a
Podstawowym zadaniem sprzętowej algebry Boole’a jest fizyczna realizacja operatora X na wszelkie możliwe sposoby, w szczególności przy pomocy innych operatorów.
Jak wkrótce zobaczymy dysponując zaledwie jednym operatorem logicznym:
NAND, NOR, implikacji prostej => albo implikacji odwrotnej ~>
Możemy zrealizować wszystkie inne operatory a zatem zbudować (sprzętowo!) dowolny komputer.
Definicja zero-jedynkowa 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
|
Aksjomaty wynikające z definicji operatora OR:
1+1 =1
1+0 =1
0+1 =1
0+0 =0
Prawa algebry Boole’a wynikające z definicji operatora OR:
p+0 =p
p+1 =1
p+p =p
p+~p =1
Dowody formalne:
Kod: |
p ~p 1 0 p+1 p+0 p+~p
1 0 1 0 1 1 1
0 1 1 0 1 0 1
|
Poprawność wszystkich praw algebry Boole’a widać jak na dłoni.
W szczególności:
p+0=p
czego dowodem jest tożsamość odpowiednich kolumn wynikowych
Definicja zero-jedynkowa 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
|
Aksjomaty wynikające z definicji operatora AND:
1*1 =1
1*0 =0
0*1 =0
0*0 =0
Prawa algebry Boole’a wynikające z definicji operatora AND:
p*1 =p
p*0 =0
p*p =p
p*~p=0
Dowody formalne:
Kod: |
p ~p 1 0 p*1 p*0 p*~p
1 0 1 0 1 0 0
0 1 1 0 0 0 0
|
Poprawność wszystkich praw algebry Boole’a widać jak na dłoni.
W szczególności:
p*1=p
czego dowodem jest tożsamość odpowiednich kolumn wynikowych
Fundament algebry Boole’a:
p*~p =0
p+~p =1
Przydatne prawa dodatkowe
Łączność:
p+(q+r) = (p+q)+r
p*(q*r)=(p*q)*r
Przemienność:
p+q=q+r
p*q=q*r
Mnożenie logiczne wielomianów:
(p+q)*(r+s) = p*r+p*s+q*r+q*s
Wyciąganie zmiennej przed nawias:
p*q+p*r = p*(q+r)
Najważniejszym prawem algebry Boole’a jest prawo przejścia do logiki przeciwnej.
Prawo przejścia do logiki przeciwnej:
Negujemy zmienne i wymieniamy operatory na przeciwne
Operatory komplementarnie przeciwne to:
OR(+) vs AND(*)
Implikacja prosta => vs implikacja odwrotna ~>
Przykłady:
1.
Y=p+q
~Y=~p*~q
2.
Y=p*q
~Y=~p+~q
3.
p=>q
~p~>~q
4.
(p+q) => (r*s)
(~p*~q)~>(~r+~s)
Stąd mamy kolejne prawa algebry Boole’a.
1.
Prawo De Morgana dla operatora OR:
Y=p+q
~Y=~p*~q
Związek logiki dodatniej (bo Y) i ujemnej (bo ~Y)
Y=~(~Y) - prawo podwójnego przeczenia
Stąd mamy prawo De Morgana dla operatora OR:
Y = p+q = ~(~p*~q)
2.
Prawo De Morgana dla operatora AND
Y=p*q
~Y=~p+~q
Związek logiki dodatniej (bo Y) i ujemnej (bo ~Y)
Y=~(~Y) - prawo podwójnego przeczenia
Stąd mamy prawo De Morgana dla operatora AND:
Y = p*q = ~(~p+~q)
3.
p=>q
~p~>~q
Definicje operatorów implikacji wyrażone przy pomocy operatorów OR i AND
p=>q = ~p+q = ~(p*~q) - definicja implikacji prostej =>
p~>q = p+~q = ~(~p*q) - definicja implikacji odwrotnej ~>
Prawa Kubusia:
p=>q = ~p~>~q
p~>q = ~p=>~q
Dowody formalne praw Kubusia w równaniach algebry Boole’a:
I prawo Kubusia:
p=>q = ~p~>~q
p=>q = ~p+q - definicja implikacji prostej =>
p~>q = p+~q - definicja implikacji odwrotnej ~>
~p~>~q = (~p)+ ~(~q) = ~p+q = p=>q
cnd
II prawo Kubusia:
p~>q = ~p=>~q
p~>q = p+~q - definicja implikacji odwrotnej ~>
p=>q = ~p+q - definicja implikacji prostej =>
~p=>~q = (~p) + ~(~q) = p+~q = p~>q
cnd
Przykład minimalizacji funkcji logicznej:
Y = p+q = p*q + p*~q + ~p*q
Dowód tożsamości:
Y = p*q + p*~q + ~p*q = p(q+~q) + ~p*q = p*1 + ~p*q = p+~p*q
Wykorzystane prawa:
1. Wyciągniecie zmiennej p przed nawias
2. q+~q=1
3. p*1=p
Mamy:
Y=p+(~p*q)
Przejście do logiki ujemnej poprzez negacje zmiennych i wymianę spójników:
~Y = ~p*(p+~q) = p*~p + ~p*~q = 0 + ~p*~q = ~p*~q
Wykorzystane prawa
1. Przejście do logiki ujemnej
2. Mnożenie zmiennej ~p przez wielomian
3. p*~p=0
4. 0+x=x
Mamy funkcję minimalną w logice ujemnej (bo ~Y):
~Y=~p*~q
Przechodząc do logiki przeciwnej mamy funkcje minimalną w logice dodatniej (bo Y)
Y = p+q
cnd
Oczywiście układ równań minimalnych:
Y=p+q
~Y=~p*~q
to nic innego jak definicja operatora OR w algebrze Kubusia.
4.1 Rachunek zero-jedynkowy
Zasady dowodów formalnych w algebrze Boole’a (rachunek zero-jedynkowy) poznamy na przykładzie dowodzenia przemienności argumentów w operatorach OR(+), AND(*), implikacji prostej =>, implikacji odwrotnej ~>.
Sprzętowa algebra Boole’a to przemiatanie przy pomocy rachunku zero-jedynkowych kompletnych tabel na wszelkie możliwe sposoby, nie interesuje nas tu rzeczywiste znaczenie zer i jedynek wewnątrz operatorów. Można łatwo napisać program komputerowy automatycznie generujący i udowadniający przy pomocy rachunku zero-jedynkowego wszelkie znane prawa algebry Boole’a.
Przykładowo, taki program bez problemu wyrzuci, iż w operatorach OR i AND zachodzi przemienność argumentów zaś, w operatorach implikacji nie zachodzi przemienność argumentów.
Niestety, Ziemianie kompletnie tego nie rozumieją twierdząc że w OR i AND program działa dobrze, czyli przemienność argumentów występuje zawsze i wszędzie (i słusznie), natomiast w implikacji program działa źle, bo wedle nich są implikacje w których przemienność argumentów nie występuje, ale są też implikacje w których przemienność argumentów występuje. Ziemianie są oczywiście w błędzie bowiem definicja implikacji jest jedna i nie może być raz tak a raz siak. Takie rozumowanie natychmiast generuje matematykę niejednoznaczną, której miejsce jest w koszu na śmieci.
Nie może być tak, że zasady dowodzenia przemienności argumentów w operatorze X (AND i OR) różnią się od zasad dowodzenia przemienności argumentów w operatorze Y (=> i ~>)
Definicja operatora OR:
Kod: |
p q Y=p+q
1 1 =1
1 0 =1
0 1 =1
0 0 =0
|
Komputerowy dowód przemienności argumentów w operatorze OR:
Kod: |
p q Y=p+q q p Y=q+p
A: 1 1 1 1 1 1
B: 1 0 1 0 1 1
C. 0 1 1 1 0 1
D: 0 0 0 0 0 0
1 2 3 4 5 6
|
Tożsamość kolumn wynikowych 3 i 6 jest dowodem przemienności argumentów w operatorze OR
Definicja operatora AND:
Kod: |
p q Y=p*q
1 1 =1
1 0 =0
0 1 =0
0 0 =0
|
Komputerowy dowód przemienności argumentów w operatorze AND:
Kod: |
p q Y=p*q q p Y=q*p
A: 1 1 1 1 1 1
B: 1 0 0 0 1 0
C. 0 1 0 1 0 0
D: 0 0 0 0 0 0
1 2 3 4 5 6
|
Tożsamość kolumn wynikowych 3 i 6 jest dowodem przemienności argumentów w operatorze AND.
Zobaczmy teraz jak wygląda przemienność argumentów w implikacji.
Definicja operatora implikacji prostej =>:
Kod: |
p q p=>q
1 1 =1
1 0 =0
0 0 =1
0 1 =1
|
W algebrze Boole’a wiersze możemy dowolnie przestawiać to bez znaczenia, dla łatwości dowodów formalnych powinniśmy jednak zachowywać tą samą kolejność wejściową p i q zarówno w definicjach jak i dowodach.
Formalny dowód braku przemienności argumentów w implikacji prostej =>:
Kod: |
p q p=>q q p q=>p
A: 1 1 =1 1 1 =1
B: 1 0 =0 0 1 =1
C: 0 0 =1 0 0 =1
D: 0 1 =1 1 0 =0
1 2 3 4 5 6
|
Brak tożsamości kolumn ABCD3 i ABCD6 jest dowodem formalnym braku przemienności argumentów w implikacji prostej.
Definicja operatora implikacji odwrotnej ~>:
Kod: |
p q p~>q
1 1 =1
1 0 =1
0 0 =1
0 1 =0
|
Formalny dowód braku przemienności argumentów w implikacji odwrotnej ~>:
Kod: |
p q p~>q q p q~>p
A: 1 1 =1 1 1 =1
B: 1 0 =1 0 1 =0
C: 0 0 =1 0 0 =1
D: 0 1 =0 1 0 =1
1 2 3 4 5 6
|
Brak tożsamości kolumn ABCD3 i ABCD6 jest dowodem formalnym braku przemienności argumentów w implikacji odwrotnej.
4.2 Minimalny zestaw operatorów w algebrze Boole’a
W sprzętowej algebrze Boole’a możemy postawić problem:
Jaki jest zestaw minimalny operatorów logicznych pozwalających zbudować wszystkie inne operatory.
Twierdzenie:
W sprzętowej algebrze Boole’a dysponując dowolnym z czterech operatorów:
NAND, NOR, implikacja prosta =>, albo implikacja odwrotna ~>
Możemy zbudować wszystkie inne operatory logiczne, zatem i dowolny komputer.
Definicje operatorów logicznych w równaniach algebry Boole’a mamy w pkt. 1.0.
Dowód:
1.
Definicja operatora NAND:
Y=~(p*q)
Dowód:
Wymuszamy q=1 i mamy definicję negatora
Y=~(p*1) = ~p
Mając negator, negujemy prawą stronę otrzymując definicje bramki AND:
Y=~(~(p*q) = p*q
Mając negator i bramkę AND mamy wszystko co potrzeba do zbudowania dowolnego innego operatora
2.
Definicja operatora NOR:
Y=~(p+q)
Dowód:
Wymuszamy q=0 i mamy definicję negatora
Y=~(p+0) = ~p
Mając negator, negujemy prawą stronę otrzymując definicje bramki OR:
Y=~(~(p+q) = p+q
Mając negator i bramkę OR mamy wszystko co potrzeba do zbudowania dowolnego innego operatora
3.
Definicja implikacji prostej:
p=>q = ~p+q
Dowód:
Wymuszając q=0 mamy definicję negatora
p=>q = ~p+0 = ~p
Mając negator negujemy sygnał wejściowy ~p i mamy bramkę OR
p=>q = ~(~p)+q = p+q
Mając negator i bramkę OR mamy wszystko co potrzeba do zbudowania dowolnego innego operatora
4.
Definicja implikacji odwrotnej:
p~>q = p+~q
Dowód:
Wymuszając p=0 mamy definicję negatora
p=>q = p+~q = ~q
Mając negator negujemy sygnał wejściowy ~q i mamy bramkę OR
p=>q = p+~(~q) = p+q
Mając negator i bramkę OR mamy wszystko co potrzeba do zbudowania dowolnego innego operatora
Poprawność powyższych dowodów można bez problemu pokazać w laboratorium techniki cyfrowej.
Jeśli ktokolwiek twierdzi iż nie jest to prawdą, to musi udowodnić iż techniczna algebra Boole’a nie jest matematyką ścisłą, życzę powodzenia.
Pozostałe operatory nie są dobre bo …
5.
Definicja operatora AND:
Y=p*q
Nie mamy tu szans na zbudowanie negatora
6.
Definicja operatora OR:
Y=p+q
Tu również nie mamy szans na zbudowanie negatora
7.
Definicja XOR:
p XOR q = p*~q + ~p*q
Tu nie mamy szans ani na zbudowanie operatora OR, ani tez na zbudowanie operatora AND
Dowód:
Wymuszamy p=1
p XOR q = 1*~q + 0*q = ~q
Mamy definicje negatora ale nie mamy szans na definicja AND, ani też na definicję OR
8.
Równoważność:
p<=>q = p*q+~p*~q
W tym przypadku mamy identycznie jak w XOR
Podstawiamy p=1
p<=>q = 1*q + 0*~q = q
Podstawiamy:
p=0
p<=>q = 0*q + 1*~q = ~q
Mamy definicje negatora ale nie mamy szans na definicja AND, ani też na definicję OR
cnd
Ostatnio zmieniony przez rafal3006 dnia Wto 9:41, 19 Mar 2013, w całości zmieniany 5 razy
|
|
Powrót do góry |
|
|
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
rafal3006
Opiekun Forum Kubusia
Dołączył: 30 Kwi 2006
Posty: 35967
Przeczytał: 15 tematów
Skąd: z innego Wszechświata Płeć: Mężczyzna
|
Wysłany: Sob 20:43, 16 Mar 2013 Temat postu: |
|
|
...
|
|
Powrót do góry |
|
|
Zobacz poprzedni temat :: Zobacz następny temat |
Autor |
Wiadomość |
rafal3006
Opiekun Forum Kubusia
Dołączył: 30 Kwi 2006
Posty: 35967
Przeczytał: 15 tematów
Skąd: z innego Wszechświata Płeć: Mężczyzna
|
Wysłany: Sob 21:36, 16 Mar 2013 Temat postu: |
|
|
.
|
|
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
|