Proste zadanko z teorii bramek logicznych

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
rafal3006
Użytkownik
Użytkownik
Posty: 158
Rejestracja: 11 mar 2007, o 19:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 1 raz

Proste zadanko z teorii bramek logicznych

Post autor: rafal3006 »

Proste zadanko z teorii bramek logicznych

logika-f100/dowod-na-niezupelnosc-zbior ... l#p5649570
Carino pisze: 12 lis 2022, o 11:50 Witam, jak rozwiązać tego typu zadanie?

"Rozważmy taki spójnik \(\displaystyle{ \oplus}\), że \(\displaystyle{ p \oplus q \equiv \neg p}\). Pokaż, że zbiór \(\displaystyle{ \{ \oplus \}}\) nie jest zupełny."

Dostałem radę, żeby zrobić to indukcją, nie wiem jednak do końca jak i proszę o pomoc.
Zainspirowany powyższym tematem zakładam nowy temat, bo nie mam pojęcia co to jest zbiór spójników zupełny/niezupełny etc.

Jestem przybyszem ze świata techniki.
Na podstawie dedukcji dalszych postów w powyższym temacie myślę, że podobne zadanie na gruncie teorii bramek logicznych może być takie.

Zbadaj, czy istnieje bramka logiczna \(\displaystyle{ ?}\) spełniająca poniższą tożsamość logiczną:
\(\displaystyle{ p?q = \neg q}\)
Oczywiście, jeśli po stronie wejścia bramki \(\displaystyle{ ?}\) postawimy wymóg, iż zmienne \(\displaystyle{ p}\) i \(\displaystyle{ q}\) muszą być zmiennymi binarnymi to nie ma bramki logicznej \(\displaystyle{ ?}\) która by spełniała:
\(\displaystyle{ p?q = \neg q}\)
ale!
Jeśli dopuścimy iż na wejście bramki \(\displaystyle{ p}\) albo \(\displaystyle{ q}\) możemy podawać stałe binarne o wartości logicznej \(\displaystyle{ 1}\) albo \(\displaystyle{ 0}\) to istnieją bramki spełniające poniższą tożsamość:
\(\displaystyle{ p?q = \neg q}\)

Dowód:
Jedziemy po definicjach wszystkich możliwych bramek dwuwejściowych w logice matematycznej.
Wprowadźmy znaczek:
#### - nie da się uzyskać powyższej tożsamości
1.
Bramka "i"(\(\displaystyle{ *}\)):
\(\displaystyle{ p*q}\) #### \(\displaystyle{ \neg q}\) - nie ma takiej możliwości
2.
Bramka "lub"(\(\displaystyle{ +}\)):
\(\displaystyle{ p+q}\) #### \(\displaystyle{ \neg q}\) - nie ma takiej możliwości
3.
Bramka równoważności \(\displaystyle{ p \Leftrightarrow q}\):
\(\displaystyle{ p \Leftrightarrow q}\) = \(\displaystyle{ p*q+ \neg p* \neg q}\)
Tu jeśli na wejściu p podamy logiczne zero to uzyskamy:
\(\displaystyle{ 0 \Leftrightarrow q = 0*q + \neg (0)* \neg q = 0+1* \neg q = 0+ \neg q = \neg q}\) - istnieje taka możliwość
4.
Bramka spójnika "albo"($):
\(\displaystyle{ p}\)$\(\displaystyle{ q}\) = \(\displaystyle{ p* \neg q + \neg p*q}\)
tu dla \(\displaystyle{ p=1}\) mamy:
\(\displaystyle{ 1}\)$\(\displaystyle{ q}\) = \(\displaystyle{ 1* \neg q + \neg (1)*q = \neg q+0*q = \neg q}\) - istnieje taka możliwość
5.
Bramka warunku wystarczającego =>:
\(\displaystyle{ p}\)=>\(\displaystyle{ q}\) = \(\displaystyle{ \neg p+q}\)
\(\displaystyle{ p}\)=>\(\displaystyle{ q}\) #### \(\displaystyle{ \neg q}\) - nie ma takiej możliwości
6.
Bramka warunku koniecznego ~>:
\(\displaystyle{ p}\)~>\(\displaystyle{ q}\) = \(\displaystyle{ p+ \neg q}\)
Dla \(\displaystyle{ p=0}\) mamy:
\(\displaystyle{ 0}\)~>\(\displaystyle{ q}\) = \(\displaystyle{ 0+ \neg q = \neg q}\) - istnieje taka możliwość
7.
Bramka chaosu \(\displaystyle{ p}\)|~~>\(\displaystyle{ q}\) (zdanie zawsze prawdziwe):
\(\displaystyle{ p}\)|~~>\(\displaystyle{ q}\) = \(\displaystyle{ p*q+p* \neg q + \neg p*q + \neg p* \neg q =1}\)
Nie ma możliwości uzyskania tożsamości logicznej:
\(\displaystyle{ p}\)|~~>\(\displaystyle{ q}\) #### \(\displaystyle{ \neg q}\) - nie ma takiej możliwości
8.
Bramka śmierci \(\displaystyle{ p}\)|~~~>\(\displaystyle{ q}\) (zdanie zawsze fałszywe):
\(\displaystyle{ p}\)|~~~>\(\displaystyle{ q}\) = \(\displaystyle{ \neg}\) (\(\displaystyle{ p}\)|~~>\(\displaystyle{ q}\)) \(\displaystyle{ =0}\)
Nie ma możliwości uzyskania tożsamości logicznej:
\(\displaystyle{ p}\)|~~~>\(\displaystyle{ q}\) #### \(\displaystyle{ \neg q}\) - nie ma takiej możliwości

Rozpatrzyliśmy wszystkie możliwe dwuwejściowe bramki logiczne (spójniki logiczne), co kończy dowód.
Zadanie postawione na gruncie bramek logicznych zostało rozwiązane.

P.S.
Oryginalne zadanie było takie:
\(\displaystyle{ p \oplus q \equiv \neg p}\)
Ja przeanalizowałem (przez literówkę):
\(\displaystyle{ p \oplus q \equiv \neg q}\)
co dla idei jest bez znaczenia
ODPOWIEDZ