Előadások - Matematikai logika és algoritmusok elmélete - n1.doc fájl. A matematikai logika és az algoritmuselmélet problémája

1.3 A fejlett matematikai logika története

Bevezetés

A matematikai logika és az algoritmuselmélet problémája

A matematikai logika és az algoritmusok elméletének matematikai eredményei

A modern civilizáció és az MLiTA szerepe

A történelem mérföldkövei

Szervezeti megjegyzések

A matematika felépítése. Halmazelmélet

Matematikai tevékenységkutató program - Hilbert

Általános ötlet

A Hilbert Program eredményei

A halmazelmélet nyelve és axiómái.én. Példák

Könnyű beküldeni jó munkáját a tudásbázisba. Használja az alábbi űrlapot

Hasonló dokumentumok

Logikai szimbólumok és jelentésük (szemantika)

Példák halmazok létezésének axiómáira

A könyvet a szerzők által a Moszkvai Állami Egyetem Mechanikai és Matematikai Karának junior hallgatói számára tartott előadások és szemináriumok anyagai alapján írták. Szó esik a matematikai logika alapfogalmairól (állítási logika, elsőrendű nyelvek, kifejezhetőség, propozíciószámítás, eldönthető elméletek, teljességi tétel, modellelmélet alapelvei). Az előadást matematikaiskolák diákjainak, matematikus hallgatóknak és a matematikai logika iránt érdeklődőknek szánjuk. A könyv körülbelül 200 különböző nehézségű feladatot tartalmaz.

Az állítások logikája.
Kijelentések és műveletek
„Ha az n szám racionális, akkor n algebrai szám. De ez nem algebrai. Ez azt jelenti, hogy p nem racionális." Nem kell tudnunk, hogy mi az n szám, mely számokat nevezzük racionálisnak és melyeket algebrainak ahhoz, hogy felismerjük, ez az érvelés helyes abban az értelemben, hogy a következtetés valójában a két kimondott premisszákból következik. Ez a fajta helyzet - amikor egy bizonyos állítás igaz, függetlenül a benne foglalt állítások jelentésétől - a propozicionális logika tárgyát képezi.

Ez a kezdet (különös tekintettel arra, hogy a logika szak a Filozófia Kar programjának része volt, ahol „dialektikus logikát” is tanultak) riasztó, de valójában megfontolásaink teljesen precíz matematikai jellegűek lesznek, bár kezdjük azzal, hogy informális motivációk.

Tartalomjegyzék
Előszó
1. Állítási logika
1.1. Kijelentések és műveletek
1.2. Komplett szalagrendszerek
1.3. Funkcionális elemek sémái
2. Állításszámítás
2.1. Propozíciós kalkulus (PC)
2.2. A teljességi tétel második bizonyítása
2.3. Ellenpélda keresése és szekvenciális számítás
2.4. Intuicionista propozicionális logika
3. Elsőrendű nyelvek
3.1. Képletek és értelmezések
3.2. Az igazság meghatározása
3.3. Kifejezhető predikátumok
3.4. Kifejezhetőség az aritmetikában
3.5. Kimondhatatlan predikátumok: automorfizmusok
3.6. A kvantorok kiiktatása
3.7. Presburger Aritmetika
3.8. Tarski-Seidenberg tétel
3.9. Elemi ekvivalencia
3.10. Ehrenfeucht játéka
3.11. Teljesítménycsökkentés
4. Predikátumszámítás
4.1. Általánosan érvényes képletek
4.2. Axiómák és következtetési szabályok
4.3. A predikátumszámítás helyessége
4.4. Következtetések predikátumszámításban
4.5. A predikátumszámítás teljessége
4.6. Változók átnevezése
4.7. Előtag normál forma
4.8. Herbrand tétele
4.9. Skolemov függvények
5. Elméletek és modellek
5.1. Az egyenlőség axiómái
5.2. Teljesítménynövelés
5.3. Komplett elméletek
5.4. Hiányos és eldönthetetlen elméletek
5.5. Diagramok és bővítmények
5.6. Ultraszűrők és kompaktság
5.7. Nem szabványos elemzés
Irodalom
Tárgymutató
Névmutató.

Töltse le ingyenesen az e-könyvet kényelmes formátumban, nézze meg és olvassa el:
- fileskachat.com, gyors és ingyenes letöltés.

Letöltés pdf
Az alábbiakban megvásárolhatja ezt a könyvet a legjobb áron, kedvezménnyel, kiszállítással Oroszország egész területén. Vásárolja meg ezt a könyvet

Töltse le az Előadások a matematikai logikáról és az algoritmusok elméletéről című könyvet, 2. rész, Nyelvek és számítások, Vereshchagin N.K., Shen A., 2012 - pdf - letéti fájlok.

Matematikai logika és algoritmusok elmélete – Előadások kurzusa
Bevezetés.

Cél.

Ez a kurzus olyan ismeretek és készségek fejlesztését szolgálja, amelyek a számítástechnika területén felmerülő problémák felállításához és megoldásához szükséges elméleti alapot képeznek, a számítási struktúrák, algoritmusok és információfeldolgozó programok létrehozása során felmerülő korlátok helyes megértéséhez.

A diszkrét matematika kurzus új részei, bár oktatási programok és előadássorozatok formájában valósulnak meg, még nem léteznek monográfiák formájában, legalábbis orosz nyelven, mivel a műszaki egyetemek diszkrét matematika kurzusa olyan régi alkalmazott problémákra összpontosít, amelyek mérnököknek kellett megoldaniuk. A matematikai logikában különösen a logikai áramkörök minimalizálása volt az, ami mára elvesztette jelentőségét.

Érdekes megjegyezni, hogy a logikai áramkörök szintézisének elmélete, amely egy szinte teljes „biológiai cikluson” ment keresztül a kutatók egy generációjának szeme láttára, nagyon tanulságos példája annak, hogy a műszaki tudományok olyan ágai, amelyek rosszul kapcsolódnak az alapokhoz. a tudomány nagyon érzékeny az elavulásra. Alig 10 évvel ezelőtt minden műszaki folyóirat tele volt a logikai áramkörök minimalizálásáról és szintéziséről szóló cikkekkel. A tudósok által kidolgozott minimalizálási módszerek többsége mára feledésbe merült, és a gyakorlatban nincs rájuk kereslet. És azok az ötletek, amelyeket akkoriban tisztán elméletinek tekintettek, gyakorlati alkalmazásra találtak a modern technikában. Például a fuzzy logika, a Petri-hálók és az algoritmuselmélet kiállta az idő próbáját, és széles körben használják a kibernetika és programozás különböző területein, mint például a rendszerprogramozás, a számítási komplexitás és a mesterséges intelligencia.

Az algoritmusok elmélete pedig a diszkrét matematika központi részévé vált. A legtöbb orosz nyelvű monográfiától eltérően azonban az előadások során ezek a kérdések gyakorlati, mérnöki problémák megoldásának eszközeként kerülnek bemutatásra.

Mint ismeretes, minden évtized után gyökeresen megváltoznak a számítógépek hardverelemei, az operációs rendszerek, a hozzáférési eszközök és maguk a programok. A mögöttes struktúrák és algoritmusok azonban sokkal hosszabb ideig változatlanok maradnak. Ezeket az alapokat évezredekkel ezelőtt kezdték lerakni, amikor kidolgozták a formális logikát és kidolgozták az első algoritmusokat.

A matematikai logika és az algoritmusok elmélete hagyományosan a fundamentális tudományokhoz tartozik, és úgy tartják, hogy kevés kapcsolata van a gyakorlattal, és nehezen érthető. Valóban, amikor J. Boole megalkotta a Boole-algebra matematikai apparátusát, az sokáig nem talált gyakorlati alkalmazásra, de a 20. században ez a matematikai apparátus tette lehetővé az összes számítógép-alkatrész tervezését. Következésképpen ezen előítéletek közül az elsőt sikeresen cáfolja a számítástechnika fejlődése.

Ami a diszciplína megértésének nehézségével kapcsolatos előítéletet illeti, az nagyrészt abból a tényből fakad, hogy a matematikai logikáról és az algoritmusok elméletéről szóló könyveket matematikusok írtak matematikusok számára.

Most, amikor a számítástechnika képességei sokszorosára nőttek, és sokkal több a személyi számítógép, mint ahány ember tudja, hogyan tudja azokat hatékonyan használni, megérteni, mit lehet és mit nem lehet megtenni a modern számítástechnika segítségével. kivételes fontosságú.

Az általános algoritmuselmélet mutatta meg, hogy vannak olyan problémák, amelyek nem megoldhatók, bármilyen erős is a számítási teljesítmény, és ennek gyorsan fejlődő ága - a számítási komplexitás elmélete - fokozatosan elvezet annak megértéséhez, hogy vannak megoldható problémák. de objektíve összetettek, és összetettségük némileg abszolút értelemben is kiderülhet, i.e. gyakorlatilag elérhetetlen a modern számítógépek számára.

Ez a tanfolyam a következő célokat tűzte ki:

1. Mutassa be az összes vizsgált kérdést a lehető legegyszerűbben, de ne egyszerűbben, mint egy magasan kvalifikált szakembertől elvárható.

2. Az információs rendszerek tervezésének és elemzésének gyakorlati problémái jelentik a kiindulópontot, a formális apparátus pedig eszköze e problémák szisztematikus megoldásának. Mély meggyőződésünk, hogy a tanuló nem egy edény, amelyet meg kell tölteni, hanem egy fáklya, amelyet meg kell gyújtani.

3. A kurzus minden része önellenőrző kérdéseket tartalmaz. A tanfolyam elvégzéséhez a hallgatónak válaszolnia kell ezekre a kérdésekre.

A kurzus elsajátítása eredményeként a hallgató a vonatkozó elméleti részek világos megértése alapján képes legyen:

Valósítsa meg az információ logikai transzformációjának legegyszerűbb típusát a logikai függvények tetszőleges bázisán;

Azonosítsa a logikai struktúrát a természetes nyelvű evidenciaális érvelésben, alkosson formális bizonyítási sémákat és ellenőrizze azok helyességét.

1.2 Logikai reprezentációk
Logikai reprezentációk - a vizsgált rendszer, folyamat, jelenség leírása halmaz formájában összetett állítások alkotják egyszerű (elemi) állításokÉs logikai összeköttetések közöttük. A logikai reprezentációkat és komponenseiket bizonyos tulajdonságok és a rajtuk megengedett transzformációk halmaza (műveletek, következtetési szabályok stb.) jellemzi, megvalósítva a formális (matematikai) által kidolgozottakat. A logikában a helyes érvelési módszerek a logika törvényei.

Az állítások formális bemutatásának módszereit (szabályait), a meglévő állításokból logikailag helyes transzformációkkal új állítások felépítését, valamint az állítások igazságának vagy hamisságának megállapításának módszereit (módszereit) tanulmányozzuk matematikai logika. A modern matematikai logika két fő részből áll: kijelentések logikájaés lefedve azt predikátum logika(1.1. ábra), amelynek felépítéséhez két megközelítés (nyelv) létezik, amelyek a formális logika két változatát alkotják: logikai algebraÉs logikai számítás. A formális logika ezen nyelveinek alapfogalmai között egy az egyhez megfelelés van. Izomorfizmusukat végső soron a mögöttes megengedhető transzformációk egysége biztosítja.

Rizs. 1.1
A hagyományos logikai ágak fő tárgyai az állítások.

Nyilatkozat - kijelentő mondat (nyilatkozat, ítélet), o amiről van értelme azt mondani, hogy az igaz vagy hamis.Állítások formájában fogalmazódik meg minden tudományos ismeret (fizika, kémia, biológia stb. törvényei és jelenségei, matematikai tételek stb.), a mindennapi élet eseményei, a közgazdaságtanban és a gazdálkodási folyamatokban felmerülő helyzetek. A felszólító és kérdő mondatok nem állítások.

Példák az állításokra: „Kétszer kettő az négy”, „A 21. században élünk”, „A rubel az orosz fizetőeszköz”, „Aljosa Oleg testvére”, „Az egyesülés, a metszés és az összeadás műveletei logikai műveletek halmazokon ”, „Az ember halandó” , „A kifejezések helyeinek átrendezése nem változtat az összegen”, „Ma hétfő van”, „Ha esik az eső, vigyünk egy esernyőt.”

Ahhoz, hogy ezekkel a mondatokkal állításként tovább operálhassunk, mindegyikről tudnunk kell, hogy igaz vagy hamis, i.e. ismerje meg őket igazságérték (igazság). Figyeljük meg, hogy bizonyos esetekben egy állítás igaza vagy hamissága attól függ, hogy milyen konkrét valóságot (rendszert, folyamatot, jelenséget) próbálunk leírni a segítségével. Ebben az esetben az adott állítást egy adott értelmezésben (kontextusban) igaznak (vagy hamisnak) mondjuk. Feltételezzük továbbá, hogy a kontextus adott, és az állításnak van bizonyos igazságértéke.

A logika mint tudomány a 4. században alakult ki. I.E Arisztotelész görög tudós alkotta meg.

A „logika” szó a görög „logos” szóból származik, amely egyrészt „szót” vagy „kifejezést”, másrészt gondolkodást jelent. Ozhegov S.I. magyarázó szótárában. Azt mondják: "A logika a gondolkodás törvényeinek és formáinak tudománya." A 17. században Leibniz német tudós egy új tudomány létrehozását tervezte, amely „az igazság kiszámításának művészete” lenne. . Ebben a logikában Leibniz szerint minden állításnak megfelelő szimbóluma lenne, az érvelésnek pedig számítási formája lenne. Leibniznek ez az ötlete, mivel nem találkozott kortársai megértésével, nem terjedt el és nem fejlesztették ki, és ragyogó találgatás maradt.

Csak a 19. század közepén. George Boole ír matematikus testesítette meg Leibniz gondolatát 1854-ben megírta "A gondolkodás törvényeinek vizsgálata" című munkáját, amely lefektette a logikai algebra alapjait, amelyben a hétköznapi algebra törvényeihez hasonló törvények érvényesek, de a betűk igen. nem számokat jelöl, hanem állításokat. A Boole-algebra nyelvén le lehet írni az érvelést és „kiszámolni” annak eredményeit. Ez azonban nem terjed ki minden érvelésre, csak annak egy bizonyos típusára. , Ezért a Boole-algebrát propozíciószámításnak tekintjük.

A Boole-féle logikai algebra egy új tudomány – a matematikai logika – embriója volt. Ezzel szemben Arisztotelész logikáját hagyományos formális logikának nevezik. A „matematikai logika” elnevezés e tudomány két jellemzőjét tükrözi: egyrészt a matematikai logika olyan logika, amely a matematika nyelvét és módszereit használja; másodsorban a matematikai logikát a matematika igényei keltik életre.

A 19. század végén. A Georg Cantor által megalkotott halmazelmélet megbízható alapnak tűnt minden matematika számára, beleértve a matematikai logikát is, legalábbis a propozíciószámítás (Boole algebra) számára, mert Kiderült, hogy a Cantor-algebra (halmazelmélet) izomorf a Boole-algebrával.

Maga a matematikai logika a matematika olyan ágává vált, amely eleinte nagyon elvontnak tűnt, és végtelenül távol áll a gyakorlati alkalmazásoktól. Ez a terület azonban nem maradt sokáig a „tiszta” matematikusok területe. A 20. század elején. (1910) orosz tudós Ehrenfest P.S. rámutatott a Boole-algebra apparátusának a telefonkommunikációban történő alkalmazásának lehetőségére a kapcsolóáramkörök leírására. 1938-1940-ben szinte egyszerre jelentek meg V. I. Shestakov szovjet tudós, Shannon amerikai tudós, valamint Nakasima és Hakazawa japán tudósok a matematikai logika digitális technológiában való alkalmazásáról. Az első monográfiát, amely a matematikai logika felhasználásával foglalkozik a digitális berendezések tervezésében, a Szovjetunióban jelentette meg M. A. Gavrilov szovjet tudós. 1950-ben. A matematikai logika szerepe a modern mikroprocesszoros technológia fejlődésében rendkívül fontos: számítógépes hardver tervezésében, minden programozási nyelv fejlesztésében és diszkrét automatizálási eszközök tervezésében használják.

A különböző országok tudósai nagymértékben hozzájárultak a matematikai logika fejlesztéséhez: a Kazany Egyetem professzora, Poretsky P.S., de-Morgan, Peirce, Turing, Kolmogorov A.N., Heidel K. és mások.

1.4 Kérdések az önellenőrzéshez.

1. Fogalmazza meg a tanfolyam céljait!

Diákok, végzős hallgatók, fiatal tudósok, akik a tudásbázist tanulmányaikban és munkájukban használják, nagyon hálásak lesznek Önnek.

A műnek még nincs HTML verziója.
Az alábbi linkre kattintva letöltheti a mű archívumát.

A matematikai logika alapdefiníciói, a logikai és ekvivalens függvények. A Boole-algebra általános fogalmai. Zhegalkin algebra: állítások és predikátumok. A formális elmélet definíciója. Az algoritmusok elméletének elemei, rekurzív függvények, Turing-gép.

előadások tanfolyama, hozzáadva 2011.08.08

A gondolkodás alapvető formái: fogalmak, ítéletek, következtetések. George Boole esszéje, amely részletesen feltárta a logikai algebrát. Egy állítás igazságértéke (azaz igazság vagy hamisság). Az inverzió (negáció) és a konjunkció logikai műveletei.

bemutató, hozzáadva 2016.12.14

Halmazok grafikus értelmezése és a rajtuk végzett műveletek. Matematikai logika, Boole-algebra. Tökéletes konjunktív normál forma. Egyenértékű képletek és bizonyításuk. A Boole-függvények rendszerének teljessége. Predikátum logika, gráfelmélet.

előadás, hozzáadva 2009.12.01

A Boole-algebra megjelenésének története, a propozíciós számítási rendszer kialakulása. Módszerek összetett logikai állítások igazságának vagy hamisságának megállapítására algebrai módszerekkel. Diszjunkció, konjunkció és tagadás, igazságtáblák.

bemutató, hozzáadva 2014.02.22

Négyzetmátrixok és determinánsok. Koordináta lineáris tér. Lineáris egyenletrendszer tanulmányozása. Mátrixok algebrája: összeadásuk és szorzásuk. Komplex számok geometriai ábrázolása és trigonometrikus formájuk. Laplace tétele és alapja.

képzési kézikönyv, hozzáadva: 2009.02.03

A pozitív (természetes) számok elméletének alapfogalma. Gyorsírás fejlesztése aritmetikai műveletekhez. Az oszthatóság szimbolikus nyelve. Összehasonlítások tulajdonságai és algebra. Összehasonlítás felvetése a hatalommal. Újra négyzetesítés. Fermat kis tétele.

bemutató, hozzáadva 2014.06.04

Digitális információfeldolgozó rendszerek. A Boole algebra fogalma. A logikai műveletek megnevezései: diszjunkció, konjunkció, inverzió, implikáció, ekvivalencia. A Boole algebra törvényei és azonosságai. A számítógépek logikai alapjai. Szerkezeti képletek átalakítása.

bemutató, hozzáadva 2014.10.11

Matematikai logika és algoritmusok elmélete

Előadó: A. L. Semenov

1. előadás

Bevezetés 1

A matematikai logika és az algoritmuselmélet problémája 1

A matematikai logika és az algoritmuselmélet matematikai eredményei 2

A modern civilizáció és az MLiTA 2 szerepe

A matematika felépítése. Halmazelmélet 5

Matematikai tevékenységkutatási program - Hilbert 9

Általános ötlet 9

A Hilbert Program eredményei 12

A halmazelmélet nyelve és axiómái. I. Példák 12

Logikai szimbólumok és jelentésük (szemantika) 12

Példák axiómákra a 13. halmazok létezésére

A matematikai logika és az algoritmusok elmélete által megoldott probléma matematikai definíciók és tételek rendszerének felépítése, amely lehetővé teszi a következő típusú emberi tevékenységek matematikai leírását és tanulmányozását:

Tételek bizonyítása és matematikai fogalmak meghatározása
A matematikai objektumok közötti kapcsolatok leírása
Következmények levonása kísérletileg megállapított állításokból, hipotézisekből stb.
Meghatározott tulajdonságú és funkciójú eszközök (mechanikus, elektronikus stb.) tervezése.
Formális utasítások létrehozása és megvalósítása (algoritmusok és programok leírása, alkalmazása)
Megfelelés megállapítása a kívánt eredmény leírása és az eredmény elérésére tervezett algoritmus között (a helyesség igazolása)

A matematikai logika és az algoritmusok elmélete (matematikai, egzakt) kritériumokat ad a felsorolt tevékenységek helyességére.

A kutatás elvégzésével a következőkkel kapcsolatos eredményeket kapunk:

Egy adott nyelven leírható halmazok és relációk
Bizonyítható képletek halmazai
Valódi képletek halmazai (a 2. bekezdéshez képest alapvető különbség van)
Matematikai struktúrák halmazai, amelyekben egy adott halmaz képletei igazak
Az algoritmusok által kiszámított függvényosztályok
Egy olyan algoritmus megléte, amely meghatározza a képletek igazságát vagy bizonyíthatóságát
Számítási komplexitás
Az objektumok összetettsége

stb.

Az emberiség fejlődésének jelentős előrehaladása az anyagi tárgyak feldolgozására, az energia fogadására és továbbítására (ezek a gépek által használt), szállítóeszközök, világítás stb.

Évszázadok óta az volt az ötlet, hogy olyan gépeket hozzanak létre, amelyek nem anyaggal és energiával, hanem információs objektumokkal dolgoznak. Sőt, ilyen gépeket hoztak létre, sőt sikeresen működtek is, például egy aritmetikai műveletek elvégzését lehetővé tevő gépet - egy összeadógépet (B. Pascal).

A 20. század első felében általános leírást adtak az ember általi formális információfeldolgozás lehetséges módszereiről. A 20. század közepére felfedezték azokat a fizikai elveket, amelyek lehetővé tették olyan eszközök létrehozását, amelyek sok információt képesek tárolni és nagyon gyorsan feldolgozni. Univerzális eszközöket hoztak létre - olyan számítógépeket, amelyek mindent megtehetnek, amit egy személy formálisan megtehet, de sokkal gyorsabban, mint egy személy.

Általánosságban véve azt mondhatjuk, hogy a matematikai logika adja az elméleti matematika, az algoritmusok elmélete pedig a számítási gyakorlat (számítógép-használat) alapjait. A részletesebb vizsgálat azonban azt mutatja, hogy a matematikai logika számos vívmánya alkalmazásra talált az információs technológiák fejlesztésében és alkalmazásában, és az algoritmikus megfontolások a tiszta matematika különböző szakaszaiban is jelentősek.

A matematikai bizonyításokról és számításokról alkotott modern eszmék kialakulásának fontos momentumai a német matematikusok eredményei a 19. század végén és a 20. század elején.

Különösen fontos volt David Hilbert (1862. 01. 23. - 1943. 01. 14.) beszéde a II. Nemzetközi Matematikus Kongresszuson (Párizs, 1900). Ott megfogalmazott 23 ún. Hilbert problémái– az akkori matematika és a XX. századi matematika fejlődése szempontjából a legfontosabb. Hilbert egyes problémái egy adott matematikai állítás igazságának meghatározására vonatkoztak, mások inkább valamilyen kutatási program végrehajtására irányuló javaslatnak nevezhetők.

A Hilbert-listán szereplő I., II., X. feladatok a matematikai logika és az algoritmusok elméletéhez kapcsolódnak.

Az ezredforduló hét matematikai problémája közül az első is a mi témánkhoz kapcsolódik (nem szerepelt a Hilbert-feladatok között).

A kurzus a matematikai logika és algoritmuselmélet fentebb említett problémáit és azok modern szemléletét tárgyalja.

A kurzus készítői úgy vélik, hogy a matematika tanulásának és a matematikussá válásnak az a legjobb módja, ha saját maga végzi a matematikát. Matematikusok alatt itt mindenkit értünk, akinek szakmai tevékenységének (sokak számára egész életének) lényeges része a matematikai objektumokkal végzett munka matematikai tevékenységi módszerekkel. Az információtechnológiai tevékenység jelentős része például így épül fel. A „matematika” alatt a feladatok megoldását értjük közben először is, nem az a fajta, amit a legtöbbet az iskolában, vagy az egyetem első évében a kalkulus tanfolyamon oldanak meg. Olyan feladatokra gondolunk, ahol valami újat kell kitalálnia. Természetesen a matematika egy új területének elsajátítása során sok ilyen feladatnak egyszerűnek és régen megoldottnak kell lennie, de alapvetően nem különböznek azoktól a problémáktól, amelyeket egy profi matematikusnak és programozónak kell megoldania.

Az olyan típusú problémák, amelyekről most beszélünk, mind előadásokban, mind gyakorlati feladatokban megfogalmazódnak. Nem minden megfogalmazott feladat lesz teljesen egyszerű. Sőt: egy részüket matematikából egészen mostanában megoldották, lesz olyan is, ami még nincs megoldva, és olyan is, aminek egyáltalán nincs megoldása (de hasznos megoldani).

Javasoljuk, hogy a tanfolyam során vegyen részt problémamegoldásban, és beszélje meg azokat oktatójával (és természetesen egymással). Ez:

Segít jobban megérteni az előadások tartalmát és a teljes matematikai területet, amelyhez a kurzus kapcsolódik
Jobb, ha felkészülsz a vizsgára, és részben „átmened” (a kurzus során felmerülő problémák megoldását a vizsgán „jóváírják”, erről a tanáraid mesélnek)
Próbálja ki magát a matematika egy ígéretes területén, és esetleg válassza az egyetemi szakiránynak, ami hasznos lehet az egyetem utáni munkájához.

Egy másik hely, ahol problémákat oldanak meg és megoldásaikat megvitatják, a Matematikai logikával és számítástechnikával foglalkozó szeminárium kisdiákoknak. Ott az egyszerű feladatokkal együtt, amelyek lehetővé teszik az ügy lényegének megértését, azonnal felajánlják mind az összetett, mind a még meg nem oldott feladatokat.

A következő előadás anyagai felkerülnek az internetre a honlapra http://lpcs.math.msu.su/vml2013/

Rajtuk kívül a könyvekből ismerkedhetsz meg a tananyaggal:

N.K. Vereshchagin, A. Shen, Előadások a matematikai logikáról és az algoritmusok elméletéről, szerk. MCCME (mccme.ru)
I. A. Lavrov, L. L. Maksimova, Problémák a halmazelméletben, a matematikai logikában és az algoritmusok elméletében,

amelyek az interneten is elérhetők.

Végül az utolsó dolog. A matematikai logika és az algoritmuselmélet egyik alkalmazott eredménye a matematikai tevékenység különböző összetevőinek automatizálása. IN különösen, bizonyos típusú matematikai bizonyítások ellenőrzése automatizálható. Az ilyen automatizálás területe természetesen folyamatosan bővül maguknak az automatizálási algoritmusoknak a fejlesztése, a matematikusok jobb megértése ezen algoritmusok alkalmazásának, a tapasztalatok felhalmozódása és a számítási képességek növekedése miatt. A bizonyítékok ellenőrzésének automatizálására ma a legnépszerűbb és leghatékonyabb számítási keretrendszer a Coq. Tanszékünk workshopot tart a Coq-ról, ahol megtanulhatod, hogyan kell használni ezt a környezetet, elképzelheted a képességeit és korlátait.

A matematika modern szerkezete, különösen az egyetemi oktatás módja, halmazelméleten alapul. Most felidézzük ennek az elméletnek néhány alapfogalmát.

A göndör zárójeleket gyakran használják a készletek meghatározására. Belülük elhelyezhetjük az adott halmaz összes elemét: (2, 14, 5.4), vagy speciális módon írhatjuk le: (x|x egy valós szám és sin(x)>0).

A halmazműveletekhez a következő jelölést használjuk: egy elemnek a halmazban való tagsága ∊, halmazok felvétele ⊂, unió ∪, metszéspont ∩, különbség \.

Legyen két tárgyunk x,y. Rendezett pár x; y> olyan objektumot hívnak meg, amelyhez egyedileg visszaállítják x, y, más szóval: x; y> = x′; y′> → ( x = x′ y = y′).

A munka x X y két szett x És y az összes rendezett pár halmaza u; v>, hol u ∊ x És v ∊ y.

Hasonlóképpen rendelt n-ki tárgyak és n fokozat x n készletek x. Ebben meg lehet egyezni x 1 van x.

A halmazok közötti kapcsolat x, y termékük bármely részhalmazát nevezzük x X y.

n-helyi kapcsolat a forgatáson x bármely részhalmazt hívjuk n-a halmaznak.

Hozzáállás f között x És y függvényének nevezzük x V y, ha a reláció bármely két eleme első összetevőinek egybeeséséből f az utóbbiak egybeesése következik.

Egy függvény tartománya az első összetevőinek halmaza.

Ha egy függvény tartománya innen származik x V y egybeesik x, akkor a függvény megjelenik x V yés írj f : x → y. Sok minden funkció megjelenik x V y, által jelölve y x .

Funkció f : x → y közötti bijekciónak nevezzük x És y, vagy bijekció -ból x V y, vagy izomorfizmus x És y, ha az elemek második összetevőinek egybeeséséből f ebből következik, hogy az első elemek egybeesnek, és ezen felül a második elemek f alkotják a teljes készletet y. Az izomorf halmazokat ekvivalens halmazoknak is nevezik.

Egy halmazt megszámlálhatónak nevezünk, ha ekvivalens a természetes sorozattal.

Feladat. Bizonyítsuk be, hogy egy természetes sorozat minden részhalmaza egyenértékű vagy a kezdeti szegmensével (amely megegyezik egyes elemeivel), vagy a teljes természetes sorozattal.

Az utolsó feladatban megfogalmazott elemi megfigyelés – hogy egy rész izomorf lehet az egészhez képest – valószínűleg triviálisnak tűnik a másodéves hallgatók számára. De ez volt a halmazelmélet egyik első felfedezése.

A véges halmazok méret szerint összehasonlíthatók. Ha az egyik izomorf egy másik részhalmazával, akkor kevesebb eleme van. Ez nem igaz a végtelen halmazok esetében. Ezt a helyzetet Galileo Galilei írta le a következő párbeszédben, amelyet rövidítéssel mutatunk be:

Beszélgetések Ésmatematikaibizonyíték, két újjal kapcsolatbantudomány ágai,összefüggő TomechanikaÉshelyi mozgalom

signora Galileo Galilea Linceo, filozófus és első matematikus Őfensége Toszkána nagyhercege

Salviati. ...az összes szám – négyzetek és nem négyzetek – száma együtt nagyobb, mint a négyzetek önmagukban; nem igaz?

Simplicio. Ez ellen nem tudok vitatkozni.

Salviati. Annyi négyzet van, ahány gyök, mivel minden négyzetnek megvan a saját gyöke és minden gyökérnek saját négyzete; egyetlen négyzetnek sem lehet több gyöke, és egyetlen gyökérnek sem lehet több négyzeténél.

Sagredo. Mit kell tenni, hogy megtaláljuk a kiutat? egy ilyen helyzet ?

Salviati. Nem látok más megoldási lehetőséget, mint annak beismerése, hogy az egyenlőség tulajdonságai, valamint a nagyobb és kisebb nagyságrendek nem léteznek ott, ahol a végtelennel van dolgunk, és csak véges mennyiségekre alkalmazhatók. Ezért amikor Signor Simplicio egyenlőtlen sorokat ajánl fel, és megkérdezi, hogyan lehetséges, hogy a nagyobbik nem tartalmaz több pontot, mint a kisebb, azt válaszolom neki, hogy nincs több, nincs kevesebb és nem ugyanannyi, de mindegyikben végtelen szám.

Azonban még a végtelen halmazok között is van bizonyos sorrend, amint azt a következő tétel is mutatja, amelyet Cantor is bizonyítás nélkül hirdetett meg, és hamarosan más német matematikusok is bebizonyították.

Cantor–Bernstein tétel. Legyen bijekció a halmazok között Aés a halmaz egy részhalmaza B, valamint egy bijekció a halmazok között Bés a halmaz egy részhalmaza A. Aztán a készletek AÉs B- erőben egyenlő.

Feladat. Bizonyítsuk be a Cantor–Bernstein-tételt!

Feladat. Összehasonlítható-e bármilyen halmaz a kardinalitás szempontjából, vagyis igaz-e, hogy bármelyikre AÉs B, vagy A ugyanolyan erős részhalmaz B, vagy B ugyanolyan erős részhalmaz A?

A funkciók közül kiemeljük tulajdonságait– függvények, amelyek csak a 0 és 1 értéket veszik fel. Minden tulajdonság megad egy relációt – olyan elemek halmazát, amelyeken az értéke 1. Bármely függvény f : x → B-t hívják jellegzetes(on x). Vegyük észre, hogy jelölésünkben és konvencióinknál B=(0,1)=2. Így az összes jellemző függvény halmaza be x megkapja a B jelölést x vagy 2 x .

Feladat. Szerkesszünk izomorfizmust a karakterisztikus függvények halmaza között xés a halmaz számos részhalmaza x.

Feladat. Bizonyítsuk be, hogy bármely halmaz részhalmaza nem izomorf vele.

Megoldási ötlet [Cantor Diagonal]. Legyen izomorfizmus G : x → 2 x létezik. Tekintsük az egyes elemeket y sokunk közül x megfelelő részhalmazát G(y). Tudunk-e az elemektől x gyűjtsünk egy részhalmazt C, ami eltérne a készlettől G(y) "elemen y» ? Illetve mi ugyanaz, hogyan kell egy jellemző függvényt megszerkeszteni f C , ami eltérne a halmaz jellemző funkciójától G (y) "a ponton y» mindenesetre y?

Ha x természetes számok halmaza, akkor a bizonyítás egyértelmű grafikus formát ölt. Felhívjuk a számot y, ami a karakterisztikus függvénybe kerül f, funkciószám f.

………

Ebben a táblázatban a szám sorban n a karakterisztikus függvényt a számmal írjuk ki n. A táblázatnak nincs függvénye, amelyet az 1-ről 0-ra és 0-ról 1-re változtatva kapott átlójából (negációs művelet).

Feladat. Bizonyítsuk be, hogy a valós számok halmaza ekvivalens a természetes sorozat részhalmazainak halmazával.

David Hilbert birtokolja a matematikát, mint a matematikailag leírt tevékenység területét, a matematikai tevékenység kutatásának fontosságát a matematika eszközeivel, valamint egy ilyen kutatási program bemutatását - a Hilbert-programot.

Hilbert matematikatanulmányi programjai a következőképpen ábrázolhatók:

A matematika rendszerként is ábrázolható
- axiómák - olyan állítások, amelyeket igaznak fogadunk el és
- bizonyítási szabályok – új állítások beszerzése.
A matematikai tevékenység gyakorlatának meg kell győznie bennünket arról, hogy a választott rendszer lehetővé teszi az összes szükséges bizonyítás megalkotását. IN ideális esetben ez megtörténhet hogy ezzel a rendszerrel bármely matematikai állítás bizonyítható vagy cáfolható. (Ezt a tulajdonságot ún teljesség.)
Egyes matematikai bizonyítások „különösen robusztusak és meggyőzőek”. Ilyenek például az aritmetikai számítások. Csak ezeket használva megbizonyosodhat arról, hogy a matematikához választott rendszer nem enged ellentmondásokat. (Ez a tulajdonság az ún következetesség.) Sőt, kiderülhet, hogy a matematika teljessége egyszerű, érthető és meggyőző érveléssel is bizonyítható.

A teljesség tulajdonság hasznossága egyértelmű. Általában, amikor egy matematikai állítást próbálunk bizonyítani, egyidejűleg annak cáfolatát is keressük. Biztos szeretnék lenni abban, hogy egy ilyen tevékenység végül eredményre vezet, és ez „csak” képességeink és időnk kérdése. Hilbert úgy vélte: „Minden matematikai probléma megoldhatóságáról való meggyőződés nagy segítség a munkánkban; folyamatos felszólítást hallunk magunkban: itt a probléma, keress megoldást. Megtalálhatja a tiszta gondolkodáson keresztül; mert a matematikában nincs Ignorabimus!”

Vegye figyelembe, hogy a konzisztencia tulajdonsága sokkal fontosabb. A priori elképzelhető egy olyan tudományos elmélet, amelyben az ellentmondás valahol a periférián található, és néhány lényegtelen kérdéshez kapcsolódik. Mindazonáltal minden alapvető matematikai bizonyítási rendszer felépítése olyan, hogy egy ellentmondás bizonyíthatósága (például az a tény, hogy néhány nagyon nagy szám szorzata egy harmadik, egy másik pedig egy negyedik) azonnal a bizonyíthatósághoz vezet. bármely matematikai állításból. Az ellentmondás nem „lokalizálható”.

A Hilbert Program céljainak elérése felé tett első lépések már a megfogalmazás előtt megtörténtek. Ráadásul a Program logikusan következett belőlük. Ezek a lépések.

Bizonyíték. Logikák. A 19. század végén világossá vált, hogyan kell formalizálni az érvelés rendszerét. Ez a formalizálás Gottlob Frege (1848. 11. 08. - 1925. 07. 26.) munkáiban fejeződött be.

Halmazelmélet. A matematika másik vívmánya a 19. század végén az volt, hogy megértette, hogy minden matematika egységesen bemutatható halmazokban (ahogyan a modern matematika kurzusokban is megtörténik, és fentebb is idéztük). Ez Georg munkáiban készült Kantor (1845.03.3 - 1918.01.6).

Így nem maradt más hátra, mint megfelelő axiómarendszert választani, és a továbbiakban a következetesség és teljesség bizonyításának útját követni. Az ilyen bizonyítékok egyszerű és megbízható eszközökkel történő megszerzésének reménye a következőkhöz kapcsolódott. Az axiómák és a bizonyítási szabályok használata a képletekkel való munka meglehetősen egyszerű folyamatának tűnik. Maguk a képletek egyszerű tárgyak, szimbólumok láncai. A matematika játéknak tűnik, mint például a sakk. Tegyük fel, hogy be kell bizonyítanunk, hogy a sakkban bizonyos pozíciók lehetetlenek. Ezt elvileg persze mindenféle sakkjátszmán keresztül meg lehet tenni. De elképzelhető egyszerűbb érvelés is, például azon a tényen alapszik, hogy nem adnak darabokat a mezőhöz, hogy a püspökök világos négyzetek, néha sötét négyzetek stb. Az ilyen érvelés valószínűleg nem használ valós számokat , integrálok és még bonyolultabb matematikai objektumok.

Rendszer axiómák a halmazelmélethez század első évtizedeiben épült, az első modernhez közel álló megfogalmazás Ernst Zermeloé (1871.7.27 - 1953.5.21.) és ő adta ki 1908-ban.

Mi történt később a Hilbert programmal? Ezt most röviden megfogalmazzuk, a következő tanfolyamon pedig részletesebben is kifejtjük.

Egyrészt a programot sikeresen végrehajtották:

Az axiomatikus halmazelmélet a modern matematika alapja.
A harmincas években N. Bourbaki gyűjtőálnéven matematikusok csoportja jött létre. Alkotói tevékenységének maximumát az 1950-es és 60-as években érte el. Ez a csoport következetesen és szisztematikusan mutatta be a modern matematika jelentős részét halmazelméletre épülőként.

Ugyanakkor a Program alapvetően megbukott:

A matematika nem teljes, és nem is lehet teljes.
A matematika konzisztenciáját nem csak valamilyen megbízható meggyőző eszközzel lehet megállapítani.

Ez Kurt Gödel telepítette(1906. 04. 28. – 1978. 01. 14.) az 1930-as években.

A matematikai bizonyítási rendszer (halmazelmélet) megfogalmazását a logikai nyelv leírásával kezdjük.

Logikai értékek: I (igaz), L (hamis) vagy 1, 0 szimbólumok. A két 0 és 1 szimbólum halmazát B-vel jelöljük.

Logikai műveletek:(nem, tagadás), (és, kötőszó), (vagy, diszjunkció), → (következik, implikáció), ≡ (ekvivalencia) az 1 (I) és 0 (A) szimbólumokra vonatkoznak, és alkalmazásuk eredménye: az alábbi táblázat írja le:

Kvantifikátorok, amit természetesen Ön is ismer - x (létezik x ), y (bármelyikhez y )

Érv
Funkció sz.

A halmazelmélet számos axiómája halmazok létezésére vonatkozó kijelentés, beleértve a más halmazokból képzett halmazokat is.

Ahhoz, hogy halmazokról beszélhessünk, különösen a rájuk vonatkozó axiómák megfogalmazásához, szükséges a logikai szimbólumok mellé halmazelmélethez kapcsolódó szimbólumokat is hozzáadni. Hogyan írjam le mit x – üres halmaz, vagyis olyan halmaz, amelynek nincsenek elemei? Például így:

y ( y ∊ x ) (mindenkinek y ez nem igaz y tartozik x )

Szükségünk volt egy tagsági szimbólumra ∊. Adjuk hozzá nyelvünk ábécéjéhez.

Ahhoz, hogy legyen miről beszélnünk, jó lenne legalább egy készlet létezésében biztosak lenni. Kezdjük az üressel (Ø):

x y ( y ∊ x ) [Az üres halmaz axiómája.]

Meg akarunk határozni néhány konkrét halmazt, a halmazok tulajdonságait stb. Ezekhez jelöléseket szeretnénk bevezetni.

Az üres halmazt nullának tekintjük.
Hogyan kapjuk meg a következő számot egy számból n? Adja hozzá az összes elemhez n még mindig csak n. Vagyis figyelembe vesszük a következő elemeit n az összes elemet számozza nés több n. Az összes kapott elem halmazt alkot N:
- 1 az (0)
- 2 jelentése (0,1)= (0, (0))

Feladat. Hány elem van az 5-ös számban (halmazban)? És bőséggel n?

Az így felépített természetes sorozat létezését a következő axióma garantálja. A könnyebb érthetőség érdekében részekre osztottuk, és megjegyzéseket (szögletes zárójelben) írtunk ezekhez a részekhez:

s (u (u ∊ s v (v ∊ u )) [mintsveheted a natúr sorozatotN; tartalmazni fogu - nulla]

u (u ∊ s → [ Mert mindenfélét u -tól s ]

v (v ∊ s [leszv -tóls , ]

w (w ∊ v ≡ (w ∊ u w = u ))))) [mellettu ] [ A végtelenség axiómája ]
Ezt az axiómát azonban nem csak a természetes sorozatok, hanem más halmazok is kielégíthetik

Feladat. Például milyen?

Feladat. Hogyan írhatjuk le pontosan az általunk felépített természetes sorozatokat?

A matematikai konstrukciókban halmazokon végzett műveleteket használnak. A már megkezdett utat követve olyan axiómákat kell hozzáadnunk, amelyek garantálják e műveletek eredményeinek meglétét. Íme egy másik példa:

usv(w(w ∊ v →w ∊ u) ≡ v ∊ s) [Fokozati axióma]

Feladat. Ellenőrizze, hogy az utolsó képlet értelmesen azt jelenti, hogy létezik egy adott halmaz összes részhalmaza.

Természetesen szükségünk lesz például egy halmazra, amely két adat metszéspontja stb.

Fent elkezdtük fokozatosan készleteket építeni. Világos, hogyan kell folytatni ezt az utat, például egész számok halmazát, majd racionális számokat, egész számpárok halmazaként, amelyeken valamilyen ekvivalencia-reláció, majd valós számok halmazaként stb.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete