imported>Alfred Heiligenbrunner: /* Verknüpfungen zweier Aussagen */ Benennung der fehlenden 6 Funktionen

2025-08-04T10:39:13Z

Verknüpfungen zweier Aussagen: Benennung der fehlenden 6 Funktionen

Neue Seite

Dies ist eine '''Formelsammlung''' zum mathematischen Teilgebiet der [[Mathematische Logik|Logik]].

== [[Aussagenlogik]] ==
Logische Werte:
* wahr (true) 1
* falsch (false) 0
Erweiterte Logik:
* unbestimmt ([[Don’t-Care]]) X

[[Aussage (Logik)|Aussagen]] können durch [[Logischer Operator|logische Operatoren]], auch [[Junktor]]en genannt, verknüpft werden. Die üblichen Junktoren sind:

{| class="wikitable"
! Name
! Symbol
! sprachliche Umschreibung
! Operation
! Definition
|-
| Negator ||<math>\neg</math>|| nicht || Negation || Die Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist.
|-
| Konjunktor ||<math>\land</math>|| und || Konjunktion || Die Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind.
|-
| Disjunktor ||<math>\lor</math>|| oder || Disjunktion || Die Disjunktion von zwei Werten ist genau dann wahr, wenn mindestens ein Wert wahr ist.
|}

Um die Symbole des Konjunktors und des Disjunktors leicht auseinanderhalten zu können, gibt es die Eselsbrücke mit den drei O: „Oder ist Oben Offen.“ Alternativ merkt man sich "'''A'''nd" (Englisch) für und, sowie "'''v'''el" (Latein) für oder.

=== Verknüpfungen zweier Aussagen ===
{| class="wikitable"
! rowspan=3 colspan=2 | Name
! rowspan=3 | sprachliche Umschreibung
! colspan=2 | äquivalente Darstellungen
! colspan=4 | [[Wahrheitstabelle]]
! rowspan=3 | [[Logikgatter|Logikgatter]]
|-
! rowspan=2 | durch Negator, Konjunktor und Disjunktor
! rowspan=2 | durch andere Junktoren
! colspan=2 | A=1
! colspan=2 | A=0
|-
! B=1
! B=0
! B=1
! B=0
|-
| colspan=2 | [[Konjunktion (Logik)|Konjunktion]] || A und B ||<math>A \land B</math>||<math>\neg(B \to \neg A)</math>
| 1 || 0 || 0 || 0 || [[Und-Gatter|AND]]
|-
| colspan=2 | Exklusion, [[Gegensatz#Der kontradiktorische, konträre, subkonträre und subalterne Gegensatz (logisches Quadrat)|konträrer Gegensatz]] || nicht zugleich A und B ||<math>\neg ( A \land B)</math>, <math>\neg A \lor \neg B</math>||<math>A \mid B</math>, <math>A \to \neg B</math>, <math>B \to \neg A</math>|| 0 || 1 || 1 || 1 || [[NAND-Gatter|NAND]]
|-
| colspan=2 | [[Disjunktion]] || A oder B (oder beide) ||<math>A \lor B</math>||<math>\neg A \to B</math>, <math>\neg B \to A</math>|| 1 || 1 || 1 || 0 || [[Oder-Gatter|OR]]
|-
| colspan=2 | Nihilition, Rejektion || weder A noch B ||<math>\neg ( A \lor B )</math>, <math>\neg A \land \neg B</math>|| || 0 || 0 || 0 || 1 || [[NOR-Gatter|NOR]]
|-
| colspan=2 | [[Kontravalenz]], [[Gegensatz#Der kontradiktorische, konträre, subkonträre und subalterne Gegensatz (logisches Quadrat)|kontradiktorischer Gegensatz]] || entweder A oder B ||<math>(A \land \neg B) \lor (\neg A \land B)</math>, <math>(A \lor B) \land (\neg A \lor \neg B)</math>||<math>A \veebar B</math>, <math>\neg(A \leftrightarrow B)</math>|| 0 || 1 || 1 || 0 || [[Exklusiv-Oder-Gatter|XOR]]
|-
| colspan=2 | [[Bikonditional]], Bisubjunktion, materiale Äquivalenz || B dann und nur dann, wenn A; genau dann B, wenn A ||<math>(A \land B) \lor (\neg A \land \neg B)</math>, <math>(A \lor \neg B) \land (\neg A \lor B)</math>||<math>(A \leftrightarrow B)</math>, <math>(A \to B) \land (B \to A)</math>|| 1 || 0 || 0 || 1 || [[XNOR-Gatter|XNOR]]
|-
| rowspan="2" | Konditional, [[Subjunktion]], materiale Implikation || Implikation || wenn A, dann B ||<math>\neg A \lor B</math>||<math>A \to B</math>, <math>\neg B \to \neg A</math>|| 1 || 0 || 1 || 1 || rowspan="2" |
|-
| Replikation || wenn B, dann A ||<math>\neg B \lor A</math>||<math>B \to A</math>, <math>\neg A \to \neg B</math>|| 1 || 1 || 0 || 1
|-
| rowspan="2" | Inhibition || Postsektion || A und nicht B ||<math>A \land \neg B</math>||<math>\neg (A \to B)</math>|| 0 || 1 || 0 || 0 || rowspan="2" |
|-
| Präsektion || B und nicht A ||<math>B \land \neg A</math>||<math>\neg (B \to A)</math>|| 0 || 0 || 1 || 0
|}

Insgesamt sind 16 Funktionen mit zwei Input-Variablen möglich. Zu den genannten zehn Funktionen kommen noch die eher uninteressanten Funktionen konstant_0, konstant_1, <math>A, \neg A, B, \neg B</math> dazu.

=== Logische Grundgesetze ===
{| class="wikitable"
|-
| [[Gesetz der doppelten Negation]]
| colspan="2" |<math>x \leftrightarrow \neg (\neg x)</math>
|-
| [[Kommutativgesetz#Aussagenlogik|Kommutativgesetze]] || <math>x \land y \leftrightarrow y \land x</math> || <math>x \lor y \leftrightarrow y \lor x</math>
|-
| [[Assoziativgesetz]]e || <math>x \land ( y \land z )\leftrightarrow(x \land y) \land z</math> || <math>(x\lor y)\lor z\leftrightarrow x\lor(y\lor z)</math>
|-
| [[Distributivgesetz]]e || <math>x \land ( y \lor z ) \leftrightarrow ( x \land y ) \lor ( x \land z )</math> || <math>x \lor ( y \land z ) \leftrightarrow ( x \lor y ) \land ( x \lor z )</math>
|-
| [[Idempotenz]] || <math>x \land x \leftrightarrow x</math> || <math>x \lor x \leftrightarrow x</math>
|-
| Gesetze der [[Negation#Logik|Negation]] (Tautologie / Kontradiktion) || <math>x \lor \neg x \leftrightarrow 1</math> || <math>x \land \neg x \leftrightarrow 0</math>
|-
| [[Absorptionsgesetz (Logik)|Absorptionsgesetze]]|| <math>x \land ( x \lor y ) \leftrightarrow x</math> || <math>x \lor ( x \land y ) \leftrightarrow x</math>
|-
| [[Neutrales Element|Neutralität]] || <math>x \lor 0 \leftrightarrow x</math> || <math>x \land 1 \leftrightarrow x</math>
|-
| [[De Morgansche Gesetze]] || <math>\neg ( x \land y ) \leftrightarrow \neg x \lor \neg y</math> || <math>\neg ( x \lor y ) \leftrightarrow \neg x \land \neg y</math>
|}

=== [[Schlussregel]]n ===
{| class="wikitable"
| [[Modus ponens]] || <math>\{a \rightarrow b, a\} \vdash b</math>
|-
| [[Modus tollens]] || <math>\{a \rightarrow b, \neg b\} \vdash \neg a</math>
|-
| Hypothetischer [[Syllogismus]] || <math>\{a \rightarrow b, b \rightarrow c\} \vdash a \rightarrow c</math>
|-
| Disjunktiver Syllogismus || <math>\{a \lor b, \neg a\} \vdash b</math>
|}

== Prädikatenlogik ==
=== [[Quantor]]en ===
p ist Platzhalter für eine prädikatenlogische Aussageform.

{| class="wikitable"
| <math>\forall _x p \leftrightarrow \neg (\exist _x \neg p)</math>
| <math>\exist _x p \leftrightarrow \neg (\forall _x \neg p)</math>
|-
| <math>\neg \forall _x p \leftrightarrow (\exist _x \neg p)</math>
| <math>\neg \exist _x p \leftrightarrow (\forall _x \neg p)</math>
|}

=== [[Pränexform]] ===
<math>\phi</math> und <math>\psi</math> sind im Folgenden Platzhalter für prädikatenlogische Aussageformen. Die Umformungen in Zeilen 1, 2, 4 und 5 der Tabelle gelten nur, wenn x innerhalb von <math>\psi</math> nicht frei vorkommt, d. h., wenn durch das Verschieben des Quantors keine Variablenbindung entsteht (bzw. aufgelöst wird), die zuvor nicht da war (bzw. da war).

Unproblematisch ist das, wenn die Variablen in den Aussageformen <math>\phi</math> und <math>\psi</math> jeweils unterschiedlich benannt sind.

{| class="wikitable"
| <math>(\forall x \phi) \land \psi \leftrightarrow \forall x ( \phi \land \psi)</math>
| <math>(\forall x \phi) \lor \psi \leftrightarrow \forall x ( \phi \lor \psi)</math>
|-
| <math>(\exists x \phi) \land \psi \leftrightarrow \exists x (\phi \land \psi)</math>
| <math>(\exists x \phi) \lor \psi \leftrightarrow \exists x (\phi \lor \psi)</math>
|-
| <math>\lnot \exists x \phi \leftrightarrow \forall x \lnot \phi</math>
| <math>\lnot \forall x \phi \leftrightarrow \exists x \lnot \phi</math>
|-
| <math>((\forall x \phi ) \rightarrow \psi) \leftrightarrow \exists x (\phi \rightarrow \psi)</math>
| <math>((\exists x \phi ) \rightarrow \psi) \leftrightarrow \forall x (\phi \rightarrow \psi)</math>
|-
| <math>(\psi \rightarrow (\exists x \phi)) \leftrightarrow \exists x (\psi \rightarrow \phi)</math>
| <math>(\psi \rightarrow (\forall x \phi)) \leftrightarrow \forall x (\psi \rightarrow \phi)</math>
|}

== Minimale Schlussregeln ==
=== Quasiordnung ===
<math>\vdash</math> ist im Folgenden eine Quasiordnung zwischen Aussagen.

<math>
\begin{array}{c}
{~}
\\\hline
A \vdash A
\end{array}
\qquad\begin{array}{c}
A\vdash B \qquad B\vdash C
\\\hline
A \vdash C
\end{array}
</math>

=== Konjunktion ===
<math>\top</math> und <math>\land</math> werden durch folgende Regeln definiert.

<math>
\begin{array}{c}
{~}
\\\hline
A \vdash \top
\end{array}
\qquad\begin{array}{c}
A\vdash B \qquad A\vdash C
\\\hline
A \vdash B \land C
\end{array} {\uparrow}{\downarrow}
</math>

=== Disjunktion ===
<math>\bot</math> und <math>\lor</math> werden durch folgende Regeln definiert.

<math>
\begin{array}{c}
{~}
\\\hline
\bot \vdash A
\end{array}
\qquad\begin{array}{c}
A\vdash C \qquad B\vdash C
\\\hline
A\lor B \vdash C
\end{array} {\uparrow}{\downarrow}
</math>

=== Heyting-Implikation und -Negation ===
<math>\to</math> wird durch die Regel

<math>
\begin{array}{lcr}
A \land B &\vdash& C
\\\hline
A &\vdash& B \to C
\end{array}{\uparrow}{\downarrow}
</math>

definiert, und <math>\lnot</math> per
<math>\lnot A := A \to \bot</math>.

Es gelten
*<math>A\land \lnot A \vdash \bot</math>,
*<math>\lnot \top \vdash \bot</math> und
*<math>\top \vdash \lnot \bot</math>.

=== Ko-Heyting-Implikation und -Negation ===
Dual zu <math>\to</math> und <math>\lnot</math> sind <math>\setminus</math> und <math>\sim</math>.

<math>
\begin{array}{lcr}
A \setminus B &\vdash& C
\\\hline
A &\vdash& B \lor C
\end{array}{\uparrow}{\downarrow}
</math>,

<math>{\sim} A := \top \setminus A</math>.

Es gelten
*<math>\top\vdash A \lor {\sim} A</math>
*<math>{\sim} \top \vdash \bot</math> und
*<math>\top \vdash {\sim} \bot</math>.

=== Beziehung zwischen den Negationen ===
Es gilt immer <math>\lnot A \vdash {\sim} A</math>. Gilt auch <math>{\sim}A \vdash \lnot A</math>, erhält man klassische Logik.

=== Quantoren ===
Es sei <math>f\colon X \to Y</math> eine Abbildung. Eine beliebige Aussage <math>A</math> über Elemente von <math>Y</math> kann per <math>f</math> in eine Aussage über <math>X</math>-Elemente transformiert werden; Notation: <math>A\circ f</math>.
<math>(\mathord{-} \circ f)</math> ist ein Funktor. Sein Rechts- und Linksadjungierter ist der All- bzw. Existenzquantor, d. h.,

<math>\begin{array}{lcr}
A \circ f &\vdash_X& B
\\\hline
A &\vdash_Y& \forall_f B
\end{array}{\uparrow}{\downarrow}
\qquad\begin{array}{rcl}
C &\vdash_X& A \circ f
\\\hline
\exists_f C&\vdash_Y& A
\end{array}{\uparrow}{\downarrow}</math>.

== Siehe auch ==

* [[Liste mathematischer Symbole]]

[[Kategorie:Logik]]
[[Kategorie:Formelsammlung|Logik]]
[[Kategorie:Liste (Mathematik)]]

Formelsammlung Logik - Versionsgeschichte

imported>Alfred Heiligenbrunner: /* Verknüpfungen zweier Aussagen */ Benennung der fehlenden 6 Funktionen