w1logikaE.pdf

Informacjeorganizacyjne

• WykładowcaDrhab.DariuszWrzosek,profUW,e-mail:darekw@mimuw.edu.pl,

http://www.mimuw.edu.pl/darekw/biologia.html

• wiczeniagodz.16.15wgmachuWydziałuMatematyki:

• DrMarekBodnargrupy4,8poniedziałek4,8sala2043

• MgrGabrielPietrzkowskigrupy1,5wtoreksala117Ipi¦tropoprawejstronie

• MgrGabrielPietrzkowskigrupy2,6±rodasala3160

• MgrTomaszCie±lakgrupy3,7czwarteksala2043

1Podstawylogiki

Napierwszymwykładziepoznamypodstawylogikimatematycznej.Ogólnierzeczujmuj¡cinieco

upraszczaj¡clogikatonaukaozasadachpoprawnegorozumowania.Logikaformalnalubmatema-

tyczna,którejpodstawypoznamysytuujesi¦napograniczuﬁlozoﬁiimatematyki.Zajmujesi¦

onami¦dzyinnymibadaniemtakichregułwnioskowania,dzi¦kiktórymzprawdziwo±cijednych

zda«wnosimyoprawdziwo±ciinnychzda«bezrozpatrywaniaichgł¦bszychznacze«izwi¡zkuz

rzeczywisto±ci¡.Tunale»ypodkre±li¢,»ezajmiemysi¦jedyniepodstawamirachunkuzda«ilo-

gikidwuwarto±ciowejtoznaczytakiejktóraprzyjmuje,»edanezdaniemo»eby¢alboprawdziwe

albofałszyweinicpo±rodku.Takoncepcjajestkluczowadlamatematykiinaukprzyrodniczych

gdy»naukitestwierdzaj¡naogółoistnieniulubnieistnieniupewnychobiektówlubichcechst¡d

dwuwarto±ciowo±¢s¡dów,niemo»nazarazemistnie¢inieistnie¢.Rozwa»asi¦tak»elogikiwie-

lowarto±ciowe,któremaj¡zastosowanienaprzykładprzymodelowaniuprocesówdecyzyjnychw

przypadkuró»negostopniapewno±cicodoprawdziwo±cis¡dów,np.systemyeksperckiewspoma-

gaj¡cepodejmowaniedecyzjiprzezlekarza.

Tenwykładmanaceluzapoznanieprzyszłychbiologówzpodstawamilogikiformalnej,której

prawa,cho¢zdaj¡si¦by¢powszechnierespektowane,nies¡powszechnieznaneiwykorzystywane.

1.1Poj¦ciezdaniawlogice

Deﬁnicja1Zdaniemwlogicenazywamywyra»enieoznajmuj¡ce,któremumo»naprzyporz¡dko-

wa¢warto±¢prawdyozn.1lubfałszuozn.0.

Nieka»dezdaniezpunktuwidzeniagramatykijestzdaniemzpunktuwidzenialogiki.Oczywi±cie

pytanianies¡zdaniamiwsensielogicznym,azdanie

Litera”a”poprzedzaliter¦”b”

mimoi»jestdobrzezbudowaneiwyra»apewiens¡dtojegoprawdziwo±¢zale»yodkontekstu.

Dopierozdanie

Litera”a”poprzedzaliter¦”b”wwyrazie”absolut”.

spełniaju»wymogipowy»szejdeﬁnicji.

Zauwa»my,»ewdeﬁnicjizdanianiemamowyotymwjakisposóbmo»nastwierdzi¢czy

danezdaniejestprawdziweczynie.Logikaniezajmujesi¦bezpo±redniobadaniemrzeczywisto±ci

empirycznejalebadaniemwzajemnychzale»no±cimi¦dzyzdaniami,któreco±orzeczywisto±ci

stwierdzaj¡.Rozwa»mydwaprosteprzykładyzastosowanialogiki.

Rozpatrzmydwazdania

A.Ka»dyseryjnieprodukowany

samochódosobowyna±wieciema

kierownic¦polewejstronie.

B.Samochód,którykupuj¦wsalonie

ﬁrmowymmakierownic¦polewejstronie.

Zdanie B wynikanamocyprawalogiki,którepoznamydalej,zezdania A .Uznaniezdania B

zaprawdziwenamocy A niewymaga»adnejwiedzyo±wiecie.Bystwierdzi¢czyzdanie A jest

prawdziwetrzebazdoby¢okre±lon¡wiedz¦empiryczn¡,wykona¢obserwacje.Bywalecsalonów

samochodowegomo»eodwiedzi¢WyspyBrytyjskieitamnatraﬁ¢namodelzkierownic¡poprawej

stronie.Dzi¦kiprawulogiki(patrzdalejtautologia7.)mo»eby¢wtedypewien,»ezdanie A jest

fałszyweiwtymprzypadkulogikaprowadzidowzbogaceniawiedzyo±wiecie.

Rozwa»mytrzyinneprzykładyzda«zło»onych

C.Je±lipadadeszcztoszukamparasola.

D.Niepadadeszczlubszukamparasola.

E.Padadeszczinieszukamparasola.

ZdanieCjestprzykłademimplikacjizdanieD.alternatywyazdanieE.koniunkcji.Dzi¦kiprawom

logiki,którepoznamywdalszejcz¦±ciwykładumo»nastwierdzi¢,»ezdanie D mimo,»ebrzmi

niecodziwnie,znaczytosamocozdanie C azdanie E przeczyimobu.

Najcz¦±ciejmamydoczynieniazezdaniamizło»onymi,którychpodstawowetypyterazpo-

znamy,przyjmuj¡ckonwencj¦,»ezdaniaoznaczamyliterami p,q,r....

Zaprzeczeniezdania p oznaczamyprzez ¬ p .

Podstawylogikiklasycznejformułowanowszkolestoików(ChryzypIIIwp.n.e).Znanes¡dzieła

ArystotelesaAnalitykipierwszeiAnalitykiwtóreobejmuj¡cepodstawylogikiznanewstaro»ytno-

±ci.Rozwójwspółczesnejlogikiszedłwparzezrozwojemmatematykiizainicjowanybyłpracami

Boole’azpołowyXIXw.NaprzełomiewiekówXIXiXXs¡dzononawet,»ecał¡matematyk¦da

si¦sprowadzi¢dostosowaniapodstawowychregułlogicznych(programHilberta).Słynnedzieło

BertrandaRussellaiAlfredaWhiteheadaPrincipiamathematicaokre±liłopodstawylogikiformal-

nejimatematykidaj¡cnadziej¦nazrealizowanieprogramuHilberta,alerówniesłynneodkrycia

G¨ o dlazpocz¡tkuXXw.odebrałynadziej¦nazrealizowanietejidei.Mówi¡cwdu»ymuproszcze-

niuokazałosi¦,»ewobr¦biepodstawowychteoriimatematycznychtakichjaknpteoriazboru

liczbnaturalnychobejmuj¡caarytmetyk¦,mo»nasformułowa¢poprawniezbudowane”sensowne”

zdaniaoktórychnigdyniedowiemysi¦czys¡prawdziweczynie.Wi¦cejnatentematmo»na

przeczyta¢wksi¡»ceohistoriimatematyki[22]lubwksi¡»cepopularno-naukowej[7].

1.2Podstawowezdaniazło»one

Podstawowezdaniazło»oneokre±lasi¦deﬁniuj¡cichwarto±¢logiczn¡napodstawiewarto±cilo-

gicznejzda«składowych.Najlepiejujmujesi¦t¦zale»no±¢wpostacitzw.tabeleklogicznych.

Dodajmy,»eponi»szepodstawowezdaniazło»onemaj¡swojeodpowiednikiwteoriizbiorówo

czymwspomnimynanast¦pnymwykładzie.

• Równowa»no±¢zda« p,q ozn. p , q odpowiadawyra»eniu-zdanie p jestprawdziwe

wtedyitylkowtedygdyprawdziwejestzdanie q .Zdanie p jestrównowa»nezdaniu q

gdyobazdanias¡jednocze±nieprawdziweb¡d¹fałszywe.

pqp , q

11 1

01 0

10 0

00 1

Wdalszymci¡guzamiastwyra»enia”wtedyitylkowtedy”b¦dziemyu»ywa¢skrótu”w.t.w”.

• Koniunkcjazda«- p i q ozn. p ^ q jestprawdziwaw.t.w.gdyobaczłonykoniunkcjis¡

jednocze±nieprawdziwe.

pqp ^ q

10 0

01 0

00 0

11 1

• Alternatywazda«- p lub q ozn. p _ q jestprawdziwaw.t.w.gdyprzynajmniejjedenz

członówalternatywyjestprawdziwy.

pqp _ q

10 1

01 1

00 0

11 1

Wartopodkre±li¢,»ealternatywadwóchzda«jestprawdziwymzdaniemtak»ewtedygdy

obazdaniaskładowes¡prawdziweanietylkogdyjednozdwóchjestprawdziwecocz¦sto

wmowiepotocznejjestmylone.Wcelupodkre±lenianiemo»no±cijednoczesnegospełnienia

obuzda«składowychlepieju»y¢słowa”albo”zamiast”lub”takjakwsłynnymby¢albonie

by¢.

• Implikacja-je±li p to q ozn. p ) q jestprawdziwagdypoprzednikimplikacji p jest

fałszywylubnast¦pnikimplikacji q jestprawdziwyifałszywatylkowtedygdyprawdziwyjest

poprzednikifałszywynast¦pnik.Sensimplikacji p ) q dobrzeoddajerzadkoju»u»ywane

okre±lenie-zda nie p poci¡gazasob¡zdanie q .

pqp ) q

11 1

01 1

00 1

10 0

Dodajmy,»edwazdania p i q s¡równowa»negdy p ) q i q ) p .

Nale»ypodkre±li¢,»eje±lipoprzednikimplikacjijestfałszywytoimplikacjajestzawszeprawdziwa.

Zdanie”Je±lib¦dzieszsi¦uczyłcałytydzie«przedegzaminemtogozdasz”jestfałszywetylko

wtedygdyuczyłe±si¦całytydzie«przedegzaminemigoniezdałe±.Jestonoprawdziwerównie»

wtedygdynieuczyłe±si¦przeztydzie«izdałe±egzamingdy»owynikuegzaminumogłyprzecie»

przes¡dzi¢jakie±inneczynnikinieobj¦tewpoprzednikuimplikacji.Jestonooczywi±cieprawdziwe

gdynieuczyłe±si¦przeztydzie«iniezdałe±egzaminu.

Podkre±lmy,»eimplikacjirozumianejjakwy»ejnienale»ymyli¢zwnioskowaniemlogicznym,

którejestzastosowaniemktórego±prawalogikiprzyprzechodzeniuodzało»e«(przesłanek)do

wniosku.Zast¡pieniekonstrukcjiokresuwarunkowego”je±liptoq”wyra»eniem”zpwynikaq”

mo»eprowadzi¢donieporozumie«.Poni»szezdaniejestprzykłademoczywistegownioskowania

dedukcyjnego

Je±liwykładowcamatematyki

mieszkawKrakowie

tomieszkawPolsce.

Fakt,»emieszkamwWarszawieniewpływanaprawdziwo±¢tegozdania,zgodniezdeﬁnicj¡

implikacji.

Zdanie

Je±li4jestpodzielneprzez2

topiesmaczterynogi.

jestprzykłademprawdziwejimplikacjibozarównopoprzednikjakinast¦pniks¡zdaniamipraw-

dziwymialeoczywi±cieniejesttoprzykładwnioskowania,cho¢owypowiadaj¡cymtozdaniez

pewno±ci¡mo»naco±wywnioskowa¢.

Deﬁnicja2Wprzypadkuimplikacji

p ) q (1)

zdanie q nazywamywarunkiemkoniecznymdlazdania p azdanie p nazywamywarunkiem

wystarczaj¡cymdlazdania q .Implikacj¦ q ) p nazywasi¦implikacj¡odwrotn¡do(1),im-

plikacj¦ ¬ q )¬ p nazywasi¦kontrapozycj¡(1)aimplikacj¦ ¬ p )¬ q implikacj¡przeciwn¡

do(1).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: