Pogonowski Jerzy - Logika Matematyczna (skrypt).pdf - ♥ Matematyka - adamrex

LogikaMatematyczna16–17

JerzyPogonowski

ZakładLogikiStosowanejUAM

www.logic.amu.edu.pl

pogon@amu.edu.pl

SemantykaKRP(1)

JerzyPogonowski (MEG) LogikaMatematyczna16–17 SemantykaKRP(1) 1/50

Plannadzi±

Rozpoczynamyprezentacj¦ KlasycznegoRachunkuPredykatów (KRP).

Wtyminast¦pnymwykładzieomówimy:

składni¦isemantyk¦j¦zykaKRP

tautologieorazwynikanielogicznewKRP

j¦zykKRPjakostandardwkonstrukcjij¦zykówteoriinaukowych.

Kolejnewykładydotycz¡ceKRPpo±wi¦coneb¦d¡ró»nymoperacjom

konsekwencji:

tablicowej

aksjomatycznej

zało»eniowej

rezolucyjnej

gentzenowskiej.

JerzyPogonowski (MEG) LogikaMatematyczna16–17 SemantykaKRP(1) 2/50

Plannadzi±

Poka»emy,»ewszystkieteoperacjekonsekwencjis¡trafneipełne.Jednaz

podstawowychró»nicmi¦dzyKRPaomówionymwcze±niejKRZpolegana

tym,»eKRP niejest rozstrzygalny:nieistniejealgorytm,pozwalaj¡cy

rozstrzyga¢odowolnejformulej¦zykaKRPczyjestonaprawem

(tautologi¡)tegorachunku.KRPjestjedynie półrozstrzygalny :je±lijaka±

formułaj¦zykaKRZ jest tautologi¡KRP,tofakttenmo»napo±wiadczy¢

zapomoc¡metodyalgorytmicznej(bazuj¡cejnaktórej±zwymienionych

wy»ejoperacjikonsekwencji).

Uwaga. Problematykaomawianawsemestrzeletnimjesttrudniejszaodtej

przedstawionejdotychczas.Zalecasi¦udziałwzaj¦ciach,odrabianiezada«

domowych,samodzielnerozwi¡zywaniezada«.B¦dziemyistotniekorzysta¢

zwiadomo±ciprzedstawionychnazaj¦ciachze Wst¦pudoMatematyki .

JerzyPogonowski (MEG) LogikaMatematyczna16–17 SemantykaKRP(1) 3/50

Plannadzi± Literaturazalecana

Literaturazalecana

Wniniejszejprezentacjipodajemyjedyniepotrzebnedeﬁnicjeorazformułujemy

twierdzenia.Dowodywszystkichtwierdze«orazprzykładyi¢wiczeniapodanow

plikusemkrp.pdf.Zalecan¡literatur¡dotejproblematykijest:

Batóg,T.2003.Podstawylogiki.WydawnictwoNaukoweUAM,Pozna«

(strony109–112oraz238–261).

Ławrow,I.A.,Maksimowa,L.L.2004.Zadaniazteoriimnogo±ci,logiki

matematycznejiteoriialgorytmów.WydawnictwoNaukowePWN,Warszawa

(strony85–89oraz95–96,azwłaszczaprzypistłumaczanastronach87–88).

Marek,I.2002.Elementylogikiformalnej.WydawnictwoUniwersytetu

l¡skiego,Katowice.

Pogorzelski,W.A.1981.Klasycznyrachunekpredykatów.Zarysteorii.

Pa«stwoweWydawnictwoNaukowe,Warszawa.

Stanosz,B.2005.wiczeniazlogiki.WydawnictwoNaukowePWN,

Warszawa.

JerzyPogonowski (MEG) LogikaMatematyczna16–17 SemantykaKRP(1) 4/50

J¦zykKRP Alfabet

Alfabet

NiechI,J,Kb¦d¡dowolnymizbiorami.Rozpatrzmy alfabet

= 1 [ 2 [ 3 [ 4 [ 5 [ 6 ,gdzie:

1 ={x 0 ,x 1 ,x 2 ,...} — zmienneindywiduowe ,

2 ={P n i

i } i2I (n i 2N) — predykaty ,

3 ={f n j

j } j2J (n j 2N) — symbolefunkcyjne ,

4 ={a k } k2K — stałeindywiduowe ,

5 ={^,_,!,¬,,8,9}— stałelogiczne ,

6 ={,,,(,)} — symbolepomocnicze .

JerzyPogonowski (MEG) LogikaMatematyczna16–17 SemantykaKRP(1) 5/50

Pogonowski Jerzy - Logika Matematyczna (skrypt).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: