Bøker. Last ned DJVU-bøker, PDF gratis

KAZAN TECHNICAL UNIVERSITY oppkalt etter. A.N. Tupolev

Sh. I. GALIEV

MATEMATISK LOGIKK OG ALGORITMETEORI

OPPLÆRINGEN

Kazan 2002

Galiev Sh. I. Matematisk logikk og teori om algoritmer. - Kazan: Forlaget til KSTU. A.N. Tupolev. 2002. - 270 s.

ISBN 5-93629-031-X

Håndboken inneholder følgende avsnitt. Proposisjons- og predikatlogikk med applikasjoner, inkludert oppløsningsmetoden og elementer av dens implementering i PROLOG-språket. Klassisk kalkulus (utsagn og predikater) og elementer av ikke-klassisk logikk: logikk med tre verdier og flere verdier, modal, tidsmessig og uklar logikk. Teori om algoritmer: normale algoritmer, Turing-maskiner, rekursive funksjoner og deres relasjoner. Begrepet beregningskompleksitet, ulike (i kompleksitet) klasser av problemer og eksempler på slike problemer.

Alle kapitler er gitt kontrollspørsmål og øvelser, opsjoner er gitt typiske oppgaver og tester for selvkontroll av assimilering av materialet.

Manualen er beregnet på studenter ved tekniske universiteter i spesialitet 2201 innen "Informatikk og informatikk" og kan brukes for spesialitet 2202 og andre spesialiteter innen dette feltet.

INTRODUKSJON

Logikk blir vanligvis forstått som vitenskapen om metoder for bevis og tilbakevisning. Matematisk logikk er logikk utviklet ved hjelp av matematiske metoder.

Når man studerer metoder for bevis og tilbakevisning, er logikk først og fremst interessert i formen for å oppnå sanne konklusjoner, og ikke i innholdet i premisser og konklusjoner i et bestemt argument. Tenk for eksempel på følgende to utganger:

1. Alle mennesker er dødelige. Sokrates er en mann. Derfor er Sokrates dødelig.

2. Alle kattunger elsker å leke. Mura er en kattunge. Følgelig elsker Mura å spille.

Begge disse konklusjonene har samme form: Alle A er B, C er A; derfor er C B. Disse konklusjonene er sanne i kraft av sin form, uavhengig av innholdet, uavhengig av om premissene og konklusjonene som er tatt av seg selv er sanne eller usanne. Systematisk formalisering og katalogisering de riktige måtene resonnement er en av logikkens hovedoppgaver. Hvis det matematiske apparatet brukes og forskningen primært er viet til studiet av matematisk resonnement, så er denne logikken matematisk logikk (formell logikk). Denne definisjonen er ikke en streng (presis) definisjon. For å forstå emnet og metoden for matematisk logikk, er det best å begynne å studere det.

Matematisk logikk begynte å ta form for lenge siden. Opprinnelsen til ideene og metodene fant sted i Antikkens Hellas, det gamle India Og Det gamle Kina fra ca 600-tallet. f.Kr e. Allerede i løpet av denne perioden prøvde forskere å ordne kjeden av matematiske bevis i en slik kjede at overgangen fra en kobling til en annen ikke etterlot noen tvil og vant universell anerkjennelse. Allerede i de tidligste manuskriptene som har nådd oss, er "kanonen" for matematisk presentasjonsstil godt etablert. Deretter får den endelig fullføring fra de store klassikerne: Aristoteles, Euklid, Arkimedes. Konseptet med bevis hos disse forfatterne er ikke forskjellig fra vårt.

Logikken som en uavhengig vitenskap har sitt opphav i studiene til Aristoteles (384 - 322 f.Kr.). Den store eldgamle filosofen Aristoteles gjennomfører en leksikon systematisering eldgammel kunnskap på alle områder av den daværende vitenskapen. Aristoteles' logiske studier presenteres hovedsakelig i hans to verk "First Analytics" og "Second Analytics", samlet under vanlig navn"Organon" (Kunnskapsinstrument).

Spesielt bemerkelsesverdig veldig viktig for dannelse og utvikling av matematisk logikk en av de mest strålende prestasjonene i menneskehetens historie, nemlig transformasjonen av geometri til et eksakt deduktivt system i arbeidet til Euclid (330 - 275 f.Kr.) "Principia". Det var denne deduktive tilnærmingen med en klar bevissthet om mål og metoder som dannet grunnlaget for utviklingen av filosofisk og matematisk tankegang i de påfølgende århundrene.

Også av stor betydning for dannelsen og utviklingen av logikk var prestasjoner i algebra (Boole algebra) og i andre matematiske disipliner, inkludert igjen i geometri (skapingen av ikke-euklidisk geometri - geometrien til Lobachevsky - Gauss - Bolyai). Kort anmeldelse Dannelsen av matematisk logikk kan finnes i.

Mange, mange forskere, både fra antikken, fra middelalderen og påfølgende tider, deltok i dannelsen og utviklingen av matematisk logikk.

Grunnleggende og anvendt betydning av matematisk logikk

Den grunnleggende betydningen av matematisk logikk er begrunnelsen av matematikk (analyse av grunnlaget for matematikk).

Den anvendte verdien av matematisk logikk er for tiden veldig stor. Matematisk logikk brukes til følgende formål:

analyse og syntese (konstruksjon) av digitale datamaskiner og andre diskrete automater, inkludert intelligente systemer;

analyse og syntese av formelle og maskinelle språk, for naturlig språkanalyse;

analyse og formalisering av det intuitive konseptet beregnbarhet;

avklare eksistensen av mekaniske prosedyrer for å løse problemer av en viss type;

analyse av beregningsmessige kompleksitetsproblemer.

Også matematisk logikk viste seg å være nært forbundet med en rekke problemstillinger innen lingvistikk, økonomi, psykologi og filosofi.

Denne håndboken skisserer de grunnleggende konseptene for matematisk logikk og teorien om algoritmer. Materialet presentert i manualen

tilsvarer staten pedagogisk standard for feltet "Informatikk og informatikk" og kan brukes for studenter som studerer i ulike spesialiteter innen dette feltet.

Ved skriving av manualen ble det brukt litteratur, og selvfølgelig også andre kilder. Listen over referanser inkluderer bøker som det er tilrådelig for en nysgjerrig og krevende student å anmelde.

Håndboken i hvert kapittel inneholder spørsmål for selvtesting av teoretisk materiale og øvelser designet for å utvikle problemløsningsferdigheter og utdype kunnskap om temaet som presenteres. I tillegg inneholder manualen muligheter for typiske oppgaver og tester for egenkontroll av materialmestring.

Den foreslåtte læreboken (2. utgave, stereotypi) danner grunnlaget for et sett for forløpet av matematisk logikk og teori om algoritmer, som også inkluderer en samling problemer (Igoshin V.I. Problemer og øvelser i matematisk logikk og teori om algoritmer).

Det grunnleggende i teorien er skissert i detalj, retningene for penetrering av logikk inn i grunnlaget for algebra, analyse, geometri er vist, og materialet er tegnet på skolekurs matematikk for sin logiske analyse, forholdet mellom matematisk logikk og datamaskiner, informatikk, systemer er preget kunstig intelligens.

Introduksjon. Matematisk logikk i systemet for moderne utdanning.
Logikk og intuisjon. Tradisjonell logikk og matematisk logikk. Litt historie. Matematisk logikk - logikk eller matematikk? Matematisk logikk i undervisning i matematikk. Matematisk logikk og moderne datamaskiner.
Kapittel I. Proposisjonalgebra.
§ 1. Uttalelser og operasjoner på dem.
Begrepet ytring. Negasjon av uttalelsen. Sammensetning av to utsagn. Disjunksjon av to utsagn. Implikasjon av to utsagn. Ekvivalens av to utsagn. Språkkonjunksjoner og logiske operasjoner (språk og logikk). Generell visning for logiske operasjoner.
§2. Proposisjonelle algebraformler.
Konstruksjon av komplekse utsagn. Konseptet med en proposisjonell algebraformel. Den logiske betydningen av et sammensatt utsagn. Tegne opp sannhetstabeller for formler. Klassifisering av proposisjonelle algebraformler. Tenkning og matematisk logikk
§ 3. Proposisjonalgebras tautologier.
Om betydningen av tautologier. Grunnleggende tautologier. Grunnleggende regler for å få en tautologi.
§ 4. Logisk ekvivalens av formler.
Konseptet med ekvivalens av formler. Et tegn på ekvivalens av formler. Eksempler på ekvivalente formler. Ekvivalente transformasjoner av formler. Ekvivalenser i logikk og identiteter i algebra.
§ 5. Normalformer for proposisjonelle algebraformler.
Konseptet med normale former. Perfekte normale former. Representasjon av proposisjonelle algebraformler ved perfekte disjunktive normalformer (PDN). Representasjon av proposisjonelle algebraformler ved perfekte konjunktive normalformer (PCN). To måter å redusere en proposisjonell algebraformel til perfekt normal form
§ 6. Logisk rekkefølge av formler.
Konseptet med logisk konsekvens. Tegn på logisk konsekvens. To egenskaper med logisk konsekvens. Konsistens og ekvivalens av formler. Regler for logisk slutning. En annen måte å sjekke logiske implikasjoner. Finne konsekvenser fra gitte premisser. Finne premisser for en gitt konsekvens.
§ 7. Anvendelse av proposisjonalgebra på logisk-matematisk praksis.
Direkte og inverse teoremer. Nødvendige og tilstrekkelige forhold. Det motsatte og det motsatte av det motsatte teoremet. Lov om kontraposisjon. Modifikasjon av strukturen til en matematisk teorem. Metoder for å bevise matematiske teoremer. Deduktiv og induktiv resonnement. Riktig og feil deduktiv resonnement. Løse logiske problemer. Prinsippet om fullstendig disjunksjon. En generalisering av prinsippet om fullstendig disjunksjon.
Kapittel II. Boolske funksjoner.
§8. Sett, relasjoner, funksjoner.
Konseptet med sett. Inkludering og likestilling av sett. Operasjoner på sett. Binære relasjoner og funksjoner. Konseptet med lar forhold.
§ 9. Boolske funksjoner av ett og to argumenter.
Opprinnelsen til boolske funksjoner. Boolske funksjoner fra ett argument. Boolske funksjoner fra to argumenter. Egenskaper for disjunksjon, konjunksjon og negasjon. Egenskaper for ekvivalens, implikasjon og negasjon. Uttrykke noen boolske funksjoner i form av andre
§ 10. Boolske funksjoner av n argumenter.
Konseptet med en boolsk funksjon. Antall boolske funksjoner. Uttrykke boolske funksjoner gjennom konjunksjon, disjunksjon og negasjon. Boolske funksjoner og proposisjonelle algebraformler. Normale former for boolske funksjoner.
§ 11. Systemer med boolske funksjoner.
Komplette systemer med boolske funksjoner. Spesielle klasser av boolske funksjoner. Posts teorem om fullstendigheten av et system av boolske funksjoner
§ 12. Anvendelse av boolske funksjoner på relékontaktkretser.
Søknadsidé. To hovedproblemer i teorien om relékretser.
§ 13. Relékontaktkretser i datamaskiner.
Binær halvadder. En-bits binær adderer. Kryptering og dekryptering.
§ 14. Om noen andre anvendelser av teorien om boolske funksjoner.
Diagnose (gjenkjenning) av sykdommer. Mønstergjenkjenning.
Kapittel III. Formalisert proposisjonskalkyle.
§ 15. Aksiomersystemet og teorien om formell slutning.
Begynnelsen på den aksiomatiske teorien om utsagn: innledende begreper, aksiomsystem, slutningsregel. Konseptet slutning og dets egenskaper. Teorem om deduksjon og konsekvenser av det. Anvendelse av deduksjonsteoremet. Avledede slutningsregler
§ 16. Fullstendighet og andre egenskaper ved formalisert proposisjonskalkyle
Bevisbarhet av en formel og dens identiske sannhet (syntaks og semantikk). Lemma om fradragbarhet. Fullstendighet av formalisert proposisjonskalkyle. Tilstrekkelighetsteorem. Konsistens av formalisert proposisjonell kalkulus. Bestembarhet av formalisert proposisjonskalkyle
§ 17. Uavhengighet av systemet av aksiomer for formalisert proposisjonell kalkulus.
Konseptet om uavhengighet. Uavhengighet av aksiom (A1). Uavhengighet av aksiom (A2). Uavhengighet av aksiom (A3). Uavhengighet av aksiomsystemet
Kapittel IV. Predikatlogikk.
§ 18. Grunnleggende begreper knyttet til predikater.
Konseptet med et predikat. Klassifisering av predikater. Sannhetssettet til et predikat. Ekvivalens og rekkefølge av predikater
§ 19. Logiske operasjoner på predikater.
Negasjon av et predikat. Sammensetning av to predikater. Design for å gå til dikats-siden. Egenskaper for negasjon, konjunksjon og disjunksjon. Implikasjon og ekvivalens av to predikater.
§ 20. Kvantifiseringsoperasjoner på predikater.
Generell kvantifiserer. Eksistens kvantifiserer. Numeriske kvantifiserere. Begrensede kvantifiserere. Logisk firkant
§ 21. Formler for predikatlogikk.
Konseptet med en predikatlogikkformel. Klassifisering av predikatlogiske formler. Tautologier av predikatlogikk
§ 22. Ekvivalente transformasjoner av formler og logisk konsekvens av formler i predikatlogikk
Konseptet med ekvivalens av formler. Redusert form for predikatlogiske formler. Prenex normal form for predikatlogiske formler. Logisk etterfølgelse av predikatlogiske formler
§ 23. Løsningsproblemer for formlers gyldighet og tilfredsstillelse.
Uttalelse av problemet og dets uløselighet i generelt syn. Løse oppgaven for formler på endelige mengder. Et eksempel på en formel som kan tilfredsstilles på et uendelig sett, men som ikke kan tilfredsstilles på et begrenset sett. Tilfredshetsoppløsningsproblemet: påvirkningen av satt kardinalitet og formelstruktur. Løse problemet for formler som inneholder kun én-steds predikatvariabler. Problemet med å løse generell gyldighet og kardinaliteten til settet som formelen vurderes på. Løsning på oppgaven for V-formler og 3-formler
§ 24. Anvendelse av predikatlogikk på logisk-matematisk praksis.
Å skrive på logiske predikater for forskjellige setninger. Sammenligning av predikatlogikk og proposisjonell logikk. Strukturen til matematiske teoremer. Metoder for resonnement: Aristotelisk syllogistisk. Aristotelisk syllogistikk og predikatlogikk. Settteoretisk tolkning av aristotelisk syllogistikk. På andre måter å resonnere på. Prinsippet om fullstendig disjunksjon i predikatform. Metode (fullstendig) matematisk induksjon Nødvendige og tilstrekkelige forhold. Predikatlogikk og settalgebra.
§ 25. Formalisert predikatregning.
Innledende begreper (språk for formalisert predikatregning). System av aksiomer for predikatregning. Uttaksregler. Teorien om formell slutning.
Kapittel V. Uformelle aksiomatiske teorier.
§ 26. Aksiomatisk metode i matematikk og aksiomatiske teorier.
Begrepet aksiomatisk teori. Hvordan aksiomatiske teorier oppstår. Eksempler på aksiomatiske teorier. Tolkninger og modeller av aksiomatisk teori.
§ 27. Egenskaper ved aksiomatiske teorier.
Konsistens. Kategorisk. Uavhengighet av aksiomsystemet. Fullstendighet.
Kapittel VI. Formelle aksiomatiske teorier.
§ 28. Om formelle aksiomatiske teorier.
Om historien til ideen om formell aksiomatisk teori. Begrepet formell aksiomatisk teori. Språk og metaspråk, teoremer og metateoremer for formell teori. Fortolkninger og modeller av formell teori. Semantisk slutning. Metamatematikk (egenskapene til formelle aksiomatiske teorier). Formalisert proposisjonell kalkulus som en formell aksiomatisk teori Formalisering av teorien om aristoteliske syllogismer.
§ 29. Egenskaper ved formalisert predikatregning.
Begrunnelse for aksiomatisering Konsistens av formalisert predikatkalkulus. Gödels teorem om eksistensen av en modell. Fullstendighet og tilstrekkelighet av formalisert predikatregning. Ufullstendighet av formalisert predikatregning i absolutt og snever betydning Kompakthetsteorem.
§ 30. Formelle teorier av første orden.
Første ordens teorier med likhet. Om formelle settteorier. Om formell regning. Om formelle teorier om tallsystemer Om formell geometri. Om formell matematisk analyse. Et generelt syn på prosessen med formalisering av matematisk teori På grensene for den aksiomatiske metoden, metoden for formalisering og logikk.
Kapittel VII. Elementer i teorien om algoritmer.
§31. En intuitiv forståelse av algoritmer.
Algoritmer er rundt oss. Uformelt konsept av en algoritme. Behovet for å klargjøre konseptet med en algoritme.
§ 32. Turingmaskiner.
Definisjon av en Turing-maskin Anvendelse av Turing-maskiner på ord. Konstruksjon av Turing-maskiner. Turing-beregnbare funksjoner. Riktig beregnbarhet av funksjoner på en Turing-maskin. Sammensetning av Turing-maskiner. Turings avhandling (hovedhypotesen til teorien om algoritmer). Turing-maskiner og moderne elektroniske datamaskiner.
§ 33. Rekursive funksjoner.
Opprinnelsen til rekursive funksjoner. Grunnleggende begreper i teorien om rekursive funksjoner og Kirkens avhandling. Primitivt rekursive funksjoner. Primitiv rekursivitet av predikater. Turing-beregning av primitive rekursive funksjoner. Ackermann funksjoner. Minimeringsoperatør. Generelt rekursive og delvis rekursive funksjoner. Turing-beregning av delvis rekursive funksjoner. Delvis rekursivitet av Turing-beregnbare funksjoner.
§34. Normale Markov-algoritmer.
Markov-bytter. Normale algoritmer og deres anvendelse på ord. Normalt beregnelige funksjoner og Markovs normaliseringsprinsipp. Klassen til alle normalt beregnbare funksjoner faller sammen med klassen til alle Turing-beregnbare funksjoner. Ekvivalens av ulike teorier om algoritmer.
§ 35. Løsbarhet og opptelling av sett.
§ 36. Uløselige algoritmiske problemer.
Nummerering av algoritmer. Turing maskinnummerering. Eksistensen av Turing-utregnerbare funksjoner. Problemer med å gjenkjenne egenanvendbarhet og anvendelighet. Algoritmisk uløselige problemer i den generelle teorien om algoritmer. Rice sin teorem. Andre eksempler på algoritmisk ubestembarhet.
§ 37. Gödels teorem om ufullstendighet i formell regning.
Formelle aksiomatiske teorier og heltall. Formell aritmetikk og dens egenskaper. Gödels ufullstendighetsteorem. Gödel og hans rolle i matematisk logikk på 1900-tallet. .
Kapittel VIII. Matematisk logikk og datamaskiner, informatikk, kunstig intelligens.
* § 38. Matematisk logikk og programvare datamaskiner.
Teorien om algoritmer og matematisk logikk er det grunnleggende grunnlaget for programmering. Beskrivelse av dataprogrammer som bruker matematisk logikk. Beskriv programmering og analyser dens konsepter ved hjelp av matematisk logikk. Verifikasjon (bevis på korrekthet) av programmer ved hjelp av matematisk logikk.
§ 39. Bruk av datamaskiner for å bevise teoremer av matematisk logikk.
"Logic Theorist"-programmet og programmer nær det. Oppløsningsmetoden for å bevise teoremer i proposisjonskalkyle og predikatregning.
§ 40. Fra matematisk logikk til logisk programmering.
Fremveksten av PROLOG-språket og dets utvikling. generelle egenskaper PROLOG språk Kort beskrivelse PROLOG språk og eksempler. Bruksområder for PROLOG-språket.
§41. Matematisk logikk og informatikk.
Generelt konsept om databasen. Relasjonsdatabase og spørringslogikk i den.
§ 42. Matematisk logikk og kunstige intelligenssystemer Utviklingshistorie og faget kunstig intelligens som vitenskap. Representasjon av kunnskap i kunstige intelligenssystemer. Ekspertsystemer. PROLOG-språk i kunstig intelligens-systemer. Kan en maskin tenke?
Konklusjon: Er logikken allmektig når det gjelder å kjenne tenkningens lover?
Bibliografi.

Logikk og intuisjon.
Menneskelig mental aktivitet er en kompleks og mangefasettert prosess som skjer på både bevisst og ubevisst (underbevisst) nivå. Dette er det høyeste nivået av menneskelig erkjennelse, evnen til adekvat å reflektere objekter og virkelighetsfenomener, dvs. å finne sannheten.

Logikk og intuisjon er to motstridende og uløselig forbundne egenskaper ved menneskelig tenkning. Logisk (deduktiv) tenkning er forskjellig ved at den alltid leder fra sanne premisser til en sann konklusjon, uten å stole på erfaring, intuisjon og andre. eksterne faktorer. Intuisjon (fra latin intuitio - "nær gransking") er evnen til å forstå sannheten ved direkte å observere den uten begrunnelse ved å bruke logisk strenge bevis. Dermed er intuisjon en slags antipode, en motvekt til logikk og strenghet.

Den logiske delen av tankeprosessen skjer på bevissthetsnivået, den intuitive delen - på det underbevisste nivået.
Utviklingen av naturvitenskap og spesielt matematikk er utenkelig uten intuisjon. Det er to typer intuisjon i vitenskapelig kunnskap1: intuisjon-vurdering og intuisjon-gjetting. Intuisjonsdom (eller filosofisk intuisjonsdom) er preget av det faktum at i dette tilfellet utføres den direkte sannhetsoppfatningen, den objektive sammenhengen av ting, ikke bare uten logisk strenge bevis, men slikt bevis for en gitt sannhet eksisterer ikke og kan i prinsippet ikke eksistere. Intuisjonsvurdering utføres som en enkelt (engangs) syntetisk integrert handling av generaliserende karakter. Dette er nettopp naturen til logisk ubeviselige utsagn i tesene til Turing, Church og Markov vurdert i teorien om algoritmer.

Last ned e-boken gratis i et praktisk format, se og les:
Last ned boken Mathematical logic and theory of algorithms, Igoshin V.I., 2008 - fileskachat.com, rask og gratis nedlasting.

Federal Agency for Education

TOMSK STATE UNIVERSITY OF CONTROL SYSTEMS AND RADIO ELECTRONICS (TUSUR)

Institutt for automatisering av informasjonsbehandling

Jeg bekrefter:

Hode avdeling IDF

Professor

Jepp. Ekhlakov

"__" _____________2007

Retningslinjer

til gjennomføring praktisk jobb ved disiplin

"Matematisk logikk og teori om algoritmer"

for studenter med spesialitet 230102 –

"Automatisk informasjonsbehandling og kontrollsystemer"

Utviklere:

Kunst. lærer ved avdelingen IDF

AT. Peremitina

Tomsk – 2007

Praktisk leksjon nr. 1 “Proposisjonelle algebraformler” 3

Praktisk leksjon nr. 2 «Ekvivalente transformasjoner av proposisjonelle algebraformler» 10

Praktisk leksjon nr. 3 "Normale formler" 12

Praktisk leksjon nr. 4 «Logisk resonnement» 14

Praktisk leksjon nr. 5 "Formler for predikatlogikk" 18

Øv #6 boolske funksjoner 23

Øv #7 Delvis rekursive funksjoner 28

Øv #8 Turing-maskiner 34

Praktisk leksjon nr. 1 "Proposisjonelle algebraformler"

Læren om utsagn – utsagns algebra, eller logikkens algebra – er den enkleste logiske teorien. Atomforestillingen om proposisjonalgebraen er uttalelse - en deklarativ setning som en uttalelse om sannhet eller usannhet gir mening i forhold til.

Et eksempel på en sann uttalelse: "Jorden dreier seg rundt solen." Et eksempel på en falsk uttalelse: "3 > 5". Ikke hver setning er et utsagn; utsagn inkluderer ikke spørrende og utropssetninger. Setningen "Grøt er en velsmakende rett" er ikke en uttalelse, siden det ikke kan være konsensus om det er sant eller usant. Setningen "Det er liv på Mars" bør betraktes som en uttalelse, siden den objektivt sett er enten sann eller usann, selv om ingen ennå vet hvilken.

Siden emnet for studiet av logikk bare er sannhetsverdiene til utsagn, introduseres bokstavbetegnelsene A, B, ... eller X,Y... for dem.

Hver påstand anses å være enten sann eller usann. For korthets skyld skriver vi 1 i stedet for den sanne verdien, og 0 i stedet for den falske verdien. For eksempel, X = "Jorden roterer rundt solen" og Y = "3 > 5", med X = 1 og Y = 0. Et utsagn kan ikke være både sant og usant .

Utsagn kan være enkle eller sammensatte. Utsagnene "jorden kretser rundt solen" og "3 > 5" er enkle. Sammensatte utsagn er dannet av enkle utsagn ved bruk av koblinger av naturlig (russisk) språk NOT, AND, OR, IF-THEN, THEN-AND-BARE-THEN. Når du bruker bokstavnotasjoner for utsagn, erstattes disse forbindelsene med spesielle matematiske symboler, som kan betraktes som symboler logiske operasjoner.

Nedenfor viser tabell 1 alternativer for symboler for å betegne koblinger og navnene på de tilsvarende logiske operasjonene.

Benektelse (inversjon) utsagn X er et utsagn som er sant hvis og bare hvis X usann (angitt med eller , står det «ikke X” eller “det er ikke sant det X”).

Konjunksjon
to påstander er en påstand som er sann hvis og bare hvis begge påstandene er sanne X Og Y. Denne logiske operasjonen tilsvarer koblingen av uttalelser med fagforeningen "og".

Disjunksjon
to uttalelser X Og Y En påstand kalles falsk hvis og bare hvis begge påstandene X Og Y falsk. I dagligtale tilsvarer denne logiske operasjonen konjunksjonen "eller" (ikke det eksklusive "eller").

Ved implikasjon to uttalelser X Og Y er en påstand som er falsk hvis og bare hvis X sant, men Y– usann (betegnet
; leser " X innebærer Y", "Hvis X, Det Y”). Operandene til denne operasjonen har spesielle navn: X- pakke, Y- konklusjon.

Ekvivalens to uttalelser X Og Y er et utsagn som er sant hvis og bare hvis sannheten verdsetter X Og Y er de samme (betegnelse:
).

Tabell 1. Logiske operasjoner

Operandene til logiske operasjoner kan bare ha to verdier: 1 eller 0. Derfor kan hver logisk operasjon , &,,, enkelt spesifiseres ved hjelp av en tabell, som indikerer verdien av resultatet av operasjonen avhengig av verdiene av operandene. Denne tabellen kalles sannhetstabell (Tabell 2).

Tabell 2. Sannhetstabell over logiske operasjoner

Ved å bruke de logiske operasjonene definert ovenfor, kan man konstruere fra enkle utsagn proposisjonelle logiske formler som representerer forskjellige sammensatte utsagn. Den logiske betydningen av et sammensatt utsagn avhenger av strukturen til utsagnet, uttrykt med formelen, og de logiske verdiene til de elementære utsagnene som danner den.

For systematisk studie av formler som uttrykker utsagn, introduseres variable utsagn P, P 1 , P 2 , ..., P N, tar verdier fra settet (0, 1).

Proposisjonell logisk formel F (P 1 , P 2 ,..., P N) kalles en tautologi eller identisk med sann hvis verdien for noen verdier P 1 , P 2 ,..., P N det er 1 (sant). Formler som evalueres til sann for minst ett sett av en liste med variabler kalles gjennomførbart . Formler som evalueres til usann for en hvilken som helst variabelverdi kalles motsetninger (identisk usant, umulig).

Forfatter: Guts A.K.
Utgiver: O.: Heritage
Utgivelsesår: 2003
Sider: 108
ISBN 5-8239-0126-7
Lese:
Nedlasting: matematicheskayalogika2003.djvu

OMSK STATE UNIVERSITY FAKULTET DATAVITENSKAP INSTITUTT
KYBERNETIKK
A.K. Guts
Matematisk logikk og teori om algoritmer
Omsk 2003
VVK 60 UDC 53:630.11
Guts A.K. Matematisk logikk og teori for algoritmer: Opplæringen. -
Omsk: Heritage Publishing House. Dialog-Sibir, 2003. - 108 s.
ISBN 5 - 8239 - 0126 - 7
Læreboken er viet presentasjon av grunnlaget for matematisk logikk og teori
algoritmer. Grunnlaget for manualen er bygd opp av forelesningsnotater som ble gitt
andreårsstudenter ved informatikkavdelingen i Omsk
statlig universitet i 2002.
For studenter som studerer i spesialitet 075200 - "Datamaskin
sikkerhet" og spesialitet 220100 - "Datamaskiner,
komplekser, systemer og nettverk."
ISBN 5 - 8239 - 0126 - 7
(c) Omsk State University, 2003
Innholdsfortegnelse
I Logic 7
1 Klassisk logikk 8
1.1. Proposisjonell logikk........................................ 8
1.1.1. Uttalelser ................................................... 8
1.1.2. Grunnleggende logiske lover........................ 9
1.1.3. Russells logiske paradoks................... 10
1.1.4. Algebra (logikk) av proposisjoner............... 11
1.1.5. Relédiagrammer................................... 12
1.1.6. Ekvivalente formler................................... 14
1.1.7. Boolsk algebra................................ 15
1.1.8. Sanne og generelt gyldige formler........... 15
1.1.9. Løsbarhetsproblemet........................ 15
1.1.10. Logisk konsekvens...................... 16
1.1.11. Syllogismer................................... 17
1.2. Predikatlogikk........................................ 17
1.2.1. Predikater og formler........................ 18
1.2.2. Tolkninger................................... 19
1.2.3. Sannhet og tilfredsstillelse av formler. Modeller,
generell gyldighet, logisk konsekvens........ 20
1.2.4. Gottlob Frege........................ 21
1.2.5. Skolemov funksjoner
og skolemisering av formler......................... 22
1.3. Oppløsningsmetode........................................... 25
1.3.1. Metode for oppløsninger i logikk
uttalelser................................ 25
1.3.2. Metode for oppløsninger i logikk
predikater........................................ 29
3
4
Innholdsfortegnelse
2 Formelle teorier (kalkulus) 31
2.1. Definisjon av formell teori, eller kalkulus. . 32
2.1.1. Bevis. Konsistens av teorien.
Teoriens fullstendighet................................... 32
2.2. Proposisjonskalkyle........................ 33
2.2.1. Språk- og avledningsregler for proposisjonskalkyle
............................................. 33
2.2.2. Et eksempel på et bevis på teoremet................... 35
2.2.3. Fullstendighet og konsistens
proposisjonskalkyle........................ 36
2.3. Predikatregning ................................... 37
2.3.1. Språk og slutningsregler for predikatregning 37
2.3.2. Fullstendighet og konsistens
predikatregning........................ 39
2.4. Formell aritmetikk................................... 39
2.4.1. Egalitære teorier........................ 39
2.4.2. Språk og regler for avledning av formell regning
.............................................. 39
2.4.3. Konsistens av formell
aritmetikk. Gentzens teorem................... 40
2.4.4. Gödels ufullstendighetsteorem................................... 41
2.4.5. Kurt Gödel................................... 42
2.5. Automatisk utledning av teoremer................................... 43
2.5.1. S.Yu. Maslov................................ 43
2.6. Logisk programmering................................... 45
2.6.1. Logisk program........................ 46
2.6.2. Logiske programmeringsspråk... 49
3 Ikke-klassiske logikker 50
3.1. Intuisjonistisk logikk................................... 50
3.2. Uklar logikk........................................... 51
3.2.1. Uklare delsett................................... 51
3.2.2. Operasjoner på fuzzy
delsett........................................ 52
3.2.3. Egenskaper til et sett med fuzzy
delsett........................................ 53
3.2.4. Uklar proposisjonell logikk................................ 54
3.2.5. Uklare relékretser........... 56
3.3. Modal logikk................................... 56
3.3.1. Typer av modalitet................................... 57
Innholdsfortegnelse
5
3.3.2. Kalkulus 1 og T (Feis-von Wright)........ 57
3.3.3. Beregning S4, S5
og Brouwers kalkulus........................ 58
3.3.4. Betydningen av formler........................ 59
3.3.5. Kripkes semantikk........................ 60
3.3.6. Andre tolkninger av modaler
tegn................................... 62
3.4. Georg von Wright................................... 62
3.5. Timinglogikk................................... 62
3.5.1. Pryors tidslogikk................................ 63
3.5.2. Lemmons tidsmessige logikk................................ 64
3.5.3. Von Wrights tidsmessige logikk................... 64
3.5.4. Timing Logic Application
til programmering........................ 65
3.5.5. Pnuelis tidslogikk................... 67
3.6. Algoritmiske logikk................................... 70
3.6.1. Konstruksjonsprinsipper
1 >

Bøker. Last ned DJVU-bøker, PDF gratis. Gratis digitalt bibliotek
A.K. Guts, matematisk logikk og teori om algoritmer

Du kan (programmet vil merke gul)
Du kan se en liste over bøker om høyere matematikk sortert alfabetisk.
Du kan se en liste over bøker om høyere fysikk, sortert alfabetisk.

• Last ned boken gratis, volum 556 KB, djvu-format (moderne lærebok)

Damer og herrer!! For å laste ned filer av elektroniske publikasjoner uten "feil", klikk på den understrekede lenken med filen HØYRE museknapp, velg en kommando "Lagre målet som..." ("Lagre objekt som...") og lagre den elektroniske publikasjonsfilen på din lokale datamaskin. Elektroniske publikasjoner presenteres vanligvis i Adobe PDF- og DJVU-formater.

I. Logikk
1. Klassisk logikk
1.1. Proposisjonell logikk
1.1.1. Uttalelser
1.1.2. Grunnleggende logiske lover
1.1.3. Russells logiske paradoks
1.1.4. Proposisjonalgebra (logikk)
1.1.5. Relédiagrammer
1.1.6. Tilsvarende formler
1.1.7. boolsk algebra
1.1.8. Sanne og generelt gyldige formler
1.1.9. Løsbarhetsproblem
1.1.10. Logisk konsekvens
1.1.11. Syllogismer
1.2. Predikatlogikk
1.2.1. Predikater og formler
1.2.2. Tolkninger
1.2.3. Sannhet og tilfredsstillelse av formler. Modeller, generell gyldighet, logisk konsekvens
1.2.4. Gottlob Frege
1.2.5. Skolemov funksjoner
og skolemisering av formler
1.3. Oppløsningsmetode
1.3.1. Oppløsningsmetode i proposisjonell logikk
1.3.2. Oppløsningsmetode i predikatlogikk

2. Formelle teorier (kalkulus)
2.1. Definisjon av formell teori, eller kalkulus
2.1.1. Bevis. Konsistens av teorien. Teoriens fullstendighet
2.2. Proposisjonskalkyle
2.2.1. Språk- og avledningsregler for proposisjonskalkyle
2.2.2. Eksempel på bevis for teoremet
2.2.3. Fullstendighet og konsistens av proposisjonskalkyle
2.3. Predikatregning
2.3.1. Språk og slutningsregler for predikatregning
2.3.2. Fullstendighet og konsistens av predikatregning
2.4. Formell aritmetikk
2.4.1. Egalitære teorier
2.4.2. Språk og regler for avledning av formell regning
2.4.3. Konsistens av formell aritmetikk. Gentzens teorem
2.4.4. Gödels ufullstendighetsteorem
2.4.5. Kurt Gödel
2.5. Automatisk utledning av teoremer
2.5.1. S.Yu. Maslov
2.6. Logisk programmering
2.6.1. Logisk program
2.6.2. Logiske programmeringsspråk

3. Ikke-klassiske logikker
3.1. Intuisjonistisk logikk
3.2. Uklar logikk
3.2.1. Uklare undergrupper
3.2.2. Operasjoner på uklare undergrupper
3.2.3. Egenskaper for et sett med uklare delsett
3.2.4. Uklar proposisjonell logikk
3.2.5. Uklare relédiagrammer
3.3. Modal logikk
3.3.1. Typer modalitet
3.3.2. Kalkulus 1 og T (Feis-von Wright)
3.3.3. Calculus S4, S5 og Wrauer calculus
3.3.4. Betydningen av formler
3.3.5. Kripke semantikk
3.3.6. Andre tolkninger av modaler
3.4. Georg von Wright
3.5. Temporal logikk
3.5.1. Priors tidsmessige logikk
3.5.2. Lemmons tidsmessige logikk
3.5.3. Von Wrights tidsmessige logikk
3.5.4. Anvendelse av timinglogikk til programmering
3.5.5. Pnuelis tidsmessige logikk
3.6. Algoritmisk logikk
3.6.1. Prinsipper for å konstruere algoritmisk logikk
3.6.2. Charles Hoare
3.6.3. Algoritmisk Hoare-logikk

II. Algoritmer
4. Algoritmer
4.1. Konseptet med en algoritme og en beregningsbar funksjon
4.2. Rekursive funksjoner
4.2.1. Primitivt rekursive funksjoner
4.2.2. Delvis rekursive funksjoner
4.2.3. Kirkens avhandling
4.3. Turing-Post maskin
4.3.1. Funksjonsberegninger på en Turing-Post-maskin
4.3.2. Regneeksempler
4.3.3. Turings avhandling
4.3.4. Universal maskin Turing-Post
4.4. Alan Turing
4.5. Emil Post
4.6. Effektive algoritmer
4.7. Algoritmisk uløselige problemer

5. Kompleksiteten til algoritmer
5.1. Forstå kompleksiteten til algoritmer
5.2. Problemklassene P og NP
5.2.1. Problemklasse P
5.2.2. Problemklasse NP
5.2.3. Ikke-deterministisk Turing-maskin
5.3. Om begrepet kompleksitet
5.3.1. Tre typer vanskeligheter
5.3.2. Fire kategorier av tall ifølge Kolmogorov
5.3.3. Kolmogorovs avhandling
5.4. A.N. Kolmogorov

6. Algoritmer av virkeligheten
6.1. Generator virtuell virkelighet
6.2. Turing-prinsippet
6.3. Logisk mulige miljøer i Cantgoutou

Kort oppsummering av boken

Læreboken er viet presentasjonen av det grunnleggende om matematisk logikk og teorien om algoritmer. Grunnlaget for manualen består av forelesningsnotater som ble gitt til andreårsstudenter ved Institutt for informatikk ved Omsk State University i 2002. For studenter som studerer i spesialiteten "Datasikkerhet" og i spesialiteten "Datamaskiner, komplekser, systemer og nettverk."

Hva er vitenskapen om logikk? Dette er en teori som lærer hvordan man kan resonnere riktig, trekke konklusjoner og konklusjoner riktig, noe som resulterer i korrekte (riktige) utsagn. Derfor må logikk som vitenskap inneholde en liste med regler for å få korrekte utsagn. Et slikt sett med regler og konklusjoner kalles en liste over syllogismer. Et utsagn er et utsagn om objektene som studeres som har en entydig og presist definert betydning. På russisk er en uttalelse en deklarativ setning, som kan sies å fortelle oss noe sant eller noe helt usant. Derfor kan et utsagn enten være sant eller usant.

Bøker, bøker last ned, last ned bok, bøker online, les online, last ned bøker gratis, les bøker, les bøker på nettet, les, bibliotek på nettet, bøker lest, les gratis på nettet, les bøker gratis, e-bok, les online bøker, beste bøker matematikk og fysikk, interessante bøker matematikk og fysikk, e-bøker, bøker gratis, bøker for gratis nedlasting, last ned bøker for gratis matematikk og fysikk, last ned bøker gratis i sin helhet, nettbibliotek, last ned bøker gratis, les bøker på nettet gratis uten registrering matematikk og fysikk, les bøker på nettet gratis matematikk og fysikk, elektronisk bibliotek matematikk og fysikk, bøker å lese nettmatematikk og fysikk, verden av bøker matematikk og fysikk, les gratis matematikk og fysikk, nettbibliotek matematikk og fysikk, les bøker matematikk og fysikk, bøker på nett gratis matematikk og fysikk, populære bøker matematikk og fysikk, bibliotek med gratis bøker matematikk og fysikk, last ned e-bok matematikk og fysikk, gratis bibliotek online matematikk og fysikk, e-bøker nedlasting, lærebøker online matematikk og fysikk, bibliotek e-bøker matematikk og fysikk, last ned e-bøker gratis uten registrering matematikk og fysikk, gode bøker matematikk og fysikk, last ned bøker i fullstendig matematikk og fysikk, elektronisk bibliotek les gratis matematikk og fysikk, elektronisk bibliotek last ned gratis matematikk og fysikk, nettsteder for nedlasting bøker matematikk og fysikk , smarte bøker matematikk og fysikk, søk etter bøker matematikk og fysikk, last ned e-bøker gratis matematikk og fysikk, e-bok nedlasting matematikk og fysikk, de beste bøkene matematikk og fysikk, elektronisk bibliotek gratis matematikk og fysikk, les online gratis bøker matematikk og fysikk, nettsted for matematikk og fysikkbøker, elektronisk bibliotek, nettbøker å lese, elektronisk bok for matematikk og fysikk, nettsted for nedlasting av bøker gratis og uten registrering, gratis nettbibliotek matematikk og fysikk, hvor kan du laste ned matematikk og fysikk bøker gratis, les bøker gratis og uten registrering matematikk og fysikk, lærebøker last ned matematikk og fysikk, last ned gratis e-bøker matematikk og fysikk, last ned gratis bøker i sin helhet, bibliotek online gratis, beste e-bøker matematikk og fysikk, nettbibliotek for bøker matematikk og fysikk, last ned e-bøker gratis uten registrering, nettbibliotek nedlasting gratis, hvor kan du laste ned gratis bøker, gratis elektroniske biblioteker, gratis e-bøker, gratis elektroniske biblioteker, nettbibliotek gratis, gratis til lese bøker, bøker på nett gratis å lese, lese gratis på nettet, interessante bøker å lese matematikk og fysikk på nettet, lesebøker på nett matematikk og fysikk , elektronisk elektronisk bibliotek matematikk og fysikk, gratis bibliotek med elektroniske bøker matematikk og fysikk, nettbibliotek å lese, les matematikk og fysikk gratis og uten registrering, finn en bok matematikk og fysikk, katalog over bøker matematikk og fysikk, last ned bøker på nettet for gratis matematikk og fysikk, internettbibliotek matematikk og fysikk, last ned gratis bøker uten registrering matematikk og fysikk, hvor du kan laste ned bøker for gratis matematikk og fysikk, hvor du kan laste ned bøker, nettsteder for gratis nedlasting av bøker, online lese, bibliotek lese, bøker lese online gratis uten registrering, bøker bibliotek, gratis bibliotek online, nettbibliotek lese gratis, lese bøker gratis og uten registrering, elektronisk bibliotek last ned bøker gratis, les online gratis.

,
Siden 2017 har vi fornyet mobilversjonen av nettsiden for mobiltelefoner (forkortet tekstdesign, WAP-teknologi) - den øverste knappen i øvre venstre hjørne av nettsiden. Hvis du ikke har tilgang til Internett via en personlig datamaskin eller Internett-terminal, kan du bruke mobiltelefonen til å besøke nettsiden vår (forkortet design) og om nødvendig lagre dataene fra nettsiden til minnet på mobiltelefonen din. Lagre bøker og artikler til din mobiltelefon (Mobilt Internett) og last dem ned fra telefonen til datamaskinen. Praktisk nedlasting av bøker via en mobiltelefon (til telefonminnet) og til datamaskinen via et mobilt grensesnitt. Rask Internett uten unødvendige tagger, gratis (til prisen av Internett-tjenester) og uten passord. Materialet er kun gitt til informasjonsformål. Direkte lenker til bokfiler og artikler på nettstedet og salg av disse av tredjeparter er forbudt.

Merk. En praktisk tekstlenke for fora, blogger, sitering av nettstedmateriale, html-koden kan kopieres og enkelt limes inn på nettsidene dine når du siterer materiale fra nettstedet vårt. Materialet er kun gitt til informasjonsformål. Du kan også lagre bøker på mobiltelefonen din via Internett (det er mobilversjon nettsted - lenke øverst til venstre på siden) og last dem ned fra telefonen til datamaskinen. Direkte lenker til bokfiler er forbudt.