UND |
ODER
|
|
|
Kommutativgesetze
|
|
|
Assoziativgesetze
|
|
|
Idempotenzgesetze
|
|
|
Neutralitätsgesetze
|
|
|
Extremalgesetze
|
|
|
Komplementärgesetze
|
|
|
De Morgansche Gesetze
|
|
|
Absorptionsgesetze
|
Distributivgesetze:
![{\displaystyle A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5738bfe08b232b10e8b8bd499c3f9bd57b3a2fc)
![{\displaystyle A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4abc0ef9362aacb6481f4cac2bbb1166b1bafe5)
Involution:
![{\displaystyle {\overline {\overline {A}}}\Leftrightarrow A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a511c5924fef42100608848ae581fd8285c1655)
A |
B |
Wert
|
0 |
0 |
a
|
0 |
1 |
b
|
1 |
0 |
c
|
1 |
1 |
d
|
Nr. |
dcba |
Fkt. |
Name
|
0 |
0000 |
|
Kontradiktion
|
1 |
0001 |
|
2 |
0010 |
|
3 |
0011 |
|
4 |
0100 |
|
5 |
0101 |
|
6 |
0110 |
|
Kontravalenz
|
7 |
0111 |
|
8 |
1000 |
|
Konjunktion
|
9 |
1001 |
|
Äquivalenz
|
10 |
1010 |
|
11 |
1011 |
|
Implikation
|
12 |
1100 |
|
13 |
1101 |
|
14 |
1110 |
|
Disjunktion
|
15 |
1111 |
|
Tautologie
|
Darstellung mit Negation, Konjunktion und Disjunktion
[Bearbeiten]
![{\displaystyle A\Rightarrow B\iff {\overline {A}}\lor B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1504c7da6cd2a3da8697c0740872dacab3726ba8)
![{\displaystyle (A\Leftrightarrow B)\iff ({\overline {A}}\land {\overline {B}})\lor (A\land B)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e57e3817bef66ccc7bb16e345b14bdd62c9c66f9)
![{\displaystyle A\oplus B\iff ({\overline {A}}\land B)\lor (A\land {\overline {B}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb86cc33f5aac5a0b763499dd3d46c4f8d15c661)
![KV-Diagramm-Vorlage mit acht Feldern](//upload.wikimedia.org/wikibooks/de/4/4e/FormelsammlungLogikKV8.png)
Modus ponens:
![{\displaystyle (A\Rightarrow B)\land A\implies B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ce1b33d1d1425d66daa1f53301a9d4b5ae9699e)
Modus tollens:
![{\displaystyle (A\Rightarrow B)\land {\overline {B}}\implies {\overline {A}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3a4e8ef6223450b47c0e2f922e2ed637ea8e407)
Modus tollendo ponens:
![{\displaystyle (A\lor B)\land {\overline {A}}\implies B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77bff4c9baf4e27920411a6e6a6aa36b4909c120)
Modus ponendo tollens:
![{\displaystyle {\overline {A\land B}}\land A\implies {\overline {B}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/519889dcdc61e1f2292b2fe29e305dc1c4c0eb86)
Kontraposition:
![{\displaystyle A\Rightarrow B\iff {\overline {B}}\Rightarrow {\overline {A}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d69768e769459f119c8080b71bca5824f84aace)
Beweis durch Widerspruch:
![{\displaystyle ({\overline {A}}\Rightarrow B\land {\overline {B}})\implies A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2722954f0c9aa603e220f137853b996060e6e23)
Zerlegung einer Äquivalenz:
![{\displaystyle (A\Leftrightarrow B)\iff (A\Rightarrow B)\land (B\Rightarrow A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83ed0419f4da906fd7e3d4b9cfbbbf4627fdc6f9)
Kettenschluss:
![{\displaystyle (A\Rightarrow B)\land (B\Rightarrow C)\implies (A\Rightarrow C)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/608c22cc60f4e11d5f26e043cb0ed46faf8f54e9)
Ringschluss:
![{\displaystyle (A\Rightarrow B)\land (B\Rightarrow C)\land (C\Rightarrow A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe430bde0a51a28008721212415103a252ff258d)
![{\displaystyle \implies (A\Leftrightarrow B)\land (A\Leftrightarrow C)\land (B\Leftrightarrow C)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7cb1fe70c102be36c407090bec9aba8482e1590)
Ringschluss, allgemein:
![{\displaystyle (A_{1}\Rightarrow A_{2})\land \ldots \land (A_{n-1}\Rightarrow A_{n})\land (A_{n}\Rightarrow A_{1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbc0676e37716ce73e94251f2b5153f6f9b6fa2e)
![{\displaystyle \implies \forall i,j\,[A_{i}\Leftrightarrow A_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8da12d02356a7ac773d13ce14e32313421b99b19)
Modus ponens:
![{\displaystyle \{\varphi ,\varphi \rightarrow \psi \}\vdash \psi }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3036ea1fa922202c0fa494e5de10efe12e273b84)
Sei
eine endliche Menge von Formeln.
Korrektheit der Aussagenlogik.
Es gilt:
![{\displaystyle (M\vdash \psi )\implies (M\models \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81e7c91e7839dc97f99f1b389b61b6d3d4490e7d)
Vollständigkeit der Aussagenlogik.
Es gilt:
![{\displaystyle (M\models \psi )\implies (M\vdash \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d5a9b323dfabfc8f588ed8b4f999195981d9603)
Deduktionstheorem (syntaktisch).
Es gilt:
![{\displaystyle (M\cup \{\varphi \}\vdash \psi )\iff (M\vdash \varphi \rightarrow \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca8bc2be858505ff9fb6f95480a37049162a9240)
Infolge gilt auch:
![{\displaystyle (\{\varphi _{1},\ldots ,\varphi _{n}\}\vdash \psi )\iff (\vdash \varphi _{1}\land \ldots \land \varphi _{n}\rightarrow \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42cd2b82c696607f0f5950428b7fc70519464509)
Deduktionstheorem (semantisch).
Es gilt:
![{\displaystyle (M\cup \{\varphi \}\models \psi )\iff (M\models \varphi \rightarrow \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4955bb4c650cd7de6f646d05261c245f0b16f208)
Infolge gilt auch:
![{\displaystyle (\{\varphi _{1},\ldots ,\varphi _{n}\}\models \psi )\iff (\models \varphi _{1}\land \ldots \land \varphi _{n}\rightarrow \psi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3208cbd4a4c4e8067a321fe57b089168fa638837)
Einsetzungsregel.
Sei v eine logische Variable. Ist φ eine tautologische Formel, dann ergibt sich wieder eine tautologische Formel, wenn man jedes Vorkommen von v in φ durch eine Formel ψ ersetzt. Formal:
![{\displaystyle (\models \varphi )\implies (\models \varphi [v:=\psi ]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c829a4cacb14ce322652c0b4afe1985920f1ac41)
Das gilt auch für die simultane Substitution:
![{\displaystyle (\models \varphi )\implies (\models \varphi [v_{1}:=\psi _{1},\ldots ,v_{n}:=\psi _{n}]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3922063d562037158aeee5b0bc5db21b0b2b6ef)
Beispiel. Man überzeugt sich z. B. mittels einer Wahrheitstabelle von
![{\displaystyle \models A\land (A\rightarrow B)\rightarrow B.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b23cffc84c352a60f6f907731d0a978b01d8dd66)
Unter Anwendung der Einsetzungsregel lassen sich die zwei Variablen simultan gegen Formeln austauschen:
![{\displaystyle \models \varphi \land (\varphi \rightarrow \psi )\rightarrow \psi .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fba3d9be167653bab0dcca72844c063264470c86)
Zieht man nun die Vollständigkeit und das Deduktionstheorem heran, ergibt sich der Modus ponens:
![{\displaystyle \{\varphi ,\varphi \rightarrow \psi \}\vdash \psi .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8c75c4e43018f2f44d8da2870a3bf4db7300ff)
Definition. Formale Sprache der Aussagenlogik.
Sei
die Menge der logischen Variablen.
Die Menge der wohlgeformten Formeln ist durch die folgende formale Grammatik definiert:
- Bei 0 und 1 handelt es sich um Formeln.
- Jede Variable aus V ist eine Formel.
- Sind φ und ψ Formeln, dann sind es auch
.
Die Menge der wohlgeformten Formeln ist die formale Sprache der Aussagenlogik.
Bemerkung:
- Für die Praxis wird
definiert.
- Außerdem können Klammernpaare wie bei Punktrechnung-vor-Strichrechnung weggelassen werden, wobei die Bindungsstärke in absteigender Reihenfolge
ist.
- Anstelle von
wird auch
geschrieben.
Es folgen historische Axiomatisierungen.
Das Axiom (P4) ist redundant.
Definition. Modellrelation.
Eine Formelmenge M modelliert eine Formel ψ, wenn jedes Modell von M auch ein Modell von ψ ist. Kurz:
![{\displaystyle (M\models \psi )\;:\Longleftrightarrow \;\forall I[(I\models M)\implies (I\models \psi )].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e393926fb0627ffc84f84da96d915c6cc09b1a00)
Definition. Tautologie.
Eine Formel wird tautologisch (allgemeingültig) genannt, wenn jede Interpretation für sie auch ein Modell ist. Kurz:
![{\displaystyle (\models \varphi )\;:\Longleftrightarrow \;\forall I(I(\varphi )=1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/875803b5b2ff3d46e98633e2ff47f531a0897b1f)
Eine Formel ist genau dann tautologisch, wenn sie durch die leere Menge modelliert wird:
![{\displaystyle (\models \varphi )\iff (\{\}\models \varphi ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9848a03455c265ecefe34ae2ffcfd5dd171bce6b)
Definition. Erfüllbare Formel.
Eine Formel wird erfüllbar genannt, wenn sie ein Modell besitzt. Kurz:
![{\displaystyle \operatorname {erf} [\varphi ]\;:\Longleftrightarrow \;\exists I(I(\varphi )=1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83dd811a5eff2648ea647af57024de76795cc3e0)
Definition. Unerfüllbare Formel.
Eine Formel wird unerfüllbar genannt, wenn sie kein Modell besitzt. Kurz:
![{\displaystyle \neg \operatorname {erf} [\varphi ]\iff \forall I(I(\varphi )=0).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23726a63f27c202654141b2753ba4cf3cda37ecd)
Definition. Erfüllbarkeitsäquivalenz.
Zwei Formeln φ und ψ heißen erfüllbarkeitsäquivalent, wenn gilt:
![{\displaystyle \operatorname {erf} [\varphi ]\iff \operatorname {erf} [\psi ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/101385805233d7ba5c44a1c75af7f42f9b4a6d2d)
Das Modell der ersten Formel braucht dabei nicht mit dem Modell der zweiten Formel übereinzustimmen.
Verneinung (De Morgansche Gesetze):
![{\displaystyle \neg \forall x[P(x)]\iff \exists x[\neg P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62a89e794f4aeef6649697ac605d4e95fbd4c9db)
![{\displaystyle \neg \exists x[P(x)]\iff \forall x[\neg P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d4ed0a8577c409586d4551ff26e3efc11773c16)
Verallgemeinerte Distributivgesetze:
![{\displaystyle P\land \exists x[Q(x)]\iff \exists x[P\land Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a865705386c7cac2f541914ecf2cc06f310e72aa)
![{\displaystyle P\lor \forall x[Q(x)]\iff \forall x[P\lor Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/168734450d98f2bad2460d0588c1c711bb526c3c)
Verallgemeinerte Idempotenzgesetze:
![{\displaystyle \exists x{\in }M\,[P]\iff (M\neq \{\})\land P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\0&{\text{wenn}}\;M=\{\}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60a7e73d515cb886397773e4b72984cc09cb671f)
![{\displaystyle \forall x{\in }M\,[P]\iff (M=\{\})\lor P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\1&{\text{wenn}}\;M=\{\}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e9e9caec7a4720faf3089422806a72e5a93ae6d)
Äquivalenzen:
![{\displaystyle \forall x\forall y[P(x,y)]\iff \forall y\forall x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b90226c80062f3fd15343bb1f742b9968a10bf8)
![{\displaystyle \exists x\exists y[P(x,y)]\iff \exists y\exists x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9eaf4d427581b1b9302fb80a699fddad02e32af)
![{\displaystyle \forall x[P(x)\land Q(x)]\iff \forall x[P(x)]\land \forall x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5c325b3967273188efc1305e78281e2026be04f)
![{\displaystyle \exists x[P(x)\lor Q(x)]\iff \exists x[P(x)]\lor \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10954544fd0a6140d53063ddf369da789b9b664f)
![{\displaystyle \forall x[P(x)\Rightarrow Q]\iff \exists x[P(x)]\Rightarrow Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/197b0d7da8c1c1c6523d452d59092890fb42058a)
![{\displaystyle \forall x[P\Rightarrow Q(x)]\iff P\Rightarrow \forall x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e41fa4b0f450aa19843b68c44ec38c94ee556241)
![{\displaystyle \exists x[P(x)\Rightarrow Q(x)]\iff \forall x[P(x)]\Rightarrow \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb3bb3df29c39088d8260519cbcd5895d1f22050)
Implikationen:
![{\displaystyle \exists x\forall y[P(x,y)]\implies \forall y\exists x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9b5b950d4ce172109e000e35e9b37112df6831a)
![{\displaystyle \forall x[P(x)]\lor \forall x[Q(x)]\implies \forall x[P(x)\lor Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f559cd8a3262b6429025a65097a54a022704fa6)
![{\displaystyle \exists x[P(x)\land Q(x)]\implies \exists x[P(x)]\land \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d3b4f31615784181fc9a3f2e9658b5940c296c3)
![{\displaystyle \forall x[P(x)\Rightarrow Q(x)]\implies (\forall x[P(x)]\Rightarrow \forall x[Q(x)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de48500bc136458631862177605c295a97b9f3f7)
![{\displaystyle \forall x[P(x)\Leftrightarrow Q(x)]\implies (\forall x[P(x)]\Leftrightarrow \forall x[Q(x)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0abfeb9a2cf63e78de92a36d49dba42618860da1)
Sei
.
![{\displaystyle \forall x{\in }M\,[P(x)]\iff P(x_{1})\land \ldots \land P(x_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/117da61f5b6d9f542907d5f05de6921f403389e4)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff P(x_{1})\lor \ldots \lor P(x_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e4f7fc7f8e5988695be6d548424864277fd5f2c)
![{\displaystyle \forall x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\forall x[x\notin M\vee P(x)]\iff \forall x[x\in M\Rightarrow P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a4639ba98d1b1827c56e8df4a7faae56deab7d7)
![{\displaystyle \exists x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\exists x[x\in M\wedge P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e908c0518b63c3f36bbddce9381f79270b045f55)
![{\displaystyle \forall x{\in }M{\setminus }N\,[P(x)]\iff \forall x{\in }M\,[x\notin N\Rightarrow P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16c4c48857e12f3952c66f133a34f432f1d2fdb2)
![{\displaystyle \exists (x,y)\,[P(x,y)]\iff \exists x\exists y\,[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f47430bd8c15b370977a1ccb0809ce121ce8285f)
![{\displaystyle \forall (x,y)\,[P(x,y)]\iff \forall x\forall y\,[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1ac9e70ab80ef25b952693272743fe800fedd0a)
Analog gilt
![{\displaystyle \exists (x,y,z)[P(x,y,z)]\iff \exists x\exists y\exists z\,[P(x,y,z)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0309c3ef8b56872f7ac5dc78b11cd59d020b53a9)
![{\displaystyle \forall (x,y,z)[P(x,y,z)]\iff \forall x\forall y\forall z\,[P(x,y,z)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/650e4491eee513721619de32fe341b9f4a2f61ea)
usw.
Sei
und
.
Mit
ist die Bildmenge von
bezüglich
gemeint.
![{\displaystyle \forall x{\in }M\,[P(x)]\iff P(M)=\{1\}\iff M\subseteq \{x{\in }G\mid P(x)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b601c75a300c41b101533fc565942db6b04b176a)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \{1\}\subseteq P(M)\iff M\cap \{x{\in }G\mid P(x)\}\neq \{\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0004039fb0f641c24b235a8ab5c76cab8221d097)
Sei
eine Injektion. Es gilt:
![{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall y\in g(M)\,[P(g^{-1}(y))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba4aa82c7489e45fb52ee38e36ae6a44110af06e)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists y\in g(M)\,[P(g^{-1}(y))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ff4bf2823b86316ec1c5e7ba48622f12ce9fe7a)
Ist
eine bijektive Selbstabbildung auf
, so gilt speziell:
![{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall x{\in }M\,[P(g^{-1}(x))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/944574dd5eeb64327a404ab00d5a1febd65dd231)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists x{\in }M\,[P(g^{-1}(x))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa3a38972c31e35c57e8aa856ecd15681572d73)
Quantor für eindeutige Existenz:
![{\displaystyle \exists !x\,[P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2de5632d68703e84c626b7d4a72758f038bb328d)
![{\displaystyle :\Longleftrightarrow \;\exists x\,[P(x)\land \forall y\,[P(y)\Rightarrow x=y]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4109df6763f826cc8d32be042bd2aaf31d531c9)
![{\displaystyle \iff \exists x\,[P(x)]\land \forall x\forall y[P(x)\land P(y)\Rightarrow x=y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2474413c4a267d4ea1283bd4a98e150a9587f1e)