Zusammenfassung: Vorlesungen zur mathematischen Logik und Theorie der Algorithmen. Fragen zum Selbsttest. §2.1. Normale Formen
Mathematische Logik und Theorie der Algorithmen – VorlesungsverlaufEinführung.
Zweck.
Neue Abschnitte des diskreten Mathematikkurses werden zwar in Form von Bildungsprogrammen und Vorlesungsreihen umgesetzt, existieren jedoch zumindest in russischer Sprache noch nicht in Form von Monographien, da sich der diskrete Mathematikkurs für technische Universitäten auf alte angewandte Probleme konzentriert Ingenieure mussten lösen. Insbesondere in der mathematischen Logik war es die Minimierung logischer Schaltkreise, die heute an Relevanz verloren hat.
Es ist interessant festzustellen, dass die Theorie der Synthese logischer Schaltkreise, die vor den Augen einer Generation von Forschern einen fast vollständigen „biologischen Zyklus“ durchlaufen hat, ein sehr lehrreiches Beispiel dafür ist, wie Zweige der technischen Wissenschaften schlecht mit den Grundlagenwissenschaften verbunden sind Wissenschaft ist sehr anfällig für Veralterung. Noch vor 10 Jahren waren alle Fachzeitschriften voll mit Artikeln über die Minimierung und Synthese logischer Schaltkreise. Die meisten von Wissenschaftlern entwickelten Minimierungsmethoden sind heute vergessen und in der Praxis nicht gefragt. Und jene Ideen, die damals als rein theoretisch galten, haben in der modernen Technik praktische Anwendung gefunden. Beispielsweise haben sich Fuzzy-Logik, Petri-Netze und Algorithmentheorie bewährt und werden in verschiedenen Bereichen der Kybernetik und Programmierung wie Systemprogrammierung, rechnerische Komplexität und künstliche Intelligenz häufig eingesetzt.
Und die Theorie der Algorithmen wurde zum zentralen Teil der diskreten Mathematik. Im Gegensatz zu den meisten Monographien in russischer Sprache werden diese Themen jedoch im Laufe der Vorlesungen als Mittel zur Lösung praktischer, technischer Probleme dargestellt.
Wie Sie wissen, verändern sich nach jedem Jahrzehnt die Hardwarekomponenten von Computern, Betriebssystemen, Zugriffstools und die Programme selbst radikal. Die ihnen zugrunde liegenden Strukturen und Algorithmen bleiben jedoch noch viel länger unverändert. Diese Grundlagen wurden vor Tausenden von Jahren gelegt, als die formale Logik entwickelt und die ersten Algorithmen entwickelt wurden.
Mathematische Logik und Algorithmentheorie gehören traditionell zur Grundlagenwissenschaft und gelten als wenig praxisbezogen und schwer verständlich. Als J. Boole den mathematischen Apparat der Booleschen Algebra entwickelte, fand dieser zwar lange Zeit keine praktische Anwendung, aber im 20. Jahrhundert war es dieser mathematische Apparat, der es ermöglichte, alle Computerkomponenten zu entwerfen. Folglich wird das erste dieser Vorurteile durch die Entwicklung der Computertechnologie erfolgreich widerlegt.
Das Vorurteil über die Schwierigkeit, diese Disziplin zu verstehen, beruht größtenteils auf der Tatsache, dass Bücher über mathematische Logik und Algorithmentheorie von Mathematikern für Mathematiker geschrieben wurden.
Jetzt, da die Fähigkeiten der Computertechnologie um ein Vielfaches gestiegen sind und es viel mehr Personalcomputer selbst gibt als Menschen, die wissen, wie man sie effektiv nutzt, ist es wichtig zu verstehen, was mit Hilfe moderner Computertechnologie möglich ist und was nicht außerordentliche Bedeutung.
Es war die allgemeine Theorie der Algorithmen, die zeigte, dass es Probleme gibt, die unlösbar sind, egal wie leistungsfähig die Rechenleistung ist, und ihr sich schnell entwickelnder Zweig – die Theorie der rechnerischen Komplexität – führt allmählich zu dem Verständnis, dass es Probleme gibt, die lösbar sind. aber objektiv komplex, und ihre Komplexität kann sich im absoluten Sinne als einigermaßen herausstellen, d.h. für moderne Computer praktisch unzugänglich.
In diesem Kurs wurden folgende Ziele festgelegt:
1. Stellen Sie alle betrachteten Fragestellungen so einfach wie möglich dar, jedoch nicht einfacher, als es für einen hochqualifizierten Spezialisten erforderlich ist.
2. Praktische Probleme des Entwurfs und der Analyse von Informationssystemen sind der Ausgangspunkt, und der formale Apparat ist ein Mittel zur systematischen Lösung dieser Probleme. Wir sind zutiefst davon überzeugt, dass ein Schüler kein Gefäß ist, das gefüllt werden muss, sondern eine Fackel, die angezündet werden muss.
3. Jeder Abschnitt des Kurses enthält Selbsttestfragen. Um diesen Kurs abzuschließen, muss der Student alle diese Fragen beantworten.
Als Ergebnis der Beherrschung dieses Kurses sollte der Student, basierend auf einem klaren Verständnis der relevanten theoretischen Abschnitte, in der Lage sein:
Implementieren Sie die einfachste Art der logischen Transformation von Informationen in eine beliebige Basis logischer Funktionen;
Identifizieren Sie die logische Struktur des beweiskräftigen Denkens in natürlicher Sprache, erstellen Sie formale Beweisschemata und überprüfen Sie deren Richtigkeit.
1.2 Logische Darstellungen
Logische Darstellungen - Beschreibung des untersuchten Systems, Prozesses oder Phänomens in Form einer Menge komplexe Aussagen besteht aus einfache (elementare) Aussagen Und logische Verknüpfungen zwischen ihnen. Logische Darstellungen und ihre Komponenten zeichnen sich durch bestimmte Eigenschaften und eine Reihe zulässiger Transformationen (Operationen, Inferenzregeln usw.) aus, die in formalen (mathematischen) Methoden entwickelt wurden. In der Logik sind die richtigen Argumentationsmethoden die Gesetze der Logik.
Methoden (Regeln) der formalen Darstellung von Aussagen, die Konstruktion neuer Aussagen aus bestehenden unter Verwendung logisch korrekter Transformationen sowie Methoden (Methoden) zur Feststellung der Wahrheit oder Falschheit von Aussagen werden untersucht mathematische Logik. Die moderne mathematische Logik umfasst zwei Hauptabschnitte: Logik von Aussagen und es abdecken Prädikatenlogik(Abb. 1.1), für deren Konstruktion es zwei Ansätze (Sprachen) gibt, die zwei Varianten der formalen Logik bilden: Algebra der Logik Und logisches Kalkül. Zwischen den Grundkonzepten dieser Sprachen der formalen Logik besteht eine Eins-zu-eins-Entsprechung. Ihre Isomorphie wird letztlich durch die Einheit der zugrunde liegenden zulässigen Transformationen gewährleistet.
Reis. 1.1
Die Hauptobjekte traditioneller Zweige der Logik sind Aussagen.
Stellungnahme - Aussagesatz (Aussage, Urteil), o was es Sinn macht, das zu sagen WAHR oder FALSCH. Alle wissenschaftlichen Erkenntnisse (Gesetze und Phänomene der Physik, Chemie, Biologie etc., mathematische Theoreme etc.), Ereignisse des Alltags, Situationen in der Wirtschaft und Managementprozesse werden in Form von Aussagen formuliert. Imperativ- und Fragesätze sind keine Aussagen.
Beispiele für Aussagen: „Zweimal zwei ist vier“, „Wir leben im 21. Jahrhundert“, „Der Rubel ist die russische Währung“, „Aljoscha ist Olegs Bruder“, „Die Operationen Vereinigung, Schnittpunkt und Addition sind boolesche Operationen auf Mengen.“ “, „Der Mensch ist sterblich“, „Eine Neuordnung der Begriffe ändert nichts an der Summe“, „Heute ist Montag“, „Wenn es regnet, sollte man einen Regenschirm mitnehmen.“
Um mit diesen Sätzen als Aussagen weiter operieren zu können, müssen wir für jeden von ihnen wissen, ob er wahr oder falsch ist, d. h. kenne sie Wahrheitswert (Wahrheit). Beachten Sie, dass die Wahrheit oder Falschheit einer Aussage in manchen Fällen davon abhängt, welche konkrete Realität (System, Prozess, Phänomen) wir mit ihrer Hilfe zu beschreiben versuchen. In diesem Fall wird gesagt, dass die gegebene Aussage in einer bestimmten Interpretation (Kontext) wahr (oder falsch) ist. Wir gehen weiterhin davon aus, dass der Kontext gegeben ist und die Aussage einen gewissen Wahrheitswert hat.
1.3 Geschichte der entwickelten mathematischen Logik
Die Logik als Wissenschaft entstand im 4. Jahrhundert. Chr. Es wurde vom griechischen Wissenschaftler Aristoteles geschaffen.Das Wort „Logik“ kommt vom griechischen „logos“, was einerseits „Wort“ oder „Darstellung“ und andererseits „Denken“ bedeutet. Im erklärenden Wörterbuch von Ozhegov S.I. Es heißt: „Logik ist die Wissenschaft von den Gesetzen des Denkens und seinen Formen.“ Im 17. Jahrhundert Der deutsche Wissenschaftler Leibniz plante die Schaffung einer neuen Wissenschaft, nämlich „der Kunst, die Wahrheit zu berechnen“. . In dieser Logik hätte laut Leibniz jede Aussage ein entsprechendes Symbol und die Argumentation hätte die Form von Berechnungen. Da diese Idee von Leibniz nicht auf das Verständnis seiner Zeitgenossen stieß, wurde sie weder verbreitet noch weiterentwickelt und blieb eine brillante Vermutung.
Erst Mitte des 19. Jahrhunderts. Der irische Mathematiker George Boole verkörperte die Idee von Leibniz. 1854 schrieb er das Werk „Untersuchung der Gesetze des Denkens“, das den Grundstein für die Algebra der Logik legte, in der Gesetze gelten, die den Gesetzen der gewöhnlichen Algebra ähneln, die Buchstaben jedoch bezeichnen keine Zahlen, sondern Aussagen. In der Sprache der Booleschen Algebra kann man das Denken beschreiben und seine Ergebnisse „berechnen“. Es deckt jedoch nicht alle Überlegungen ab, sondern nur eine bestimmte Art davon. , Daher wird die Boole-Algebra als Aussagenkalkül betrachtet.
Booles Algebra der Logik war der Embryo einer neuen Wissenschaft – der mathematischen Logik. Im Gegensatz dazu wird die Logik des Aristoteles als traditionelle formale Logik bezeichnet. Der Name „mathematische Logik“ spiegelt zwei Merkmale dieser Wissenschaft wider: Erstens ist mathematische Logik eine Logik, die die Sprache und Methoden der Mathematik verwendet; zweitens wird die mathematische Logik durch die Bedürfnisse der Mathematik zum Leben erweckt.
Ende des 19. Jahrhunderts. Die von Georg Cantor geschaffene Mengenlehre schien eine verlässliche Grundlage für die gesamte Mathematik, einschließlich der mathematischen Logik, zumindest für die Aussagenrechnung (Boolesche Algebra), zu sein, denn Es stellte sich heraus, dass die Cantor-Algebra (Mengenlehre) isomorph zur Boole-Algebra ist.
Die mathematische Logik selbst wurde zu einem Zweig der Mathematik, der zunächst höchst abstrakt und unendlich weit von praktischen Anwendungen entfernt schien. Allerdings blieb dieses Gebiet nicht lange die Domäne „reiner“ Mathematiker. Zu Beginn des 20. Jahrhunderts. (1910) Russischer Wissenschaftler Ehrenfest P.S. wies auf die Möglichkeit hin, den Apparat der Booleschen Algebra in der Telefonkommunikation zur Beschreibung von Schaltkreisen zu verwenden. In den Jahren 1938-1940 erschienen fast gleichzeitig die Arbeiten des sowjetischen Wissenschaftlers V.I. Shestakov, des amerikanischen Wissenschaftlers Shannon und der japanischen Wissenschaftler Nakashima und Hakazawa über die Anwendung der mathematischen Logik in der digitalen Technologie. Die erste Monographie über den Einsatz mathematischer Logik beim Entwurf digitaler Geräte wurde in der UdSSR vom sowjetischen Wissenschaftler M.A. Gavrilov veröffentlicht. im Jahr 1950. Die Rolle der mathematischen Logik bei der Entwicklung moderner Mikroprozessortechnologie ist äußerst wichtig: Sie wird beim Entwurf von Computerhardware, bei der Entwicklung aller Programmiersprachen und beim Entwurf diskreter Automatisierungsgeräte verwendet.
Wissenschaftler aus verschiedenen Ländern haben einen großen Beitrag zur Entwicklung der mathematischen Logik geleistet: Professor der Kasaner Universität Poretsky P.S., de-Morgan, Peirce, Turing, Kolmogorov A.N., Heidel K. und andere.
1.4 Fragen zum Selbsttest.
1. Formulieren Sie die Ziele des Kurses
Wolga-Universität benannt nach. Tatischtschewa.
Vorlesungen zur mathematischen Logik und Theorie der Algorithmen.
Zusammengestellt von: außerordentlicher Professor S.V. Kaverin.
Kapitel I. Algebra der Logik.
§1.1. Definition einer booleschen Funktion.
Boolesche Funktion y=f(x 1 ,x 2 ,…,x n)von P Variablen x 1 , x 2 ,...,x n ist jede Funktion, in der die Argumente und die Funktion den Wert entweder 0 oder 1 annehmen können, d. h. Eine boolesche Funktion ist eine Regel, nach der eine beliebige Menge von Nullen und Einsen berechnet wird
(x 1 ,x 2 ,...,x n) wird der Wert 0 oder 1 zugewiesen.
Boolesche Funktionen auch genannt logische Algebrafunktionen, Binärfunktionen und Schaltfunktionen.
Boolesche Funktion von N Variablen können durch eine Wahrheitstabelle spezifiziert werden, in der Sätze von Argumentwerten in aufsteigender Reihenfolge ihrer Zahlen angeordnet sind : Zuerst kommt die Menge, die die binäre Zerlegung von 0 darstellt (diese Menge hat die Nummer 0); dann kommt die Menge, die die binäre Entwicklung von 1, dann 2, 3 usw. ist. Der letzte Satz besteht aus N Einheiten und ist die binäre Entwicklung der Zahl 2 N-1 (diese Anordnungsreihenfolge der Mengen wird aufgerufen lexikographische Ordnung). Bedenken Sie, dass die Zählung bei 0 beginnt und der Wert einer booleschen Funktion entweder 0 oder sein kann N
1 kommen wir zu dem Schluss, dass es nur 22 verschiedene boolesche Funktionen gibt N Variablen. So gibt es beispielsweise 16 boolesche Funktionen von zwei Variablen, 256 von drei usw.
Beispiel 1.1.1.(Abstimmung) . Betrachten wir ein Gerät, das die Annahme eines bestimmten Beschlusses durch das „Dreierkomitee“ aufzeichnet. Jedes Ausschussmitglied drückt bei der Genehmigung eines Beschlusses seinen eigenen Knopf. Stimmt die Mehrheit der Mitglieder dafür, ist der Beschluss gefasst. Dies wird von einem Aufnahmegerät aufgezeichnet. Somit implementiert das Gerät die Funktion f(x,y,z ) , dessen Wahrheitstabelle die Form hat
| X | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| j | 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 |
Eine boolesche Funktion wird auch eindeutig spezifiziert, indem alle Tupel aufgezählt werden, bei denen sie den Wert 0 annimmt, oder indem alle Tupel aufgezählt werden, bei denen sie den Wert 1 annimmt. Die im Beispiel erhaltene Funktion F kann auch durch das folgende Gleichungssystem angegeben werden: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Ein Vektor boolescher Funktionswerte y=f(x 1 ,x 2 ,…,x n) ist eine geordnete Menge aller Werte der Funktion f, in der die Werte in lexikographischer Reihenfolge geordnet sind. Angenommen, eine Funktion aus drei Variablen f sei durch einen Wertevektor (0000 0010) spezifiziert, und Sie müssen eine Menge finden, auf der f den Wert 1 annimmt. Denn 1 steht an 7. Stelle und die Nummerierung in lexikographischer Reihenfolge beginnt bei 0, dann ist es notwendig, die binäre Entwicklung von 6 zu finden. Somit nimmt die Funktion f den Wert 1 auf der Menge (110) an.
§1.2. Elementare boolesche Funktionen.
Unter den Booleschen Funktionen stechen die sogenannten elementaren Booleschen Funktionen hervor, mit denen sich jede beliebige Boolesche Funktion beliebig vieler Variablen beschreiben lässt.
1. Es wird eine boolesche Funktion f(x 1 ,x 2 ,…,x n) aufgerufen, die auf allen Mengen von Nullen und Einsen den Wert 1 annimmt Konstante 1 oder identische Einheit. Bezeichnung : 1 .
2. Es wird eine boolesche Funktion f(x 1 ,x 2 ,…,x n) aufgerufen, die auf allen Mengen von Nullen und Einsen den Wert 0 annimmt konstant 0 oder identische Null. Bezeichnung : 0 .
3. Verweigerung ist eine boolesche Funktion einer Variablen, die durch die folgende Wahrheitstabelle definiert ist
Andere Namen : logische Multiplikation (Produkt); logisches „und“.
Bezeichnungen : x&y, xÿy, x⁄y, min(x,y).
5. Disjunktion
Anderer Name : logische Konsequenz. Bezeichnungen : xØy, xfly, xy.
7. Gleichwertigkeit ist eine boolesche Funktion zweier Variablen, die durch die folgende Wahrheitstabelle definiert ist
Anderer Name : Anti-Äquivalenz. Bezeichnungen : x∆y, x+y.
9. Schaeffers Schlaganfall ist eine boolesche Funktion zweier Variablen, die durch die folgende Wahrheitstabelle definiert ist
Anderer Name : Negation der Disjunktion, logisches „Nicht-Oder“, Webb-Funktion.
Bezeichnung : x∞y ; für die Webb-Funktion - x±y.
Kommentar. Die in der Notation elementarer Funktionen verwendeten Symbole Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ werden Konnektive oder Operationen genannt.
§1.3. Boolesche Funktionen mithilfe elementarer Funktionen angeben.
Wenn Sie einige boolesche Funktionen anstelle von Variablen in eine logische Funktion ersetzen, ist das Ergebnis eine neue aufgerufene boolesche Funktion Überlagerung substituierte Funktionen (komplexe Funktion). Mithilfe der Superposition können Sie komplexere Funktionen erhalten, die von einer beliebigen Anzahl von Variablen abhängen können. Wir werden das Schreiben boolescher Funktionen als elementare boolesche Funktionen bezeichnen Formel Implementierung dieser Funktion.
Beispiel 1.3.1. Gegeben sei eine elementare boolesche Funktion x¤y. Ersetzen wir statt x die Funktion x 1 ∞x 2. Wir erhalten eine Funktion von drei Variablen (x 1 ∞x 2)¤y. Wenn wir anstelle der Variablen y beispielsweise x 3 ∆x 4 ersetzen, erhalten wir eine neue Funktion aus vier Variablen: (x 1 ∞x 2)¤(x 3 ∆x 4). Offensichtlich erhalten wir auf diese Weise boolesche Funktionen, die durch elementare boolesche Funktionen ausgedrückt werden.
Mit Blick auf die Zukunft stellen wir das fest beliebig Eine boolesche Funktion kann als Überlagerung elementarer Funktionen dargestellt werden.
Um komplexe Funktionen kompakter zu schreiben, führen wir die folgenden Konventionen ein: : 1) äußere Klammern entfallen; 2) Operationen in Klammern werden zuerst ausgeführt; 3) Es wird davon ausgegangen, dass die Priorität der Konnektive in der folgenden Reihenfolge abnimmt : Ÿ, ⁄, ¤, Ø, ~. Für äquivalente Konnektive und die übrigen Konnektive (∆,|,∞) sollten Sie vorerst Klammern setzen.
Beispiele 1.3.2. In der Formel x⁄y¤z werden die Klammern wie folgt gesetzt: ((x⁄y)¤z), weil Betrieb ⁄ ist stärker als Betrieb ¤ gemäß unserer Vereinbarung.
1. In der Formel x¤y~zØx werden die Klammern wie folgt gesetzt: ((x¤y)~(zØx))
2. In der Formel (x∆y)~zØxy¤Ÿz werden die Klammern wie folgt gesetzt: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Die Formel xØyØz ist nach unserer Vereinbarung nicht korrekt geschrieben, weil Durch die Platzierung von Klammern ergeben sich zwei unterschiedliche Funktionen: ((xØy)Øz) und (xØ(yØz)).
§1.4. Signifikante und nicht signifikante Variablen.
Boolesche Funktion y=f(x 1 ,x 2 ,…,x n) hängt maßgeblich davon ab aus Variable X k, wenn eine solche Menge von Werten existiert A 1 ,A 2 ,…,A k - 1, A k+1, A k + 2 ,…, A N dass f (A 1,a 2,…,a k-1 , 0 ,A k+1,a k+2,…,a N) π F (A 1,a 2,…,a k-1 , 1 ,A k+1,a k+2,…,a N).
In diesem Fall X k wird als essentielle Variable bezeichnet , sonst X k wird als unbedeutende (Dummy-)Variable bezeichnet . Mit anderen Worten: Eine Variable ist irrelevant, wenn ihre Änderung den Wert der Funktion nicht ändert.
Beispiel 1.4.1. Die booleschen Funktionen f 1 (x 1 ,x 2) und f 2 (x 1 ,x 2) seien durch die folgende Wahrheitstabelle definiert:
| 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 |
Für diese Funktionen ist die Variable x 1 - ist signifikant und die Variable x 2 ist nicht signifikant.
Offensichtlich ändern boolesche Funktionen ihre Werte nicht durch die Einführung (oder Entfernung) irrelevanter Variablen. Daher werden im Folgenden boolesche Funktionen bis auf unwichtige Variablen betrachtet (im Beispiel können wir schreiben: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Wahrheitstabellen. Äquivalente Funktionen.
Wenn Sie die Wahrheitstabellen für Elementarfunktionen kennen, können Sie die Wahrheitstabelle der Funktion berechnen, die diese Formel implementiert.
Beispiel 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Somit implementiert die Formel F1 die Disjunktion. Beispiel 1.5.2. F2=x 1 ⁄x 2 Øx 1
Somit implementiert die Formel F3 die Disjunktion.
Die booleschen Funktionen f1 und f2 werden aufgerufen Äquivalent, wenn auf jedem Satz ( A 1 ,A 2 ,…, ein) Nullen und Einsen, die Werte der Funktionen fallen zusammen. Die Notation für äquivalente Funktionen lautet wie folgt : f1=f2.
Gemäß den angegebenen Beispielen 1-3 können wir schreiben
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. Grundlegende Äquivalenzen.
Die angegebenen Äquivalenzen sind oft nützlich, wenn mit booleschen Funktionen gearbeitet wird.
Unten stehen H, H1, H2,... für einige boolesche Funktionen.
1. Gesetz der doppelten Negation: H = H.
2. Idempotenz
3. Kommutativität:
H1*H2=H2*H1, wobei das Symbol * einen der Konnektoren &, ¤, ∆ bedeutet,
4. Assoziativität:
H1*(H2*H3)=(H1*H2)*H3, wobei das Symbol * eine der Verknüpfungen &, ¤, ∆, ~ bedeutet.
5. Distributivität:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. De Morgans Gesetze:
H1& H2 = H1 ∨ H2 , H1∨ H2 = H1 & H2 .
7. Übernahmeregeln:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Klebegesetze:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Inversionsgesetze: H ∨ H = 1, H & H = 0.
10. Regeln für Operationen mit Konstanten:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Um die Wahrheit der oben genannten Äquivalenzen zu überprüfen, genügt es, die entsprechenden Wahrheitstabellen zu erstellen.
Beachten Sie, dass die Assoziativitätseigenschaft einer Operation die Erweiterung dieser Operation auf eine beliebige Anzahl von Variablen ermöglicht. So ist zum Beispiel die Schreibweise x¤у¤z¤w richtig, weil Jede Anordnung von Klammern führt zur gleichen Funktion. Die kommutative Natur einer Operation ermöglicht es Ihnen, Variablen in einer Formel auszutauschen. Zum Beispiel: x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Funktionale Vollständigkeit.
In einem typischen modernen Digitalcomputer sind die Zahlen 0 und 1. Daher sind die vom Prozessor ausgeführten Anweisungen boolesche Funktionen. Im Folgenden zeigen wir, dass jede boolesche Funktion durch Konjunktion, Disjunktion und Negation implementiert wird. Folglich ist es möglich, den erforderlichen Prozessor zu bauen, der über Elemente verfügt, die Konjunktion, Disjunktion und Negation implementieren. Dieser Abschnitt ist der Beantwortung der Frage gewidmet: Gibt es (und wenn ja, welche) andere Systeme boolescher Funktionen, die die Eigenschaft haben, dass sie zum Ausdruck aller anderen Funktionen verwendet werden können?
Lassen Sie uns eine Reihe von Funktionsklassen vorstellen.
1. Die Klasse von Funktionen, die die Konstante 0 bewahren, d. h. solche Funktionen
2. Die Klasse von Funktionen, die die Konstante 1 bewahren, d. h. solche Funktionen
3. Die Klasse der selbstdualen Funktionen, d.h. solche Funktionen y=f(x 1 ,x 2 ,…,x n) mit f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4. Klasse linearer Funktionen, d.h. solche Funktionen y=f(x 1 ,x 2 ,…,x n), die dargestellt werden können als f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, wobei c 0, c 1, c 2 ...Koeffizienten, die den Wert 0 oder 1 annehmen können.
5. Klasse monotoner Funktionen. Auf der Menge der Mengen von Nullen und Einsen Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) führen wir eine Teilordnung wie folgt ein:
(A 1 ,a 2 ,...,a n)§( B 1 ,b 2 ,...,b n) dann und nur dann, wenn A 1 § B 1 , eine 2 § b 2 ,…,a N § B N. Eine Funktion f(x 1, x 2,..., x n) heißt monoton, wenn für zwei beliebige Elemente aus B n gilt, dass
(A 1 ,a 2 ,...,a n)§( B 1 ,b 2 ,...,b n) Daraus folgt, dass f( A 1 ,a 2 ,...,a n)§F( B 1 ,b 2 ,...,b n).
Man nennt ein System S von booleschen Funktionen, deren Überlagerung jede beliebige boolesche Funktion darstellen kann funktionell vollständig . Man sagt, dass sich ein funktional vollständiges System S boolescher Funktionen bildet Basis im logischen Raum. Die Basis S heißt minimal , wenn das Entfernen einer Funktion dieses System unvollständig macht.
Vollständigkeitskriterium (Satz von Post) . Ein System S boolescher Funktionen ist genau dann vollständig, wenn es mindestens eine Funktion enthält: nichterhaltende Konstante 0, nichterhaltende Konstante 1, nichtselbstdual, nichtlinear und nichtmonoton.
Tabelle 1.7 zeigt die Eigenschaften, die elementare boolesche Funktionen haben (das Symbol * gibt eine Eigenschaft an, die eine bestimmte Funktion hat).
Unter Verwendung des Satzes von Post und Tabelle 1.7 können Sie Basen aus Elementarfunktionen gemäß der folgenden Regel bilden. Indem man eine beliebige elementare boolesche Funktion wählt und sie bei Bedarf durch andere Funktionen ergänzt, sodass sie alle zusammen den Satz der funktionalen Vollständigkeit erfüllen. Durch die Funktionen dieser Basis können wir uns ausdrücken Alle andere boolesche Funktionen.
Lassen Sie uns einige häufig verwendete Basen in Anwendungen erstellen.
Tabelle 1.7
| Name | Bezeichnung | Nicht lagerfähig Konstanten |
Nicht lagerfähig Konstanten |
Samodvoys Gültigkeit |
||
| Konst.0 | 0 | * | * | |||
| Konst.1 | 1 | * | * | |||
| Negativ | Ÿ | * | * | * | ||
| Kongyun. | & | * | * | |||
| Disjunktion. | ¤ | * | * | |||
| Implizit. | Ø | * | * | * | * | |
| Äquivalent. | ~ | * | * | * | ||
| Summe durch mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Pierces Pfeil | ∞ | * | * | * | * | * |
1. Als Grundlage dient das Funktionensystem S1=(Ÿ,⁄,¤). Um eine boolesche Funktion auf eine Form zu reduzieren, die nur Konnektiven aus der Basis S1 enthält, können die folgenden Äquivalenzen nützlich sein: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x & y .
2. Das System S2=(Ÿ,&) bildet eine Basis. Eine beliebige Funktion kann zunächst auf eine Form reduziert werden, die Konnektive aus S1 und dann enthält
Verwenden Sie die Beziehung x ∨ y = x ⋅ y.
3. Als Basis dient das System S3=(Ÿ,¤). Eine beliebige Funktion kann zunächst auf eine Form reduziert werden, die Konnektive aus S1 und dann enthält
Verwenden Sie die Beziehung x ⋅ y = x ∨ y.
4. Eine Basis bildet das System S4=(1,&,∆). Eine beliebige Funktion kann zunächst auf eine Form reduziert werden, die Konnektive aus S1 enthält, und dann die Beziehungen x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y verwenden.
5. Als Basis dient das System S5=(|). Eine beliebige Funktion kann zunächst auf eine Form reduziert werden, die Konnektive aus S2 enthält, und dann die Beziehungen x ⋅ y = x y, x = xx verwenden.
6. Das System S6=(∞) bildet eine Basis. Eine beliebige Funktion kann zunächst auf eine Form reduziert werden, die Konnektive aus S3 enthält, und dann
Verwenden Sie die Beziehungen x ∨ y = x ↓ y, x = x ↓ x.
7. Als Basis dient das System S7=(Ø,0).
Beispiel 1.7.1. Schreiben Sie die Funktion x¨(y∆z) in der Basis S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)
Kapitel II. Boolsche Algebra.
Die Menge aller booleschen Werte in der Basis S1=( ÿ, &, ⁄} bilden boolsche Algebra. Daher werden in der Booleschen Algebra alle Formeln mit drei Konnektoren geschrieben: Ÿ, &, ¤. Wir haben die Eigenschaften dieser Algebra teilweise in Kapitel I untersucht (siehe zum Beispiel grundlegende Äquivalenzen). Dieses Kapitel befasst sich mit Eigenschaften, die für die Boolesche Algebra spezifisch sind. Daher werden wir uns in diesem Kapitel nur mit drei Funktionen befassen: ÿ, &, ⁄.
§2.1. Normale Formen.
Normalformen sind eine syntaktisch eindeutige Art, eine Formel zu schreiben, die eine bestimmte Funktion implementiert.
Wenn x eine logische Variable ist und σœ(0,1), dann wird der Ausdruck x σ = x, wenn σσ == 10 oder x σ = 10, wenn x x =≠σσ , x ein Buchstabe genannt . Die Buchstaben x und Ÿx heißen Gegensätze. Konjunkt disjunkt sogenannte Buchstabendisjunktion. Beispielsweise sind die Formeln x ⋅ y ⋅ z und x ⋅ y ⋅ x ⋅ x Konjunktionen, die Formeln x ∨ y ∨ z und x ∨ y ∨ x sind Disjunkten und die Formel z ist sowohl eine Konjunktion als auch eine Disjunktion.
Disjunktive Normalform (DNF) heißt eine Disjunktion einer endlichen Anzahl von Konjunktionen .
Konjunktive Normalform (CNF) heißt Konjunktion endlich vieler Klauseln .
Einfacher ausgedrückt: DNF ist die Summe von Produkten und CNF ist das Produkt logischer Summen.
1. xÿy¤yÿz¤x ist DNF (Summe der Produkte).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z ist CNF (Produkt von Summen).
3. x ∨ y ∨ z ∨ w ist DNF und CNF (gleichzeitig).
4. x ⋅ y ⋅ z ⋅ w ist DNF und CNF (gleichzeitig).
5. (x¤x¤y)·(y¤z¤x)·z ist CNF.
6. x⋅y⋅z und x⋅y⋅x⋅x sind DNFs.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z ist keine Normalform (nicht DNF oder CNF).
Die Funktion f sei in der Basis S1 geschrieben. Diese Funktion wird wie folgt auf Normalform reduziert:
1) Wir verwenden die Gesetze von De Morgan, um die Formel in eine Form umzuwandeln, in der sich die negativen Vorzeichen nur auf einzelne Variablen beziehen;
2) Wir wenden die Regel zum Entfernen doppelter Negationen an: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) und das zweite Verteilungsgesetz für die Reduktion auf CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Jede boolesche Funktion kann unendlich viele DNF- und CNF-Darstellungen haben. Wenn man beispielsweise zusätzlich die Gesetze der Inversionen und die Regeln für Operationen mit Konstanten anwendet, kann man sicherstellen, dass in jeder einzelnen Konjunktion oder Disjunktion jede Variable nicht mehr als einmal vorkommt (entweder sie selbst oder ihre Negation).
Beispiel 2.1.1. Zur Reduktion auf DNF verwenden wir das 1. Gesetz der Distributivität.
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)= ist CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = – das ist ein weiterer CNF
X · y · ∨ x ≤ y · Zechen y ∨ x ≤y · Z ∨ x ≤ y · ZëZ = 0∨ x ≤y · Z ∨ x · y · Z =
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ist ein DNF
Beispiel 2.1.2. Um auf CNF zu reduzieren, ist es notwendig, das zweite Gesetz der Distributivität zu verwenden.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y · Zechen (x∨y) = (x∨y · Z) ≤ (x∨x∨y) = (x∨y) · (x∨z) ≤ (1∨y) =
= (x ∨ y) ⋅ (x ∨ z) ist CNF
§2.2. Perfekte Normalformen.
Wenn in jedem Term einer Normalform alle Variablen vertreten sind (entweder sie selbst oder ihre Negationen) und in jeder einzelnen Konjunktion oder Disjunktion eine Variable genau einmal vorkommt (entweder sie selbst oder ihre Negation), dann heißt diese Form perfekte Normalform (SDNF oder SCNF). Beispiele: Gegeben sei eine Funktion von drei Variablen f(x,y,z).
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ist eine perfekte DNF.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) ist eine perfekte CNF.
3. (x ∨ y) ⋅ (x ∨ z) ist keine perfekte CNF, weil Beispielsweise enthält die erste Summe nicht die Variable z.
4. xÿyÿz ist ein perfekter DNF. Satz 2.2.1.
1. Jede boolesche Funktion, die nicht identisch Null ist, hat bis zur Position der Terme nur eine SDNF.
2. Jede boolesche Funktion, die nicht mit 1 identisch ist, hat bis zur Position der Terme nur eine SCNF.
Wir werden den Satz konstruktiv beweisen, als Lösung für das folgende Problem: Erstellen Sie mithilfe dieser Wahrheitstabelle eine SDNF.
Betrachten wir die Lösung am Beispiel der in einer Tabelle (Tabelle 2.2) angegebenen Funktion f(x,y,z) für n=3.
Beispiel 2.2.1. Erstellen Sie mithilfe dieser Wahrheitstabelle (Tabelle 2.2) eine SDNF.
Tabelle 2.2
| X | j | z | Basic Konjunktionen |
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 |
Grundkonjunktionen (bzw Bestandteile_1), die in der Tabelle enthalten sind, entsprechen einem bestimmten Satz von Nullen und Einsen, die die Variablen x,y,z annehmen. Wähler werden aufgebaut_ 1 nach folgender Regel: Eine Variable ist im Produkt selbst enthalten, wenn sie auf einer gegebenen Menge den Wert 1 annimmt, andernfalls ist ihre Negation im Produkt enthalten. So nehmen beispielsweise auf der Menge (0,0,1) die Variablen x,y den Wert 0 an und daher sind ihre Negationen im Produkt enthalten, und die Variable z nimmt den Wert 1 an und ist daher im Produkt selbst enthalten . Für eine gegebene Menge (0,0,1) ist konstituent_1 gleich x ⋅ y ⋅ z .
Offensichtlich ist die Konjunktion x ⋅ y ⋅ z nur auf der Menge gleich 1
(0,0,0) und x ⋅ y ⋅ z ist 1 auf der Menge (0,0,1) usw. (siehe Tabelle). Beachten Sie als Nächstes, dass die Disjunktion zweier Basiskonjunktionen auf genau zwei Mengen, die diesen Basiskonjunktionen entsprechen, gleich 1 ist. Beispielsweise ist die Funktion x ⋅ y ⋅ z¤x ⋅ y ⋅ z nur auf zwei Mengen gleich 1 – (0,0,0) und (0,0,1), und auf allen anderen Mengen ist sie gleich 0. Ebenso ist die Disjunktion von drei Grundkonjunktionen gleich 1 auf genau drei Mengen, die diesen Grundkonjunktionen entsprechen usw.
Das. wir bekommen Regel: zum Erstellen von SDNF Sie sollten die Zeilen auswählen, in denen die Funktion gleich 1 ist, und dann die Disjunktion der entsprechenden Hauptkonjunktionen nehmen, um die gewünschte SDNF zu erhalten. Für unser Beispiel haben wir also x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Aufgabe. Konstruieren Sie mithilfe dieser Wahrheitstabelle die SCNF.
Verfassung_0 für eine Menge von Nullen und Einsen (die die Variablen x,y,z annehmen) ist wie folgt aufgebaut: Die Variable ist in der Disjunktion selbst enthalten, wenn sie den Wert dieser Menge annimmt 0 , andernfalls enthält das Werk seine Negation.
Regel zum Aufbau von SKNF: Sie sollten Zeilen auswählen, in denen die Funktion gleich ist 0 , und nehmen Sie dann die Konjunktion der entsprechenden Konstituenten_0. Das Ergebnis ist der gewünschte SCNF. Für unser Beispiel gilt also f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Kommentar. Um eine perfekte CNF-Funktion f zu konstruieren, reicht es aus, eine perfekte DNF für die Funktion f zu konstruieren, und dann
Konstruieren wir anhand der Bemerkung den SCNF für unser Beispiel. 1. Wir erstellen einen SDNF für die Negation.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Wir verwenden die Gesetze von de Morgan f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == (x ∨ y ∨ z ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Die beschriebene Methode zur Ermittlung des SDNF (und SCNF) mithilfe der Wahrheitstabelle ist häufig arbeitsintensiver als der folgende Algorithmus.
1. SDNF finden Wir reduzieren diese Formel zunächst auf DNF.
2. Wenn eine Konjunktion K (d. h. K ist das Produkt einer bestimmten Anzahl von Variablen oder deren Negationen) beispielsweise die Variable y nicht enthält, dann ersetzen wir diese Konjunktion durch die äquivalente Formel K&(y ∨ y) und anwenden Das Gesetz der Distributivität legen wir der DNF die resultierende Formel vor; Wenn mehrere Variablen fehlen, fügen wir für jede von ihnen die entsprechende Formel der Form (y ∨ y) zur Konjunktion hinzu.
3. Wenn der resultierende DNF mehrere identische Bestandteile der Einheit enthält, dann lassen wir nur einen davon übrig. Das Ergebnis ist SDNF.
Kommentar: Um eine SCNF in eine Klausel zu konstruieren, die beispielsweise keine Variable enthält bei Wir fügen eine Formel der Form y⋅ y hinzu, d.h. Wir ersetzen diese Disjunktion durch die äquivalente Formel D ∨ y⋅ y und unter Anwendung des 2. Distributivitätssatzes.
Beispiel 2. 2. 2. Konstruieren Sie eine SDNF für die Funktion f unter Verwendung äquivalenter Transformationen.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =
RÜCKZUG.
Die Berechnung von SDNF ist nicht nur theoretisch, sondern auch von großer praktischer Bedeutung. Beispielsweise wird in vielen modernen Programmen mit grafischer Oberfläche eine visuelle Form in Form einer Tabelle verwendet, um komplexe logische Bedingungen zu erstellen: Bedingungen werden in Zellen geschrieben, und die Zellen einer Spalte werden als durch eine Konjunktion verbunden betrachtet, und die Spalten gelten als durch eine Disjunktion verbunden, das heißt, sie bilden einen DNF (oder umgekehrt, in diesem Fall stellt sich heraus, dass es sich um einen KNF handelt). Auf diese Weise ist insbesondere die grafische Oberfläche QBE (Query-byExample) konzipiert, mit der logische Bedingungen bei der Abfrage eines DBMS formuliert werden.
Algorithmus 2.2.1. Bau von SDNF
Eingang: Vektor
Vektor F: Array von 0..1 entsprechenden Funktionswerten.
Ausfahrt: eine Folge von Symbolen, die einen Datensatz der SDNF-Formel für eine bestimmte Funktion bilden.
f:= FALSCH(Zeichen für das Vorhandensein des linken Operanden der Disjunktion) für ich aus 1Zu 2n Tun
Wenn F[i] = 1 dann wenn F Dann
Ertrag„¤“ (Hinzufügen eines Disjunktionszeichens zur Formel; Operator Ertrag m druckt
Symbol m) anders f:= WAHR
Ende wenn g:= FALSCH(Zeichen für das Vorhandensein des linken Operanden der Konjunktion) für J aus 1Zu N TU als ob G Dann
Ertrag„⁄“ (Hinzufügen eines Konjunktionszeichens zur Formel)
anders g: =wahr
Ende wenn wenn V (Hinzufügen einer Variablenkennung zur Formel
§2.3. DNF-Minimierung nach Quines Methode.
Jede Formel hat eine endliche Anzahl an Vorkommen von Variablen. Das Vorkommen einer Variablen bezieht sich auf den Platz, den die Variable in der Formel einnimmt. Die Aufgabe besteht darin, für eine gegebene boolesche Funktion f einen DNF zu finden, der diese Funktion repräsentiert und die geringste Anzahl an Vorkommen von Variablen aufweist.
Wenn x eine logische Variable ist und σœ(0,1), dann ist der Ausdruck x σ =xx, wenn σσ== 10 .
angerufen Brief . Konjunkt sogenannte Buchstabenkonjunktion. Beispielsweise sind die Formeln x ⋅ y ⋅ z und x ⋅ y ⋅ x ⋅ x Konjunktionen . Ein Elementarprodukt ist eine Konjunktion, in der eine Variable nur einmal vorkommt (entweder sie selbst oder ihre Negation).
Die Formel f1 heißt implizit Formeln f , wenn f1 ein Elementarprodukt ist und f 1 ⁄ f = f 1, d.h. das heißt, für die den Formeln entsprechenden Funktionen gilt die Ungleichung f 1 § f. Der Implikant f1 einer Formel f heißt einfach , wenn nach dem Verwerfen eines Buchstabens aus f1 keine Formel erhalten wird, die ein Implikant der Formel f ist.
Beispiel 2.3.1 . Finden wir alle Implikanten und einfachen Implikanten für die Formel f=xØy . Es gibt insgesamt 8 Elementarprodukte mit Variablen X Und u. Nachfolgend sind der Übersichtlichkeit halber ihre Wahrheitstabellen aufgeführt:
| X | j | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | X | j | X | j | |||||||
| 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 | |||||||
Aus den Wahrheitstabellen schließen wir, dass die Formeln x ⋅ y , x ⋅ y , x ⋅ y , x ,y - alle Implikanten der Formel xØy, und von diesen Implikanten sind die Formeln x und y einfach (die Formel x ⋅ y zum Beispiel ist kein einfacher Implikant, da wir durch Weglassen des Buchstabens y den Implikanten x erhalten).
Abgekürzt DNF heißt die Disjunktion aller Primimplikanten einer gegebenen Formel (Funktion) .
Satz 2.3.1. Jede boolesche Funktion, die nicht die Konstante 0 ist, kann als Kurzschrift-DNF dargestellt werden.
In Beispiel 2.3.1 wird die der Formel xØy entsprechende Funktion durch die Formel x ∨ y dargestellt, die ihr abgekürztes DNF ist.
Ein reduzierter DNF kann zusätzliche Implikanten enthalten, deren Entfernung die Wahrheitstabelle nicht verändert. Wenn wir alle unnötigen Implikanten aus einem reduzierten DNF entfernen, erhalten wir einen DNF namens Sackgasse.
Beachten Sie, dass die Darstellung einer Funktion als Dead-End-DNF im allgemeinen Fall mehrdeutig ist. Aus allen Dead-End-Formularen wird das Formular mit der geringsten Häufigkeit von Variablen ausgewählt minimaler DNF (MDNF).
Betrachten Sie die Methode Quina, um die MDNF zu finden, die eine gegebene boolesche Funktion darstellt. Wir definieren die folgenden drei Operationen:
1. Vollständiger Klebevorgang : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. Teilklebevorgang:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. Operation der Elementarabsorption f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Satz 2.3.2(Satz von Quine). Wenn wir basierend auf der SDNF-Funktion alle möglichen Operationen des unvollständigen Klebens und dann der elementaren Absorption durchführen, dann wird das Ergebnis ein reduzierter DNF sein, d. h. eine Disjunktion aller einfachen Implikanten.
Beispiel 2.3.2. Die Funktion f(x,y,z) sei durch eine perfekte DNF f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z gegeben. Dann führen wir in zwei Schritten alle möglichen Vorgänge des unvollständigen Klebens und dann der elementaren Absorption durch
F 
Somit ist die verkürzte DNF einer Funktion f die Formel y¤x·z.
In der Praxis ist es bei der Durchführung unvollständiger Klebevorgänge in jeder Phase möglich, nicht die an diesen Vorgängen beteiligten Begriffe aufzuschreiben, sondern nur die Ergebnisse aller möglichen vollständigen Klebevorgänge und Konjunktionen, die an keinem Klebevorgang beteiligt sind, aufzuschreiben.
Beispiel 2. 3. 3. Die Funktion f(x,y,z) sei durch eine perfekte DNF f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z gegeben.
Dann führen wir die Vorgänge des Klebens und anschließend der Elementarabsorption durch
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
Um aus dem reduzierten DNF den minimalen DNF zu erhalten, wird die Quine-Matrix verwendet , welches wie folgt aufgebaut ist. Die Spaltenüberschriften der Tabelle enthalten die Bestandteile der perfekten DNF-Einheit und die Zeilenüberschriften enthalten die einfachen Implikanten des resultierenden abgekürzten DNF. In der Tabelle markieren Sternchen die Schnittpunkte von Zeilen und Spalten, bei denen die Konjunktion im Zeilenkopf im Konstituenten der Einheit, dem Spaltenkopf, enthalten ist.
Zum Beispiel 2.3.3. Die Quine-Matrix hat die Form
In einem Dead-End-DNF wird die minimale Anzahl einfacher Implikanten ausgewählt, deren Disjunktion alle Konstituenten der Einheit bewahrt, d. h. jede Spalte der Quine-Matrix enthält ein Sternchen am Schnittpunkt mit der Zeile, die einem der Konstituenten entspricht ausgewählte Implikanten. Als minimaler DNF wird der Dead-End-DNF gewählt, der die geringste Anzahl an Variablenvorkommen aufweist.
In Beispiel 2.3.3 finden wir unter Verwendung der Quine-Matrix, dass die minimale DNF einer gegebenen Funktion x ⋅ y ¤ x ⋅ z ist.
Kommentar.
Verwenden Sie f =f und die Gesetze von De Morgan.
§ 2.4. Carnot-Karten.
Eine andere Möglichkeit, einfache Implikantenformeln mit einer kleinen Anzahl von Variablen zu erhalten (und damit die minimale DNF zu finden), basiert auf der Verwendung sogenannter Carnot-Karten.
Die Karnaugh-Karte ist ein spezieller Tabellentyp, der das Auffinden minimaler Formen vereinfacht und erfolgreich verwendet wird, wenn die Anzahl der Variablen sechs nicht überschreitet. Karnaugh-Karten für Funktionen, die von n Variablen abhängen, sind ein Rechteck, das in 2 n Zellen unterteilt ist. Jede Zelle des Diagramms ist einem binären n-dimensionalen Satz zugeordnet. Die Werte einer bestimmten Funktion f aus der Wahrheitstabelle werden in die erforderlichen Quadrate eingetragen, entspricht die Zelle jedoch 0, bleibt sie normalerweise leer.
In Tabelle 2.4.1. zeigt ein Beispiel für die Markierung einer Karnaugh-Karte für eine Funktion, die von drei Variablen abhängt. Die unteren vier Zellen der Karte entsprechen binären Mengen, in denen die Variable X Nimmt den Wert 1 an, entsprechen die oberen vier Zellen den Mengen, in denen die Variable enthalten ist X nimmt den Wert 0 an. Die vier Zellen, die die rechte Hälfte der Karte bilden, entsprechen Mengen, in denen die Variable y; nimmt den Wert 1 usw. an. In Tabelle 2.4.2. Dargestellt ist die Markierung der Karnaugh-Karte für n=4 Variablen.
Um einen minimalen DNF zu konstruieren, führen wir Folgendes aus: Klebevorgang „1“. Die zusammenklebenden Werte „1“ entsprechen benachbarten Zellen, also Zellen, die sich nur im Wert einer Variablen unterscheiden (im grafischen Bild durch eine vertikale oder horizontale Linie getrennt, unter Berücksichtigung der Nähe gegenüberliegender Extremzellen).
Beim Kleben von „1“ geht es darum, einzelne Zellen der Karnaugh-Karte zu Gruppen zusammenzufassen, und die folgenden Regeln müssen befolgt werden:
1. Die Anzahl der in einer Gruppe enthaltenen Zellen muss als Vielfaches von 2 ausgedrückt werden, d. h. 2 m mit m=0,1,2,...
2. Jede Zelle in einer Gruppe von 2 m Zellen muss m benachbarte Zellen in der Gruppe haben.
3. Jede Zelle muss zu mindestens einer Gruppe gehören.
4. Jede Gruppe sollte die maximale Anzahl an Zellen enthalten, d. h. Keine Gruppe sollte in einer anderen Gruppe enthalten sein.
5. Die Anzahl der Gruppen sollte minimal sein.
Lesefunktion f entsprechend der Klebegruppe wird wie folgt vorgegangen: Variablen, die in den Zellen der Klebegruppe die gleichen Werte behalten, werden in die Konjunktion einbezogen, und die Werte 1 entsprechen den Variablen selbst und die Werte 0 entsprechen ihre Verneinungen.
Wir stellen Vorlagen vor, die beim Aufbau von Abdeckungen helfen 1 (wir betrachten die Variablen als gleich, werden sie aber nicht schreiben). Um die Notation zu vereinfachen, werden wir die Variablen nicht markieren, ihre Bezeichnungen jedoch wie in den Tabellen 2.4.1 und 2.4.2 beibehalten.
| 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 |
Beispiel 2.4.1. Erstellen Sie MDNF.
Zuerst schauen wir, ob es irgendwelche Beschichtungen gibt_ 1 Von 16 Zellen bedeckt mindestens eine unbedeckte 1. Es gibt keine solchen Abdeckungen. Wir gehen zu Abdeckungen von 8 Zellen über. Mal sehen, ob es Abdeckungen von 1 von 8 Zellen gibt, die mindestens eine unbedeckte 1 abdecken. Es gibt keine solchen Abdeckungen. Wir gehen zu Abdeckungen von 4 Zellen über. Mal sehen, ob es Abdeckungen von 1 von 4 Zellen gibt, die mindestens eine unbedeckte 1 bedecken. Es gibt zwei solcher Abdeckungen. Wir gehen zu Abdeckungen von 2 Zellen über. Es gibt nur eine solche Beschichtung. Somit wurde alles abgedeckt. Als nächstes wollen wir sehen, ob wir einige der Abdeckungen entfernen können, damit alle Einheiten abgedeckt bleiben. Am Ende schreiben wir die MDNF aus: f =x⋅z∨y⋅w∨y⋅z⋅w.
Kommentar. Um den minimalen CNF einer Funktion f zu konstruieren, reicht es aus, den minimalen DNF für die Funktion f zu konstruieren, und dann
Verwenden Sie f =f und die Gesetze von De Morgan.
Kapitel III. Zhegalkin-Algebra.
Der Satz boolescher Funktionen, der in der Zhegalkin-Basis S4=(∆,&,1) definiert ist, wird Zhegalkin-Algebra genannt.
Grundeigenschaften.
1. Kommutativität
H1∆H2=H2∆H1, H1&H2=H2
2. Assoziativität
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. Distributivität
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. Eigenschaften der Konstanten H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Aussage 3.1.1. Alle anderen booleschen Funktionen können durch die Operationen der Zhegalkin-Algebra ausgedrückt werden:
Ÿ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. Das Zhegalkin-Polynom (Polynom Modulo 2) von n Variablen x 1 ,x 2 ,…,x n ist ein Ausdruck der Form c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, wobei Konstanten mit k kann die Werte 0 oder 1 annehmen.
Wenn das Zhegalkin-Polynom keine Produkte einzelner Variablen enthält, wird es als linear (lineare Funktion) bezeichnet.
Beispielsweise sind f=x∆yz∆xyz und f1=1∆x∆y∆z Polynome, wobei das zweite eine lineare Funktion ist.
Satz 3.1.1. Jede boolesche Funktion wird auf einzigartige Weise in Form eines Zhegalkin-Polynoms dargestellt.
Lassen Sie uns die wichtigsten Methoden zum Konstruieren von Zhegalkin-Polynomen aus einer gegebenen Funktion vorstellen.
1. Methode mit unsicheren Koeffizienten . Sei P(x 1 ,x 2 ,…,x n) das gewünschte Zhegalkin-Polynom, das die gegebene Funktion f(x 1 ,x 2 ,…,xn) implementiert. Schreiben wir es in das Formular
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 .
Finden wir die Koeffizienten mit k. Dazu weisen wir den Variablen x 1 , x 2 ,…, x n nacheinander Werte aus jeder Zeile der Wahrheitstabelle zu. Als Ergebnis erhalten wir ein System aus 2 n Gleichungen mit 2 n Unbekannten, das eine eindeutige Lösung hat. Nachdem wir es gelöst haben, finden wir die Koeffizienten des Polynoms P(x 1 ,x 2 ,…,xn).
2. Eine Methode, die auf der Transformation von Formeln über eine Reihe von Konnektiven basiert ( ÿ,&}. Konstruieren Sie eine Formel Ф über der Menge der Konnektive (Ÿ,&) und realisieren Sie die gegebene Funktion f(x 1 ,x 2 ,…,x n). Ersetzen Sie dann überall Unterformeln der Form A durch A∆1, öffnen Sie die Klammern mit dem Distributivgesetz (siehe Eigenschaft 3) und wenden Sie dann die Eigenschaften 4 und 5 an.
Beispiel 3.1.1. Konstruieren Sie ein Zhegalkin-Polynom für die Funktion f(x,y)=xØy.
Lösung. 1 . (Methode der unbestimmten Koeffizienten). Schreiben wir das benötigte Polynom in das Formular
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Verwendung der Wahrheitstabelle
| X | 0 | 0 | 1 | 1 |
| j | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
wir finden, dass 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
Daraus ergibt sich konsistent: c 0 =1, c 1 =1, c 2 =0, c 12 =1. Daher ist xØy=1∆x∆xy (vergleiche mit Aussage 3.1).
2. (Formelkonvertierungsmethode.) Wir haben
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Beachten Sie, dass der Vorteil der Zhegalkin-Algebra (im Vergleich zu anderen Algebren) in der Arithmetisierung der Logik liegt, die es ermöglicht, Transformationen boolescher Funktionen ganz einfach durchzuführen. Ihr Nachteil gegenüber der Booleschen Algebra ist die Umständlichkeit der Formeln.
Kapitel IV. Aussagen. Prädikate.
§4.1. Aussagen.
Bei der Konstruktion der Algebra der Logik haben wir einen funktionalen Ansatz verwendet. Es wäre jedoch möglich, diese Algebra konstruktiv zu konstruieren. Definieren Sie zunächst die Untersuchungsobjekte (Anweisungen), führen Sie Operationen für diese Objekte ein und untersuchen Sie ihre Eigenschaften. Lassen Sie uns formale Definitionen geben.
Indem ich sage Nennen wir einen Aussagesatz, über den man eindeutig sagen kann, ob er zu einem bestimmten Zeitpunkt wahr (Wert I oder 1) oder falsch (Wert L oder 0) ist. Zum Beispiel „5 ist eine Primzahl“, „Esc-Taste gedrückt“ usw. Verwendung von Konnektiven „nicht“, „und“, „oder“, „wenn,... dann“, „wenn und nur wenn“ (sie entsprechen den Operationen „Ÿ“, „&“, „¤“, „Ø“ , „~“ » entsprechend) können komplexere Aussagen (Sätze) konstruiert werden. So ist die Aussagenalgebra aufgebaut.
Um die Aufzeichnung komplexer Aussagen zu vereinfachen, wird der Vorrang von Konnektiven eingeführt: „Ÿ“, „&“, „¤“, „Ø“, „~“, wodurch unnötige Klammern weggelassen werden können.
Wir nennen einfache Aussagen propositionale Variablen.
Lassen Sie uns das Konzept einer Formel vorstellen.
1. Aussagenvariablen sind Formeln.
2. Wenn A, B Formeln sind, dann sind die Ausdrücke ŸA, A⁄B, A¤B, AØB, A~B Formeln.
3. Formeln sind nur nach den Absätzen 1 und 2 aufgebaute Ausdrücke.
Eine Formel, die den Wert AND für alle Werte von Aussagenvariablen annimmt, heißt Tautologie (oder allgemein gültig), und eine Formel, die für alle Werte der Aussagenvariablen den Wert A annimmt, heißt widersprüchlich (oder unmöglich)
Die Beschreibung der Eigenschaften der Aussagenalgebra ähnelt der Beschreibung der entsprechenden Funktionen in der Booleschen Algebra und wird hier weggelassen.
§4.2. Prädikate. Logische Operationen auf Prädikaten.
Gegenstand der Untersuchung in diesem Kapitel sind Prädikate – Abbildungen beliebiger Mengen in eine Menge von Aussagen. Tatsächlich vollziehen wir einen Übergang zu einer neuen Abstraktionsebene, einen Übergang der gleichen Art wie in der Schule – von der Arithmetik reeller Zahlen zur Algebra numerischer Funktionen.
Definition 2.1 Es seien x 1 ,x 2 ,…,xn Symbole von Variablen beliebiger Natur. Wir nennen diese Variablen Subjektvariablen. Die Variablenmengen (x 1 ,x 2 ,…,x n) sollen zur Menge M=(M1,M2,…Mn) gehören, die wir als Themenbereich bezeichnen (d. h. x i œM i, wobei Mi als Domäne bezeichnet wird). der Definition der Variablen xi). Ein Lokalitätsprädikat n (ein n-stelliges Prädikat), das für einen Themenbereich M definiert ist, ist eine logische Funktion, die entweder den Wert AND oder den Wert L annimmt.
Beispiel 4.2.1. D(x1,x2) = „Die natürliche Zahl x1 wird (ohne Rest) durch die natürliche Zahl x2 geteilt.“ - ein zweistelliges Prädikat, das auf der Menge der Paare natürlicher Zahlen M=NäN definiert ist. Offensichtlich ist D(4,2) = und D(3,5) = 0.
Beispiel 4.2.2. Q(x) ==“x 2<-1, хœR» - одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) - тождественно ложен, т. е.
Q(x) = À für alle xœR.
Beispiel 4.2.3. B(x,y,z) = "x 2 +y 2 Ein auf M definiertes Prädikat P heißt identisch wahr, wenn es für beliebige Werte der Subjektvariablen den Wert AND annimmt; Das Prädikat P heißt identisch falsch, wenn es für beliebige Werte der Subjektvariablen den Wert A annimmt. Prädikat Q aus Beispiel 4.2.2. ist identisch falsch. Da Prädikate Funktionen mit Werten in einer Reihe von Anweisungen sind, in denen logische Operationen eingeführt werden, werden diese Operationen natürlich für Prädikate definiert. Seien P und Q Prädikate, die auf M definiert sind. Dann 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ädikate P und Q, definiert auf M heißen äquivalent (schreibe P=Q), wenn P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) für jede Menge (x 1 ,x 2 ,…, x n )
Subjektvariablen von M .
Satz 4.2.1 Die Menge der auf M definierten n-ären Prädikate bildet eine boolesche Prädikatenalgebra. Damit gelten für sie die Grundäquivalenzen (siehe §1.6). Sei P(x 1 ,x 2 ,…,xn) ein auf M definiertes n-äres Prädikat. Legen wir x i = fest A. Definieren wir das (n-1)-äre Prädikat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) wie folgt: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1 ,x 2 ,…,xk1, A,xk+1,xn). Sie sagen, dass das Prädikat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) aus dem Prädikat P(x 1 ,x 2 ,…,xn) durch Festlegen des Werts von i- erhalten wird. te Variable: x i = A
. Definition
4.3.1
. Sei P(x) ein unäres Prädikat. Verknüpfen wir damit eine Aussage mit der Bezeichnung „xP(x)“ (sprich „für jedes x P(x)“), die genau dann wahr ist, wenn P(x) ein identisch wahres Prädikat ist. Die Aussage „xP(x)“. Man sagt, dass man es aus dem Prädikat P erhält, indem man einen universellen Quantor über die Variable x anhängt. Definition 4.3.2. Sei P(x) ein unäres Prädikat. Verknüpfen wir es mit einer Aussage mit der Bezeichnung $xP(x) (lesen Sie „es gibt x P(x)“), die genau dann falsch ist, wenn P(x) ein identisch falsches Prädikat ist. Man sagt, dass man die Aussage $xP(x) aus dem Prädikat P erhält, indem man der Variablen x einen Existenzquantor anhängt. Anmerkung 1. Die Symbole „ und $ für Quantoren sind umgekehrte lateinische Buchstaben A bzw. E, die die Anfangsbuchstaben in englischen Wörtern sind Alle- Alle, Existieren- existieren. Anmerkung 2. Anweisungen können als Prädikate betrachtet werden, die keine Variablen enthalten, d. h. Prädikate mit 0 Stellen (oder Prädikate beliebiger Lokalität). Sei P(x 1 ,x 2 ,…,xn) ein auf M definiertes n-äres Prädikat. Legen wir darin die Werte der Variablen x 1 ,x 2 ,…,x k-1 ,x k fest +1 ,x n . Wir fügen dem resultierenden unären Prädikat Q(x k) einen universellen (Existenz-)Quantor hinzu und erhalten eine Aussage. Somit ist eine feste Menge von Werten von Variablen x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n mit einer Aussage verbunden, die den Quantor der Universalität (Existenz) verwendet. Dieses (n-1)-äre Prädikat der Variablen x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n soll aus dem ursprünglichen Prädikat P(x 1 ,x 2 ,…, x n) durch Hinzufügen eines Quantifizierers Universalität (Existenz) in der k-ten Variablen. Dieses Prädikat wird wie folgt bezeichnet: „x zu P(x 1 ,x 2 ,…,x n) ($x zu P(x 1 ,x 2 ,…,x n)“). Sie sagen, dass es an den Quantor der Universalität (Existenz) gebunden ist. Beispiel 4.3.1. Sei D(x1,x2) = „Die natürliche Zahl x1 ist (ohne Rest) durch die natürliche Zahl x2 teilbar.“ - zweistelliges Prädikat. Ordnen wir seinen Variablen nacheinander Quantoren zu. Es ist klar, dass 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. Somit haben wir (durch den Vergleich von 7 und 8 im letzten Beispiel) den Satz bewiesen: Typischerweise werden Verknüpfungen und Quantoren wie folgt nach Priorität geordnet: Ÿ, ", $, &, ¤, Ø, ~. Satz 4.3.1. Entgegengesetzte Quantoren kommutieren im Allgemeinen nicht. Satz 4.3.2.(Basisäquivalenzen, die Quantoren enthalten) Folgende Äquivalenzen finden statt: 1. De Morgans Gesetze ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Kommutativität ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Distributivität ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Einschränkungen der Wirkung von Quantoren ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Für jedes zweistellige Prädikat ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Formale Theorie(oder Infinitesimalrechnung)
Y- Das: 1. Satz A
Charaktere bilden sich Alphabet
;
1.
ein Haufen F
Wörter im Alphabet A, F
à A
die aufgerufen werden Formeln
;
3. Teilmenge B
Formeln, B
à F
,
die aufgerufen werden Axiome; 4. viele Beziehungen R
auf einer Reihe von Formeln namens Regeln der Schlussfolgerung. Viele Symbole A
kann endlich oder unendlich sein. Üblicherweise wird zur Bildung von Symbolen eine endliche Menge von Buchstaben verwendet, denen ggf. natürliche Zahlen als Indizes zugeordnet werden. Viele Formeln F
üblicherweise durch induktive Definition gegeben, zum Beispiel mittels einer formalen Grammatik. Diese Menge ist in der Regel unendlich. Sets A
Und F
gemeinsam bestimmen Sprache
,
oder Unterschrift
,
formale Theorie. Viele Axiome B
kann endlich oder unendlich sein. Ist die Menge der Axiome unendlich, so wird sie in der Regel durch eine endliche Menge von Axiomenschemata und Regeln zur Generierung bestimmter Axiome aus dem Axiomenschema spezifiziert. Viele Inferenzregeln R
, in der Regel natürlich. Also, Kalkül Y es gibt eine vier (A, F, B, R)
. Durch Ableitung in der Analysis Y ist eine Folge von Formeln F 1 ,F 2 ,…,Fn, so dass für jedes k (1§k§n) die Formel Fk entweder ein Axiom der Infinitesimalrechnung Y oder eine direkte Konsequenz aller vorherigen Formeln ist, die durch die Folgerungsregel erhalten wurden . Eine Formel G heißt Satz der Infinitesimalrechnung Y (ableitbar in Y oder beweisbar in Y), wenn es eine Schlussfolgerung F 1 ,F 2 ,…,F n ,G gibt, die als Ableitung der Formel G oder als Beweis der Formel G bezeichnet wird Satz G. Dies wird wie folgt geschrieben: F 1,F 2,…,F n + G. Infinitesimalrechnung Y angerufen konsistent, wenn nicht alle Formeln beweisbar sind. Eine andere Definition der Konsistenz kann gegeben werden: Ein Kalkül heißt konsistent, wenn in ihm die Formeln F und ŸF (die Negation von F) nicht gleichzeitig ableitbar sind. Infinitesimalrechnung Y angerufen vollständig(oder adäquat), wenn jede wahre Aussage M einem Theorem der Theorie entspricht Y
. Formale Theorie Y angerufen entscheidbar, wenn es einen Algorithmus gibt, der für jede Formel der Theorie bestimmt, ob diese Formel ein Satz der Theorie ist Y oder nicht. Unter Verwendung des Konzepts der formalen Analysis definieren wir Aussagenkalkül (PS). Alphabet IW besteht aus 1. Briefe A, B, Q, R, P und andere, ggf. mit Indizes (die Aussagenvariablen genannt werden), 2. logische Symbole(Bänder) Ÿ, &, ¤, Ø, 3. Hilfs Figuren
(,). Viele Formeln IV wird induktiv bestimmt: 1. Alle Aussagenvariablen sind IV-Formeln; 2. wenn A, B Formeln sind IV ,
toŸA, A⁄B, A¤B, AØB - FormelnIV ;
3. Ein Ausdruck ist genau dann eine IV-Formel, wenn dies anhand der Punkte „1“ und festgestellt werden kann Somit wird jede IV-Formel aus Aussagenvariablen unter Verwendung der Konnektive Ÿ, ⁄, ¤, Ø konstruiert. In Zukunft werden wir beim Schreiben von Formeln einige Klammern weglassen und dabei die gleichen Konventionen wie im vorherigen Kapitel verwenden. Axiome IV sind die folgenden Formeln (für alle Formeln 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); Diese Formeln werden IV-Axiomschemata genannt .
Beim Einsetzen bestimmter Formeln in ein beliebiges Schema erhält man einen Sonderfall des Axiomschemas. Schlussfolgerungsregel Im IE gibt es eine Schlussfolgerungsregel (modus ponens): Wenn A und AØB ableitbare Formeln sind, dann ist auch B ableitbar Symbolisch wird es so geschrieben: A, A B →
B
. Wenn beispielsweise die Aussagen A⁄B und A⁄BØ(AØC) ableitbar sind, dann ist auch die Aussage AØC gemäß der Inferenzregel ableitbar. Eine Formel G soll aus den Formeln F 1 ,F 2 ,…,F n (bezeichnet mit F 1 ,F 2 ,…,F n +G) ableitbar sein, wenn es eine Folge von Formeln F 1 ,F 2 ,… gibt ,F k ,G , wobei jede Formel entweder ein Axiom ist oder zur Liste der Formeln F 1,F 2,...,F n (Hypothesen genannt) gehört oder aus früheren Formeln gemäß der Regel von erhalten wird Inferenz. Die Ableitbarkeit der Formel G aus „ (bezeichnet mit +G) ist äquivalent zur Tatsache, dass G ein IV-Theorem ist. Beispiel 5.2.1. Zeigen wir, dass die Formel AØA in IV ableitbar ist. Dazu erstellen wir die Ableitung dieser Formel: 1) Ersetzen Sie in Axiom 2 B durch AØA und C durch A. Wir verstehen das Axiom (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) in Axiom 1 ersetzen wir B durch A. Wir erhalten AØ(AØA); 3) Aus 1 und 2 schließen wir entsprechend dem Modus Ponens (AØ((AØA)ØA))Ø(AØA); 4) In Axiom 1 ersetzen wir B durch AØA. Wir erhalten AØ((AØA)ØA); 5) aus Absätzen. 3 und 4, gemäß der Inferenzregel, ist + AØA wahr. Satz 5.2.1. 1. Wenn F 1 ,F 2 ,…,Fn,A,B IV-Formeln sind, Г=(F 1 ,F 2 ,…,Fn), Г+A, dann Г,B+A. (Sie können die Anzahl der Hypothesen erhöhen). 2. Genau dann, wenn F 1 ,F 2 ,…,F n +A, wenn F 1 ⁄F 2 ⁄…⁄F n +A (Reduktion vieler Hypothesen auf eine Hypothese). Satz 5.3.1. (Abzugssatz) Wenn Г,B+A, dann Г+BØA, wobei Г eine Menge einiger Formeln Г=(F 1 ,F 2 ,…,F n ) ist. Folgerung 5.3.1. Dann und nur dann, wenn F 1 ,F 2 ,…,F n +A, wann Nachweisen. Sei F 1 ,F 2 ,…,F n +A. Dann gilt unter Anwendung des Deduktionssatzes F 1 ,F 2 ,…,F n-1 +F n ØA. Ähnlich F 1 ,F 2 ,…,F n-2 +F n 1Ø(F n ØA) usw. Wenn wir den Prozess so oft fortsetzen, wie erforderlich, erhalten wir F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) Um die Hinlänglichkeit zu beweisen, nehmen Sie an, dass +B, wobei B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Verwenden wir Satz 5.2.1, Punkt 1: F 1 +B .
Gemäß der Schlussfolgerungsregel erhalten wir F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), dann haben wir nach n Schritten F 1 ,F 2 ,…,F n +A . Somit reduziert sich dank Korollar 5.3.1. die Prüfung der Ableitbarkeit der Formel A aus den Formeln F 1,F 2,…,F n auf die Prüfung der Beweisbarkeit der Formel F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Denken Sie daran, dass eine Formel A als identisch wahr (oder als Tautologie) bezeichnet wird, wenn der Wert der Formel A für jede Menge von Werten der Aussagenvariablen gleich eins ist. Der folgende Satz reduziert die Überprüfung der Beweisbarkeit einer Formel auf die Überprüfung ihrer identischen Wahrheit. Satz 5.3.2. (zur Vollständigkeit). Formel A ist genau dann beweisbar, wenn A identisch wahr ist (Tautologie): +A ‹ A-Tautologie. Um also festzustellen, ob eine Formel beweisbar ist, reicht es aus, ihre Wahrheitstabelle zu erstellen. Bekanntlich gibt es einen effektiven Algorithmus zum Erstellen einer Wahrheitstabelle und daher IV lösbar. Beispiel 5.3.1. Beweisen wir, dass P+P. Nach dem Deduktionssatz entspricht dies +(PØP). Nach dem Vollständigkeitssatz wiederum reicht es zu beweisen, dass (РØР) eine Tautologie ist. Erstellen einer Wahrheitstabelle für die Formel (РØР) ,
Wir sind davon überzeugt, dass (РØР) identisch wahr und daher beweisbar ist. Satz 5.3.3. (über Konsistenz). Der IW-Kalkül ist konsistent. Nachweisen. Nach dem Vollständigkeitssatz ist jede Formel, die nicht identisch wahr ist, im IW nicht beweisbar. Eine solche Formel ist beispielsweise die Formel A⁄(ŸA). Die Formelmenge Г heißt umstritten
,
wenn Г+А⁄(ŸА) .
Wenn Г eine widersprüchliche Formelmenge ist, bezeichnen wir diese Tatsache mit Г+. Stellungnahme
5.3.1.
Formel A ist aus der Menge der Formeln Г genau dann ableitbar, wenn die Menge Г»(ŸA) widersprüchlich ist. Die automatische Beweisführung von Theoremen ist der Grundstein der Logikprogrammierung, der künstlichen Intelligenz und anderer moderner Programmiertrends. Im Allgemeinen gibt es möglicherweise keinen Algorithmus, mit dem man bei einer gegebenen beliebigen Formel A nach einer endlichen Anzahl von Schritten bestimmen kann, ob A im Kalkül Y ableitbar ist oder nicht. Für einige einfache formale Theorien (z. B. Aussagenkalkül) und einige einfache Klassen von Formeln (z. B. angewandte Prädikatenrechnung mit einem unären Prädikat) sind jedoch Algorithmen zum automatischen Beweisen von Theoremen bekannt. Im Folgenden skizzieren wir am Beispiel der Aussagenrechnung die Grundlagen der Resolutionsmethode – einer klassischen und zugleich beliebten Methode zum automatischen Beweisen von Theoremen. Denken Sie daran, dass der Ausdruck gilt, wenn x eine logische Variable ist und σœ(0,1). x σ = xx, wenn σσ == 10 oder x σ = 10, wenn x x =≠σσ , wird aufgerufen Brief. Die Buchstaben x und Ÿx heißen konträr.
Konjunkt sogenannte Buchstabenkonjunktion. disjunkt sogenannte Buchstabendisjunktion. Seien D 1 = B 1 ∨ A, D 2 = B 2 ∨ A Klauseln. Die Klausel B 1 ¤B 2 heißt resolvent Die Klauseln D 1 und D 2 werden durch den Buchstaben A gekennzeichnet und mit res A (D 1 ,D 2) bezeichnet. Die Auflösung der Klauseln D 1 und D 2 ist die Auflösung durch einen Buchstaben und wird mit res(D 1 ,D 2) bezeichnet. Offensichtlich ist res(A,ŸA)=0. Tatsächlich, weil A=A¤0 und ŸA=ŸA¤0, dann res(A,ŸA)=0¤0=0. Wenn die Klauseln D 1 und D 2 keine kontrastierenden Zeichen enthalten, dann haben sie keine Auflösungszeichen. Beispiel 5.5.1. Wenn D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, dann 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) existiert nicht. Aussage 5.5.1. Wenn res(D 1 ,D 2) existiert, dann D 1 ,D 2 + res(D 1 ,D 2). Sei S=(D 1 ,D 2 ,…,Dn) die Menge der Klauseln. Eine Folge von Formeln F 1 ,F 2 ,…,F n heißt eine resolute Ableitung von S, wenn für jede Formel F k eine der Bedingungen erfüllt ist: 2. Es gibt j, k
Satz 5.5.1.
(über die Vollständigkeit der Auflösungsmethode). Eine Menge von Klauseln S ist genau dann widersprüchlich, wenn es eine auflösende Konklusion aus S gibt, die mit 0 endet. Beachten Sie, dass die Auflösungsmethode verwendet werden kann, um die Ableitbarkeit einer Formel F aus einem gegebenen Satz von Formeln F 1,F 2,…,F n zu überprüfen. Tatsächlich ist die Bedingung F 1 ,F 2 ,…,F n +F äquivalent zur Bedingung F 1 ,F 2 ,…,F n ,ŸF+ (viele Formeln sind widersprüchlich), die wiederum äquivalent zur Bedingung Q+ ist, wobei Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Reduzieren wir die Formel Q auf CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, dann Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Die Aufgabe, die Ableitbarkeit von F 1 ,F 2 ,...,F n +F zu prüfen, läuft also darauf hinaus, die Inkonsistenz der Klauselmenge S=(D 1 ,D 2 ,...,D m ) zu prüfen. , was der Existenz einer dekretierten Schlussfolgerung 0 aus S entspricht. Beispiel 5.5.2.Überprüfen Sie das Verhältnis AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) mit der Auflösungsmethode. Laut Aussage 5.3.1. muss nachschauen Inkonsistenz vieler Formeln S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Wir präsentieren alle Formeln von. S bis 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) . Somit erhalten wir eine Menge von Klauseln S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Konstruieren wir eine auflösende Schlussfolgerung aus S, die mit 0 endet: 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 . Daraus schließen wir, dass die Formel AØ(BØF) aus der Menge der Formeln AØ(BØC), CDØE, ŸFØD&(Ÿ)E ableitbar ist. Beachten Sie, dass die Auflösungsmethode ausreicht, um die mögliche Erfüllbarkeit einer bestimmten Menge von Klauseln S zu ermitteln. Dazu nehmen wir in die Menge S alle Klauseln auf, die durch auflösende Deduktionen von S erhalten werden. Aus dem Satz über die Vollständigkeit der Auflösungsmethode es folgt Folgerung 5.5.1. Wenn eine Menge von Klauseln S die Resolventen aller ihrer Elemente enthält, dann ist S genau dann erfüllbar, wenn 0–S. Ein charakteristisches Merkmal der Moderne ist der weit verbreitete Einsatz von Computern zur Lösung von Problemen (Aufgaben) in verschiedenen Bereichen menschlichen Handelns. Allerdings muss das Problem zunächst algorithmisch gelöst werden, d.h. Es muss eine formale Vorschrift gegeben werden, anhand derer man das Endergebnis zur Lösung aller Probleme einer bestimmten Art erhalten kann (dies ist ein intuitives, nicht strenges Konzept eines Algorithmus). Zum Beispiel ein Algorithmus zum Ermitteln des größten gemeinsamen Teilers zweier natürlicher Zahlen a, b, wie folgt: 1) Erweitern Sie die Zahl A nach Primfaktoren; 2) Wiederholen Sie Schritt 1 für B
Und Gehen Sie zu Schritt 3; 3) das Produkt gemeinsamer Primfaktoren aus Erweiterungen zusammensetzen A Und B mit Indizes, die dem kleinsten der Inklusionsindizes in den Erweiterungen entsprechen. Nachdem wir dieses Beispiel analysiert haben, stellen wir die wichtigsten Merkmale (Eigenschaften) des Algorithmus fest: 1.
Massencharakter- Anwendbarkeit des Algorithmus nicht auf ein Problem, sondern auf eine Klasse von Problemen. 2.
Diskretion- eine klare Aufteilung in einzelne Stufen (Schritte) des Algorithmus. 3.
Determinismus- eine solche Organisation der Ausführungsphasen, bei der immer klar ist, wie der Übergang von einer Phase zur anderen erfolgen soll. 4.
Glied- Um bei der Anwendung eines Algorithmus zur Lösung eines bestimmten Problems ein Ergebnis zu erhalten, wird eine endliche Folge von Schritten des Algorithmus ausgeführt: Beachten Sie, dass, wenn das Vorhandensein eines Algorithmus an sich als Beweis für die Existenz eines Algorithmus dient, zum Nachweis seiner Abwesenheit eine strenge mathematische Definition eines Algorithmus erforderlich ist. Versuche, das Konzept eines Algorithmus zu formalisieren, führten zur Entstehung Turingmaschinen, als ein imaginäres Gerät, das den Algorithmus implementiert. Ein weiterer Schritt bei der Definition des Konzepts eines Algorithmus war das Erscheinungsbild rekursive Funktionen ,
als Funktionen, die das Konzept eines Algorithmus formalisieren und das intuitive Konzept der Berechenbarkeit implementieren. Es stellte sich bald heraus, dass die Menge der rekursiven Funktionen mit der Menge der auf Turing-Maschinen berechenbaren Funktionen übereinstimmte. Neue Konzepte, die dann auftauchten und behaupteten, das Konzept eines Algorithmus zu erklären, erwiesen sich als äquivalent zu auf Turing-Maschinen berechenbaren Funktionen und damit zu rekursiven Funktionen. Das Ergebnis der anhaltenden Diskussion darüber, was ein Algorithmus ist, war eine Aussage, die heute Churchs These genannt wird. These der Kirche. Das Konzept eines Algorithmus oder der Berechenbarkeit durch ein mechanisches Gerät stimmt mit dem Konzept der Berechenbarkeit auf Turing-Maschinen (und daher mit dem Konzept einer rekursiven Funktion) überein. Mit anderen Worten: Ein Algorithmus ist ein Prozess, der durch ein Funktionsdiagramm dargestellt und von einer Turing-Maschine implementiert werden kann. Eine Turingmaschine ist ein (abstraktes) Gerät bestehend aus einem Band, einem Steuergerät und einem Lesekopf. Das Band ist in Zellen unterteilt. Jede Zelle enthält genau ein Zeichen von externes Alphabet
A=(
ein 0 ,
a 1 ,…,
ein ). Ein Symbol (wir werden es bezeichnen Ÿ
) des Alphabets A wird als leer bezeichnet, und jede Zelle, die derzeit ein leeres Zeichen enthält, wird (in diesem Moment) als leere Zelle bezeichnet. Es wird davon ausgegangen, dass das Band in beide Richtungen potenziell unbegrenzt ist. Kontrollgerät Zu jedem Zeitpunkt befindet sich q j in einem Zustand, der zur Menge gehört Q=(q 0 , q 1 ,..., q m )(m=l). Die Menge Q heißt internes Alphabet
.
Eine dieser Bedingungen (normalerweise q 0) heißt final und einige andere (normalerweise q 1) - anfänglich. Der Lesekopf bewegt sich entlang des Bandes, sodass er zu jedem Zeitpunkt genau eine Zelle des Bandes abtastet. Der Kopf kann den Inhalt der überwachten Zelle lesen und anstelle des überwachten Symbols ein neues Symbol aus dem externen Alphabet hineinschreiben A(möglicherweise das Gleiche). Während des Betriebs ändert das Steuergerät je nach Zustand, in dem es sich befindet, und dem vom Kopf betrachteten Symbol, seinen internen Zustand Q. Dann erteilt er dem Kopf den Befehl, ein bestimmtes Zeichen aus dem externen Alphabet in der überwachten Zelle zu drucken A, und befiehlt dann dem Kopf, entweder an Ort und Stelle zu bleiben oder eine Zelle nach rechts oder eine Zelle nach links zu bewegen. Im Endzustand hört die Maschine auf zu arbeiten. Konfiguration auf Band (oder Maschinenwort) heißt eine Menge, die gebildet wird durch: 1) Reihenfolge A
ich (1)
,A
ich (2)
,...,A
Ist) Zeichen aus dem externen Alphabet A, in Bandzellen aufgezeichnet, wo A
ich
(1)
.- das in der ersten Zelle links geschriebene Symbol usw. (Jede solche Sequenz heißt in einem Wort), 2) der Zustand des internen Speichers q r ; 3) Nummer k wahrgenommene Zelle. Wir werden die Maschinenkonfiguration wie folgt schreiben: 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) Hier R- Die wahrgenommene Zelle wird als Bruch hervorgehoben. Wenn sich die Maschine im internen Zustand befindet q ich, akzeptiert eine Zelle mit einem Symbol ein u, schreibt zum nächsten Zeitpunkt ein Symbol in diese Zelle ein r, geht in den internen Zustand über qs und bewegt sich entlang des Bandes, dann heißt es, dass die Maschine den Befehl ausführt q i a u
Æ
q s a r S, wobei das Symbol S einen der folgenden Werte annehmen kann: -1 – Kopf nach links verschieben; +1 - Kopfverschiebung nach rechts; 0 – der Kopf bleibt an Ort und Stelle. Die Liste aller Befehle (Fünflinge), die den Betrieb einer Turing-Maschine bestimmen, wird aufgerufen Programm dieses Auto. Das Maschinenprogramm wird häufig in Form einer Tabelle angegeben. Also für die oben in der Tabelle beschriebene Situation an der Kreuzung Linien A
u und Spalte q ich wird stehen q s a r S(siehe Tabelle 6.2.1) Tabelle 6.2.1. Wenn das Programm Autos für ein Paar umfasst (
q i ,a u
)
fünf fehlt, dann in der Tabelle am Schnittpunkt der Linie ein u, und Spalte q ich ein Bindestrich wird hinzugefügt. Also, Eine Turingmaschine ist per Definition, Bausatz M=(A,Q,P), Wo A- externes Alphabet, Q— Alphabet der internen Zustände, P- Programm. Wenn eine Maschine, nachdem sie mit einem auf Band geschriebenen Wort P zu arbeiten begonnen hat, den Endzustand erreicht, wird sie aufgerufen auf dieses Wort anwendbar. Das Ergebnis seiner Arbeit ist das auf das Band geschriebene Wort im Endzustand. Andernfalls soll die Maschine nicht auf das Wort R anwendbar sein. Beispiel 6.2.1. Lassen Sie uns eine Turing-Maschine bauen, die natürliche Zahlen addiert, die im unären Zahlensystem geschrieben sind (d. h. mit einem Symbol geschrieben). |.
Zum Beispiel 5=|||||.). Lösung. Betrachten Sie das Alphabet A
= {|, +, ⁄}. Die Maschine wird durch folgendes Programm bestimmt: Schreiben wir die Konfigurationen auf, die beim Betrieb dieser Maschine nacheinander auf das ursprüngliche Wort ||+ ||| entstehen , d.h. 2+3. Hier verwenden wir bei der Aufzeichnung der Konfiguration die folgende Konvention: Der Zustand, in dem sich die Maschine befindet, wird in Klammern rechts hinter dem beobachteten Buchstaben geschrieben. Beispiel 6.2.2. Bauen Sie eine Turingmaschine, die im unären Zahlensystem geschriebene natürliche Zahlen verdoppelt. Lösung. Konstruieren wir die erforderliche Maschine im Alphabet A=(|, α, ⁄). Das Programm für eine solche Maschine könnte so aussehen: Wenden wir die resultierende Maschine auf das Wort an ||
. Einführung eines neuen Buchstabens α und Ersetzung der ursprünglichen Buchstaben |
auf α ermöglicht die Unterscheidung des Originals |
und neu (zugewiesen) |
. Zustand q 1 sorgt für Ersatz |
auf α ,
Zustand q 2 Bietet die Suche nach α ,
soll ersetzen |
, und Stoppen der Maschine in dem Fall, wenn α nicht erkannt wird, q 3 sorgt für die Vollendung |
für den Fall, dass α durch ersetzt wurde |.
Lassen Sie uns das in diesem Absatz vereinbaren 1. Die Menge N der natürlichen Zahlen enthält 0 (Null), d.h. N=(0,1,2,3,...); 2. Die betrachteten Funktionen f=f(x 1 ,x 2 ,…,x n) sind nur definiert, wenn die Variablen Werte von N annehmen, d.h. xiœN; 3. Wertebereich der Funktionen DŒN; 4. Die betrachteten Funktionen f=f(x 1 ,x 2 ,…,x n) können teilweise definiert werden, d.h. nicht für alle Mengen natürlicher Zahlen definiert. Lassen Sie uns in Betracht ziehen einfache Funktionen o(x)=0, s(x)=x+1,
I m n (x 1 ,..., x n)
=
x m Diese Funktionen können mit einem geeigneten mechanischen Gerät (z. B. einer Turingmaschine) berechnet werden. Definieren wir Operatoren, die neue Funktionen basierend auf einer oder mehreren gegebenen Funktionen erstellen. Überlagerungsoperator. Es sei die Funktion f(x 1 ,x 2 ,…,x k) von k Variablen und k Funktionen f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n). gegeben n Variablen. Eine Überlagerung der Funktionen f,f 1 ,…,f k ist die Funktion j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n)) Wir sagen, dass die Funktion j durch die Anwendung des Superpositionsoperators S k+1 auf die Funktionen f,f 1 ,…,f k erhalten wird, und schreiben j=S k+1 (f,f 1 ,…,f k) Zum Beispiel S 2 (s, o)=s(o(x)), d.h. eine Funktion, die identisch gleich 1 ist, und S 2 (s,s)=s(s(x)) ist eine Funktion y(x)=x+2. Primitiver Rekursionsoperator. Gegeben seien die Funktionen g(x 1 ,x 2 ,…,x n) und h(x 1 ,x 2 ,…,x n+2). Konstruieren wir eine Funktion f(x 1 ,x 2 ,…,x n+1) Lassen Sie die Werte x 1 ,x 2 ,…,x n fest sein. Dann nehmen wir an: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) f 1 (x 1 ,x 2 ,…,x n ,y+1)= h(x 1 ,x 2 ,…,x n ,y, f(x 1 ,x 2 ,…,x n ,y)) Diese Gleichungen definieren die Funktion f(x 1 ,x 2 ,…,x n+1) eindeutig. Eine Funktion f heißt eine Funktion, die mit dem primitiven Rekursionsoperator R erhalten wird. Es wird die Notation f=R(g,h) verwendet. Die induktive Definition einer Funktion (demonstriert im primitiven Rekursionsoperator) ist in der Mathematik keine Seltenheit. Beispielsweise wird 1) ein Grad mit natürlichem Exponenten induktiv bestimmt: A
0
=1, A n+ 1
=ein n
ÿ A
; 2) Fakultät: 0!=1, (n+1)!= n!ÿ(n+1) usw. Definition. Funktionen, die aus der einfachsten Form o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m durch endlich häufige Anwendung von Superpositionsoperatoren und primitiver Rekursion erhalten werden können werden genannt primitiv rekursiv. Überprüfen wir, ob die Funktion u(x,y)=x+y primitiv rekursiv ist. Tatsächlich gilt: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Dies ist ein primitives Rekursionsschema, da x= I 1 1 (x) und u(x,y)+1=s(u(x,y))=S 2 (s,u). Hier ist g(x)= I 1 1 (x) und h(x,y,u)=s(u)=S 2 (s, I 3 3). Ebenso ist bewiesen, dass die Funktionen m(x,y)=xÿy, d(x,y)=x y (wir nehmen per Definition an 0 0 =1), fact(x)=x! und viele andere sind primitiv rekursiv. Notiz; dass primitiv rekursive Funktionen überall definiert sind (d. h. definiert für alle Werte ihrer Argumente). Tatsächlich die einfachsten Funktionen o, s, I m n sind überall definiert, und die Anwendung von Superpositions- und primitiven Rekursionsoperatoren auf überall definierte Funktionen ergibt auch überall definierte Funktionen. Also eine Funktion wie = x − y, wenn x ≥ y< y f(x,y) existiert nicht, wenn x kann nicht primitiv rekursiv sein. Wir haben hier kein Recht, die Funktion f(x,y)=x-y zu berücksichtigen, da die Funktionswerte natürliche Zahlen (also nicht negativ) sein müssen. Man kann jedoch die Funktion berücksichtigen ÷ y = 0x − y wenn x x<≥y.y Überprüfen wir, ob es primitiv rekursiv ist. Beweisen wir zunächst, dass die Funktion j(x)=xπ1 primitiv rekursiv ist. Tatsächlich ist j(0)=0. j(y+1)=(y+1)π1=y, was als primitives Rekursionsschema für die Funktion xπ1 dient. Schließlich ist xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) ein primitives Rekursionsschema für xπy. Eine wesentlich breitere Klasse von Funktionen als primitive rekursive Funktionen ist die Klasse der rekursiven Funktionen (siehe Definition unten). In der Literatur werden diese Funktionen auch aufgerufen teilweise rekursiv .
Um sie zu bestimmen, führen wir einen weiteren Operator ein. Minimierungsoperator. Gegeben sei die Funktion f(x 1 ,x 2 ,… ,x n ,x n+1). Lassen Sie uns einige Werte festlegen x 1 ,x 2 ,… ,x n der ersten n Variablen und berechnen f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,… ,x n ,2) usw. Wenn y die kleinste natürliche Zahl ist, für die f(x 1 ,x 2 ,… X n ,y)=x n+1 (d. h. Werte f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1 ,x 2 ,… X n ,y-1) alle existieren und nicht gleich xn +1 sind), dann setzen wir g(x 1 ,x 2 ,… X n ,x n+1)=y. Somit ist g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Wenn ja j Nein, dann gehen wir davon aus, dass f(x 1 ,x 2 ,… ,x n ,x n+1) nicht definiert ist. Es sind also drei Fälle möglich: 1. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) existieren und nicht gleich xn +1 sind, und 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 ,… ,x n ,y-1) existieren und sind nicht gleich xn +1, aber f(x 1 ,x 2 ,…,x n ,y) existiert nicht; 3. f(x 1 ,x 2 ,… ,x n ,i) existieren für alle iœN und sind von xn +1 verschieden. Wenn der 1. Fall auftritt, dann ist g(x 1 ,x 2 ,… ,x n ,x n+1)=y, und wenn der 2. oder 3. Fall vorliegt, dann ist g(x 1 ,x 2 ,… ,x n , x n +1) ist nicht definiert. Eine auf diese Weise erhaltene Funktion g soll mithilfe des Minimierungsoperators aus f erhalten werden M. Wir schreiben g= Mf. Der Minimierungsoperator ist eine offensichtliche Verallgemeinerung des Umkehrfunktionsoperators. Die Verallgemeinerung ist ziemlich tiefgreifend, da die Funktion f nicht eins zu eins sein muss (in der Variablen x n+1). Definition. Funktionen, die vom Einfachsten abgeleitet werden können o(x)=0, s(x)=x+1,
I m n (x 1 ,..., x n)
= x m Die Anwendung von Superpositionsoperatoren, primitiven Rekursionen und Minimierungsoperatoren wird endlich oft aufgerufen rekursiv. Die Klasse der rekursiven Funktionen ist breiter als die Klasse der primitiven rekursiven Funktionen, schon allein deshalb, weil sie nicht nur Funktionen enthält, die überall definiert sind. Beweisen wir zum Beispiel, dass die Funktion = x − y, wenn x ≥ y< y f(x,y) existiert nicht, wenn x ist rekursiv. Tatsächlich ist f(x,y)=min(z| y+z=x), und es wurde zuvor festgestellt, dass die Funktion u(x,y)=x+y primitiv rekursiv ist. Rekursive Funktionen spiegeln unser intuitives Verständnis der Funktionen wider, die ein mechanisches Gerät berechnen kann. Insbesondere sind sie auf Turingmaschinen berechenbar (siehe vorheriger Absatz). Im Gegenteil, jede auf einer Turing-Maschine berechenbare Funktion ist rekursiv. Wir werden diesen Sachverhalt nicht überprüfen, da dies zu viel Zeit und Platz in Anspruch nehmen würde. Ein vollständiger Beweis findet sich beispielsweise im Buch von A.I. Maltsev „Algorithmen und rekursive Funktionen“. Beachten Sie, dass nicht jede Funktion natürlicher Argumente rekursiv ist, nicht einmal jede Funktion eines einzelnen Arguments. Die Existenz nichtrekursiver Funktionen ist der „mathematische Grund“ für das Vorhandensein algorithmisch unlösbarer Probleme. In verschiedenen Teilgebieten der Mathematik gibt es algorithmisch unlösbare Probleme, d. h. Probleme, für die es keinen Lösungsalgorithmus gibt, und zwar nicht, weil er noch nicht erfunden wurde, sondern weil er prinzipiell unmöglich ist. Natürlich muss der Algorithmus im Sinne von Turingmaschinen und rekursiven Funktionen verstanden werden. Lassen Sie uns eines dieser Probleme formulieren Stoppproblem der Turingmaschine. Eine Turingmaschine ist ein Objekt, das durch eine endliche Anzahl von Parametern definiert ist. Alle Teilabbildungen von einer endlichen Menge auf eine andere können effizient neu nummeriert werden. Daher kann jeder Turingmaschine eine Zahl (eine natürliche Zahl) zugewiesen werden. Sei T(n) eine Turingmaschine mit der Nummer n. Einige Maschinen, die mit einem leeren Band in Betrieb gehen, bleiben irgendwann stehen, andere laufen auf unbestimmte Zeit. Es entsteht das Problem: Bestimmen Sie bei gegebener natürlicher Zahl n, ob eine Turing-Maschine T(n), die auf einem leeren Band gestartet wird, stoppt oder nicht. Diese Aufgabe algorithmisch unentscheidbar. Das heißt, es gibt kein automatisches Verfahren ,
für jedes n entscheidet es, ob die Maschine T(n) stoppt oder nicht. Dies hindert uns nicht daran, für eine bestimmte Maschine zu bestimmen, ob sie stoppt oder nicht. Es gibt keine Methode, die dieses Problem für alle Maschinen gleichzeitig löst .
Wie findet man angesichts eines Problems einen effizienten Algorithmus, um es zu lösen? Und wenn ein Algorithmus gefunden wird, wie kann er dann mit anderen Algorithmen verglichen werden, die das gleiche Problem lösen? Wie kann man seine Qualität beurteilen? Fragen dieser Art sind sowohl für Programmierer als auch für diejenigen, die sich mit der theoretischen Informatik befassen, von Interesse. Es gibt viele Kriterien zur Bewertung von Algorithmen. Am häufigsten interessiert uns die Reihenfolge des Wachstums der Zeit und der Speicherkapazität, die zur Lösung eines Problems erforderlich sind, wenn die Eingabedaten zunehmen. Wir möchten jeder spezifischen Aufgabe eine Zahl zuordnen, die wir ihre Größe nennen ,
Dies würde ein Maß für die Menge der Eingabedaten ausdrücken. Beispielsweise kann die Größe eines Matrixmultiplikationsproblems die größte Größe der Faktormatrizen sein. Die Zeit, die ein Algorithmus als Funktion der Problemgröße benötigt, wird aufgerufen Zeitkomplexität dieser Algorithmus. Das Verhalten dieser Komplexität im Grenzfall mit zunehmender Problemgröße wird aufgerufen asymptotische Zeitkomplexität
.
Ebenso können wir definieren kapazitive Komplexität und asymptotisch-kapazitive Komplexität. Es ist die asymptotische Komplexität des Algorithmus, die letztendlich die Größe der Probleme bestimmt, die mit diesem Algorithmus gelöst werden können. Wenn ein Algorithmus Eingaben der Größe n in der Zeit cÿn 2 verarbeitet, wobei c -
eine Konstante, dann sagen wir, dass die zeitliche Komplexität dieses Algorithmus O(n 2) ist (sprich „von Ordnung und Quadrat“). Man könnte meinen, dass die enorme Steigerung der Rechengeschwindigkeit durch die aktuelle Generation digitaler Rechenmaschinen die Bedeutung effizienter Algorithmen verringern würde. Es passiert jedoch das Gegenteil. Da Rechenmaschinen immer schneller werden und wir größere Probleme lösen können, ist es die Komplexität des Algorithmus, die die Vergrößerung der Problemgröße bestimmt, die mit zunehmender Maschinengeschwindigkeit erreicht werden kann. Nehmen wir an, wir haben fünf Algorithmen A1,A2,…,A5 mit den folgenden Zeitkomplexitäten: Zeitkomplexität ist hier die Anzahl der Zeiteinheiten, die erforderlich sind, um eine Eingabe der Größe n zu verarbeiten. Die Zeiteinheit sei eine Millisekunde (1 Sekunde = 1000 Millisekunden). Dann kann Algorithmus A1 eine Eingabe der Größe 1000 in einer Sekunde verarbeiten, während A5 eine Eingabe der Größe nicht mehr als 9 verarbeiten kann. In der Tabelle. 6.5.1. Es werden die Größen der Probleme angegeben, die mit jedem dieser fünf Algorithmen in einer Sekunde, einer Minute und einer Stunde gelöst werden können. Tabelle 6.5.3. Nehmen wir an, dass die nächste Computergeneration zehnmal schneller sein wird als die aktuelle. In Tabelle 6.5.2. zeigt, wie die Größe der Probleme, die wir aufgrund dieser Geschwindigkeitssteigerung lösen können, zunimmt. Beachten Sie, dass bei Algorithmus A5 eine Verzehnfachung der Geschwindigkeit die Größe des lösbaren Problems um nur drei Einheiten erhöht (siehe letzte Zeile in Tabelle 6.5.2.), während sich bei Algorithmus A3 die Größe des Problems um mehr als das Dreifache erhöht . Tabelle 6.5.4. Betrachten wir nun anstelle des Effekts einer höheren Geschwindigkeit den Effekt der Verwendung eines effizienteren Algorithmus. Kehren wir zu Tabelle 6.5.1 zurück. Wenn wir 1 Minute als Vergleichsbasis nehmen, können wir durch Ersetzen des Algorithmus A4 durch den Algorithmus A3 ein sechsmal größeres Problem lösen und durch Ersetzen von A4 durch A2 ,
Sie können ein 125-mal größeres Problem lösen. Diese Ergebnisse sind weitaus beeindruckender als die zweifache Verbesserung, die durch die zehnfache Geschwindigkeit erreicht wird. Nimmt man 1 Stunde als Vergleichsbasis, fällt der Unterschied noch deutlicher aus. Daraus schließen wir, dass die asymptotische Komplexität eines Algorithmus ein wichtiges Maß für die Qualität des Algorithmus ist und mit zunehmender Rechengeschwindigkeit noch wichtiger zu werden verspricht. Obwohl hier das Hauptaugenmerk auf die Wachstumsordnung der Mengen gelegt wird, muss man verstehen, dass eine große Wachstumsordnung in der Komplexität des Algorithmus eine kleinere multiplikative Konstante (Konstante) haben kann C in der Definition von O(f(x))), als eine geringfügige Steigerung der Komplexität eines anderen Algorithmus. In diesem Fall kann ein Algorithmus mit schnell zunehmender Komplexität für kleine Probleme – vielleicht sogar für alle Probleme, die uns interessieren – vorzuziehen sein. Nehmen wir beispielsweise an, dass die Zeitkomplexitäten der Algorithmen A1, A2, A3, A4, A5 tatsächlich 1000n, 100nÿlog(n), 10n2, n3 bzw. 2 betragen. n Dann eignet sich A5 am besten für Probleme der Größe 2§n§9, A2 – für Probleme der Größe 10§n§58, A1 – bei 59§n§1024 und A1- mit n>1024.- 1. F. A. Novikov. Diskrete Mathematik für Programmierer./ St. Petersburg: Peter, 2001, 304С. 2. S. V. Sudoplatov, E. V. Ovchinnikova. Elemente der diskreten Mathematik./ M., INFRA-M, Nowosibirsk, NSTU-Verlag, 3. Y.M.Erusalimsky. Diskrete Mathematik / M., „Universitätsbuch“, 2001, 279 S. 4. A. Aho, J. Hopcroft, J. Ullman. Konstruktion und Analyse von Rechenalgorithmen. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Kurs in diskreter Mathematik./ M., MAI Publishing House, 1992, 264S.§4.3. Quantoren und ihre Eigenschaften.
Kapitel V. Formale Theorien.
§5.1. Definition der formalen Theorie.
§5.2. Aussagenkalkül.
§5.3. Abzugssatz. Vollständigkeit von IV.
§5.4. Automatischer Beweis von Theoremen.
§5.5. Auflösungsmethode im IW.
Kapitel VI. Elemente der Algorithmentheorie.
§6.1. Algorithmusdefinition.
§6.2. Turing Maschine.
q 0
…
q ich
…
q m
…
ein u
Q
S
A
rS
…
§6.3. Rekursive Funktionen
§6.4. Algorithmisch unlösbare Probleme.
§6.5. Algorithmen und ihre Komplexität.
LITERATUR.
