Wizje Kubusia

[rafal3006]

a)
Udowodnij, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji.

b)
Udowodnij, że za pomocą równoważności i negacji nie można zdefiniować alternatywy i koniunkcji.

To może pokażę jak to jest w technicznej algebrze Boole’a - przecież to też jest matematyka, zgadza się?
Stosuję notację z technicznej algebry Boole’a:
\(\displaystyle{ +}\) - alternatywa (bramka OR)
\(\displaystyle{ *}\) - koniunkcja (bramka AND)

Definicja bramki logicznej implikacji prostej:
\(\displaystyle{ Y = p \Rightarrow q = \neg p+q}\)
gdzie:
\(\displaystyle{ Y = p \Rightarrow q}\) - wyjście bramki logicznej

Mamy:
\(\displaystyle{ Y = \neg p + q}\)
Wymuszając:
\(\displaystyle{ q=0}\)
mamy definicję negacji (negator):
\(\displaystyle{ Y = \neg p}\)
Negując \(\displaystyle{ p}\) mamy definicję bramki OR:
\(\displaystyle{ Y = p+q}\)
Dysponując bramką OR i negatorem możemy zbudować dowolny operator.

Wniosek:
Bramka implikacji prostej jest wystarczająca na to, by zbudować dowolny operator logiczny.

Teraz zadania:
a/
Bramka OR:
\(\displaystyle{ Y=p+q}\)
Bramka AND:
\(\displaystyle{ Y=p*q}\)

Nie da się z tych bramek w żaden sposób uzyskać negatora, zatem z OR i AND nie zbudujemy żadnego operatora z wyjątkiem OR i AND.
cnd

b/
Równoważność \(\displaystyle{ +}\) negator
Nie da się zbudować ani bramki AND, ani OR dysponując bramka równoważności i negatorem.
\(\displaystyle{ Y= p \Leftrightarrow q = p*q + \neg p* \neg q}\)
stąd:
\(\displaystyle{ Y= p*q + \neg p* \neg q}\)
gdzie:
\(\displaystyle{ Y}\) - wyjście bramki logicznej równoważności

Jeśli zanegujemy \(\displaystyle{ p}\) to mamy:
\(\displaystyle{ Y= \neg p*q + p* \neg q}\)
Jeśli wymusimy:
\(\displaystyle{ p=1}\) to mamy
\(\displaystyle{ Y = 0*q + 1* \neg q = \neg q}\)
Nie da się w żaden sposób uzyskać z operatora równoważności ani bramki OR, ani AND, zatem nie da się zbudować z tego zestawu żadnego operatora z wyjątkiem równoważności
cnd

[norwimaj]

To może pokażę jak to jest w technicznej algebrze Boole’a - przecież to też jest matematyka, zgadza się?

Oczywiście algebry Boole'a (w szczególności algebry Lindenbauma-Tarskiego) są częścią matematyki, chociaż nie jestem pewien czy to samo pod tym pojęciem rozumiemy.

Dysponując bramką OR i negatorem możemy zbudować dowolny operator.

To prawda.

Wniosek:
Bramka implikacji prostej jest wystarczająca na to, by zbudować dowolny operator logiczny.

A to bzdura. Jest niewystarczająca z podobnych powodów, jak przedstawione przeze mnie jako rozwiązanie punktu a). Bierzesz wartościowanie przypisujące wszystkim zmiennym prawdę.

Nie możesz wymusić, żeby jakaś zmienna zdaniowa była fałszywa. (na tym się opiera Twój dowód)

zatem z OR i AND nie zbudujemy żadnego operatora z wyjątkiem OR i AND.

W pewnym sensie jest to prawda. Ale na pewno nie w takim, że ze zmiennych \(\displaystyle{ p}\) i \(\displaystyle{ q}\) oraz spójników \(\displaystyle{ \land}\) i \(\displaystyle{ \lor}\) możemy zbudować tylko \(\displaystyle{ p\land q}\) i \(\displaystyle{ p\lor q}\). Możemy zbudować też \(\displaystyle{ p\lor (p\land q)}\).

Nawet jest to jakiś sposób na rozwiązanie zadania, ale musiałbyś go dopracować.

Nie da się w żaden sposób uzyskać z operatora równoważności ani bramki OR, ani AND,

To stwierdzenie, podobnie poprzednie, nieudowodnione.

[rafal3006]

Wniosek:
Bramka implikacji prostej jest wystarczająca na to, by zbudować dowolny operator logiczny.

A to bzdura. Jest niewystarczająca z podobnych powodów, jak przedstawione przeze mnie jako rozwiązanie punktu a). Bierzesz wartościowanie przypisujące wszystkim zmiennym prawdę.

Nie możesz wymusić, żeby jakaś zmienna zdaniowa była fałszywa. (na tym się opiera Twój dowód)

Widzę, że zupełnie nie rozumiesz technicznej algebry Boole’a. W świecie techniki bez problemu mogę wymusić, aby dowolna zmienna była równa \(\displaystyle{ 1}\) albo \(\displaystyle{ 0}\).
\(\displaystyle{ Y= \neg p+q}\)
W świecie rzeczywistym podłączasz wejście \(\displaystyle{ q}\) powyższego układu do \(\displaystyle{ 0}\) i masz negator. W świecie rzeczywistym dysponując wyłącznie bramką implikacji prostej o definicji jak wyżej bez najmniejszego problemu zbudujesz wszystkie pozostałe operatory, a zatem i dowolny komputer - zapraszam do laboratorium techniki cyfrowej. Nie możesz obalić jakimś tam dowodem „matematycznym” iż nie da się zbudować z operatora implikacji każdego innego operatora, skoro bez problemu da się w świecie rzeczywistym. Jako ciekawostkę mogę dodać iż inżynierowie nie mają najmniejszego pojęcia co to jest prawda/fałsz, zdanie prawdziwe/fałszywe w algebrze Boole’a … a mimo to te komputery im doskonale działają.

zatem z OR i AND nie zbudujemy żadnego operatora z wyjątkiem OR i AND.

W pewnym sensie jest to prawda. Ale na pewno nie w takim, że ze zmiennych \(\displaystyle{ p}\) i \(\displaystyle{ q}\) oraz spójników \(\displaystyle{ \land}\) i \(\displaystyle{ \lor}\) możemy zbudować tylko \(\displaystyle{ p\land q}\) i \(\displaystyle{ p\lor q}\). Możemy zbudować też \(\displaystyle{ p\lor (p\land q)}\).

Nawet jest to jakiś sposób na rozwiązanie zadania, ale musiałbyś go dopracować.

Dowolny operator można zbudować na nieskończenie wiele sposobów, z jedną, jedyną, postacią minimalną.
Prawo algebry Boole’a:
\(\displaystyle{ p=p+(p*q)}\)
Dowód:
\(\displaystyle{ Y=p+(p*q)}\)
Przejście do logiki ujemnej \(\displaystyle{ ( \neg Y)}\) poprzez negacje zmiennych i wymianę operatorów:
\(\displaystyle{ \neg Y = \neg p*( \neg p+ \neg q)}\)
\(\displaystyle{ \neg Y = \neg p* \neg p+ \neg p* \neg q = \neg p + \neg p* \neg q = \neg p*(1+ \neg q) = \neg p*1 = \neg p}\)
Powrót do logiki dodatniej:
\(\displaystyle{ Y=p}\)
cnd
Jak widzisz, nie uzyskałeś swoim równaniem definicji ŻADNEGO operatora logicznego poza \(\displaystyle{ Y=p}\)
Co więcej!
\(\displaystyle{ p=p+(p*x)}\)
Za \(\displaystyle{ x}\) możesz sobie podstawić dowolnie długą funkcję logiczną z dowolną ilością zmiennych, co nie oznacza że zbudowałeś jakikolwiek inny operator logiczny poza poniższym:
\(\displaystyle{ Y=p}\)
W technice to się nazywa operator transmisji.

Nie da się w żaden sposób uzyskać z operatora równoważności ani bramki OR, ani AND,

To stwierdzenie, podobnie poprzednie, nieudowodnione.

W świecie techniki to jest dziecinnie prosty dowód, zrozumiały dla każdego inżyniera.

[norwimaj]

Widzę, że zupełnie nie rozumiesz technicznej algebry Boole’a.

:rotfl:

W świecie techniki bez problemu mogę wymusić, aby dowolna zmienna była równa \(\displaystyle{ 1}\) albo \(\displaystyle{ 0}\).

To prawda, ale nie tego dotyczyło zadanie. Jeśli już chcesz to rozwiązywać w oparciu o algebry L-T, to musi to być algebra \(\displaystyle{ B(\emptyset)}\), a nie \(\displaystyle{ B(\{\neg q\})}\), bo inaczej używasz nie tylko implikacji, ale też negacji.

Widzę że zupełnie nie rozumiesz rachunku zdań. Klocki, z których się buduje formuły rachunku zdań, to zmienne zdaniowe i spójniki. Nie ma żadnego "podłączania jakiejś zmiennej do zera".

zapraszam do laboratorium techniki cyfrowej.

Poproszę o imienne zaproszenie, wysłane listem poleconym na mój adres, wraz z podaniem stawianych mi zarzutów.

Jako ciekawostkę mogę dodać iż inżynierowie nie mają najmniejszego pojęcia co to jest prawda/fałsz, zdanie prawdziwe/fałszywe w algebrze Boole’a … a mimo to te komputery im doskonale działają.

Możliwe że tacy inżynierowie istnieją, ale nie są to ci sami, którzy tworzą komputery i ich oprogramowanie.

Prawo algebry Boole’a:
\(\displaystyle{ p=p+(p*q)}\)
Dowód:
\(\displaystyle{ Y=p+(p*q)}\)
Przejście do logiki ujemnej \(\displaystyle{ ( \neg Y)}\) poprzez negacje zmiennych i wymianę operatorów:
\(\displaystyle{ \neg Y = \neg p*( \neg p+ \neg q)}\)
\(\displaystyle{ \neg Y = \neg p* \neg p+ \neg p* \neg q = \neg p + \neg p* \neg q = \neg p*(1+ \neg q) = \neg p*1 = \neg p}\)
Powrót do logiki dodatniej:
\(\displaystyle{ Y=p}\)
cnd

Ja doskonale wiem, że \(\displaystyle{ p=p+(p*q)}\) w algebrze Boole'a i ten bełkotliwy dowód nie jest mi potrzebny. W każdym razie \(\displaystyle{ p}\) jest czymś innym niż \(\displaystyle{ p+q}\) i czymś innym niż \(\displaystyle{ p*q}\), czyli dobrze napisałem. Za to Ty napisałeś stwierdzenie, które nie wiadomo jak należy rozumieć:

zatem z OR i AND nie zbudujemy żadnego operatora z wyjątkiem OR i AND.

Jeśli nie będziesz pisał jasno i w miarę ściśle, o co Ci chodzi, to nikogo na tym forum nie przekonasz. Bełkot i machanie rękami nie są mile widziane w matematyce.

To stwierdzenie, podobnie poprzednie, nieudowodnione.

W świecie techniki to jest dziecinnie prosty dowód, zrozumiały dla każdego inżyniera.

W przypadku tak prostego zadania można chyba cały dowód przytoczyć? Moim zdaniem nie wystarczy napisać, że dowód jest dziecinnie prosty i masz ten dowód gdzieś. Taka informacja jest bezużyteczna dla osoby chcącej zobaczyć rozwiązanie zadania. Chociaż link do dowodu wypada podać.

[rafal3006]

W świecie techniki bez problemu mogę wymusić, aby dowolna zmienna była równa \(\displaystyle{ 1}\) albo \(\displaystyle{ 0}\).

To prawda, ale nie tego dotyczyło zadanie. Jeśli już chcesz to rozwiązywać w oparciu o algebry L-T, to musi to być algebra \(\displaystyle{ B(\emptyset)}\), a nie \(\displaystyle{ B(\{\neg q\})}\), bo inaczej używasz nie tylko implikacji, ale też negacji.

Widzę że zupełnie nie rozumiesz rachunku zdań. Klocki, z których się buduje formuły rachunku zdań, to zmienne zdaniowe i spójniki. Nie ma żadnego "podłączania jakiejś zmiennej do zera".

Weźmy zadanie podobne:
Udowodnij że dysponując wyłącznie operatorem NOR albo NAND można zbudować dowolny operator logiczny.

Dowód:
Definicja operatora NAND:
\(\displaystyle{ Y= \neg (p*q) = \neg p+ \neg q}\)
Definicja operatora NOR:
\(\displaystyle{ Y= \neg (p+q) = \neg p* \neg q}\)
Fundamentem dowodu jest dowód, iż z tych definicji da się wyprowadzić definicję operatora negacji.

Zajmijmy się NAND (w NOR będzie analogicznie)
Definicja operatora NAND:
\(\displaystyle{ Y= \neg (p*q) = \neg p+ \neg q}\)

Jak wyprowadzić operator negacji?

Można to zrobić na wiele sposobów:
1.
\(\displaystyle{ Y= \neg (p*q)}\)
Zwieramy wejścia \(\displaystyle{ p}\) i \(\displaystyle{ q}\) i mamy operator negacji:
\(\displaystyle{ Y = \neg r}\)
2.
Wymuszamy \(\displaystyle{ q=1}\) i mamy operator negacji:
\(\displaystyle{ Y= \neg (p*q) = \neg (p*1) = \neg p}\)
3.
\(\displaystyle{ Y= \neg p+ \neg q}\)
Ustawiamy:
\(\displaystyle{ \neg q=0}\)
i mamy operator negacji:
\(\displaystyle{ Y= \neg p + 0 = \neg p}\)

Mając operator negacji plus definicję NAND (NOR) mamy wyżej wszystko, możemy zbudować dowolny operator logiczny.
Oczywiście nie może być tak że którykolwiek z dowodów w bramkach logicznych wyżej (to jest świat rzeczywisty!) obalisz jakimś tam rachunkiem zdań.

Twój zarzut że nie wolno mi tutaj używać operatora negacji jest chybiony, bo ten operator uzyskaliśmy z samej bramki NAND, której oczywiście wolno nam użyć w dowolnych ilościach.

Czy zgadzasz się z powyższym?

P.S.

W przypadku tak prostego zadania można chyba cały dowód przytoczyć?

Pełny dowód dla zadania A oczywiście mam, ale najpierw chcę się dowiedzieć czy rozumiesz i akceptujesz to co wyżej.

-- 17 lutego 2013, 14:30 --

Kod: Zaznacz cały

http://www.sfinia.fora.pl/metodologia,12/algebra-kubusia-logika-czlowieka,6474.html#185474

Temat:
Rzeczywista budowa operatorów OR i AND
… jest fundamentalnie inna niż to się Ziemianom wydaje.

W przypadku tak prostego zadania można chyba cały dowód przytoczyć? Moim zdaniem nie wystarczy napisać, że dowód jest dziecinnie prosty i masz ten dowód gdzieś. Taka informacja jest bezużyteczna dla osoby chcącej zobaczyć rozwiązanie zadania. Chociaż link do dowodu wypada podać.

ok.

a)
Udowodnij, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji.

Wstęp teoretyczny:

We „Wstępie do matematyki”

Kod: Zaznacz cały

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

znajduje się dowód iż matematycy znają algorytm przejścia z dowolnej tabeli zero-jedynkowej do równoważnych równań logicznych opisujących tą tabelę.

Fundamentem algorytmu [url=http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html]prof. Newelskiego z UWr (uwaga 2.7)[/url] są definicje spójników „i”(*) oraz „lub”(+) z naturalnego języka mówionego.

Definicje rodem z technicznej algebry Boole’a spójników „i”(*) i „lub”(+) są następujące.

Definicja spójnika „i” (*) - koniunkcji:
Iloczyn logiczny (spójnik „i”(*) ) n-zmiennych binarnych jest równy 1 wtedy i tylko wtedy gdy wszystkie zmienne są równe 1
\(\displaystyle{ Y = (A1*A2*...An)=1 \Leftrightarrow A1=1 i A2=1 i ... An=1}\)

Definicja spójnika „lub”(+) - alternatywy:
Suma logiczna (spójnik „lub”(+) ) n-zmiennych binarnych jest równa 1 wtedy i tylko wtedy gdy którakolwiek zmienna jest równa 1
\(\displaystyle{ Y = (A1+A2+...An)=1 \Leftrightarrow A1=1 lub A2=1 lub ... An=1}\)

W swoim algorytmie prof. Newelski musiał skorzystać i korzysta z najważniejszych praw algebry Boole’a:
\(\displaystyle{ p=0 \Leftrightarrow \neg p=1}\)
\(\displaystyle{ p=1 \Leftrightarrow \neg p=0}\)

Dlaczego te prawa są najważniejsze?
Bo człowiek w swojej naturalnej logice operuje wyłącznie równaniami algebry Boole’a, nigdy tabelami zero-jedynkowymi. Bez tych praw niemożliwy jest matematyczny opis naturalnej logiki człowieka, bo niemożliwe jest przejście z tabeli zero-jedynkowej do równań logicznych ja opisujących i z powrotem.

Wszelkie prawa logiczne opisane są równaniami algebry Boole’a, nigdy tabelami zero-jedynkowymi.
Wyłącznie w logice symbolicznej (równania algebry Boole’a) mamy dostęp do wszystkich praw logicznych i możemy z nich swobodnie korzystać np. prawo przejścia do logiki ujemnej i z powrotem.

Dlaczego nie ma tych praw w żadnym podręczniku matematyki i Wikipedii?
… oto jest pytanie.

Algorytm prof. Newelskiego poznamy na przykładzie operatora OR.

Zero-jedynkowa definicja operatora OR:
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y=p+q \\
A: 1 & 1 & 1 \\
B: 1 & 0 & 1 \\
C: 0 & 1 & 1 \\
D: 0 & 0 & 0 \\
1 & 2 & 3
\end{tabular}}\)
W algebrze Boole’a dla dowolnej tabeli zero-jedynkowej możemy ułożyć dwa podstawowe i nie tożsame równania algebry Boole’a, jedno opisujące wynikowe jedynki i drugie, opisujące wynikowe zera. Kompletny algorytm to zaledwie trzy kroki.

Równania algebry Boole’a opisujące wynikowe jedynki:
1.
Spis z natury:
\(\displaystyle{ A: Y=1 \Leftrightarrow p=1 i q=1}\)
lub
\(\displaystyle{ B: Y=1 \Leftrightarrow p=1 i q=0}\)
lub
\(\displaystyle{ C: Y=1 \Leftrightarrow p=0 i q=0}\)

2.
Korzystając z prawa algebry Boole’a:
\(\displaystyle{ p=0 \Leftrightarrow \neg p=1}\)
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)

Sprowadzamy wszystkie zmienne do jedynek:
\(\displaystyle{ A: Y=1 \Leftrightarrow p=1 i q=1}\)
lub
\(\displaystyle{ B: Y=1 \Leftrightarrow p=1 i \neg q=1}\)
lub
\(\displaystyle{ C: Y=1 \Leftrightarrow \neg p=1 i \neg q=1}\)

3.
Stąd na podstawie definicji spójnika „i”(*) w poziomach i spójnika „lub”(+) w pionie mamy końcowe równanie algebry Boole’a opisujące powyższą tabelę zero-jedynkową:
\(\displaystyle{ Y = p*q + p* \neg q + \neg p* \neg q}\)

Oczywiście równanie to opisuje wyłącznie obszar ABC123 powyżej tabeli.
Dokładnie ten sam obszar ABC123 opisuje nagłówek tabeli:
\(\displaystyle{ Y=p+q}\)
na mocy definicji spójnika „lub”(+).

Stąd mamy tożsamość matematyczną:
\(\displaystyle{ Y = p+q}\)
\(\displaystyle{ Y = p*q + p* \neg q + \neg p* \neg q}\)
\(\displaystyle{ Y=Y}\)

stąd równoważna definicja spójnika „lub”(+):
ABC123:
\(\displaystyle{ Y = p+q = p*q + p* \neg q + \neg p* \neg q}\)
Powyższe równanie opisuje obszar ABC123.

Jeśli je zanegujemy dwustronnie korzystając z prawa przejścia do logiki przeciwnej:
Negujemy zmienne i wymieniamy spójniki na przeciwne
to otrzymamy równanie algebry Boole’a opisujące linię D123!

Algorytm Wuja Zbója:
1.
Uzupełniamy nawiasy i brakujące spójniki:
\(\displaystyle{ Y = p+q = (p*q) + (p* \neg q) + ( \neg p* \neg q)}\)

2.
Negujemy zmienne i wymieniamy spójniki na przeciwne
\(\displaystyle{ \neg Y = \neg p* \neg q = ( \neg p+ \neg q)*( \neg p+q)*(p+q)}\)
oczywiście równania ABC123 i D123 nie są tożsame.

W technice układów cyfrowych oznacza to że jeśli zbudujemy układy 1 i 2 w bramkach logicznych i połączymy wyjścia \(\displaystyle{ Y}\) i \(\displaystyle{ \neg Y}\) to zobaczymy kupę dymu i smrodu, wszystko wyleci w powietrze.

Równania algebry Boole’a opisujące wynikowe zera:

Zero-jedynkowa definicja operatora OR:
\(\displaystyle{ \begin{tabular}{rcl}
p & q & Y=p+q \\
A: 1 & 1 & 1 \\
B: 1 & 0 & 1 \\
C: 0 & 1 & 1 \\
D: 0 & 0 & 0 \\
1 & 2 & 3
\end{tabular}}\)
Postępujemy identycznie jak wyżej algorytmem prof. Newelskiego

1.
Spis z natury dla wynikowych zer (tu mamy tylko jedno w linii D123):
\(\displaystyle{ Y=0 \Leftrightarrow p=0 i q=0}\)

2.
Korzystając z prawa algebry Boole’a:
\(\displaystyle{ p=0 \Leftrightarrow \neg p=1}\)
Jeśli \(\displaystyle{ p=0}\) to \(\displaystyle{ \neg p=1}\)

Sprowadzamy wszystkie zmienne do jedynek:
\(\displaystyle{ \neg Y=1 \Leftrightarrow \neg p=1 i \neg q=1}\)

3.
Na mocy definicji spójnika „i”(*) mamy równanie końcowe opisujące linię D123:
\(\displaystyle{ \neg Y= \neg p* \neg q}\)
co matematycznie oznacza:
\(\displaystyle{ \neg Y=1 \Leftrightarrow \neg p=1 i \neg q=1}\)

Oczywiście, negując linię D123 musimy otrzymać definicje spójnika „lub”(+) w równaniu algebry Boole’a opisującą wyłącznie obszar ABC123.

Równanie opisujące linię D123:
\(\displaystyle{ \neg Y= \neg p* \neg q}\)
co matematycznie oznacza:
\(\displaystyle{ \neg Y=1 \Leftrightarrow \neg p=1 i \neg q=1}\)

Przejście do logiki przeciwnej \(\displaystyle{ (Y)}\) poprzez negację zmiennych i wymianę spójników na przeciwne.
Równanie opisujące obszar ABC123:
\(\displaystyle{ Y=p+q}\)
co matematycznie oznacza:
\(\displaystyle{ Y=1 \Leftrightarrow p=1 lub q=1}\)

Nanieśmy nasze równania na definicję operatora OR:
\(\displaystyle{ \begin{tabular}{rcll}
p & q & Y=p+q \\
A: 1 & 1 & 1 & /Y=p*q \\
B: 1 & 0 & 1 & /Y=p* \neg q \\
C: 0 & 1 & 1 & /Y= \neg p * q\\
D: 0 & 0 & 0 & / \neg Y= \neg p * \neg q\\
1 & 2 & 3
\end{tabular}}\)
Użyteczną technikę tworzenia równania logicznego dla dowolnej linii w spójniku „i”(*) widać jak na dłoni.
Jeśli na wybranej pozycji mamy 1 to przepisujemy nagłówek kolumny.
Jeśli na wybranej pozycji mamy 0 to przepisujemy zanegowany nagłówek kolumny

Wniosek:
Kompletną tabelę zero-jedynkową operatora OR (wszystkie cztery linie) opisuje układ rówań logicznych:
\(\displaystyle{ A: Y=p+q}\)
\(\displaystyle{ B: \neg Y= \neg p* \neg q}\)

Związek logiki dodatniej \(\displaystyle{ (Y)}\) i ujemnej \(\displaystyle{ ( \neg Y)}\):
\(\displaystyle{ Y= \neg ( \neg Y)}\)

Podstawiając A i B mamy prawo De Morgana:
\(\displaystyle{ Y = p+q = \neg ( \neg p* \neg q)}\)

Dopiero to równanie opisuje kompletny operator OR, wszystkie cztery linie!
\(\displaystyle{ Y = p+q = \neg ( \neg p* \neg q)}\)

Dowód:
Twierdzenie:
Jeśli w operatorze OR zanegujemy wszystkie zmienne to na podstawie prawa De Morgana musimy otrzymać definicję operatora AND.

Definicja operatora OR:
1.
\(\displaystyle{ Y = p+q = \neg ( \neg p* \neg q)}\)

Dowód:
2.
Negujemy zmienne wejściowe p i q:
\(\displaystyle{ y = \neg p + \neg q = \neg (p*q)}\)

3.
Negujemy wyjście y:
\(\displaystyle{ \neg y = \neg ( \neg p+ \neg q) = p*q}\)

Równanie 3 to oczywiście pełna definicja operatora AND w równaniu algebry Boole’a.
Zauważmy że operator AND (3) jest logiką ujemną \(\displaystyle{ ( \neg y)}\) w stosunku do operatora OR (1).

Zauważmy że równanie:
\(\displaystyle{ Y=p+q}\)
nie jest kompletnym opisem operatora OR (opisującym wszystkie cztery linie) bo negujemy zmienne i nie otrzymujemy definicji operatora AND.
\(\displaystyle{ \neg Y= \neg p+ \neg q}\)

Sensacyjny wniosek!

W równaniu logicznym:
\(\displaystyle{ Y=p+q}\)
Znaczek \(\displaystyle{ „+”}\) nie jest operatorem logicznym opisującym wszystkie cztery linie tabeli zero-jedynkowej!
Znaczek \(\displaystyle{ „+”}\) to tylko połówka operatora OR (obszar ABC123) a nie cały operator (ABCD123) jak to jest we współczesnej matematyce.

Oczywiście matematycznie zachodzi:
Operator OR ## Operator AND
gdzie:
## - różne na mocy definicji

… bo w przejściu z operatora OR do operatora AND wyłącznie negowaliśmy zmienne bez zmiany spójników!

Czy ktoś czegoś nie rozumie?
Czy ktoś zamierza obalić genialny algorytm przejścia z dowolnej tabeli zero-jedynkowej do równoważnych równań algebry Boole’a autorstwa [url=http://www.math.uni.wroc.pl/~newelski/dydaktyka/wdm-A/skrypt3/skrypt/node3.html]prof. Newelskiego z UWr (uwaga 2.7)[/url]


Wracając do naszego zadania

a)
Udowodnij, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji.

Pełna definicja operatora implikacji prostej:
\(\displaystyle{ p=>q = \neg p+q = \neg (p* \neg q)}\)

Doskonale widać, że bez operatora negacji i operatora OR (AND) fizyczna realizacja operatora implikacji nie jest możliwa.

Definicja negatora (operatora negacji):
\(\displaystyle{ Y= \neg p}\)

Pełna definicja operatora OR (alternatywy):
\(\displaystyle{ Y = p+q = \neg ( \neg p* \neg q)}\)

Pełna definicja operatora AND (koniunkcji):
\(\displaystyle{ Y = p*q = \neg ( \neg p+ \neg q)}\)

Zajmijmy się operatorem OR (dla AND będzie symetrycznie):
\(\displaystyle{ Y = p+q = \neg ( \neg p* \neg q)}\)
Z równania:
\(\displaystyle{ Y=p+q}\)
Nie da się utworzyć operatora negacji koniecznego do realizacji operatora implikacji.
Dowód:
Podstawmy:
\(\displaystyle{ q=0}\)
Mamy:
\(\displaystyle{ Y=p+q = p+0 = p}\)
W technice to jest definicja operatora transmisji \(\displaystyle{ (Y=p)}\) a nie negacji \(\displaystyle{ (Y= \neg p)}\).

Zajmijmy się tożsamym równaniem:
\(\displaystyle{ Y = \neg ( \neg p* \neg q)}\)
Podstawiamy:
\(\displaystyle{ \neg q=1}\)
stąd:
\(\displaystyle{ Y = \neg ( \neg p*1) = \neg ( \neg p) = p}\)
To również jest operator transmisji.

Rozpatrzyliśmy wyżej KOMPLETNĄ tabelę zero-jedynkową operatora OR, nie uzyskując kluczowego dla naszego zadania operatora negacji \(\displaystyle{ (Y= \neg p)}\)

Stąd:
Nie da się zrealizować operatora Implikacji z użyciem wyłącznie alternatywy (koniunkcji oczywiście też)
cnd

[rafal3006]

W świecie techniki bez problemu mogę wymusić, aby dowolna zmienna była równa \(\displaystyle{ 1}\) albo \(\displaystyle{ 0}\).

To prawda, ale nie tego dotyczyło zadanie. Jeśli już chcesz to rozwiązywać w oparciu o algebry L-T, to musi to być algebra \(\displaystyle{ B(\emptyset)}\), a nie \(\displaystyle{ B(\{\neg q\})}\), bo inaczej używasz nie tylko implikacji, ale też negacji.

Moim skromnym zdaniem cos jest zdecydowanie nie tak z matematyką ścisłą.

Nie może być tak że w technicznej algebrze Boole’a istnieją cztery operatory logiczne przy pomocy których można zbudować dowolny inny operator:
1
Definicja operatora NAND
\(\displaystyle{ Y= \neg (p*q)}\)
2.
Definicja operatora NOR
\(\displaystyle{ Y= \neg (p+q)}\)
3.
implikacja prosta
\(\displaystyle{ p \Rightarrow q = \neg p+ q}\)
4.
implikacja odwrotna
\(\displaystyle{ p \rightarrow q = p+ \neg q}\)

Natomiast na gruncie jakiejś innej matematyki istnieją wyłącznie dwa takie operatory:
NAND
NOR


Twierdzenie 1 (Techniczna algebra Boole'a):
Dysponując wyłącznie operatorami NAND, NOR ,implikacji prostej \(\displaystyle{ \Rightarrow}\), albo implikacji odwrotnej \(\displaystyle{ \rightarrow}\) można zrealizować dowolny operator logiczny. Nie da się tego zrobić dysponując wyłącznie operatorami AND, OR, \(\displaystyle{ \Leftrightarrow}\), \(\displaystyle{ XOR}\)

Twierdzenie 2 (norwimaj):
Dysponując wyłącznie operatorami NAND albo NOR można zrealizować dowolny operator logiczny. Nie da się tego zrobić dysponując wyłącznie operatorami AND, OR, \(\displaystyle{ \Leftrightarrow}\), \(\displaystyle{ XOR}\), implikacji prostej \(\displaystyle{ \Rightarrow}\), albo implikacji odwrotnej \(\displaystyle{ \rightarrow}\)

Mamy wiec dwie opcje:
A.
Według technicznej algebry Boole'a twierdzenie 1 jest prawdziwe, natomiast twierdzenie 2 jest fałszywe, co z dziecinną łatwością można udowodnić w laboratorium techniki cyfrowej.
B.
Według norwimaja twierdzenie 1 jest fałszywe, natomiast twierdzenie 2 jest prawdziwe.

Moim zdaniem jedna prawdziwa opcja to A.
Czy ktoś jest innego zdania?
Jeśli tak to proszę o uzasadnienie.

Szczegółowe dowody są w tym poście:
https://www.matematyka.pl/330499.htm#p5076286

[norwimaj]

Moim skromnym zdaniem cos jest zdecydowanie nie tak z matematyką ścisłą.

Nie może być tak że w technicznej algebrze Boole’a istnieją cztery operatory logiczne przy pomocy których można zbudować dowolny inny operator: (...)

Natomiast na gruncie jakiejś innej matematyki istnieją wyłącznie dwa takie operatory:
NAND
NOR

Rozwiązując dwa różne zadania możesz otrzymać dwie różne odpowiedzi, i nie ma w tym żadnej sprzeczności.

Inna jest sprawa, gdy dla danej formuły \(\displaystyle{ \varphi}\) chcemy znaleźć taką formułę \(\displaystyle{ \psi}\) zawierającą tylko określone spójniki, że \(\displaystyle{ \models \varphi\Leftrightarrow\psi}\), a inna, gdy dla danej formuły \(\displaystyle{ \varphi}\) i zmiennych \(\displaystyle{ p,q}\) niewystępujących w \(\displaystyle{ \varphi}\) chcemy znaleźć taką formułę \(\displaystyle{ \psi}\) zawierającą tylko określone spójniki, że \(\displaystyle{ p\land\neg q\models \varphi\Leftrightarrow\psi}\).

Najpierw powinieneś zrozumieć treść zadania, a dopiero potem rozwiązywać.

[rafal3006]

Treść zadania jest w pierwszym poście:

a)
Udowodnij, że za pomocą alternatywy i koniunkcji nie można zdefiniować implikacji.

Zauważ, że autor tematu próbuje rozwiązać problem w oparciu o rachunek zero-jedynkowy.

Techniczna algebra Boole’a to tabele zero-jedynkowe plus ZMIENNE binarne plus banalne zasady rachunku zero-jedynkowego.

Jeśli mam definicję implikacji prostej:
\(\displaystyle{ p \Rightarrow q = \neg p+q}\)
To bez problemu mogę sobie ustawić zmienne po prawej stronie na cokolwiek, 0 albo 1.
Mogę też próbkować po wszystkich możliwych wartościach zmiennych \(\displaystyle{ p}\) i \(\displaystyle{ q}\)

To jest matematyka
… gdzie 0 i 1 nie mają żadnej interpretacji.

Natomiast jeśli wtrącasz do tego interpretację typu:
1 - zdanie prawdziwe
0 - zdanie fałszywe

To lądujesz w świecie fizyki, czyli mamy do czynienia z zastosowaniem matematyki w świecie fizyki.

Podsumowując:
Na gruncie czystej matematyki, bez związku ze światem fizyki rozwiązanie musi być jednoznaczne, czyli wchodzi w grę wyłącznie opcja A z poprzedniego postu.

Takie jest moje zdanie.

[norwimaj]

Zauważ, że autor tematu próbuje rozwiązać problem w oparciu o rachunek zero-jedynkowy.

Autor rozwiązuje (a właściwie rozwiązywał) zadanie z klasycznego rachunku zdań. Zechciej zaznajomić się z podstawowymi pojęciami tego działu matematyki.

Mamy dany niepusty, zwykle nieskończony, zbiór \(\displaystyle{ Var}\), którego elementy nazywamy zmiennymi zdaniowymi. Zbiorem formuł jest najmniejszy taki zbiór \(\displaystyle{ \Form}\), który spełnia warunki:

• \(\displaystyle{ Var\subseteq Form,}\)
• jeśli \(\displaystyle{ \varphi\in Form,}\) to \(\displaystyle{ \neg\varphi\in Form,}\)
• jeśli \(\displaystyle{ \varphi,\psi\in Form,}\) to \(\displaystyle{ \varphi\land\psi,\varphi\lor\psi,\varphi\Leftrightarrow\psi,\varphi\Rightarrow\psi\in Form.}\)

Wartościowaniem (zmiennych zdaniowych) nazywamy dowolną funkcję \(\displaystyle{ \nu: Var\to\{0,1\}}\). Dla danego wartościowania \(\displaystyle{ \nu}\) definiujemy wartościowanie formuł \(\displaystyle{ \nu^{\ast}:Form\to\{0,1\}}\) wiadomo jak. Gwiazdki przy \(\displaystyle{ \nu}\) zwykle nie pisze się (lenistwo, czytelność).

Dwie formuły, \(\displaystyle{ \varphi}\) i \(\displaystyle{ \psi}\), nazywamy logicznie równoważnymi, jeśli dla każdego wartościowania \(\displaystyle{ \nu}\) mamy równość \(\displaystyle{ \nu(\varphi)=\nu(\psi)}\).


W punkcie a) zadania należy udowodnić, że nieprawdą jest, że dla każdej formuły \(\displaystyle{ \varphi}\) istnieje logicznie równoważna z nią formuła \(\displaystyle{ \psi}\), zawierająca jedynie spójniki \(\displaystyle{ \lor}\) i \(\displaystyle{ \land}\). Teraz masz już podane wszystkie niezbędne definicje i nie będzie usprawiedliwienia dla bredni, które od tej pory napiszesz.

Natomiast jeśli wtrącasz do tego interpretację typu:
1 - zdanie prawdziwe
0 - zdanie fałszywe

To lądujesz w świecie fizyki, czyli mamy do czynienia z zastosowaniem matematyki w świecie fizyki.

Akurat to, czy coś nazwiemy zerem, czy fałszem, to ma najmniejsze znaczenie.

[yorgin]

Postanawiam wtrącić swoje 3 grosze.

Twierdząc A, czyli że operatorem implikacji jesteś w stanie otrzymać dowolny dwuargumentowy operator, jesteś w błędzie.

Na gruncie czystej logiki/rachunku zdań musiałbyś pokazać w takim razie zdanie \(\displaystyle{ F_\Dleta=F(p,q,\Rightarrow)}\) dobrane dla dowolnego spójnika \(\displaystyle{ \Delta}\) takie, że

\(\displaystyle{ p\Delta q\iff F_\Delta}\)

czyli konstruktywnie wskazać \(\displaystyle{ F}\).

Mając na przykład NAND, negację dostajesz tak:

\(\displaystyle{ \neg p\iff p NAND p}\)

a koniunkcja to zaprzeczenie NAND czyli

\(\displaystyle{ p\wedge q \iff (p NAND q) NAND (p NAND q)}\)

Dalej wiadomo, że negacja i koniunkcja produkują wszystko.

Zrób to samo dla implikacji. Albo implikacji odwrotnej.

To jest dowód.



Jeśli zaczynasz wstawiać zera i jedynki, to dokonujesz wartościowania zdania. Dodatkowo, dlaczego w miejscu

\(\displaystyle{ p \Rightarrow q = \neg p+q}\)

pisząc o wstawianiu \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\) piszesz o podstawianiu tylko z jednej strony? Jaka jest w tym logika? Pisząc znak równości należy się spodziewać tautologii, podczas gdy

\(\displaystyle{ p\Rightarrow q = \neq p \vee 0}\)
jest zdaniem fałszywym dla wartościowania \(\displaystyle{ p=0}\) oraz \(\displaystyle{ q=0}\). Coś zaczyna się sypać, a chcieliśmy mieć definicję równoważną.

Nie rozumiem również, po co odwołujesz się do świata fizyki czy matematyki. Jaki w tym cel? Zdania prawdziwe czy zdania fałszywe to element logiki matematycznej, \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\) to tylko symbole opisujące wartość logiczną zdania. Mogę je podmieniać na \(\displaystyle{ P, F}\) albo \(\displaystyle{ \ksi, \eta}\) lub cokolwiek innego.

To lądujesz w świecie fizyki, czyli mamy do czynienia z zastosowaniem matematyki w świecie fizyki.

Jakiś konstruktywny przykład czy to tylko gdybanie?