http://ii.drx.pl/ 2026-05-23T20:50:40+02:00 http://ii.drx.pl/ http://ii.drx.pl/lib/images/favicon.ico text/html 2009-10-25T20:46:24+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:100?rev=1256499984&do=diff Dowodzenie implikacji wprost polega na założeniu poprzednika i wyprowadzeniu zeń następnika. Ponieważ strzałeczki są dwie, osiągamy w końcu: * W założeniu: * W celu: * Weźmy więc tego , dla którego z wynika i skorzystajmy z faktu, że dla każdego jest . * Wtedy w szczególności dla naszego jest , a że , to i . * Koniec. text/html 2009-10-22T01:03:14+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:109?rev=1256166194&do=diff Nie są. * Niech , a cokolwiek. * Wtedy jest tautologią. * A z kolei tautologią nie jest. Jest za to popularnym wśród kobiet błędem zwanym „uogólnianiem”:) text/html 2009-10-13T11:55:19+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:11?rev=1255427719&do=diff Rozwiązanie sprowadza się do skorzystania ze skróconej metody zero-jedynkowej w sposób opisany w skrypcie. Jeśli udowodnimy, że formuła jest tautologią, oznaczamy ją jako A. W przeciwnym razie możemy w analogiczny sposób spróbować udowodnić, że jest sprzeczna - usiłując znaleźć wartościowanie spełniające. Jeśli się to nie uda, oznaczamy ją jako C. Jeśli natomiast znajdziemy takie wartościowania, oznaczamy ją przez B i podajemy je. text/html 2009-10-22T01:03:46+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:110?rev=1256166226&do=diff Są. Aby pokazać równoważność, pokażmy implikacje w obie strony. * * Do założeń wkładamy i , chcemy pokazać, że . * Ponieważ w nie ma wolnych wystąpień , jeśli uda nam się udowodnić, że jest spełniona dla pewnego , będziemy mogli twierdzić, że jest spełniona dla dowolnego , czyli niezależnie od niego - „odczepiamy” ją od . * Weźmy więc taki , że (jego istnienie mamy zapewnione w jednym z założeń). * Dla każdego mamy , więc w szczególności jest tak dla naszego . * Ponieważ… text/html 2009-10-22T01:04:14+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:119?rev=1256166254&do=diff * * text/html 2009-10-23T16:33:43+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:120?rev=1256308423&do=diff * * text/html 2009-10-22T01:05:06+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:123?rev=1256166306&do=diff Można. Jak się chce, to wszystko można. text/html 2009-10-22T01:05:34+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:129?rev=1256166334&do=diff * Nie * Tak * Tak * Nie * Nie * Tak * Nie * Tak * Nie * Tak Dowodów mi się nie chce pisać. Ale Ty też możesz edytować tę stronę. text/html 2009-10-10T17:43:40+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:13?rev=1255189420&do=diff * Zdanie prawdziwe. Załóżmy nie wprost, że i są tautologiami, a nie jest. Oznacza to, że istnieje wartościowanie takie, że . Wtedy albo , a więc jedna z tych formuł nie jest tautologią, co jest sprzeczne z założeniem. * Zdanie nieprawdziwe. Niech , a . Wtedy jest spełniona dla fałszywego i niespełnione dla prawdziwego, a jest spełniona dla prawdziwego i niespełniona dla fałszywego, jednak jest formułą sprzeczną. * Zdanie prawdziwe. Załóżmy nie wprost, że nie jest spełnialna, a … text/html 2009-10-22T01:06:05+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:132?rev=1256166365&do=diff * Nie. * Niech , , . * Wtedy , a . * Tak. * Weźmy dowolne . * Wtedy . * Z przemienności koniunkcji mamy: . * Czyli . text/html 2009-10-22T15:57:14+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:140?rev=1256219834&do=diff Równoważność ciągu formuł udowodnimy poprzez udowodnienie wszystkich implikacji „w prawo”. * * Wykażmy zawieranie . * Weźmy dowolne . * Z definicji sumy zbiorów mamy: . * Rozważmy przypadek . Wtedy w sposób trywialny . * Wpp., . Ale ponieważ , z definicji zawierania zbioru mamy: . * Ponieważ wybraliśmy dowolne , udowodniliśmy zawieranie . * Zawieranie jest trywialne (a jeśli prowadzący się uprze, to powinieneś/powinnaś już sam(a) umieć to rozpisać) * Ponieważ prawdzi… text/html 2009-11-02T23:04:38+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:144?rev=1257199478&do=diff Łączność Weźmy dowolny . Pokazaliśmy, że jeśli , to . Czytając to od tyłu, pokażemy implikację odwrotną. Rysunek jest ZŁY! Z rysunku nic nie wynika! Przemienność Tożsamości * * * text/html 2009-11-02T21:56:03+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:151?rev=1257195363&do=diff Cpż, Jak się pokazuje inkluzje? No! Weźmy dow. . Wtedy, z definicji sumy rodziny zbiorów, mamy: . Z definicji przekroju zbiorów: Weźmy takie , że i . Skoro należy do , to należy też do , bo ta suma zawiera . Podobnie można pokazać, że należy do . Zatem należy do , co chcieliśmy pokazać. text/html 2009-11-02T01:52:13+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:179?rev=1257123133&do=diff Porządne zrobienie zadania 151. znacząco pomaga przy robieniu tego. Konkretniej, mamy tam udowodnioną inkluzję w prawo dla dowolnych rodzin i kontrprzykład przy inkluzji w lewo. Pozostaje nam więc pokazać, że dla rodzin wstępujących inkluzja w lewo również zachodzi. text/html 2009-11-07T11:00:15+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:181?rev=1257588015&do=diff Z góry uprzedzam, że późno już i nie chce mi się tak naprawdę pisać tego rozwiązania, więc może być „za prosto”. Zauważmy, że . Skoro tak, to , bo przecież jest rodziną zstępującą, czyli (można to sobie indukcyjnie udowodnić z definicji). text/html 2009-11-29T22:05:19+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:192?rev=1259528719&do=diff Zachodzi. . . , stąd teza. Ps. niech ktoś tu powstawia nowe linie, bo ja nie wiem jak :D Powstawialem --- drx 2009/11/29 22:04 text/html 2009-11-02T01:54:26+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:197?rev=1257123266&do=diff Tu takie zabytkowe rozwiązanie. Dzisiaj przykłady byłyby pewnie mniej trywialne, ale cóż... text/html 2009-11-07T11:04:54+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:201?rev=1257588294&do=diff Pokażmy, że jest zwrotna. Weźmy dowolne . Pokażemy, że . Ponieważ , to . Pokażmy, że jest symetryczna. Weźmy dowolne . Jeśli , to , więc należy do . W przeciwnym razie, . Ponieważ , to niezależnie od tego, czy należy do , czy , również należy do . text/html 2009-11-11T15:27:59+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:202?rev=1257949679&do=diff Tu nie ma nic trudnego. Właściwie, czytając samo rozwiązanie, można sobie tylko utrudnić, więc spróbuj sam(a), pamiętając definicje przekroju rodziny zbiorów i relacji przechodniej. * Weźmy dowolne . Wtedy , bo jest właśnie tak zdefiniowane (). No i z definicji przekroju rodziny zbiorów mamy . * Weźmy dowolne . Wtedy , czyli jest przechodnia (co nam wystarczy, bo jeśli jest przech. i zawiera , to jest w ). * Weźmy dowolne . Wiemy z poprzedniego podpunktu, że i należą do wszystkich … text/html 2009-11-13T23:58:14+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:203?rev=1258153094&do=diff Weźmy dowolne . Wtedy, z definicji sumy, istnieją takie , że . Wtedy . text/html 2009-12-03T22:46:05+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:204?rev=1259876765&do=diff Że jest przechodnia, to już wiemy z poprzedniego zadania. Pozostaje pokazać: * * Pokażmy, że jeśli jest relacją przechodnią zawierającą , to . * FIXME UWAGA! to rozwiązanie będzie brzydkie! (ale nie mogę na razie wymyślić ładniejszego) Pokażę tą drugą kropkę, do pierwszej nic dodać nic ująć. Niech będzie przechodnia. Pokażemy że , skąd, dzięki uwadze iwana, wyniknie nam teza zadania. Lecimy: dla pewnego . Ustalmy to n. . Skoro , to: text/html 2009-11-11T16:26:40+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:206?rev=1257953200&do=diff * Fałsz. Weźmy sobie i , . Wtedy przeciwdziedziną jest , a - . * Prawda. Weźmy dowolne . Wtedy istnieje takie , że . Znajdźmy więc takie , że . To proste: . * Prawda. Weźmy dowolne takie, że . Wtedy . Pokażmy, że . Załóżmy nie wprost, że . Wtedy , co przeczy założeniu, że g jest funkcją. * Fałsz. Niech i , . Wtedy jest ładną identycznością, ale . text/html 2009-11-30T22:45:33+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:211?rev=1259617533&do=diff Cudowne zadanie! Sam miód! Tą jedyną funkcją jest identyczność. Pokażemy, że jest monotoniczną bijekcją typu i że nie istnieje żadna inna taka funkcja. Identyczność to oczywiście funkcja taka, że dla każdego . * Izomorfizmu porządkowego pewnie jeszcze nie znacie, ale każdy wie, że jest monotoniczna, jeśli dla dowolnych mamy . No i mamy: . * Bijekcje zwykle są „na”. Weźmy dowolne . Wtedy dla mamy , więc identyczność jest „na”. * Są też różnowartościowe. . * No a teraz załóżmy nie w… text/html 2009-11-22T23:10:19+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:216?rev=1258927819&do=diff Proste wystarczy zanegować definicje. text/html 2009-11-23T22:27:24+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:219?rev=1259011644&do=diff Kontrprzykład dla 219: A={1,2,3} R = { <1,1>,<2,2>,<3,3>,<1,2>,<2,1> } S = { <1,1>,<2,2>,<3,3>,<2,3>,<3,2> } SR = { <1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<2,3>,<3,2>,<1,3> } W złożeniu jest para <1,3>, a nie ma <3,1> więc nie jest symetryczna. text/html 2009-12-02T00:03:01+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:220?rev=1259708581&do=diff Okay, w skrócie będzie: Zał że * zwrotność banalna * . zał, bsdo, to pierwsze. Więc dla jest: . * przechodniość: . W drugą stronę: zał że dwa przypadki: * ... sprzeczność. * Niech i załóżmy, że T jest równoważnością. Wtedy sprzeczność. text/html 2009-10-12T18:08:02+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:26?rev=1255363682&do=diff * , reszta obojętnie * , , * , , text/html 2009-10-14T17:06:09+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:34?rev=1255532769&do=diff zdefiniujemy ciąg rekurencyjnie: Tak, no to ja zwrócę uwagę, że w zasadzie: * * * * I dla na przykład otrzymujemy tautologię, a więc to nie jest dobry przykład. Co więcej, nie wskazano błędu w moim dowodzie. iwan Jeśli rozpatrujemy formuły o nieskończonej liczbie zmiennych, to może zadziałać: text/html 2009-10-10T20:51:19+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:38?rev=1255200679&do=diff Przypomnijmy, że spójnik implikacji łączy w prawo, czyli np. znaczy . Dowód indukcyjny względem . * Dla mamy: . Wybierzmy dowolne wartościowanie . Ponieważ , formuła jest prawdziwa, a ponieważ wybraliśmy dowolne wartościowanie, jest zarazem tautologią. * Dla mamy , o której zakładamy, że jest tautologią. Pokażmy, że również jest tautologią. Korzystając z przypomnianej łączności, zapisujemy: . Korzystając z punktu pierwszego stwierdzamy, że formuła w nawiasie jest tautologią, a korzys… text/html 2009-10-10T18:48:06+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:43?rev=1255193286&do=diff Nie są. Rozważmy przykład: , , . Mamy wtedy , ale . text/html 2009-10-20T19:18:09+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:44?rev=1256059089&do=diff Formuły są równoważne. Określmy wartościowania, dla których będą fałszywe. Pierwsza - dla prawdziwej i dla fałszywej. Rekurencyjnie powtarzając to rozumowanie, dochodzimy do wniosku, że formuły , , muszą być prawdziwe, a fałszywa. Przy każdym innym wartościowaniu formuła jest spełniona. Druga formuła również jest fałszywa dokładnie przy tym jednym wartościowaniu. Tak więc są sobie równoważne. == text/html 2009-10-10T23:32:17+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:52?rev=1255210337&do=diff Pierwsza formuła Dowód indukcyjny po n. * . . Formuła jest fałszywa dla wartościowania. * . . jest fałszywa dla . Implikacja jest fałszywa, gdy jest prawdziwe, a fałszywe. Różnych wartościowań jest , więc jest fałszywa dla text/html 2009-10-20T15:31:52+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:57?rev=1256045512&do=diff Zaznaczam, że nie jestem pewien poprawności tych rozwiązań. Ewentualne potwierdzenie lub poprawki mile widziane. * * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * * to-do * to-do * to-do * to-do * to-do * to-do * * to-do * to-do * to-do * to-do * to-do * to-do * to-do * * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * * to-do text/html 2009-10-21T00:57:22+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:59?rev=1256079442&do=diff Pytanie od czytelnika :P: nie może być po po prostu ? dla [definicja z whitebooka]? Wtedy nie ma r, a musi też być. xP Z wynikiem rozwiązania się oczywiście zgodzę, natomiast pytanie brzmi jak rozwiązywaliście to zadanie? Bo metoda prób i błędów nie będzie optymalna na 180sek. kartkówce ;p text/html 2009-10-20T23:48:19+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:64?rev=1256075299&do=diff * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * tu trzeba skorzystać z rozdizelności alternatywy względem koniunkcji :) * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do * to-do text/html 2009-10-21T01:15:05+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:67?rev=1256080505&do=diff Załóżmy, że istnieje formuła jej równoważna. W jednej z klauzul musiałaby zawierać literał lub , ponieważ inaczej dla wartościowań i przybierałaby tę samą wartość, podczas gdy nasza formuła przybiera dla pierwszego , a dla drugiego . Co więcej, dla prawdziwego pierdolę, dalej nie robię. Człowiek się stara, a w zamian tylko kłamstwa i oskarżenia. text/html 2009-10-19T12:48:07+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:68?rev=1255949287&do=diff Taką formułą jest ... Dowodzimy indukcyjnie, że zmienna p musi być użyta dokładnie n+1 razy. Przypadek bazowy wynika z wcześniejszego zadania, a krok: Wiemy z założenia, że aby wyrazić formułę f(n) , potrzebujemy co najmniej n+1 wystąpień zmiennej p. Skoro f(n+1) = f(n) , to formuła dla n+1 musi wyrażać to, co formuła dla n, oraz dodatkowo jeszcze tę ostatnią alternatywę. Wobec tego zmienna p musi być użyta jeszcze jeden raz, co daje w sumie n+2 użycia. text/html 2009-10-21T02:20:52+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:74?rev=1256084452&do=diff @pomysł na rozwiązanie: Zbiór tych spójników nie jest zupełny, ponieważ za ich pomocą nie można uzyskać negacji pojedynczego zdania (obalenie twierdzenia poprzez kontrprzykład?). text/html 2009-10-19T01:32:10+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:76?rev=1255908730&do=diff Najpierw dowód 1-zupełności zbioru Mamy 4 funkcje boolowskie jedno argumentowe i wszystkie możemy przedstawić za pomocą tych spójników: opisuje funkcję opisuje funkcję opisuje funkcję opisuje funkcję Dalej trzeba przedstawić, że nie jest to zbiór zupełny, co robimy poprzez wykazanie, że nie da się uzyskać alternatywy. text/html 2009-10-20T23:50:23+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:80?rev=1256075423&do=diff Mamy pokazać, że zbiór {⇒, ⊥} jest zupełny głębokość n = 1 ~ p ≡ (p ⇒ ⊥) Τ ≡ (⊥ ⇒ ⊥) n = 2 trzeba pokazać koniunkcje, alternatywę i równoważność (trzy kropki będą bo mi się nie chce co chwile tego samego robić) p ∨ q ≡ ~ p ⇒ q ≡ (p ⇒ ⊥) ⇒ q p ∧ q ≡ ~ (~ p ∨ ~ q) ≡ ... ≡ (p ⇒ (q ⇒ ⊥)) ⇒ ⊥ p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) ≡ ... ≡ ⇒ ⊥ text/html 2009-10-20T23:30:04+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:85?rev=1256074204&do=diff Korzystając z 80 wiemy, że {⇒, ⊥} jest zupełne, a nasz zbiór {⊕, Τ} jest to: ⊕ ≡ ~ ⇒ oraz Τ ≡ ~⊥ Czyli zostaje pokazać nam, że ~ da sie przedstawić za pomocą tych spójników. ~p ≡ p ∧ ⊥ ≡ p ∧ ~ Τ ≡ p ⊕ Τ text/html 2009-10-17T03:06:49+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:86?rev=1255741609&do=diff to NAND, czyli negacja koniunkcji. Z zadania 80. wiemy, że jest zupełny. Wystarczy więc wyrazić te dwa spójniki za pomocą . ( to może być rownież NOR) text/html 2009-10-27T23:37:34+02:00 http://ii.drx.pl/logika_dla_informatykow:skrypt:98?rev=1256683054&do=diff Ponieważ ja te zadania robiłem od końca, to pozwolę sobie właśnie teraz na nieco relaksu. Niech „zapłacisz jej 100zł”, a „pójdzie z tobą do łóżka”. I teraz oznacza, że istnieje taka dziewoja, która za 100zł pójdzie z tobą do łóżka.