Aussagenlogik

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Aussagenlogik

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

--------------------------

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

Aussagenlogik

Stichpunkte

Allgemein
	Die Aussagenlogik
	ist ein Bereich der Logik
	der sich mit der logischen Bewertung von Aussagen befasst
	auch (veraltet) Urteilslogik
	Dabei werden Elementaraussagen durch Junktoren verknÃ¼pft
	Die Struktur der Elementaraussagen wird nicht untersucht
	Dies leistet die PrÃ¤dikatenlogik. Dieser Artikel befasst sich mit der klassischen Aussagenlogik
	in der der Satz vom ausgeschlossenen Dritten (also das "Tertium non datur") gilt: Jede Aussage ist entweder wahr oder falsch
	ist das nicht zwingend der Fall
	Von einem konstruktivischen Standpunkt gesehen
	der den Begriff "wahr" etwa im Sinne von "beweisbar" versteht
	Dieser Standpunkt findet seinen Ausdruck in Systemen der intuitionistischen Aussagenlogik
	"Verbergen") 1 Umgangssprachliche Einleitung 1.1 Einfache Aussage (Elementaraussage) 1.2 Verneinte Aussage - Negation 1.3 und-verknÃ¼pfte Aussagen - Konjunktion 1.4 oder-verknÃ¼pfte Aussagen - Disjunktion 1.5 Folgerungen - Implikation bzw
	Siehe hierzu auch den Artikel Dialogische Logik. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Subjunktion 1.6 Gleichwertige Aussagen - Ã„quivalenz 1.7 Verneinung einer und-verknÃ¼pften Aussage 1.8 Verneinung einer oder-verknÃ¼pften Aussage 1.9 Die Verneinung der Ã„quivalenz - die Antivalenz oder Kontravalenz 1.10 Die Begriffe "notwendig" und "hinreichend" 2 Formaler Zugang 2.1 Einleitung 2.2 Syntax 2.2.1 AbkÃ¼rzungen 2.3 Semantik/Aussagen 3 ErfÃ¼llbarkeit 4 Siehe auch [Bearbeiten]
Umgangssprachliche Einleitung
	[Bearbeiten]
Einfache Aussage (Elementaraussage)
	der entweder wahr (w
	true) oder nicht wahr (f
	false) ist
	wahr
	falsch
	Eine Aussage A ist ein Satz
	Dies gilt sowohl fÃ¼r einfache als auch fÃ¼r verknÃ¼pfte Aussagen. "Halbwahrheiten" gibt es nicht
	Eine Aussage kann sowohl der gewÃ¶hnlichen Sprache entstammen als auch der Sprache der Mathematik
	kann man derzeit nicht entscheiden
	ob <math>A_1<math> wahr oder falsch ist. Ob <math>A_3<math> wahr ist
	bevor man entscheiden kann
	<math>A_4<math> dagegen ist falsch. <math>A_1<math> muss man zunÃ¤chst prÃ¼fen
	Beispiele fÃ¼r einfache Aussagen: <math>A_1<math>: MÃ¼nchen ist 781 km von Hamburg entfernt. <math>A_2<math>: 9 ist durch 3 teilbar. <math>A_3<math>: Kaiserslautern wird in dieser Saison deutscher FuÃŸballmeister. <math>A_4<math>: Alle Autos sind grÃ¼n. <math>A_2<math> ist offensichtlich wahr
	Das wird sich erst am Ende der FuÃŸballsaison herausstellen
	den Wahrheitsgehalt zu beurteilen
	auch wenn man (noch) nicht in der Lage ist
	In der klassischen Aussagenlogik ist eine Aussage entweder wahr oder nicht wahr
	Dies ist zum Beispiel bei den ungelÃ¶sten mathematischen Problemen der Fall
	Anmerkung: <math>A_4<math> ist eine All-Aussage; die Struktur solcher Aussagen ist Gegenstand der PrÃ¤dikatenlogik
	Im Sinne der Aussagenlogik ist es eine Elementaraussage. [Bearbeiten]
Verneinte Aussage - Negation
	dass man der Aussage A das Wort nicht geeignet einfÃ¼gt
	Das Gegenteil bzw. die Verneinung einer Aussage A erhÃ¤lt man immer dadurch
	Formal schreibt man fÃ¼r "nicht A" Â¬A
	auf Englisch und in der Schaltalgebra auch "NOT A". <math>A<math> <math>neg A<math> falsch wahr wahr falsch Wir verneinen die obigen Beispiele: <math>neg A_1<math>: MÃ¼nchen ist nicht 781 km von Hamburg entfernt. <math>neg A_2<math>: 9 ist nicht durch 3 teilbar <math>neg A_3<math>: Kaiserslautern wird in dieser Saison nicht deutscher FuÃŸballmeister. <math>neg A_4<math>: Nicht alle Autos sind grÃ¼n
	Es kann durchaus grÃ¼ne Autos geben und es gibt auch Autos
	dann ist die Verneinung <math>neg A<math> wahr. Eine Aussage <math>A<math> kann nicht gleichzeitig wahr und falsch sein. Die Aussagen <math>A<math> und <math>neg A<math> kÃ¶nnen nicht gleichzeitig wahr sein. [Bearbeiten]
	dann ist die Verneinung <math>neg A<math> falsch. Wenn eine Aussage <math>A<math> falsch ist
	die nicht grÃ¼n sind. Allgemein gilt fÃ¼r die Verneinung: Wenn eine Aussage <math>A<math> wahr ist
und-verknÃ¼pfte Aussagen - Konjunktion
	wenn entweder A oder B oder beide Aussagen falsch sind. <math>A<math> <math>B<math> <math>A and B<math> falsch falsch falsch falsch wahr falsch wahr falsch falsch wahr wahr wahr Beispiele fÃ¼r eine und-VerknÃ¼pfung: A: 9 ist duch 3 teilbar B: 9 ist eine Quadratzahl Diese Teilaussagen und ihre Negationen werden nun durch <math>and<math> miteinander verknÃ¼pt: <math>C_1<math>: 9 ist durch 3 teilbar und 9 ist eine Quadratzahl. <math>C_2<math>: 9 ist nicht durch 3 teilbar und 9 ist eine Quadratzahl. <math>C_3<math>: 9 ist durch 3 teilbar und 9 ist keine Quadratzahl. <math>C_4<math>: 9 ist nicht durch 3 teilbar und 9 ist keine Quadratzahl. Nur <math>C_1 = A and B<math> ist wahr
	weil <math>A<math> wahr ist und auch <math>B<math> wahr ist. <math>C_2 = neg A and B<math> ist falsch
	wenn sowohl A als auch B jeweils wahr sind. Andernfalls ist C falsch
	Man kann zwei Aussagen A und B durch das Wort und (Schreibweise: <math>and<math>) miteinander verknÃ¼pfen. Dadurch erhÃ¤lt man eine neue Aussage <math>C<math>. Sprechweise: A und B Schreibweise: <math>A and B<math> auf Englisch und in der Schaltalgebra auch A AND B Die Aussage C ist immer dann wahr
	weil <math>neg A<math> falsch ist. <math>C_3 = A and neg B<math> ist falsch
	nÃ¤mlich dann
	weil <math>neg B<math> falsch ist. <math>C_4 = neg A and neg B<math> ist falsch
	weil sowohl <math>neg A<math> als auch <math>neg B<math> falsch ist. [Bearbeiten]
oder-verknÃ¼pfte Aussagen - Disjunktion
	Man kann 2 Aussagen A und B durch das Wort oder miteinander verknÃ¼pfen und erhÃ¤lt so eine neue Aussage C
	bzw. wenn beide Teilaussagen wahr sind
	Achtung! Das logische oder hat eine andere Bedeutung als das umgangssprachliche "oder"
	wenn mindestens eine der Teilaussagen A oder B wahr ist
	das meist im Sinne von "entweder ... oder" benutzt wird. Sprechweise: "A oder B"; genauer: "A oder auch B" Schreibweise: <math>A vee B<math> auf Englisch und in der Schaltalgebra auch A OR B Die Aussage C ist immer dann wahr
	Andernfalls ist C falsch
	weil sowohl <math>A<math> als auch <math>B<math> wahr sind. <math>C_6 = neg A vee B<math> ist wahr
	weil <math>A<math> wahr ist. [Bearbeiten]
	weil <math>B<math> wahr ist. <math>C_7 = A vee neg B<math> ist wahr
	weil <math>neg A<math> falsch ist und auch <math>neg B<math> falsch ist. <math>C_5 = A vee B<math> ist wahr
	wenn sowohl A als auch B falsch sind. <math>A<math> <math>B<math> <math>A vee B<math> falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr wahr Beispiel fÃ¼r eine oder-VerknÃ¼pfung: A: 9 ist duch 3 teilbar B: 9 ist eine Quadratzahl Diese Teilaussagen und ihre Negationen werden nun durch <math>vee<math> miteinander verknÃ¼pt: <math>C_5<math>: 9 ist durch 3 teilbar oder 9 ist eine Quadratzahl. <math>C_6<math>: 9 ist nicht durch 3 teilbar oder 9 ist eine Quadratzahl. <math>C_7<math>: 9 ist durch 3 teilbar oder 9 ist keine Quadratzahl. <math>C_8<math>: 9 ist nicht durch 3 teilbar oder 9 ist keine Quadratzahl. Nur <math>C_8 = neg A vee neg B<math> ist falsch
	nÃ¤mlich dann
Folgerungen - Implikation bzw. Subjunktion
	so spricht man von einer Subjunktion. <math>A rightarrow B<math> <math>A<math> <math>B<math> <math>A rightarrow B<math> falsch falsch wahr falsch wahr wahr wahr falsch falsch wahr wahr wahr Sprechweisen: Aus A folgt B Unter der Voraussetzung A gilt B A impliziert B Wenn A gilt
	also ist n teilbar durch 3. Aus einer wahren Folgerung <math>A Rightarrow B<math> kann man eine weitere wahre Folgerung ableiten
	wird die unÃ¼berdachte StraÃŸe nass. Wenn Person x einen Wagen der Marke BMW hat
	Wenn man aus einer wahren Aussage A schlieÃŸen kann
	dass dann auch die Aussage B wahr ist
	nÃ¤mlich <math>neg B Rightarrow neg A<math>
	dann hat x ein Auto. n ist teilbar durch 6
	spricht man von einer Implikation. Schreibweise: <math>A Rightarrow B<math> Ist man noch wÃ¤hrend des Dialogs in der Aussagenlogik
	dann gilt auch B Aussage B ist notwendig fÃ¼r Aussage A (siehe Abschnitt "notwendig und hinreichend") Aussage A ist hinreichend fÃ¼r Aussage B (siehe Abschnitt "notwendig und hinreichend") Beispiele: Wenn es regnet
	kann es nicht geregnet haben. Wenn x kein Auto hat
	kann x keinen Wagen der Marke BMW haben. Wenn n nicht durch 3 teilbar ist
	kann n nicht durch 6 teilbar sein. Umgangssprachlich lÃ¤sst man sich gelegentlich zu weiteren - falschen - Aussagen verleiten: Weil es nicht regnete
	kann die StraÃŸe nicht nass sein
	FÃ¼r die Beispiele bedeutet dies: Wenn die unÃ¼berdachte StraÃŸe nicht nass ist
	also hat x kein Auto. falsch
	denn er kÃ¶nnte ja einen Mercedes haben n ist nicht durch 6 teilbar
	da die StraÃŸe auch aus anderen GrÃ¼nden nass werden kann (Rohrbruch
	also ist n auch nicht durch 3 teilbar.Auch diese Folgerung ist falsch
	Diese Folgerung ist falsch
	Ãœbung der Feuerwehr ...). x hat keinen Wagen der Marke BMW
	dann erhÃ¤lt man aus der Aussage Â¬A keine Aussage Ã¼ber B; B kann wahr oder falsch sein. ("Ex falso quolibet" - "Aus Falschem - was du willst") Die Implikation ist ein wichtiges Mittel in der Mathematik
	Die Zahl 15 ist nicht durch 6 teilbar und sehr wohl durch 3. Das bedeutet: Wenn die Folgerung <math>A Rightarrow B<math> wahr ist
	Die meisten mathematischen SÃ¤tze sind eine Implikation. [Bearbeiten]
Gleichwertige Aussagen - Ã„quivalenz
	wenn n durch 2 und durch 3 teilbar ist.Wenn n durch 6 teilbar ist
	dann folgt daraus
	wenn gilt: <math>A Rightarrow B<math> und umgekehrt <math>B Rightarrow A<math>. <math>A<math> <math>B<math> <math>A Leftrightarrow B<math> falsch falsch wahr falsch wahr falsch wahr falsch falsch wahr wahr wahr Schreibweise: <math>A Leftrightarrow B<math> Sprechweisen: Aussage A ist Ã¤quivalent zu Aussage B. A ist genau dann (dann und nur dann) wahr
	wenn auch B wahr ist. A ist notwendig und hinreichend fÃ¼r B. (siehe Abschnitt "notwendig und hinreichend") Beispiel: Die ganze Zahl n ist genau dann durch 6 teilbar
	Zwei Aussagen A und B sind Ã¤quivalent
	dass n durch 2 und durch 3 teilbar ist
	Umgekehrt gilt aber auch: Wenn n durch 2 und durch 3 teilbar ist
	wenn Morgen Mittwoch ist. [Bearbeiten]
	dann ist n durch 6 teilbar. Heute ist genau dann Dienstag
Verneinung einer und-verknÃ¼pften Aussage
	Die Verneinung zu der Aussage "A und B"
	also <math>neg(A and B)<math>ist gleichwertig mit der oder-verknÃ¼pften Aussage <math>(neg A) vee (neg B)<math>Auf Englisch und in der Schaltalgebra schreibt man dafÃ¼r A NAND B (not-and). <math>A<math> <math>B<math> <math>neg(A and B)<math> falsch falsch wahr falsch wahr wahr wahr falsch wahr wahr wahr falsch Beispiel:Aussage A: Die ganze Zahl n ist durch 2 teilbar.Aussage B: Die ganze Zahl n ist durch 3 teilbar
	Aussage "A und B": n ist durch 2 und durch 3 teilbar
	Verneinung: n ist nicht durch 2 und durch 3 teilbar. Dies besagt dasselbe wie: n ist nicht durch 2 teilbar
	oder n ist nicht durch 3 teilbar [Bearbeiten]
Verneinung einer oder-verknÃ¼pften Aussage
	also <math>neg(A vee B)<math>ist gleichwertig mit der und-verknÃ¼pften Aussage <math>(neg A) and (neg B)<math>Auf Englisch und in der Schaltalgebra schreibt man dafÃ¼r A NOR B (not-or). <math>A<math> <math>B<math> <math>neg(A vee B)<math> falsch falsch wahr falsch wahr falsch wahr falsch falsch wahr wahr falsch Beispiel:Aussage A: Die ganze Zahl n ist durch 2 teilbar.Aussage B: Die ganze Zahl n ist durch 3 teilbar
	Die Verneinung zu der Aussage "A oder B"
	Aussage "A oder B": n ist teilbar durch 2 oder auch teilbar durch 3
	Verneinung: n weder durch 2 noch durch 3 teilbar. Dies besagt dasselbe wie: n ist nicht durch 2 und auch nicht durch 3 teilbar [Bearbeiten]
Die Verneinung der Ã„quivalenz - die Antivalenz oder Kontravalenz
	<math>A<math> <math>B<math> <math>neg(A Leftrightarrow B)<math> falsch falsch falsch falsch wahr wahr wahr falsch wahr wahr wahr falsch Durch die Verneinung einer Ã„quivalenz-Aussage <math>A Leftrightarrow B<math> erhÃ¤lt man eine Antivalenz-Aussage <math>neg(A Leftrightarrow B) <math>.In Englisch und in der Schaltalgebra schreibt man dafÃ¼r A XOR B (eXclusiv-or)
	Sprechweisen: Aussage A ist antivalent zu Aussage B
	Aussage A ist kontravalent zu Aussage B
	wenn entweder nur A oder nur B wahr ist
	Entweder es gilt Aussage A oder es gilt Aussage B. Antivalenz ist dann gegeben
	oder n ist nicht durch 6 teilbar. Heute ist entweder Dienstag oder Mittwoch. [Bearbeiten]
	Angewandt auf die Beispiele: Die ganze Zahl n ist entweder durch 2 und durch 3 teilbar
Die Begriffe "notwendig" und "hinreichend"
	Betrachten wir die Implikation <math>ARightarrow B<math> Man sagt: B ist notwendig fÃ¼r A
	Ohne B kann A nicht erfÃ¼llt sein
	Ferner ist A hinreichend fÃ¼r B
	Es reicht aus
	dass A wahr ist
	Dann ist auch B wahr
	Beispiel 1: Ist n durch 6 teilbar
	dann ist n auch durch 3 teilbar. Teilbarkeit durch 3 ist notwendig fÃ¼r die Teilbarkeit von 6
	Wenn n nicht durch 3 teilbar ist
	dann kann n auch nicht durch 6 teilbar sein
	Teilbarkeit durch 6 ist hinreichend fÃ¼r die Teilbarkeit durch 3
	dass n auch durch 3 teilbar ist
	dass n durch 6 teilbar ist
	Wenn man weiÃŸ
	dann reicht dies aus
	um zu wissen
	dennoch nicht hinreichend fÃ¼r die Teilbarkeit durch 6
	Teilbarkeit durch 3 ist zwar notwendig
	hat x ein Auto. Man muss Besitzer eines Autos sein
	d.h. es ist notwendig
	9 ist durch 3 teilbar (notwendige Bedingung erfÃ¼llt) und 9 ist nicht teilbar durch 6. Beispiel 2: Wenn x einen BMW hat
	um Ã¼berhaupt einen BMW besitzen zu kÃ¶nnen
	kann man nicht gleichzeitig einen BMW haben
	da man ja andernfalls ein Auto hÃ¤tte
	Hat man kein Auto
	der Besitzer eines BMW zu sein
	wenn n durch 3 teilbar und gerade ist. Die Aussage "n ist durch 3 teilbar und n ist gerade" ist notwendig und hinreichend fÃ¼r die Teilbarkeit durch 6. Mehr Ã¼ber "notwendig" und "hinreichend" (http://www.ct-webspace.de/notwendigHinreichend/notwendigHinreichend.html) [Bearbeiten]
	um mit Wahrheit sagen zu kÃ¶nnen
	Es ist allerdings hinreichend
	man habe ein Auto. Beispiel 3: n ist genau dann durch 6 teilbar
Formaler Zugang
	[Bearbeiten]
Einleitung
	was das soll
	SpÃ¤testens beim lauten Lesen von SÃ¤tzen wie: "Die Aussage A&and;B ist genau dann wahr
	wird der selbstbewusste Laie verlangen
	dass ihm erklÃ¤rt wird
	wenn die Aussagen A und B wahr sind"
	Sicherheit in die Regeln des logischen SchlieÃŸens zu bringen
	Die Antwort des Logikers: Es soll versucht werden
	dass scheinbar zwingende SchlÃ¼sse zu offensichtlich absurden Ergebnisse fÃ¼hren kÃ¶nnen
	Seit den Sophisten ist dem Abendland klar
	Immer wieder wurden Paradoxien formuliert und von groÃŸen Denkern als Herausforderung empfunden
	Logiker versuchen deshalb
	die Regeln des Argumentierens so streng wie mÃ¶glich zu fassen
	dass hierzu eine Trennung der Sprachebenen unerlÃ¤sslich ist: Die formale Aussage A&and;B soll dadurch erklÃ¤rt werden
	Das einleitende Beispiel macht klar
	dass auf einer metasprachlichen Ebene Ã¼ber die Aussage A wie auch Ã¼ber die Aussage B geredet wird
	Ein Versuch dies durchzufÃ¼hren
	die Aussagenlogik als formales System zu definieren
	besteht darin
	Die Begriffe "wahr" und "falsch" kommen in diesem System zunÃ¤chst Ã¼berhaupt nicht vor
	Statt dessen werden Axiome gesetzt
	aus denen weitere "herleitbare" Zeichenketten aufgrund von bestimmten Schlussregeln hergeleitet werden
	die einfach als Zeichenketten angesehen werden
	dass in einem formalen System nur Zeichenketten (SÃ¤tze) hergeleitet werden kÃ¶nnen
	die bei einer plausiblen Interpretation auch wahr sind
	NatÃ¼rlich ist das Ziel dabei
	Andererseits sollen alle SÃ¤tze
	auch hergeleitet werden kÃ¶nnen
	die als "wahr" interpretierbar sind
	das zweite die nach VollstÃ¤ndigkeit des formalen Systems
	Das erste ist die Forderung nach Konsistenz
	mit der wir es hier zu tun haben
	Bei der klassischen Aussagenlogik
	ist dieses Problem gelÃ¶st
	Das hÃ¤ngt damit zusammen
	dass sich auf dieser Ebene der Logik auch keine Paradoxien formulieren lassen. [Bearbeiten]
Syntax
	wedge
	(
	neg
	) } = empty<math> Nenne V die Menge der atomaren Formeln
	Formale Definition aussagenlogischer Formeln Sei V eine abzÃ¤hlbare unendliche Menge mit der Eigenschaft: <math>V cap { vee
	(
	) }<math>und induktiv definiert: alle atomaren Formeln <math>F in V<math> sind Formeln ist F eine Formel
	neg
	so sind auch <math>(F wedge G) <math> und <math>(F vee G)<math> Formeln keine anderen WÃ¶rter (die sich nicht Ã¼ber diese Definition herleiten lassen) sind aussagenlogische Formeln <math> neg F<math> heiÃŸt Negation von F <math>(F wedge G) <math> heiÃŸt Konjunktion (und) von F und G <math>(F vee G)<math> heiÃŸt Disjunktion (oder) von F und G [Bearbeiten]
	so ist auch <math> neg F<math> eine Formel sind F und G zwei Formeln
	Eine aussagenlogische Formel wird definiert als Wort Ã¼ber dem Alphabet <math>V cup { vee
	wedge
AbkÃ¼rzungen
	<math>(F_1 rightarrow F_2) = ( neg F_1 vee F_2 )<math> (Implikation oder Subjunktion wenn ... dann...
	dass diese Ã„quivalenz bei der intuitionistischen Interpretation der Subjunktion nicht gilt! Siehe auch Dialogische Logik) <math>(F_1 leftrightarrow F_2) = ( F_1 wedge F_2 ) vee ( neg F_1 wedge neg F_2 ) <math> (Ã„quivalenz oder Bisubjunktion ... genau dann wenn ...) [Bearbeiten]
	wobei zu berÃ¼cksichtigen ist
Semantik/Aussagen
	die als wahr oder falsch bestimmt werden kÃ¶nnen
	Als Aussagen gelten SÃ¤tze
	Diese werden als logische Aussagen bezeichnet
	d.h. dem SchlieÃŸen von Voraussetzungen (PrÃ¤missen) auf eine Schlussfolgerung (Konklusion)
	Die Aussagenlogik beschÃ¤ftigt sich mit dem korrekten Folgern
	In der klassischen Aussagenlogik muss der Aussage dabei entweder wahr oder falsch zugeordnet werden
	tertium non datur). Es kÃ¶nnen auch aussagenlogische Sprachen definiert werden
	die mit weniger Operatoren arbeiten
	d.h. es gibt nur zwei Werte (Zweiwertigkeitsprinzip
	um alle booleschen Funktionen nachbilden zu kÃ¶nnen
	d.h. die vorhandenen Operatoren mÃ¼ssen mÃ¤chtig genug sein
	Eine solche Sprache muss funktional vollstÃ¤ndig sein
	die negierte Konjunktion) und NOR (Nicht-Oder
	die negierte Disjunktion)
	Es gibt zwei Operatoren
	mit denen alleine schon eine Aussagenlogik definiert werden kann: NAND (Nicht-Und
	d.h. fÃ¼r alle Belegungen ihrer Variablen
	heiÃŸen Tautologien
	Aussagen
	Aussagen
	die fÃ¼r alle Belegungen falsch sind (z.B. p und Â¬p)
	heiÃŸen Kontradiktionen
	wahr sind (z.B. p oder Â¬p)
	die immer
	Die Aussagenlogik ist eine AusprÃ¤gung der Booleschen Algebra
	Der nÃ¤chste komplexere Logikformalismus ist die PrÃ¤dikatenlogik. [Bearbeiten]
ErfÃ¼llbarkeit
	ist fÃ¼r allgemeine Formeln nicht effizient lÃ¶sbar
	Die Feststellung
	ob eine Aussage/Formel erfÃ¼llbar - oder eine Tautologie ist
	Bei einer Formel mit n atomaren Formeln sind <math>2^n<math> Belegungen zu Ã¼berprÃ¼fen (mittels Brute Force und Wahrheitstabellen)
	Das ErfÃ¼llbarkeitsproblem ist NP-vollstÃ¤ndig
	Es gibt allerdings optimierte Algorithmen
	die dieses Problem relativ schnell fÃ¼r Horn-Formeln oder fÃ¼r Formeln in KNF (Konjunktive Normalform) lÃ¶sen kÃ¶nnen
	Eine ausfÃ¼hrliche Beschreibung findet sich im Artikel ErfÃ¼llbarkeitsproblem der Aussagenlogik. [Bearbeiten]
Siehe auch
	Elementaraussage PrÃ¤dikatenlogik Wahrheitstabelle Schlussregel Boolesche Funktion Wahrheitswertefunktion Formelsammlung Logik en:Propositional calculus et:Lauseloogika fr:Calcul des propositions hu:Ã?tÃ©letlogika zh:å½¢å¼?é€»è¾‘

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Aussagenlogik aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

Autopoiese A.A. Autoren/A Autoren/H Autoren/C Autoren/I Autoren/K Autoren/J Autoren/V Autoren/G

[ Zurück ]

Inhalt Lexikon:

Allgemein

Umgangssprachliche Einleitung

Einfache Aussage (Elementaraussage)

Verneinte Aussage - Negation

und-verknÃ¼pfte Aussagen - Konjunktion

oder-verknÃ¼pfte Aussagen - Disjunktion

Folgerungen - Implikation bzw. Subjunktion

Gleichwertige Aussagen - Ã„quivalenz

Verneinung einer und-verknÃ¼pften Aussage

Verneinung einer oder-verknÃ¼pften Aussage

Die Verneinung der Ã„quivalenz - die Antivalenz oder Kontravalenz

Die Begriffe "notwendig" und "hinreichend"

Formaler Zugang

Einleitung

Syntax

AbkÃ¼rzungen

Semantik/Aussagen

ErfÃ¼llbarkeit

Siehe auch