Czy matematycy znają prosty algorytm wyznaczania KPN i DPN?

[rafal3006]

Ciekaw jestem …
Czy matematycy znają prosty algorytm wyznaczania KPN i DPN dla dowolnie długiej funkcji logicznej (algorytm komputerowy)?

Przykład:
Wyznaczyć KPN i DPN z poniższych funkcji logicznych.
1.
\(\displaystyle{ a* \neg b + b* \neg c}\)
2.
\(\displaystyle{ ( \neg a+b)*( \neg b+c)}\)

[royas]

Z prostym nie ma problemu. Problem jest ze złożonością takiego algorytmu.

[rafal3006]

Pod pojęciem "prosty" rozumiem banalny, czyli możliwy do wykonania np. maksymalnie w dwóch krokach zarówno przez człowieka jak i przez komputer.

Czy znasz taki?

Czy możesz go zaprezentować na powyższym przykładzie?

[yorgin]

A czy możesz używać symboli matematycznych? Gwiazdki i kropki nie są powszechnie używanymi symbolami na koniunkcję i alternatywę.

I przydałoby się doprecyzować, czym jest jeden krok.

[rafal3006]

Jestem ze świata techniki, dla mnie z kolei ptaszki matematyków są mało czytelne.
To są dwa tożsame systemy symboli:

Kod: Zaznacz cały

http://www.fpga.agh.edu.pl/russek/tul/PDF/algebrab.pdf

Skoro założyłem temat z symbolami \(\displaystyle{ *}\) i \(\displaystyle{ +}\) to myślę, że możemy przy nich zostać.

Wymyśliłem taki algorytm:

Dana jest funkcja KPN

Krok 1.
Robię tabelę zero-jedynkową dla KPN
Krok 2.
Odczytuję funkcję DPN

Koniec dowodu.

Czy matematycy to znają?

Po prostu nie wiem, bo to jest tak banalne iż niemożliwe jest aby matematycy tego nie znali.

[yorgin]

Jednak jesteśmy na forum matematycznym, nie technicznym.

A prezentowany przez Ciebie algorytm można zastosować dla dowolnego zdania o dowolnie wielu zmiennych oraz dowolnych spójnikach logicznych - matematykom jest on dobrze znany, można takie rzeczy robić na pierwszym roku na ćwiczeniach z logiki i teorii mnogości (lub cokolwiek o innej nazwie ale odpowiednim zakresie) o ile są przewidziane w programie.

[rafal3006]

Wiem jak wygląda mój algorytm w świecie techniki.
Na 100% jest inny niż algorytm w świecie matematyki.
Oczywiście algorytmów może być wiele, ale mój na pewno nie jest znany matematykom.

Czy możesz zatem rozwiązać moje dwa przykłady na gruncie algorytmu matematyków?
Wtedy ja pokażę bardzo prosty algorytm działający w świecie techniki.

Jeśli musisz to możesz używać matematycznych ptaszków, jakoś przeżyję, ale chcę zauważyć, że tu jest cała masa tematów z moją notacją.

[yorgin]

Wiem jak wygląda mój algorytm w świecie techniki.
Na 100% jest inny niż algorytm w świecie matematyki.

Różnica polega zapewne na tym, iż używamy innych symboli na operatory logiczne.

Skrótowo. Najprostsza aczkolwiek niedająca najbardziej zwartej postaci, to analiza tabelowa. Dla zdania

\(\displaystyle{ Z = (\neg p \vee q)\wedge (p\vee \neg q)}\)

robię tabelkę

\(\displaystyle{ \begin{array}{c|c|c}
p & q & Z\\
0 & 0 & 1 \\
0& 1 & 0\\
1& 0 & 0\\
1& 1 & 1
\end{array}}\)

i odczytuję układy, dla których mam zdanie prawdziwe. Stąd tworzę sobie zdanie w DPN

\(\displaystyle{ (\neg p\wedge \neg q)\vee (p\wedge q)}\)

w sposób łatwy do odgadnięcia.

[rafal3006]

Wiem jak wygląda mój algorytm w świecie techniki.
Na 100% jest inny niż algorytm w świecie matematyki.

Różnica polega zapewne na tym, iż używamy innych symboli na operatory logiczne.

Skrótowo. Najprostsza aczkolwiek niedająca najbardziej zwartej postaci, to analiza tabelowa. Dla zdania

\(\displaystyle{ Z = (\neg p \vee q)\wedge (p\vee \neg q)}\)

robię tabelkę

\(\displaystyle{ \begin{array}{c|c|c}
p & q & Z\\
0 & 0 & 1 \\
0& 1 & 0\\
1& 0 & 0\\
1& 1 & 1
\end{array}}\)

i odczytuję układy, dla których mam zdanie prawdziwe. Stąd tworzę sobie zdanie w DPN

\(\displaystyle{ (\neg p\wedge \neg q)\vee (p\wedge q)}\)

w sposób łatwy do odgadnięcia.

Weźmy problem odwrotny:
\(\displaystyle{ (\neg p\wedge \neg q)\vee (p\wedge q)}\)

Tu z kolei musisz odczytywać kiedy zdanie jest fałszywe?
\(\displaystyle{ Z = (\neg p \vee q)\wedge (p\vee \neg q)}\)

Na jakiej matematycznej podstawie?
Skąd to wziąłeś?
Skąd wiesz że jedną w jedną stronę musisz szukać zdań prawdziwych a w drugą fałszywych?
Kiedy których?

Rzecz najważniejsza:
Na jakiej podstawie matematycznej tworzysz równanie algebry Boole'a z tabeli zero-jedynkowej?
Chodzi mi o konkretne prawo algebry Boole'a które musiałeś zastosować i zastosowałeś, ale go nie znasz.
Ja znam to prawo ...

Sorry, zdążyłeś na powyzsze odpowiedzieć wiec odtwarzam.

[norwimaj]

Tabelki to dobra metoda dla (bardzo) małych formuł. Miałem nadzieję, że rafal3006 zaprezentuje jakiś wielomianowy sposób. Wtedy bym się czegoś nowego nauczył.

Przy okazji, kto poda postać DNF poniższej formuły? Może nie jest to ambitny przykład, ale dobrze jest przetestować swoje algorytmy najpierw na prostych przykładach.


\(\displaystyle{ (\neg p_{12}\lor \neg p_{21})\land (\neg p_{13}\lor \neg p_{31})\land (\neg p_{14}\lor \neg p_{41})\land (\neg p_{15}\lor \neg p_{51})\land (\neg p_{21}\lor \neg p_{12})\land\\
(\neg p_{23}\lor \neg p_{32})\land (\neg p_{24}\lor \neg p_{42})\land (\neg p_{25}\lor \neg p_{52})\land (\neg p_{31}\lor \neg p_{13})\land (\neg p_{32}\lor \neg p_{23})\land\\
(\neg p_{34}\lor \neg p_{43})\land (\neg p_{35}\lor \neg p_{53})\land (\neg p_{41}\lor \neg p_{14})\land (\neg p_{42}\lor \neg p_{24})\land (\neg p_{43}\lor \neg p_{34})\land\\
(\neg p_{45}\lor \neg p_{54})\land (\neg p_{51}\lor \neg p_{15})\land (\neg p_{52}\lor \neg p_{25})\land (\neg p_{53}\lor \neg p_{35})\land (\neg p_{54}\lor \neg p_{45})\land\\
(p_{12}\lor p_{21})\land (p_{13}\lor p_{31})\land (p_{14}\lor p_{41})\land (p_{15}\lor p_{51})\land (p_{21}\lor p_{12})\land\\
(p_{23}\lor p_{32})\land (p_{24}\lor p_{42})\land (p_{25}\lor p_{52})\land (p_{31}\lor p_{13})\land (p_{32}\lor p_{23})\land\\
(p_{34}\lor p_{43})\land (p_{35}\lor p_{53})\land (p_{41}\lor p_{14})\land (p_{42}\lor p_{24})\land (p_{43}\lor p_{34})\land\\
(p_{45}\lor p_{54})\land (p_{51}\lor p_{15})\land (p_{52}\lor p_{25})\land (p_{53}\lor p_{35})\land (p_{54}\lor p_{45})\land\\
(\neg p_{12}\lor \neg p_{23}\lor p_{13})\land (\neg p_{12}\lor \neg p_{24}\lor p_{14})\land (\neg p_{12}\lor \neg p_{25}\lor p_{15})\land\\
(\neg p_{13}\lor \neg p_{32}\lor p_{12})\land (\neg p_{13}\lor \neg p_{34}\lor p_{14})\land (\neg p_{13}\lor \neg p_{35}\lor p_{15})\land\\
(\neg p_{14}\lor \neg p_{42}\lor p_{12})\land (\neg p_{14}\lor \neg p_{43}\lor p_{13})\land (\neg p_{14}\lor \neg p_{45}\lor p_{15})\land\\
(\neg p_{15}\lor \neg p_{52}\lor p_{12})\land (\neg p_{15}\lor \neg p_{53}\lor p_{13})\land (\neg p_{15}\lor \neg p_{54}\lor p_{14})\land\\
(\neg p_{21}\lor \neg p_{13}\lor p_{23})\land (\neg p_{21}\lor \neg p_{14}\lor p_{24})\land (\neg p_{21}\lor \neg p_{15}\lor p_{25})\land\\
(\neg p_{23}\lor \neg p_{31}\lor p_{21})\land (\neg p_{23}\lor \neg p_{34}\lor p_{24})\land (\neg p_{23}\lor \neg p_{35}\lor p_{25})\land\\
(\neg p_{24}\lor \neg p_{41}\lor p_{21})\land (\neg p_{24}\lor \neg p_{43}\lor p_{23})\land (\neg p_{24}\lor \neg p_{45}\lor p_{25})\land\\
(\neg p_{25}\lor \neg p_{51}\lor p_{21})\land (\neg p_{25}\lor \neg p_{53}\lor p_{23})\land (\neg p_{25}\lor \neg p_{54}\lor p_{24})\land\\
(\neg p_{31}\lor \neg p_{12}\lor p_{32})\land (\neg p_{31}\lor \neg p_{14}\lor p_{34})\land (\neg p_{31}\lor \neg p_{15}\lor p_{35})\land\\
(\neg p_{32}\lor \neg p_{21}\lor p_{31})\land (\neg p_{32}\lor \neg p_{24}\lor p_{34})\land (\neg p_{32}\lor \neg p_{25}\lor p_{35})\land\\
(\neg p_{34}\lor \neg p_{41}\lor p_{31})\land (\neg p_{34}\lor \neg p_{42}\lor p_{32})\land (\neg p_{34}\lor \neg p_{45}\lor p_{35})\land\\
(\neg p_{35}\lor \neg p_{51}\lor p_{31})\land (\neg p_{35}\lor \neg p_{52}\lor p_{32})\land (\neg p_{35}\lor \neg p_{54}\lor p_{34})\land\\
(\neg p_{41}\lor \neg p_{12}\lor p_{42})\land (\neg p_{41}\lor \neg p_{13}\lor p_{43})\land (\neg p_{41}\lor \neg p_{15}\lor p_{45})\land\\
(\neg p_{42}\lor \neg p_{21}\lor p_{41})\land (\neg p_{42}\lor \neg p_{23}\lor p_{43})\land (\neg p_{42}\lor \neg p_{25}\lor p_{45})\land\\
(\neg p_{43}\lor \neg p_{31}\lor p_{41})\land (\neg p_{43}\lor \neg p_{32}\lor p_{42})\land (\neg p_{43}\lor \neg p_{35}\lor p_{45})\land\\
(\neg p_{45}\lor \neg p_{51}\lor p_{41})\land (\neg p_{45}\lor \neg p_{52}\lor p_{42})\land (\neg p_{45}\lor \neg p_{53}\lor p_{43})\land\\
(\neg p_{51}\lor \neg p_{12}\lor p_{52})\land (\neg p_{51}\lor \neg p_{13}\lor p_{53})\land (\neg p_{51}\lor \neg p_{14}\lor p_{54})\land\\
(\neg p_{52}\lor \neg p_{21}\lor p_{51})\land (\neg p_{52}\lor \neg p_{23}\lor p_{53})\land (\neg p_{52}\lor \neg p_{24}\lor p_{54})\land\\
(\neg p_{53}\lor \neg p_{31}\lor p_{51})\land (\neg p_{53}\lor \neg p_{32}\lor p_{52})\land (\neg p_{53}\lor \neg p_{34}\lor p_{54})\land\\
(\neg p_{54}\lor \neg p_{41}\lor p_{51})\land (\neg p_{54}\lor \neg p_{42}\lor p_{52})\land (\neg p_{54}\lor \neg p_{43}\lor p_{53})\land\\
(p_{12}\lor p_{13}\lor p_{14}\lor p_{15})\land (p_{21}\lor p_{23}\lor p_{24}\lor p_{25})\land (p_{31}\lor p_{32}\lor p_{34}\lor p_{35})\land\\
(p_{41}\lor p_{42}\lor p_{43}\lor p_{45})\land (p_{51}\lor p_{52}\lor p_{53}\lor p_{54})}\)

Skąd wiesz że jedną w jedną stronę musisz szukać zdań prawdziwych a w drugą fałszywych?

Nie wiem, do czego się odnosisz, ale domyślam się z kontekstu. Sprawa jest oczywista. Jeśli chcemy znaleźć CNF formuły \(\displaystyle{ \varphi}\), to możemy znaleźć DNF formuły \(\displaystyle{ \neg\varphi}\) a następnie ten DNF zanegować.

-- 18 mar 2013, o 22:05 --

Chodzi mi o konkretne prawo algebry Boole'a które musiałeś zastosować i zastosowałeś, ale go nie znasz.
Ja znam to prawo ...

Nie bądź pyszny, bo Cię zjedzą.

[yorgin]

Weźmy problem odwrotny:
\(\displaystyle{ (\neg p\wedge \neg q)\vee (p\wedge q)}\)

Tu z kolei musisz odczytywać kiedy zdanie jest fałszywe?
\(\displaystyle{ Z = (\neg p \vee q)\wedge (p\vee \neg q)}\)

Tak.

Na jakiej matematycznej podstawie?
Skąd to wziąłeś?
Skąd wiesz że jedną w jedną stronę musisz szukać zdań prawdziwych a w drugą fałszywych?
Kiedy których?

Odpowiadając kolejno:

Na podstawie interpretacji zachowania się alternatywy/koniunkcji.

Istnieje coś takiego, jak wymyślanie formuł. Mogę wziąć cokolwiek, byleby spełniało założenia postaci, do jakiej sprowadzam. I sprawdzam, czy jest to formuła równoważna. Mogę brać cokolwiek, ale wybieram to, z czego najprościej jest budować. Z klocków, które są prawdziwe/fałszywe tylko przy ściśle określonym wartościowaniu. Krótko podsumowując - wymyśliłem kilka miesięcy temu niezależnie od źródeł dowód konstruowalności spójników z negacji i alternatywy/koniunkcji albo też z NOR/NAND i teraz łatwo mogę nimi tworzyć co tylko mi się podoba. Ale to już temat na inną dyskusję.

Proste prawa logiki plus odpowiedź na poprzednie pytanie.

Kiedy to zależy od tego, do jakiej postaci dążę.

P.S. Nie znam teorii algebr Boole'a. Bazuję na elementarzu, z którym całkiem dobrze sobie radzę i całkiem sporo jestem w stanie zrobić.

[Zordon]

\(\displaystyle{ (\neg p_{12}\lor \neg p_{21})\land (\neg p_{13}\lor \neg p_{31})\land (\neg p_{14}\lor \neg p_{41})\land (\neg p_{15}\lor \neg p_{51})\land (\neg p_{21}\lor \neg p_{12})\land\\
(\neg p_{23}\lor \neg p_{32})\land (\neg p_{24}\lor \neg p_{42})\land (\neg p_{25}\lor \neg p_{52})\land (\neg p_{31}\lor \neg p_{13})\land (\neg p_{32}\lor \neg p_{23})\land\\
(\neg p_{34}\lor \neg p_{43})\land (\neg p_{35}\lor \neg p_{53})\land (\neg p_{41}\lor \neg p_{14})\land (\neg p_{42}\lor \neg p_{24})\land (\neg p_{43}\lor \neg p_{34})\land\\
(\neg p_{45}\lor \neg p_{54})\land (\neg p_{51}\lor \neg p_{15})\land (\neg p_{52}\lor \neg p_{25})\land (\neg p_{53}\lor \neg p_{35})\land (\neg p_{54}\lor \neg p_{45})\land\\
(p_{12}\lor p_{21})\land (p_{13}\lor p_{31})\land (p_{14}\lor p_{41})\land (p_{15}\lor p_{51})\land (p_{21}\lor p_{12})\land\\
(p_{23}\lor p_{32})\land (p_{24}\lor p_{42})\land (p_{25}\lor p_{52})\land (p_{31}\lor p_{13})\land (p_{32}\lor p_{23})\land\\
(p_{34}\lor p_{43})\land (p_{35}\lor p_{53})\land (p_{41}\lor p_{14})\land (p_{42}\lor p_{24})\land (p_{43}\lor p_{34})\land\\
(p_{45}\lor p_{54})\land (p_{51}\lor p_{15})\land (p_{52}\lor p_{25})\land (p_{53}\lor p_{35})\land (p_{54}\lor p_{45})\land\\
(\neg p_{12}\lor \neg p_{23}\lor p_{13})\land (\neg p_{12}\lor \neg p_{24}\lor p_{14})\land (\neg p_{12}\lor \neg p_{25}\lor p_{15})\land\\
(\neg p_{13}\lor \neg p_{32}\lor p_{12})\land (\neg p_{13}\lor \neg p_{34}\lor p_{14})\land (\neg p_{13}\lor \neg p_{35}\lor p_{15})\land\\
(\neg p_{14}\lor \neg p_{42}\lor p_{12})\land (\neg p_{14}\lor \neg p_{43}\lor p_{13})\land (\neg p_{14}\lor \neg p_{45}\lor p_{15})\land\\
(\neg p_{15}\lor \neg p_{52}\lor p_{12})\land (\neg p_{15}\lor \neg p_{53}\lor p_{13})\land (\neg p_{15}\lor \neg p_{54}\lor p_{14})\land\\
(\neg p_{21}\lor \neg p_{13}\lor p_{23})\land (\neg p_{21}\lor \neg p_{14}\lor p_{24})\land (\neg p_{21}\lor \neg p_{15}\lor p_{25})\land\\
(\neg p_{23}\lor \neg p_{31}\lor p_{21})\land (\neg p_{23}\lor \neg p_{34}\lor p_{24})\land (\neg p_{23}\lor \neg p_{35}\lor p_{25})\land\\
(\neg p_{24}\lor \neg p_{41}\lor p_{21})\land (\neg p_{24}\lor \neg p_{43}\lor p_{23})\land (\neg p_{24}\lor \neg p_{45}\lor p_{25})\land\\
(\neg p_{25}\lor \neg p_{51}\lor p_{21})\land (\neg p_{25}\lor \neg p_{53}\lor p_{23})\land (\neg p_{25}\lor \neg p_{54}\lor p_{24})\land\\
(\neg p_{31}\lor \neg p_{12}\lor p_{32})\land (\neg p_{31}\lor \neg p_{14}\lor p_{34})\land (\neg p_{31}\lor \neg p_{15}\lor p_{35})\land\\
(\neg p_{32}\lor \neg p_{21}\lor p_{31})\land (\neg p_{32}\lor \neg p_{24}\lor p_{34})\land (\neg p_{32}\lor \neg p_{25}\lor p_{35})\land\\
(\neg p_{34}\lor \neg p_{41}\lor p_{31})\land (\neg p_{34}\lor \neg p_{42}\lor p_{32})\land (\neg p_{34}\lor \neg p_{45}\lor p_{35})\land\\
(\neg p_{35}\lor \neg p_{51}\lor p_{31})\land (\neg p_{35}\lor \neg p_{52}\lor p_{32})\land (\neg p_{35}\lor \neg p_{54}\lor p_{34})\land\\
(\neg p_{41}\lor \neg p_{12}\lor p_{42})\land (\neg p_{41}\lor \neg p_{13}\lor p_{43})\land (\neg p_{41}\lor \neg p_{15}\lor p_{45})\land\\
(\neg p_{42}\lor \neg p_{21}\lor p_{41})\land (\neg p_{42}\lor \neg p_{23}\lor p_{43})\land (\neg p_{42}\lor \neg p_{25}\lor p_{45})\land\\
(\neg p_{43}\lor \neg p_{31}\lor p_{41})\land (\neg p_{43}\lor \neg p_{32}\lor p_{42})\land (\neg p_{43}\lor \neg p_{35}\lor p_{45})\land\\
(\neg p_{45}\lor \neg p_{51}\lor p_{41})\land (\neg p_{45}\lor \neg p_{52}\lor p_{42})\land (\neg p_{45}\lor \neg p_{53}\lor p_{43})\land\\
(\neg p_{51}\lor \neg p_{12}\lor p_{52})\land (\neg p_{51}\lor \neg p_{13}\lor p_{53})\land (\neg p_{51}\lor \neg p_{14}\lor p_{54})\land\\
(\neg p_{52}\lor \neg p_{21}\lor p_{51})\land (\neg p_{52}\lor \neg p_{23}\lor p_{53})\land (\neg p_{52}\lor \neg p_{24}\lor p_{54})\land\\
(\neg p_{53}\lor \neg p_{31}\lor p_{51})\land (\neg p_{53}\lor \neg p_{32}\lor p_{52})\land (\neg p_{53}\lor \neg p_{34}\lor p_{54})\land\\
(\neg p_{54}\lor \neg p_{41}\lor p_{51})\land (\neg p_{54}\lor \neg p_{42}\lor p_{52})\land (\neg p_{54}\lor \neg p_{43}\lor p_{53})\land\\
(p_{12}\lor p_{13}\lor p_{14}\lor p_{15})\land (p_{21}\lor p_{23}\lor p_{24}\lor p_{25})\land (p_{31}\lor p_{32}\lor p_{34}\lor p_{35})\land\\
(p_{41}\lor p_{42}\lor p_{43}\lor p_{45})\land (p_{51}\lor p_{52}\lor p_{53}\lor p_{54})}\)

A co to ? Zgaduję, że jakiś trudny przykład dla SAT-solvera.

[norwimaj]

Zordon, odpowiadam na pw, żeby nie psuć innym zabawy.

[rafal3006]

Sorry że przechodzę na znaczki z technicznej algebry Boole'a, ptaszki mnie męczą, mam słaby wzrok.

Tabelki to dobra metoda dla (bardzo) małych formuł. Miałem nadzieję, że rafal3006 zaprezentuje jakiś wielomianowy sposób. Wtedy bym się czegoś nowego nauczył.

Chodzi mi o konkretne prawo algebry Boole'a które musiałeś zastosować i zastosowałeś, ale go nie znasz.
Ja znam to prawo ...

Nie bądź pyszny, bo Cię zjedzą.

… no to cie zaskoczę.
Nauczę cię tworzyć równania algebry Boole’a z dowolnej tabeli zero-jedynkowej czteroma sposobami, w naturalnej logice człowieka (dwa) i w logice zero (dwa) będącej logiką totalnie odwrotną do naturalnej logiki człowieka, ale równoważną.

Prawa algebry Boole’a których na pewno nie znasz, a które pozwalają tworzyć równania algebry Boole’a z dowolnej tabeli zero-jedynkowej (albo odwrotnie) to prawa Prosiaczka.

I prawo Prosiaczka:
\(\displaystyle{ p=0 \Leftrightarrow \neg p=1}\)
II prawo Prosiaczka:
\(\displaystyle{ p=1 \Leftrightarrow \neg p=0}\)

Pierwsze prawo Prosiaczka wykorzystujemy przy tworzeniu równań algebry Boole’a w logice człowieka, gdzie wszystkie zmienne sprowadzamy do jedynek.
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)
W poziomach wykorzystujemy wtedy definicję spójnika „i”(*):
\(\displaystyle{ Y=p*q}\)
co matematycznie oznacza:
\(\displaystyle{ Y=1 \Leftrightarrow p=1 i q=1}\)
Natomiast w pionach korzystamy ze spójnika „lub”(+):
\(\displaystyle{ Y=p+q}\)
\(\displaystyle{ Y=1 \Leftrightarrow p=1 lub q=1}\)

Drugie prawo Prosiaczka wykorzystujemy przy tworzeniu równań algebry Boole’a w logice zero gdzie wszystkie zmienne sprowadzamy do zera
Jeśli \(\displaystyle{ p=1}\) to \(\displaystyle{ \neg p=0}\)
W poziomach wykorzystujemy tu definicję spójnika „lub”(+) w logice zero:
\(\displaystyle{ Y=p+q}\)
\(\displaystyle{ Y=0 \Leftrightarrow p=0 i q=0}\)
Natomiast w pionach korzystamy ze spójnika „i”(*) w logice zero:
\(\displaystyle{ Y=p*q}\)
\(\displaystyle{ Y=0 \Leftrightarrow p=0}\) lub \(\displaystyle{ q=0}\)

Przy okazji zobaczysz skąd się biorą postaci KPN i DPN.

Oczywiście nie miejsce na forum aby tłumaczyć szczegółowo bardzo prosty podkład matematyczny, nauczę cię jak to robić od czysto inżynierskiej strony.

Ziemianie umieją tworzyć równania algebry Boole’a dla dowolnej tabeli zero-jedynkowej czego dowód znajdziemy w skrypcie

Kod: Zaznacz cały

http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html

.

Problem w tym że nie znają podkładu matematycznego dzięki któremu mogą to robić, nie znają praw Prosiaczka … czyli robią „na czuja”?


Logika człowieka

Tworzenie równań logicznych w naturalnej logice człowieka:
Wszystkie zmienne sprowadzamy do jedynek na mocy prawa Prosiaczka:
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)

Weźmy nasz przykład.
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y\\
A: 1 & 1 & 1\\
B: 0 & 0 & 1\\
C: 0 & 1 & 0\\
D: 1 & 0 & 0\\
\end{tabular}}\)

Równania algebry Boole’a opisujące poszczególne linie uzyskane metodą

Kod: Zaznacz cały

http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html

.

Algorytm:
Jeśli na danej pozycji występuje jedynka to przepisujemy nagłówek tabeli
Jeśli na danej pozycji występuje zero to przepisujemy zanegowany nagłówek tabeli
W poziomie korzystamy ze spójnika „i”(*) natomiast w pionie ze spójnika „lub”(+)

Na mocy tego algorytmu równania opisujące poszczególne linie tabeli to:
\(\displaystyle{ \begin{tabular}{rcll}
p & q & Y\\
A: 1 & 1 & 1 & /Y=p*q \\
B: 0 & 0 & 1 & /Y= \neg p* \neg q \\
C: 0 & 1 & 0 & / \neg Y= \neg p * q\\
D: 1 & 0 & 0 & / \neg Y= p * \neg q\\
\end{tabular}}\)

Stąd mamy dwa równania algebry Boole’a opisujące powyższą tabelę:
1.
Równanie opisujące wynikowe jedynki (wyłącznie linie A i B):
\(\displaystyle{ Y = p*q + \neg p*\neg q}\)
2.
Równanie opisujące wynikowe zera (wyłącznie linie C i D):
\(\displaystyle{ \neg Y=\neg p*q + p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y}\) # \(\displaystyle{ \neg Y}\)

gdzie:
# - różne w znaczeniu:
Jeśli \(\displaystyle{ Y=0}\) to \(\displaystyle{ \neg Y=1}\)
Odwrotnie też zachodzi:
Jeśli \(\displaystyle{ \neg Y=1}\) to \(\displaystyle{ Y=0}\)
Stąd mamy prawa Prosiaczka:
\(\displaystyle{ Y=0 \Leftrightarrow \neg Y=1}\)
\(\displaystyle{ Y=1 \Leftrightarrow \neg Y=0}\)
mówiące o związku logiki dodatniej (bo \(\displaystyle{ Y}\)) z logiką ujemną (bo \(\displaystyle{ \neg Y}\))

Matematycznie zachodzi też:
\(\displaystyle{ Y = \neg (\neg Y)}\) - związek logiki dodatniej i ujemnej

Podstawiając 1 i 2 mamy prawo De Morgana dla logiki dodatniej (bo \(\displaystyle{ Y}\)):
3.
\(\displaystyle{ Y = p*q + \neg p*\neg q = \neg (\neg p*q + p*\neg q) = (p+\neg q)*(\neg p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y=Y}\)

Podstawiając 1 i 3 mamy związek KPN i DPN:
\(\displaystyle{ Y = p*q + \neg p*\neg q = (p+\neg q)*(\neg p+q)}\)

Prawo De Morgana w logice ujemnej (bo \(\displaystyle{ \neg Y}\)):
\(\displaystyle{ \neg Y = \neg (Y)}\) - matematyczny związek logiki ujemnej (bo \(\displaystyle{ \neg Y}\)) i dodatniej (bo \(\displaystyle{ Y}\))
Podstawiając 1 i 2 mamy:
4.
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = \neg (p*q + \neg p*\neg q) = (\neg p+\neg q)*(p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ \neg Y = \neg Y}\)

Podstawiając 2 i 4 mamy związek KPN i DPN:
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = (\neg p+\neg q)*(p+q)}\)

Czy wszyscy rozumieją skąd biorą się postaci KPN i DPN?


Logika zero

Tworzenie równań logicznych w logice zero.
W logice zero wszystkie zmienne sprowadzamy do zera korzystając z prawa Prosiaczka:
Jeśli \(\displaystyle{ p=1}\) to \(\displaystyle{ \neg p=0}\)

Weźmy nasz przykład.
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y\\
A: 1 & 1 & 1\\
B: 0 & 0 & 1\\
C: 0 & 1 & 0\\
D: 1 & 0 & 0\\
\end{tabular}}\)
Algorytm:
Jeśli na danej pozycji występuje zero to przepisujemy nagłówek tabeli
Jeśli na danej pozycji występuje jedynka to przepisujemy zanegowany nagłówek tabeli
W poziomie korzystamy ze spójnika „lub”(+) natomiast w pionie ze spójnika „i”(*)

Na mocy tego algorytmu równania opisujące poszczególne linie tabeli to:
\(\displaystyle{ \begin{tabular}{rclll}
p & q & Y & \neg Y\\
A: 1 & 1 & 1 & 0 & / \neg Y= \neg p+ \neg q \\
B: 0 & 0 & 1 & 0 & / \neg Y= p + q \\
C: 0 & 1 & 0 & 1 & / Y= p + \neg q\\
D: 1 & 0 & 0 & 1 & / Y= \neg p + q\\
\end{tabular}}\)

Stąd uzyskujemy dwa równania algebry Boole’a opisujące powyższą tabelę.

Równanie logiczne opisujące wyłącznie linie A i B:
1Z:
\(\displaystyle{ \neg Y=(\neg p+\neg q)*(p+q)}\)

Równanie logiczne opisujące wyłącznie linie C i D:
2Z:
\(\displaystyle{ Y=(p+\neg q)*(\neg p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y}\) # \(\displaystyle{ \neg Y}\)
gdzie:
# - różne w znaczeniu:
Jeśli \(\displaystyle{ Y=0}\) to \(\displaystyle{ \neg Y=1}\)
Odwrotnie też zachodzi:
Jeśli \(\displaystyle{ \neg Y=1}\) to \(\displaystyle{ Y=0}\)
Stąd mamy prawa Prosiaczka:
\(\displaystyle{ Y=0 \Leftrightarrow \neg Y=1}\)
\(\displaystyle{ Y=1 \Leftrightarrow \neg Y=0}\)
mówiące o związku logiki dodatniej (bo \(\displaystyle{ Y}\)) z logiką ujemną (bo \(\displaystyle{ \neg Y}\))

Matematycznie zachodzi też:
\(\displaystyle{ Y = \neg (\neg Y)}\) - związek logiki dodatniej i ujemnej

Podstawiając 2Z i 1Z mamy prawo De Morgana dla logiki dodatniej (bo Y):
3Z.
\(\displaystyle{ Y = (p+\neg q)*(\neg p+q) = \neg [(\neg p+\neg q)*(p+q)] = p*q + \neg p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y=Y}\)

Podstawiając 3Z i 2Z mamy związek KPN i DPN:
\(\displaystyle{ Y = p*q + \neg p*\neg q = (p+\neg q)*(\neg p+q)}\)

Prawo De Morgana w logice ujemnej (bo \(\displaystyle{ \neg Y}\)):
\(\displaystyle{ \neg Y = \neg (Y)}\) - matematyczny związek logiki ujemnej (bo \(\displaystyle{ \neg Y}\)) i dodatniej (bo \(\displaystyle{ Y}\))

Podstawiając 1Z i 2Z mamy:
4Z.
\(\displaystyle{ \neg Y = (\neg p+\neg q)*(p+q) = \neg [(p+\neg q)*(\neg p+q)] = \neg p*q + p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ \neg Y = \neg Y}\)

Podstawiając 4Z i 1Z mamy związek KPN i DPN:
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = (\neg p+\neg q)*(p+q)}\)

Czy wszyscy rozumieją skąd biorą się postaci KPN i DPN?

Podsumowanie:
Logika człowieka i logika zero to logiki totalnie odwrotne, ale równoważne. Jedna z nich jest zbędna.
Oczywiście w kosmos wykopujemy logikę zero, odwrotną do naturalnej logiki człowieka.

Jak wam się podoba?

[bartek118]

Sorry że przechodzę na znaczki z technicznej algebry Boole'a, ptaszki mnie męczą, mam słaby wzrok.

Tabelki to dobra metoda dla (bardzo) małych formuł. Miałem nadzieję, że rafal3006 zaprezentuje jakiś wielomianowy sposób. Wtedy bym się czegoś nowego nauczył.

Chodzi mi o konkretne prawo algebry Boole'a które musiałeś zastosować i zastosowałeś, ale go nie znasz.
Ja znam to prawo ...

Nie bądź pyszny, bo Cię zjedzą.

… no to cie zaskoczę.
Nauczę cię tworzyć równania algebry Boole’a z dowolnej tabeli zero-jedynkowej czteroma sposobami, w naturalnej logice człowieka (dwa) i w logice zero (dwa) będącej logiką totalnie odwrotną do naturalnej logiki człowieka, ale równoważną.

Prawa algebry Boole’a których na pewno nie znasz, a które pozwalają tworzyć równania algebry Boole’a z dowolnej tabeli zero-jedynkowej (albo odwrotnie) to prawa Prosiaczka.

I prawo Prosiaczka:
\(\displaystyle{ p=0 \Leftrightarrow \neg p=1}\)
II prawo Prosiaczka:
\(\displaystyle{ p=1 \Leftrightarrow \neg p=0}\)

Pierwsze prawo Prosiaczka wykorzystujemy przy tworzeniu równań algebry Boole’a w logice człowieka, gdzie wszystkie zmienne sprowadzamy do jedynek.
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)
W poziomach wykorzystujemy wtedy definicję spójnika „i”(*):
\(\displaystyle{ Y=p*q}\)
co matematycznie oznacza:
\(\displaystyle{ Y=1 \Leftrightarrow p=1 i q=1}\)
Natomiast w pionach korzystamy ze spójnika „lub”(+):
\(\displaystyle{ Y=p+q}\)
\(\displaystyle{ Y=1 \Leftrightarrow p=1 lub q=1}\)

Drugie prawo Prosiaczka wykorzystujemy przy tworzeniu równań algebry Boole’a w logice zero gdzie wszystkie zmienne sprowadzamy do zera
Jeśli \(\displaystyle{ p=1}\) to \(\displaystyle{ \neg p=0}\)
W poziomach wykorzystujemy tu definicję spójnika „lub”(+) w logice zero:
\(\displaystyle{ Y=p+q}\)
\(\displaystyle{ Y=0 \Leftrightarrow p=0 i q=0}\)
Natomiast w pionach korzystamy ze spójnika „i”(*) w logice zero:
\(\displaystyle{ Y=p*q}\)
\(\displaystyle{ Y=0 \Leftrightarrow p=0}\) lub \(\displaystyle{ q=0}\)

Przy okazji zobaczysz skąd się biorą postaci KPN i DPN.

Oczywiście nie miejsce na forum aby tłumaczyć szczegółowo bardzo prosty podkład matematyczny, nauczę cię jak to robić od czysto inżynierskiej strony.

Ziemianie umieją tworzyć równania algebry Boole’a dla dowolnej tabeli zero-jedynkowej czego dowód znajdziemy w skrypcie

Kod: Zaznacz cały

http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html

.

Problem w tym że nie znają podkładu matematycznego dzięki któremu mogą to robić, nie znają praw Prosiaczka … czyli robią „na czuja”?


Logika człowieka

Tworzenie równań logicznych w naturalnej logice człowieka:
Wszystkie zmienne sprowadzamy do jedynek na mocy prawa Prosiaczka:
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)

Weźmy nasz przykład.
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y\\
A: 1 & 1 & 1\\
B: 0 & 0 & 1\\
C: 0 & 1 & 0\\
D: 1 & 0 & 0\\
\end{tabular}}\)

Równania algebry Boole’a opisujące poszczególne linie uzyskane metodą

Kod: Zaznacz cały

http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html

.

Algorytm:
Jeśli na danej pozycji występuje jedynka to przepisujemy nagłówek tabeli
Jeśli na danej pozycji występuje zero to przepisujemy zanegowany nagłówek tabeli
W poziomie korzystamy ze spójnika „i”(*) natomiast w pionie ze spójnika „lub”(+)

Na mocy tego algorytmu równania opisujące poszczególne linie tabeli to:
\(\displaystyle{ \begin{tabular}{rcll}
p & q & Y\\
A: 1 & 1 & 1 & /Y=p*q \\
B: 0 & 0 & 1 & /Y= \neg p* \neg q \\
C: 0 & 1 & 0 & / \neg Y= \neg p * q\\
D: 1 & 0 & 0 & / \neg Y= p * \neg q\\
\end{tabular}}\)

Stąd mamy dwa równania algebry Boole’a opisujące powyższą tabelę:
1.
Równanie opisujące wynikowe jedynki (wyłącznie linie A i B):
\(\displaystyle{ Y = p*q + \neg p*\neg q}\)
2.
Równanie opisujące wynikowe zera (wyłącznie linie C i D):
\(\displaystyle{ \neg Y=\neg p*q + p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y}\) # \(\displaystyle{ \neg Y}\)

gdzie:
# - różne w znaczeniu:
Jeśli \(\displaystyle{ Y=0}\) to \(\displaystyle{ \neg Y=1}\)
Odwrotnie też zachodzi:
Jeśli \(\displaystyle{ \neg Y=1}\) to \(\displaystyle{ Y=0}\)
Stąd mamy prawa Prosiaczka:
\(\displaystyle{ Y=0 \Leftrightarrow \neg Y=1}\)
\(\displaystyle{ Y=1 \Leftrightarrow \neg Y=0}\)
mówiące o związku logiki dodatniej (bo \(\displaystyle{ Y}\)) z logiką ujemną (bo \(\displaystyle{ \neg Y}\))

Matematycznie zachodzi też:
\(\displaystyle{ Y = \neg (\neg Y)}\) - związek logiki dodatniej i ujemnej

Podstawiając 1 i 2 mamy prawo De Morgana dla logiki dodatniej (bo \(\displaystyle{ Y}\)):
3.
\(\displaystyle{ Y = p*q + \neg p*\neg q = \neg (\neg p*q + p*\neg q) = (p+\neg q)*(\neg p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y=Y}\)

Podstawiając 1 i 3 mamy związek KPN i DPN:
\(\displaystyle{ Y = p*q + \neg p*\neg q = (p+\neg q)*(\neg p+q)}\)

Prawo De Morgana w logice ujemnej (bo \(\displaystyle{ \neg Y}\)):
\(\displaystyle{ \neg Y = \neg (Y)}\) - matematyczny związek logiki ujemnej (bo \(\displaystyle{ \neg Y}\)) i dodatniej (bo \(\displaystyle{ Y}\))
Podstawiając 1 i 2 mamy:
4.
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = \neg (p*q + \neg p*\neg q) = (\neg p+\neg q)*(p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ \neg Y = \neg Y}\)

Podstawiając 2 i 4 mamy związek KPN i DPN:
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = (\neg p+\neg q)*(p+q)}\)

Czy wszyscy rozumieją skąd biorą się postaci KPN i DPN?


Logika zero

Tworzenie równań logicznych w logice zero.
W logice zero wszystkie zmienne sprowadzamy do zera korzystając z prawa Prosiaczka:
Jeśli \(\displaystyle{ p=1}\) to \(\displaystyle{ \neg p=0}\)

Weźmy nasz przykład.
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y\\
A: 1 & 1 & 1\\
B: 0 & 0 & 1\\
C: 0 & 1 & 0\\
D: 1 & 0 & 0\\
\end{tabular}}\)
Algorytm:
Jeśli na danej pozycji występuje zero to przepisujemy nagłówek tabeli
Jeśli na danej pozycji występuje jedynka to przepisujemy zanegowany nagłówek tabeli
W poziomie korzystamy ze spójnika „lub”(+) natomiast w pionie ze spójnika „i”(*)

Na mocy tego algorytmu równania opisujące poszczególne linie tabeli to:
\(\displaystyle{ \begin{tabular}{rclll}
p & q & Y & \neg Y\\
A: 1 & 1 & 1 & 0 & / \neg Y= \neg p+ \neg q \\
B: 0 & 0 & 1 & 0 & / \neg Y= p + q \\
C: 0 & 1 & 0 & 1 & / Y= p + \neg q\\
D: 1 & 0 & 0 & 1 & / Y= \neg p + q\\
\end{tabular}}\)

Stąd uzyskujemy dwa równania algebry Boole’a opisujące powyższą tabelę.

Równanie logiczne opisujące wyłącznie linie A i B:
1Z:
\(\displaystyle{ \neg Y=(\neg p+\neg q)*(p+q)}\)

Równanie logiczne opisujące wyłącznie linie C i D:
2Z:
\(\displaystyle{ Y=(p+\neg q)*(\neg p+q)}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y}\) # \(\displaystyle{ \neg Y}\)
gdzie:
# - różne w znaczeniu:
Jeśli \(\displaystyle{ Y=0}\) to \(\displaystyle{ \neg Y=1}\)
Odwrotnie też zachodzi:
Jeśli \(\displaystyle{ \neg Y=1}\) to \(\displaystyle{ Y=0}\)
Stąd mamy prawa Prosiaczka:
\(\displaystyle{ Y=0 \Leftrightarrow \neg Y=1}\)
\(\displaystyle{ Y=1 \Leftrightarrow \neg Y=0}\)
mówiące o związku logiki dodatniej (bo \(\displaystyle{ Y}\)) z logiką ujemną (bo \(\displaystyle{ \neg Y}\))

Matematycznie zachodzi też:
\(\displaystyle{ Y = \neg (\neg Y)}\) - związek logiki dodatniej i ujemnej

Podstawiając 2Z i 1Z mamy prawo De Morgana dla logiki dodatniej (bo Y):
3Z.
\(\displaystyle{ Y = (p+\neg q)*(\neg p+q) = \neg [(\neg p+\neg q)*(p+q)] = p*q + \neg p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ Y=Y}\)

Podstawiając 3Z i 2Z mamy związek KPN i DPN:
\(\displaystyle{ Y = p*q + \neg p*\neg q = (p+\neg q)*(\neg p+q)}\)

Prawo De Morgana w logice ujemnej (bo \(\displaystyle{ \neg Y}\)):
\(\displaystyle{ \neg Y = \neg (Y)}\) - matematyczny związek logiki ujemnej (bo \(\displaystyle{ \neg Y}\)) i dodatniej (bo \(\displaystyle{ Y}\))

Podstawiając 1Z i 2Z mamy:
4Z.
\(\displaystyle{ \neg Y = (\neg p+\neg q)*(p+q) = \neg [(p+\neg q)*(\neg p+q)] = \neg p*q + p*\neg q}\)

Oczywiście matematycznie zachodzi:
\(\displaystyle{ \neg Y = \neg Y}\)

Podstawiając 4Z i 1Z mamy związek KPN i DPN:
\(\displaystyle{ \neg Y = \neg p*q + p*\neg q = (\neg p+\neg q)*(p+q)}\)

Czy wszyscy rozumieją skąd biorą się postaci KPN i DPN?

Podsumowanie:
Logika człowieka i logika zero to logiki totalnie odwrotne, ale równoważne. Jedna z nich jest zbędna.
Oczywiście w kosmos wykopujemy logikę zero, odwrotną do naturalnej logiki człowieka.

Jak wam się podoba?

Nie podoba się, ani w tym żadnej nowości, ani żadnej wiedzy. Twa potęga polega tylko na tym, że rozpisujesz i opisujesz po 10 razy to samo. Przy okazji - nie wiem co za idiota nazwał te trywialne własności "Prawami Prosiaczka". Wszystko co tu nam prezentujesz to trywialne zasady logiki matematycznej, które można zapisać o wiele krócej niż te Twoje wypociny.