Artikel

1.2: Aussagen und Logik - Mathematik


Logik ist im Grunde das Studium der gültigen Argumentation. Nachdem wir diese Form der Logik untersucht haben, werden wir uns logische Argumente ansehen und wie wir die Gültigkeit einer Behauptung bestimmen können.

Boolesche Logik

Wir können Gegenstände oft als zu Sets gehörend klassifizieren. Wenn Sie in die Bibliothek gehen, um nach einem Buch zu suchen, und sie Sie bitten, Ihre Suche mit Vereinigungen, Schnittmengen und Ergänzungen von Mengen auszudrücken, würde sich das ein wenig seltsam anfühlen. Stattdessen verwenden wir normalerweise Wörter wie „und“, „oder“ und „nicht“, um unsere Keywords zu einer Suche zu verbinden. Diese Wörter, die die Grundlage der Booleschen Logik bilden, stehen in direktem Zusammenhang mit unseren Mengenoperationen. (Die boolesche Logik wurde vom englischen Mathematiker George Boole aus dem 19. Jahrhundert entwickelt.)

Boolesche Logik

Die boolesche Logik kombiniert mehrere Aussagen, die entweder wahr oder falsch sind, zu einem Ausdruck, der entweder wahr oder falsch ist.

In Verbindung mit Mengen ist eine Suche wahr, wenn das Element Teil der Menge ist.

Angenommen, M ist die Menge aller Mystery-Bücher und C ist die Menge aller Comedy-Bücher. Wenn wir nach „Geheimnis“ suchen, suchen wir nach allen Büchern, die ein Element der Menge M sind; die Suche gilt für Bücher, die sich im Set befinden.

Wenn wir nach „Mystery und Comedy“ suchen, suchen wir ein Buch, das ein Element beider Sets ist, in der Schnittmenge. Wenn wir nach „Mystery oder Comedy“ suchen, suchen wir nach einem Buch, das ein Mysterium, eine Komödie oder beides ist, das die Vereinigung der Sets darstellt. Wenn wir nach „keine Komödie“ gesucht haben, suchen wir in der Bibliothek nach jedem Buch, das keine Komödie ist, die Ergänzung des Sets C.

Verbindung zu Set-Operationen

A- und B-Elemente im Schnittpunkt A ⋂ B

A- oder B-Elemente in der Vereinigung A ⋃ B

keine A-Elemente im Komplement Ac

Beachten Sie hier, dass oder ist nicht exklusiv. Dies ist ein Unterschied zwischen dem booleschen logischen Gebrauch des Wortes und dem alltäglichen Gebrauch. Wenn Ihr Lebensgefährte fragt: "Wollen Sie in den Park oder ins Kino gehen?" sie schlagen normalerweise eine ausschließliche Wahl vor – die eine oder die andere, aber nicht beides. In der Booleschen Logik ist der oder ist nicht exklusiv – eher wie in einem Restaurant gefragt „Möchtest du Pommes?“ oder ein Getränk dazu?" Die Antwort „beides, bitte“ ist eine akzeptable Antwort.

Beispiel (PageIndex{1})

Angenommen, wir durchsuchen eine Bibliotheksdatenbank nach mexikanischen Universitäten. Drücken Sie eine vernünftige Suche mit boolescher Logik aus.

Lösung

Wir könnten mit der Suche „Mexiko und Universität“ beginnen, würden aber wahrscheinlich Ergebnisse für den US-Bundesstaat New Mexico finden. Um dies zu berücksichtigen, könnten wir unsere Suche so überarbeiten, dass sie lautet:

Mexiko und Universität nicht "New-Mexiko"

In den meisten Internetsuchmaschinen ist es nicht erforderlich, das Wort aufzunehmen und; Die Suchmaschine geht davon aus, dass Sie nach beiden suchen, wenn Sie zwei Schlüsselwörter angeben. In der Google-Suche ist das Stichwort oder wird als ODER großgeschrieben, und ein negatives Vorzeichen vor einem Wort wird verwendet, um anzuzeigen nicht. Anführungszeichen um eine Phrase weisen darauf hin, dass nach der gesamten Phrase gesucht werden sollte. Die Suche aus dem vorherigen Beispiel bei Google könnte so geschrieben werden:

Mexiko-Universität - „New Mexico“

Beispiel (PageIndex{2})

Beschreiben Sie die Zahlen, die die Bedingung erfüllen: gerade und kleiner als 10 und größer als 0

Lösung

Die Zahlen, die alle drei Anforderungen erfüllen, sind {2, 4, 6, 8}

Manchmal können Aussagen auf Englisch mehrdeutig sein. Aus diesem Grund verwendet die Boolesche Logik Klammern, um Präzedenzfälle anzuzeigen, genau wie in der algebraischen Reihenfolge der Operationen.

Beispiel (PageIndex{3})

Beschreiben Sie die Zahlen, die die Bedingung erfüllen: ungerade Zahl und kleiner als 20 und größer als 0 und (Vielfaches von 3 oder Vielfaches von 5)

Lösung

Die ersten drei Bedingungen beschränken uns auf die Menge {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}

Die letzten gruppierten Bedingungen sagen uns, Elemente dieser Menge zu finden, die ebenfalls entweder ein Vielfaches von 3 oder ein Vielfaches von 5 sind. Damit bleibt die Menge {3, 5, 9, 15}

Beachten Sie, dass wir ein ganz anderes Ergebnis erhalten hätten, wenn wir geschrieben hätten (ungerade Zahl und kleiner als 20 und größer als 0 und Vielfaches von 3) oder Vielfaches von 5 of

Der erste gruppierte Satz von Bedingungen würde {3, 9, 15} ergeben. In Kombination mit der letzten Bedingung erweitert sich dieses Set jedoch ohne Grenzen:

{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, …}

Beispiel (PageIndex{4})

Der englische Satz „Geh in den Laden und kauf mir Eier und Bagels oder Müsli“ ist mehrdeutig; Es ist nicht klar, ob die Anforderer Eier immer zusammen mit Bagels oder Müsli verlangen oder ob sie entweder die Kombination von Eiern und Bagels oder nur Müsli verlangen.

Lösung

Aus diesem Grund verdeutlicht die Verwendung von Klammern die Absicht:

Eier und (Bagels oder Getreide) bedeutet Option 1: Eier und Bagels, Option 2: Eier und Getreide

(Eier und Bagels) oder Getreide bedeutet Option 1: Eier und Bagels, Option 2: Getreide

Beachten Sie, dass eine Bedingungskette ohne Gruppierungssymbole oft von links nach rechts interpretiert wird, was zu letzterer Interpretation führt.

Bedingte Anweisungen

Neben der Suche wird Boolesche Logik häufig in Tabellenkalkulationsanwendungen wie Excel verwendet, um bedingte Berechnungen durchzuführen. Eine Aussage ist etwas, das entweder wahr oder falsch ist. Eine Aussage wie 3 < 5 ist wahr; eine Aussage wie „eine Ratte ist ein Fisch“ ist falsch. Eine Aussage wie „x < 5“ ist für einige Werte von x wahr und für andere falsch. Wenn eine Aktion oder ein Ergebnis vom Wert einer Aussage abhängt, bildet sie eine Bedingung.

Anweisungen und Bedingungen

Eine Aussage ist entweder wahr oder falsch. Eine Bedingung ist eine zusammengesetzte Anweisung der Form „wenn p dann q“ oder „wenn p dann q, sonst s“.

Beispiel (PageIndex{5})

Im allgemeinen Sprachgebrauch wäre ein Beispiel für eine bedingte Aussage „Wenn es regnet, dann gehen wir ins Einkaufszentrum. Sonst machen wir eine Wanderung.“

Lösung

Die Aussage „Wenn es regnet“ ist die Bedingung – dies kann für einen bestimmten Tag wahr oder falsch sein. Wenn die Bedingung zutrifft, folgen wir der ersten Vorgehensweise und gehen zum Einkaufszentrum. Wenn die Bedingung falsch ist, verwenden wir die Alternative und gehen eine Wanderung.

Beispiel (PageIndex{6})

Wie bereits erwähnt, werden bedingte Anweisungen häufig in Tabellenkalkulationsanwendungen wie Excel oder Google Sheets verwendet.

In Excel können Sie einen Ausdruck wie =IF(A1<2000, A1+1, A1*2) eingeben.

Lösung

Beachten Sie, dass es nach dem IF drei Teile gibt. Der erste Teil ist die Bedingung, und die zweiten beiden sind Berechnungen. Excel betrachtet den Wert in Zelle A1 und vergleicht ihn mit 2000. Wenn diese Bedingung wahr ist, wird die erste Berechnung verwendet, und 1 wird zum Wert von A1 addiert und das Ergebnis wird gespeichert. Wenn die Bedingung falsch ist, wird die zweite Berechnung verwendet, und A1 wird mit 2 multipliziert und das Ergebnis wird gespeichert.

Mit anderen Worten, diese Aussage entspricht der Aussage „Wenn der Wert von A1 kleiner als 2000 ist, dann addiere 1 zum Wert in A1. Andernfalls multiplizieren Sie A1 mit 2".

Beispiel (PageIndex{7})

Der Ausdruck =IF(A1>5, 2*A1, 3*A1) wird verwendet. Finden Sie das Ergebnis, wenn A1 3 ist, und das Ergebnis, wenn A1 8 ist.

Lösung

Dies ist äquivalent zu sagen

Wenn A1 > 5, dann berechne 2*A1. Berechnen Sie andernfalls 3*A1

Wenn A1 3 ist, dann ist die Bedingung falsch, da 3 > 5 nicht wahr ist, also führen wir die alternative Aktion aus und multiplizieren mit 3, was 3*3 = 9 . ergibt

Wenn A1 8 ist, dann ist die Bedingung wahr, da 8 > 5, also multiplizieren wir den Wert mit 2, was 2*8=16 . ergibt

Beispiel (PageIndex{8})

Ein Buchhalter muss 15% des Einkommens für Steuern einbehalten, wenn das Einkommen unter 30.000 USD liegt, und 20% des Einkommens, wenn das Einkommen 30.000 USD oder mehr beträgt. Schreiben Sie einen Ausdruck, der den einzubehaltenden Betrag berechnet.

Lösung

Unsere Bedingung muss den Wert mit 30.000 vergleichen. Wenn das Einkommen weniger als 30.000 beträgt, müssen wir 15% des Einkommens berechnen: 0,15 * Einkommen. Wenn das Einkommen mehr als 30.000 beträgt, müssen wir 20% des Einkommens berechnen: 0,20 * Einkommen.

In Worten könnten wir schreiben „Wenn Einkommen < 30.000, dann multipliziere mit 0,15, sonst multipliziere mit 0,20“. In Excel würden wir schreiben:

=WENN(A1<30000, 0,15*A1, 0,20*A1)

Wie zuvor können wir komplexere Bedingungen erstellen, indem wir die Operatoren verwenden und, oder, und nicht einfachere Bedingungen zusammenzufügen.

Beispiel (PageIndex{9})

Ein Elternteil könnte zu seinem Kind sagen: „Wenn Sie Ihr Zimmer aufräumen und den Müll rausbringen, können Sie Eis essen.“

Hier gibt es zwei einfachere Bedingungen:

1) Das Kind putzt sein Zimmer

2) Das Kind bringt den Müll raus

Lösung

Da diese Bedingungen verbunden wurden mit und, ist die kombinierte Bedingung nur wahr, wenn beide einfacheren Bedingungen wahr sind; Wenn eine der Aufgaben nicht erledigt ist, ist die Bedingung der Eltern nicht erfüllt.

Beachten Sie, dass, wenn die Eltern gesagt hätten: „Wenn Sie Ihr Zimmer aufräumen oder den Müll rausbringen, können Sie Eis essen“, dann müsste das Kind nur eine Aufgabe erledigen, um die Bedingung zu erfüllen.

Angenommen, Sie möchten, dass etwas passiert, wenn ein bestimmter Wert zwischen 100 und 300 liegt. Um die Bedingung „A1 < 300 und A1 > 100“ in Excel zu erstellen, müssen Sie „AND(A1<300, A1>100)“ eingeben. . Ebenso würden Sie für die Bedingung „A1=4 oder A1=6“ „OR(A1=4, A1=6)“ eingeben.

Beispiel (PageIndex{10})

In einer Tabelle enthält Zelle A1 das Jahreseinkommen und A2 enthält die Anzahl der abhängigen Personen.

Eine bestimmte Steuergutschrift gilt, wenn jemand ohne Angehörige weniger als 10.000 US-Dollar verdient oder wenn jemand mit Familienangehörigen weniger als 20.000 US-Dollar verdient. Schreiben Sie eine Regel, die dies beschreibt.

Lösung

Es gibt zwei Möglichkeiten, die Regel zu erfüllen:

das Einkommen weniger als 10.000 beträgt und die unterhaltsberechtigten Personen 0 sind, oder

das Einkommen weniger als 20.000 beträgt und die Unterhaltsberechtigten nicht 0 sind.

Informell könnten wir diese schreiben als

(A1 < 10000 und A2 = 0) oder (A1 < 20000 und A2 > 0)

Im Excel-Format würden wir schreiben

WENN(ODER(AND(A1<10000, A2=0), AND(A1<20000, A2>0)), „Sie qualifizieren sich“, „Sie qualifizieren sich nicht“)

Quantifizierte Aussagen

Wörter, die eine ganze Menge beschreiben, wie „alle“, „alle“ oder „keiner“, werden als universelle Quantoren bezeichnet, weil diese Menge als universelle Menge angesehen werden könnte. Im Gegensatz dazu werden Wörter oder Phrasen wie „einige“, „eins“ oder „mindestens einer“ als existenzielle Quantoren bezeichnet, weil sie die Existenz mindestens eines Elements in einer Menge beschreiben.

Quantifizierer

EIN universeller Quantor besagt, dass eine ganze Reihe von Dingen ein Merkmal gemeinsam haben.

Ein existenzieller Quantor besagt, dass eine Menge mindestens ein Element enthält.

Etwas Interessantes passiert, wenn wir eine quantifizierte Aussage negieren oder das Gegenteil behaupten.

Beispiel (PageIndex{11})

Angenommen, Ihr Freund sagt: „Jeder betrügt seine Steuern“. Was ist die Mindestmenge an Beweisen, die Sie benötigen, um Ihrem Freund das Gegenteil zu beweisen?

Lösung

Um zu zeigen, dass es nicht stimmt, dass jeder seine Steuern betrügt, braucht es nur eine Person, die seine Steuern nicht betrügt. Es wäre völlig in Ordnung, mehr Leute zu produzieren, die nicht betrügen, aber ein Gegenbeispiel ist alles, was Sie brauchen.

Es ist wichtig zu beachten, dass Sie nicht nachweisen müssen, dass absolut niemand seine Steuern betrügt.

Beispiel (PageIndex{12})

Angenommen, Ihr Freund sagt: „Einer dieser sechs Kartons Milch läuft aus.“ Was ist die Mindestmenge an Beweisen, die Sie benötigen, um Ihrem Freund das Gegenteil zu beweisen?

Lösung

In diesem Fall müssten Sie alle sechs Kartons überprüfen und nachweisen, dass keiner von ihnen undicht ist. Sie können die Aussage Ihres Freundes nicht widerlegen, indem Sie nur einen der Kartons überprüfen.

Wenn wir eine Aussage mit einem universellen Quantor negieren, erhalten wir eine Aussage mit einem existenziellen Quantor und umgekehrt.

Eine quantifizierte Aussage verneinen

Die Negation von „alle A sind B“ lautet „mindestens ein A ist nicht B“.

Die Negation von „kein A ist B“ lautet „mindestens ein A ist B“.

Die Negation von „mindestens ein A ist B“ lautet „kein A ist B“.

Die Negation von „mindestens ein A ist nicht B“ lautet „alle A sind B“.

Beispiel (PageIndex{13})

"Jemand hat eine Taschenlampe mitgebracht." Schreiben Sie die Negation dieser Aussage.

Lösung

Die Verneinung lautet: „Niemand hat eine Taschenlampe mitgebracht“.

Beispiel (PageIndex{14})

"Es gibt keine geraden Primzahlen." Schreiben Sie die Negation dieser Aussage.

Lösung

Die Negation lautet „Mindestens eine Primzahl ist gerade“.

Jetzt ausprobieren 1

  1. Schreiben Sie die Verneinung von „Alle isländischen Kinder lernen Englisch in der Schule“.

Aussagenlogik und Logik erster Ordnung.

Wie lautet die korrekte Übersetzung der folgenden Aussage in die mathematische Logik? „Einige reelle Zahlen sind rational“

=> Diese Aussage kann ausgedrückt werden als => Für alle X kann x entweder Gold oder Silber sein, dann ist das Ornament X kostbar => Für alle X, (G(X) v S(x)) => P(X) .

Diese Lösung wird beigesteuert von Anil Saikrishna Devarsetty .

Seien fsa und pda zwei Prädikate, so dass fsa(x) bedeutet, dass x ein endlicher Automat ist und pda(y) bedeutet, dass y ein Kellerautomat ist. Sei äquivalent ein anderes Prädikat, so dass äquivalent (a, b) bedeutet, dass a und b äquivalent sind. Welche der folgenden logischen Anweisungen erster Ordnung stellt Folgendes dar: Jeder endliche Automat hat einen äquivalenten Kellerautomaten.

Betrachten Sie jede Option:
(A) Wenn alles ein FSA ist, dann gibt es für alles einen gleichwertigen PDA.
(B) Es ist nicht der Fall, dass für alle y, wenn es eine FSA gibt, diese einen gleichwertigen PDA hat.
(C) Alles ist ein FSA und hat einen gleichwertigen PDA.
(D) Alles ist ein PDA und es existiert ein gleichwertiger FSA.
Somit ist Option (A) richtig.

Bitte kommentieren Sie unten, wenn Sie im obigen Beitrag etwas falsch finden.

I und II sind nach Demorgans Gesetz gleich Das III. kann zu I vereinfacht werden. schon seit stimmt immer

1.2: Aussagen und Logik - Mathematik

am 29. Mai 2018 um 09:54 Uhr

Definition 1 Eine Aussage, die entweder wahr oder falsch ist, heißt a Vorschlag

Nicht alle Sätze sind Aussagen. Fragen, Ausrufe, Befehle oder in sich widersprüchliche Sätze wie die folgenden Beispiele können weder behauptet noch geleugnet werden.

  • Ist Mathematik Logik?
  • Sie da!
  • Keine Panik
  • Dieser Satz ist falsch
  • Es ist ein Dreieck
  • x + 1 = 2
  • x + y = z
    Die folgenden Sätze sind Aussagen
  1. Washington, D.C., ist die Hauptstadt der Vereinigten Staaten von Amerika
  2. Toronto ist die Hauptstadt Kanadas
  3. 1 + 1 = 2
  4. 2 + 2 = 3

Aussagen 1 und 3 sind wahr, während 2 und 4 falsch sind.

Definition 2 Sei (p) ein Satz. Die Negation von (p), bezeichnet mit ( eg p) (auch bezeichnet mit (overline

)), ist die Aussage "Es ist nicht so, dass (p)". Der Satz ( eg p) lautet "nicht (p)". Der Wahrheitswert der Negation (p), ( eg p), ist das Gegenteil des Wahrheitswerts von (p).

Beispiel 1
Finden Sie die Negation des Satzes ( ext<"Michaels PC läuft unter Linux">) und drücken Sie dies in einfachem Englisch aus.
Lösung
Die Negation ist ( ext<"Es ist nicht der Fall, dass Michaels PC Linux läuft">). Diese Verneinung kann einfacher ausgedrückt werden als ( ext<"Michaels PC läuft nicht unter Linux">).

Die Wahrheitstafel für die Negation eines Satzes.

Definition 3 Seien (p) und (q) Sätze. Die Konjunktion von (p) und (q), bezeichnet mit (pland q), ist der Satz "(p) und (q)". Die Konjunktion von (p) und (q) ist wahr, wenn sowohl (p) als auch (q) wahr sind, andernfalls ist sie falsch.

Beispiel 3
Finden Sie die Konjunktion der Sätze (p) und (q), wobei (p) der Satz ist ( ext<"Rebeccas PC hat mehr als 16GB freien Festplattenspeicher">) und (q ) ist der Satz ( ext<"Der Prozessor in Rebeccas PC läuft schneller als 1GHz">).
Lösung
Die Konjunktion dieser Präpositionen, (p land q), ist die Präposition ( ext<"Rebeccas PC hat mehr als 16 GB freien Festplattenspeicher, und der Prozessor in Rebeccas PC läuft schneller als 1 GHz">). Diese Konjunktion kann einfacher ausgedrückt werden als ( ext<"Rebeccas PC hat mehr als 1 GB freien Festplattenspeicher und sein Prozessor läuft schneller als 1 GHz">). Damit diese Konjunktion wahr ist, müssen beide gegebenen Bedingungen wahr sein. Es ist falsch, wenn eine oder beide dieser Bedingungen falsch sind.

Die Wahrheitstafel für die Konjunktion zweier Aussagen.

Definition 4 Seien (p) und (q) Sätze. Die Disjunktion von (p) und (q), bezeichnet mit (plorq), ist der Satz "p oder q". Die Disjunktion von (plorq) ist falsch, wenn sowohl (p) als auch (q) falsch sind, andernfalls ist sie wahr.

Beispiel 4
Wie lautet die Disjunktion der Sätze (p) und (q), wobei (p) und (q) dieselben Sätze wie in Beispiel 3 sind?
Lösung
Die Disjunktion von (p) und (q), (plor q), ist der Satz ( ext<"Rebeccas PC hat mindestens 16GB freien Festplattenspeicher, oder der Prozessor in Rebeccas PC läuft schneller als 1 GHz">).

Die Wahrheitstafel für die Disjunktion zweier Aussagen.

Definition 5 Seien (p) und (q) Sätze. Das exklusive Oder von (p) und (q), bezeichnet mit (poplus q), ist der Satz, der wahr ist, wenn genau eines von (p) und (q) wahr ist und ist ansonsten falsch.

Die Wahrheitstafel für das exklusive Oder von zwei Aussagen.

Definition 6 Seien (p) und (q) Sätze. Die bedingte Aussage (pimplies q) ist der Satz "wenn (p), dann (q)". Die bedingte Aussage (pimplies q) ist falsch, wenn (p) wahr und (q) falsch ist, andernfalls wahr. In der bedingten Aussage (pimplies q) heißt (p) Hypothese (oder Vorsatz oder Prämisse) und (q) heißt Schlussfolgerung (oder Folge).

Beispiel 5
Sei (p) die Aussage ( ext<"Maria lernt diskrete Mathematik">) und (q) die Aussage ( ext<"Maria findet einen guten Job">). Drücken Sie die Aussage (p implies q) als eine Aussage im Englischen aus.
Lösung
(p ​​implies q) steht für die Aussage ( ext<"wenn Maria diskrete Mathematik lernt, dann findet sie einen guten Job">).

Die Wahrheitstabelle für die bedingte Aussage von zwei Präpositionen.

Gegeben eine bedingte Aussage "wenn (p) , dann (q)", können wir drei verwandte Aussagen erstellen
1. Umkehrung: Der Satz von (qimplies p) heißt die Umkehrung von (pimplies q)
2. Kontrapositiv: Der Satz von ( eg q implies eg p) heißt Kontrapositiv von (p implies q)
3. Inverse: Der Satz von ( eg p implies eg q) heißt die Umkehrung von (p implies q)

Beispiel 6
Was sind die Umkehrungen, die Gegensätze und die Umkehrungen der bedingten Aussage ( ext<"Die Heimmannschaft gewinnt, wenn es regnet">)?
Lösung
Da "q wann immer p" eine der Möglichkeiten ist, die bedingte Aussage (p implies q) auszudrücken, kann die ursprüngliche Aussage in ( ext<"Wenn es regnet, dann gewinnt die Heimmannschaft">) umgeschrieben werden. . Das Gegenteil dieser bedingten Aussage ist ( ext<"Wenn die Heimmannschaft nicht gewinnt, dann regnet es nicht">). Das Gegenteil ist ( ext<"Wenn die Heimmannschaft gewinnt, dann regnet es">). Das Gegenteil ist ( ext<"Wenn es nicht regnet, dann gewinnt die Heimmannschaft nicht">).

Die Wahrheitstafel für das Konverse, das Kontrapositiv und das Inverse der bedingten Aussage zweier Aussagen

(p) (q) ( eg p) ( eg q) (p ​​impliziert q) (q impliziert p) ( eg q impliziert eg p) ( eg p impliziert eg q)
T T F F T T T T
F T T F T F T F
T F F T F T F T
F F T T T T T T

Definition 7 Seien (p) und (q) Sätze. Die bibedingte Aussage (p iff q) ist der Satz "(p) genau dann, wenn (q)". Die bibedingte Aussage (piff q) ist wahr, wenn (p) und (q) dieselben Wahrheitswerte haben, andernfalls ist sie falsch. Bibedingte Aussagen werden auch Biimplikationen genannt.

Beispiel 7
Sei (p) die Aussage ( ext<"Sie können den Flug nehmen">) und sei (q) die Aussage ( ext<"Sie kaufen ein Ticket">). Dann ist (p iff q) die Aussage ( ext<"Sie können den Flug nur dann nehmen, wenn Sie ein Ticket kaufen">).


Von Rittern und Knappen

Lewis Carroll (alias Charles
Lutwidge Dodgson, 1832 – 1898)

Logik- und Wahrheitstabellen können verwendet werden, um eine Vielzahl von Rätselproblemen zu lösen, von denen viele von dem Autor von Alice im Wunderland, Lewis Carroll (1832 – 1898), erfunden wurden.

Ein schiffbrüchiger Seemann kommt auf einer mysteriösen Insel an, die von Rittern bewohnt wird, die immer die Wahrheit sagen, und Schurken, die immer lügen. Beim Versuch, nach Hause zu kommen, klopft er an die Tür einer der Hütten. Der Inselbewohner, der die Tür öffnet, sagt, dass er und seine Frau beide Schurken sind. Wen sollte der Seemann fragen, um den richtigen Weg nach Hause zu finden?

Dieses Problem ist mit Hilfe von Logik- und Wahrheitstabellen leicht zu lösen. Seien H und W zwei Sätze, die wahr sind, wenn der Mann bzw. die Frau Ritter sind, und falsch, wenn sie Schurken sind.

Der Ehemann sagte, dass sowohl er als auch seine Frau Schurken sind, d.h. dass ¬H &und ¬W . Wenn er ein Ritter ist, ist dieser Satz wahr, und wenn er ein Schurke ist, ist er falsch. Insbesondere wissen wir, dass H &equiv (¬H &and ¬W) wahr sein muss.

Wir können eine Wahrheitstabelle zeichnen, um den Wert dieser Aussage in Abhängigkeit von den möglichen Werten von H und W zu bestimmen:

Die einzige Reihe, in der H &equiv (¬H &and ¬W) wahr ist, ist die zweite Reihe, in der der Ehemann ein Schurke und die Frau ein Ritter ist. Deshalb sollte der Matrose die Frau nach dem Weg nach Hause fragen.


Warum ist ein Rabe wie ein Schreibtisch?

Sie hätten das obige Knights and Knaves-Rätsel leicht lösen können, ohne eine ganze Wahrheitstabelle zu erstellen, aber vielleicht nicht so viel komplexeres Problem:

Der Seemann trifft drei verschiedene Inselbewohner, die wir einfach A, B und C nennen. Inselbewohner A behauptet, B und C seien Ritter, und B sagt, A sei ein Schurke und C sei ein Ritter. Wer sagt die Wahrheit?

Da wir eine zusätzliche Person haben, gibt es doppelt so viele Zeilen in der Wahrheitstabelle, aber die Prinzipien bleiben gleich. In diesem Beispiel müssen wir die Zeile finden, in der (A &equiv (B &and C)) &and (B &equiv (¬A &and C)) wahr ist. Können Sie herausfinden, wie dieser Satz dem ursprünglichen Problem entspricht?

Die einzig mögliche Lösung ist, wenn A, B und C alle Schurken sind. Leider gibt es niemanden, dem der Segler vertrauen kann&hellip

Ihr Browser unterstützt kein HTML-Video.

& Kopie 1986 Jim Henson Productions, Lucasfilm, TriStar Pictures (Fair Use Policy)


Extreme Mathematik: 1 + 1 = 2

Endlich habe ich online eine Kopie des großartigen Höhepunkts des ehrgeizigsten Mathematikwerks des 20. Jahrhunderts gefunden. Die letzte Seite des Beweises von Russel und Whitehead, dass 1+1=2 ist. Auf Seite 378 (ja, dreihundertachtundsiebzig!) der Principia Mathematica.. Ja, es ist da. Das Ganze: die gesamte Principia in all ihrer scheußlichen Pracht, gescannt und für uns alle verfügbar gemacht, um sie völlig unverständlich zu machen.

Für diejenigen, die das Glück haben, dies nicht zu wissen, war die Principia im Grunde ein Versuch, die perfekte Mathematik zu schaffen: eine vollständige Formalisierung aller mathematischen Dinge, in der alle wahren Aussagen nachweisbar wahr sind, alle falschen Aussagen nachweislich falsch sind, und es können keine paradoxen Aussagen geschrieben, geschweige denn bewiesen werden.

Zu Beginn des 20. Jahrhunderts gab es viele Bedenken über das Paradox. Mengentheoretiker waren auf seltsame Dinge gestoßen - Dinge wie die schreckliche Menge aller Mengen, die sich selbst nicht enthalten. (Wenn es sich selbst enthält, dann enthält es sich nicht, aber wenn es sich nicht enthält, dann enthält es sich selbst. Und dann müssen wirklich schlechte Schauspieler so tun, als wären sie Roboter, die kurzschließen, während Leonard Nimoy selbstgefällig zuschaut.)

Also taten sich einige wirklich kluge Typen namens Bertrand Russell und Alfred North Whitehead zusammen und verbrachten Jahre ihres Lebens damit, herauszufinden, wie man Mathe machen kann, ohne schlechte Schauspieler einzubeziehen. 378 Seiten später hatten sie es geschafft zu beweisen, dass 1+1=2. Fast.

Eigentlich waren sie noch nicht da. Nach 378 Seiten konnten sie sprich darüber wie Sie beweisen können, dass 1+1=2 ist. Aber sie konnten es noch nicht wirklich tun, weil sie es noch nicht geschafft hatten, Addition zu definieren.

Und dann kam dieser widerliche Kerl namens Kurt Gödel, der zeigte, dass das alles eine große Zeitverschwendung war. An diesem Punkt gehe ich davon aus, dass Russell und Whitehead losgingen und ihre Gehirne explodierten, ziemlich genau so, wie es die schlechten Schauspieler später vorgeben würden.

Mehr wie das

Ein unterhaltsamer Beitrag. Aber vielleicht die Principia war nicht ganz so sinnlos wie du vermutest.

Wow, ich glaube, das hatte ich noch nie zuvor gesehen. Metal Machine Musik für Mathefreaks. Natürlich ist die maschinelle Beweisverifikation heutzutage ein Nebengewerbe und führt (meiner Meinung nach) zu einer größeren Wahrheitssicherheit der Aussagen, deren Beweise so verifiziert werden können, zum Beispiel wäre es von großem Interesse, eine solche Verifikation von Beweisen zu haben die Klassifikation endlicher einfacher Gruppen zum Beispiel, daher denke ich, dass es etwas übertrieben ist, zu sagen, dass alles Zeitverschwendung war.

Ratten. Ich wollte einen Nitpick posten, dass der Name nicht Gödel, sondern Gödel ist. Doch dann stellt sich heraus, dass der entscheidende zweite Buchstabe seines Namens in der Vorschau durch ein Fragezeichen ersetzt wird. Wahrscheinlich ein Fehler in der Blogging-Software. Oh, aber warte! Es funktioniert sofort, wenn ich es erneut aus der Vorschau versuche! Wie sehr seltsam.

Könnten Sie bitte auf ein Bild mit besserer Auflösung verlinken - der Text ist unleserlich.

Ich würde den letzten Absatz als umformulieren.


An diesem Punkt nehme ich an, dass Russell, Whitehead UND ALLE IHRE WELTWEITEN MATHEMATISCHEN WELTWEITEN losgingen und ihre Gehirne explodierten, ziemlich genau so, wie es die schlechten Schauspieler später vorgeben würden
.

Über Gödels Vermutung empfehle ich diesen Roman.

Korrektur: Gödels schöne Mathematik ist ein Theorem, keine Vermutung.

Ist 1 + 1 = 2 also nur eine Näherung?

Ich nehme an, du bist kein großer Fan von Zahlentheorie, der Liebe meines verzerrten Lebens? *Grinsen*

Mein Lieblingsteil dieser Geschichte ist, dass Mrs. Whitehead Russell, den ungepflegten, freidenkenden Sozialisten, anscheinend missbilligte und es nicht dulden würde, ihn bei sich zu haben. Also wurde die Principia in Whiteheads Küche geschrieben, wo sich die beiden treffen würden, nachdem Mrs. Whitehead ins Bett gegangen war.

Natürlich machten beide Männer danach noch viele weitere lohnende Dinge, also keine explodierenden Gehirne, denke ich.

(Jetzt kann ich nicht mehr ausgraben, wo ich diese Geschichte zum ersten Mal gelesen habe, aber sie ist mir seit Jahren im Gedächtnis geblieben)

Ich habe wirklich großen Respekt vor Russell und Whitehead. Ich meinte es sehr ernst, als ich sagte, die principia sei das ehrgeizigste Werk der Mathematik des 20. Jahrhunderts. Sie machten sich ernsthaft daran, ein ernstes Problem zu lösen, und sie gingen erstaunlich intensiv und schwierig vor, um zu versuchen, das Problem ein für alle Mal zu lösen.

Es ist nicht ihre Schuld, dass das, woran sie arbeiteten, eigentlich unmöglich war. Niemand ahnte, dass die Bemühungen zum Scheitern verurteilt waren.

Und man kann noch viel von den Methoden der principia lernen. Es ist wirklich sowohl großartig als auch abscheulich: großartig insofern, als es eine der erstaunlichsten Anwendungen menschlicher Intelligenz, Argumentation und Abstraktion ist, die jemals geschrieben wurden einfachste arithmetische Aussagen werden sinnvoll, ohne Widersprüche zuzulassen.

Wenn Sie dem Link im Originalbeitrag folgen, haben sie die gesamten Principia online. Die Seite, von der dieses Bild stammt, ist Seite 378. Ich kann kein Bild mit besserer Qualität erstellen, die Berechtigungen für das gescannte Dokument, auf das ich verlinkt habe, erlauben mir nicht, die Bildänderungen vorzunehmen, die ich brauche, um es lesbar zu machen in einer vernünftigen Größe. Aber Sie können es - und den ganzen Rest der Principia - sehen, indem Sie dem Link folgen.

In der Tat extreme Mathematik. Irgendwo sagen Sie, dass Mathematik Spaß macht, und das ist es auch, aber hier ruiniert die Komplexität der Notation den Spaß. Kurz nachdem (fast) bewiesen wurde, dass 1+1=2 ist, kommen die Eilmeldungen nur ein paar Seiten später ("382"):

Ich denke, sie waren auf dem richtigen Weg, aber das Tempo war etwas langsam.

Ich denke, dass das Programm, die Mathematik vollständig streng zu machen, damals eine gute Idee war, aber in der Praxis ist es nur begrenzt nützlich. Tatsächlich war die Hauptleistung wahrscheinlich das (damals) kontraintuitive Ergebnis, dass einige Aussagen unentscheidbar sind. Das ist ein wichtiges Ergebnis, das sonst verpasst worden wäre.

Wenn man jedoch versucht, jemanden dazu zu bringen, wie ein Mathematiker zu denken, stellt sich die Frage nicht, wie man den Formalismus präzisiert, sondern wie man ihn in die kognitive Maschinerie des menschlichen Gehirns abbildet. Es ist ein großer Unterschied, ob man jeden Schritt eines Beweises verifiziert und tatsächlich ein Gefühl dafür hat, warum das Ganze wahr ist. Im letzteren Fall lässt man sich leicht in die Irre führen, daher sollten Sie dies auf ähnliche Fragen anwenden können und die richtige Antwort erhalten. Sie sollten nicht bei der Intuition stehen bleiben, aber wenn sie gut platziert ist, sollte das eigentliche Schreiben eines formalen Beweises einem mechanischen Prozess nahe kommen, ohne dass es dabei zu großen Überraschungen kommt.

Ich denke, Polya war in How to Solve It auf dem richtigen Weg, indem sie Heuristiken vorschlug, die offensichtlich nicht solide sind, aber tatsächlich gut funktionieren, um Probleme in den Griff zu bekommen: z paradox), schlaf drüber (funktioniert nur, wenn du wirklich intensiv nachgedacht hast). Ich denke, es gibt nicht genug Gewicht in dieser Richtung im Mathematikunterricht, mit dem Ergebnis, dass die Leute Mathematik mit sinnbetäubenden Seiten des Formalismus gleichsetzen, die nur das Produkt und nicht den Prozess der Mathematik wiedergeben, wie er von Menschen mit einem für die Aufgabe ungeeigneten Gehirn praktiziert wird .

Eigentlich sollten wir bei der Verfügbarkeit von Computern in einigen Fällen beides tun können. Geben Sie den Menschen eine lesbare Zusammenfassung der Beweisschritte (was wir in einer mathematischen Veröffentlichung als "Beweis" bezeichnen) und konstruieren Sie dann einen formal überprüfbaren Beweis - es muss nicht auf eine minimale Menge von Axiomen hinausgehen, nur gut etablierte Theoreme .

Wenn Vulkanier völlig logisch wären, würde Russells Paradox nicht ihr Köpfe explodieren auch? Vielleicht führte die Tatsache, dass er überlebte, als all diese Computer starben, zu der Schlussfolgerung von Spock: "Logik ist der Anfang der Weisheit, Valeris, nicht das Ende."

Erinnere dich an die Futurama Episode, in der Leela versucht, den bösen Weihnachtsmann-Roboter mit einem logischen Paradoxon zu zerstören? "Ha! Mein Kopf war mit paradoxen Knautschzonen gebaut!" gefällt mir auch gut Ghost in the Shell: Eigenständiger Komplex Episode, in der ein Roboter einen anderen, weniger fähigen mit dem Lügner-Paradoxon überrumpelt.

Äh, zu meinem vorherigen Beitrag: Es wird klar, dass scienceblogs.com seine Zeichensätze auf eine schlechte Art und Weise vermischt. Es verwendet Latin-1 für die Hauptseiten und damit auch für das Posting-Formular. Aber die Kommentarvorschau verwendet utf-8, also sah es gut aus, als ich Kurts Nachnamen dort schrieb. Aber dann wird es wieder als Latin-1 angezeigt, also wird es vermasselt. Ich schätze, ich werde herausfinden, wem ich den Fehler melden soll. Tut mir leid wegen der Off-Topic-ness, aber ich denke, großartige Leute wie Kurt G. verdienen es, ihren Namen richtig geschrieben zu bekommen.

Für ein ähnliches modernes Projekt siehe auch Metamaths Beweis, dass 2+2=4 ist.

PaulC schrieb: „Ich denke, dass das Programm, die Mathematik vollständig streng zu machen, damals eine gute Idee war, aber in der Praxis ist es nur begrenzt nützlich."

Es wäre nützlich gewesen, da zukünftige mathematische Beweise, die ihrem Formalismus folgten, "vertrauenswürdiger" gewesen wären. Das Problem ist, woher wissen Sie, dass ein mathematischer Beweis, den Sie vor sich haben, nicht implizit auf einem Paradox beruht (wie der "Menge aller Mengen")? Wenn die Grundlagen Ihres mathematischen Fachgebiets suspekt sind, dann sind alle Schlussfolgerungen ähnlich suspekt.

Ich vermute, es wäre sehr nützlich gewesen, wenn es funktioniert hätte.

"Tatsächlich war die Hauptleistung wahrscheinlich das (damals) kontraintuitive Ergebnis, dass einige Aussagen unentscheidbar sind. Das ist ein wichtiges Ergebnis, das sonst verpasst worden wäre."

Aber Russell und Whitehead kamen nicht zu dem unentscheidbaren Ergebnis. Das war Gödel.

Es sei denn, Sie denken irgendwie, dass Gödel nicht an seinen Sachen gearbeitet hätte, ohne dass Principia Mathematica an erster Stelle stand. Das ist eine ziemlich indirekte Verbindung und nicht wirklich eine "Leistung" von Russell und Whitehead.

Harald,
Es ist nicht alles von scienceblogs.com, da zum Beispiel Pharyngula gut zu funktionieren scheint. Vielleicht ist es nur dieser Blog.

Meine Mathematikgeschichte ist nicht die beste, aber ich denke, es gibt eine starke Verbindung zwischen den Principia und Gödel. Ich glaube, ich habe die Geschichte in einem Vortrag gehört, den Greg Chaitin bei der Arbeit hielt, aber ich bin mir nicht sicher. Dies wäre mein erstes Jahr in meinem Job gewesen, das vor 10 Jahren war, daher sind viele Gespräche von vor langer Zeit verwischt worden.

Wie auch immer, wenn ich mich richtig erinnere, ist die Geschichte, dass R&W nicht allein war. Das Problem des Paradoxes war *das* mathematische Problem, an dem die Leute interessiert waren. Die Principia war der ehrgeizigste Ansatz, um das Paradox-Problem zu lösen. Viele andere sehr berühmte Mathematiker arbeiteten daran. Besonders wichtig für die Geschichte Gödels war Hilbert.

Gödel kam, als das Zeug in vollem Gange war, und wurde durch einen Kurs über Russells Arbeit zur Zahlentheorie (durch? mit einem Buch von? Russell) in das Feld eingeführt. Sie können also argumentieren, dass Russell ein wichtiger Beweger bei dem war, was zu Gödels Unvollständigkeitssatz führte.

Aber ich denke, dass die Unvollständigkeit eher von einer Reaktion auf Hilbert als von R&W getrieben wurde.

Bei Problemen mit dem Textformat werde ich mich an den technischen Guru von Seed wenden und sehen, ob wir das Problem beheben können.

Kennzeichen,
Die Geschichte scheint unvollständig zu sein. :-)

Mein Name wird normalerweise von TypeKey bereitgestellt, das ich auf Pharyngula gestartet habe. Wir können alle überprüfen, was mit meinem "Omlaut o" passiert. Oder Gödels. :-)

Russell und Whitehead waren nicht die einzigen, die daran interessiert waren, einen Weg zu entwickeln, um mathematische Prinzipien formal zu beweisen, beginnend mit Axiomen. Peanos Axiome gingen Gödel voraus. Zuvor hatte Boole sicherlich das Ziel, logische Argumente zu formalisieren.

Ohne ein Programm zur Formalisierung der Mathematik hätte Gödel das Ganze selbst tun müssen – nicht nur zeigen, dass Inferenzschritte als Zahlen kodiert werden können, sondern die ganze Idee eines formalen symbolischen Beweises erfinden. Er war ein brillanter Kerl, aber es scheint vernünftig anzunehmen, dass ihm die Tatsache geholfen hat, dass die Leute bereits eine Vorstellung davon hatten, was mit einem formalen Beweis gemeint war. Und tatsächlich hatte Hilbert schon die Frage gestellt, ob diese ausreichen, um alles zu entscheiden. Diese Frage macht nur Sinn, wenn Sie der Meinung sind, dass ein formaler Beweis etwas Interessantes oder Wertvolles sein könnte.

Tatsächlich zeigen die Beweise, dass Gödel direkt beeinflusst wurde, zugegebenermaßen von Hilberts Programm, http://plato.stanford.edu/entries/hilbert-program/, das im Grunde ein Plan war, um zu versuchen, die Mathematik formal zu entscheiden.

Also, kurz gesagt, ja, ich bin zuversichtlich, dass es sehr unwahrscheinlich ist, dass Goedel hereingekommen wäre und sein Unvollständigkeitsergebnis bewiesen hätte, wenn es nicht eine signifikante Fermentation von Mathematikern gegeben hätte, die daran interessiert waren, zu zeigen, dass die gesamte Mathematik formal bewiesen werden könnte . Ich meine, ich denke, es hätte passieren können, aber es ist nicht das, was tatsächlich passiert ist, und was tatsächlich passiert ist, erforderte die Arbeit vieler Mathematiker über ein Jahrhundert oder so, von denen die meisten von dem Ziel motiviert waren, Vollständigkeit und nicht Unvollständigkeit zu beweisen.

Inwieweit Goedel insbesondere von Whitehead und Russell beeinflusst wurde, interessierte mich nicht. Ich habe keine Ahnung und habe mich in meinem Kommentar nicht speziell darauf bezogen.

Laut Wikipedia war mein Gedächtnis tatsächlich erstaunlich nah :-)

Gödel kam durch eines von Russells Lehrbüchern mit den Ideen in Berührung, aber Hilberts Versuch, in die gleiche Richtung wie R&W zu gehen, hatte tatsächlich mehr mit Gödel zu tun als R&W. Aber die Informationen, die ich finden kann, deuten stark darauf hin, dass Gödel ohne Hilbert nicht die Arbeit gemacht hätte, die zur Unvollständigkeit führte.

Danke für diesen Link sieht aus wie eine sehr schöne Zusammenfassung des Hilbert-Programms.

Und dann kam dieser widerliche Kerl namens Kurt Gödel, der zeigte, dass das alles eine große Zeitverschwendung war. An diesem Punkt gehe ich davon aus, dass Russell und Whitehead losgingen und ihre Gehirne explodierten, ziemlich genau so, wie es die schlechten Schauspieler später vorgeben würden.

Die große Ironie besteht natürlich darin, dass es Russell war, der auf den fatalen Fehler in Freges Logiksystem hingewiesen hatte Freges erste Antwort auf Russell ist einer der Klassiker der Mathematik.

mjd/blog/math/PM.html diskutiert dies und hat auch ein raffiniertes Postscript, das die Symbologie in PM mit der Wahl von Lambda für Lambda-Kalkül verknüpft. Eine ausgezeichnete Lektüre.

Ich erinnere mich, dass R&W die paradoxe "Menge aller Mengen, die nicht Mitglieder ihrer selbst sind" erfunden hat, aber dachte, dass solche paradoxen Aussagen diskrete Kuriositäten seien, die sicher vom Rest der Mathematik als einfach unentscheidbar "abgegrenzt" werden könnten, wie der Wert 0/0. Gödel hat einen Konstruktionsbeweis entwickelt, der dieses Konzept verwendet, um zu zeigen, dass unbeweisbare Aussagen nicht vom Rest der Mathematik getrennt werden können.

Meistens, aber nicht ganz richtig.

Russell ist der Entdecker der "Menge aller Mengen, die nicht Mitglieder ihrer selbst sind", sie wird Russells Paradoxon genannt.

Die Mathematiker glaubten damals allgemein, dass paradoxe Konstrukte Fehler seien, die durch unzureichende Formalismen verursacht wurden, und dass sie durch die Schaffung einer geeigneten Grundlage für die Mathematik beseitigt werden könnten. Das ist ein großer Teil der zentralen Idee hinter dem Programm von Principia und Hilbert. Sie dachten, wenn sie bei Null anfangen und die Mathematik vollständig in formaler Logik aufbauen, könnten sie zu einem Entscheidungsverfahren: ein Verfahren, das für jede mathematische Aussage einen Beweis für ihre Wahrheit oder ihre Falschheit liefern könnte.

Sie glaubten nicht, dass die paradoxen Aussagen "abgemauert" werden könnten, sie hielten sie für grundlegende Fehler in der Grundlage der Mathematik, bedeutungslose Aussagen, die nur konstruiert werden konnten, weil die mathematischen Formalismen, die sie erlaubten, ungültig waren. Sie dachten, dass sie durch die richtige Konstruktion der Mathematik im Grunde "weggehen" würden: Es gäbe keine Möglichkeit, sie auch nur auszusprechen, weil sie auf ungültigen Konzepten beruhten.

Die Idee hinter der Konstruktion von R&W (und auch Hilberts Programm, wenn ich mich richtig erinnere) war ein System von Typen: Jede Aussage war klar definiert, um sich über eine bestimmte Art von Wert zu erstrecken, und keine Aussage konnte in irgendeiner Weise definiert werden das erlaubte es, über sich selbst zu sprechen. So könnten Sie zum Beispiel Prädikate erster Ordnung haben, die über Basiswerte argumentieren könnten, Prädikate zweiter Ordnung, die über Basiswerte folgern könnten, und Prädikate erster Ordnung Prädikate dritter Ordnung, die über Basiswerte, Prädikate erster und zweiter Ordnung usw. Aber kein Prädikat könnte jemals über sich selbst folgern: Ein Prädikat N-ter Ordnung könnte niemals über etwas jenseits der (N-1)-Prädikate hinaus folgern.

Der Schlüssel zu dem, was Gödel tat, war zu zeigen, wie man diese Trennung nicht durchsetzen konnte: Selbst im strengsten typtheoretischen Rahmen ist man könnten stellen beispielsweise Prädikate erster Ordnung unter Verwendung natürlicher Zahlen dar und erlauben dann Prädikaten erster Ordnung, sich über in Zahlen codierte Prädikate erster Ordnung zu erstrecken. (Eigentlich denke ich, dass es nicht nur natürliche Zahlen waren, sondern natürliche Zahlen mit Peano-Arithmetik.)

Wenn Sie daran denken, formalisierte (maschinenüberprüfbare) Mathematik zu machen, denken Sie zweimal darüber nach. Du machst einen Beweis, dann noch einen und . du bist süchtig. Du willst keine romantische Mathematik mehr machen. Jeder Standardbeweis (also eine informelle Beweisskizze) scheint voller Fehler und fehlender Referenzen zu sein. Russel hat sich nie erholt. Achtung.
Süchtig

PS Was die Nützlichkeit formalisierter (und maschinenüberprüfbarer) Mathematik betrifft, so denke ich, dass die interessanteste Anwendung darin besteht, formalisierte Beweise in logischen Systemen zu schreiben, die sich stark von dem unterscheiden, wofür unser Gehirn natürlicherweise verdrahtet ist (zum Beispiel Quantenlogik, siehe Metamaths Quantum Explorer). Dies kann nicht auf informelle Weise geschehen - Menschen können solche Beweise nicht zuverlässig überprüfen. Vielleicht wird sich eines Tages herausstellen, dass die darauf aufbauende Mathematik die physikalische Welt, in der wir leben, besser beschreiben kann als die, die auf klassischer Logik und ZF-Mengentheorie basiert?

Ich habe gerade mein Exemplar der April-Ausgabe von Notices of the American Mathematical Society erhalten. Die ganze Ausgabe ist im Wesentlichen eine Hommage an Kurt G. Das Ganze ist im Web verfügbar. Genießen! (Aber liest jemand Kommentare zu einem Blogbeitrag, der schon mehrere Tage alt ist?)

Dank eines Hinweises des Seed-Tech-Guru denke ich, dass die Zeichensatzprobleme behoben sind und alles jetzt UTF-8 tun sollte.

Nun, wenn Sie einen tatsächlichen formalen Beweis wollen, sehen Sie sich den Metamath-Beweis von 2+2=4 an. (1+1=2 ist langweilig, denn so definiert es 2.) Dies ist ein wirklich raffinierter Hypertext eines computerverifizierten Beweises, der aus den Axiomen der Zermelo-Fraenkel-Mengentheorie abgeleitet wurde. Das ist der 5254. Satz im System, obwohl nicht alle der vorhergehenden 5253 für den Beweis erforderlich sind. (Insbesondere Nummer 1329, das Axiom der Wahl, ist keine Voraussetzung.)

Dies beinhaltet auch viele andere, bedeutsamere Mathematik, wie zum Beispiel, dass wenn eine unendliche Reihe gegen einen Grenzwert konvergiert, dieser Grenzwert eindeutig ist.

Um die Geschichte für Interessierte ein wenig aufzuklären: Gödels Arbeit entstand als Reaktion auf Hilberts Aufforderung an die Mathematiker, die Konsistenz, Vollständigkeit und Entscheidbarkeit der Arithmetik mit endlichen Methoden zu beweisen. Der Titel seiner überaus wichtigen Arbeit ist jedoch "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I" (Übersetzung aus dem Deutschen Martin Davis). Wie Sie sehen, hat R& W eine direkte Verbindung nach Gödel. Als Fußnote, wie Sie feststellen werden, endet der Titel mit einem römischen (I), was darauf hinweist, dass dies nur Teil 1 der Arbeit ist. Es gab nie einen zweiten Teil!

Tatsächlich ist 1 + 1 = 3 für ausreichend große Werte von 1. Der Beweis bleibt dem Leser als Übung überlassen.

Gödels Aufsatz, der das Unvollständigkeitstheorem veröffentlicht, lautet "Über formal unentscheidbare Sätze der Principia Mathematica und verwandte Systeme" oder "On Formally Undecidable Propositions in Principia Mathematica and Related Systems".

R&W fließen also zwangsläufig in seine Arbeit ein, auch wenn er nur deren Notation und Semantik verwendet.

Die tatsächliche Seitenzahl ist 378+1. (Versorgen Sie Ihre eigene Pointe.)

Die Dienste von Russell und Whitehead für die Klärung von Konzepten und die Reinigung der Mathematik von metaphysischen Begriffen werden vielleicht noch lange nicht vergessen. Zweifellos waren sie Gründerväter der modernen symbolischen/mathematischen Logik. Wenn sie auf Seite 1+1=2 bewiesen haben 378, sie waren keine Narren, sondern engagiert und gründlich. Ihr Engagement sollte respektiert werden, anstatt ausgelacht zu werden. Die großen Köpfe wurden immer auf diese Weise gedemütigt. Es gibt immer Raum für Fehler und Verbesserungen, aber würdige den Beitrag anderer ohne Vorurteile .

Um auf Kommentar 37 zu antworten: Nein, 1 + 1 = 2 ist keine Definition, obwohl es sicherlich so aussieht.

Uns wurde unser ganzes Leben lang gesagt, dass 1 + 1 = 2 wahr ist, weil es einfacher ist, sich daran zu erinnern, als es zu verstehen. Was also Russel und Whitehead (ebenfalls Gödel und Landau) zu beweisen versuchten, war, dass die ganze uns bekannte Mathematik aus nur wenigen primitiven Axiomen abgeleitet werden kann. Sicherlich scheint 1 + 1 = 2 ein offensichtliches Ergebnis zu sein, aber wenn ich fragen würde "Ja, ein Apfel plus ein Apfel sind zwei Äpfel, aber woher wissen wir, dass das für sehr, sehr große Zahlen gilt?" Es ist gefährlich, solche Annahmen zu treffen, weil sie manchmal falsch sind. Es reicht also zu zeigen, dass die Addition von 1 zu beispielsweise a 1+a ergibt, oder noch einfacher, es genügt zu zeigen, dass die Addition von 1 zu 1 2 ergibt. Das ist es, was all diese Mathematiker wollten. :)

Spenden

ScienceBlogs ist der Ort, an dem Wissenschaftler direkt mit der Öffentlichkeit kommunizieren. Wir sind Teil von Science 2.0, einer gemeinnützigen Organisation für den Wissenschaftsunterricht, die gemäß Abschnitt 501(c)(3) des Internal Revenue Code tätig ist. Bitte spenden Sie steuerlich abzugsfähig, wenn Sie Wert auf unabhängige Wissenschaftskommunikation, Zusammenarbeit, Partizipation und Open Access legen.

Sie können auch mit Amazon Smile einkaufen und obwohl Sie nichts mehr bezahlen, bekommen wir eine Kleinigkeit.


5. Wahrscheinlichkeitslogik erster Ordnung

In diesem Abschnitt werden wir Wahrscheinlichkeitslogiken erster Ordnung diskutieren. Wie in Abschnitt 1 dieses Beitrags erläutert wurde, gibt es viele Möglichkeiten, wie eine Logik probabilistische Merkmale aufweisen kann. Die Modelle der Logik können probabilistische Aspekte haben, der Begriff der Konsequenz kann einen probabilistischen Charakter haben oder die Sprache der Logik kann probabilistische Operatoren enthalten. In diesem Abschnitt werden wir uns auf die logischen Operatoren konzentrieren, die einen Geschmack erster Ordnung haben. Die Variante erster Ordnung unterscheidet diese Operatoren von den probabilistischen Modaloperatoren des vorherigen Abschnitts.

Betrachten Sie das folgende Beispiel von Bacchus (1990):

Mehr als 75% aller Vögel fliegen.

Es gibt eine einfache probabilistische Interpretation dieses Satzes, nämlich wenn man wählt zufällig aus ein Vogel, dann beträgt die Wahrscheinlichkeit, dass der ausgewählte Vogel fliegt, mehr als 3/4. Um diese Art von Aussagen auszudrücken, werden probabilistische Operatoren erster Ordnung benötigt.

Es gibt eine andere Art von Satz, wie den folgenden Satz, der in Halpern (1990) diskutiert wurde:

Die Wahrscheinlichkeit, dass Tweety fliegt, ist größer als (0.9).

Dieser Satz berücksichtigt die Wahrscheinlichkeit, dass Tweety (ein bestimmter Vogel) fliegen kann. Diese beiden Arten von Sätzen werden durch zwei verschiedene Arten von Semantik angesprochen, wobei die erstere Wahrscheinlichkeiten über eine Domäne beinhaltet, während die letztere Wahrscheinlichkeiten über eine Menge möglicher Welten beinhaltet, die von der Domäne getrennt sind.

5.1 Ein Beispiel für eine Wahrscheinlichkeitslogik erster Ordnung

In diesem Unterabschnitt betrachten wir eine bestimmte Wahrscheinlichkeitslogik erster Ordnung, deren Sprache so einfach wie möglich ist, um uns auf die probabilistischen Quantoren zu konzentrieren. Die Sprache ist der Sprache der klassischen Logik erster Ordnung sehr ähnlich, aber anstelle des bekannten universellen und existenziellen Quantors enthält die Sprache einen probabilistischen Quantor.

Die Sprache basiert auf einer Reihe von einzelne Variablen (bezeichnet durch (x, y, z, x_1, x_2, ldots)), eine Menge von Funktionssymbole (bezeichnet mit (f, g, h, f_1, ldots)) wobei jedem Symbol eine Stelle zugeordnet ist (Nullfunktionssymbole werden auch genannt individuelle Konstanten) und eine Reihe von Prädikatsbuchstaben (bezeichnet durch ( R, P_1, ldots)), wobei jedem Symbol eine Stelle zugeordnet ist. Die Sprache enthält zwei Arten von syntaktischen Objekten, nämlich Begriffe und Formeln. Die Begriffe werden induktiv wie folgt definiert:

Jede einzelne Variable (x) ist ein Term.

Jedes Funktionssymbol (f) der Stelligkeit (n) gefolgt von einem (n)-Tupel von Termen ((t_1,ldots,t_n)) ist ein Term.

Bei dieser Begriffsdefinition werden die Formeln induktiv wie folgt definiert:

Jeder Prädikatsbuchstabe (R) der Stelligkeit (n) gefolgt von einem (n)-Tupel von Termen ((t_1,ldots,t_n)) ist eine Formel.

Wenn (phi) eine Formel ist, dann ist es auch ( eg phi).

Wenn (phi) und (psi) Formeln sind, dann ist es auch ((phiwedgepsi)).

Wenn (phi) eine Formel und (q) eine rationale Zahl im Intervall ([0,1]) ist, dann ist es auch (Px (phi) geq q).

Formeln der Form (Px(phi)geq q) sind zu lesen als: &ldquotDie Wahrscheinlichkeit, ein (x) so auszuwählen, dass (x) (phi) erfüllt, ist mindestens ( q)&rdquo. Die Formel (Px(phi)leq q) ist eine Abkürzung von (Px( eg phi) geq 1-q) und (Px(phi)=q) ist eine Abkürzung von (Px(phi)geq q keil Px(phi) leq q). Jedes freie Vorkommen von (x) in (phi) ist durch den Operator gebunden.

Diese Sprache wird auf sehr einfachen Modellen erster Ordnung interpretiert, die Tripel (M=(D,I,P)) sind, wobei die Domäne des Diskurses (D) ist eine endliche nichtleere Menge von Objekten, die Interpretation (I) ordnet jedem in der Sprache vorkommenden (n)-ären Funktionssymbol eine (n)-äre Funktion auf (D) zu und eine (n)-äre Beziehung auf ( D) mit jedem (n)-ären Prädikatsbuchstaben. (P) ist a Wahrscheinlichkeitsfunktion die jedem Element (d) in (D) eine Wahrscheinlichkeit (P(d)) zuweist, so dass (sum_ P(d)=1).

Um Formeln zu interpretieren, die freie Variablen enthalten, braucht man auch ein Zuordnung (g), der jeder Variablen ein Element von (D) zuweist. Die Interpretation ([![t]!]_) eines Termes (t) gegeben ein Modell (M=(D,I,P)) und eine Zuweisung (g) ist induktiv wie folgt definiert:

Wahrheit ist definiert als eine Beziehung (models) zwischen Modellen mit Zuweisungen und Formeln:

(M,g models R(t_1,ldots,t_n)) wenn (([![t_1]!], ldots, [![t_n]!]) in I(R ))

(M,g models eg phi) wenn (M,g ot models phi)

(M,g models (phi wedge psi)) wenn (M,g models phi) und (M,g models psi)

Betrachten Sie als Beispiel ein Modell einer Vase mit neun Murmeln: fünf sind schwarz und vier sind weiß. Nehmen wir an, dass (P) jeder Murmel eine Wahrscheinlichkeit von 1/9 zuweist, was die Idee einfängt, dass man mit gleicher Wahrscheinlichkeit jede Murmel auswählt. Angenommen, die Sprache enthält ein unäres Prädikat (B), dessen Interpretation die Menge der schwarzen Murmeln ist. Der Satz (Px(B(x)) = 5/9) ist in diesem Modell unabhängig von der Zuweisung wahr.

Die Logik, die wir gerade vorgestellt haben, ist zu einfach, um viele Formen der Argumentation über Wahrscheinlichkeiten zu erfassen. Wir werden hier drei Erweiterungen besprechen.

5.1.1 Quantifizierung über mehr als eine Variable

Zunächst möchte man über Fälle nachdenken, in denen mehr als ein Objekt aus der Domäne ausgewählt wird. Betrachten Sie zum Beispiel die Wahrscheinlichkeit, zuerst eine schwarze Murmel zu nehmen, sie zurückzulegen und dann eine weiße Murmel aus der Vase zu nehmen. Diese Wahrscheinlichkeit ist 5/9 ( imes) 4/9 = 20/81, aber wir können dies in der obigen Sprache nicht ausdrücken. Dazu benötigen wir einen Operator, der mehrere Variablen gleichzeitig behandelt, geschrieben als (Px_1,ldots x_n (phi) geq q). Die Semantik für solche Operatoren muss dann ein Wahrscheinlichkeitsmaß für Teilmengen von (D^n) liefern. Am einfachsten geht das, indem man einfach das Produkt der Wahrscheinlichkeitsfunktion (P) auf (D) nimmt, das als Erweiterung von (P) auf Tupel aufgefasst werden kann, wobei (P(d_1 ,ldots d_n)= P(d_1) imes cdots imes P(d_n)), was folgende Semantik ergibt:

Dieser Ansatz wird von Bacchus (1990) und Halpern (1990) verfolgt und entspricht der Idee, dass Selektionen unabhängig und mit Ersetzungen sind. Mit dieser Semantik kann das obige Beispiel als (Px,y (B(x) wedge eg B(y))= 20/81) formalisiert werden. Es gibt auch allgemeinere Ansätze, das Maß auf der Domäne auf Tupel aus der Domäne auszudehnen, wie etwa von Hoover (1978) und Keisler (1985).

5.1.2 Bedingte Wahrscheinlichkeit

Betrachtet man das Ausgangsbeispiel, dass mehr als 75 % aller Vögel fliegen, stellt man fest, dass dies in einem Modell, in dem die Domäne Objekte enthält, die keine Vögel sind, nicht angemessen erfasst werden kann. Diese Objekte sollten für das, was man ausdrücken möchte, keine Rolle spielen, aber die Wahrscheinlichkeitsquantoren quantifizieren über den gesamten Bereich. Um die Quantifizierung einzuschränken, muss man bedingte Wahrscheinlichkeitsoperatoren (Px (phi | psi) geq q) mit folgender Semantik hinzufügen:

(M,g models Px (phi | psi) geq q) genau dann, wenn es ein (d in D) gibt mit (M,g[x mapsto d] models psi ) dann

Mit diesen Operatoren drückt die Formel (Px(F(x) mid B(x)) > 3/4) aus, dass mehr als 75% aller Vögel fliegen.

5.1.3 Wahrscheinlichkeiten als Begriffe

Wenn man die Wahrscheinlichkeit verschiedener Ereignisse vergleichen möchte, beispielsweise die Auswahl einer schwarzen und einer weißen Kugel, kann es bequemer sein, Wahrscheinlichkeiten als eigenständige Terme zu betrachten. Das heißt, ein Ausdruck (Px(phi)) wird so interpretiert, dass er sich auf eine rationale Zahl bezieht. Dann kann man die Sprache mit arithmetischen Operationen wie Addition und Multiplikation und mit Operatoren wie Gleichheit und Ungleichung erweitern, um Wahrscheinlichkeitsterme zu vergleichen. Man kann dann sagen, dass man eine schwarze Kugel doppelt so wahrscheinlich wählt wie eine weiße Kugel wie (Px(B(x))=2 imes Px(W(x))). Eine solche Erweiterung erfordert, dass die Sprache zwei getrennte Klassen von Begriffen enthält: eine für Wahrscheinlichkeiten, Zahlen und die Ergebnisse arithmetischer Operationen mit solchen Begriffen und eine für den Diskursbereich, über den die probabilistischen Operatoren quantifizieren. Wir werden eine solche Sprache und Semantik hier nicht im Detail vorstellen. Ein solches System findet man bei Bacchus (1990).

5.2 Mögliche Welt-Wahrscheinlichkeitslogik erster Ordnung

In diesem Unterabschnitt betrachten wir eine Wahrscheinlichkeitslogik erster Ordnung mit einer Mögliche-Welt-Semantik (die wir FOPL abkürzen). Die Sprache von FOPL ähnelt dem Beispiel, das wir in Abschnitt 5.1 in Bezug auf die von Bacchus gegeben haben, außer dass wir hier vollständige Quantorenformeln der Form ((forall x)phi) für jede Formel (phi) haben. , und anstelle von Wahrscheinlichkeitsformeln der Form (Px(phi)ge q) haben wir Wahrscheinlichkeitsformeln der Form (P(phi)ge q) (ähnlich den Wahrscheinlichkeitsformeln in der propositionalen Wahrscheinlichkeit Logik).

Die Modelle von FOPL haben die Form (M = (W,D,I,P)), wobei (W) eine Menge von mögliche Welten, (D) ist a Domäne des Diskurses, (I) ist eine lokalisierte Interpretationsfunktion, die jedes (win W) auf eine Interpretationsfunktion (I(w)) abbildet, die jeder Funktion und jedem Prädikatssymbol eine Funktion oder ein Prädikat von geeigneter Bedeutung zuordnet, und (P) ist eine Wahrscheinlichkeitsfunktion, die jedem (w) in (W) eine Wahrscheinlichkeit (P(w)) zuweist.

Ähnlich dem einfachen Beispiel zuvor verwenden wir eine Zuweisungsfunktion (g), die jede Variable auf ein Element der Domäne (D) abbildet. Um Terme zu interpretieren, bilden wir für jedes Modell (M), Welt (win W) und Zuweisungsfunktion (g) jeden Term (t) wie folgt auf Domänenelemente ab:

Wahrheit wird gemäß einer Beziehung (models) zwischen Pointed Models (Modellen mit bezeichneten Welten) mit Zuweisungen und Formeln wie folgt definiert:

(M,w,g models R(t_1,ldots,t_n)) wenn (([![t_1]!], ldots, [![t_n]!]) in I (w)(R))

(M,w,g models eg phi) wenn (M,w,g ot models phi)

(M,w,g models (phi wedge psi)) wenn (M,w,g models phi) und (M,w,g models psi)

(M,w,gmodels (forall x)varphi) genau dann (M,w,g[x/d]models varphi) für alle (din D), wobei (g[x/d]) ist dasselbe wie (g), außer dass es (x) auf (d) abbildet.

Betrachten Sie als Beispiel ein Modell, bei dem es zwei mögliche Vasen gibt: 4 weiße Murmeln und 4 schwarze Murmeln wurden in beide möglichen Vasen gelegt.Aber dann wurde ein anderer Marmor, genannt , in die Vase gelegt, aber in einer möglichen Vase war sie weiß und in der anderen schwarz. Somit gibt es am Ende zwei mögliche Vasen: eine mit 5 schwarzen Murmeln und 4 weißen Murmeln und die andere mit 4 schwarzen Murmeln und 5 weißen Murmeln. Angenommen, (P) weist den beiden möglichen Vasen (1/2) Wahrscheinlichkeit zu. Dann ist (P(B(mathsf)) = 1/2) gilt für diese Variablenzuweisung, und wenn eine andere Variablenzuweisung gewählt würde, wäre die Formel ((exists x) P(B(x)) = 1/2) immer noch wahr .

5.3 Metalogik

Im Allgemeinen ist es schwierig, Beweissysteme für Wahrscheinlichkeitslogiken erster Ordnung bereitzustellen, da das Gültigkeitsproblem für diese Logiken im Allgemeinen unentscheidbar ist. Es ist nicht einmal wie in der klassischen Logik erster Ordnung der Fall, dass man in endlicher Zeit herausfinden kann, ob eine Inferenz gültig ist (siehe Abadi und Halpern (1994)).

Dennoch gibt es viele Ergebnisse für die Wahrscheinlichkeitslogik erster Ordnung. Hoover (1978) und Keisler (1985) untersuchen beispielsweise Vollständigkeitsergebnisse. Bacchus (1990) und Halpern (1990) liefern auch vollständige Axiomatisierungen sowie Kombinationen von Wahrscheinlichkeitslogiken erster Ordnung bzw. Wahrscheinlichkeitslogiken erster Ordnung. In Ognjanović und Ra&scaronković (2000) wird eine unendliche vollständige Axiomatisierung für eine allgemeinere Version der hier vorgestellten Wahrscheinlichkeitslogik erster Ordnung der möglichen Welt gegeben.


1.2: Aussagen und Logik - Mathematik

Die Aussagenlogik beschäftigt sich mit Aussagen und ihren Zusammenhängen. Der Begriff des Satzes kann hier nicht genau definiert werden. Grob gesagt, a Vorschlag ist ein möglicher Zustand der Welt, der entweder wahr oder falsch ist, z.B. die Möglichkeit, dass es regnet, die Möglichkeit, dass es bewölkt ist und so weiter. Die Bedingung muss nicht wahr sein, damit sie eine Aussage ist. Tatsächlich möchten wir vielleicht sagen, dass es falsch ist oder dass es wahr ist, wenn eine andere Aussage wahr ist.

In diesem Kapitel betrachten wir zunächst die syntaktischen Regeln, die die Sprache der Aussagenlogik definieren. Wir führen dann den Begriff einer Wahrheitszuweisung ein und verwenden ihn, um die Bedeutung von Sätzen der Aussagenlogik zu definieren. Danach präsentieren wir ein mechanisches Verfahren zum Bewerten von Sätzen für eine gegebene Wahrheitszuordnung und wir präsentieren ein mechanisches Verfahren zum Finden von Wahrheitszuordnungen, die Sätze erfüllen. Wir schließen mit einigen Beispielen der Aussagenlogik bei der Formalisierung natürlicher Sprache und digitaler Schaltkreise.

2.2 Syntax

In der Aussagenlogik gibt es zwei Arten von Sätzen – einfache Sätze und zusammengesetzte Sätze. Einfache Sätze drücken einfache Tatsachen über die Welt aus. Zusammengesetzte Sätze drücken logische Beziehungen zwischen den einfacheren Sätzen aus, aus denen sie bestehen.

Einfache Sätze in der Aussagenlogik werden oft genannt Satzkonstanten oder manchmal, logische Konstanten. Im Folgenden schreiben wir Satzkonstanten als Zeichenfolgen aus Buchstaben, Ziffern und Unterstrichen ("_"), wobei das erste Zeichen ein Kleinbuchstabe ist. Beispielsweise, regnet ist eine Satzkonstante, ebenso wie REGEN, r32aining, und raining_or_snowing. Es regnet ist keine Satzkonstante, da sie mit einem Großbuchstaben beginnt. 324567 schlägt fehl, weil es mit einer Zahl beginnt. es regnet oder schneit schlägt fehl, weil es Bindestriche (anstelle von Unterstrichen) enthält.

Zusammengesetzte Sätze werden aus einfacheren Sätzen gebildet und drücken Beziehungen zwischen den konstituierenden Sätzen aus. Es gibt fünf Arten von zusammengesetzten Sätzen, nämlich. Negationen, Konjunktionen, Disjunktionen, Implikationen und B-Bedingungen.

EIN Negation besteht aus dem Negationsoperator ¬ und einem beliebigen Satz, genannt Ziel. Zum Beispiel, wenn der Satz p, können wir die Negation von bilden p Wie nachfolgend dargestellt.

EIN Verbindung ist eine Folge von Sätzen, die durch Vorkommen des &and-Operators getrennt und in Klammern eingeschlossen sind, wie unten gezeigt. Die konstituierenden Sätze heißen verbindet. Zum Beispiel können wir die Konjunktion von bilden p und q wie folgt.

EIN Disjunktion ist eine Folge von Sätzen, die durch Vorkommen des &or-Operators getrennt und in Klammern eingeschlossen sind. Die konstituierenden Sätze heißen disjunkt. Zum Beispiel können wir die Disjunktion von bilden p und q wie folgt.

Ein Implikation besteht aus einem Satzpaar, das durch den Operator &rArr getrennt und in Klammern eingeschlossen ist. Der Satz links vom Operator heißt Vorgänger, und der Satz rechts heißt der konsequent. Die Implikation von p und q wird unten gezeigt.

EIN bikonditionell ist eine Kombination aus einer Implikation und einer umgekehrten Implikation. Zum Beispiel können wir das Bikonditional von . ausdrücken p und q Wie nachfolgend dargestellt.

Beachten Sie, dass die konstituierenden Sätze innerhalb eines zusammengesetzten Satzes entweder einfache Sätze oder zusammengesetzte Sätze oder eine Mischung aus beiden sein können. Das Folgende ist beispielsweise ein gesetzlicher zusammengesetzter Satz.

Ein Nachteil unserer Schreibweise besteht darin, dass die Klammern dazu neigen, sich aufzubauen und richtig zugeordnet werden müssen. Es wäre schön, wenn wir auf Klammern verzichten könnten, z.B. Vereinfachung des vorhergehenden Satzes zu dem unten gezeigten.

Ganz auf Klammern können wir leider nicht verzichten, da wir dann bestimmte Sätze nicht eindeutig wiedergeben könnten. Der oben gezeigte Satz könnte beispielsweise durch das Weglassen von Klammern in einem der folgenden Sätze entstanden sein.

Die Lösung für dieses Problem ist die Verwendung von Operator-Priorität. Die folgende Tabelle zeigt eine Rangfolge unserer Operatoren. Der Operator ¬ hat eine höhere Priorität als &and &and hat eine höhere Priorität als &oder &or hat eine höhere Priorität als &rArr und &rArr hat eine höhere Priorität als &hArr.

In Sätzen ohne Klammern kommt es häufig vor, dass ein Ausdruck auf beiden Seiten von Operatoren flankiert wird. Bei der Interpretation solcher Sätze stellt sich die Frage, ob der Ausdruck mit dem Operator links oder rechts assoziiert ist. Wir können Vorrang verwenden, um diese Entscheidung zu treffen. Insbesondere stimmen wir darin überein, dass ein Operand in einer solchen Situation immer mit dem Operator mit höherer Priorität assoziiert wird. Die folgenden Beispiele zeigen, wie diese Regeln in verschiedenen Fällen funktionieren. Die Ausdrücke auf der rechten Seite sind die vollständig in Klammern gesetzten Versionen der Ausdrücke auf der linken Seite.

&nicht p &und q ((&nicht p) &und q)
p &und nichtq (p &und nicht q))
p &und q &oder r ((p &und q) &oder r)
p &oder q &und r (p &oder (q &und r))
p &rArr q &hArr r ((p &rArr q) &hArr r))
p &hArr q &rArr r (p &hArr (q &rArr r))

Wenn ein Operand von zwei &and-Operatoren oder von zwei &or-Operatoren umgeben ist, wird der Operand links zugeordnet. Wenn ein Operand von zwei &rArr-Operatoren oder von zwei &hArr-Operatoren umgeben ist, wird der Operand rechts zugeordnet.

p &und q &und r ((p &und q) &und r))
p &oder q &oder r ((p &oder q) &oder r))
p &rArr q &rArr r (p &rArr (q &rArr r))
p &hArr q &hArr r (p &hArr (q &hArr r))

Beachten Sie, dass nur weil die Priorität es uns in einigen Fällen erlaubt, Klammern zu löschen, nicht bedeutet, dass wir ganz auf Klammern verzichten können. Betrachten Sie das zuvor gezeigte Beispiel. Der Vorrang beseitigt die Mehrdeutigkeit, indem er diktiert, dass der Satz ohne Klammern eine Implikation mit einer Disjunktion als Vorläufer ist. Dies ist jedoch in den Fällen problematisch, in denen wir eine Disjunktion mit einer Implikation als Disjunktion ausdrücken wollen. In solchen Fällen müssen wir mindestens ein Klammerpaar beibehalten.

Wir beenden den Abschnitt mit zwei einfachen Definitionen, die bei der Diskussion der Aussagenlogik nützlich sind. EIN propositionales Vokabular ist eine Menge von Satzkonstanten. EIN propositionale Sprache ist die Menge aller propositionalen Sätze, die aus einem propositionalen Vokabular gebildet werden können.

2.3 Semantik

Die Behandlung der Semantik in der Logik ist der Behandlung in der Algebra ähnlich. Die Algebra kümmert sich nicht um die Bedeutung von Variablen in der realen Welt. Interessant sind die Beziehungen zwischen den Werten der Variablen, die in den von uns geschriebenen Gleichungen ausgedrückt werden. Algebraische Methoden sind darauf ausgelegt, diese Beziehungen zu respektieren, unabhängig davon, was die Variablen darstellen.

In ähnlicher Weise kümmert sich die Logik nicht um die Bedeutung von Satzkonstanten in der realen Welt. Interessant ist die Beziehung zwischen den Wahrheitswerten einfacher Sätze und den Wahrheitswerten zusammengesetzter Sätze, in denen die einfachen Sätze enthalten sind. Wie bei der Algebra sind logische Argumentationsmethoden unabhängig von der Bedeutung von Satzkonstanten, es kommt nur auf die Form von Sätzen an.

Obwohl die den Aussagekonstanten zugewiesenen Werte in dem gerade beschriebenen Sinne nicht entscheidend sind, ist es in Bezug auf Logik manchmal nützlich, Wahrheitszuweisungen explizit zu machen und verschiedene Zuweisungen oder alle Zuweisungen usw. zu berücksichtigen. Eine solche Zuordnung wird Wahrheitszuordnung genannt.

Formal, a Wahrheitszuordnung denn ein propositionales Vokabular ist eine Funktion, die jeder der Propositionskonstanten des Vokabulars einen Wahrheitswert zuweist. Im Folgenden verwenden wir die Ziffer 1 als Synonym für wahr und 0 als Synonym für falsch und wir beziehen uns auf den Wert einer Konstanten oder eines Ausdrucks unter einer Wahrheitszuweisung ich durch Hochstellen der Konstanten oder des Ausdrucks mit ich als hochgestellt.

Die unten gezeigte Zuweisung ist ein Beispiel für den Fall eines propositionalen Vokabulars mit nur drei Propositionskonstanten, d.h. p, q, und r.

p ich = 1
q ich = 0
ich bin = 1

Die folgende Zuordnung ist eine weitere Wahrheitszuordnung für das gleiche Vokabular.

p ich = 0
q ich = 0
ich bin = 1

Beachten Sie, dass die obigen Formeln selbst keine Sätze in der Aussagenlogik sind. Die Aussagenlogik lässt keine hochgestellten Zeichen zu und verwendet kein =-Symbol. Vielmehr handelt es sich um informelle Aussagen auf Metaebene Über besondere Wahrheitszuweisungen. Obwohl es manchmal verwirrend sein kann, über Aussagenlogik mit einer ähnlichen Notation wie der Aussagenlogik zu sprechen, ermöglicht es uns, Metainformationen präzise und effizient zu übermitteln. Um Probleme zu minimieren, verwenden wir in diesem Buch eine solche Meta-Notation nur selten und nur dann, wenn die Verwechslungsgefahr gering ist.

Betrachtet man die vorhergehenden Wahrheitszuweisungen, ist es wichtig zu bedenken, dass jede Wahrheitszuweisung, was die Logik betrifft, genauso gut ist wie jede andere. Die Logik selbst legt die Wahrheitszuweisung einzelner Satzkonstanten nicht fest.

Andererseits, gegeben eine Wahrheitszuordnung für die Satzkonstanten einer Sprache, Logik tut Festlegen der Wahrheitszuweisung für alle zusammengesetzten Sätze in dieser Sprache. Tatsächlich ist es möglich, den Wahrheitswert eines zusammengesetzten Satzes durch wiederholtes Anwenden der folgenden Regeln zu bestimmen.

Ist der Wahrheitswert eines Satzes wahr, der Wahrheitswert seiner Negation ist falsch. Ist der Wahrheitswert eines Satzes falsch, der Wahrheitswert seiner Negation ist wahr.

Der Wahrheitswert einer Konjunktion ist wahr genau dann, wenn die Wahrheitswerte seiner Konjunkte beides sind wahr andernfalls ist der Wahrheitswert falsch.

&phi &psi &phi &und &psi
1 1 1
1 0 0
0 1 0
0 0 0

Der Wahrheitswert einer Disjunktion ist wahr genau dann, wenn der Wahrheitswert von mindestens einer seiner Disjunkten . ist wahr andernfalls ist der Wahrheitswert falsch. Beachten Sie, dass dies die inklusive oder Interpretation des &or-Operators und unterscheidet sich von der Exklusiv oder Interpretation, bei der eine Disjunktion genau dann wahr ist, wenn eine ungerade Anzahl ihrer Disjunkten wahr ist.

&phi &psi &phi &oder &psi
1 1 1
1 0 1
0 1 1
0 0 0

Der Wahrheitswert einer Implikation ist falsch wenn und nur wenn sein Vorläufer ist wahr und seine Konsequenz ist falsch andernfalls ist der Wahrheitswert wahr. Das nennt man materielle Implikationen.

&phi &psi &phi &rArr &psi
1 1 1
1 0 0
0 1 1
0 0 1

Eine bikonditionale ist wahr genau dann, wenn die Wahrheitswerte ihrer Konstituenten übereinstimmen, d. h. sie sind entweder beides wahr oder beides falsch.

&phi &psi &phi &hArr &psi
1 1 1
1 0 0
0 1 0
0 0 1

Mit diesen Definitionen ist es leicht, die Wahrheitswerte zusammengesetzter Sätze mit Satzkonstanten als Konstituenten zu bestimmen. Wie wir im nächsten Abschnitt sehen werden, können wir die Wahrheitswerte von zusammengesetzten Sätzen mit anderen zusammengesetzten Sätzen als Teile bestimmen, indem wir zuerst die konstituierenden Sätze auswerten und dann diese Definitionen auf die Ergebnisse anwenden.

Wir beenden diesen Abschnitt mit einigen Definitionen für die zukünftige Verwendung. Wir sagen, dass eine Wahrheitszuordnung erfüllt ein Satz genau dann, wenn der Satz ist wahr unter dieser Wahrheitszuordnung. Wir sagen, dass eine Wahrheitszuordnung verfälscht ein Satz genau dann, wenn der Satz ist falsch unter dieser Wahrheitszuordnung. Eine Wahrheitszuordnung erfüllt a einstellen von Sätzen genau dann, wenn es erfüllt jeder Satz im Satz. Eine Wahrheitszuordnung verfälscht a einstellen von Sätzen genau dann, wenn es verfälscht mindestens ein Satz im Set.

2.4 Auswertung

Evaluation ist der Prozess der Bestimmung der Wahrheitswerte von zusammengesetzten Sätzen, denen eine Wahrheitszuweisung für die Wahrheitswerte von Propositionskonstanten gegeben wird.

Wie sich herausstellt, gibt es eine einfache Technik, um komplexe Sätze zu bewerten. Wir ersetzen die Satzkonstanten in unserem Satz durch wahre und falsche Werte und bilden einen Ausdruck mit Einsen und Nullen und logischen Operatoren. Wir verwenden unsere Operatorsemantik, um Teilausdrücke mit diesen Wahrheitswerten als Argumente auszuwerten. Wir wiederholen dann von innen nach außen, bis wir einen Wahrheitswert für den Satz als Ganzes haben.

Betrachten Sie als Beispiel die Wahrheitszuordnung ich unten gezeigt.

p ich = 1
q ich = 0
ich bin = 1

Mit unserer Bewertungsmethode können wir das sehen ich erfüllt (p &oder q) &und nichtq &oder r).

Betrachten Sie nun die Wahrheitszuordnung j wie folgt definiert.

p j = 0
q j = 1
r j = 0

In diesem Fall, j erfüllt nicht (p &oder q) &und nichtq &oder r).

Mit dieser Technik können wir die Wahrheit beliebiger Sätze in unserer Sprache bewerten. Die Kosten sind proportional zur Höhe der Strafe. Natürlich ist es in einigen Fällen möglich, zu sparen und noch besser zu werden. Wenn wir beispielsweise bei der Auswertung einer Konjunktion feststellen, dass die erste Konjunktion falsch ist, brauchen wir die zweite Konjunktion nicht auszuwerten, da der Satz als Ganzes falsch sein muss.

2.5 Zufriedenheit

Befriedigung ist das Gegenteil von Bewertung. Wir beginnen mit einem oder mehreren zusammengesetzten Sätzen und versuchen herauszufinden, welche Wahrheitszuordnungen diese Sätze erfüllen. Ein nettes Merkmal der Aussagenlogik ist, dass es effektive Verfahren gibt, um Wahrheitszuordnungen zu finden, die Sätze der Aussagenlogik erfüllen. In diesem Abschnitt betrachten wir eine Methode, die auf Wahrheitstabellen basiert.

EIN Wahrheitstabelle für eine propositionale Sprache ist eine Tabelle, die alle möglichen Wahrheitszuordnungen für die propositionalen Konstanten in der Sprache zeigt. Die Spalten der Tabelle entsprechen den Satzkonstanten der Sprache, und die Zeilen entsprechen verschiedenen Wahrheitszuweisungen für diese Konstanten.

Die folgende Abbildung zeigt eine Wahrheitstabelle für eine Aussagensprache mit nur drei Aussagekonstanten (p, q, und r). Jede Spalte entspricht einer Aussagekonstanten und jede Zeile entspricht einer einzelnen Wahrheitszuweisung. Die Wahrheitszuweisungen ich und j die im vorhergehenden Abschnitt definiert wurden, entsprechen der dritten bzw. sechsten Zeile dieser Tabelle.

p q r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0

Beachten Sie, dass für eine Aussagensprache mit nein Satzkonstanten gibt es nein Spalten in der Wahrheitstabelle und 2 nein Reihen.

Bei der Lösung von Zufriedenheitsproblemen beginnen wir mit einer Wahrheitstabelle für die Satzkonstanten unserer Sprache. Dann verarbeiten wir unsere Sätze der Reihe nach, indem wir für jeden Satz ein x neben Zeilen in der Wahrheitstabelle platzieren, die Wahrheitszuweisungen entsprechen, die den Satz nicht erfüllen. Die am Ende dieses Prozesses verbleibenden Wahrheitszuweisungen sind alle möglichen Wahrheitszuweisungen der Eingabesätze.

Betrachten Sie als Beispiel den Satz p &oder q &rArr q &und r. Wir können alle Wahrheitszuordnungen finden, die diesen Satz erfüllen, indem wir eine Wahrheitstabelle für konstruieren p, q, und r. Siehe unten. Wir setzen ein x neben jede Reihe, die den Satz nicht erfüllt (Reihen 2, 3, 4, 6). Schließlich nehmen wir die restlichen Zeilen (1, 5, 7, 8) als Antworten.

p q r
1 1 1
x 1 1 0 x
x 1 0 1 x
x 1 0 0 x
0 1 1
x 0 1 0 x
0 0 1
0 0 0

Der Nachteil des Wahrheitstabellenverfahrens ist die Rechenkomplexität. Wie oben erwähnt, wächst die Größe einer Wahrheitstabelle für eine Sprache exponentiell mit der Anzahl der Propositionskonstanten in der Sprache. Wenn die Anzahl der Konstanten klein ist, funktioniert die Methode gut. Wenn die Zahl groß ist, wird das Verfahren unpraktisch. Selbst bei mittelgroßen Problemen kann es mühsam sein. Selbst für eine Anwendung wie Sorority World, wo es nur 16 Propositionskonstanten gibt, gibt es 65.536 Wahrheitszuweisungen.

Im Laufe der Jahre haben Forscher Wege vorgeschlagen, um die Leistung der Wahrheitstabellenüberprüfung zu verbessern. Der beste Ansatz für den Umgang mit großen Vokabularien besteht jedoch darin, anstelle der Wahrheitstabellenprüfung symbolische Manipulationen (d. h. logisches Denken und Beweise) zu verwenden. Wir diskutieren diese Methoden in den Kapiteln 4 und 5.

2.6 Beispiel - Natürliche Sprache

Als Übung für die Arbeit mit Aussagenlogik betrachten wir die Kodierung verschiedener englischer Sätze als formale Sätze in der Aussagenlogik. Wie wir sehen werden, ist der Aufbau englischer Sätze zusammen mit verschiedenen Schlüsselwörtern wie such wenn und Nein, bestimmen, wie solche Sätze übersetzt werden sollen.

Die folgenden Beispiele betreffen drei Eigenschaften von Personen, und wir weisen jeder dieser Eigenschaften eine andere Aussagekonstante zu. Wir verwenden die Konstante c bedeuten, dass eine Person cool ist. Wir verwenden die Konstante f bedeuten, dass eine Person lustig ist. Und wir verwenden die Konstante p bedeutet, dass eine Person beliebt ist.

Betrachten wir als erstes Beispiel den englischen Satz Wenn eine Person cool oder lustig ist, dann ist sie beliebt. Diesen Satz in die Sprache der Aussagenlogik zu übersetzen ist einfach. Die Verwendung der Wörter wenn und dann deutet auf eine Implikation hin. Die Bedingung (cool oder lustig) ist eindeutig eine Disjunktion, und die Schlussfolgerung (Beliebt) ist nur eine einfache Tatsache. Unter Verwendung des Vokabulars aus dem letzten Absatz führt dies zu dem unten gezeigten Satz der Aussagenlogik.

Als nächstes haben wir den Satz Eine Person ist nur beliebt, wenn sie entweder cool oder lustig ist. Dies ist dem vorherigen Satz ähnlich, aber das Vorhandensein des Satzes nur wenn legt nahe, dass die Konditionalität in die andere Richtung geht. Es entspricht dem Satz Wenn eine Person beliebt ist, dann ist sie entweder cool oder lustig. Und dieser Satz kann wie unten gezeigt direkt in die Aussagenlogik übersetzt werden.

Eine Person ist genau dann beliebt, wenn sie entweder cool oder lustig ist. Die Verwendung des Satzes dann und nur dann, wenn schlägt ein biconditional vor, wie in der unten gezeigten Übersetzung. Beachten Sie, dass dies der Konjunktion der beiden oben gezeigten Implikationen entspricht. Das Bikonditional erfasst diese Konjunktion in einer kompakteren Form. p &hArr c &oder f

Schließlich haben wir einen negativen Satz. Es gibt niemanden, der sowohl cool als auch lustig ist. Das Wort Nein schlägt hier eine Negation vor. Um die Übersetzung in die Aussagenlogik zu erleichtern, können wir dies zunächst umformulieren als Es ist nicht so, dass es eine Person gibt, die sowohl cool als auch lustig ist. Dies führt direkt zu der folgenden Codierung.

Beachten Sie, dass nur weil wir Sätze in die Sprache der Aussagenlogik übersetzen können, nicht bedeutet, dass sie wahr sind. Die gute Nachricht ist, dass wir mit unserem Bewertungsverfahren feststellen können, welche Sätze wahr und welche falsch sind?

Angenommen, wir stellen uns eine Person vor, die cool und lustig und beliebt ist, d. h. die Propositionskonstanten c und f und p sind alle wahr. Welche unserer Sätze sind wahr und welche falsch.

Anhand des zuvor beschriebenen Bewertungsverfahrens können wir sehen, dass für diese Person der erste Satz wahr ist.

Auch der zweite Satz ist richtig.

Da der dritte Satz eigentlich nur die Konjunktion der ersten beiden Sätze ist, trifft er auch zu, was wir wie unten gezeigt direkt bestätigen können.

Leider stimmt der vierte Satz nicht, da die Person in diesem Fall sowohl cool als auch lustig ist.

In diesem speziellen Fall sind drei der Sätze wahr, während einer falsch ist. Das Ergebnis davon ist, dass es keine solche Person gibt (vorausgesetzt, die in unseren Sätzen ausgedrückte Theorie ist richtig). Die gute Nachricht ist, dass es Fälle gibt, in denen alle vier Sätze wahr sind, z. eine Person, die cool und beliebt, aber nicht lustig ist, oder eine Person, die lustig und beliebt, aber nicht cool ist. Zu bedenkende Frage: Was ist an einer Person weder cool noch lustig oder beliebt? Ist das nach unserer Theorie möglich? Welcher der Sätze wäre wahr und welcher falsch?

2.7 Beispiel – Digitale Schaltungen

Betrachten wir nun die Verwendung der Aussagenlogik bei der Modellierung eines Teils der physischen Welt, in diesem Fall einer digitalen Schaltung, wie sie beim Bau von Computern verwendet wird.

Das folgende Diagramm ist eine bildliche Darstellung einer solchen Schaltung. Es gibt drei Eingänge Knoten, einige interne Knoten und zwei Ausgabeknoten. Da sind fünf Tore diese Knoten miteinander verbinden - zwei xor Tore (die Tore oben), zwei und Tore (die Tore unten links) und ein oder Tor (das Tor unten rechts).

Zu einem bestimmten Zeitpunkt kann ein Knoten in einer Schaltung entweder auf oder aus. Die Eingangsknoten werden von außerhalb der Schaltung gesetzt. Ein Gatter setzt seinen Ausgang entweder auf oder aus basierend auf dem Typ des Gatters und den Werten seiner Eingangsknoten. Die Ausgabe von an und Tor ist auf genau dann, wenn beide Eingänge . sind auf. Der Wert von an oder Knoten ist auf genau dann, wenn mindestens einer seiner Eingänge . ist auf. Die Ausgabe von an xor Tor ist auf genau dann, wenn seine Eingaben nicht übereinstimmen.

Angesichts der booleschen Natur von Signalen auf Knoten und des deterministischen Charakters von Gattern ist es ganz natürlich, digitale Schaltungen in der Aussagenlogik zu modellieren. Wir können jeden Knoten einer Schaltung als Satzkonstante darstellen, mit der Idee, dass der Knoten auf genau dann, wenn die Konstante wahr ist. Mit der Sprache der Aussagenlogik können wir das Verhalten von Gattern erfassen, indem wir Sätze schreiben, die die Werte der Eingangsknoten und Ausgangsknoten der Gatter in Beziehung setzen.

Die unten gezeigten Sätze erfassen die fünf Tore in der oben gezeigten Schaltung. Knoten Ö muss sein auf genau dann, wenn Knoten p und q nicht zustimmen.

(p &und nichtq) &oder nichtp &und q) &hArr Ö
r &und Ö &hArr ein
p &und q &hArr b
(Ö &und nichtr) &oder nichtÖ &und r) &hArr so
ein &oder b &hArr c

Sobald wir dies getan haben, können wir unsere Formalisierung verwenden, um die Schaltung zu analysieren - um festzustellen, ob sie der Spezifikation entspricht, um zu testen, ob eine bestimmte Instanz richtig funktioniert, und um das Problem zu diagnostizieren, wenn dies nicht der Fall ist.

Rekapitulieren

Die Syntax der Aussagenlogik beginnt mit einer Menge von Satzkonstanten. Zusammengesetzte Sätze werden gebildet, indem einfachere Sätze mit logischen Operatoren kombiniert werden. In der hier verwendeten Version der Aussagenlogik gibt es fünf Arten von zusammengesetzten Sätzen – Negationen, Konjunktionen, Disjunktionen, Implikationen und B-Bedingungen. EIN Wahrheitszuordnung für Aussagenlogik ist eine Abbildung, die jeder der Aussagekonstanten in der Sprache einen Wahrheitswert zuweist. Eine Wahrheitszuweisung erfüllt ein Satz genau dann, wenn der Satz ist wahr unter dieser Wahrheitszuweisung gemäß Regeln, die die logischen Operatoren der Sprache definieren. Auswertung ist der Prozess der Bestimmung der Wahrheitswerte eines komplexen Satzes, wenn eine Wahrheitszuordnung für die Wahrheitswerte der Satzkonstanten in diesem Satz gegeben ist. Befriedigung ist der Prozess der Bestimmung, ob ein Satz eine Wahrheitszuordnung hat, die ihn erfüllt.

Probleme

Aufgabe 2.1: Sagen Sie, ob jeder der folgenden Ausdrücke ein syntaktisch legaler Satz der Aussagenlogik ist.

(ein)p &und nichtp
(b)&nichtp &oder nichtp
(c)&nicht(q &oder r) &nichtq &rArr &nicht&nichtp
(d)(p &und q) &oder (p &nicht&und q)
(e)p &oder nichtq &und nichtp &oder nichtq &rArr p &oder q

Aufgabe 2.2: Betrachten Sie eine Wahrheitszuordnung, in der p ist wahr, q ist falsch, r ist wahr. Verwenden Sie diese Wahrheitszuordnung, um die folgenden Sätze auszuwerten.

(ein)p &rArr q &und r
(b)p &rArr q &oder r
(c)p &und q &rArr r
(d)p &und q &rArr &nichtr
(e)p &und q &hArr q &und r

Problem 2.3: Ein kleines Unternehmen stellt Widgets in einer Vielzahl von Bestandteilen (Aluminium, Kupfer, Eisen), Farben (Rot, Grün, Blau, Grau) und Oberflächen (matt, strukturiert, beschichtet) her. Obwohl es mehr als tausend mögliche Kombinationen von Widget-Features gibt, vermarktet das Unternehmen nur eine Teilmenge der möglichen Kombinationen. Die folgenden Sätze sind Einschränkungen, die die Möglichkeiten charakterisieren. Angenommen, ein Kunde bestellt ein Kupfer-Widget, das sowohl grün als auch blau mit einer matten Beschichtung ist. Ihre Aufgabe besteht darin, festzustellen, welche Einschränkungen erfüllt und welche verletzt werden.

(ein)Aluminium &oder Kupfer &oder Eisen
(b)Aluminium &rArr grau
(c)Kupfer &und nichtbeschichtet &rArr rot
(d)beschichtet &und nichtKupfer &rArr Grün
(e)Grün &oder Blau &hArr &nichttexturiert &und nichtEisen

Aufgabe 2.4: Betrachten Sie die unten gezeigten Sätze. Es gibt hier drei Propositionskonstanten, was bedeutet, dass es acht mögliche Wahrheitszuordnungen gibt. Wie viele dieser Aufgaben erfüllen alle diese Sätze?

p &oder q &oder r
p &rArr q &und r
q &rArr &nichtr

Problem 2.5: Ein kleines Unternehmen stellt Widgets in einer Vielzahl von Bestandteilen (Aluminium, Kupfer, Eisen), Farben (Rot, Grün, Blau, Grau) und Oberflächen (matt, strukturiert, beschichtet) her. Obwohl es mehr als tausend mögliche Kombinationen von Widget-Features gibt, vermarktet das Unternehmen nur eine Teilmenge der möglichen Kombinationen. Die folgenden Sätze sind einige Einschränkungen, die die Möglichkeiten charakterisieren. Hier ist es Ihre Aufgabe, Materialien, Farben und Oberflächen so auszuwählen, dass alle der Produktbeschränkungen erfüllt sind. Beachten Sie, dass dies auf mehreren Wegen möglich ist.

Aluminium &oder Kupfer &oder Eisen
rot &oder Grün &oder Blau &oder grau
Aluminium &rArr grau
Kupfer &und nichtbeschichtet &rArr rot
Eisen &rArr beschichtet

Aufgabe 2.6: Betrachten Sie eine Aussagensprache mit drei Aussagekonstanten - Pilz, lila, und giftig - jedes mit Angabe der durch seine Schreibweise vorgeschlagenen Eigenschaft. Codieren Sie mit diesen Satzkonstanten die folgenden englischen Sätze als Sätze der Satzlogik.

(ein)Alle lila Pilze sind giftig.
(b)Ein Pilz ist nur giftig, wenn er lila ist.
(c)Ein Pilz ist nur dann giftig, wenn er lila ist.
(d)Kein lila Pilz ist giftig.

Aufgabe 2.7: Betrachten Sie die in Abschnitt 2.7 beschriebene digitale Schaltung. Angenommen, wir setzen Knoten p, q, und r sein auf, und wir beobachten, dass alle anderen Knoten auf. Beim Ausführen unseres Bewertungsverfahrens würden wir feststellen, dass der erste Satz in unserer Beschreibung der Schaltung nicht stimmt. Daher ist die Schaltung defekt. Gibt es eine Kombination von Eingängen? p, q, und r das würde dazu führen, dass alle anderen Knoten auf in einer korrekt funktionierenden Schaltung? Hinweis: Um dies zu beantworten, müssen Sie eine Wahrheitstabelle mit nur acht Zeilen betrachten (die möglichen Werte für Knoten p, q, und r), da alle anderen Knoten als auf.


1.2: Aussagen und Logik - Mathematik

Fast jeder kennt das Spiel Tic-Tac-Toe, bei dem die Spieler X und O auf einem Drei-mal-Drei-Raster markieren, bis ein Spieler drei hintereinander macht oder das Raster ohne Gewinner (ein Unentschieden) gefüllt wird. Die Regeln sind so einfach, dass Kinder im Alter von 3 oder 4 Jahren die Idee bekommen können.

Anfangs kann ein kleines Kind willkürlich spielen und das Raster markieren, ohne darüber nachzudenken, wie der andere Spieler reagieren könnte. Zum Beispiel könnte das Kind eifrig zwei hintereinander machen, aber nicht sehen, dass seine ältere Schwester in ihrem nächsten Zug drei hintereinander schaffen kann.

Erst im Alter von etwa 6 Jahren beginnen Kinder, Strategien zu entwickeln, indem sie die möglichen Bewegungen und Reaktionen ihres Gegners betrachten. Das Kind beginnt mit systematischem Denken oder was wir Logik nennen, um zu entscheiden, was im Spiel passiert, wenn ein Zug dem anderen vorgezogen wird.

Die damit verbundene Logik kann ziemlich komplex sein, insbesondere für ein kleines Kind. Angenommen, Sie sind an der Reihe (X) und das Raster sieht derzeit so aus. Wo sollst du spielen?

Ihr Denkprozess (oder das, was wir ein logisches Argument nennen) könnte in etwa so aussehen:

  • Es braucht drei in Folge, um das Spiel zu gewinnen.
  • Ich kann nicht drei in Folge machen, egal wo ich in diesem Zug spiele.
  • Wenn meine Gegnerin an der Reihe wäre, könnte sie drei in Folge machen, indem sie ein O in die obere linke Ecke setzt.
  • Wenn ich mein X nicht in die obere linke Ecke setze, hat mein Gegner die Möglichkeit, dort zu spielen.
  • Daher muss ich ein X in die obere linke Ecke setzen.

Da Sie viel erfahrener sind als das typische 6-jährige Kind, wette ich, dass Sie sofort gesehen haben, wo das X gespielt werden sollte, auch ohne alle oben aufgeführten Details zu durchdenken. Wenn Sie in Ihrer Kindheit eine ganze Reihe von Tic-Tac-Toe-Spielen gespielt haben, dann gibt es in Ihrem Gehirn neuronale Bahnen, die für die Tic-Tac-Toe-Logik fest verdrahtet sind, genau wie ein Computer schwierig sein könnte. verkabelt, um bestimmte Routineaufgaben zu erledigen.

Tatsächlich folgen Computer den Regeln der Logik durch Design. Bestimmte Komponenten, die als Gates bezeichnet werden, leiten Elektrizität auf verschiedene Weise durch die gesamte Schaltung des Computers, sodass dieser alle Vorgänge ausführen kann, für die er programmiert ist.

Egal, ob Sie versuchen, die siegreiche Tic-Tac-Toe-Strategie zu finden, ein gültiges Argument zusammenzustellen, um andere Gesetzgeber davon zu überzeugen, wichtige Mittel zu erhalten, oder leistungsstarke Computer zu entwickeln, um komplizierte Probleme zu lösen, Logik ist ein wesentlicher Bestandteil unserer Welt.


7. Wichtige metatheoretische Ergebnisse für die Aussagenkalküle

Hinweis: Dieser Abschnitt ist relativ technisch und richtet sich an ein Publikum mit Vorkenntnissen in Logik oder Mathematik. Anfänger können zum nächsten Abschnitt springen.

In diesem Abschnitt skizzieren wir informell die Beweise, die für einige wichtige Merkmale der Aussagenlogik gegeben wurden. Unser erstes Thema betrifft jedoch die Sprache PL’ im Allgemeinen.

Metatheoretisches Ergebnis 1: Die Sprache PL’ ist expressiv adäquat, das heißt im Kontext der klassischen bivalenten Logik gibt es keine Wahrheitsfunktionen, die in ihr nicht repräsentiert werden könnten.

Wir haben in Abschnitt III(c) festgestellt, dass die Konnektoren ‘‘, ‘↔’ und ‘‘ kann mit den Konnektoren von PL definiert werden’ (‘→’ und ‘‘). Allgemeiner gesagt besagt das metatheoretische Ergebnis 1, dass jede Aussage, die unter Verwendung von wahrheitsfunktionalen Konnektoren erstellt wurde, unabhängig davon, was diese Konnektoren sind, eine äquivalente Aussage hat, die nur mit ‘→’ und ‘ . gebildet wird‘. Hier ist der Beweis.

1. Nehmen Sie an, dass ist ein WFF, das in einer Sprache erstellt wurde und eine Reihe von wahrheitsfunktionalen Verknüpfungen enthält, einschließlich derer, die nicht in PL, PL’ oder PL” zu finden sind. Beispielsweise, könnte einige drei- oder vierstellige wahrheitsfunktionale Konnektoren oder Konnektoren wie das exklusive oder oder das Zeichen ‘ . verwenden‘ oder andere, die Sie sich vorstellen können.

2. Wir müssen zeigen, dass es ein wff . gibt nur mit den Konnektoren ‘→’ und ‘ . gebildet‘ das ist logisch äquivalent zu . Weil wir bereits gezeigt haben, dass Formen äquivalent zu denen aus ‘‘, ‘↔’ und ‘‘ kann aus ‘→’ und ‘ . aufgebaut werden‘, wir sind berechtigt, sie ebenfalls zu verwenden.

3. Damit es logisch äquivalent zu ist , die wff die wir konstruieren, muss den gleichen finalen Wahrheitswert für jede mögliche Wahrheitswertzuweisung zu den Aussagebuchstaben haben, die ihn bilden , oder mit anderen Worten, es muss dieselbe letzte Spalte in einer Wahrheitstabelle haben.

4. Lass seien Sie die unterschiedlichen Aussagebuchstaben, aus denen sich . Für einige mögliche Wahrheitswertzuordnungen zu diesen Buchstaben, mag wahr sein, und für andere kann falsch sein. Der einzige harte Fall wäre der, in dem ist kontingent. Wenn nicht kontingent waren, es muss entweder eine Tautologie oder ein Selbstwiderspruch sein. Da eindeutig Tautologien und Selbstwidersprüche in PL’ konstruiert werden können und alle Tautologien einander logisch äquivalent sind und alle Selbstwidersprüche einander äquivalent sind, ist unsere Aufgabe in diesen Fällen einfach. Nehmen wir stattdessen an, dass ist kontingent.

5. Konstruieren wir ein wff auf die folgende Weise.

(a) Betrachten Sie nacheinander jede Wahrheitswertzuordnung zu den Buchstaben . Konstruieren Sie für jede Wahrheitswertzuweisung eine Konjunktion aus den Buchstaben, die die Wahrheitswertzuweisung wahr macht, zusammen mit den Negationen dieser Buchstaben, die die Wahrheitswertzuweisung falsch macht. Wenn die betreffenden Buchstaben beispielsweise ‘ . sind‘, ‘‘ und ‘‘, und die Wahrheitswertzuweisung ergibt ‘‘ und ‘‘ wahr, aber ‘‘ false, betrachte die Konjunktion ‘‘.

(b) Bilden Sie aus den resultierenden Konjunktionen eine komplexe Disjunktion, die aus den in Schritt (a) gebildeten Konjunktionen gebildet wird, für die die entsprechende Wahrheitswertzuweisung wahr. Wenn beispielsweise die Wahrheitswertzuweisung ‘‘ und ‘‘ wahr, aber ‘‘ falsche Marken wahr, schließen Sie die Disjunktion ein. Nehmen wir zum Beispiel an, dass diese Wahrheitswertzuweisung wahr, ebenso wie die Zuweisung, in der ‘‘ und ‘‘ und ‘‘ werden alle falsch gemacht, aber keine andere Wahrheitswertzuweisung macht wahr. In diesem Fall wäre die resultierende Disjunktion ‘‘.

6. Die wff in Schritt 5 konstruiert ist logisch äquivalent zu . Bedenken Sie, dass für diese Wahrheitswertzuweisungen assignment stimmt, eine der Konjunktionen, aus denen die Disjunktion besteht wahr ist, und daher ist auch die ganze Disjunktion wahr. Für diese Wahrheitswertzuweisungen falsch, keine der Konjunktionen, aus denen ist wahr, da jede Konjunktion mindestens eine Konjunktion enthält, die bei dieser Wahrheitswertzuweisung falsch ist.

7. Weil wird nur mit ‘ . konstruiert‘, ‘‘ und ‘‘, und diese können wiederum nur mit ‘ . definiert werden‘ und ‘→’ und weil ist äquivalent zu , es gibt eine wff, die nur aus ‘ . aufgebaut ist‘ und ‘→’ das entspricht , unabhängig von den Konnektoren, aus denen .

8. Daher ist PL’ ausdrücklich ausreichend.

Folgerung 1.1: Sprache PL” ist auch ausdrucksvoll ausreichend.

Das Korollar folgt sofort aus dem metatheoretischen Ergebnis 1, zusammen mit der in Abschnitt III(c) festgestellten Tatsache, dass ‘→’ und ‘‘ kann nur mit ‘|’ definiert werden.

Metatheoretisches Ergebnis 2 (alias “The Deduction Theorem”): Im Aussagenkalkül PC, wann immer es gilt, dass , das gilt auch

Das bedeutet, dass immer dann, wenn wir ein gegebenes Ergebnis in PC mit einer bestimmten Anzahl von Prämissen beweisen können, es möglich ist, alle gleichen Prämissen mit Ausnahme einer Ausnahme zu verwenden, , um die bedingte Aussage aus der entfernten Prämisse zu beweisen, , als Vorläufer und Abschluss der ursprünglichen Ableitung, , als Konsequenz. Die Bedeutung dieses Ergebnisses besteht darin, dass es in der Tat zeigt, dass die Technik des bedingten Beweises, die typischerweise in der natürlichen Deduktion (siehe Abschnitt V) verwendet wird, in der PC unnötig ist, denn wann immer es möglich ist, die Konsequenz eines bedingten Beweises zu beweisen, indem man den Antezedens als zusätzliche Prämisse, kann eine direkte Ableitung für den Konditional gefunden werden, ohne den Antezedens als Prämisse zu nehmen.

1. Nehmen Sie an, dass . Dies bedeutet, dass eine Ableitung von im Aussagenkalkül aus den Prämissen . Diese Ableitung erfolgt in Form einer geordneten Folge , wobei das letzte Glied der Sequenz, , ist , und jedes Glied der Folge ist entweder (1) eine Prämisse, d. h. es ist eine von , (2) ein Axiom von PC, (3) abgeleitet von Bisherige Mitglieder der Sequenz von modus ponens.

2. Wir müssen zeigen, dass es eine Ableitung von gibt , die zwar möglicherweise die anderen Prämissen des Arguments nutzt, aber keinen Gebrauch macht . Wir tun dies, indem wir für jedes Mitglied zeigen, , der Reihenfolge der ursprünglichen Ableitung: , kann man ableiten ohne Gebrauch von als Prämisse.

3. Jeder Schritt in der Reihenfolge der ursprünglichen Ableitung wurde auf eine von drei Wegen erreicht, wie oben in (1) erwähnt. Egal mit welchem ​​Fall wir es zu tun haben, wir können das Ergebnis erzielen, dass . Es sind drei Fälle zu berücksichtigen:

Fall (a): Angenommen ist eine Prämisse des ursprünglichen Arguments. Dann ist entweder einer von oder es ist selbst. Im letzteren Unterfall möchten wir Folgendes erhalten: ohne Benutzung zu bekommen als Prämisse. weil ist eine Instanz von TS1, wir können sie ohne Verwendung abrufen irgendein Lokal. Beachten Sie im letzteren Fall, dass ist eine der Prämissen, die wir in der neuen Ableitung verwenden dürfen. Wir dürfen auch die Instanz von AS1 einführen. . Daraus können wir durch modus ponens.

Fall (b): Angenommen ist ein Axiom. Wir müssen zeigen, dass wir es schaffen können ohne zu benutzen als Prämisse. Tatsächlich können wir es bekommen, ohne es zu verwenden irgendein Lokal. weil ein Axiom ist, können wir es auch in der neuen Ableitung verwenden. Wie im letzten Fall haben wir als ein weiteres Axiom (eine Instanz von AS1). Aus diesen beiden Axiomen kommen wir zu durch modus ponens.

Fall (c): Angenommen, wurde von früheren Mitgliedern der Sequenz abgeleitet von modus ponens. Konkret gibt es einige und so dass beide j und k sind weniger als ich, und nimmt die Form an . Wir können davon ausgehen, dass wir bereits beides herleiten konnten -das ist, -und in der neuen Ableitung ohne Verwendung von . (Dies mag fragwürdig erscheinen, falls entweder oder wurde selbst erwischt modus ponens. Beachten Sie jedoch, dass dies die Annahme nur zurückdrängt und man schließlich zum Anfang der ursprünglichen Ableitung gelangt. Die ersten beiden Schritte der Sequenz, nämlich und , kann nicht abgeleitet worden sein von modus ponens, da dies voraussetzen würde, dass es zwei vorherige Mitglieder der Folge gegeben hat, was unmöglich ist.) In unserer neuen Ableitung haben wir also bereits beide und .
Beachte das ist eine Instanz von AS2 und kann daher in die neue Ableitung eingeführt werden. In zwei Schritten von modus ponens, wir kommen an , wieder ohne zu benutzen als Prämisse.

4. Wenn wir jeden Schritt der ursprünglichen Ableitung durchgehen, zeigen wir für jeden dieser Schritte , wir können bekommen ohne zu benutzen als Prämisse kommen wir schließlich zum letzten Schritt der ursprünglichen Ableitung, , welches ist selbst. Wenn wir das Verfahren aus Schritt (3) anwenden, erhalten wir das ohne Gebrauch von als Prämisse. Die so gebildete neue Ableitung zeigt daher, dass , was wir zu zeigen versuchten.

Das Interessante an diesem Beweis für das metatheoretische Ergebnis 2 ist, dass er bei einer Ableitung für ein bestimmtes Ergebnis, die eine oder mehrere Prämissen verwendet, ein Rezept bereitstellt, um diese Ableitung in eine bedingte Aussage umzuwandeln, in der eine der Prämissen des ursprünglichen Arguments ist zum Vorläufer geworden. Dies mag an einem Beispiel deutlicher werden.

Betrachten Sie die folgende Ableitung für das Ergebnis, dass :

1. Prämisse
2. AS1
3. 1,2 MP
4. AS2
5. 3,4 MP

Es ist möglich, die obige Ableitung in eine Ableitung umzuwandeln, die keine Prämissen verwendet und die zeigt, dass ist ein Theorem von PC. Das Verfahren für eine solche Transformation besteht darin, jeden Schritt der ursprünglichen Ableitung zu betrachten und für jeden zu versuchen, dieselbe Anweisung abzuleiten, nur beginnend mit ““, ohne Verwendung von “” als Voraussetzung. Wie dies geschieht, hängt davon ab, ob der Schritt eine Prämisse, ein Axiom oder ein Ergebnis von . ist modus ponens, und je nachdem, welches dies einer der drei im obigen Beweis skizzierten Verfahren ist. Das Ergebnis ist folgendes:

1. TS1
2. AS1
3. AS1
4. 2,3 MP
5. AS2
6. 4,5 MP
7. 1,6 MP
8. AS2
9. AS1
10. 8,9 MP
11. AS2
12. 10,11 MP
13. 7,12 MP

Das Verfahren zur Umwandlung einer Ableitungsart in eine andere ist reine Routine. Darüber hinaus ist das Ergebnis oft nicht die eleganteste oder einfachste Art, das zu zeigen, was Sie zeigen wollten. Beachten Sie beispielsweise, dass die Zeilen (2) und (7) überflüssig sind und mehr Schritte als nötig unternommen wurden. Das reine Auswendigverfahren ist jedoch effektiv.

Dieses metatheoretische Ergebnis geht auf Jacques Herbrand (1930) zurück.

Es ist für sich genommen interessant, besonders wenn man es als Ersatz oder Ersatz für die bedingte Beweistechnik betrachtet. Es ist jedoch auch sehr nützlich, um andere metatheoretische Ergebnisse zu beweisen, wie wir weiter unten sehen werden.

Metatheoretisches Ergebnis 3: Wenn ist ein wff der Sprache PL’, und die Anweisungsbuchstaben, aus denen es besteht, sind , wenn wir dann eine mögliche Wahrheitswertzuordnung zu diesen Buchstaben betrachten und die Menge der Prämissen betrachten, , das beinhaltet wenn die Wahrheitswertzuweisung wahr, aber enthält wenn die Wahrheitswertzuweisung false, und ähnlich für , wenn die Wahrheitswertzuweisung stimmt, dann gilt im PC das , und wenn es macht falsch, dann .

1. Nach der Definition eines wff, ist entweder selbst ein Statement-Buchstabe oder wird letztendlich aus den Statement-Buchstaben durch die Konnektoren ‘ . aufgebaut‘ und ‘→’.

2. Wenn selbst ein Aussagebuchstabe ist, dann ist er offensichtlich entweder oder seine Verneinung ein Mitglied von . Es ist Mitglied von wenn die Wahrheitswertzuweisung wahr macht. In diesem Fall gibt es offensichtlich eine Ableitung von von , da eine Prämisse jederzeit eingeführt werden kann. Wenn die Wahrheitswertzuweisung es stattdessen falsch macht, dann ist Mitglied von , und so haben wir eine Ableitung von von , da jederzeit wieder eine Prämisse eingeführt werden kann. Dies deckt den Fall ab, in dem unser wff einfach ein Erklärungsbrief ist.

3. Angenommen, ist aus einem anderen wff aufgebaut mit dem Zeichen ‘‘, das heißt, nehmen wir an, dass ist . Wir können davon ausgehen, dass wir bereits das gewünschte Ergebnis für . (Entweder ist ein Aussagebrief, in welchem ​​Fall das Ergebnis nach Schritt (2) gilt oder letztlich selbst aus Aussagebriefen aufgebaut ist. Selbst wenn die Überprüfung dieser Annahme eine ähnliche Annahme erfordert, werden wir letztendlich auf Aussagebriefe zurückkommen.) ist, wenn die Wahrheitswertzuweisung stimmt, dann haben wir eine Ableitung von von . Wenn es falsch ist, haben wir eine Ableitung von von . Angenommen, es macht wahr. Schon seit ist die Negation von , die Wahrheitswertzuweisung muss machen falsch. Wir müssen also zeigen, dass es eine Ableitung von gibt von . Schon seit ist , ist . Wenn wir an unsere Ableitung von anhängen von die Ableitung von , eine Instanz von TS2, können wir eine Ableitung von erreichen durch modus ponens, was erforderlich war. Nehmen wir stattdessen an, dass die Wahrheitswertzuweisung falsch, dann gibt es nach unserer Annahme eine Ableitung von von . Schon seit ist die Negation von , muss diese Wahrheitswertzuweisung machen wahr. Jetzt, einfach ist , also haben wir schon eine Ableitung davon von .

4. Nehmen wir stattdessen an, dass ist aus anderen wffs aufgebaut und mit dem Zeichen ‘→’, das heißt, nehmen wir an, dass ist . Auch hier können wir davon ausgehen, dass wir bereits das gewünschte Ergebnis für und . (Wiederum sind sie entweder selbst Aussagebriefe oder in gleicher Weise aus Aussagebriefen aufgebaut.) Angenommen, die von uns betrachtete Wahrheitswertzuordnung macht wahr. weil ist , nach der Semantik für das Zeichen ‘→’ muss die Wahrheitswertzuweisung entweder machen falsch oder wahr. Nehmen Sie den ersten Unterfall. Wenn es macht falsch, dann gibt es nach unserer Annahme eine Ableitung von von . Wenn wir hieran die Ableitung der Instanz von TS3 anhängen, , durch modus ponens wir kommen zur Ableitung von , das ist, , von . Wenn stattdessen die Wahrheitswertzuweisung wahr, dann gibt es nach unserer Annahme eine Ableitung von von . Wenn wir dieser Ableitung die Instanz von AS1 hinzufügen, , durch modus ponens, kommen wir dann wieder zu einer Ableitung von , das ist, , von . Wenn stattdessen die Wahrheitswertzuweisung falsch, dann seit ist , muss die fragliche Wahrheitswertzuweisung machen wahr und falsch. Nach unserer Annahme ist es dann möglich, beides zu beweisen und von . Wenn wir diese beiden Ableitungen verketten und ihnen die Ableitung der Instanz von TS4 hinzufügen, , dann durch zwei Anwendungen von modus ponens, können wir ableiten , das ist einfach , was gewünscht war.

Aus dem Obigen sehen wir, dass der Aussagenkalkül PC verwendet werden kann, um die geeigneten Ergebnisse für eine komplexe wff zu demonstrieren, wenn als Prämisse entweder die Wahrheit oder die Falschheit aller ihrer einfachen Teile gegeben ist. Dies ist natürlich die Grundlage der wahrheitsfunktionalen Logik, dass die Wahrheit oder Falschheit jener komplexen Aussagen, die man darin machen kann, vollständig durch die Wahrheit oder Falschheit der einfachen Aussagen bestimmt wird, die in sie eingehen. Das metatheoretische Ergebnis 3 ist für sich allein wieder interessant, spielt aber eine entscheidende Rolle beim Beweis der Vollständigkeit, dem wir uns als nächstes zuwenden.

Metatheoretisches Ergebnis 4 (Vollständigkeit): Wenn /> ein wff der Sprache PL’ und eine Tautologie ist, dann /> ist ein Theorem der Aussagenlogik.

Diese Eigenschaft des Aussagenkalküls heißt Vollständigkeit weil es zeigt, dass die Aussagenkalküle als deduktives System, das alle Wahrheiten der Logik erfassen soll, ein Erfolg ist. Jedes wff ist nur aufgrund der wahrheitsfunktionalen Natur der Konnektoren, aus denen es besteht, wahr, etwas, das man nur mit den Axiomen von PC beweisen kann modus ponens. Hier ist der Beweis:

1. Angenommen, ist eine Tautologie. Dies bedeutet, dass jede mögliche Wahrheitswertzuweisung zu ihren Aussagebuchstaben macht sie wahr.

2. Lassen Sie die Aussage Buchstaben ausmachen Sein , in einer bestimmten Reihenfolge angeordnet (sagen wir alphabetisch und nach der numerischen Reihenfolge ihrer Indizes). Aus (1) und dem metatheoretischen Ergebnis 3 folgt, dass in PC eine Ableitung von mit jede mögliche Menge von Räumlichkeiten das für jeden Aussagebuchstaben entweder aus ihm oder seiner Negation besteht.

3. Nach metatheoretischem Ergebnis 2 können wir aus jeder dieser Prämissenmengen entweder oder , je nachdem, was es enthält, und machen Sie es zu einem Vorläufer einer Bedingung, in der ist konsequent, und das Ergebnis wird ohne Verwendung beweisbar sein oder als Prämisse. Dies bedeutet, dass für jede mögliche Menge von Prämissen bestehend aus entweder oder und so weiter, bis , wir können beides ableiten und .

4. Das wff ist eine Instanz von TS5. Also für jede Menge von Prämissen, aus denen man beides ableiten kann und , durch zwei Anwendungen von modus ponens, kann man auch ableiten selbst.

5. Setzen wir (3) und (4) zusammen, erhalten wir das Ergebnis kann aus jeder möglichen Menge von Prämissen abgeleitet werden, bestehend aus entweder oder und so weiter, bis .

6. Wir können die gleichen Überlegungen wie in den Schritten (3)-(5) anwenden, um zu entfernen oder seine Negation aus den Prämissenmengen durch den Deduktionssatz, was zu dem Ergebnis führt, dass für jede Menge von Prämissen bestehend aus entweder oder und so weiter, bis , ist es möglich abzuleiten . Wenn wir diese Argumentation weiter anwenden, erhalten wir schließlich das Ergebnis, das wir ableiten können mit entweder oder seine Negation als unsere einzige Prämisse. Unter Anwendung des Deduktionssatzes bedeutet dies wiederum, dass beide und kann im PC ohne Verwendung nachgewiesen werden irgendein Prämissen, das heißt, sie sind Theoreme. Verketten der Ableitungen dieser Sätze, zusammen mit der Instanz von TS5, , und durch zwei Anwendungen von modus ponens, es folgt dem selbst ist ein Theorem, was wir zu demonstrieren versuchten.

Der obige Nachweis der Vollständigkeit des System-PC ist bei der Visualisierung leichter zu erkennen. Angenommen, nur zur Veranschaulichung, dass die Tautologie, die wir im System-PC demonstrieren möchten, drei Anweisungsbuchstaben hat, ‘‘, ‘‘ und ‘‘. Es gibt acht mögliche Wahrheitswertzuordnungen für diese Buchstaben, und da ist eine Tautologie, die alle machen wahr. Wir können zumindest so viel davon skizzieren ‘s Wahrheitstabelle:


1.2: Aussagen und Logik - Mathematik


Lehrer: Md. Tarek Habib
Büro: Raum Nr. 506, Ebene 5, CSE-Gebäude, Erweiterung des Narzissenturms
Handy # : 01709076951, 01559-024179
Email: [email protected]

Kursbegründung:

Dieser Kurs konzentriert sich auf mathematische Definitionen und Beweise sowie anwendbare Methoden zur Lösung und Analyse von Problemen, die in der Informatik auftreten. Es trainiert die Studierenden, die Fähigkeit zu entwickeln, quantitativ zu denken und Probleme kritisch zu analysieren.

Kursziele:

Mathematisches Denken: Um mathematische Argumente und Formeln aus mathematischem Denken und Logik zu konstruieren

Kombinatorische Analyse: Entwicklung von Fähigkeiten zur Problemlösung durch die Fähigkeit, Objekte zu zählen oder aufzuzählen

Algorithmisches Denken: Mathematische Methoden zur Entwicklung von Algorithmen verwenden

Anwendungen und Modellierung: Um mathematische Modelle auf Anwendungen in der Informatik anzuwenden.

Kursergebnisse:

Kann Rechenprobleme mit mathematischen Modellen lösen

Kann grundlegende mathematische Argumentationstechniken und logische Operationen für technische Probleme implementieren

Kann die Graphentheorie und andere mathematische Methoden sowohl auf Datenstrukturen als auch auf die Analyse von Algorithmen und einige andere analytische Probleme in der Informatik anwenden


Schau das Video: Discrete Math Applications of Propositional Logic (November 2021).