Boeken. Download DJVU-boeken, PDF gratis

TECHNISCHE UNIVERSITEIT KAZAN hen. A. N. Tupoleva

Sh. I. Galiev

WISKUNDE LOGICA EN THEORIE VAN ALGORITHMEN

TUTORIAL

Kazan 2002

Galiev Sh. I. Wiskundige logica en theorie van algoritmen. - Kazan: Uitgeverij van KSTU. A.N. Toepolev. 2002. - 270 d.

ISBN 5-93629-031-X

De handleiding bevat de volgende paragrafen. De logica van proposities en predikaten met toepassingen, inclusief de oplossingsmethode en elementen van de implementatie ervan in de PROLOG-taal. Klassieke calculus (van proposities en predikaten) en elementen van niet-klassieke logica: driewaardige en meerwaardige logica, modale, temporele en vage logica. Theorie van algoritmen: normale algoritmen, Turingmachines, recursieve functies en hun relaties. Het concept van computationele complexiteit, verschillende (naar complexiteit) klassen van problemen en voorbeelden van dergelijke problemen.

Alle hoofdstukken zijn voorzien van controlevragen en oefeningen, opties voor typische taken en testen voor zelfbeheersing van de beheersing van de stof worden gegeven.

De handleiding is bedoeld voor studenten van technische universiteiten in de specialiteit 2201 van de richting "Informatica en Computer Engineering" en kan worden gebruikt voor de specialiteit 2202 en andere specialiteiten op dit gebied.

INVOERING

Logica wordt meestal begrepen als de wetenschap van methoden van bewijs en weerlegging. Wiskundige logica is logica die is ontwikkeld met behulp van wiskundige methoden.

Door de methoden van bewijzen en weerleggingen te bestuderen, is logica in de eerste plaats geïnteresseerd in de vorm van het verkrijgen van ware conclusies, en niet in de inhoud van premissen en conclusies in deze of gene redenering. Beschouw bijvoorbeeld de volgende twee uitgangen:

1. Alle mensen zijn sterfelijk. Socrates is een man. Daarom is Socrates sterfelijk.

2. Alle kittens houden van spelen. Moura is een kitten. Daarom houdt Moura van spelen.

Beide conclusies hebben dezelfde vorm: alle A zijn B, C is A; daarom is C B. Deze conclusies zijn waar vanwege hun vorm, ongeacht de inhoud, ongeacht of de premissen en conclusies op zichzelf waar of onwaar zijn. Het systematisch formaliseren en catalogiseren van correcte redeneringen is een van de belangrijkste taken van de logica. Als in dit geval het wiskundige apparaat wordt gebruikt en het onderzoek voornamelijk is gewijd aan de studie van wiskundig redeneren, dan is deze logica wiskundige logica (formele logica). Deze definitie is geen strikte (exacte) definitie. Om het onderwerp en de methode van wiskundige logica te begrijpen, kun je het beste beginnen met het bestuderen ervan.

Wiskundige logica begon lang geleden vorm te krijgen. De oorsprong van zijn ideeën en methoden vond plaats in het oude Griekenland, het oude India en het oude China vanaf ongeveer de 6e eeuw. BC e. Reeds in deze periode probeerden wetenschappers de keten van wiskundige bewijzen in zo'n keten te ordenen dat de overgang van de ene schakel naar de andere geen twijfel zou laten en universele erkenning zou krijgen. Reeds in de vroegste manuscripten die tot ons zijn gekomen, is de 'canon' van de wiskundige presentatiestijl stevig verankerd. Vervolgens ontvangt hij de definitieve voltooiing van de grote klassiekers: Aristoteles, Euclides, Archimedes. Het concept van bewijs voor deze auteurs verschilt niet van het onze.

Logica als onafhankelijke wetenschap vindt zijn oorsprong in de studies van Aristoteles (384 - 322 v. Chr.). De grote filosoof van de oudheid, Aristoteles, voerde een encyclopedische systematisering uit van oude kennis op alle gebieden van de toen bestaande wetenschap. De logische studies van Aristoteles worden voornamelijk gepresenteerd in zijn twee werken "First Analytics" en "Second Analytics", verenigd onder de algemene titel "Organon" (Instrument of Knowledge).

Van bijzonder belang is het grote belang voor de vorming en ontwikkeling van wiskundige logica van een van de meest briljante prestaties in de geschiedenis van de mensheid, namelijk de transformatie van geometrie in een exact deductief systeem in het werk van Euclides (330 - 275 v.Chr.) "Begin". Het was deze deductieve benadering met een duidelijk besef van doelen en methoden die de basis vormde voor de ontwikkeling van het filosofische en wiskundige denken in de daaropvolgende eeuwen.

Ook van groot belang voor de vorming en ontwikkeling van logica waren prestaties in de algebra (Bule-algebra) en in andere wiskundige disciplines, ook weer in de meetkunde (de creatie van niet-Euclidische meetkunde - Lobachevsky-Gauss-Bolyai-meetkunde). Een kort overzicht van de vorming van wiskundige logica is te vinden in.

Vele en vele wetenschappers namen deel aan de vorming en ontwikkeling van wiskundige logica, zowel in de oudheid als in de Middeleeuwen en de daaropvolgende tijden.

Fundamentele en toegepaste betekenis van wiskundige logica

Het fundamentele belang van wiskundige logica is de onderbouwing van de wiskunde (analyse van de grondslagen van de wiskunde).

De toegepaste waarde van wiskundige logica is momenteel erg hoog. Wiskundige logica wordt gebruikt voor de volgende doeleinden:

analyse en synthese (constructie) van digitale computers en andere discrete automaten, waaronder intelligente systemen;

analyse en synthese van formele en machinetalen, voor de analyse van natuurlijke taal;

analyse en formalisering van het intuïtieve concept van berekenbaarheid;

het bestaan ​​​​van mechanische procedures achterhalen voor het oplossen van problemen van een bepaald type;

analyse van computationele complexiteitsproblemen.

Ook bleek de wiskundige logica nauw verbonden te zijn met een aantal vraagstukken van taalkunde, economie, psychologie en filosofie.

Deze handleiding schetst de basisconcepten van wiskundige logica en de theorie van algoritmen. Het materiaal gepresenteerd in de handleiding

komt overeen met de staatsonderwijsstandaard voor de richting "Informatica en computertechniek" en kan worden gebruikt voor studenten die in verschillende specialiteiten van deze richting studeren.

Bij het schrijven van de handleiding is gebruik gemaakt van literatuur en natuurlijk zijn er ook andere bronnen gebruikt. De literatuurlijst bevat boeken die voor een leergierige en veeleisende student wenselijk zijn om te bekijken.

In de handleiding bevat elk hoofdstuk vragen voor zelftesten van theoretisch materiaal en oefeningen die zijn ontworpen om probleemoplossende vaardigheden te ontwikkelen en de kennis over het gepresenteerde onderwerp te verdiepen. Daarnaast biedt de handleiding opties voor typische taken en tests voor zelfcontrole van de assimilatie van het materiaal.

Het voorgestelde leerboek (2e ed., stereotype) vormt de basis van een set voor de cursus wiskundige logica en de theorie van algoritmen, die ook een verzameling problemen omvat (Igoshin V.I. Taken en oefeningen in wiskundige logica en de theorie van algoritmen) .

De fundamenten van de theorie worden in detail beschreven, de richtingen van penetratie van logica in de fundamenten van algebra, analyse, geometrie worden getoond, het materiaal van de schoolwiskundecursus wordt gebruikt voor de logische analyse, de relatie van wiskundige logica met computers, informatica en kunstmatige-intelligentiesystemen wordt gekenmerkt.

Invoering. Wiskundige logica in het systeem van het moderne onderwijs.
Logica en intuïtie. Logische traditionele en wiskundige logica. Een beetje geschiedenis. Wiskundige logica - logica of wiskunde? Wiskundige logica in het wiskundeonderwijs. Wiskundige logica en moderne computers.
Hoofdstuk I. Algebra van uitspraken.
§ 1. Verklaringen en bewerkingen daarop.
Het begrip uiting. Ontkenning van de verklaring. Samenvoeging van twee zinnen. Disjunctie van twee uitspraken. Implicatie van twee uitspraken. Gelijkwaardigheid van twee uitspraken. Vakbonden van de taal en logische bewerkingen (taal en logica). Algemeen overzicht van logische bewerkingen.
§2. Propositionele algebra formules.
Constructie van complexe zinnen. Het concept van een propositiealgebra-formule. De logische betekenis van een samengestelde verklaring. Samenstelling van waarheidstabellen voor formules. Classificatie van formules van propositiealgebra. Denken en wiskundige logica
§ 3. Tautologieën van propositiealgebra.
Over de betekenis van tautologieën. Basis tautologieën. Basisregels voor het verkrijgen van een tautologie.
§ 4. Logische equivalentie van formules.
Het concept van equivalentie van formules. Teken van gelijkwaardigheid van formules. Voorbeelden van equivalente formules. Equivalente transformaties van formules. Gelijkwaardigheid in logica en identiteiten in algebra.
§ 5. Normaalvormen voor propositionele algebraformules.
Het concept van normale vormen. Perfecte normaalvormen. Vertegenwoordiging van propositiealgebra-formules door perfecte disjunctieve normaal (CDN) vormen. Vertegenwoordiging van formules van propositionele algebra door perfect conjunctieve normaal (SKN) vormen. Twee manieren om een ​​propositie-algebra-formule te reduceren tot een perfecte normaalvorm
§ 6. Logisch volgen van formules.
Het concept van een logisch gevolg. Tekenen van een logisch gevolg. Twee eigenschappen van logisch gevolg. Opvolging en equivalentie van formules. Regels voor logisch redeneren. Een andere manier om logisch volgen te controleren. Het vinden van consequenties van deze premissen. Ruimte zoeken voor dit onderzoek.
§ 7. Toepassing van propositiealgebra op de logisch-wiskundige praktijk.
Directe en inverse stellingen. Noodzakelijke en voldoende voorwaarden. Tegengestelde en inverse van de tegenovergestelde stelling. De wet van de tegenpositie. Wijziging van de structuur van de wiskundige stelling. Methoden voor het bewijzen van wiskundige stellingen. Deductief en inductief redeneren. Correcte en onjuiste deductieve redenering. Logische problemen oplossen. Het principe van volledige disjunctie. Een generalisatie van het principe van volledige disjunctie.
Hoofdstuk II. Booleaanse functies.
§acht. Verzamelingen, relaties, functies.
Het concept van een reeks. Inclusie en gelijkheid van sets. Operaties op sets. Binaire relaties en functies. Het concept van een grote relatie.
§ 9. Booleaanse functies van één en twee argumenten.
Oorsprong van booleaanse functies. Booleaanse functies uit één argument. Booleaanse functies van twee argumenten. Eigenschappen van disjunctie, conjunctie en negatie. Eigenschappen van equivalentie, implicatie en ontkenning. Sommige Booleaanse functies uitdrukken in termen van andere
§ 10. Booleaanse functies van n argumenten.
Het concept van een Booleaanse functie. Het aantal booleaanse functies. Expressie van booleaanse functies door middel van conjunctie, disjunctie en negatie. Booleaanse functies en formules van propositiealgebra. Normale vormen van Booleaanse functies.
§ 11. Systemen van Booleaanse functies.
Complete systemen van Booleaanse functies. Speciale klassen van Booleaanse functies. Stelling van Post over de volledigheid van een systeem van Booleaanse functies
§ 12. Toepassing van Booleaanse functies op relaiscontactcircuits.
Toepassing idee. Twee hoofdtaken van de theorie van relaiscontactcircuits.
§ 13. Relaiscontactcircuits in computers.
Binaire halve opteller. Enkele bit binaire opteller. encoder en decoder.
§ 14. Over enkele andere toepassingen van de theorie van Booleaanse functies.
Diagnose (herkenning) van ziekten. Patroonherkenning.
Hoofdstuk III. Geformaliseerde propositiecalculus.
§ 15. Het systeem van axioma's en de theorie van formele gevolgtrekking.
Het begin van de axiomatische propositietheorie: beginconcepten, systeem van axioma's, gevolgtrekkingsregel. Het concept van gevolgtrekking en zijn eigenschappen. De deductiestelling en de gevolgen ervan. Toepassing van de aftrekstelling. Afgeleide gevolgtrekkingsregels
§ 16. Volledigheid en andere eigenschappen van de geformaliseerde propositiecalculus
Bewijsbaarheid van een formule en zijn identieke waarheid (syntaxis en semantiek). Afleidbaarheid Lemma. Volledigheid van de geformaliseerde propositiecalculus. De adequaatheidsstelling. Consistentie van de geformaliseerde propositiecalculus. Beslisbaarheid van de geformaliseerde propositiecalculus
§ 17. Onafhankelijkheid van het systeem van axioma's van de geformaliseerde propositiecalculus.
Het concept van onafhankelijkheid. Onafhankelijkheid van het axioma (A1). Onafhankelijkheid van het axioma (A2). Axioma onafhankelijkheid (A3). Onafhankelijkheid van het axiomasysteem
Hoofdstuk IV. Predikaat logica.
§ 18. Basisbegrippen met betrekking tot predikaten.
Het concept van een predikaat. Classificatie van predikaten. De waarheidsverzameling van het predikaat. Gelijkwaardigheid en volgende predikaten
§ 19. Logische bewerkingen op predikaten.
Predikaat ontkenning. Conjunctie van twee predikaten. Ontwerp om naar de dicat-pagina te gaan. Eigenschappen van negatie, conjunctie en disjunctie. Implicatie en equivalentie van twee predikaten.
§ 20. Kwantificatorbewerkingen op predikaten.
Algemene kwantificator. Bestaan ​​kwantificator. Numerieke kwantoren. Beperkte kwantoren. Logisch vierkant
§ 21. Formules van predikatenlogica.
Het concept van een predikaatlogica-formule. Classificatie van predikaatlogica-formules. Tautologieën van predikaatlogica
§ 22. Equivalente transformaties van formules en logische consequentie van formules van predikatenlogica
Het concept van equivalentie van formules. Gereduceerde vorm voor predikaatlogica-formules. Prenex normaalvorm voor predikaatlogica formules. Logisch volgen van predikaatlogica-formules
§ 23. Oplossingsproblemen voor de validiteit en vervulbaarheid van formules.
Verklaring van het probleem en de onoplosbaarheid ervan in het algemeen. Oplossing van het probleem voor formules op eindige verzamelingen. Een voorbeeld van een formule die haalbaar is op een oneindige verzameling en niet uitvoerbaar op een eindige verzameling. Verzadigingsoplossingsprobleem: invloed van set-kardinaliteit en formulestructuur. Het probleem oplossen voor formules die alleen predikaatvariabelen van één plaats bevatten. Het probleem van het oplossen van de geldigheid en kardinaliteit van de verzameling waarop de formule wordt beschouwd. Probleemoplossing voor V-formules en 3-formules
§ 24. Toepassing van predikatenlogica op de logisch-wiskundige praktijk.
Opnemen in de taal van logische predikaten van verschillende zinnen. Vergelijking van predikatenlogica en propositielogica. De structuur van wiskundige stellingen. Redeneermethoden: Aristotelische syllogistiek. Aristotelische syllogistiek en logica van predikaten. Set-theoretische interpretatie van de Aristotelische syllogistic. Over andere manieren van redeneren. Het principe van volledige disjunctie in predikaatvorm. Methode van (volledige) wiskundige inductie Noodzakelijke en voldoende voorwaarden. Predikaatlogica en setalgebra.
§ 25. Geformaliseerde predikaatberekening.
Primaire concepten (taal van geformaliseerde predikatenrekening). Het systeem van axioma's van predikaatrekening. terugtrekking regels. Theorie van formele gevolgtrekking.
Hoofdstuk V. Informele axiomatische theorieën.
§ 26. Axiomatische methode in de wiskunde en axiomatische theorieën.
Het concept van axiomatische theorie. Hoe axiomatische theorieën ontstaan. Voorbeelden van axiomatische theorieën. Interpretaties en modellen van axiomatische theorie.
§ 27. Eigenschappen van axiomatische theorieën.
Samenhang. categorisch. Onafhankelijkheid van het systeem van axioma's. Volledigheid.
Hoofdstuk VI. Formele axiomatische theorieën.
§ 28. Over formele axiomatische theorieën.
Over de geschiedenis van het idee van een formele axiomatische theorie. Het concept van de formele axiomatische theorie. Taal en metataal, stellingen en metatheorems van de formele theorie. Interpretaties en modellen van formele theorie. semantische uitvoer. Metathematica (eigenschappen van formele axiomatische theorieën). Geformaliseerde propositiecalculus als een formele axiomatische theorie.Formalisering van de theorie van Aristotelische syllogismen.
§ 29. Eigenschappen van de geformaliseerde predikaatberekening.
Rechtvaardiging van de axiomatisering Consistentie van de geformaliseerde predikaatberekening. De stelling van Gödel over het bestaan ​​van een model. Volledigheid en adequaatheid van de geformaliseerde predikaatberekening. Onvolledigheid van de geformaliseerde predikaatberekening in de absolute en enge zin Compactheidsstelling.
§ 30. Formele theorieën van de eerste orde.
Eerste orde theorieën met gelijkheid. Op formele verzamelingentheorieën. Op formeel rekenen. Over formele theorieën over getalsystemen, over formele meetkunde. Over formele wiskundige analyse. Algemene kijk op het proces van formalisering van wiskundige theorie Op de grenzen van de axiomatische methode, de methode van formalisering en logica.
Hoofdstuk VII. Elementen van de theorie van algoritmen.
§31. Intuïtief begrip van algoritmen.
Algoritmen om ons heen. Een informeel begrip van een algoritme. De noodzaak om het concept van een algoritme te verduidelijken.
§ 32. Turingmachines.
Definitie van een Turing-machine Toepassing van Turing-machines op woorden. Turingmachine ontwerp. Turing-berekenbare functies. Correcte berekenbaarheid van functies op een Turingmachine. Samenstelling van Turingmachines. Turing's thesis (een basisvermoeden in de theorie van algoritmen). Turingmachines en moderne elektronische computers.
§ 33. Recursieve functies.
Oorsprong van recursieve functies. Basisconcepten van de theorie van recursieve functies en de stelling van de kerk. Primitieve recursieve functies. Primitieve recursiviteit van predikaten. Turing-berekenbaarheid van primitieve recursieve functies. Ackerman functies. minimalisatie exploitant. Algemene recursieve en gedeeltelijk recursieve functies. Turing-berekenbaarheid van gedeeltelijk recursieve functies. Gedeeltelijke recursiviteit van Turing-berekenbare functies.
§34. Normale Markov-algoritmen.
Markov wissels. Normale algoritmen en hun toepassing op woorden. Normaal berekenbare functies en het Markov-normalisatieprincipe. Samenval van de klasse van alle normaal berekenbare functies met de klasse van alle Turing berekenbare functies. Gelijkwaardigheid van verschillende theorieën van algoritmen.
§ 35. Beslisbaarheid en opsombaarheid van verzamelingen.
§ 36. Onoplosbare algoritmische problemen.
Algoritme nummering. Turingmachine nummering. Bestaan ​​van niet-berekenbare Turing-functies. Problemen met het herkennen van eigen toepasbaarheid en toepasbaarheid. Algoritmisch onoplosbare problemen in de algemene theorie van algoritmen. De stelling van Rice. Andere voorbeelden van algoritmische onbeslisbaarheid.
§ 37. De stelling van Godel over de onvolledigheid van de formele rekenkunde.
Formele axiomatische theorieën en natuurlijke getallen. Formele rekenkunde en zijn eigenschappen. De onvolledigheidsstelling van Gödel. Gödel en zijn rol in de wiskundige logica van de 20e eeuw. .
Hoofdstuk VIII. Wiskundige logica en computers, informatica, kunstmatige intelligentie.
* § 38. Wiskundige logica en computersoftware.
De theorie van algoritmen en wiskundige logica is de fundamentele basis van programmeren. Beschrijving van computerprogramma's met behulp van wiskundige logica. Beschrijving van de programmering en analyse van de concepten met behulp van wiskundige logica. Verificatie (bewijs van juistheid) van programma's met behulp van wiskundige logica.
§ 39. Toepassing van computers voor het bewijs van stellingen van de wiskundige logica.
Het programma "Logica-theoreticus" en programma's die er dichtbij staan. Resolutiemethode voor het bewijzen van stellingen in propositiecalculus en predikatencalculus.
§ 40. Van wiskundige logica naar logisch programmeren.
De opkomst van de PROLOG-taal en de ontwikkeling ervan. Algemene kenmerken van de PROLOG-taal. Korte beschrijving van de PROLOG-taal en voorbeelden. Toepassingsgebieden van de PROLOG-taal.
§41. Wiskundige logica en informatica.
Algemeen concept van de database. Relationele database en querylogica erin.
§ 42. Wiskundige logica en kunstmatige intelligentiesystemen De geschiedenis van ontwikkeling en het onderwerp van kunstmatige intelligentie als wetenschap. Vertegenwoordiging van kennis in kunstmatige-intelligentiesystemen. Expertsystemen. PROLOG-taal in kunstmatige-intelligentiesystemen. Kan een machine denken.
Conclusie: Is logica almachtig in de kennis van de wetten van het denken?
Bibliografie.

Logica en intuïtie.
Menselijke mentale activiteit is een complex en veelzijdig proces dat zowel op het bewuste als op het onbewuste (onderbewuste) niveau plaatsvindt. Dit is het hoogste niveau van menselijke kennis, het vermogen om objecten en fenomenen van de werkelijkheid adequaat weer te geven, d.w.z. om de waarheid te vinden.

Logica en intuïtie zijn twee tegengestelde en onlosmakelijk met elkaar verbonden eigenschappen van het menselijk denken. Logisch (deductief) denken onderscheidt zich doordat het altijd leidt tot een ware conclusie uit ware premissen, zonder te vertrouwen op ervaring, intuïtie en andere externe factoren. Intuïtie (van het Latijnse intuitio - "nauw staren") is het vermogen om de waarheid te begrijpen door directe observatie ervan zonder onderbouwing met behulp van logisch rigoureus bewijs. Intuïtie is dus een soort antipode, een tegenwicht tegen logica en strengheid.

Het logische deel van het denkproces vindt plaats op het niveau van bewustzijn, het intuïtieve deel - op het onderbewuste niveau.
De ontwikkeling van de wetenschap en vooral de wiskunde is ondenkbaar zonder intuïtie. Er zijn twee soorten intuïtie in wetenschappelijke kennis1: intuïtie-oordeel en intuïtie-gissing. Intuïtie-oordeel (of filosofisch intuïtie-oordeel) wordt gekenmerkt door het feit dat in dit geval de directe waarneming van de waarheid, de objectieve verbinding van dingen niet alleen wordt uitgevoerd zonder logisch rigoureus bewijs, maar dergelijk bewijs bestaat niet voor deze waarheid en kan in principe niet bestaan. Intuïtie-oordeel wordt uitgevoerd als een enkele (eenmalige) synthetische holistische handeling van generaliserende aard. Het is deze aard van logisch onbewijsbare uitspraken die de stellingen van Turing, Church en Markov in de theorie van algoritmen hebben.

Gratis e-book downloaden in handig formaat, kijken en lezen:
Download het boek Mathematical Logic and Theory of Algorithms, Igoshin VI, 2008 - fileskachat.com, snel en gratis te downloaden.

Federaal Agentschap voor Onderwijs

TOMSK STATE UNIVERSITEIT VAN CONTROLESYSTEMEN EN RADIO-ELEKTRONICA (TUSUR)

Afdeling Automatisering van Informatieverwerking

Ik keur het goed:

Hoofd cafe AOI

Professor

JEP. Ekhlakov

"__" ______________2007

Richtlijnen

tot de uitvoering van praktisch werk aan de discipline

"Wiskundige logica en theorie van algoritmen"

voor studenten van specialiteit 230102 -

"Geautomatiseerde systemen voor informatieverwerking en controle"

ontwikkelaars:

Kunst. docent bij de afdeling AOI

DAN. Peremitina

Tomsk - 2007

Praktijkles nr. 1 "Propositional Algebra Formulas" 3

Praktijkles nr. 2 "Equivalente transformaties van propositiealgebraformules" 10

Praktijkles nr. 3 "Normale formules" 12

Praktijkles nr. 4 "Logisch redeneren" 14

Praktijkles nr. 5 "Formules van predikatenlogica" 18

Oefen #6 Booleaanse functies 23

Oefen #7 Gedeeltelijk recursieve functies 28

Oefen #8 Turing Machines 34

Praktijkles nr. 1 "Propositionele Algebra Formules"

De leer van proposities - de algebra van proposities, of de algebra van logica - is de eenvoudigste logische theorie. Het atomaire begrip van de propositiealgebra is uitspraak - een declaratieve zin in verband waarmee de verklaring over de waarheid of onwaarheid zinvol is.

Een voorbeeld van een ware uitspraak: "De aarde draait om de zon." Een voorbeeld van een valse verklaring: "3 > 5". Niet elke zin is een statement; uitspraken bevatten geen vragende en uitroepende zinnen. De zin: "Pap is een heerlijk gerecht" is geen uitspraak, omdat er geen consensus kan zijn over waar of onwaar. De zin "Er is leven op Mars" moet als een verklaring worden beschouwd, omdat deze objectief waar of onwaar is, hoewel nog niemand weet welke.

Aangezien het onderwerp van studie van logica alleen de waarheidswaarden van proposities zijn, worden de letteraanduidingen A, B, ... of X, Y ... voor hen geïntroduceerd.

Elke bewering wordt als waar of onwaar beschouwd. Kortheidshalve schrijven we 1 in plaats van de ware waarde en 0 in plaats van de valse waarde X= "De aarde draait om de zon" en Y= "3 > 5", en X=1 en Y= 0. De bewering kan niet zowel waar als onwaar zijn.

Verklaringen kunnen enkelvoudig of samengesteld zijn. De uitspraken "de aarde draait om de zon" en "3 > 5" zijn eenvoudig. Samengestelde uitspraken worden gevormd uit eenvoudige uitspraken met behulp van natuurlijke (Russische) taalverbindingen NOT, AND, OR, IF-THEN, THEN-AND-ONLY-THEN. Bij gebruik van alfabetische notatie voor uitspraken, worden deze connectieven vervangen door speciale wiskundige symbolen, die kunnen worden beschouwd als symbolen van logische bewerkingen.

Hieronder staan ​​in tabel 1 varianten van symbolen voor het aanduiden van connectieven en de namen van de bijbehorende logische bewerkingen.

Ontkenning (inversie) uitspraken X is een bewering die waar is als en slechts als X vals (aangeduid of , leest "niet" X” of “het is niet waar dat X”).

voegwoord
van twee proposities heet een propositie die waar is als en slechts als beide proposities waar zijn X en Y. Deze logische bewerking komt overeen met de verbinding van uitspraken met de unie "en".

disjunctie
twee zinnen X en Y Een bewering is onwaar als en slechts als beide beweringen X en Y vals. In de omgangstaal komt deze logische bewerking overeen met de unie "of" (niet exclusief "of").

implicatie twee zinnen X en Y is een bewering die onwaar is als en slechts als X waar, en Y- false (aangeduid als
; leest " X houdt in Y", "als X, dan Y”). De operanden van deze bewerking hebben speciale namen: X- pakket, Y- conclusie.

Gelijkwaardigheid twee zinnen X en Y wordt een bewering genoemd die waar is als en slechts dan als de waarheid waarden X en Y zijn hetzelfde (symbool:
).

Tabel 1. Logische bewerkingen

De operanden van logische bewerkingen kunnen slechts twee waarden aannemen: 1 of 0. Daarom kan elke logische bewerking , &, , ,  eenvoudig worden gespecificeerd met behulp van de tabel, waarbij de waarde van het resultaat van de bewerking wordt aangegeven, afhankelijk van de waarden van de operanden. Zo'n tafel heet waarheidstabel (Tafel 2).

Tabel 2. Waarheidstabel van logische bewerkingen

Met behulp van de logische bewerkingen die hierboven zijn gedefinieerd, is het mogelijk om te bouwen vanuit eenvoudige proposities propositielogica formules die verschillende samengestelde uitspraken vertegenwoordigen. De logische betekenis van een samengestelde verklaring hangt af van de structuur van de verklaring, uitgedrukt door de formule, en de logische waarden van de elementaire verklaringen die het vormen.

Voor de systematische studie van formules die uitspraken uitdrukken, worden variabele uitspraken geïntroduceerd P, P 1 , P 2 , ..., P N, waarden uit de set nemen (0, 1).

Propositionele logische formule F (P 1 , P 2 ,..., P N) heet een tautologie of identiek waar als de waarde voor alle waarden P 1 , P 2 ,..., P N is 1 (waar). Formules die voor ten minste één set variabelenlijsten als waar worden geëvalueerd, worden aangeroepen uitvoerbaar . Formules die de waarde "false" aannemen voor alle waarden van de variabelen worden genoemd tegenstellingen (identiek onwaar, onmogelijk).

Auteur: Guts A.K.
Uitgever: O.: Heritage
Jaar van uitgave: 2003
Pagina's: 108
ISBN 5-8239-0126-7
Lezen:
downloaden: matematicheskayalogika2003.djvu

OMSK STATE UNIVERSITY FACULTEIT IN COMPUTER WETENSCHAPPEN AFDELING
CYBERNETICA
AK Ingewanden
Wiskundige logica en theorie van algoritmen
Omsk 2003
VVK 60 UDC 53:630.11
Guts AK Wiskundige logica en theorie van algoritmen: leerboek. -
Omsk: Erfgoed Publishing. Dialog-Siberië, 2003. - 108 p.
ISBN 5-8239-0126-7
Het leerboek is gewijd aan de presentatie van de grondslagen van wiskundige logica en theorie
algoritmen. De basis van de handleiding zijn de abstracts van gelezen colleges
tweedejaars studenten van de afdeling computerwetenschappen van Omsk
Staatsuniversiteit 2002.
Voor studenten die studeren in de specialiteit 075200 - "Computer
beveiliging" en specialiteit 220100 - "Computers,
complexen, systemen en netwerken".
ISBN 5-8239-0126-7
(c) Staatsuniversiteit van Omsk, 2003
Inhoudsopgave
ik logica 7
1 Klassieke logica 8
1.1. Logica van proposities ........................... 8
1.1.1. Gezegden .............................. 8
1.1.2. Basiswetten van de logica ................................. 9
1.1.3. Russell's logische paradox ............... 10
1.1.4. Algebra (logica) van proposities ............... 11
1.1.5. Ladderdiagrammen .................................. 12
1.1.6. Equivalente formules .................. 14
1.1.7. Boole-algebra.................................. 15
1.1.8. Ware en geldige formules ........... 15
1.1.9. Het probleem van de oplosbaarheid .................... 15
1.1.10. Logisch gevolg .................................. 16
1.1.11. Syllogismen ................................... 17
1.2. Predikaatlogica ................................... 17
1.2.1. Predikaten en formules ............... 18
1.2.2. Interpretaties.................................. 19
1.2.3. Waarheid en vervulbaarheid van formules. modellen,
geldigheid, logisch gevolg........ 20
1.2.4. Gottlob Frege.................................. 21
1.2.5. Skolem-functies
en skolemisering van formules ...................... 22
1.3. Resolutiemethode ................................ 25
1.3.1. Methode van resoluties in logica
uitingen.................................. 25
1.3.2. Methode van resoluties in logica
predikaten .............................. 29
3
4
Inhoudsopgave
2 Formele theorieën (calculus) 31
2.1. Definitie van formele theorie of calculus. . 32
2.1.1. Een bewijs. Consistentie van de theorie.
Volledigheid van de theorie .............................. 32
2.2. Propositionele calculus ................................. 33
2.2.1. Taal en regels voor de inferentie van de propositiecalculus
............................................. 33
2.2.2. Een voorbeeld van het bewijs van de stelling .............. 35
2.2.3. Volledigheid en consistentie
propositiecalculus ................................. 36
2.3. Predikaatberekening ................................. 37
2.3.1. Taal en afleidingsregels van de predikaatrekening 37
2.3.2. Volledigheid en consistentie
predikaatberekening ...................... 39
2.4. Formele rekenkunde .............................. 39
2.4.1. Egalitaire theorieën.................................. 39
2.4.2. Taal en regels voor het afleiden van formele rekenkunde
.............................................. 39
2.4.3. Consistentie van de formele
rekenkundig. Stelling van Gentzen .............. 40
2.4.4. De onvolledigheidsstelling van Gödel ........................... 41
2.4.5. Kurt Gödel................... 42
2.5. Automatische afleiding van stellingen .............................. 43
2.5.1. S.Yu. Maslov.................................. 43
2.6. Logische programmering.................................. 45
2.6.1. Logisch programma ...................... 46
2.6.2. Logische programmeertalen.... 49
3 Niet-klassieke logica 50
3.1. Intuïtionistische logica ...................... 50
3.2. Vage logica .................................. 51
3.2.1. Fuzzy subsets ................................. 51
3.2.2. Bewerkingen op fuzzy
subsets ........................... 52
3.2.3. Eigenschappen van de verzameling van fuzzy
subsets.................................. 53
3.2.4. Fuzzy Propositionele Logica ....... 54
3.2.5. Vage ladderdiagrammen ........... 56
3.3. Modale logica................................... 56
3.3.1. Soorten modaliteit ........................... 57
Inhoudsopgave
5
3.3.2. Calculus 1 en T (Feis-von Wright) ........ 57
3.3.3. Berekening S4, S5
en Brouwer's calculus ................................. 58
3.3.4. Formule Waardering ................................. 59
3.3.5. Semantiek van Kripke .............................. 60
3.3.6. Andere interpretaties van modalen
borden ................................. 62
3.4. Georg von Wright ................................... 62
3.5. Tijdelijke logica .............................. 62
3.5.1. De timinglogica van Pryor .................. 63
3.5.2. Lemmon's timinglogica................... 64
3.5.3. De temporele logica van Von Wright ........... 64
3.5.4. Toepassing van timinglogica
naar programmeren................................ 65
3.5.5. Pnueli temporele logica .................. 67
3.6. Algoritmische logica.................................. 70
3.6.1. Constructie principes
1 >

Boeken. Download DJVU boeken, PDF gratis. Gratis elektronische bibliotheek
AK Lef, wiskundige logica en theorie van algoritmen

Dat kan (het programma zal het geel markeren)
U kunt de lijst met boeken over hogere wiskunde alfabetisch gesorteerd zien.
Je kunt de lijst met boeken over hogere natuurkunde alfabetisch gesorteerd zien.

• Gratis boek downloaden, volume 556 Kb, .djvu-formaat (modern leerboek)

Dames en heren!! Om bestanden van elektronische publicaties zonder "glitches" te downloaden, klikt u op de onderstreepte link met het bestand Rechter muis knop, selecteer een commando "Sla doelwit op als ..." ("Sla doelwit op als...") en sla het e-pub-bestand op uw lokale computer op. Elektronische publicaties zijn meestal in Adobe PDF- en DJVU-indelingen.

I. Logica
1. Klassieke logica
1.1. propositielogica
1.1.1. gezegden
1.1.2. Basiswetten van de logica
1.1.3. Russells logische paradox
1.1.4. Algebra (logica) van uitspraken
1.1.5. Ladderdiagrammen
1.1.6. Gelijkwaardige formules
1.1.7. Boole-algebra
1.1.8. Ware en geldige formules
1.1.9. Beslisbaarheidsprobleem
1.1.10. logisch gevolg
1.1.11. Syllogismen
1.2. Predikaatlogica
1.2.1. Predikaten en formules
1.2.2. Interpretaties
1.2.3. Waarheid en vervulbaarheid van formules. Modellen, validiteit, logisch gevolg
1.2.4. Gottlob Frege
1.2.5. Skolem-functies
en scolemisering van formules
1.3. Resolutie Methode:
1.3.1. Methode van resoluties in de propositielogica
1.3.2. Resolutiemethode in predikaatlogica

2. Formele theorieën (calculus)
2.1. Definitie van formele theorie of calculus
2.1.1. Een bewijs. Consistentie van de theorie. Volledigheid van de theorie
2.2. propositieberekening
2.2.1. Taal en regels voor de inferentie van de propositiecalculus
2.2.2. Stellingbewijs voorbeeld
2.2.3. Volledigheid en consistentie van de propositionele calculus
2.3. predikaatberekening
2.3.1. Taal en afleidingsregels van de predikaatrekening
2.3.2. Volledigheid en consistentie van de predikaatberekening
2.4. Formele rekenkunde
2.4.1. Egalitaire theorieën
2.4.2. Taal en regels voor het afleiden van formele rekenkunde
2.4.3. Consistentie van formele rekenkunde. Stelling van Gentzen
2.4.4. Onvolledigheidsstelling van Godel
2.4.5. Kurt Gödel
2.5. Automatische afleiding van stellingen
2.5.1. S.Yu. Maslov
2.6. Logisch programmeren
2.6.1. logisch programma
2.6.2. Logische programmeertalen

3. Niet-klassieke logica
3.1. intuïtionistische logica
3.2. vage logica
3.2.1. Fuzzy subsets
3.2.2. Bewerkingen op vage subsets
3.2.3. Eigenschappen van de verzameling vage deelverzamelingen
3.2.4. Vage propositielogica
3.2.5. Vage ladderdiagrammen
3.3. modale logica
3.3.1. Modaliteitstypen
3.3.2. Calculus 1 en T (Feis-von Wright)
3.3.3. Calculus S4, S5 en Wrouer Calculus
3.3.4. Formule waardering
3.3.5. Semantiek van Kripke
3.3.6. Andere interpretaties van modale tekens
3.4. Georg von Wright
3.5. Tijdelijke logica
3.5.1. De timinglogica van Pryor
3.5.2. Lemmon's temporele logica
3.5.3. De temporele logica van Von Wright
3.5.4. Toepassing van timinglogica op programmeren
3.5.5. Pnueli temporele logica
3.6. Algoritmische logica
3.6.1. Principes van het construeren van algoritmische logica
3.6.2. Charles Hoare
3.6.3. Hoare's algoritmische logica

II. Algoritmen
4. Algoritmen
4.1. Concept van algoritme en berekenbare functie
4.2. Recursieve functies
4.2.1. Primitieve recursieve functies
4.2.2. Gedeeltelijk recursieve functies
4.2.3. stelling van de kerk
4.3. Turing-Post-machine
4.3.1. Functieberekeningen op een Turing-Post-machine
4.3.2. Rekenvoorbeelden
4.3.3. Turing-scriptie
4.3.4. Universele Turing-Post-machine
4.4. Alan Turing
4.5. Emil Post
4.6. Efficiënte algoritmen
4.7. Algoritmisch onoplosbare problemen

5. Complexiteit van algoritmen
5.1. Het concept van de complexiteit van algoritmen
5.2. Probleemklassen Р en NP
5.2.1. Probleemklas
5.2.2. Klasse van problemen NP
5.2.3. Niet-deterministische Turing Machine
5.3. Over het begrip complexiteit
5.3.1. Drie soorten moeilijkheid
5.3.2. Vier categorieën getallen volgens Kolmogorov
5.3.3. Het proefschrift van Kolmogorov
5.4. EEN. Kolmogorov

6. Algoritmen van de werkelijkheid
6.1. Virtual Reality-generator
6.2. Turing-principe
6.3. Logisch mogelijke Kantgotu-omgevingen

Korte samenvatting van het boek

Het leerboek is gewijd aan de presentatie van de grondslagen van de wiskundige logica en de theorie van algoritmen. Het leerboek is gebaseerd op aantekeningen die in 2002 werden gegeven aan tweedejaarsstudenten van de afdeling Computerwetenschappen van de Omsk State University. Voor studenten die studeren in de specialiteit "Computerbeveiliging" en in de specialiteit "Computers, complexen, systemen en netwerken".

Wat is de wetenschap van logica. Dit is een theorie die leert correct te redeneren, conclusies en conclusies correct te trekken, resulterend in correcte (juiste) uitspraken. Daarom moet logica als wetenschap een lijst met regels bevatten voor het verkrijgen van correcte uitspraken. Zo'n reeks regels, gevolgtrekkingen, wordt een lijst met syllogismen genoemd. Een statement is een statement over de te bestuderen objecten met een ondubbelzinnige en nauwkeurig gedefinieerde betekenis. In het Russisch is een uiting een declaratieve zin waarover gebeden wordt om te zeggen dat het ons iets waars of iets helemaal verkeerds vertelt. Daarom kan de bewering waar of onwaar zijn.

Boeken, download boeken, download boek, boeken online, lees online, download gratis boeken, lees boeken, lees boeken online, lees, bibliotheek online, boeken lezen, lees online gratis, lees boeken gratis, ebook, lees boeken online, beste boeken wiskunde en natuurkunde, interessante boeken wiskunde en natuurkunde, e-books, gratis boeken, gratis boeken downloaden, gratis boeken downloaden wiskunde en natuurkunde, boeken volledig gratis downloaden, online bibliotheek, boeken gratis downloaden, boeken gratis online lezen zonder registratie wiskunde en natuurkunde, gratis online boeken lezen wiskunde en natuurkunde, elektronische bibliotheek wiskunde en natuurkunde, boeken om online te lezen wiskunde en natuurkunde, de wereld van boeken wiskunde en natuurkunde, gratis wiskunde en natuurkunde lezen, bibliotheek online wiskunde en natuurkunde, boeken lezen wiskunde en natuurkunde, boeken online gratis wiskunde en natuurkunde, populaire boeken wiskunde en natuurkunde, bibliotheek met gratis boeken wiskunde en natuurkunde, download elektr wiskunde en natuurkunde boek, gratis online wiskunde en natuurkunde bibliotheek, download e-books, online wiskunde en natuurkunde leerboeken, wiskunde en natuurkunde e-book bibliotheek, e-books gratis download zonder registratie wiskunde en natuurkunde, goede wiskunde en natuurkunde boeken, download volledige wiskundeboeken en natuurkunde, elektronische bibliotheek gratis lezen wiskunde en natuurkunde, elektronische bibliotheek gratis download wiskunde en natuurkunde, sites voor het downloaden van boeken wiskunde en natuurkunde, slimme boeken wiskunde en natuurkunde, zoeken naar boeken wiskunde en natuurkunde, download e-books gratis wiskunde en natuurkunde, e-book download wiskunde en natuurkunde, de beste boeken over wiskunde en natuurkunde, elektronische bibliotheek voor gratis wiskunde en natuurkunde, lees online gratis boeken over wiskunde en natuurkunde, site voor boeken over wiskunde en natuurkunde, elektronische bibliotheek, online boeken om te lezen , boek over elektronische wiskunde en natuurkunde, site om gratis en zonder registratie boeken te downloaden , een gratis online bibliotheek met wiskunde en natuurkunde, waar u gratis boeken over wiskunde en natuurkunde kunt downloaden, gratis en zonder registratie boeken kunt lezen over wiskunde en natuurkunde, leerboeken over wiskunde en natuurkunde kunt downloaden, gratis e-boeken over wiskunde en natuurkunde kunt downloaden, download gratis boeken volledig, bibliotheek gratis online, de beste e-books wiskunde en natuurkunde, online bibliotheek met boeken wiskunde en natuurkunde, download e-books gratis zonder registratie, online bibliotheek download gratis, waar gratis boeken te downloaden, e- gratis bibliotheken, gratis e-boeken, gratis e-bibliotheken, gratis online bibliotheek, gratis boeken lezen, gratis boeken online lezen, gratis online lezen, interessante boeken om online te lezen wiskunde en natuurkunde, boeken lezen online wiskunde en natuurkunde, elektronische bibliotheek online wiskunde en natuurkunde, gratis bibliotheek met elektronische boeken wiskunde en natuurkunde, bibliotheek online om gratis en zonder registratie te lezen, lezen en wiskunde en natuurkunde, vind een boek met wiskunde en natuurkunde, catalogus met boeken over wiskunde en natuurkunde, download gratis online boeken wiskunde en natuurkunde, online bibliotheek met wiskunde en natuurkunde, download gratis boeken zonder registratie wiskunde en natuurkunde, waar u kunt downloaden gratis boeken wiskunde en natuurkunde, waar u boeken kunt downloaden, sites om gratis boeken te downloaden, online om te lezen, bibliotheek om te lezen, boeken om gratis online te lezen zonder registratie, boekenbibliotheek, gratis bibliotheek online, online bibliotheek om gratis te lezen , boeken om gratis en zonder registratie te lezen, elektronische bibliotheek om gratis boeken te downloaden, online om te lezen is gratis.

,
Sinds 2017 hervatten we de mobiele versie van de website voor mobiele telefoons (afgekort tekstontwerp, WAP-technologie) - de bovenste knop in de linkerbovenhoek van de webpagina. Als u geen toegang heeft tot internet via een personal computer of internetterminal, kunt u met uw mobiele telefoon onze website bezoeken (afgekort ontwerp) en, indien nodig, gegevens van de website opslaan in het geheugen van uw mobiele telefoon. Bewaar boeken en artikelen op uw mobiele telefoon (mobiel internet) en download ze van uw telefoon naar uw computer. Handig downloaden van boeken via mobiele telefoon (naar telefoongeheugen) en naar uw computer via mobiele interface. Snel internet zonder onnodige tags, gratis (voor de prijs van internetdiensten) en zonder wachtwoorden. Het materiaal wordt ter beoordeling aangeboden. Directe links naar bestanden van boeken en artikelen op de website en de verkoop ervan door derden is verboden.

Opmerking. Een handige tekstlink voor forums, blogs, het citeren van websitemateriaal, de html-code kan worden gekopieerd en eenvoudig in uw webpagina's worden geplakt bij het citeren van ons websitemateriaal. Het materiaal wordt ter beoordeling aangeboden. Bewaar boeken ook op uw mobiele telefoon via internet (er is een mobiele versie van de site - de link staat linksboven op de pagina) en download ze van uw telefoon naar uw computer. Directe links naar boekbestanden zijn verboden.