Udowodnij, że są tylko dwa spójniki logiczne, dwuargumentowe takie, że za pomocą Lukasz: Hej, mam do zrobienia dosyć trudne dla mnie zadanie, nawet bardzo. Udowodnij, że są tylko dwa spójniki logiczne, dwuargumentowe takie, że za pomocą każdego z nich można wyrazić każdy inny spójnik dwuargumentowy. Wiem że tymi dwoma spójnikami to NAND i NOR i mam to udowodnione dla każdego spójnika 2 argumentowego. Ale kompletnie nie wiem jak mam udowodnić że np koniunkcja nie może zbudować innego wyrażenia? Łatwiej udowodnić że coś się da niż nie da Z góry dzięki za pomoc.

ite: zajrzyj do tego tekstu http://logic.amu.edu.pl/images/e/e8/Kon04.pdf

Lukasz: @ite dzięki za odpowiedź. Prześledziłem tego pdf'a i trochę rozumiem trochę nie, więc może masz czas mi to wytłumaczyć. Rozumiem, że h przyjmuje jako "parametry" wyraz p i q. Jak to jest że jak h przyjmie 0,0 = prawda to mozna zrobić negację a 1,1 = prawda nie da się?

ite: Wieczorem będę mieć chwilę czasu to odpiszę.

Lukasz: Jasne, będę czekał.

Tomek: Gdzie studiujesz Łukasz?

ite: h jest funktorem dwuargumentowym za pomocą którego (jako jedynego) mamy zdefiniować wszystkie pozostałe funktory (i te jedno− i dwuargumentowe), a więc również negację. Jak działa negacja? Zmienia wartość na przeciwną. I tak działa binegacja (NOR) i dysjunkcja (NAND) p | ∼p | p↓p | p/p −−−−−−−−−−−−−−−−−−−−−− 1 | 0 | 0 | 0 0 | 1 | 1 | 1 Tak samo ma działać funktor, którego szukamy. I dlatego konieczna jest zmiana wartości na przeciwną h (0,0) = 1 i h (1,1) = 0, tak jak w tabeli powyżej.

Lukasz: Hm.. okej już rozumiem. Teraz trochę mi się rozjaśniło. Mam jeszcze jedno ostatnie zadanie z tego typu: Udowodnij, że za pomocą równoważności i negacji nie można wyrazić koniunkcji. to już taką tabelą się nie da chyba? to jest chyba jeszcze gorsze zadanie od poprzedniego.

Lukasz: Co do tego co napisałeś, to nie wziąłem wczesniej pod uwagę funktorów jednoargumentowych i ciężko mi było zrozumieć zdanie że za pomocą negacji nie można wyrazić verum ani falsum (właściwie według mnie powinno być napisane chyba że nie można wyrazić żadnych funktorów)

ite: Za pomocą negacji można wyrazić asercję (i negację oczywiście). Dwóch pozostałych funktorów jednoargumentowych ( jednoargumentowego verum i jednoarg.falsum) nie da się za jej pomocą zdefiniować.

ite: To, że za pomocą równoważności i negacji nie można wyrazić koniunkcji, pewnie ma związek z tym, że równoważność jest funktorem typu 2:2 (prawda : fałsz), a koniunkcja to 1:3, ale pomysłu na dowód nie mam.