Wykłady ze Wste˛pu do Matematyki Jacek Cichon´ WPPT, Politechnika Wrocławska MAJ 2012 Spis tres´ci 1 RachunekZdan´ 7 1.1 ZdaniaiWaluacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Przegla˛dNajwaz˙niejszychTautologii . . . . . . . . . . . . . . . . . . 10 1.3 MetodyDowodzeniaTwierdzen´ . . . . . . . . . . . . . . . . . . . . 12 1.4 NotacjaPolska . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2 Zbiory 20 2.1 AksjomatEkstensjonalnos´ci . . . . . . . . . . . . . . . . . . . . . . 20 2.2 OperacjeMnogos´ciowe . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 DiagramyVenna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3 Kwantyfikatory 32 3.1 Definicjakwantyfikatorów . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Własnos´cikwantyfikatorów. . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Kwantyfikatoryograniczone . . . . . . . . . . . . . . . . . . . . . . 37 3.4 Działaniauogólnione . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4 RelacjeiFunkcje 43 4.1 PodstawoweKlasyRelacji . . . . . . . . . . . . . . . . . . . . . . . 44 4.2 Funkcje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3 FunkcjeLogiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4 ObrazyiPrzeciwobrazy. . . . . . . . . . . . . . . . . . . . . . . . . 50 4.5 IndeksowaneRodzinyZbiorów . . . . . . . . . . . . . . . . . . . . . 52 4.6 ProduktyKartezjan´skie . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.7 FunkcjeCharakterystyczne . . . . . . . . . . . . . . . . . . . . . . . 53 4.8 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5 Relacjerównowaz˙nos´ci 57 5.1 Rozbicia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 Konstruowanieobiektówmatematycznych . . . . . . . . . . . . . . . 60 5.3 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 6 Cze˛s´ciowePorza˛dki 64 6.1 Wyróz˙nioneelementy . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.2 Porza˛dkinarodzinachfunkcji . . . . . . . . . . . . . . . . . . . . . 68 6.3 LiniowePorza˛dki . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 1 6.4 LematKuratowskiego-Zorna . . . . . . . . . . . . . . . . . . . . . . 72 6.5 Dobreporza˛dki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 6.6 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 7 IndukcjaMatematyczna 78 7.1 Definicjerekurencyjne . . . . . . . . . . . . . . . . . . . . . . . . . 78 7.2 Zbioryskon´czone . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 7.3 Permutacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.4 SymbolNewtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 7.5 ZasadaDirichleta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 7.6 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8 Teoriamocy 90 8.1 TwierdzeniaCantora . . . . . . . . . . . . . . . . . . . . . . . . . . 91 8.2 Zbioryprzeliczalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 8.3 Zbiorymocycontinuum . . . . . . . . . . . . . . . . . . . . . . . . 95 8.4 Algebramocy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 8.5 Funkcjeobliczalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 8.6 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 9 DrzewaiRelacjeUfundowane 103 9.1 RelacjeUfundowane . . . . . . . . . . . . . . . . . . . . . . . . . . 103 9.2 SystemyPrzepisuja˛ce . . . . . . . . . . . . . . . . . . . . . . . . . . 104 9.3 Drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.4 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A AlgebryBoole’a 111 A.1 Ciałazbiorów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 A.2 Ideałyifiltry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 A.3 Twierdzenieoreprezentacji . . . . . . . . . . . . . . . . . . . . . . . 119 A.4 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 B Kraty 122 B.1 Kratyzupełne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 B.2 Tablicesemantyczne . . . . . . . . . . . . . . . . . . . . . . . . . . 125 B.3 C´wiczeniaizadania . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 C Aksjomatyteoriimnogos´ci 130 C.1 Aksjomaty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 C.2 Oniesprzecznos´ci . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 C.3 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 D LiczbyPorza˛dkoweiKardynalne 136 D.1 IndukcjaPozaskon´czona . . . . . . . . . . . . . . . . . . . . . . . . 138 D.2 FunkcjaHartogsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 D.3 LiczbyKardynalne . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 D.4 Pote˛gowanieLiczbKardynalnych . . . . . . . . . . . . . . . . . . . 145 D.5 Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 E Wskazówkidozadan´ 150 Bibliografia 155 Indeks 156 Wste˛p Ksia˛z˙kazawieradziewie˛c´wykładówpos´wie˛conychomówieniuorazuporza˛dkowaniu podstawowych poje˛c´ matematycznych. Ich tres´c´ odpowiada w przybliz˙eniu wykła- dom ze “Wste˛pu do Matematyki”, które autor wielokrotnie prowadził dla studentów Instytutu Matematycznego Uniwersytetu Wrocławskiego oraz Wydziału Podstawo- wychProblemówTechnikiPolitechnikiWrocławskiej. Autorpragniegora˛copodzie˛- kowac´prof.B.We˛glorzowiorazprofW.Kordeckiemuzaszereguwag,którepomogły uporza˛dkowac´ iunowoczes´nic´ materiał. Dzie˛kuje˛ równiez˙ studentomWPPTPWrza pomocweliminowaniuusterekzwczes´niejszychwersjitejksia˛z˙ki. Główna cze˛s´c´ ksia˛z˙ki odpowiada zakresowi materiału który obowia˛zywał wszy- stkichstudentówitenzakresmateriałupowiniendobrzeopanowac´ kaz˙dystudentin- formatyki i matematyki. Cze˛s´ci ksia˛z˙ki umieszczone w dodatkach stanowia˛rozsze- rzeniepodstawowegokursu. 1. Wwykładziepierwszymomawiamypodstawowepoje˛ciaRachunkuZdan´.Wy- kładopieramynapoje˛ciuwaluacji,zewzgle˛dunaliczne,zwłaszczawinforma- tyce,zastosowaniauogólnien´ tegopoje˛cia. Głównymcelemtegowykładujest przegla˛dpodstawowychtautologiiorazwprowadzeniupoje˛ciareguływniosko- wania. 2. Wwykładziedrugimzajmujemysie˛ RachunkiemZbiorów. Rozwaz˙aniaopie- ramyoAksjomatEkstensjonalnos´ci.Pierwszymdowodzonymprzeznasfaktem jesttwierdzenieRussell’aonieistnieniuzbioruwszystkichzbiorów. Naste˛pnie omawiamy własnos´ci sumy, przekroju i róz˙nicy zbiorów. Wszystkie dowody sprowadzamydoRachunkuZdan´. 3. W wykładzie trzecim zajmujemy sie˛ własnos´ciami kwantyfikatorów W tym miejscu wykład traci nieco na precyzji. Interpretacje˛ kwantyfikatorów redu- kujemydoRachunkuZbiorów. ZbardziejprecyzyjnymwprowadzeniedoRa- chunkuPredykatówstudencizapoznaja˛sie˛nawykładziezLogikiMatematycz- nejlubLogikiAlgorytmicznej.Elementemwymagaja˛cymszczególnejuwagisa˛ uzasadnienia zalez˙nos´ci pomie˛dzy wyraz˙eniami zbudowanymi z bloku dwóch kwantyfikatorów. W wykładzie tym omawiamy równiez˙ poje˛cie sumy i prze- krojudowolnejrodzinyzbiorów. 4. Wykład czwarty pos´wie˛camy relacjom. Definiujemy podstawowe klasy rela- cji, w tym poje˛cie funkcji. Zajmujemy sie˛ obrazami i przeciwobrazami zbio- 4 rówprzezrelacje. Omawiamyfunkcjelogiczne-pokazujemy,z˙estandardowy zestawspójnikówlogicznychjestzupełny(syntezaformułyodbywasie˛ zapo- moca˛tabeliwartos´cirozwaz˙anejfunkcji). Naste˛pnieomawiamyindeksowane rodzinyzbioróworazproduktykartezjan´skie. Wkon´cuwprowadzamypoje˛cie funkcjicharakterystycznejzbioru. 5. Wykładpia˛typos´wie˛conyjestwcałos´cirelacjomrównowaz˙nos´ci. Pokazujemy w nim, jak startuja˛c z liczb naturalnych moz˙na zdefiniowac´ liczby całkowite, wymierneirzeczywiste. 6. Wykład szósty pos´wie˛cony jest cze˛s´ciowym porza˛dkom. Po wprowadzeniu podstawowych poje˛c´ omawiamy porza˛dki na rodzinach funkcji. Celem tego fragmentu rozwaz˙an´ jest przybliz˙enie czytelnikom notacji f = O(g). Na- ste˛pnieomawiamylinioweporza˛dkiiporza˛dekleksykograficznynaprzestrzeni słów. PrzechodzimydoprezentacjiLematuKuratowskiego-Zornaijegopod- stawowychkonsekwencji. WprowadzamyAksjomatWyboru. Podkoniectego wykładuomawiamypoje˛ciedobregoporza˛dku. 7. W wykładzie pos´wie˛conym Indukcji Matematycznej pokazujemy jej równo- waz˙nos´c´ zdobrymuporza˛dkowaniemzbioruliczbnaturalnych,omawiamyde- finicjerekurencyjne. Przypominamypoje˛ciepermutacjiiwprowadzamysym- bolNewtona. Rozwaz˙aniakon´czymyzasada˛Dirichleta. 8. W wykładzie ósmym omawiamy poje˛cie równolicznos´ci i nierównos´ci mocy. Twierdzenie Cantora - Bernsteina wyprowadzamy za pomoca˛Lematu Bana- cha. Omawiamyzbioryprzeliczalneizbiorycontinuum. Głównymobszarem zainteresowan´ jestzbiórN∪{ℵ0,2ℵ0},jednakpodkoniecrozdziałuwprowa- dzamyhierarchie˛ liczb(cid:105) dlan∈N. n 9. Wykładdziewia˛typos´wie˛conyjestrelacja˛ufundowanym, systemomprzepisu- ja˛cym oraz drzewom. Tematy te umieszczone sa˛w głównej cze˛s´ci ksia˛z˙ki ze wzgledunaichlicznezastosowaniawinformatyce. 10. WdodatkuAznajdujesie˛ wprowadzeniedoteoriialgebrBoole’a. Rozpoczy- namyoddefinicji,akon´czymynasłabejwersjitwierdzeniaStone’aoreprezen- tacji. Wtrakcierozwaz˙an´ pojawiasie˛ poje˛cieciałazbiorów. 11. WdadatkuBwprowadzamypoje˛ciekratyidowodzimytwierdzenieKnastera- Tarskiego o punkcie stałym. Za jego pomoca˛podajemy alternatywny dowód LematuBanacha.Naste˛pnieomawiamydrzewa,dowodzimytwierdzenieKöniga oistnieniunieskon´czonejgałe˛zi. Nazakon´czeniewprowadzamypoje˛cietablic semantycznychdlarachunkuzdan´. 12. WdodatkuComawiamysystemaksjomatówteoriimnogos´ciZermelo-Fraen- kel’aizagadnieniazwia˛zanezniesprzecznos´cia˛tejteorii. SPISTRES´CI 6 13. WdodatkuDomawiamyliczbyporza˛dkoweorazliczbykardynalne. Rozwaz˙a- niakon´czymyomówieniem,jakimalefemmoz˙ebyc´ liczbacontinuum. 14. W dodatku E znajduja˛sie˛ szkice rozwia˛zan´ lub wskazówki do trudniejszych zadan´. Zdos´wiadczeniaautorawynika,z˙epierwszedziewie˛c´wykładówmoz˙nazrealizo- wac´ wtrakciepierwszegosemestrustudiówinformatycznychorazmatematycznych. Aby to osia˛gna˛c´ nalez˙y wykład prowadzic´ stosunkowo szybko. Najbardziej obszer- nym poje˛ciowo jest wykład szósty, pos´wie˛cony cze˛s´ciowym porza˛dkom. Nalez˙y go rozbic´ naconajmniejczterygodzinywykładowe. Do kaz˙dego wykładu doła˛czone sa˛c´wiczenia oraz zadania. C´wiczenia sa˛ruty- nowe i stosunkowo proste. Powinny byc´ przerobione przez wszystkich studentów. Zadaniasa˛niecotrudniejszeiwymagaja˛pewnegopomysłu. Oprócztychzadan´ stu- dencipowinnizostac´ zache˛cenidozapoznaniasie˛ zewszystkimizadaniamizwia˛za- nymiztematamiomawianyminawykładziezksia˛z˙ki[6]. Jakoliterature˛ pomocnicza˛dowykładówmoz˙napolecic´ ksia˛z˙ki[4]oraz[7]. Stu- dentom, którzy moga˛czuc´ niedosyt formalizmu logicznego po trzecim wykładzie, moz˙na polecic´ ksia˛z˙ke˛ [1]. Jako literature˛ pomocnicza˛do materiału omawianego w dodatkachmoz˙napolecic´ pozycje[3],[5]oraz[2]. 1 Rachunek Zdan´ Reductioadabsurdum,whichEuclid lovedsomuch,isoneofa mathematician’sfinestweapons.Itis afarfinergambitthananychess gambit:achessplayermayofferthe sacrificeofapawnorevenapiece, butamathematicianoffersthegame. G.H.Hardy RachunekZdan´ jestdziałemlogikimatematycznejbadaja˛cymzwia˛zkipomie˛dzy zdaniamiutworzonymizezmiennychzdaniowychzapomoca˛spójnikówlogicznych. W klasycznym rachunku zdan´ - a takim włas´nie rachunkiem zdan´ zajmowac´ sie˛ be˛- dziemy podczas tego wykładu - przyjmuje sie˛, z˙e kaz˙demu zdaniu moz˙na przypisac´ jedna˛zdwóchwartos´cilogicznych-prawde˛lubfałsz.Wrozwaz˙aniachnaszychtres´c´ zdan´ niebe˛dziemiałaz˙adnegoznaczenia. Waz˙nabe˛dzietylkoichwartos´c´ logiczna. 1.1 ZdaniaiWaluacje Symbolep ,p ,p ,...nazywac´ be˛dziemyzmiennymizdaniowymi. Symbole(cid:62)i⊥ 0 1 2 sa˛stałymi; symbol(cid:62)nazywamyzdaniemzawszeprawdziwezas´ ⊥nazywamyzda- niem zawsze fałszywym. Oprócz zmiennych zdaniowych rozwaz˙ac´ be˛dziemy spój- nikilogiczne: ∧, ∨, ¬, →, oraz↔. Spójnik∧nazywamykoniunkcja˛, ∨nazywamy alternatywa˛, ¬ nazywamy negacja˛ba˛dz´ zaprzeczeniem. Kolejne dwa spójniki lo- giczne nazywamy implikacja˛i równowaz˙nos´cia˛. Do konstrukcji je˛zyka Rachunku Zdan´ potrzebujemy jeszcze dwóch symboli. Sa˛nimi nawiasy. Pierwszy z nich, „(”, nazywamynawiasemotwieraja˛cymzas´drugi,„)”,nawiasemzamykaja˛cym. Okres´limy teraz poje˛cie zdania Rachunku Zdan´. Posłuz˙ymy sie˛ w tym celu tak zwana˛technika˛rekurencyjna˛. Definicja1.1(Zdania) 1. Zmiennezdanioweorazstałe(cid:62)i⊥sa˛zdaniami. 2. Jes´liwyraz˙eniaϕiψsa˛zdaniami,torówniez˙zdaniamisa˛naste˛puja˛cewyraz˙e- nia: (ϕ∧ψ),(ϕ∨ψ),(ϕ→ψ),(ϕ↔ψ)i¬ϕ. 3. Dowolne wyraz˙enie jest zdaniem, jes´li moz˙e zostac´ zbudowane ze zmiennych zdaniowych w wyniku zastosowania pewnej skon´czonej liczby reguł z punktu (2). 7 ROZDZIAŁ1. RACHUNEKZDAN´ 8 Z powyz˙szej definicji moz˙na wyprowadzic´ kilka podstawowych faktów o rodzinie wszystkichzdan´. Przykład1.1 Jakoprzykładpokaz˙emy,z˙ewkaz˙dymzdaniuwyste˛pujeparzystaliczba nawiasów. Rozwaz˙my mianowicie rodzine˛ Ω tych wszystkich wyraz˙en´, które maja˛ parzysta˛ilos´c´nawiasów.Wtedyrodzinazmiennychzdaniowychzawierasie˛wrodzinie Ω, bowiem zero jest liczba˛parzysta˛. Zauwaz˙my naste˛pnie, z˙e jes´li wyraz˙enia ϕ i ψ sa˛elementamirodzinyΩ,czylimaja˛parzysta˛liczbanawiasów,torówniez˙wyraz˙enia (ϕ∧ψ), (ϕ∨ψ), (ϕ → ψ), (ϕ ↔ ψ) i ¬ϕ maja˛parzysta˛ilos´c´ nawiasów. Zatem kaz˙dezdaniejestelementemrodzinyΩ,cokon´czydowód. Wartos´ciamilogicznyminazywamysymbole0i1,któreinterpretujemyjakofałsz iprawde˛. Nazbiorzewartos´cilogicznych{0,1}okres´lamydziałania∧, ∨, ⇒, ⇔ oraz¬: zapomoca˛naste˛puja˛cejtabelki: p q p∧q p∨q p⇒q p⇔q ¬p 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 Czytelnikpowinienzwrócic´uwage˛narozróz˙nieniemiedzyspójnikamilogicznymi∧, ∨,→,↔,¬orazdziałaniami∧,∨,⇒,⇔oraz¬. Definicja1.2 Waluacja˛nazywamy dowolny cia˛g π = (w ,w ,w ,...) wartos´ci lo- 0 1 2 gicznych. Dla dowolnego zdania ϕ oraz dowolnej waluacji π = (w ,w ,w ,...) moz˙emy 0 1 2 okres´lic´ wartos´c´ π(ϕ)waluacjiπ naϕ. Procestennazywamywartos´ciowaniemzda- niazdaniaϕnazadanejwaluacjiπ. Definicja1.3(Wartos´ciowanie) Niech π be˛dzie waluacja˛. Dla dowolnej zmiennej zdaniowej p okres´lamy π(p ) = w . Jes´li ϕ oraz ψ sa˛zdaniami i okres´lone sa˛juz˙ i i i wartos´ciπ(ϕ)orazπ(ψ)),to 1. π((cid:62)) = 1, 2. π(⊥) = 0, 3. π(ϕ∧ψ) = π(ϕ)∧π(ψ), 4. π(ϕ∨ψ) = π(ϕ)∨π(ψ), 5. π(ϕ→ψ) = π(ϕ)⇒π(ψ), 6. π(ϕ↔ψ) = π(ϕ)⇔π(ψ), 7. π(¬ϕ) = ¬(π(ϕ)). Powyz˙szadefinicjamoz˙ewygla˛dac´ naniecoskomplikowana˛. Lecztakwistocienie jest. Stanietosie˛ zpewnos´cia˛jasnejuz˙ poprzes´ledzeniupierwszegoprzykładu. Przykład1.2 Niech π = (1,0,1,1,1,1,...) oraz niech ϕ = ((p ∨p )∧(¬p )). 0 1 2 Wtedy π(ϕ)=π((p ∨p )∧(¬p ))=π(p ∨p )∧π(¬p )= 0 1 2 0 1 2 (π(p )∨π(p ))∧¬(π(p ))=(1∨0)∧¬(1)=1∧0=0. 0 1 2 ROZDZIAŁ1. RACHUNEKZDAN´ 9 Obliczeniatemoz˙nazapisac´ troche˛ mniejformalnie,alezatobardziejczytelnie π(ϕ)=(1∨0)∧(¬1)=1∧0=0. Definicja1.4 Zdanieϕnazywamytautologia˛,cozapisujemyjako|=ϕ,jes´liπ(ϕ)= 1dladowolnejwaluacjiπ. Najprostsza˛tautologia˛jest oczywis´cie zdanie (cid:62). Inny prosty przykład to zda- nie p ∨¬p . Zauwaz˙my, z˙e do zbadania, czy dane zdanie jest waluacja˛wystarczy 0 0 tylkotenfragmentwaluacji,któryodpowiadazmiennymwchodza˛cymwskładanali- zowanegozdania. Ułatwiatoznaczniebadanietego,czydanezdaniejestwaluacja˛i sprowadzatozagadnieniedoznanejzeszkołys´redniejmetodyzero-jedynkowej. Przykład1.3 Pokaz˙emy,z˙ezdanie((p ∨p )∨p )↔(p ∨(p ∨p ))jesttautologia˛. 0 1 2 0 1 2 Niechϕ=((p ∨p )∨p )orazψ =(p ∨(p ∨p )).Rozwaz˙mynaste˛puja˛ca˛tabelke˛: 0 1 2 0 1 2 p p p p ∨p p ∨p ϕ ψ ϕ↔ψ 0 1 2 0 1 1 2 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 1 W tabelce tej mamy 8 wierszy, gdyz˙ istnieje 8 = 23 równych kombinacji wartos´ci logicznych p , p i p . W kolejnych kolumnach ustalonego wiersza prowadzone sa˛ 0 1 2 wszystkiepomocniczeobliczenia, którychcelemjestwyznaczeniewartos´cilez˙a˛cejw ostatniejkolumnie. Rozwaz˙anezdaniejesttautologia˛,gdyz˙wostatniejkolumniewy- ste˛puja˛tylkowartos´ci1. Zwróc´my uwage˛ na to, z˙e metoda tabelek zero - jedynkowych okres´la automa- tyczna˛metode˛ badania tego, czy dane zdanie jest tautologia˛. Zagadnienia tego typu nazywamy rozstrzygalnymi. Jednak metoda ta dla zdan´ zbudowanych ze 100 zmie- nnych zdaniowych wymagałaby rozpatrzenia 2100 ≈ 1.2·1030 przypadków, co jest zadaniemznacznieprzekraczaja˛cymmoceobliczeniowewspółczesnychkomputerów. Niewiadomo,czyistniejeistotnieszybszyalgorytmrozstrzygaja˛cyodanymzdaniu, czyjestonotautologia˛. Definicja1.5 Zdanieϕnazywamysprzecznym,jes´liπ(ϕ)=0dladowolnejwaluacji π. Zdania sprzeczne nazywane sa˛czasem anty-tautologiami. Zauwaz˙my, z˙e zdanie ψjestsprzecznewtedyitylkowtedy,gdyzdanie¬ψjesttautologia˛.Podobnie,zdanie π jest tautologia˛wtedy i tylko wtedy, gdy zdanie ¬ψ jest sprzeczne. Najprostszym przykładem zdania sprzecznego jest zdanie ⊥. Innym prostym przykładem zdania sprzecznegojestp ∧¬p . 0 0 Definicja1.6 Zdanie ϕ nazywamy spełnialnym, jes´li istnieje waluacja π taka, z˙e π(ϕ)=1.