Introduktion.
Formål.
Nye afsnit af det diskrete matematikkursus, selvom de er implementeret i form læseplaner og serier af forelæsninger, eksisterer endnu ikke i form af monografier, i det mindste på russisk, da forløbet af diskret matematik for tekniske universiteter fokuseret på det gamle anvendte problemer, som ingeniører skulle løse. Især i matematisk logik det var minimering logiske kredsløb, som har mistet sin relevans i dag.
Det er interessant at bemærke, at teorien om logisk kredsløbssyntese, efter at have gennemgået næsten en komplet "biologisk cyklus" for øjnene af en generation af forskere, er et meget lærerigt eksempel på, hvordan industrier er meget modtagelige for forældelse tekniske videnskaber, svagt relateret til grundlæggende videnskab. 10 år siden alt tekniske magasiner var fyldt med artikler om minimering og syntese af logiske kredsløb. De fleste af de minimeringsmetoder, der er udviklet af videnskabsmænd, er nu glemt og er ikke efterspurgte i praksis. Og de ideer, der blev betragtet som rent teoretiske på det tidspunkt, fandt praktisk anvendelse i moderne teknologi. For eksempel har fuzzy logic, petri-net og algoritmeteori bestået tidens tand og er meget brugt i forskellige områder kybernetik og programmering, som f.eks system programmering, beregningsmæssig kompleksitet og kunstig intelligens.
Og teorien om algoritmer blev den centrale del af diskret matematik. Men i modsætning til de fleste monografier på russisk præsenteres disse spørgsmål i løbet af forelæsninger som et middel til at løse praktiske, tekniske problemer.
Som det er kendt, efter hvert årti, komponentbasen af computere, OS, adgangsmidlerne og selve programmerne ændrer sig radikalt. De strukturer og algoritmer, der ligger til grund for dem, forbliver dog uændrede i meget længere tid. Disse fundamenter begyndte at blive lagt for tusinder af år siden, da formel logik blev udviklet og de første algoritmer blev udviklet.
Matematisk logik og teorien om algoritmer hører traditionelt til grundlæggende videnskab og anses for at være af ringe praktisk relevans og svære at forstå. Ja, da J. Bull skabte matematiske apparater Boolesk algebra, det tog ham lang tid at finde praktisk ansøgning, dog var det i det 20. århundrede netop dette matematiske apparat, der gjorde det muligt at designe alle computerkomponenter. Følgelig er den første af disse fordomme med succes tilbagevist af udviklingen computerteknologi.
Hvad angår fordommen om vanskeligheden ved at forstå denne disciplin, så stammer den i høj grad fra det faktum, at bøger om matematisk logik og teorien om algoritmer blev skrevet af matematikere for matematikere.
Nu, hvor computerteknologiens muligheder er steget mange gange, og den personlige computere Der er langt flere mennesker end mennesker, der ved, hvordan man bruger dem effektivt, og det er yderst vigtigt at forstå, hvad der kan og ikke kan gøres med moderne computerteknologi.
Nemlig generel teori Algoritmer har vist, at der er problemer, der er uløselige, uanset hvor stærk computerkraften er, og dens hastigt udviklende gren, teorien om beregningskompleksitet, fører gradvist til forståelsen af, at der er problemer, der kan løses, men som objektivt set er komplekse, og deres kompleksitet kan vise sig at være i en eller anden forstand absolut, de. praktisk talt utilgængelige for moderne computere.
Dette kursus satte følgende mål:
1. Præsentér alle de emner, der overvejes, så enkelt som muligt, men ikke enklere end det, der kræves af en højt kvalificeret specialist.
2. Praktiske problemer design og analyse informationssystemer er udgangspunktet, og det formelle apparat er midlet systematisk løsning disse problemer. Det er vores dybe overbevisning, at en elev ikke er et kar, der skal fyldes, men en fakkel, der skal tændes.
3. Hvert afsnit af kurset indeholder selvtestspørgsmål. Til assimilering dette kursus eleven skal besvare alle disse spørgsmål.
Som et resultat af at mestre dette kursus, skal den studerende, baseret på en klar forståelse af de relevante teoretiske afsnit, være i stand til at:
Implementere enkleste form logisk konvertering information på et vilkårligt grundlag af logiske funktioner;
Fremhæv i bevismæssig begrundelse naturligt sprog logisk struktur, opbyg formelle bevisskemaer og kontroller deres rigtighed.
1.2 Logiske repræsentationer
Logiske repræsentationer - beskrivelse af systemet, processen, fænomenet under undersøgelse i form af et sæt komplekse udsagn består af simple (elementære) udsagn Og logiske forbindelser
mellem dem. Logiske repræsentationer og deres komponenter er kendetegnet ved visse egenskaber og et sæt tilladte transformationer over dem (operationer, slutningsregler osv.), der implementerer dem, der er udviklet i formel (matematisk) logik rigtige metoder ræsonnement - logikkens love.
Metoder (regler) for formel præsentation af udsagn, konstruktion af nye udsagn fra eksisterende ved hjælp af logisk korrekte transformationer, samt metoder (metoder) til at fastslå sandheden eller falskheden af udsagn studeres i matematisk logik. Moderne matematisk logik omfatter to hovedafsnit: logikken i udsagn og dækker det prædikatlogik(Fig. 1.1), til hvis konstruktion der er to tilgange (sprog), der danner to varianter af formel logik: logikkens algebra Og logisk beregning. Der er en en-til-en overensstemmelse mellem de grundlæggende begreber i disse sprog af formel logik. Deres isomorfisme er i sidste ende sikret af enhed af de underliggende tilladelige transformationer.
Ris. 1.1
Hovedformålene med traditionelle grene af logik er udsagn.
Udmelding - erklærende sætning (erklæring, dom), o hvilket det giver mening at sige, at det rigtigt eller falsk. Alle videnskabelig viden(love og fænomener inden for fysik, kemi, biologi osv., matematiske teoremer osv.), begivenheder Hverdagen, situationer, der opstår i økonomi og ledelsesprocesser, formuleres i form af udsagn. Imperativ og spørgende sætninger er ikke udsagn.
Eksempler på udsagn: "To gange to er fire", "Vi lever i det 21. århundrede", "Rublen er den russiske valuta", "Alyosha er Olegs bror", "Operationerne med union, kryds og addition er boolske operationer på sæt ", "Mennesket er dødeligt", "Omarrangering af vilkårenes steder ændrer ikke summen", "I dag er det mandag", "Hvis det regner, du burde tage en paraply."
For yderligere at kunne operere med disse sætninger som udsagn, skal vi for hver af dem vide, om det er sandt eller falsk, dvs. kender dem sandhedsværdi (sandhed). Bemærk, at i nogle tilfælde afhænger sandheden eller falskheden af et udsagn af, hvilken specifik virkelighed (system, proces, fænomen), vi forsøger at beskrive med dens hjælp. I dette tilfælde siges det givne udsagn at være sandt (eller falsk) i en given fortolkning (kontekst). Vi antager endvidere, at konteksten er givet og udsagnet har en vis sandhedsværdi.
1.3 Historien om udviklet matematisk logik
Logik som videnskab blev dannet i det 4. århundrede. f.Kr. Det blev skabt af den græske videnskabsmand Aristoteles.Ordet "logik" kommer fra det græske "logos", som på den ene side betyder "ord" eller "udlægning", og på den anden side tænkning. I forklarende ordbog Ozhegova S.I. Det siges: "Logik er videnskaben om tænkningens love og dens former." I det 17. århundrede Den tyske videnskabsmand Leibniz planlagde at skabe en ny videnskab, som ville være "kunsten at beregne sandheden" . I denne logik ville hvert udsagn ifølge Leibniz have et tilsvarende symbol, og ræsonnement ville have form af beregninger. Denne idé om Leibniz, der ikke havde mødt forståelsen af sine samtidige, blev ikke spredt eller udviklet og forblev et strålende gæt.
Først i midten af 1800-tallet. Den irske matematiker George Boole legemliggjorde Leibniz' idé. I 1854 skrev han værket "Undersøgelse af tankelovene", som lagde grundlaget for logikkens algebra, hvor love, der ligner almindelig algebras love, gælder, men bogstaverne gør det. ikke betegne tal, men udsagn. På boolsk algebras sprog kan man beskrive ræsonnement og "beregne" dets resultater. Det dækker dog ikke alle ræsonnementer, men kun et bestemt deres type, Derfor betragtes Boole algebra som en propositionel regning.
Den boolske logiks algebra var embryonet ny videnskab- matematisk logik. I modsætning hertil kaldes Aristoteles' logik traditionel formel logik. Navnet "matematisk logik" afspejler to træk ved denne videnskab: For det første er matematisk logik logik, der bruger matematikkens sprog og metoder; for det andet bringes matematisk logik til live af matematikkens behov.
I slutningen af det 19. århundrede. Den mængdeteori, som Georg Cantor skabte, syntes at være et pålideligt grundlag for al matematik, inklusive matematisk logik, i det mindste for propositionalregning (Boole algebra), fordi Det viste sig, at Cantor-algebra (mængdelære) er isomorf til Boole-algebra.
Matematisk logik blev i sig selv en gren af matematikken, der i starten virkede meget abstrakt og uendeligt langt fra praktiske anvendelser. Dette område forblev dog ikke "rene" matematikeres domæne længe. I begyndelsen af det 20. århundrede. (1910) Den russiske videnskabsmand Ehrenfest P.S. påpegede muligheden for at bruge apparatet fra boolsk algebra i telefonkommunikation til at beskrive koblingskredsløb. I 1938-1940 dukkede næsten samtidigt værker af den sovjetiske videnskabsmand V.I. Shestakov, den amerikanske videnskabsmand Shannon og de japanske videnskabsmænd Nakashima og Hakazawa op om anvendelsen af matematisk logik i digital teknologi. Den første monografi dedikeret til brugen af matematisk logik i design af digitalt udstyr blev offentliggjort i USSR af den sovjetiske videnskabsmand M.A. Gavrilov. i 1950. Den matematiske logiks rolle i udviklingen af moderne mikroprocessorteknologi er ekstremt vigtig: den bruges i design af computerhardware, i udviklingen af alle programmeringssprog og i design af diskrete automatiseringsenheder.
Forskere ydede et stort bidrag til udviklingen af matematisk logik forskellige lande: Professor ved Kazan University Poretsky P.S., de-Morgan, Pierce, Turing, Kolmogorov A.N., Heidel K. et al.
1.4 Spørgsmål til selvtest.
1. Formuler kursets mål
Send dit gode arbejde i videnbasen er enkel. Brug formularen nedenfor
Studerende, kandidatstuderende, unge forskere, der bruger videnbasen i deres studier og arbejde, vil være dig meget taknemmelig.
Der er endnu ingen HTML-version af værket.
Du kan downloade værkets arkiv ved at klikke på nedenstående link.
Lignende dokumenter
Grundlæggende definitioner af matematisk logik, boolske og tilsvarende funktioner. Generelle begreber boolsk algebra. Zhegalkin algebra: udsagn og prædikater. Definition formel teori. Elementer i teorien om algoritmer, rekursive funktioner, Turing-maskine.
forelæsningsforløb, tilføjet 08/08/2011
Grundlæggende former for tænkning: begreber, domme, slutninger. Et essay af George Boole, der udforskede logisk algebra i detaljer. Sandhedsværdien (dvs. sandhed eller falskhed) af et udsagn. Logiske operationer af inversion (negation) og konjunktion.
præsentation, tilføjet 14.12.2016
Grafisk fortolkning af sæt og operationer på dem. Matematisk logik, boolsk algebra. Perfekt konjunktiv normalform. Tilsvarende formler og deres bevis. Systemets fuldstændighed booleske funktioner. Prædikatlogik, grafteori.
foredrag, tilføjet 12/01/2009
Historie om fremkomsten af boolsk algebra, udvikling af propositionalregningssystemet. Metoder til at fastslå sandheden eller falskheden af komplekse logiske udsagn vha algebraiske metoder. Disjunktion, konjunktion og negation, sandhedstabeller.
præsentation, tilføjet 22/02/2014
Firkantede matricer og determinanter. Koordiner lineært rum. Systemforskning lineære ligninger. Algebra af matricer: deres addition og multiplikation. Geometrisk billede komplekse tal og dem trigonometrisk form. Laplaces sætning og grundlag.
træningsmanual, tilføjet 03/02/2009
Grundbegrebet i teorien om positive (naturlige) tal. Udvikling af stenografi til aritmetiske operationer. Et symbolsk sprog for delelighed. Egenskaber og algebra for sammenligninger. At rejse sammenligninger med magter. Omkvadering. Fermats lille teorem.
præsentation, tilføjet 06/04/2014
Systemer digital behandling Information. Begrebet Boole algebra. Betegnelser for logiske operationer: disjunktion, konjunktion, inversion, implikation, ækvivalens. Love og identiteter for Boole algebra. Logisk grundlæggende COMPUTER. Konvertering af strukturformler.
præsentation, tilføjet 10/11/2014
Bogen er skrevet baseret på materialer fra forelæsninger og seminarer udført af forfatterne for juniorstuderende ved fakultetet for mekanik og matematik ved Moskva State University. Den taler om den matematiske logiks grundlæggende begreber (propositionel logik, første-ordens sprog, udtrykbarhed, propositional calculus, afgørbare teorier, fuldstændighedssætningen, principper for modelteori). Oplægget er beregnet til studerende matematikskoler, matematikstuderende og alle interesserede matematisk logik. Bogen indeholder omkring 200 opgaver af forskellig sværhedsgrad.
Udsagns logik.
Ytringer og operationer
"Hvis tallet n er rationelt, så n - algebraisk tal. Men det er ikke algebraisk. Så p er ikke rationelt." Vi behøver ikke at vide, hvad tallet n er, hvilke tal der kaldes rationelle og hvilke der er algebraiske, for at erkende, at dette ræsonnement er korrekt i den forstand, at konklusionen faktisk følger af de to angivne præmisser. Denne form for situation - når et bestemt udsagn er sandt uanset betydningen af de udsagn, der er inkluderet i det - udgør genstand for propositionel logik.
Denne begyndelse (især taget i betragtning, at logikforløbet var en del af det Filosofiske Fakultets uddannelse, hvor man også studerede ”dialektisk logik”) er alarmerende, men faktisk vil vores overvejelser have en helt præcis matematisk karakter, selvom vi starter med uformelle motivationer.
Indholdsfortegnelse
Forord
1. Propositionel logik
1.1. Ytringer og operationer
1.2. Komplet ligament systemer
1.3. Skemaer af funktionelle elementer
2. Propositionsregning
2.1. Propositionalregning (PC)
2.2. Andet bevis på fuldstændighedssætningen
2.3. At finde et modeksempel og efterfølgende regning
2.4. Intuitionistisk propositionel logik
3. Første ordens sprog
3.1. Formler og fortolkninger
3.2. Definition af sandhed
3.3. Udtrykkelige prædikater
3.4. Udtrykkelighed i aritmetik
3.5. Uudsigelige prædikater: automorfismer
3.6. Eliminering af kvantifikatorer
3.7. Presburger Aritmetik
3.8. Tarski-Seidenbergs sætning
3.9. Elementær ækvivalens
3.10. Ehrenfeuchts spil
3.11. Effektreduktion
4. Prædikatregning
4.1. Generelt gyldige formler
4.2. Aksiomer og slutningsregler
4.3. Rigtigheden af prædikatregning
4.4. Konklusioner i prædikatregning
4.5. Fuldstændighed af prædikatregning
4.6. Omdøbning af variabler
4.7. Forordet normalform
4.8. Herbrands sætning
4.9. Skolemov funktioner
5. Teorier og modeller
5.1. Aksiomer for lighed
5.2. Power boost
5.3. Fuldstændige teorier
5.4. Ufuldstændige og uafklarelige teorier
5.5. Diagrammer og udvidelser
5.6. Ultrafiltre og kompakthed
5.7. Ikke-standard analyse
Litteratur
Emneindeks
Indeks over navne.
Gratis download e-bog i et praktisk format, se og læs:
- fileskachat.com, hurtig og gratis download.
Download pdf
Nedenfor kan du købe denne bog til den bedste pris med rabat med levering i hele Rusland. Køb denne bog
Download bogen Forelæsninger om matematisk logik og teori om algoritmer, del 2, Sprog og beregning, Vereshchagin N.K., Shen A., 2012 - pdf - depositfiler.
Volzhsky University opkaldt efter. Tatishcheva.
Forelæsninger om matematisk logik og teori om algoritmer.
Udarbejdet af: Lektor S.V. Kaverin.
Kapitel I. Logikkens algebra.
§1.1. Definition af en boolsk funktion.
boolesk funktion y=f(x1,x2,…,xn)fra P variable x 1 , x 2 ,...,x n er enhver funktion, hvor argumenterne og funktionen kan tage værdien enten 0 eller 1, dvs. en boolsk funktion er en regel, hvorved et vilkårligt sæt af nuller og ettaller
(x 1 ,x 2 ,...,x n) er tildelt værdien 0 eller 1.
booleske funktioner også kaldet logiske algebrafunktioner, binære funktioner og koblingsfunktioner.
Boolesk funktion fra n variabler kan specificeres af en sandhedstabel, hvor sæt af argumentværdier er arrangeret i stigende rækkefølge efter deres tal : i første omgang rekruttering er i gang, der repræsenterer den binære udvidelse af 0 (dette sæt er nummereret 0); så kommer sættet, som er den binære udvidelse af 1, derefter 2, 3 osv. Det sidste sæt består af n enheder og er den binære udvidelse af tallet 2 n-1 (denne rækkefølge af arrangement af sæt vil blive kaldt leksikografisk rækkefølge). I betragtning af at tællingen starter fra 0, og værdien af en boolsk funktion kan være enten 0 eller n
1, konkluderer vi, at der kun er 22 forskellige boolske funktioner af n variabler. Således er der for eksempel 16 boolske funktioner af to variable, 256 af tre osv.
Eksempel 1.1.1.(stemme) . Lad os overveje en enhed, der registrerer vedtagelsen af en bestemt beslutning af "komitéen på tre". Hvert udvalgsmedlem trykker på sin egen knap, når de godkender en beslutning. Stemmer et flertal af medlemmerne for, vedtages beslutningen. Dette optages af en optageenhed. Således implementerer enheden funktionen f(x,y,z ) , hvis sandhedstabel har formen
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
En boolsk funktion er også entydigt specificeret ved at optælle alle tupler, hvorpå den har værdien 0, eller ved at optælle alle tupler, hvorpå den har værdien 1. Funktionen opnået i eksemplet f kan også specificeres ved følgende system af ligheder: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
En vektor af booleske funktionsværdier y=f(x 1 ,x 2 ,...,x n) er et ordnet sæt af alle værdier af funktionen f, hvor værdierne er ordnet efter leksikografisk rækkefølge. Lad for eksempel en funktion af tre variable f specificeres af en vektor af værdier (0000 0010), og det er nødvendigt at finde et sæt, hvor f tager værdien 1. Fordi 1 er på 7. pladsen og nummerering ind leksikografisk orden starter ved 0, så skal vi finde den binære udvidelse af 6. Funktionen f tager således værdien 1 på mængden (110).
§1.2. Elementære booleske funktioner.
Blandt boolske funktioner skiller de såkaldte elementære boolske funktioner sig ud, ved hjælp af hvilke enhver boolsk funktion af et vilkårligt antal variable kan beskrives.
1. En boolsk funktion f(x 1 ,x 2 ,…,x n), der tager værdien 1 på alle sæt nuller og enere kaldes konstant 1, eller identisk enhed. Betegnelse : 1 .
2. En boolsk funktion f(x 1 ,x 2 ,…,x n), der tager værdien 0 på alle sæt nuller og enere kaldes konstant 0, eller identisk nul. Betegnelse : 0 .
3. Afslag er en boolsk funktion af en variabel, der er defineret af følgende sandhedstabel
Andre navne : logisk multiplikation (produkt); logisk "og".
Betegnelser : x&y, xÿy, x⁄y, min(x,y).
5. Disjunktion
Andet navn : logisk konsekvens. Betegnelser : xØy, xfly, xy.
7. Ækvivalens er en boolsk funktion af to variable, der er defineret af den følgende sandhedstabel
Andet navn : anti-ækvivalens. Betegnelser : x∆y, x+y.
9. Schaeffers slagtilfælde er en boolsk funktion af to variable, der er defineret af følgende sandhedstabel
Andet navn : negation af disjunktion, logisk "ikke-eller", Webb-funktion.
Betegnelse : x∞y ; for Webb-funktionen - x±y.
Kommentar. Symboler Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ involveret i notationen elementære funktioner vi vil kalde dem forbindelser eller operationer.
§1.3. Angivelse af booleske funktioner ved hjælp af elementære.
Hvis du erstatter nogle boolske funktioner i en logisk funktion i stedet for variabler, er resultatet en ny boolsk funktion kaldet superposition substituerede funktioner (kompleks funktion). Ved at bruge superposition kan du opnå mere komplekse funktioner, der kan afhænge af et vilkårligt antal variable. Vi vil kalde at skrive booleske funktioner i form af elementære booleske funktioner formel implementerer denne funktion.
Eksempel 1.3.1. Lad en elementær boolsk funktion x¤y være givet. Lad os erstatte funktionen x 1 ∞x 2 i stedet for x. Vi får en funktion af tre variable (x 1 ∞x 2)¤y. Hvis vi i stedet for variablen y erstatter f.eks. x 3 ∆x 4, får vi ny funktion fra fire variable: (x 1 ∞x 2)¤(x 3 ∆x 4). Naturligvis vil vi på denne måde opnå booleske funktioner, som vil blive udtrykt gennem elementære boolske funktioner.
Ser vi fremad, bemærker vi det nogen en boolsk funktion kan repræsenteres som en superposition af elementære funktioner.
For en mere kompakt optagelse komplekse funktioner lad os introducere følgende konventioner : 1) ydre beslag er udeladt; 2) operationer i parentes udføres først; 3) det vurderes, at prioriteten af connectives falder i følgende rækkefølge : Ÿ, ⁄, ¤, Ø, ~. For ækvivalente forbindelser og de resterende forbindelser (∆,|,∞), skal du indsætte parenteser indtil videre.
Eksempler 1.3.2. I formlen x⁄y¤z placeres parenteserne på følgende måde: ((x⁄y)¤z), fordi operation ⁄ er stærkere end operation ¤ i henhold til vores aftale.
1. I formlen x¤y~zØx er parenteserne placeret som følger: ((x¤y)~(zØx))
2. I formlen (x∆y)~zØxy¤Ÿz er parenteserne placeret som følger: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Formlen xØyØz er efter vores aftale ikke skrevet korrekt, pga placering af parenteser resulterer i to forskellige funktioner: ((xØy)Øz) og (xØ(yØz)).
§1.4. Signifikante og ikke-signifikante variable.
Boolesk funktion y=f(x 1 ,x 2 ,...,x n) afhænger væsentligt fra variabel x k hvis et sådant sæt værdier findes -en 1 ,-en 2 ,…,-en k - 1, -en k+1, -en k + 2,…, -en n at f (en 1,a 2,…,a k-1 , 0 ,en k+1,a k+2,…,a n) π f (en 1,a 2,…,a k-1 , 1 ,en k+1,a k+2,…,a n).
I dette tilfælde x k kaldes en væsentlig variabel , V Ellers x k kaldes en insignifikant (dummy) variabel . Med andre ord er en variabel irrelevant, hvis ændring af den ikke ændrer værdien af funktionen.
Eksempel 1.4.1. Lad de boolske funktioner f 1 (x 1 ,x 2) og f 2 (x 1 ,x 2) defineres af følgende sandhedstabel:
| x 1 | x 2 | f 1 (x 1, x 2) | f 2 (x 1,x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
For disse funktioner er variablen x 1 - er signifikant, og variablen x 2 er ikke signifikant.
Det er klart, at boolske funktioner ikke ændrer deres værdier ved at introducere (eller fjerne) irrelevante variable. Derfor betragtes boolske funktioner i det følgende op til uvæsentlige variable (i eksemplet kan vi skrive: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Sandhedstabeller. Tilsvarende funktioner.
Når du kender sandhedstabellerne for elementære funktioner, kan du beregne sandhedstabellen for den funktion, som denne formel implementerer.
Eksempel 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Således implementerer formel F1 disjunktionen. Eksempel 1.5.2. F2=x 1 ⁄x 2 Øx 1
Således implementerer formel F3 disjunktionen.
De boolske funktioner f1 og f2 kaldes tilsvarende, hvis på hvert sæt ( -en 1 ,-en 2 ,…, en n) nuller og ettaller, værdierne af funktionerne falder sammen. Notationen for ækvivalente funktioner er som følger : f1=f2.
Ifølge de givne eksempler 1-3 kan vi skrive
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2 ;
X 1 ⁄x 2 Øx 1 = 1;
((x 1 ⁄x 2)∆x 1)∆x 2 =x 1 ¤x 2.
§1.6. Grundlæggende ækvivalenser.
De givne ækvivalenser er ofte nyttige, når du arbejder med booleske funktioner.
Under H, H1, H2,... står for nogle boolske funktioner.
1. Lov om dobbelt negation: H = H.
2. Idempotens
3. Kommutativitet:
H1*H2=H2*H1, hvor symbolet * betyder et af forbindelsesleddet &, ¤, ∆,
4. Associativitet:
H1*(H2*H3)=(H1*H2)*H3, hvor symbolet * betyder et af forbindelsesleddet &, ¤, ∆, ~.
5. Distributivitet:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. De Morgans love:
H1& H2 = H1 ∨ H2, H1∨ H2 = H1 & H2.
7. Overtagelsesregler:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Love for limning:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Inversionslove: H ∨ H = 1, H & H = 0.
10. Regler for operationer med konstanter:
H¤1=1, H&1=H, H¤0=H, H&0=0.
For at kontrollere sandheden af ovenstående ækvivalenser er det nok at konstruere de tilsvarende sandhedstabeller.
Bemærk, at en operations associativitetsegenskab gør det muligt at udvide denne operation til et vilkårligt antal variable. Så for eksempel er notationen x¤у¤z¤w korrekt, fordi ethvert arrangement af parenteser resulterer i den samme funktion. Den kommutative karakter af en operation giver dig mulighed for at bytte variable i en formel. For eksempel x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Funktionel fuldstændighed.
I en typisk moderne digital computer er tallene 0 og 1. Derfor er instruktionerne, som processoren udfører, booleske funktioner. Nedenfor vil vi vise, at enhver boolsk funktion er implementeret gennem konjunktion, disjunktion og negation. Som følge heraf er det muligt at bygge den nødvendige processor med elementer til sin rådighed, der implementerer konjunktion, disjunktion og negation. Dette afsnit er dedikeret til at besvare spørgsmålet: er der (og hvis ja, hvilke) andre systemer med boolske funktioner, der har den egenskab, at de kan bruges til at udtrykke alle andre funktioner.
Lad os introducere en række klasser af funktioner.
1. Klassen af funktioner, der bevarer konstanten 0, dvs. sådanne funktioner
2. Klassen af funktioner, der bevarer konstanten 1, dvs. sådanne funktioner
3. Klassen af selvdobbelte funktioner, dvs. sådanne funktioner y=f(x 1 , x 2 , …, x n) således at f(x 1 , x 2 , … , x n) = f(x 1 , x 2 , … , x n) .
4. klasse lineære funktioner, dvs. sådanne funktioner y=f(x 1 ,x 2 ,…,x n), som kan repræsenteres som f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, hvor c 0, c 1, c 2 ... koefficienter, der kan tage værdien 0 eller 1.
5. Klasse monotone funktioner. På sættet af sæt af nuller og enere Bn =((x 1 ,x 2 ,...,x n):x i œ(0,1),i=1,2,...,n) introducerer vi en delvis rækkefølge som følger:
(-en 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) hvis og kun hvis -en 1 § b 1 , en 2 § b 2,…,a n § b n. En funktion f(x 1, x 2,..., x n) kaldes monotonisk hvis for to vilkårlige elementer fra B n sådan, at
(-en 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) det følger, at f( -en 1 ,a 2 ,...,a n)§f( b 1 ,b 2 ,...,b n).
Et system S af boolske funktioner, hvis superposition kan repræsentere enhver boolsk funktion, kaldes funktionelt komplet . De siger, det er funktionelt komplet system S Boolske funktioner dannes basis i logisk rum. Grundlaget S kaldes minimal , hvis fjernelse af en funktion fra det gør dette system til ufuldstændigt.
Fuldstændighedskriterium (Postens teorem) . Et system S af booleske funktioner er komplet, hvis og kun hvis det indeholder mindst én funktion: ikke-bevarende konstant 0, ikke-bevarende konstant 1, ikke-selv-dual, ikke-lineær og ikke-monotonisk.
Tabel 1.7 viser de egenskaber, som elementære booleske funktioner har (symbolet * angiver en egenskab, som en given funktion har).
Ved hjælp af Posts sætning og tabel 1.7 kan man bygge baser ud fra elementære funktioner iflg næste regel. Ved at vælge en hvilken som helst elementær boolsk funktion og om nødvendigt supplere den med andre funktioner, så de alle tilsammen opfylder den funktionelle fuldstændighedssætning. Gennem funktionerne i dette grundlag kan vi udtrykke Alle andre booleske funktioner.
Lad os konstruere nogle ofte anvendte baser i applikationer.
Tabel 1.7
| Navn | Betegnelse | Ulagerbarhed konstanter |
Ulagerbarhed konstanter |
Samodvoys gyldighed |
||
| Konst.0 | 0 | * | * | |||
| Konst.1 | 1 | * | * | |||
| Negativ | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Disjunktion. | ¤ | * | * | |||
| Implik. | Ø | * | * | * | * | |
| Tilsvarende. | ~ | * | * | * | ||
| Sum af mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Pierces pil | ∞ | * | * | * | * | * |
1. Systemet af funktioner S1=(Ÿ,⁄,¤) danner et grundlag. For at reducere en boolsk funktion til en form, der kun indeholder bindeled fra basis S1, kan følgende ækvivalenser være nyttige: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Systemet S2=(Ÿ,&) danner en basis. Vilkårlig funktion kan først reduceres til en form indeholdende connectives fra S1 og derefter
brug relationen x ∨ y = x ⋅ y.
3. Systemet S3=(Ÿ,¤) danner basis. En vilkårlig funktion kan først reduceres til en form, der indeholder connectives fra S1 og derefter
brug relationen x ⋅ y = x ∨ y.
4. Systemet S4=(1,&,∆) danner et grundlag. En vilkårlig funktion kan først reduceres til en form, der indeholder bindeled fra S1 og derefter bruge relationerne x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Systemet S5=(|) danner en basis. En vilkårlig funktion kan først reduceres til en form, der indeholder bindeled fra S2 og derefter bruge relationerne x ⋅ y = x y , x = xx .
6. Systemet S6=(∞) danner basis. En vilkårlig funktion kan først reduceres til en form, der indeholder connectives fra S3 og derefter
brug relationerne x ∨ y = x ↓ y, x = x ↓ x.
7. Systemet S7=(Ø,0) danner grundlag.
Eksempel 1.7.1. Skriv funktionen x¨(y∆z) i grundlaget S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∅ z ∅ z y)
Kapitel II. boolsk algebra.
Sættet af alle booleaner i basis S1=( ÿ, &, ⁄} form boolsk algebra. I boolsk algebra er alle formler således skrevet ved hjælp af tre bindeled: Ÿ, &, ¤. Vi undersøgte delvist denne algebras egenskaber i kapitel I (se f.eks. grundlæggende ækvivalenser). Dette kapitel omhandler egenskaber, der er specifikke for boolsk algebra, og derfor vil vi i dette kapitel kun beskæftige os med tre funktioner: ÿ, &, ⁄.
§2.1. Normale former.
Normalformer er en syntaktisk entydig måde at skrive en formel på, der implementerer givet funktion.
Hvis x er en logisk variabel, og σœ(0,1) så kaldes udtrykket x σ = x hvis hvis σσ == 10 eller x σ = 10 hvis hvis x x =≠σσ , kaldes x et bogstav . Bogstaverne x og Ÿx kaldes modsætninger. Konjunkt disjunkt kaldet adskillelse af bogstaver. For eksempel er formlerne x ⋅ y ⋅ z og x ⋅ y ⋅ x ⋅ x konjunkter, formlerne x ∨ y ∨ z og x ∨ y ∨ x er disjunkter, og formlen z er både et konjunkt og et disjunkt.
Disjunktiv normalform (DNF) kaldes en disjunktion af et endeligt antal konjunktioner .
Konjunktiv normal form (CNF) kaldes en konjunktion af et endeligt antal sætninger .
Mere enkelt: DNF er summen af produkter, og CNF er produktet af logiske summer Eksempler.
1. xÿy¤yÿz¤x er DNF (summen af produkter).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z er CNF (produkt af summer).
3. x ∨ y ∨ z ∨ w er DNF og CNF (samtidigt).
4. x ⋅ y ⋅ z ⋅ w er DNF og CNF (samtidigt).
5. (x¤x¤y)·(y¤z¤x)·z er CNF.
6. x⋅y⋅z og x⋅y⋅x⋅x er DNF'er.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z er ikke en normal form (ikke DNF eller CNF).
Lad funktionen f skrives i basis S1. Denne funktion reduceres til normal form som følger:
1) vi bruger De Morgans love til at transformere formlen til en form, hvor de negative fortegn kun vedrører individuelle variable;
2) vi anvender reglen for at fjerne dobbeltnegativer: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) , og den anden fordelingslov for reduktion til CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Enhver boolsk funktion kan have et uendeligt antal DNF- og CNF-repræsentationer. For eksempel, ved at bruge yderligere lovene for inversioner og operationsreglerne med konstanter, er det muligt at sikre, at enhver variabel i hver enkelt konjunkt eller disjunkt ikke optræder mere end én gang (enten sig selv eller dens negation).
Eksempel 2.1.1. For at reducere til DNF bruger vi den 1. fordelingslov.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= er CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - dette er en anden CNF
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z er en DNF
Eksempel 2.1.2. For at reducere til CNF er det nødvendigt at bruge den anden lov om distributivitet.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) er CNF
§2.2. Perfekte normale former.
Hvis i hvert led af en normalform alle variable er repræsenteret (enten sig selv eller deres negationer), og i hver enkelt konjunkt eller disjunktion optræder en variabel nøjagtig én gang (enten sig selv eller dens negation), så kaldes denne form perfekt normal form (SDNF eller SCNF). Eksempler: Lad en funktion af tre variable f(x,y,z) være givet.
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z er en perfekt DNF.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) er en perfekt CNF.
3. (x ∨ y) ⋅ (x ∨ z) er ikke en perfekt CNF, fordi f.eks. inkluderer den første sum ikke variablen z.
4. xÿyÿz er en perfekt DNF. Sætning 2.2.1.
1. Enhver boolsk funktion, der ikke er identisk nul, har kun én SDNF, op til placeringen af vilkårene.
2. Enhver boolsk funktion, der ikke er identisk med 1, har kun én SCNF, op til termernes placering.
Vi vil bevise sætningen konstruktivt, som en løsning på følgende problem: Brug denne sandhedstabel til at konstruere en SDNF.
Lad os overveje løsningen ved at bruge eksemplet med funktionen f(x,y,z) givet i en tabel (tabel 2.2) for n=3.
Eksempel 2.2.1. Konstruer en SDNF ved hjælp af denne sandhedstabel (tabel 2.2).
Tabel 2.2
| x | y | z | grundlæggende konjunktioner |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Grundlæggende konjunktioner (eller bestanddele_1) inkluderet i tabellen svarer til et specifikt sæt nuller og dem, der tager variable x,y,z. Bestanddele bliver bygget_ 1 efter følgende regel: en variabel er inkluderet i selve produktet, hvis den tager værdien 1 på et givet sæt, ellers er dens negation inkluderet i produktet. Så for eksempel på mængden (0,0,1) tager variablerne x,y værdien 0 og derfor er deres negationer inkluderet i produktet, og variablen z tager værdien 1 og er derfor inkluderet i selve produktet . For en given mængde (0,0,1) er bestanddel_1 lig med x ⋅ y ⋅ z .
Det er klart, at konjunktionen x ⋅ y ⋅ z kun er lig med 1 i mængden
(0,0,0), og x ⋅ y ⋅ z er 1 på sættet (0,0,1) osv. (se tabel). Bemærk dernæst, at disjunktionen af to grundlæggende konjunktioner er lig med 1 på præcis to sæt, der svarer til disse grundlæggende konjunktioner. For eksempel er funktionen x ⋅ y ⋅ z¤x ⋅ y ⋅ z kun lig med 1 på to sæt - (0,0,0) og (0,0,1), og på alle andre mængder er den lig med 0. Tilsvarende er disjunktionen af tre af basisforbindelser lig med 1 på nøjagtigt tre mængder, der svarer til disse grundforbindelser mv.
At. vi får regel: til at konstruere SDNF du skal vælge de rækker, hvor funktionen er lig med 1, og derefter tage disjunktionen af de tilsvarende hovedkonjunktioner, vi opnår den ønskede SDNF. Så for vores eksempel har vi x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Opgave. Brug denne sandhedstabel til at konstruere SCNF.
Forfatning_0 for et sæt af nuller og ettaller (som tager variablerne x,y,z) er konstrueret som følger: variablen er inkluderet i selve disjunktionen, hvis den tager værdien på dette sæt 0 , ellers omfatter værket dets negation.
Regel for konstruktion af SKNF: du skal vælge linjer, hvor funktionen er lig med 0 , og tag derefter konjunktionen af de tilsvarende bestanddele_0. Resultatet bliver den ønskede SCNF. Så for vores eksempel har vi f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Kommentar. For at konstruere en perfekt CNF-funktion f, er det nok at konstruere en perfekt DNF for funktionen f, og derefter
Lad os konstruere SCNF til vores eksempel baseret på bemærkningen. 1. Vi bygger en SDNF til negation.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Vi bruger de Morgans love f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z = y ⋅ z = y ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Den beskrevne metode til at finde SDNF (og SCNF) ved hjælp af sandhedstabellen er ofte mere arbejdskrævende end den følgende algoritme.
1. For at finde SDNF denne formel Vi reducerer først til DNF.
2. Hvis en eller anden konjunktion K (dvs. K er produktet af et vist antal variabler eller deres negationer) ikke inkluderer f.eks. variablen y, så erstatter vi denne konjunktion med den ækvivalente formel K&(y ∨ y) og anvender loven om distributivitet, præsenterer vi den resulterende formel til DNF; hvis der mangler flere variabler, tilføjer vi for hver af dem den tilsvarende formel for formen (y ∨ y) til konjunktionen.
3. Hvis den resulterende DNF indeholder flere identiske bestanddele af enheden, efterlader vi kun én af dem. Resultatet er SDNF.
Kommentar: At konstruere en SCNF til en klausul, der ikke indeholder f.eks. en variabel på vi tilføjer en formel på formen y⋅ y, dvs. Vi erstatter denne disjunkt med den ækvivalente formel D ∨ y⋅ y og anvender den 2. fordelingslov.
Eksempel 2. 2. 2. Konstruer en SDNF for funktionen f ved hjælp af ækvivalente transformationer.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z ⋅ z y ⋅ z y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =
TRÆKKE SIG TILBAGE.
Beregningen af SDNF er ikke kun teoretisk, men også af stor praktisk betydning. For eksempel i mange moderne programmer med en grafisk grænseflade til at komponere kompleks logiske forhold der bruges en visuel form i form af en tabel: betingelser er skrevet i cellerne, og cellerne i en kolonne anses for at være forbundet med en konjunktion, og kolonnerne anses for at være forbundet med en disjunktion, dvs. danne en DNF (eller omvendt, i dette tilfælde opnås en CNF). Det er især sådan den grafiske grænseflade QBE (Query-byExample) er designet, brugt til at formulere logiske betingelser, når der forespørges på et DBMS.
Algoritme 2.2.1. Opbygning af SDNF
Indgang: vektor X: række af streng - variable identifikatorer, matrix V: matrix af 0..1 af alle forskellige sæt af variabelværdier,
vektor F: matrix med 0..1 tilsvarende funktionsværdier.
Afslut: en sekvens af symboler, der danner en registrering af SDNF-formlen for en given funktion.
f:= falsk(tegn på tilstedeværelsen af venstre operand af disjunktionen) til jeg fra 1til 2n gør
hvis F[i] = 1 så hvis f derefter
udbytte"¤" (føjer et disjunktionstegn til formlen; operator udbytte m udskriver
symbol m) andet f:= rigtigt
Afslut Hvis g:= falsk(tegn på tilstedeværelsen af venstre operand af konjunktionen) til j fra 1til n gøre hvis g derefter
udbytte"⁄" (føjer et konjunktionstegn til formlen)
andet g: =sandt
ende hvis hvis V ( tilføjer en variabel-id til formlen
§2.3. DNF-minimering ved Quines metode.
Hver formel har endeligt nummer forekomster af variable. Forekomsten af en variabel refererer til den plads, som variablen indtager i formlen. Opgaven er at finde, for en given boolsk funktion f, en DNF, der repræsenterer denne funktion og har mindste antal forekomster af variable.
Hvis x er en logisk variabel, og σœ(0,1) så udtrykket x σ =xx hvis hvis σσ== 10 .
hedder brev . Konjunkt kaldet konjunktion af bogstaver. For eksempel er formlerne x ⋅ y ⋅ z og x ⋅ y ⋅ x ⋅ x konjunktioner . Et elementært produkt er en konjunktion, hvor enhver variabel ikke optræder mere end én gang (enten sig selv eller dens negation).
Formel f1 kaldes implikant formler f , hvis f1 er et elementært produkt og f 1 ⁄ f = f 1, dvs. altså for de funktioner, der svarer til formlerne, gælder uligheden f 1 § f. Implikanten f1 af en formel f kaldes enkel , hvis der efter at have kasseret et bogstav fra f1 ikke opnås en formel, der er en implikant af formlen f.
Eksempel 2.3.1 . Lad os finde alle implikanter og simple implikanter for formlen f=xØy . Der er i alt 8 elementære produkter med variable x Og u. Nedenfor er deres sandhedstabeller givet for klarhedens skyld:
| x | y | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Ud fra sandhedstabellerne konkluderer vi, at formlerne x ⋅ y , x ⋅ y , x ⋅ y , x ,y - alle implikanter af formlen xØy, og af disse implikanter er formlerne x og y simple (formlen x ⋅ y f.eks. er ikke en simpel implikant, da vi kasserer bogstavet y, får implikanten x).
Forkortet DNF kaldes disjunktionen af alle prime implikanter af en given formel (funktion) .
Sætning 2.3.1. Enhver boolsk funktion, der ikke er konstanten 0, kan repræsenteres som en stenografi DNF.
I eksempel 2.3.1 er funktionen svarende til formlen xØy repræsenteret af formlen x ∨ y, som er dens forkortede DNF.
En reduceret DNF kan indeholde ekstra implikanter, hvis fjernelse ikke ændrer sandhedstabellen. Hvis vi fjerner alle unødvendige implikanter fra en reduceret DNF, får vi en DNF kaldet blindgyde.
Bemærk, at repræsentationen af en funktion som en blindgyde DNF i almindelig sag tvetydig. Ved at vælge fra alle blindgydeformer giver den form med det mindste antal forekomster af variable minimal DNF (MDNF).
Overvej metoden Quina, at finde den MDNF, der repræsenterer en given boolsk funktion. Vi definerer følgende tre operationer:
1. fuld limningsdrift : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. delvis limning:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. funktion af elementær absorption f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Sætning 2.3.2(Quines sætning). Hvis vi, baseret på SDNF-funktionen, udfører alle mulige operationer med ufuldstændig limning og derefter elementær absorption, så vil resultatet være en reduceret DNF, dvs. en disjunktion af alle simple implikanter.
Eksempel 2.3.2. Lad funktionen f(x,y,z) være givet ved en perfekt DNF f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Derefter, ved at udføre i to trin alle mulige operationer med ufuldstændig limning og derefter elementær absorption, har vi
f 
Således er den forkortede DNF af en funktion f formlen y¤x·z.
I praksis, når du udfører ufuldstændige limningsoperationer på hvert trin, er det muligt ikke at skrive de termer, der er involveret i disse operationer, men kun at skrive resultaterne af alle mulige komplette limninger og konjunktioner, der ikke er involveret i nogen limning.
Eksempel 2. 3. 3. Lad funktionen f(x,y,z) være givet ved en perfekt DNF f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Derefter udfører vi limning og derefter elementær absorption, vi har
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
For at opnå den minimale DNF fra den reducerede DNF, bruges Quine-matrixen , som er opbygget som følger. Tabellens kolonneoverskrifter indeholder bestanddelene af den perfekte DNF-enhed, og rækkeoverskrifterne indeholder de simple implikanter fra den resulterende forkortede DNF. I tabellen markerer asterisker de skæringspunkter mellem rækker og kolonner, for hvilke konjunktionen i rækkeoverskriften er inkluderet i enhedens bestanddel, som er kolonneoverskriften.
For eksempel 2.3.3. Quine-matrixen har formen
I en blindgyde-DNF vælges minimumsantallet af simple implikanter, hvis disjunktion bevarer alle enhedens bestanddele, dvs. hver kolonne i Quine-matricen indeholder en stjerne i skæringspunktet med rækken, der svarer til en af udvalgte implikanter. Den blindgyde DNF, der har det mindste antal forekomster af variabler, vælges som minimum DNF.
I eksempel 2.3.3, ved hjælp af Quine-matrixen, finder vi, at minimum DNF for en given funktion er x ⋅ y ¤ x ⋅ z.
Kommentar.
brug f =f og De Morgans love.
§ 2.4. Carnot kort.
En anden måde at opnå simple implikante formler med et lille antal variable (og derfor at finde minimum DNF) er baseret på brugen af såkaldte Carnot-kort.
Carnot-kortet er speciel type en tabel, der forenkler processen med at finde minimale former og bruges med succes, når antallet af variable ikke overstiger seks. Karnaugh-kort for funktioner afhængigt af n variable er et rektangel opdelt i 2 n celler. Hver celle i diagrammet er forbundet med et binært n-dimensionelt sæt. Værdierne af en given funktion f fra sandhedstabellen indtastes i de nødvendige kvadrater, men hvis cellen svarer til 0, forbliver den normalt tom.
I tabel 2.4.1. viser et eksempel på markering af et Karnaugh-kort for en funktion, der afhænger af tre variable. De nederste fire celler på kortet svarer til binære sæt, hvori variablen x tager værdien 1, svarer de øverste fire celler til sæt, hvori variablen x tager værdien 0. De fire celler, der udgør den højre halvdel af kortet, svarer til mængder, hvori variablen y; tager værdien 1 osv. I tabel 2.4.2. Markeringen af Karnaugh-kortet for n=4 variabler er vist.
For at konstruere en minimal DNF udfører vi limningsprocedure "1". Værdierne "1", der klæber sammen, svarer til naboceller, dvs. celler, der kun adskiller sig i værdien af en variabel (ved grafisk fremstilling adskilt lodret el vandret linje under hensyntagen til nærheden af modsatte ekstreme celler).
Processen med at lime "1" kommer ned til at kombinere enkeltceller på Karnaugh-kortet i grupper, og følgende regler skal følges;
1. Antallet af celler, der indgår i én gruppe, skal udtrykkes som et multiplum af 2, dvs. 2 m hvor m=0,1,2,...
2. Hver celle, der indgår i en gruppe på 2 m celler, skal have m naboceller i gruppen.
3. Hver celle skal tilhøre mindst én gruppe.
4. Hver gruppe bør omfatte maksimalt antal celler, dvs. ingen gruppe bør være indeholdt i en anden gruppe.
5. Antallet af grupper skal være minimalt.
Læsefunktion f i henhold til limningsgruppen udføres som følger: variabler, der sparer samme værdier i cellerne i limgruppen indgår de i en konjunktion, og værdierne 1 svarer til variablerne selv, og værdierne 0 svarer til deres negationer.
Vi præsenterer skabeloner, der hjælper med at opbygge dækninger 1 (vi anser variablerne for at være de samme, men vi vil ikke skrive dem). For at forenkle notationen markerer vi ikke variablerne, selvom vi beholder deres betegnelser som i tabel 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=øy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Eksempel 2.4.1. Byg MDNF.
Først ser vi om der er nogen belægninger_ 1 ud af 16 celler, der dækker mindst én udækket 1. Der er ingen sådanne belægninger. Vi går videre til belægninger af 8 celler. Lad os se, om der er dæksler af 1 ud af 8 celler, der dækker mindst én udækket 1. Der er ingen sådanne dæksler. Vi går videre til belægninger af 4 celler. Lad os se, om der er dæksler af 1 af 4 celler, der dækker mindst en udækket 1. Der er to sådanne dækninger. Vi går videre til belægninger af 2 celler. Der er kun en sådan belægning. Dermed blev alle 1 dækket. Lad os derefter se, om vi kan fjerne nogle af belægningerne, så alle enheder forbliver dækket. Til sidst skriver vi MDNF ud: f =x⋅z∨y⋅w∨y⋅z⋅w.
Kommentar. For at konstruere den minimale CNF af en funktion f, er det nok at konstruere den minimale DNF for funktionen f, og derefter
brug f =f og De Morgans love.
Kapitel III. Zhegalkin algebra.
Sættet af booleske funktioner defineret i Zhegalkin-grundlaget S4=(∆,&,1) kaldes Zhegalkin-algebraen.
Grundlæggende egenskaber.
1. kommutativitet
H1∆H2=H2∆H1, H1&H2=H2
2. associativitet
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. distributivitet
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. egenskaber af konstanterne H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Udtalelse 3.1.1. Alle andre boolske funktioner kan udtrykkes gennem operationerne i Zhegalkin algebra:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Definition. Zhegalkin-polynomiet (polynomium modulo 2) af n variable x 1 ,x 2 ,…,x n er et udtryk for formen c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2s med k12…nx1x2s kan have værdierne 0 eller 1.
Hvis Zhegalkin-polynomiet ikke indeholder produkter af individuelle variable, så kaldes det lineær (lineær funktion).
For eksempel er f=x∆yz∆xyz og f1=1∆x∆y∆z polynomier, den anden er en lineær funktion.
Sætning 3.1.1. Hver boolsk funktion er repræsenteret i form af et Zhegalkin-polynomium på en unik måde.
Lad os præsentere de vigtigste metoder til at konstruere Zhegalkin polynomier ud fra en given funktion.
1. Metode usikre koefficienter. Lad P(x 1 ,x 2 ,...,x n) være det ønskede Zhegalkin-polynomium, der implementerer den givne funktion f(x 1 ,x 2 ,...,xn). Lad os skrive det i formularen
P= c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Lad os finde koefficienterne med k. For at gøre dette tildeler vi sekventielt variablerne x 1 , x 2 ,…, x n værdier fra hver række i sandhedstabellen. Som et resultat opnår vi et system med 2 n ligninger med 2 n ubekendte, der har eneste beslutning. Når vi har løst det, finder vi koefficienterne for polynomiet P(x 1 ,x 2 ,...,xn).
2. En metode baseret på at transformere formler over et sæt af forbindelser ( ÿ,&}. Konstruer en formel Ф over sættet af forbindelsesled (Ÿ,&), realiser den givne funktion f(x 1 ,x 2 ,...,x n). Erstat derefter underformler af form A overalt med A∆1, åbn parenteserne ved hjælp af fordelingsloven (se egenskab 3), og anvend derefter egenskaberne 4 og 5.
Eksempel 3.1.1. Konstruer et Zhegalkin-polynomium for funktionen f(x,y)=xØy.
Løsning. 1 . (metode med ubestemte koefficienter). Lad os skrive det påkrævede polynomium i formen
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Brug af sandhedstabellen
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
vi finder, at f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= c 0 ∆c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1
Hvorfra vi konsekvent finder, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Derfor xØy=1∆x∆xy (sammenlign med udsagn 3.1).
2.(Formelkonverteringsmetode.) Vi har
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Bemærk, at fordelen ved Zhegalkin algebra (sammenlignet med andre algebraer) er aritmetisering af logik, som gør det muligt at udføre transformationer af boolske funktioner ganske enkelt. Dens ulempe sammenlignet med boolsk algebra er formlernes besværlighed.
Kapitel IV. Udsagn. Prædikater.
§4.1. Udsagn.
Når vi konstruerede logikkens algebra, brugte vi funktionel tilgang. Det ville dog være muligt at konstruere denne algebra konstruktivt. Først skal du definere undersøgelsesobjekterne (udsagn), introducere operationer på disse objekter og studere deres egenskaber. Lad os give formelle definitioner.
Ved at sige Lad os kalde en deklarativ sætning, om hvilken man utvetydigt kan sige, om den er sand (værdi I eller 1) eller falsk (værdi L eller 0) på et bestemt tidspunkt. For eksempel, "5 er et primtal", "Esc-tast trykket" osv. Brug af forbindelser "ikke", "og", "eller", "hvis,... så", "hvis og kun hvis" (de svarer til operationerne "Ÿ", "&", "¤", "Ø" , "~" » følgelig kan mere komplekse udsagn (sætninger) konstrueres. Sådan er propositionalgebra opbygget.
For at forenkle registreringen af komplekse udsagn introduceres forrangen af connectives: "Ÿ", "&", "¤", "Ø", "~", hvilket hjælper med at udelade unødvendige parenteser.
Vi kalder simple udsagn propositionsvariable.
Lad os introducere begrebet en formel.
1. Propositionelle variabler er formler.
2. Hvis A, B er formler, så er udtrykkene ŸA, A⁄B, A¤B, AØB, A~B formler.
3. Formler er kun udtryk konstrueret i overensstemmelse med stk. 1 og 2.
En formel, der tager værdien AND for alle værdier af propositionelle variabler, kaldes tautologi (eller generelt gyldig), og en formel, der tager værdien A for alle værdier af de propositionelle variable, kaldes modstridende (eller umuligt)
Beskrivelsen af egenskaberne ved propositionalgebra svarer til beskrivelsen af de tilsvarende funktioner i boolsk algebra, og vi udelader dem.
§4.2. Prædikater. Logiske operationer på prædikater.
Emnet for undersøgelsen i dette kapitel vil være prædikater - kortlægninger af vilkårlige mængder til et sæt af udsagn. Faktisk laver vi overgangen til nyt niveau abstraktioner, en overgang af den type, der blev lavet i skolen - fra aritmetikken af reelle tal til algebraen af numeriske funktioner.
Definition 2.1 Lad x 1 ,x 2 ,...,xn være symboler for variable af vilkårlig karakter. Vi vil kalde disse variable for emnevariable. Lad mængderne af variable (x 1 ,x 2 ,...,x n) høre til mængden M=(M1,M2,...Mn), som vi vil kalde emneområdet (dvs. x i œM i, hvor Mi kaldes domænet definition af variablen xi). Lokalitetsprædikat n (n-stedsprædikat) defineret på emneområde M, er en logisk funktion, der tager enten værdien AND eller værdien L.
Eksempel 4.2.1. D(x1,x2) = "Det naturlige tal x1 divideres (uden rest) med det naturlige tal x2." - et prædikat på to pladser defineret på et sæt par naturlige tal M=NäN. Det er klart, D(4,2) = Og D(3,5) = 0.
Eksempel 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) - тождественно ложен, т. е.
Q(x) = А for alle xœR.
Eksempel 4.2.3. B(x,y,z) = "x 2 +y 2 Et prædikat P defineret på M kaldes identisk sandt, hvis det tager værdien AND for alle værdier af emnevariablerne; Prædikatet P kaldes identisk falsk, hvis det tager værdien A for alle værdier af emnevariablerne. Prædikat Q fra eksempel 4.2.2. er identisk falsk. Da prædikater er funktioner med værdier i et sæt af udsagn, hvor logiske operationer er introduceret, er disse operationer naturligt defineret for prædikater. Lad P og Q være prædikater defineret på M. Derefter 1. ¬P(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,...,x n) ∨ Q(x 1 ,x 2 ,...,x n) 4. (P → Q)(x 1 ,x 2 ,...,x n) = P(x 1 ,x 2 ,...,x n) → Q(x 1 ,x 2 ,...,x n) Prædikater P og Q, defineret på M kaldes ækvivalent (skriv P=Q), hvis P(x 1 ,x 2 ,...,xn)=Q(x 1 ,x 2 ,...,xn) for ethvert sæt (x 1 ,x 2 ,..., x n) )
emnevariabler fra M .
Sætning 4.2.1 Sættet af n-ære prædikater defineret på M danner en boolsk prædikatalgebra. De grundlæggende ækvivalenser er således gældende for dem (se §1.6). Lad P(x 1 ,x 2 ,…,xn) være et n-ært prædikat defineret på M. Lad os fikse x i = -en. Lad os definere det (n-1)-ære prædikat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) som følger: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x1,x2,…,xk1, -en,xk+1,xn). De siger, at prædikatet Q(x 1 ,x 2 ,...,xk-1, xk+1,xn) fås fra prædikatet P(x 1 ,x 2 ,...,xn) ved at fastsætte værdien af i- variabel: x i = -en
. Definition
4.3.1
. Lad P(x) være et unært prædikat. Lad os forbinde med det et udsagn betegnet "xP(x) (læs "for enhver x P(x)"), hvilket er sandt, hvis og kun hvis P(x) er et identisk sandt prædikat. Udsagnet "xP(x) siges at være, at det opnås fra prædikatet P ved at knytte en universel kvantifier over variablen x. Definition 4.3.2. Lad P(x) være et unært prædikat. Lad os forbinde det med et udsagn betegnet $xP(x) (læs "der er x P(x)"), som er falsk, hvis og kun hvis P(x) er et identisk falsk prædikat. Udsagnet $xP(x) siges at være opnået fra prædikatet P ved at knytte en eksistentiel kvantifier til variablen x. Note 1. Symbolerne " og $ for kvantifikatorer er omvendte latinske bogstaver henholdsvis A og E, som er de første bogstaver i engelske ord Alle- Alle, Eksisterer- eksisterer. Note 2. Udsagn kan betragtes som prædikater, der ikke indeholder variable, det vil sige 0-stedsprædikater (eller prædikater af enhver lokalitet). Lad P(x 1 ,x 2 ,...,xn) være et n-ært prædikat defineret på M. Lad os fastsætte værdierne af variablerne x 1 ,x 2 ,...,x k-1 ,x k i det +1,xn. Vi knytter en universel (eksistens) kvantifier til det resulterende unære prædikat Q(x k) og får et udsagn. Således er et fast sæt værdier af variabler x 1 , x 2 ,..., x k-1 , x k+1 , x n forbundet med en sætning ved hjælp af kvantifieren af universalitet (eksistens). Dette (n-1)-ære prædikat af variablerne x 1 ,x 2 ,…,x k-1 ,x k+1 ,xn siges at være opnået fra det oprindelige prædikat P(x 1 ,x 2 ,…, x n) ved at tilføje en kvantifier universalitet (eksistens) i den kth variabel. Dette prædikat er betegnet: "x til P(x 1 ,x 2 ,...,x n) ($x til P(x 1 ,x 2 ,...,x n)). Om den k-te variabel (som ikke længere eksisterer) de siger, at den er bundet af universalitetens (eksistens) kvantifier. Eksempel 4.3.1. Lad D(x1,x2) = "Det naturlige tal x1 er deleligt (uden rest) med det naturlige tal x2." - prædikat på to pladser. Lad os tildele kvantifikatorer successivt til dens variable. Det er klart 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Således (ved at sammenligne 7 og 8 i det sidste eksempel) beviste vi sætningen: Typisk er forbindelsesled og kvantifikatorer sorteret efter prioritet som følger: Ÿ, ", $, &, ¤, Ø, ~. Sætning 4.3.1. Modsatte kvantificatorer pendler generelt ikke. Sætning 4.3.2.(grundlæggende ækvivalenser, der indeholder kvantifikatorer) Følgende ækvivalenser finder sted: 1. De Morgans love ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Kommutativitet ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Distributivitet ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Begrænsninger for kvantifikatorers virkning ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. For ethvert prædikat med to pladser ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Formel teori(eller beregning)
Y- Det her: 1. sæt EN
tegn dannes alfabet
;
1.
en masse F
ord i alfabetet A, F
à EN
som kaldes formler
;
3. delmængde B
formler, B
à F
,
som kaldes aksiomer; 4. mange relationer R
på et sæt formler kaldet slutningsregler. Masser af symboler EN
kan være endelig eller uendelig. Normalt bruges et endeligt sæt bogstaver til at danne symboler, som om nødvendigt tildeles naturlige tal som indekser. Masser af formler F
normalt givet ved induktiv definition, for eksempel ved hjælp af en formel grammatik. Som regel er dette sæt uendeligt. Sæt EN
Og F
i fællesskab bestemme Sprog
,
eller Underskrift
,
formel teori. Mange aksiomer B
kan være endelig eller uendelig. Hvis sættet af aksiomer er uendeligt, så specificeres det som regel ved hjælp af et endeligt sæt af aksiomskemaer og regler for generering af specifikke aksiomer fra aksiomskemaet. Masser af slutningsregler R
som regel selvfølgelig. Altså kalkulus Y der er en fire (A, F, B, R)
. Ved afledning i calculus Y er en sekvens af formlerne F 1 , F 2 ,…,Fn således, at for enhver k (1§k§n) er formlen Fk enten et aksiom for Y-regning eller en direkte konsekvens af tidligere formler opnået ved inferensreglen . En formel G kaldes en sætning af calculus Y (afledes i Y eller beviselig i Y), hvis der er en konklusion F 1 ,F 2 ,...,F n ,G som kaldes en afledning af formlen G eller et bevis for sætning G. Dette skrives som følger: F 1,F 2,...,F n + G. Calculus Y hedder konsekvent, hvis ikke alle dets formler kan bevises. En anden definition af konsistens kan gives: En calculus kaldes konsistent, hvis formlerne F og ŸF (negationen af F) ikke samtidig kan udledes i den. Calculus Y hedder komplet(eller tilstrækkeligt), hvis hvert sandt udsagn M svarer til en teoris sætning Y
. Formel teori Y hedder afgøres, hvis der er en algoritme, der for en hvilken som helst formel i teorien bestemmer, om denne formel er en teoris sætning Y eller ikke. Ved hjælp af begrebet formel calculus definerer vi propositional calculus (PS). Alfabet IW består af 1. bogstaver A, B, Q, R, P og andre, eventuelt med indeks (som kaldes propositionelle variabler), 2. logiske symboler(ligamenter) Ÿ, &, ¤, Ø, 3. hjælpe tegn
(,). Masser af formler IV bestemmes induktivt: 1. alle propositionelle variabler er IV-formler; 2. hvis A, B er formlerne IV ,
toŸA, A⁄B, A¤B, AØB - formlerIV ;
3. et udtryk er en IV-formel, hvis og kun hvis dette kan etableres ved hjælp af punkterne "1" og Enhver IV-formel er således konstrueret ud fra propositionelle variabler ved hjælp af bindeled Ÿ, ⁄, ¤, Ø. I fremtiden, når vi skriver formler, vil vi udelade nogle parenteser ved at bruge de samme konventioner som i det foregående kapitel. Aksiomer IV er følgende formler (for alle formler A,B,C) 2. (AØB)Ø((AØ(BØC))Ø(AØC)); 5. (AØB)Ø((AØC)Ø(AØ(B⁄C))); 8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA); Disse formler kaldes IV-aksiomskemaer .
Når du substituerer specifikke formler i et hvilket som helst skema, opnås et særligt tilfælde af aksiomskemaet. Regel for slutning i IE er der en konklusionsregel (modus ponens): hvis A og AØB er afledelige formler, så er B også afledelig Symbolsk er det skrevet sådan: A, A B →
B
. For eksempel, hvis udsagn A⁄B og A⁄BØ(AØC) er deducerbare, så er udsagnet AØC også afledeligt efter inferensreglen. En formel G siges at kunne udledes fra formlerne F 1 ,F 2 ,...,F n (benævnt F 1 ,F 2 ,...,F n +G), hvis der er en sekvens af formlerne F 1 ,F 2 ,... ,F k ,G , hvor enhver formel enten er et aksiom eller hører til listen over formler F 1,F 2,...,F n (kaldet hypoteser), eller er hentet fra tidligere formler i henhold til reglen om slutning. Afledningsevnen af formlen G fra " (angivet med +G) svarer til, at G er en IV-sætning. Eksempel 5.2.1. Lad os vise, at formlen AØA kan udledes i IV. For at gøre dette vil vi konstruere afledningen af denne formel: 1) i aksiom 2 erstattes B med AØA, C med A. Vi får aksiomet (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) i aksiom 1 erstatter vi B med A. Vi får AØ(AØA); 3) fra 1 og 2 ifølge modus ponens konkluderer vi (AØ((AØA)ØA))Ø(AØA); 4) i aksiom 1 erstatter vi B med AØA. Vi får AØ((AØA)ØA); 5) fra stk. 3 og 4, ifølge inferensreglen, er + AØA sand. Sætning 5.2.1. 1. Hvis F 1 ,F 2 ,…,Fn,A,B er IV-formler, Г=(F 1 ,F 2 ,...,Fn), Г+A, så Г,B+A. (du kan øge antallet af hypoteser). 2. Hvis og kun hvis F 1 ,F 2 ,…,F n +A, når F 1 ⁄F 2 ⁄…⁄F n +A (reduktion af mange hypoteser til én hypotese). Sætning 5.3.1. (deduktionssætning) Hvis Г,B+A, så Г+BØA, hvor Г er et sæt af nogle formler Г=(F 1 ,F 2 ,...,F n ). Konsekvens 5.3.1. Så og kun hvis F 1 ,F 2 ,...,F n +A, når Bevis. Lad F 1 , F 2 ,..., F n +A. Så, ved at anvende deduktionssætningen, har vi F 1 ,F 2 ,...,F n-1 +F n ØA. Tilsvarende F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA), osv. Fortsætter processen det nødvendige antal gange, får vi F 1 Ø(F 2 Ø...Ø(F n-1 Ø(F n ØA))...) For at bevise tilstrækkelighed, antag, at +B, hvor B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))...). Lad os bruge sætning 5.2.1., punkt 1: F1+B .
Ifølge konklusionsreglen får vi F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))...), så har vi efter n trin F 1 ,F 2 ,…,F n +A . Takket være konsekvens 5.3.1., er kontrol af deducerbarheden af formel A fra formlerne F 1, F 2,..., F n reduceret til at kontrollere formlens bevislighed F 1 Ø(F 2 Ø...Ø(F n-1 Ø(F n ØA))...). Husk på, at en formel A kaldes identisk sand (eller en tautologi), hvis værdien af formlen A er lig med én for ethvert sæt værdier af propositionsvariablerne. Følgende sætning reducerer verifikationen af bevisligheden af en formel til verifikationen af dens identiske sandhed. Sætning 5.3.2. (om fuldstændighed). Formel A kan bevises, hvis og kun hvis A er identisk sand (tautologi): +A ‹ A-tautologi. For at afgøre, om en formel er beviselig, er det således nok at kompilere dens sandhedstabel. Som det er kendt, er der en effektiv algoritme til at konstruere en sandhedstabel, og derfor IV løselig. Eksempel 5.3.1. Lad os bevise, at P+P. Ved deduktionssætningen svarer dette til +(PØP). Til gengæld er det ifølge fuldstændighedssætningen nok til at bevise, at (РØР) er en tautologi. Udarbejdelse af en sandhedstabel for formlen (РØР) ,
Vi er overbevist om, at (РØР) er identisk sandt og derfor beviselig. Sætning 5.3.3. (om konsistens). IW-regningen er konsistent. Bevis. Ifølge fuldstændighedssætningen kan enhver formel, der ikke er identisk sand, ikke bevises i IW. For eksempel er en sådan formel formlen A⁄(ŸA). Sættet af formler Г kaldes kontroversielle
,
hvis Г+А⁄(ŸА) .
Hvis Г er et modstridende sæt af formler, vil vi betegne dette faktum med Г+. Udmelding
5.3.1.
Formel A kan udledes fra mængden af formler Г hvis og kun hvis mængden Г»(ŸA) er modstridende. Automatisk teorembevis er hjørnestenen i logisk programmering, kunstig intelligens og andre moderne tendenser inden for programmering. Generelt set er der måske ikke en algoritme, hvormed man, givet en vilkårlig formel A, efter et endeligt antal trin kan bestemme, om A er deducerbar i kalkulationen Y eller ej. For nogle simple formelle teorier (f.eks. propositionsregning) og nogle simple klasser af formler (f.eks. anvendt prædikatregning med ét unært prædikat) kendes algoritmer til automatisk sætningsbevis. Nedenfor skitserer vi ved hjælp af eksemplet med propositionalregning det grundlæggende i opløsningsmetoden - en klassisk og samtidig populær metode til automatisk at bevise teoremer. Husk, at hvis x er en logisk variabel, og σœ(0,1) så udtrykket x σ = xx hvis hvis σσ == 10 eller x σ = 10 hvis hvis x x =≠σσ , kaldes brev. Bogstaverne x og Ÿx kaldes modstridende.
Konjunkt kaldet konjunktion af bogstaver. disjunkt kaldet adskillelse af bogstaver. Lad D 1 = B 1 ∨ A, D 2 = B 2 ∨ A være led. Klausulen B 1 ¤B 2 kaldes opløsningsmiddel klausulerne D 1 og D 2 med bogstavet A og er betegnet med res A (D 1 ,D 2). Resolventen af sætningerne D 1 og D 2 er resolventen med et bogstav og er betegnet med res(D 1 ,D 2). Naturligvis res(A,ŸA)=0. Faktisk fordi A=A¤0 og ŸA=ŸA¤0, derefter res(A,ŸA)=0¤0=0. Hvis sætning D 1 og D 2 ikke indeholder kontrasterende tegn, har de ikke opløsningsmidler. Eksempel 5.5.1. Hvis D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, så res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) eksisterer ikke. Udtalelse 5.5.1. Hvis res(D1,D2) eksisterer, så D1,D2 + res(D1,D2). Lad S=(D 1 ,D 2 ,...,Dn) være sættet af klausuler. En sekvens af formlerne F 1 , F 2 ,...,F n kaldes en resolut afledning fra S, hvis en af betingelserne for hver formel F k er opfyldt: 2. der er j, k
Sætning 5.5.1.
(om opløsningsmetodens fuldstændighed). Et sæt sætninger S er modstridende, hvis og kun hvis der er en resolut konklusion fra S, der ender på 0. Bemærk, at opløsningsmetoden kan bruges til at kontrollere deducerbarheden af en formel F fra et givet sæt af formler F 1, F 2,..., F n. Faktisk er betingelsen F 1 ,F 2 ,...,F n +F ækvivalent med betingelsen F 1 ,F 2 ,...,F n ,ŸF+ (mange formler er modstridende), som igen er ækvivalent med betingelsen Q+, hvor Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Lad os reducere formlen Q til CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, derefter Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Opgaven med at kontrollere deducerbarheden af F 1 ,F 2 ,...,F n +F kommer således ned på at kontrollere inkonsistensen af sættet af klausuler S=(D 1 ,D 2 ,...,D m ) , hvilket svarer til eksistensen af en dekret konklusion 0 fra S. Eksempel 5.5.2. Tjek forholdet AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) ved hjælp af opløsningsmetoden. Ifølge redegørelse 5.3.1. skal tjekke efter uoverensstemmelse mange formler S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Vi præsenterer alle formlerne fra. S til KNF: S = (A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), A ⋅ B ⋅ F) . Således får vi et sæt af klausuler S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Lad os konstruere en resolut konklusion fra S, der slutter med 0: 1. res A (A ∨ B ∨ C,A) = B ∨ C ; 2. res B (B ∨ C,B) = C; 3. res D (C ∨ D ∨ E,F ∨ D) = C ∨ E ∨ F ; 4. res E (C ∨ E ∨ F,F ∨ E) = C ∨ F ; 5. res C (C, C ∨ F) = F; 6. res(F, F) = 0 . Så vi konkluderer, at formlen AØ(BØF) kan udledes fra mængden af formler AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Bemærk, at opløsningsmetoden er tilstrækkelig til at opdage den mulige tilfredsstillelse af et givet sæt sætninger S. For at gøre dette, lad os inkludere i mængden S alle sætninger opnået ved resolutive deduktioner fra S. Fra sætningen om opløsningsmetodens fuldstændighed det følger Konsekvens 5.5.1. Hvis et sæt sætninger S indeholder opløsningsmidlerne for alle dets elementer, er S tilfredsstillende, hvis og kun hvis 0–S. Et karakteristisk træk ved moderniteten er den udbredte brug af computere til at løse problemer (opgaver) inden for forskellige områder af menneskelig aktivitet. Problemet skal dog først løses algoritmisk, dvs. der skal gives en formel recept, hvorefter man kan opnå det endelige resultat for at løse alle problemer af en bestemt type (dette er et intuitivt, ikke strengt koncept for en algoritme). For eksempel en algoritme til at finde den største fælles divisor af to naturlige tal a, b, som følger: 1) udvide antallet -en efter primære faktorer; 2) gentag trin 1 for b
Og gå til trin 3; 3) komponer produktet af almindelige primfaktorer fra udvidelser EN Og b med indekser lig med det mindste af indeksene for inklusion i udvidelserne. Efter at have analyseret dette eksempel bemærker vi de vigtigste funktioner (egenskaber) af algoritmen: 1.
Massekarakter- algoritmens anvendelighed ikke på et problem, men på en klasse af problemer. 2.
Diskrethed- en klar opdeling i individuelle stadier (trin) af algoritmen. 3.
Determinisme- sådan en organisering af udførelsesfaser, hvor det altid er klart, hvordan man kan foretage overgangen fra et trin til et andet. 4.
Lem- for at opnå et resultat, når du anvender en algoritme til at løse et specifikt problem, udføres en endelig rækkefølge af trin i algoritmen: Bemærk, at hvis tilstedeværelsen af en algoritme i sig selv tjener som bevis for eksistensen af en algoritme, så er det nødvendigt at have en streng matematisk definition af en algoritme for at bevise dens fravær. Forsøg på at formalisere begrebet en algoritme førte til skabelsen Turing maskiner, som en eller anden imaginær enhed, der implementerer algoritmen. Et andet skridt i at definere begrebet en algoritme var udseendet rekursive funktioner ,
som funktioner, der formaliserer begrebet en algoritme og implementerer det intuitive begreb om beregningsevne. Det blev hurtigt opdaget, at sættet af rekursive funktioner faldt sammen med det sæt funktioner, der kunne beregnes på Turing-maskiner. Nye begreber, der så dukkede op, der hævdede at forklare begrebet en algoritme, viste sig at svare til funktioner, der kunne beregnes på Turing-maskiner, og derfor til rekursive funktioner. Resultatet af den igangværende diskussion om, hvad en algoritme er, var et udsagn, der nu kaldes Kirkens tese. kirkens afhandling. Begrebet en algoritme, eller beregnelighed af en eller anden mekanisk enhed, falder sammen med begrebet beregnelighed på Turing-maskiner (og derfor med begrebet en rekursiv funktion). Med andre ord er en algoritme en proces, der kan repræsenteres af et funktionelt diagram og implementeres af en Turing-maskine. En Turing-maskine er en (abstrakt) enhed bestående af et bånd, en kontrolenhed og et læsehoved. Båndet er opdelt i celler. Hver celle indeholder præcis ét tegn fra ydre alfabet
A=(
en 0,
en 1,…,
a n). Et eller andet symbol (vi vil betegne det Ÿ
) i alfabetet A kaldes tom, og enhver celle, der i øjeblikket indeholder et tomt tegn, kaldes en tom celle (på det tidspunkt). Båndet antages at være potentielt ubegrænset i begge retninger. Kontrolenhed på hvert tidspunkt er i en eller anden tilstand q j, der hører til sættet Q=(q 0 , q 1 ,..., q m )(m=l). Mængden Q kaldes indre alfabet
.
En af disse betingelser (normalt q 0) kaldes endelig, og nogle andre (normalt q 1) - initial. Læsehovedet bevæger sig langs båndet, så det til enhver tid scanner præcis én celle på båndet. Hovedet kan læse indholdet af den observerede celle og skrive ind i den i stedet for det observerede symbol et nyt symbol fra det eksterne alfabet EN(muligvis den samme). Under drift ændrer kontrolenheden, afhængigt af den tilstand, den er placeret i, og symbolet set af hovedet, sin interne tilstand q. Derefter giver den hovedet en ordre om at udskrive et bestemt tegn fra det eksterne alfabet i cellen, der overvåges EN, og kommanderer derefter hovedet til enten at blive på plads eller flytte en celle til højre eller flytte en celle til venstre. Når maskinen er i den endelige tilstand, holder den op med at fungere. Konfiguration på bånd (eller maskinord) kaldes mængden dannet af: 1) rækkefølge -en
i (1)
, a
i(2)
,...,en
er) tegn fra det ydre alfabet EN, optaget i båndceller, hvor -en
jeg
(1)
.- symbolet skrevet i den første celle til venstre osv. (enhver sådan sekvens kaldes i et ord), 2) tilstanden af den interne hukommelse qr; 3) nummer k opfattet celle. Vi skriver maskinkonfigurationen som følger: a ,a ,..., a a i(r) a ,a ,..., a i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s) Her r- den opfattede celle fremhæves som en brøkdel. Hvis maskinen er i intern tilstand qi, accepterer en celle med et symbol et u, skriver et symbol til denne celle på næste tidspunkt en r, går ind i den interne tilstand qs og bevæger sig langs båndet, så siger de, at maskinen udfører kommandoen q jeg a u
Æ
q s a r S, hvor symbolet S kan have en af følgende værdier: -1 – skift hovedet til venstre; +1 - hovedskift til højre; 0 – hovedet forbliver på plads. Listen over alle kommandoer (kvint), der bestemmer driften af en Turing-maskine, kaldes program denne bil. Maskinprogrammet er ofte specificeret i form af en tabel. Så for situationen beskrevet ovenfor i tabellen ved krydset linjer -en
u og kolonne qi vil stå q s a r S(se tabel 6.2.1) Tabel 6.2.1. Hvis programmet omfatter biler til et par (
q i,a u
)
fem mangler, så i tabellen i skæringspunktet mellem linjen et u, og kolonne qi en tankestreg tilføjes. Så, En Turing-maskine er per definition, sæt M=(A,Q,P), Hvor EN- eksternt alfabet, Q- alfabet af indre tilstande, P- program. Hvis en maskine, der er begyndt at arbejde med et ord P skrevet på bånd, når den endelige tilstand, så kaldes den gælder for dette ord. Resultatet af dets arbejde er det ord, der er optaget på båndet i sin endelige tilstand. Ellers siges maskinen ikke at være anvendelig til ordet R. Eksempel 6.2.1. Lad os bygge en Turing-maskine, der tilføjer naturlige tal skrevet i det unære talsystem (det vil sige skrevet med et symbol |.
For eksempel 5=|||||.). Løsning. Overvej alfabetet EN
= {|, +, ⁄}. Maskinen bestemmes af følgende program: Lad os nedskrive de konfigurationer, der opstår sekventielt under driften af denne maskine på det indledende ord ||+ ||| , dvs. 2+3. Her, når vi optager konfigurationen, vil vi bruge følgende konvention: tilstanden, hvori maskinen er placeret, er skrevet i parentes til højre bag det bogstav, der observeres. Eksempel 6.2.2. Byg en Turing-maskine, der fordobler naturlige tal skrevet i det unære talsystem. Løsning. Vi vil konstruere den nødvendige maskine i alfabetet A=(|, α, ⁄). Programmet til sådan en maskine kan se sådan ud: Lad os anvende den resulterende maskine på ordet ||
. Indførelse af et nyt bogstav α og udskiftning af de originale |
på α gør det muligt at skelne originalen |
og ny (tildelt) |
. Stat q 1 sørger for erstatning |
på α ,
stat q 2 giver søgning efter α ,
beregnet til at erstatte |
, og standsning af maskinen i tilfælde af, at α ikke detekteres, q 3 sikrer færdiggørelse |
i det tilfælde, hvor α blev erstattet af |.
Lad os være enige i dette afsnit 1. mængden N af naturlige tal indeholder 0 (nul), dvs. N=(0,1,2,3,...); 2. funktionerne under overvejelse f=f(x 1 ,x 2 ,...,x n) defineres kun, når variablerne tager værdier fra N, dvs. xiœN; 3. række af værdier for funktioner DŒN; 4. funktionerne under overvejelse f=f(x 1 ,x 2 ,...,x n) kan defineres delvist, dvs. ikke defineret for alle sæt naturlige tal. Lad os introducere i betragtning simple funktioner o(x)=0, s(x)=x+1,
I m n (x 1,..., x n)
=
x m Disse funktioner kan beregnes ved hjælp af en passende mekanisk enhed (for eksempel en Turing-maskine). Lad os definere operatorer, der konstruerer nye funktioner baseret på en eller flere givne funktioner. Superpositionsoperatør. Lad funktionen f(x 1 ,x 2 ,...,x k) af k variable og k funktioner f 1 (x 1 ,x 2 ,...,x n),...,f k (x 1 ,x 2 ,...,x n) være givet n variable. En superposition af funktioner f,f 1 ,...,f k er funktionen j(x 1 ,x 2 ,...,x n)= f(f 1 (x 1 ,x 2 ,...,x n),...,f k (x 1 ,x 2 ,…,x n)) Vi siger, at funktion j opnås ved at anvende superpositionsoperatoren S k+1 på funktionerne f,f 1 ,…,f k , og skrive j=S k+1 (f,f 1 ,…,f k) F.eks. 2 (s, o)=s(o(x)), dvs. en funktion identisk lig med 1, og S 2 (s,s)=s(s(x)) er en funktion y(x)=x+2. Primitiv rekursionsoperatør. Lad funktionerne g(x 1 ,x 2 ,…,x n) og h(x 1 ,x 2 ,…,x n+2) være givet. Lad os konstruere en funktion f(x 1 ,x 2 ,…,x n+1) Lad værdierne x 1 ,x 2 ,…,x n være faste. Så antager vi: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) f 1 (x 1, x 2 ,…,xn,y+1)= h(x1,x2,…,xn,y, f(x1,x2,…,xn,y)) Disse ligheder definerer funktionen f(x 1 ,x 2 ,...,x n+1) entydigt. En funktion f kaldes en funktion opnået ved hjælp af den primitive rekursionsoperator R. Notationen f=R(g,h) bruges. Induktiv definition af en funktion (påvist i den primitive rekursionsoperator) er ikke ualmindeligt i matematik. For eksempel, 1) en grad med en naturlig eksponent bestemmes induktivt: -en
0
=1, -en n+ 1
=a n
ÿ -en
; 2) faktoriel: 0!=1, (n+1)!= n!ÿ(n+1), osv. Definition. Funktioner, der kan opnås fra den simpleste o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m ved at anvende superpositionsoperatorer og primitiv rekursion et endeligt antal gange hedder primitivt rekursivt. Lad os kontrollere, at funktionen u(x,y)=x+y er primitiv rekursiv. Faktisk har vi: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Dette er et primitivt rekursionsskema, da x= I 1 1 (x), og u(x,y)+1=s(u(x,y))=S 2 (s,u). Her er g(x)= I 1 1 (x), og h(x, y, u)=s(u)=S 2 (s, I 3 3). Det er ligeledes bevist, at funktionerne m(x,y)=xÿy, d(x,y)=x y (vi antager per definition 0 0 =1), fakta(x)=x! og mange andre er primitivt rekursive. Bemærk; at primitivt rekursive funktioner er defineret overalt (det vil sige defineret for alle værdier af deres argumenter). Faktisk de enkleste funktioner o, s, I m n er defineret overalt, og anvendelse af superposition og primitive rekursionsoperatorer på overalt definerede funktioner giver også overalt definerede funktioner. Altså en funktion som = x − y, hvis x ≥ y< y f(x,y) eksisterer ikke, hvis x kan ikke være primitivt rekursivt. Vi har ingen ret til at betragte funktionen f(x,y)=x-y her, da funktionsværdierne skal være naturlige tal (derfor ikke negative). Man kan dog overveje funktionen ÷ y = 0x − y ifif x x<≥y.y Lad os kontrollere, at det er primitivt rekursivt. Lad os først bevise, at funktionen j(x)=xπ1 er primitiv rekursiv. Faktisk, j(0)=0. j(y+1)=(y+1)π1=y, der fungerer som et primitivt rekursionsskema for funktionen xπ1. Endelig er xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) et primitivt rekursionsskema for xπy. En væsentligt bredere klasse af funktioner end primitive rekursive funktioner er klassen af rekursive funktioner (se definition nedenfor). I litteraturen kaldes disse funktioner også delvist rekursivt .
For at bestemme dem introducerer vi endnu en operatør. Minimeringsoperatør. Lad funktionen f(x 1 ,x 2 ,… ,x n ,x n+1) være givet. Lad os rette nogle værdier x 1 ,x 2 ,… ,x n af de første n variable og beregne f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,... ,x n ,2) osv. Hvis y er det mindste naturlige tal, for hvilket f(x 1 ,x 2 ,... X n ,y)=x n+1 (dvs. værdier f(x 1 ,x 2 ,... ,x n ,0), f(x 1 ,x 2 ,... ,x n ,1),...,f( x 1,x2,... Xn ,y-1) eksisterer alle og er ikke lig med xn +1), så sætter vi g(x 1 ,x 2 ,... Xn,xn+1)=y. Således er g(x1,x2,…,xn,xn+1)=min(y|f(x1,x2,…,xn,y)=xn+1). Hvis sådan y nej, så mener vi, at f(x 1 ,x 2 ,... ,x n ,x n+1) ikke er defineret. Så tre tilfælde er mulige: 1. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),...,f(x 1 ,x 2 ,… ,xn ,y-1) eksisterer og er ikke lig med xn +1, og f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x 1 ,x 2 ,... ,x n ,0), f(x 1 ,x 2 ,... ,x n ,1),...,f(x 1 ,x 2 ,... ,xn ,y-1) eksistere og er ikke lig med xn +1, men f(x 1 ,x 2 ,...,x n ,y) eksisterer ikke; 3. f(x 1 ,x 2 ,… ,x n ,i) findes for alle iœN og er forskellige fra xn +1. Hvis det 1. tilfælde forekommer, så g(x 1 ,x 2 ,… ,x n ,x n+1)=y, og hvis det 2. eller 3. tilfælde, så g(x 1 ,x 2 ,… ,x n , x n +1) er ikke defineret. En funktion g opnået på denne måde siges at være opnået fra f ved brug af minimeringsoperatoren M. Vi skriver g= Mf. Minimeringsoperatoren er en åbenlys generalisering af den omvendte funktionsoperator. Generaliseringen er ret dyb, da funktionen f ikke skal være en-til-en (i variablen x n+1) Definition. Funktioner, der kan udledes af de enkleste o(x)=0, s(x)=x+1,
I m n (x 1,..., x n)
= x m anvendelse af superpositionsoperatorer, primitiv rekursion og minimeringsoperatorer kaldes et begrænset antal gange rekursive. Klassen af rekursive funktioner er bredere end klassen af primitive rekursive funktioner, om ikke andet fordi den ikke kun indeholder funktioner, der er defineret overalt. Lad os for eksempel bevise, at funktionen = x − y, hvis x ≥ y< y f(x,y) eksisterer ikke, hvis x er rekursiv. Faktisk er f(x,y)=min(z| y+z=x), og det blev tidligere fastslået, at funktionen u(x,y)=x+y er primitivt rekursiv. Rekursive funktioner afspejler vores intuitive forståelse af de funktioner, som nogle mekaniske enheder kan beregne. De kan især beregnes på Turing-maskiner (se forrige afsnit). Tværtimod er enhver funktion, der kan beregnes på en Turing-maskine, rekursiv. Vi vil ikke kontrollere dette faktum, da det ville tage for meget tid og plads. Et komplet bevis kan for eksempel findes i bogen af A.I. Maltsev "Algorithms and recursive functions". Bemærk, at ikke alle funktioner af naturlige argumenter er rekursive, ikke engang hver funktion af et enkelt argument. Eksistensen af ikke-rekursive funktioner er den "matematiske årsag" til tilstedeværelsen af algoritmisk uløselige problemer. I forskellige grene af matematikken er der algoritmisk uløselige problemer, dvs. problemer, som der ikke findes en løsningsalgoritme for, og ikke fordi den endnu ikke er opfundet, men fordi den i princippet er umulig. Algoritmen skal selvfølgelig forstås i betydningen Turing-maskiner og rekursive funktioner. Lad os formulere et af disse problemer Turing maskine stoppe problem. En Turing-maskine er et objekt defineret af et begrænset antal parametre. Alle delvise tilknytninger fra et endeligt sæt til et andet kan effektivt omnummereres. Derfor kan hver Turing-maskine tildeles et nummer (et naturligt tal). Lad T(n) være en Turing-maskine med nummer n. Nogle maskiner, der begynder at køre på et tomt bånd, stopper til sidst, og nogle kører på ubestemt tid. Problemet opstår: givet et naturligt tal n, afgør, om en Turing-maskine T(n) lanceret på et tomt bånd vil stoppe eller ej. Denne opgave algoritmisk uafgørligt. Det vil sige, at der ikke er nogen automatisk procedure ,
for hver n bestemmer om maskinen T(n) stopper eller ej. Dette udelukker ikke, at vi for en bestemt maskine kan bestemme, om den stopper eller ej. Der er ingen metode, der løser dette for alle maskiner på én gang .
Givet et problem, hvordan finder man en effektiv algoritme til at løse det? Og hvis en algoritme findes, hvordan kan den så sammenlignes med andre algoritmer, der løser samme problem? Hvordan vurderer man dens kvalitet? Spørgsmål af denne art er af interesse for både programmører og dem, der er involveret i den teoretiske undersøgelse af computing. Der er mange kriterier for evaluering af algoritmer. Oftest vil vi være interesserede i rækkefølgen af vækst af den tid og hukommelseskapacitet, der kræves for at løse et problem, efterhånden som inputdataene øges. Vi vil gerne knytte et nummer til hver specifik opgave, kaldet dens størrelse ,
som ville udtrykke et mål for mængden af inputdata. For eksempel kan størrelsen af et matrixmultiplikationsproblem være den største størrelse af faktormatricerne. Den tid, en algoritme tager som funktion af problemets størrelse, kaldes tidskompleksitet denne algoritme. Opførselen af denne kompleksitet i grænsen, når problemets størrelse øges, kaldes asymptotisk tidskompleksitet
.
På samme måde kan vi definere kapacitiv kompleksitet og asymptotisk kapacitiv kompleksitet. Det er den asymptotiske kompleksitet af algoritmen, der i sidste ende bestemmer størrelsen af de problemer, der kan løses med denne algoritme. Hvis en algoritme behandler input af størrelse n i tid cÿn 2, hvor c -
en eller anden konstant, så siger de, at tidskompleksiteten af denne algoritme er O(n 2) (læs "af orden en square"). Man skulle tro, at den enorme stigning i computerhastigheden, som den nuværende generation af digitale computermaskiner medfører, ville reducere betydningen af effektive algoritmer. Det modsatte sker dog. Efterhånden som computere bliver hurtigere og hurtigere, og vi kan løse større problemer, er det kompleksiteten af algoritmen, der bestemmer stigningen i problemstørrelsen, der kan opnås, når maskinens hastighed øges. Lad os sige, at vi har fem algoritmer A1,A2,...,A5 med følgende tidskompleksiteter: Her er tidskompleksitet antallet af tidsenheder, der kræves for at behandle et input af størrelse n. Lad tidsenheden være et millisekund (1 sek=1000 millisekunder). Så kan algoritme A1 behandle et input på størrelse 1000 på et sekund, mens A5 kan behandle et input på størrelse højst 9. I tabellen. 6.5.1. Størrelsen af problemer, der kan løses på et sekund, et minut og en time ved hver af disse fem algoritmer, er angivet. Tabel 6.5.3. Lad os antage, at den næste generation af computere vil være 10 gange hurtigere end den nuværende. I tabel 6.5.2. viser, hvordan størrelsen af de problemer, vi kan løse på grund af denne stigning i hastigheden, vil stige. Bemærk, at for algoritme A5 øger en tidobling af hastigheden størrelsen af problemet, der kun kan løses med tre enheder (se sidste linje i tabel 6.5.2.), mens for algoritme A3 er problemets størrelse mere end tredoblet . Tabel 6.5.4. I stedet for effekten af at øge hastigheden, lad os nu overveje effekten af at bruge en mere effektiv algoritme. Lad os vende tilbage til tabel 6.5.1. Hvis vi tager 1 minut som sammenligningsgrundlag, så kan vi ved at erstatte algoritme A4 med algoritme A3 løse et 6 gange større problem og ved at erstatte A4 med A2 ,
du kan løse et problem 125 gange større. Disse resultater er langt mere imponerende end 2x forbedringen opnået med 10x hastigheden. Hvis vi tager 1 time som sammenligningsgrundlag, viser forskellen sig at være endnu større. Ud fra dette konkluderer vi, at den asymptotiske kompleksitet af en algoritme tjener som et vigtigt mål for algoritmens kvalitet, og et mål, der lover at blive endnu vigtigere med efterfølgende stigninger i beregningshastigheden. På trods af at hovedopmærksomheden her er rettet mod rækkefølgen af vækst af mængder, må man forstå, at en stor rækkefølge af vækst i kompleksiteten af algoritmen kan have en mindre multiplikativ konstant (konstant c i definitionen af O(f(x))), end en lille rækkefølge af stigning i kompleksiteten af en anden algoritme. I dette tilfælde kan en algoritme med hurtigt stigende kompleksitet være at foretrække til små problemer – måske endda til alle de problemer, vi er interesserede i. Antag for eksempel, at tidskompleksiteten af algoritmerne A1, A2, A3, A4, A5 faktisk er henholdsvis 1000n, 100nÿlog(n), 10n2, n3 og 2. n Så vil A5 være bedst til problemer af størrelse 2§n§9, A2 - til problemer med størrelse 10§n§58, A1 - ved 59§n§1024, og A1- med n>1024.- 1. F.A. Novikov. Diskret matematik for programmører./ St. Petersborg: Peter, 2001, 304С. 2. S.V. Sudoplatov, E.V. Ovchinnikova. Elements of Discrete Mathematics./ M., INFRA-M, Novosibirsk, NSTU Publishing House, 3. Y.M.Erusalimsky. Diskret matematik / M., "Universitetsbog", 2001, 279 s. 4. A. Aho, J. Hopcroft, J. Ullman. Konstruktion og analyse af beregningsalgoritmer. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Kursus i diskret matematik./ M., MAI Publishing House, 1992, 264P.§4.3. Kvantifikatorer og deres egenskaber.
Kapitel V. Formelle teorier.
§5.1. Definition af formel teori.
§5.2. Propositionsregning.
§5.3. Deduktionssætning. Fuldstændighed af IV.
§5.4. Automatisk bevis for teoremer.
§5.5. Opløsningsmetode i IW.
Kapitel VI. Elementer i teorien om algoritmer.
§6.1. Algoritme definition.
§6.2. Turing maskine.
q 0
…
qi
…
q m
…
et u
q
s
-en
rS
…
§6.3. Rekursive funktioner
§6.4. Algoritmisk uløselige problemer.
§6.5. Algoritmer og deres kompleksitet.
LITTERATUR.