Logika, zadanie nr 884
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
anka2720 post贸w: 46 |  2013-01-17 16:50:50Witam 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