Logika, zadanie nr 884

Autor	Zadanie / Rozwiązanie
anka2720 postów: 46	2013-01-17 16:50:50 Witam Wszystkich i zarazem bardzo proszę o pomoc. Mam takie zadanie: Pokazać, że wszystkie aksjomaty logiki Hilberta: (A1) $\alpha\rightarrow(\beta\rightarrow\alpha)$ (A2) $(\alpha\rightarrow(\beta\rightarrow\gamma))\rightarrow((\alpha\rightarrow\beta)\rightarrow(\alpha\rightarrow\gamma))$ (A3) $\neg\neg\alpha\rightarrow\alpha$ daje się wyprowadzić za pomocą reguł logiki Gentzena Wiadomość była modyfikowana 2013-01-18 20:06:06 przez anka2720

tumor postów: 8070	2013-01-18 21:08:22 Liczę, że masz reguły Gentzena gdzieś rozpisane, w razie czego jest internet. a1) chcemy dowieść $\vdash a\rightarrow (b \rightarrow a)$ Mamy po prawej implikację jako główny spójnik. Patrzymy na regułę, gdzie implikacja jest po prawej. Reguła mówi, że poprzednik implikacji przerzucamy na lewo. $a \vdash b \rightarrow a$ Drugi raz to samo $a,b\vdash a$ Co daje aksjomat (ewentualnie korzystamy z monotoniczności, zależy jak były reguły Gentzena wprowadzone) a2) $\vdash (a\rightarrow (b \rightarrow c))\rightarrow((a\rightarrow b)\rightarrow (a\rightarrow c))$ znów zaczynamy od reguły mówiącej od implikacji po prawej. $a\rightarrow (b \rightarrow c) \vdash (a\rightarrow b)\rightarrow (a\rightarrow c)$ $a\rightarrow (b \rightarrow c), a\rightarrow b \vdash a\rightarrow c$ $a\rightarrow (b \rightarrow c), a\rightarrow b, a \vdash c$ "a" mamy już w poprzedniku, możemy mieć dwa razy $a\rightarrow (b \rightarrow c),a , a\rightarrow b, a \vdash c$ Teraz będziemy rozkładać implikacje po lewej. To jest bardziej skomplikowane, bo nam się całość rozgałęzia. (Gdyby coś było niezrozumiałe, to napisz, jak Ci podano tę właśnie regułę) $a \vdash a$;$ \mbox{ } b \rightarrow c,a\rightarrow b, a \vdash c$ Lewa gałąź jest aksjomatem, więc będę się zajmował tylko prawą. Stosując znów regułę dla implikacji w poprzedniku dostajemy: $a \vdash a$; $b,b \rightarrow c\vdash c$ Raz jeszcze lewa gałąź jest aksjomatem, prawą rozkładamy dalej. $b \vdash b$ ; $c\vdash c$ Obie gałęzie są aksjomatami. a3) najprostszy, może spróbuj zrobić ---- Uwagi: a) spotkałem się z pewnym uproszczeniem reguł Gentzena. W szczególności wiki podaje wersję chyba daleką od oryginału, lepiej zajrzeć do angielskiej jeśli już. b) zasadniczo dowód przebiega w kierunku przeciwnym niż się "rozwiązuje". Ja szedłem od reguły udowadnianej do aksjomatów, natomiast dowód wychodzi od aksjomatów i buduje regułę. Dlatego często drzewo się pisze od dołu. c) żeby oddzielić gałęzie drzewa zastosowałem czerwony średnik, żeby się w oczy rzucił

anka2720 postów: 46	2013-01-18 21:21:58 Bardzo dziękuję:) A czy jeszcze mógłbyś napisać mi w jakiej wersji Ty masz zapisane te reguły? Bo ja w tych swoich nie mogę się połapać... Może dlatego nie potrafiłam tego zrobić. I czy mógłbyś pokazać mi jeden przykład z zastosowaniem negacji? Jestem naprawdę bardzo wdzięczna!:)

anka2720 postów: 46	2013-01-18 21:25:56 I czy da się pokazać prawdziwość aksjomatu: $\alpha\|-\alpha$

tumor postów: 8070	2013-01-18 21:52:37 Ja sobie otworzyłem jakąś stronę, żeby te reguły mieć przed oczami. http://www-users.mat.umk.pl/~fly/materialy/pl/referaty/gentzen/gentzen.pdf http://en.wikipedia.org/wiki/Sequent_calculus Aksjomat na tym polega, że jego prawdziwości się nie pokazuje. :) Reguła zazwyczaj jest zapisana w postaci ułamka. Na przykład $\frac{A \vdash B}{A \vdash B, C}$ Mianownik ułamka jest tym, co mamy, A, B, C są ciągami formuł. Reguła ta mówi, że jeśli mamy po prawej wiele formuł, to część WOLNO NAM ominąć. Zapomnieć w ogóle. :) Nie znaczy, że musimy rzecz robić. Łatwa jest reguła z implikacją po prawej (używaliśmy jej na początku). $\frac{A,a \vdash B,b}{A \vdash B, a\rightarrow b}$ Znów mamy mianownik, a robimy z niego liczni. W mianowniku występują jakieś dowolne ciągi formuł A,B których nie ruszamy, a także formuła $a\rightarrow b$ po prawej stronie. Reguła mówi, że w takim przypadku poprzednik tej implikacji przerzucamy na lewo, a następnik zostaje po prawej. Jeśli powiem regułę negacji, to już nie będziesz mieć co robić w a3) Są dwie reguły negacji, bo zależy, czy negacja występuje po lewej czy po prawej stronie. Reguły te to: $\frac{A,a \vdash B}{A \vdash B,\neg a}$ $\frac{A,\neg a \vdash B}{A \vdash B, a}$ Obie te reguły mówią, że po prostu to, co było po negacji, przerzucamy na drugą stronę już bez negacji. Na przykład gdybyśmy chcieli dowieść $\vdash (\neg a \rightarrow \neg b)\rightarrow (b\rightarrow a)$ to zaczęlibyśmy od rozbicia implikacji po prawej, potem jeszcze raz, aż otrzymalibyśmy $\neg a \rightarrow \neg b,b \vdash a$ Następnie rozdzielilibyśmy drzewo na dwie gałęzie, bo tego wymaga zajęcie się implikacją po lewej. $\neg b,b \vdash \mbox{ }$;$ \vdash a, \neg a$ i teraz przerzucamy w obu gałęziach to, co ma negację $b \vdash b$ ; $a \vdash a$ Otrzymując aksjomaty.

anka2720 postów: 46	2013-01-18 22:02:49 a co gdy mamy coś takiego: $(\forall_{x}(\alpha\Rightarrow\beta))\Rightarrow((\forall_{x}\alpha)\Rightarrow(\forall_{x}\beta))$ ?

anka2720 postów: 46	2013-01-18 22:15:26 W (A3) pierwszy krok będzie: $\neg\neg\alpha\|-\alpha$ ? I co dalej z podwójną negacją?

tumor postów: 8070	2013-01-18 22:32:47 Nie patrz na nią jak na podwójną negację. To $\neg (\neg a)$ A co się robi z negacją po lewej? Reguły masz spisane. :) W przypadku kwantyfikatorów dojdzie podstawianie. Popatrz na przykłady w necie, bo ja już idę spać ;)

anka2720 postów: 46	2013-01-18 22:40:46 To co po negacji przerzucamy na drugą stronę :) myślę, że już sobie poradzę. Naprawdę bardzo Ci dziękuję. Dzięki, że mi to wszystko rozpisałeś. Teraz zaczynam rozumieć skąd co się bierze. :)

anka2720 postów: 46	2013-01-19 11:03:18 Czy mógłbyś mi jeszcze pokazać jak udowodnić coś takiego: $\neg(\alpha\rightarrow\neg\beta)\rightarrow(\alpha\wedge\beta)$ ?

strony: 1 2 3

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj