11.1. Az algoritmus fogalma és az algoritmusok elmélete

Intuitívan az algoritmus egy olyan probléma szekvenciális megoldásának folyamata, amely diszkrét időben fordul elő úgy, hogy minden következő időpillanatban az algoritmus objektumrendszerét egy bizonyos törvény szerint megkapjuk a korábban létező objektumok rendszeréből. az előző pillanatban. Intuitív módon, mert szigorúan véve az algoritmus fogalma rokon a meghatározhatatlan halmaz fogalmával.

A GOST 19781-74 „Számítógépek. Szoftver. Kifejezések és meghatározások" algoritmus- ez egy pontos előírás, amely meghatározza a számítási folyamatot, amely a változó kezdeti adatoktól a kívánt eredményig vezet. Ebben az esetben feltételezzük az algoritmus végrehajtójának jelenlétét - egy objektumot, amely „tudja, hogyan kell végrehajtani ezeket a műveleteket”.

Az „algoritmus” szó egy 13. századi közép-ázsiai (üzbég) matematikus nevéből származik. Al Khwarizmi(Abu Abdullah Muhammad ibn Musa al Khwarizmi al Medjusi) – „Algoritmi” in Latin átírás, aki először fogalmazta meg négy aritmetikai művelet végrehajtásának szabályait (eljárását) ben decimális rendszer Leszámolás.

Amíg a számítások egyszerűek voltak, nem volt különösebb szükség algoritmusokra. Amikor felmerült az igény több lépésről lépésre történő eljárásra, akkor megjelent az algoritmusok elmélete. De ahogy a problémák még bonyolultabbá váltak, kiderült, hogy néhányukat nem lehet algoritmikusan megoldani. Ilyen például az emberi „fedélzeti számítógép” – az agy – által megoldott számos probléma. Az ilyen problémák megoldása más elveken alapul - ezeket az elveket egy új tudomány - a neuromatematika és a megfelelő technikai eszközök - a neurokomputerek használják. Ebben az esetben a tanulás, a próba és a hiba folyamatait alkalmazzák – vagyis azt, amit most csinálunk.

Egy algoritmus minőségét tulajdonságai (jellemzői) határozzák meg. Az algoritmus főbb tulajdonságai a következők:

1. Tömegjelleg. Feltételezzük, hogy az algoritmus alkalmas lehet minden ilyen típusú probléma megoldására. Például egy lineáris algebrai egyenletrendszer megoldására szolgáló algoritmusnak alkalmazhatónak kell lennie egy tetszőleges számú egyenletből álló rendszerre.

2. Hatékonyság. Ez a tulajdonság azt jelenti, hogy az algoritmusnak eredményt kell produkálnia végső szám lépéseket.

3. Bizonyosság. Az algoritmusban szereplő utasításoknak pontosnak és érthetőnek kell lenniük. Ez a jellemző biztosítja a számítási folyamat eredményének egyértelműségét megadott kezdeti adatok mellett.

4. Diszkrétség. Ez a tulajdonság azt jelenti, hogy az algoritmus által leírt folyamat és maga az algoritmus különálló elemi szakaszokra bontható, amelyek lehetőségét a felhasználó kétségtelenül végrehajthatja számítógépen.

Ma a „digitális évezredben” járunk, és úgy tűnhet, hogy az algoritmusok bármilyen feladatot képesek kezelni. Kiderült, hogy sok probléma nem oldható meg algoritmikusan. Ezek úgynevezett algoritmikusan megoldhatatlan problémák.

A feladatok algoritmikus megoldhatóságának vagy megoldhatatlanságának bizonyításához matematikailag szigorú és precíz eszközök szükségesek. A múlt század 30-as éveinek közepén kísérleteket tettek az algoritmus fogalmának formalizálására, és javasolták különféle modellek algoritmusok: rekurzív függvények; „gépek” – Turing, Post; normál Markov algoritmusok.

Ezt követően kiderült, hogy ezek és más modellek egyenértékűek abban az értelemben, hogy az általuk megoldott problémaosztályok azonosak. Ezt a tényt Church tézisének nevezik. Ez ma már általánosan elfogadott. Az algoritmus fogalmának formális meghatározása már az első számítógépek kifejlesztése előtt megteremtette az algoritmus elméletének kidolgozásának előfeltételeit. A számítástechnika fejlődése ösztönözte az algoritmusok elméletének további fejlődését. Az algoritmuselmélet a feladatok algoritmikus megoldhatóságának megállapítása mellett az algoritmusok összetettségének becslésével is foglalkozik a lépések száma (időbonyolultság) és a szükséges memória (térbonyolultság) tekintetében, valamint foglalkozik az algoritmusok bonyolultságának becslésével is. hatékony algoritmusok ebben az értelemben.

Egyes algoritmusok megvalósítása az elemi lépések végrehajtásának sebességére vonatkozó fizikai szempontból ésszerű feltételezések mellett több időt vehet igénybe, mint a modern nézet szerint az Univerzum, vagy több memóriasejt, mint a bolygót alkotó atomok. Föld.

Ezért az algoritmuselmélet másik feladata a kombinációs algoritmusok opcióinak számbavételének kiküszöbölésének problémája. Az algoritmusok összetettségének felmérése és az úgynevezett hatékony algoritmusok létrehozása az egyik legfontosabb feladatokat az algoritmusok modern elmélete.

S. N. POZDNYAKOV S. V. RYBIN

oktatóanyag

Az Orosz Föderáció Oktatási és Tudományos Minisztériuma

Szentpétervári Állami Elektrotechnikai Egyetem "LETI"

S. N. POZDNYAKOV S. V. RYBIN

MATEMATIKAI LOGIKA ÉS ALGORITMUSOK ELMÉLETE

St. Petersburg Kiadó St. Petersburg Elektrotechnikai Egyetem "LETI"

UDC 510.6 BBK V12 P47

Pozdnyakov S. N., Rybin S. V. Matematikai logikaés az algoritmusok elmélete: Tankönyv. juttatás. St. Petersburg: A Szentpétervári Elektrotechnikai Egyetem „LETI” kiadója, 2004. 64 p.

Figyelembe veszik a matematikai logika főbb gondolatait, fogalmait és módszereit, amelyek iránt a múltban megjelent új alkalmazásoknak köszönhetően nőtt az érdeklődés. utóbbi időben az információs technológiák fejlődésével kapcsolatban.

Mindkét tanuló számára használható napi forma edzés, esti és levelező fakultások műszaki egyetemek.

Lektorok: osztály matematikai elemzés Szentpétervári Állami Egyetem; Assoc. M. V. Dmitrieva (Szentpétervári Állami Egyetem).

Jóváhagyta az Egyetem Szerkesztői és Kiadói Tanácsa

oktatási segédanyagként

A matematikai logika, akárcsak az algoritmusok elmélete, már jóval a számítógépek megjelenése előtt megjelent. Megjelenésük a matematika belső problémáival, elméletei és módszerei alkalmazhatósági határainak vizsgálatával függött össze.

IN Jelenleg mindkét (egymással összefüggő) elmélet az úgynevezett számítógépes matematikában (számítástechnikában) kapott alkalmazott fejlesztést. Íme néhány felhasználási terület az alkalmazási területeken:

– szakértői rendszerek használata formális logikai következtetések a különböző területeken dolgozó szakértők tevékenységének szimulálására;

– mikroáramkörök tervezésekor a Boole-függvények elméletét alkalmazzák;

– a programok tesztelése szerkezetük logikai elemzésén alapul;

– a programok helyességének bizonyítása a logikai következtetés elméletén alapul;

– Az algoritmikus nyelvek összekapcsolják a kettőt fontos fogalmak logika: a nyelv fogalma és az algoritmus fogalma;

– A tételbizonyítás automatizálása a logika tantárgyon tanult felbontási módszeren alapul.

IN Ez a tankönyv felvázolja a matematikai logika alapgondolatait, fogalmait és módszereit, amelyek mind a fentiek, mind pedig egyéb alkalmazásai mögött állnak.

1. Bináris relációk és gráfok

1.1. Bevezetés. A probléma megfogalmazása

A bináris relációkkal már találkoztunk iskolai tanfolyam matematika Ilyen összefüggések például az egyenlőtlenség, egyenlőség, hasonlóság, párhuzamosság, oszthatóság stb. relációi. A bináris reláció mindkét objektumot „igen” logikai értékkel társítja, ha az objektumok ebben a relációban vannak, és „nem” egyébként. Más szavakkal, az objektumpárok halmaza két részhalmazra oszlik, az első részhalmaz párjai ebben a tekintetben, a második pedig nem található. Ezt a tulajdonságot lehet alapul venni egy bináris reláció meghatározásához.

Meghatározás 1.1. Legyen adott egy M halmaz. Tekintsük ennek a halmaznak a derékszögű szorzatát önmagával M × M . Az M × M halmaz R részhalmazát R bináris relációnak nevezzük az M halmazon. Ha az (x; y) pár az R halmazhoz tartozik, akkor azt mondjuk, hogy az x elem R relációban van az y elemmel, és xRy-t írunk.

Példa 1.1. Vezessük be az R összehasonlíthatósági relációt: x akkor és csak akkor hasonlítható össze y modulo m-rel, ha x és y maradékai azonosak m-vel osztva. Vagyis x ≡ y (mod m) .

Tekintsük a bevezetett R összefüggést m = 3 esetre az M = (1; 2; 3; 4; 5; 6) halmazon, majd

Az R relációt az ilyen párok halmaza határozza meg:

Példa 1.2. Tekintsük úgy, hogy M = R – dolgok halmaza

valós számok, vagy más szóval a valós egyenes pontjainak halmaza. Ekkor M × M = R 2 a koordinátasík pontjainak halmaza. Egyenlőtlenségi viszony< определяется множеством парR = = {(x; y)|x < y} .

1.1. gyakorlat.

1. A valós számok halmazán a következő összefüggés van megadva: xRy akkor

mikor és csak akkor, ha az egyik szám kétszerese a másiknak. Rajzoljon a síkra egy ponthalmazt, amely meghatározza ezt a kapcsolatot.

2. Az M = (1; 2; 3; 4; 5; 6) halmazon adott az oszthatósági összefüggés: xRy akkor és csak akkor, ha x osztható y-vel. Hány pár van benne?

ez a hozzáállás? Sorold fel ezeket a párokat!

3. Vezessük be az M = (1; 2; 3; 4; 5; 6) halmazra a koprímség összefüggését, azaz xRy akkor és csak akkor, ha x és y koprím: D(x; y) = 1 . Hány párt tartalmaz ez a reláció? Sorolja fel ezeket

1.2. Tulajdonságok bináris relációk

Meghatározás 1.2. Az M halmazon lévő R bináris relációt hívjuk

reflexív, ha ennek a halmaznak minden eleme kapcsolatban áll önmagával: xRx x M .

1.3. példa.

1. Az összehasonlíthatósági reláció reflexív (bármilyen természetes m és bármely egész számhalmazon).

2. Hozzáállás szigorú egyenlőtlenség valós számok halmazán nem reflexív.

3. Az oszthatósági reláció reflexív (bármely egész számhalmazon, amely nem tartalmaz nullát).

Meghatározás 1.3. Az M halmazon lévő R bináris relációt hívjuk

antireflexív, ha ennek a halmaznak egyetlen eleme sincs önmagával kapcsolatban: x M nem igaz, hogy xRx .

Példa 1.4.

1. A szigorú egyenlőtlenségi reláció a valós számok halmazán antireflexív.

2. A kölcsönös prímreláció antireflexív minden olyan egész halmazra, amelyet nem tartalmaz 1 és -1, reflexív az (1), (-1) , (-1; 1) halmazokon, és sem nem reflexív, sem nem antireflexív

egyébként.

Meghatározás 1.4. Az M halmazon lévő R bináris relációt szimmetrikusnak nevezzük, ha az egyes (x; y) párokkal együtt a reláció egy (y; x) szimmetrikus párt is tartalmaz: x, y M xRy yRx .

1.5. példa.

1. Az összehasonlíthatósági reláció bármely természetes számra szimmetrikus

2. A szigorú egyenlőtlenségi reláció a valós számok halmazán nem szimmetrikus.

3. Az oszthatósági reláció csak az egyet nem tartalmazó páronkénti másodlagos egészek halmazán szimmetrikus. Például prímszámok halmazán.

4. A koprím reláció az egész számok bármely halmazára szimmetrikus.

Meghatározás 1.5. Az M halmazon lévő R bináris relációt hívjuk

aszimmetrikus, ha a relációban nem szerepel pár a szimmetrikusával együtt: x, y M , ha xRy , akkor nem igaz, hogy yRx .

Példa 1.6.

1. A valós számok halmazán a szigorú egyenlőtlenségi reláció aszimmetrikus.

2. Az oszthatósági reláció nem aszimmetrikus olyan egész számok halmazán, amely nem tartalmaz nullát.

Meghatározás 1.6. Az M halmazon lévő R bináris relációt hívjuk

antiszimmetrikus, ha a relációban nem szerepel különböző elemekből álló pár a szimmetrikusával együtt: x, y M ifxRy és yRx tox = y.

Példa 1.7.

1. Hozzáállás nem szigorú egyenlőtlenség a valós számok halmazán antiszimmetrikus.

2. Az oszthatósági reláció antiszimmetrikus minden olyan egész számhalmazra, amely nem tartalmaz nullát.

1.2. gyakorlat.

1. Igaz, hogy az aszimmetrikus kapcsolat mindig antireflexív? Bizonyítsd be.

2. Igaz, hogy a szimmetrikus reláció mindig reflexív? Mutasd meg előtte.

3. Igaz, hogy az aszimmetrikus reláció mindig antiszimmetrikus? Bizonyítsd be.

4. Igaz-e, hogy egy reláció akkor és csak akkor aszimmetrikus, ha antireflexív és antiszimmetrikus? Bizonyítsd be.

Meghatározás 1.7. Egy R bináris reláció tranzitív, ha az (x; y) pár tartalmazza az (x, z) párt is, azaz x, y, x M, ha xRy és

az M halmazt u(y; z)-nek nevezzük az yRz , toxRz relációban.

Megjegyzés 1.1. A tranzitivitási tulajdonságot jól szemlélteti az elérhetőségi reláció: ha a pointy elérhető x pontokból, és a pointz elérhető a pointyból, akkor a pointz elérhető azx pontokból.

Példa 1.8.

1. Az összehasonlíthatósági reláció tranzitív minden természetesre m és bármely egész számhalmazon.

2. A szigorú (nem szigorú) egyenlőtlenségi reláció tranzitív a valós számok bármely részhalmazán.

3. Az oszthatósági reláció tranzitív a nullát nem tartalmazó egész számok halmazán.

4. A koprím reláció nem tranzitív egész számok halmazán. Például, A 2 a c3-hoz, a 3 a c4-hez tartozó másodpím, de a 2 és a 4 nem másodprím.

1.3. gyakorlat. Igaz-e, hogy tranzitív és szimmetrikus

A hozzáállás mindig reflexszerű? Bizonyítsd be.

1.3. A kapcsolatok meghatározásának módszerei

A bináris relációt meghatározó párok explicit felsorolásán kívül a relációk megadásának a következő módjai lehetségesek.

Az ellenőrzési eljárás beállítása.

Példa 1.9.

1. A kölcsönös elsőbbségi összefüggést a legnagyobb megtalálásának eljárásával ellenőrizzük közös osztó: Ha D(x; y) = 1 , akkor (x; y) benne van

a kölcsönös egyszerűség kapcsolata.

2. Az oszthatósági összefüggést a maradékkal való osztás eljárásával ellenőrizzük: ha x ≡ 0 (mod y) , akkor (x; y) benne van az oszthatósági relációban.

3. Ugyanez az eljárás ellenőrzi a maradékok egyenlőségének viszonyát az osztással m : ha (x−y)≡0 (mod m) , akkor (x; y) benne van a relációban.

A kapcsolatokra tovább véges halmazok(amelyek alapjai diszkrét matematika) a kapcsolatok meghatározásának és leírásának alábbi módszereit is alkalmazzák.

Szomszédsági mátrix megadása. Határozzuk meg az A méretű mátrixot

|M | × |M |, ahol |M | – az M halmaz elemeinek száma. Számozzuk meg az M halmaz elemeit. Ekkor aij = 1, ha az i elemszám kapcsolatban áll a j elemszámmal (iRj), egyébként pedig aij = 0.

1.10. példa. Az oszthatósági reláció szomszédsági mátrixa az M = (1; 2; 3; 4; 5; 6) halmazon így néz ki:

Hozzárendelés a grafikon szerint. A halmaz elemeit a síkon lévő pontok ábrázolják, és a gráf csúcsainak halmazát alkotják. A relációkat a gráf ívei (élei) ábrázolják: ha (x; y) benne van a relációban, akkor az x csúcsból az y-ba egy orientált ívet rajzolunk.

Példa 1.11. Grafikon az összehasonlíthatósági relációhoz modulo three on

A szomszédságok listájának megadása. A halmaz minden eleméhez fel vannak sorolva azok az elemek, amelyek adott kapcsolatban állnak vele.

Példa 1.12. Az M = (1; 2; 3; 4; 5; 6) halmaz koprím relációjának szomszédságlistája így néz ki:

Adjunk értelmezést a bináris relációk tulajdonságairól az azokat leíró gráfokon és mátrixokon.

1.1. tétel. A következő állítások igazak.

1. Egy reflexív reláció szomszédsági mátrixának átlója egyesekből áll.

2. A szimmetrikus relációnak szimmetrikus szomszédsági mátrixa van

3. A reflexív relációs gráf minden csúcsában hurkot tartalmaz.

4. Egy szimmetrikus reláció grafikonja az összekötő ívvel együtt x

y-val, y-t x-szel összekötő ívet tartalmaz.

5. A tranzitív relációgráfnak van a következő tulajdonság: ha felülről x, az ívek mentén haladva eljuthatunk az y csúcshoz, ekkor a gráfnak rendelkeznie kell egy ívvel, amely közvetlenül összeköti x-et y-val.

Megjegyzés 1.2. A szimmetrikushoz

hurkokat általában nem ábrázolnak, és az ezeket a csúcsokat összekötő orientált ívpárokat egy – orientálatlan – ív váltja fel.

Például az 1.11. példa grafikonja úgy fog kinézni, mint az ábra. 1.2.

és reflexív kapcsolatok

1.4. gyakorlat.

1. Ismertesse a szomszédsági mátrix tulajdonságait: a) antireflexív attitűd; b) aszimmetrikus kapcsolat; c) antiszimmetrikus viselet; d) tranzitív reláció.

2. Ismertesse a gráf tulajdonságait: a) tükröződésmentes hozzáállás; b) aszimmetrikus kapcsolat; c) antiszimmetrikus kapcsolat.

1.4. Egyenértékűségi reláció

Meghatározás 1.8. Egy bináris reláció, amelynek re tulajdonságai vannak

Az inflexivitást, szimmetriát és tranzitivitást ekvivalenciarelációnak nevezzük.

1.13. példa. Az összehasonlíthatósági reláció (bármilyen modulussal) az

egy ekvivalencia reláció.

Az M halmaz minden eleméhez társítsuk azokat az elemeket, amelyek egy adott ekvivalencia relációban vannak vele: Mx = (y M | xRy). A következő tétel igaz.

Tétel 1.2. Az M x és M y halmazok vagy nem metszik egymást, vagy megegyeznek

Bizonyíték. Ugyanazon osztály minden eleme ekvivalens egymással, azaz ha x, y Mz, akkor xRy. Valóban, legyen x, y Mz , tehát xRz és yRz. Az R reláció szimmetriája alapján zRy-t kapunk. Ekkor a tranzitivitás miatt xRz-ből és zRy-ből xRy-t kapunk.

Szövetségi Oktatási Ügynökség

TOMSK ÁLLAMI VEZÉRLŐRENDSZEREK ÉS RÁDIÓELEKTRONIKAI EGYETEM (TUSUR)

Információfeldolgozás Automatizálási Tanszék

Megerősítem:

Fej osztály IDF

egyetemi tanár

Yu.P. Ehlakov

"__" _____________2007

Irányelvek

a megvalósításhoz gyakorlati munka fegyelem szerint

"Matematikai logika és algoritmusok elmélete"

szakos hallgatóknak 230102 –

"Automatizált információfeldolgozó és -vezérlő rendszerek"

Fejlesztők:

Művészet. tanszék tanára IDF

HOGY. Peremitina

Tomszk – 2007

1. számú gyakorlati lecke „Propozíciós algebrai képletek” 3

2. számú gyakorlati óra" Egyenértékű transzformációk propozíciós algebrai képletek" 10

3. számú gyakorlati lecke „A képletek normál alakjai” 12

4. számú gyakorlati lecke „Logikai érvelés” 14

5. számú gyakorlati lecke „Predikátumlogika képletei” 18

6. számú gyakorlati óra „Boole-függvények” 23

7. számú gyakorlati óra „Részlegesen rekurzív függvények” 28

8. számú gyakorlati óra „Turing-gépek” 34

1. számú gyakorlati lecke „Kiállítási algebrai képletek”

Az állítások doktrínája - az állítások algebra vagy a logika algebra - a legegyszerűbb logikai elmélet. A propozíciós algebra atomi fogalma az nyilatkozat – kijelentő mondat, amellyel kapcsolatban van értelme annak igazságáról vagy hamisságáról szóló állításnak.

Példa egy igaz állításra: „A Föld a Nap körül forog.” Példa hamis állításra: "3 > 5". Nem minden mondat állítás, az állítások nem tartalmaznak kérdő és felkiáltó mondatokat. A „kása ízletes étel” mondat nem állítás, hiszen nem lehet egyetértés abban, hogy igaz vagy hamis. A „Van élet a Marson” mondatot állításnak kell tekinteni, hiszen objektíve igaz vagy hamis, bár még senki sem tudja, melyik.

Mivel a logika vizsgálatának tárgya csak az állítások igazságértékei, az A, B, ... vagy X,Y... betűjeleket vezetik be ezekre.

Minden állítás igaznak vagy hamisnak minősül. A rövidség kedvéért 1-et írunk a valódi érték helyett, és 0-t a hamis érték helyett. Például X = "A Föld a Nap körül kering" és Y = "3 > 5", ahol X = 1 és Y =. 0. Egy állítás nem lehet egyszerre igaz és hamis .

Az állítások lehetnek egyszerűek vagy összetettek. A „A Föld a Nap körül forog” és a „3 > 5” állítások egyszerűek. Az összetett állítások egyszerű állításokból készülnek a természetes (orosz) nyelv NEM, ÉS, VAGY, HA-AKKOR, AKKOR-ÉS-CSAK-AKKOR konnektívumaival. Ha az állításokhoz betűjeleket használunk, ezeket a konnektívumokat speciális matematikai szimbólumok helyettesítik, amelyek a logikai műveletek szimbólumainak tekinthetők.

Az alábbiakban az 1. táblázat a konnektívumokat jelölő szimbólumok lehetőségeit és a megfelelő logikai műveletek neveit mutatja be.

Tagadás (inverziós) állítások X olyan állítás, amely akkor és csak akkor igaz X hamis (vagy jelöléssel , „nem X” vagy „ez nem igaz X”).

Konjunkció
A két állítás akkor és csak akkor igaz, ha mindkét állítás igaz XÉs Y. Ez a logikai művelet megfelel az állítások „és” kötőszóval való összekapcsolásának.

Diszjunkció
két állítás XÉs Y Egy állítást akkor és csak akkor nevezünk hamisnak, ha mindkét állítás XÉs Y hamis. A köznyelvben ez a logikai művelet a „vagy” kötőszónak felel meg (nem a kizárólagos „vagy”).

Értelemszerűen két állítás X És Y olyan állítás, amely akkor és csak akkor hamis X igaz, de Y– hamis (jelöljük
; így szól: " X jár Y", "Ha X, Azt Y"). A művelet operandusainak speciális neveik vannak: X- csomag, Y- következtetés.

Egyenértékűség két állítás XÉs Y egy olyan állítás, amely akkor és csak akkor igaz, ha az igazság értékes XÉs Y ugyanazok (megnevezés:
).

1. táblázat. Logikai műveletek

A logikai műveletek operandusai csak két értéket vehetnek fel: 1 vagy 0. Ezért minden , &,,, logikai művelet könnyen megadható táblázat segítségével, jelezve a művelet eredményének értékét az értékek függvényében. az operandusok közül. Ezt a táblázatot hívják igazságtáblázat (2. táblázat).

2. táblázat: A logikai műveletek igazságtáblázata

A fent definiált logikai műveletek segítségével egyszerű utasításokból lehet konstruálni propozíciós logikai képletek , amely különféle összetett állításokat jelent. Az összetett állítás logikai jelentése az állítás képlettel kifejezett szerkezetétől és az azt alkotó elemi állítások logikai értékétől függ.

Az állításokat kifejező képletek szisztematikus tanulmányozásához változó utasításokat vezetünk be P, P 1 , P 2 , ..., P N, a (0, 1) halmazból vett értékeket.

Propozíciós logikai képlet F (P 1 , P 2 ,..., P N) tautológiának, ill azonos az igaz , ha értéke bármely érték esetén P 1 , P 2 ,..., P N van 1 (igaz). Olyan képleteket hívunk meg, amelyek egy változólista legalább egy halmazára igaznak számítanak megvalósítható . Azokat a képleteket, amelyek bármely változó értékére hamisra értékelnek, meghívjuk ellentmondások (ugyanúgy hamis, lehetetlen).

Szerző: Guts A.K.
Kiadó: O.: Örökség
Kiadás éve: 2003
Oldalak: 108
ISBN 5-8239-0126-7
Olvas:
Letöltés: matematicheskayalogika2003.djvu

OMSKI ÁLLAMI EGYETEM SZÁMÍTÁSTUDOMÁNYI KAR
KIBERNETIKA
A.K. Belek
Matematikai logika és algoritmusok elmélete
Omszk 2003
VVK 60 UDC 53:630.11
Guts A.K. Matematikai logika és algoritmusok elmélete: Tankönyv. -
Omszk: Örökség Kiadó. Párbeszéd-Szibéria, 2003. - 108 p.
ISBN 5-8239-0126-7
A tankönyv a matematikai logika és elmélet alapjainak bemutatását szolgálja
algoritmusok. A kézikönyv alapját az elhangzott jegyzetek képezik
tanszék másodéves hallgatói számítástechnika Omszk
Állami Egyetemen 2002-ben.
A 075200 szakterületen tanuló hallgatók számára - "Számítógép
biztonság” és 220100 szakterület – „Számítógépek,
komplexek, rendszerek és hálózatok."
ISBN 5-8239-0126-7
c) Omszki Állami Egyetem, 2003
Tartalomjegyzék
I Logic 7
1 Klasszikus logika 8
1.1. Propozíciós logika................................................ 8
1.1.1. Nyilatkozatok........................................ 8
1.1.2. A logika alaptörvényei........................ 9
1.1.3. Logikai paradoxon Russell........................ 10
1.1.4. Állítások algebra (logikája)............... 11
1.1.5. Relé diagramok.................................. 12
1.1.6. Egyenértékű képletek.................................. 14
1.1.7. Boole-algebra.................................. 15
1.1.8. Igaz és általánosan érvényes képletek........... 15
1.1.9. A megoldhatósági probléma........................ 15
1.1.10. Logikai következmény........................ 16
1.1.11. Szillogizmusok................................ 17
1.2. Predikátum logika................................................ 17
1.2.1. Predikátumok és képletek........................ 18
1.2.2. Értelmezések................................................ 19
1.2.3. A képletek igazsága és kielégíthetősége. Modellek,
általános érvényesség, logikai következmény........ 20
1.2.4. Gottlob Frege........................ 21
1.2.5. Skolemov függvények
és a képletek skolemizálása................................ 22
1.3. Felbontási módszer............................................................
1.3.1. Felbontások módszere a logikában
nyilatkozatok................................ 25
1.3.2. Felbontások módszere a logikában
predikátumok.............................................. 29
3
4
Tartalomjegyzék
2 Formális elméletek (számítás) 31
2.1. A formális elmélet vagy a számítás definíciója. . 32
2.1.1. Bizonyíték. Az elmélet összhangja.
Az elmélet teljessége.................................. 32
2.2. Állításszámítás........................ 33
2.2.1. A propozíciószámítás nyelvi és levezetési szabályai
............................................. 33
2.2.2. Példa a tétel bizonyítására........................ 35
2.2.3. Teljesség és következetesség
propozíciószámítás........................ 36
2.3. Predikátumszámítás.................................. 37
2.3.1. A predikátumszámítás nyelve és következtetési szabályai 37
2.3.2. Teljesség és következetesség
predikátumszámítás........................ 39
2.4. Formális aritmetika.............................. 39
2.4.1. Egalitárius elméletek........................ 39
2.4.2. A formális aritmetika nyelve és levezetésének szabályai
.............................................. 39
2.4.3. A formai következetesség
számtan. Gentzen tétele................... 40
2.4.4. Gödel befejezetlenségi tétele................................................ 41
2.4.5. Kurt Gödel................................................ 42
2.5. Tételek automatikus levezetése................................................ 43
2.5.1. S.Yu. Maszlov................................ 43
2.6. Logikai programozás................................ 45
2.6.1. Logikai program........................ 46
2.6.2. Logikai programozási nyelvek... 49
3 Nem klasszikus logika 50
3.1. Intuicionista logika................................ 50
3.2. Fuzzy logika................................................ 51
3.2.1. Fuzzy részhalmazok................................... 51
3.2.2. Műveletek fuzzy-n
részhalmazok........................................ 52
3.2.3. A fuzzy halmazának tulajdonságai
részhalmazok........................................ 53
3.2.4. Fuzzy propozicionális logika................................ 54
3.2.5. Fuzzy relé áramkörök........... 56
3.3. Modális logika................................ 56
3.3.1. A modalitás típusai................................ 57
Tartalomjegyzék
5
3.3.2. 1. és T kalkulus (Feis-von Wright)........ 57
3.3.3. Számítás S4, S5
és Brouwer kalkulusa........................ 58
3.3.4. A képletek jelentése........................ 59
3.3.5. Kripke szemantikája........................ 60
3.3.6. A modálok egyéb értelmezései
karakterek................................ 62
3.4. Georg von Wright................................................ 62
3.5. Időzítési logika................................ 62
3.5.1. Pryor időbeli logikája................................ 63
3.5.2. Lemmon időbeli logikája...... 64
3.5.3. Von Wright időbeli logikája...... 64
3.5.4. Időzítési logikai alkalmazás
programozáshoz........................ 65
3.5.5. Pnueli időbeli logikája................................ 67
3.6. Algoritmikus logikák.................................. 70
3.6.1. Építési alapelvek
1 >

a KAZÁNI MŰSZAKI EGYETEM. A. N. Tupolev

Sh. I. GALIEV

MATEMATIKAI LOGIKA ÉS ALGORITMUSOK ELMÉLETE

ÚTMUTATÓ

Kazan 2002

Galiev Sh. I. Matematikai logika és algoritmusok elmélete. – Kazan: a KSTU kiadó a nevét viseli. A. N. Tupolev. 2002. - 270 p.

ISBN 5-93629-031-X

A kézikönyv a következő részeket tartalmazza. Propozíciós és predikátum logika alkalmazásokkal, beleértve a feloldási módszert és megvalósításának elemeit a PROLOG nyelven. Klasszikus kalkulus (állítások és predikátumok) és a nem klasszikus logika elemei: három- és többértékű logika, modális, időbeli és fuzzy logika. Algoritmusok elmélete: normál algoritmusok, Turing-gépek, rekurzív függvények és kapcsolataik. A számítási komplexitás fogalma, különféle (komplexitásbeli) problémaosztályok és példák ilyen problémákra.

Minden fejezet rendelkezésre áll ellenőrző kérdésekés gyakorlatok, opciók adottak tipikus feladatok valamint az anyagelsajátítás önellenőrzésére szolgáló tesztek.

A kézikönyv a műszaki egyetemek hallgatói számára készült a 2201-es szakterületen az „Informatika és számítástechnika"és felhasználható a 2202-es specialitáshoz és a terület egyéb különlegességeihez.

BEVEZETÉS

A logikán általában a bizonyítási és cáfolat módszerek tudományát értik. A matematikai logika matematikai módszerekkel kifejlesztett logika.

A bizonyítási és cáfolat módszereinek tanulmányozása során a logika elsősorban az igaz következtetések levonásának formáját érdekli, nem pedig a premisszák és következtetések tartalmát egy adott érvben. Vegyük például a következő két kimenetet:

1. Minden ember halandó. Szókratész ember. Ezért Szókratész halandó.

2. Minden cica szeret játszani. Mura egy cica. Ebből következően Mura szeret játszani.

Mindkét következtetésnek ugyanaz a formája: A mindegyik B; ezért C az B. Ezek a következtetések formájuknál fogva igazak, tartalomtól függetlenül, függetlenül attól, hogy az önmagukban levont premisszák és következtetések igazak vagy hamisak. Szisztematikus formalizálás és katalogizálás a megfelelő utakat az érvelés a logika egyik fő feladata. Ha ez vonatkozik matematikai berendezésés a kutatás elsősorban a matematikai érvelés tanulmányozására irányul, akkor ez a logika az matematikai logika (formális logika). Ez a meghatározás nem szigorú (pontos) meghatározás. A matematikai logika tárgyának és módszerének megértéséhez a legjobb, ha elkezdi tanulmányozni.

A matematikai logika már régen kezdett formát ölteni. Ötletei és módszerei ben keletkeztek Ókori Görögország, Ősi IndiaÉs Ősi Kína körülbelül a 6. századból. I.E e. A tudósok már ebben az időszakban megpróbálták elrendezni a láncot matematikai bizonyítások olyan láncban, hogy az egyik láncszemről a másikra való átmenet nem hagy kétséget, és egyetemes elismerést nyer. Már a legkorábbi kéziratokban, amelyek eljutottak hozzánk, a matematikai előadásmód „kánonja” szilárdan megalapozott. Ezt követően kapja meg a végső befejezést a nagy klasszikusoktól: Arisztotelésztől, Eukleidésztől, Arkhimédésztől. A bizonyítás fogalma ezeknél a szerzőknél nem különbözik a miénktől.

Mint a logika független tudomány Arisztotelész (Kr. e. 384 - 322) tanulmányaiból származik. Nagy filozófus Az ókor Arisztotelész az ókori ismeretek enciklopédikus rendszerezését végezte el az akkor létező tudomány minden területén. Arisztotelész logikai tanulmányait főként két művében, a „First Analytics” és a „Second Analytics” című művében mutatják be. köznév"Organon" (a tudás eszköze).

Különös figyelmet érdemel nagy érték A matematikai logika kialakítása és fejlesztése az emberiség történetének egyik legragyogóbb vívmánya, nevezetesen a geometria pontos deduktív rendszerré alakítása Eukleidész (Kr. e. 330-275) „Principia” művében. Ez a deduktív megközelítés a célok és módszerek világos tudatában alapozta meg a filozófiai és matematikai gondolkodás fejlődését a következő évszázadokban.

A logika kialakulásában és fejlődésében szintén nagy jelentőséggel bírtak az algebrában (Boole-algebra) és más matematikai tudományágakban elért eredmények, beleértve ismét a geometriát (a nem euklideszi geometria létrehozása - Lobacsevszkij - Gauss - Bolyai geometriája). Rövid áttekintés A matematikai logika kialakulása ben található.

Sok-sok tudós, mind az ókorból, mind a középkorból és az azt követő időkből vett részt a matematikai logika kialakításában és fejlesztésében.

Alapvető és alkalmazott érték matematikai logika

A matematikai logika alapvető fontossága a matematika igazolása (a matematika alapjainak elemzése).

A matematikai logika alkalmazott értéke jelenleg nagyon nagy. A matematikai logikát a következő célokra használják:

digitális elemzése és szintézise (konstrukciója). számítógépekés más diszkrét automaták, beleértve az intelligens rendszereket;

elemzése és szintézise a formális és gépi nyelvek,természetes nyelvi elemzéshez;

a kiszámíthatóság intuitív fogalmának elemzése és formalizálása;

bizonyos típusú problémák megoldására szolgáló mechanikai eljárások meglétének tisztázása;

számítási komplexitási problémák elemzése.

Ezenkívül kiderült, hogy a matematikai logika szorosan összefügg számos nyelvészeti, közgazdasági, pszichológiai és filozófiai kérdéssel.

Ez a kézikönyv felvázolja a matematikai logika és az algoritmusok elméletének alapfogalmait. A kézikönyvben bemutatott anyag

állapotnak felel meg oktatási színvonal„Informatika és számítástechnika” szakra, és az ezen a területen különböző szakokon tanuló hallgatók számára használható.

A kézikönyv megírásakor szakirodalmat, és természetesen egyéb forrásokat is felhasználtak. Az irodalomjegyzékben olyan könyvek szerepelnek, amelyeket egy érdeklődő és igényes hallgatónak ajánlatos átnéznie.

A kézikönyv minden fejezetében önellenőrző kérdéseket tartalmaz. elméleti anyag valamint a problémamegoldó készségek fejlesztését és a bemutatott témával kapcsolatos ismeretek elmélyítését szolgáló gyakorlatok. Ezenkívül a kézikönyv tartalmazza a tipikus feladatokra vonatkozó lehetőségeket és az anyagelsajátítás önellenőrzésére szolgáló teszteket.