skrypt04.pdf

Uniwersytet Wrocławski, Instytut Informatyki

Studia magisterskie na kierunku Informatyka

Przedmiot obowi azkowy w semestrze zimowym pierwszego roku studiów

30 godzin wykładu + 30 godzin repetytorium + 30 godzin cwicze n

Logika dla informatykÂw

Materiaøy do zajec

Leszek Pacholski

Wrocław, 2004

2004/5

Własciciel tej kopii notatek

Rok akad.

Uwaga: W niniejszej ksi azeczce zebrano listy zada n, notatki do wykładów oraz inne

materiały przygotowywane do zajec z Logiki dla informatyków w latach 1997–2004.

Mimo iz materiały te posiadaj a bardziej dopracowan a forme, niz przygotowywane do

innych zajec kserograﬁczne kopie oraz zostały oddane do druku i oprawy, jednak nie

były poddane — jak to ma miejsce w przypadku podreczników — solidnej korekcie

i zawieraj a sporo błedów. Nie zamieszczono w nich takze szczegółowych wyjasnie n

i komentarzy. Dlatego notatki te nie s a podrecznikiem do wykładu . Maj a jedynie słu-

zyc jako wykaz zagadnie n obowi azuj acych do egzaminu i lista zada n przerabianych

na cwiczeniach. Przegl ad zalecanych do zajec podreczników jest zamieszczony na

stronie xi.

Podczas redagowania notatek wykorzystano:

– skrypt J. Tiuryna Wstep do teorii mnogosci i logiki

– listy zada n M. Zakrzewskiego

– materiały A. Koscielskiego i T. Wierzbickiego

– podreczniki wymienione w bibliograﬁi na stronie xi

Redakcja i skład: T. Wierzbicki

Konsultacja merytoryczna: A. Koscielski

Wydanie drugie, (nieznacznie) poprawione i rozszerzone

Niniejsze notatki mog a byc drukowane, powielane oraz rozpowszechniane w wersji elektronicznej i pa-

pierowej, w czesci b adz w całosci — bez koniecznosci uzyskania zgody autora — pod warunkiem nie-

osi agania bezposrednich korzysci ﬁnansowych z ich rozpowszechniania i z zachowaniem praw autorskich.

W szczególnosci dodatkowe egzemplarze mog a byc sprzedawane przez osoby trzecie jedynie po cenie

uzyskania kopii (druku, wydruku, kserografowania itp.)

Data utworzenia dokumentu: 15 wrzesnia 2004

ISBN: 83–917081–7–9

Strona WWW zajec: http://www.ii.uni.wroc.pl/~pacholsk/logika.phtml

Szanowni Panstwo,

Program wykładu logiki dla informatyków nie jest trudny — w nastepnych se-

mestrach bedziecie Panstwo słuchali duzo trudniejszych wykładów. Mimo to co roku

znaczna czesc studentów nie zdaje egzaminu z logiki.

Jednym z powodów niepowodzenia na egzaminie jest to, ze jest to dla Was pierw-

szy w zyciu wykład akademicki, w którym pojawia sie duza liczba nowych pojec. Poje-

cia te, na ogół dosyc abstrakcyjne, pojawiaj a sie licznie na kazdych zajeciach. Trzeba

sie ich wszystkich nauczyc. Nauczyc — to mało, gdyz matematyka nie polega na wy-

konywaniu mniej lub bardziej skomplikowanych rachunków, lecz na przeprowadzaniu

rozumowan. Dlatego jest bardzo wazne, byscie nie tylko je znali, ale i dobrze rozu-

mieli. Wykład ma Wam w tym pomóc, ale wielu z Was nie zdoła na samym wykładzie

opanowac całego materiału. Na wykładzie nie nauczycie sie tez sprawnie posługi-

wac wprowadzonymi pojeciami. Dlatego musicie systematycznie pracowac w domu.

Jesli przed zajeciami przypomnicie sobie wczesniej wprowadzone deﬁnicje, zwiek-

szycie swoje szanse na zrozumienie nowego materiału. Jesli natomiast nie bedziecie

znac wczesniej wprowadzonych pojec, bedziecie z duzym prawdopodobienstwem sie-

dziec na wykładzie, jak na tureckim kazaniu. Jezeli przyswojenie nowych pojec spra-

wia Wam trudnosc, radze takze przed wykładem przejrzec podane w przygotowanych

przez nas notatkach deﬁnicje, które dopiero zostan a na zajeciach wprowadzone. Byc

moze czytaj ac je po raz pierwszy przed wykładem nie potraﬁcie ich w pełni zrozumiec,

ale gdy je wczesniej przeczytacie, wyniesiecie z wykładu znacznie wiecej. Poza tym

bedziecie przed zajeciami wiedziec, czego nie rozumiecie i o co na wykładzie zapytac.

Od wielu lat wszystkim studentom zaczynaj acym studia powtarzam to, co napi-

sałem w poprzednim paragraﬁe. Niestety z marnym skutkiem. Co roku w drugiej po-

łowie semestru okazuje sie, ze znaczna czesc studentów nie rozumie wykładu, bo nie

pamieta wczesniej wprowadzonych deﬁnicji i nie zna tresci udowodnionych wcze-

sniej twierdzen. Co roku mniej niz połowa studentów zdaje egzamin z logiki. Bardzo

nas to martwi. Chcielibysmy, aby znaczna wiekszosc z Was mogła ukonczyc studia.

Dlatego aby Was zdyscyplinowac i zmusic do systematycznej pracy wprowadzamy

opisane w regulaminie zajec rygory (punktowy system zaliczania cwiczen, kartkówki,

egzamin połówkowy itd.). Ich celem nie jest uprzykrzenie Wam zycia, ale zwiekszenie

szansy na to, ze zdacie egzamin.

Leszek Pacholski

Spis tresci

A. Informacje ogólne

A.1. Program wykładu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.2. Zapisy na zajecia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A.3. Obsada zajec i konsultacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B. Literatura

C. Zasady prowadzenia i zaliczania cwicze n xiii

C.1. Wstep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

C.2. Szczegółowe zasady prowadzenia zajec . . . . . . . . . . . . . . . . . . . . . . xiv

D. Egzaminy xix

D.1. Egzamin zasadniczy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx

D.1.1. Egzamin połówkowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi

D.1.2. Egzamin koncowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi

D.2. Egzamin poprawkowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi

0. Zadania na dobry pocz atek

1. Rachunek zda n i rachunek kwantyﬁkatorów 5

1.1. Składnia rachunku zda n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2. Wartosci logiczne i znaczenie formuł zdaniowych . . . . . . . . . . . . . . . 5

1.2.1. Metoda zero-jedynkowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2.2. Skrócona metoda zerojedynkowa . . . . . . . . . . . . . . . . . . . . . 7

1.2.3. Równowaznosc formuł . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.4. Lemat o podstawianiu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3. Formalizacja rozumowan w jezyku rachunku zda n . . . . . . . . . . . . . . 15

1.4. Własnosci formuł zdaniowych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.5. Postaci normalne formuł zdaniowych . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5.1. Usuwanie symbolu negacji . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: