Matematyka.pl

Udowodnić, że negacji nie można zdefiniować za pomocą:
a) alternatywy i koniunkcji;
b) alternatywy i implikacji;
c) koniunkcji i implikacji;

Jak to zrobić? Może mi ktoś pomóc? Weźmy na początek przykład a).

Dodano po 4 godzinach 19 minutach 8 sekundach:
Podbijam pytanie.

Udowodnij, że każda formuła zbudowana za pomocą koniunkcji, alternatywy i jednej zmiennej \(\displaystyle{ p}\) jest równoważna z \(\displaystyle{ p}\).

JK

No właśnie coś mi się tak wydawało, że to trzeba robić w ten sposób, ale nie byłem pewny. Dobra to spróbuję to teraz jakoś zapisać:
Oczywiście \(\displaystyle{ p \vee p \Leftrightarrow p }\), bo jeśli \(\displaystyle{ p}\) jest prawdziwe to alternatywa dwóch zdań prawdziwych jest prawdziwa i to jest równoważne \(\displaystyle{ p}\). Jeśli natomiast \(\displaystyle{ p}\) jest fałszywe to alternatywa dwóch zdań fałszywych jest fałszywa i to jest równoważne znowu \(\displaystyle{ p}\).
Analogicznie \(\displaystyle{ p \wedge p \Leftrightarrow p}\), bo koniunkcja dwóch zdań prawdziwych jest prawdziwa i koniunkcja dwóch zdań fałszywych jest fałszywa, a zatem za każdym razem jest to równoważne \(\displaystyle{ p}\).
I teraz zauważmy, że dowolna ilość i kolejność alternatyw i koniunkcji jednej zmiennej \(\displaystyle{ p}\) jest równoważna \(\displaystyle{ p}\) bo zawsze dowolnie skomplikowana taka formuła będzie się składała z cząstkowych zdań, które są alternatywą lub koniunkcją jednej \(\displaystyle{ p}\) i zawsze taka formuła krok po kroku uprości się do \(\displaystyle{ p}\).

Czy tak jest dobrze? Trochę się rozpisałem, może można to jakoś krócej zapisać.

To jest poprawne rozumowanie, ale to nie jest dowód formalny, tylko "gawędziarski". Jak chcesz mieć dowód formalny, to musisz najpierw skonstruować zbiór wszystkich formuł, korzystających z alternatywy, koniunkcji i jednej zmiennej zdaniowej (rekurencyjnie), a potem indukcyjnie (indukcją po złożoności formuły) dowieść tego, co powyżej.

Ale to tylko wtedy, gdy dowód formalny jest potrzebny.

JK

Oto taki dowód:

Wykażemy, że każda formuła zbudowana ze: spójników koniunkcji \(\displaystyle{ \wedge}\) i alternatywy \(\displaystyle{ \vee}\) oraz zmiennej \(\displaystyle{ p}\) jest równoważna formule \(\displaystyle{ 'p'.}\)

Niech \(\displaystyle{ \alpha}\) będzie dowolną taką formułą.
Dowód przeprowadzimy indukcyjnie, ze względu na rozmiar formuły, czyli ze względu na ilość występujących w niej spójników.

Baza indukcji:
Jeśli formuła \(\displaystyle{ \alpha}\) ma rozmiar równy zero, to musi być postaci \(\displaystyle{ 'p'}\), a wtedy oczywiście:
\(\displaystyle{ p \Leftrightarrow p.}\)

Krok indukcyjny:
Niech \(\displaystyle{ n}\) będzie liczbą naturalną dodatnią, i przypuśćmy, że wszystkie rozważane formuły, które mają rozmiar silnie mniejszy od \(\displaystyle{ n,}\) mają żądaną własność. Pokażemy, że wszystkie rozważane formuły, które mają rozmiar równy dokładnie \(\displaystyle{ n,}\) mają żądaną własność.

Niech \(\displaystyle{ \alpha}\) będzie dowolną taką formułą o rozmiarze \(\displaystyle{ n}\). Ponieważ \(\displaystyle{ n>0}\), to \(\displaystyle{ \alpha}\) jest postaci \(\displaystyle{ \alpha _1\circ \alpha _{2}}\), gdzie \(\displaystyle{ \circ = \vee}\) lub \(\displaystyle{ \circ = \wedge}\) (którąś operację wykonujemy jako ostatnią). Przyglądając się takim znaczkom możemy zrozumieć, ponieważ formuła \(\displaystyle{ \alpha}\) ma rozmiar równy dokładnie \(\displaystyle{ n}\), więc formuły \(\displaystyle{ \alpha _1}\) i \(\displaystyle{ \alpha _2}\) mają rozmiar silnie mniejszy od \(\displaystyle{ n}\). Możemy zatem zastosować do nich założenie indukcyjne, i otrzymać, że: \(\displaystyle{ \alpha _1 \Leftrightarrow p}\) i \(\displaystyle{ \alpha _2 \Leftrightarrow p.}\)

Jeśli \(\displaystyle{ \circ = \wedge}\) , to \(\displaystyle{ \alpha = \alpha _1 \wedge \alpha _2 \Leftrightarrow p \wedge p \Leftrightarrow p.}\)
Jeśli \(\displaystyle{ \circ= \vee}\) , to \(\displaystyle{ \alpha = \alpha _1 \vee \alpha _2 \Leftrightarrow p \vee p \Leftrightarrow p.}\)

A więc formuła \(\displaystyle{ \alpha}\) ma żądaną własność.
Wobec dowolności wyboru takiej formuły \(\displaystyle{ \alpha}\) krok indukcyjny został dowiedziony.

Zasada indukcji porządkowej kończy dowód tego faktu.\(\displaystyle{ \square}\)

Możesz też przećwiczyć takie poniższe zadanie, odpowiadające na pytanie:

Czy przy pomocy jedynie spójnika koniunkcji \(\displaystyle{ \wedge }\) i skończonej ilości zmiennych, czy można zdefiniować dowolny spójnik??

Wskazówka: Nie można.
W tym celu uzasadnij indukcyjnie, że każda formuła zbudowana ze spójnika koniunkcji oraz zmiennych, przy wartościowaniu wszystkich zmiennych na \(\displaystyle{ 1}\) zawsze przyjmuję wartość \(\displaystyle{ 1}\) (pozostawiam to Tobie jako ćwiczenie).
Wynika stąd, że nie można w ten sposób zdefiniować dwuargumentowego spójnika fałszu \(\displaystyle{ F}\), bo jakkolwiek on by nie był zdefiniowany, to możemy rozważyć wartościowanie wszystkich zmiennych na \(\displaystyle{ 1}\), i wtedy, zgodnie z powyższym, przyjmie on wtedy wartość \(\displaystyle{ 1}\), a on przyjmuje zawsze wartość fałszu \(\displaystyle{ 0}\)- sprzeczność. Wobec czego nie można, przy pomocy koniunkcji, zdefiniować spójnika fałszu \(\displaystyle{ F.\square}\)


Jeszcze jedno ćwiczenie:

Wykaż, że przy pomocy jedynie spójnika implikacji oraz zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) można zdefiniować dokładnie sześć funkcji binarnych.

Podpowiedź:

W tym celu wykaż, że formuła zbudowana jedynie ze spójnika implikacji \(\displaystyle{ \Rightarrow}\) i zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\), jeśli ostatnią zmienną jest \(\displaystyle{ x}\), to każde wartościowanie, które wartościuje zmienną \(\displaystyle{ x}\) na \(\displaystyle{ 1,}\) wartościuje również całą formułę na \(\displaystyle{ 1}\) (wykaż to indukcyjnie).

Następnie wykaż analogiczny fakt dla drugiej zmiennej \(\displaystyle{ y}\).

Wiemy zatem, że jeśli formuła zbudowana ze zmiennych \(\displaystyle{ x}\) i \(\displaystyle{ y}\) oraz spójnika implikacji \(\displaystyle{ \Rightarrow }\), kończy się zmienną wartościowaną na \(\displaystyle{ 1}\), to cala formuła jest wartościowana na \(\displaystyle{ 1}\). Oznacza to, że w tabeli funkcji binarnej ostatni wiersz jest stale równy \(\displaystyle{ 1}\) lub ostatnia kolumna jest stale równa \(\displaystyle{ 1}\).

Takich tabel jest dokładnie \(\displaystyle{ 6}\), gdyż jeśli ostatni wiersz jest stale równy \(\displaystyle{ 1}\) :

\(\displaystyle{ \begin{array}{|c|c|c|}
\hline & 0 & 1 \\ \hline
0 & & \\ \hline
1 & 1 & 1 \\ \hline
\end{array}}\)

to mamy cztery możliwości;

w przeciwnym przypadku mamy, że ostatnia kolumna jest stale równa \(\displaystyle{ 1}\) i w dolnym wierszu mamy \(\displaystyle{ 0}\):

\(\displaystyle{ \begin{array}{|c|c|c|}
\hline & 0 & 1 \\ \hline
0 & & 1 \\ \hline
1 & 0 & 1 \\ \hline
\end{array}}\)

kolejne dwie możliwości.

Łącznie mamy sześć możliwości.

Wobec czego przy pomocy implikacji nie da się zdefiniować więcej niż \(\displaystyle{ 6}\) funkcji binarnych, a sześć funkcji binarnych uda Ci się wskazać (wskaż je, jest to proste). Wobec czego wskazane sześć funkcji binarnych są funkcjami które można zdefiniować przy pomocy samej implikacji.\(\displaystyle{ \square}\)

Podkreślmy jeszcze fenomen tego dowodu:

Po krótkich rozważaniach uda Ci się wskazać \(\displaystyle{ 6}\) funkcji binarnych, a okazało się jednak, że nie da się zdefiniować więcej niż \(\displaystyle{ 6}\) takich funkcji. Oznacza to, że wtedy trafisz doskonale te \(\displaystyle{ 6}\) funkcji binarnych, co trzeba. Co za strzał.

Jakub Gurak pisze: ↑5 sie 2023, o 15:52 Niech \(\displaystyle{ \alpha}\) będzie dowolną taką formułą o rozmiarze \(\displaystyle{ n}\). Ponieważ \(\displaystyle{ n>0}\), to \(\displaystyle{ \alpha}\) jest postaci \(\displaystyle{ \alpha _1\circ \alpha _{2}}\), gdzie \(\displaystyle{ \circ = \vee}\) lub \(\displaystyle{ \circ = \wedge}\) (którąś operację wykonujemy jako ostatnią).

Intuicyjnie to jest OK, ale formalnie niezbyt. I z tego powodu Twój dowód jest w zasadzie bardzo podobny do dowodu maxa.

JK

max123321 pisze: ↑4 sie 2023, o 22:38 Udowodnić, że negacji nie można zdefiniować za pomocą:
a) alternatywy i koniunkcji;
b) alternatywy i implikacji;
c) koniunkcji i implikacji;

Jak to zrobić? Może mi ktoś pomóc?

W technice bramek logicznych prawdą jest że dysponując bramką alternatywy czy też koniunkcji, nie da się zdefiniować negacji.
\(\displaystyle{ Y=p+q}\) - bramka alternatywy (+)
\(\displaystyle{ Y=p*q}\) - bramka koniunkcji (*)

Nie jest natomiast prawdą, że dysponując bramką implikacji o definicji:
\(\displaystyle{ Y = \neg p+q}\)
nie da się zdefiniować negacji.

Wystarczy na wejście \(\displaystyle{ q}\) podać logiczne zero.
Wtedy dla \(\displaystyle{ q=0}\) mamy:
\(\displaystyle{ Y = \neg p+q = \neg p +0 = \neg p}\)
\(\displaystyle{ Y = \neg p}\)
Na wyjściu \(\displaystyle{ Y}\) bramki logicznej pojawi się tu zawsze zanegowany sygnał \(\displaystyle{ p}\).
Dokładnie taka jest definicja negacji - dokładnie taką znajdziemy w każdym katalogu układów cyfrowych np. SN7406 Strona 2
c.n.d

Ja tutaj udowodniłem nieformalnie, że każda formuła zbudowana z alternatywy, koniunkcji i jednej zmiennej \(\displaystyle{ p}\) jest równoważna z \(\displaystyle{ p}\). No ok, ale co jeśli tych zmiennych będzie więcej na przykład cztery?

Gdyby zbudowana z alternatywy i koniunkcji formuła \(\displaystyle{ \alpha(p, q, r, t)}\) była równoważna \(\displaystyle{ \neg p}\), to te same własności miałaby też formuła \(\displaystyle{ \alpha(p, p, p, p)}\), co zostało już wykluczone.

max123321 pisze: ↑7 wrz 2023, o 23:51 Ja tutaj udowodniłem nieformalnie, że każda formuła zbudowana z alternatywy, koniunkcji i jednej zmiennej \(\displaystyle{ p}\) jest równoważna z \(\displaystyle{ p}\). No ok, ale co jeśli tych zmiennych będzie więcej na przykład cztery?

Jestem ze świata techniki więc wytłumaczę jak to jest w funkcjach logicznych (w bramkach logicznych).
Weźmy taką funkcję logiczną \(\displaystyle{ Y}\) czterech zmiennych binarnych.
\(\displaystyle{ Y = p+q+r+s}\)
Tu oczywiście nie ma szans na zdefiniowanie negacji bo wszystkie zmienne binarne są w logice dodatniej (bo \(\displaystyle{ x}\))
Wystarczy jednak, że jedna zmienna binarna będzie w logice ujemnej (bo \(\displaystyle{ \neg x}\)) i już przy pomocy takiej alternatywy da się zdefiniować negację.

Dowód:
\(\displaystyle{ Y = p+q+r+\neg s}\)
Na wejścia bramki \(\displaystyle{ p, q, r}\) podajemy logiczne zero:
\(\displaystyle{ p=q=r=0}\)
i już mamy zdefiniowaną negację:
\(\displaystyle{ Y = p+q+r+ \neg s = 0+0+0 + \neg s = \neg s}\)
Czyli:
\(\displaystyle{ Y= \neg s}\)
To jest krystalicznie czysta definicja negacji znana każdemu inżynierowi elektronikowi, którą można spotkać w absolutnie każdym katalogu bramek logicznych o czym było w tym moim poście:
logika-f100/udowodnic-ze-negacji-nie-mo ... l#p5657777

Dodano po 3 dniach 23 godzinach 16 minutach 52 sekundach:
Analogicznie będziemy mieli w koniunkcji.
Weźmy taką funkcję logiczną Y (bramkę logiczną) czterech zmiennych:
\(\displaystyle{ Y=p*q*r*s}\)
Wszystkie zmienne wejściowe \(\displaystyle{ p,q,r,s}\) są tu w logice dodatniej (bo \(\displaystyle{ x}\))
Nie mamy zatem żadnych szans na zdefiniowanie negacji \(\displaystyle{ Y= \neg x}\)
Wystarczy jednak, aby dowolna zmienna wejściowa \(\displaystyle{ p,q,r,s}\) była w logice ujemnej (bo \(\displaystyle{ \neg x}\)) i już bez problemu zdefiniujemy negację.
Dowód:
\(\displaystyle{ Y=p*q*s* \neg s}\)
Na wejściach \(\displaystyle{ p,q,r}\) funkcji logicznej Y (bramki logicznej) ustawiamy logiczne jedynki:
\(\displaystyle{ p=q=r=1}\)
Wtedy mamy:
\(\displaystyle{ Y=p*q*r* \neg s = 1*1*1* \neg s = \neg s}\)
Czyli:
\(\displaystyle{ Y= \neg s}\)
Dokładnie taka jest definicja negacji - dokładnie taką znajdziemy w każdym katalogu układów cyfrowych np. SN7406 Strona 2
c.n.d

Dodano po 32 minutach 35 sekundach:
Zauważmy, że jeśli w dowolnie długiej funkcji logicznej \(\displaystyle{ Y}\) wszystkie zmienne wejściowe będą w logice dodatniej (bo \(\displaystyle{ x}\)) to nie mamy szans na zdefiniowanie negacji \(\displaystyle{ Y= \neg x}\)
\(\displaystyle{ Y=p*q + r*s}\)
Wystarczy jednak, że dowolna zmienna będzie w logice ujemnej (bo \(\displaystyle{ \neg x}\)) i już bez problemu zdefiniujemy negację.
Dowód:
\(\displaystyle{ Y=p* \neg q + r* \neg s}\)
Tu na wejściach funkcji logicznej \(\displaystyle{ Y}\) (bramki logicznej) ustawiamy:
\(\displaystyle{ p=0}\)
\(\displaystyle{ r=1}\)
Wtedy mamy:
\(\displaystyle{ Y=p* \neg q + r* \neg s = 0* \neg q + 1* \neg s = 0+ \neg s =\neg s}\)
Czyli:
\(\displaystyle{ Y= \neg s}\)
Doskonale widać jak trywialny jest algorytm zdefiniowania negacji \(\displaystyle{ Y= \neg s}\) dla dowolnej funkcji logicznej \(\displaystyle{ Y}\), gdzie występuje co najmniej jedna zmienna binarna w logice ujemnej (bo \(\displaystyle{ \neg x}\))

Sugeruję, byś przestał zasypywać ten wątek wypowiedziami w temacie, o którym, jak się zdaje, masz niewielkie pojęcie. Zadanie polega na matematycznym udowodnieniu, że żadna formuła rachunku zdań zdefiniowana przy użyciu różnych spójników logicznych nie może być równoważna negacji. Twoje uwagi są banalne i nijak nie pomagają udowodnić tego, co trzeba. Ponadto są nie na temat - bramki logiczne w elektronice stanowią tylko jedno z wielu zastosowań logiki matematycznej i nie mają zbyt wiele wspólnego z tym, co w tym wątku najistotniejsze, tj. z dowodami matematycznymi. Operujesz też niezbyt przystępnym językiem - nie ma w matematyce takiego pojęcia, jak "logika dodatnia/ujemna", jest to żargon elektroników. Toteż chyba lepiej będzie, jeśli skoncentrujesz swoją uwagę na świecie techniki, z którego przybywasz, a matematykę zostawisz tym, którzy się na niej znają, tj. matematykom.

Dasio11 pisze: ↑13 wrz 2023, o 11:53 Twoje uwagi są banalne ...

Jako elektronik nie znam innej logiki matematycznej poza logiką bramek logicznych, w szczególności o KRZ dowiedziałem się dopiero 26 lat po ukończeniu elektroniki na Politechnice Warszawskiej - wcześniej nigdy o czymś takim jak KRZ nie słyszałem (nie było o tym nawet w jednym słowie na studiach!), słowo daję.
Cieszy mnie, że dla każdego matematyka moje uwagi są banalne.
Dziękuję.

Znalazłem tutaj inny krótszy dowód, ale go za bardzo nie rozumiem. W tym dowodzie rozważamy najkrótszą definicję postaci \(\displaystyle{ \alpha \vee \beta \Leftrightarrow \neg p}\) albo \(\displaystyle{ \alpha \wedge \beta \Leftrightarrow \neg p}\). Jeśli \(\displaystyle{ p}\) jest prawdziwe to \(\displaystyle{ \neg p}\) jest fałszywe, a zatem oba zdania \(\displaystyle{ \alpha,\beta}\) są fałszywe. Jeśli \(\displaystyle{ p}\) jest fałszywe to \(\displaystyle{ \alpha}\) lub \(\displaystyle{ \beta}\) jest prawdziwe. Jeśli \(\displaystyle{ \alpha}\) to \(\displaystyle{ \alpha \equiv \neg p}\) i wtedy jest to krótsza definicja negacji, tak samo, gdy \(\displaystyle{ \beta}\) jest prawdziwe.

Może mi ktoś wyjaśnić co tu się dzieje? Nie rozumiem za bardzo co my tu mamy dowieść. W ogóle jakoś dziwi mnie, to, że za pomocą dwóch zmiennych \(\displaystyle{ \alpha,\beta}\) próbujemy coś pokazać dla jednej zmiennej \(\displaystyle{ p}\).

To dowód, który zamiast indukcji korzysta z zasady analogicznej do zasady minimum w liczbach naturalnych. Przypuszcza się nie wprost, że istnieje formuła równoważna \(\displaystyle{ \neg p}\) zbudowana tylko z alternatywy i koniunkcji, i rozważa się najkrótszą formułę \(\displaystyle{ \varphi}\) o tej własności. Oczywiście \(\displaystyle{ \varphi}\) nie może być zmienną, zatem jest postaci \(\displaystyle{ \alpha \vee \beta}\) lub \(\displaystyle{ \alpha \wedge \beta}\) dla pewnych formuł \(\displaystyle{ \alpha, \beta}\). Z prostej analizy wynika, że wtedy \(\displaystyle{ \alpha}\) lub \(\displaystyle{ \beta}\) sama musi być równoważna \(\displaystyle{ \neg p}\), co przeczy założeniu, że \(\displaystyle{ \varphi}\) jest minimalnej długości.