| Lines 66 - 80 |
Lines 66 - 113 |
| +++ Semantische Äquivalenzen |
+++ Semantische Äquivalenzen |
| |
|
| ++++ Idempotenz |
++++ Idempotenz |
| |
|
| |
F AND F ≡ F |
| |
F OR F ≡ F |
| |
|
| |
|
| ++++ Kommunitativität |
++++ Kommunitativität |
| |
|
| |
F AND G ≡ G AND F |
| |
F OR G ≡ G OR F |
| |
|
| ++++ Assoziativität |
++++ Assoziativität |
| |
|
| |
(F AND G) AND H usw. |
| |
|
| ++++ Absorption |
++++ Absorption |
| |
|
| ++++ Distributivgesetz |
++++ Distributivgesetz |
| |
|
| ++++ Doppelnegation |
++++ Doppelnegation |
| |
|
| |
!!F ≡ F |
| |
|
| |
|
| ++++ deMorgan |
++++ deMorgan |
| |
|
| |
!(F AND G) ≡ !F OR !G |
| |
!(F OR G) ≡ !F AND !G |
| |
|
| |
|
| ++++ Kontraposition |
++++ Kontraposition |
| |
|
| |
F => G ≡ !G => !F |
| |
|
| |
|
| ++++ Implikation |
++++ Implikation |
| |
|
| |
F => G ≡ !F OR G |
| |
|
| |
|
| ++++ Koimplikation |
++++ Koimplikation |
| |
|
| |
F <=> G ≡ (F => G) AND (G => F) |
| |
|
| |
|
| Anwendung bei Regelbasierten Systemen. |
Anwendung bei Regelbasierten Systemen. |
| Lines 82 - 84 |
Lines 115 - 181 |
| Ziel: Syntaktisch einfache Regeln - keine Disjunktion im Regelrumpf. |
Ziel: Syntaktisch einfache Regeln - keine Disjunktion im Regelrumpf. |
| |
|
| A1 OR A2 => B ≡ (A_1 => B) AND (A_2 => B) |
A1 OR A2 => B ≡ (A_1 => B) AND (A_2 => B) |
| |
|
| |
(Implikation, deMorgan, Distributivität) |
| |
|
| |
+++ Hornklausl / SLD |
| |
|
| |
Wurde in logikorientierte Programmiersprachen unterrichtet, allerdings scheinbar nicht bei Prof. Neumerkel (wo ich Prolog ca. 1998 gemacht habe). |
| |
|
| |
NP-Vollständig, nicht deterministisch polynomiell |
| |
|
| |
Konzept: Guess and Check (Einfach mal raten und nachher prüfen, ob's stimmt) |
| |
|
| |
Die Lösungsverifikation (Check) ist zwar polynomiell, jedoch gibt es exponentiell viele Lösungskandidaten. Im worst-case: Nicht erfüllbar. |
| |
|
| |
Hornformeln hingegen sind polynomienell entscheidbar! |
| |
|
| |
|
| |
++++ Hornklauselmengen |
| |
|
| |
{ H1, ..., H5 } = Konjunktion |
| |
|
| |
≡ FORALL(i=1, 5) H_i |
| |
|
| |
++++ Ziel |
| |
|
| |
syntaktisch einfache Regeln -- ein einziges Literal im Folgerungsteil |
| |
|
| |
A => B1 OR B2 ≡ (A AND !B1 => B2) AND ..... |
| |
|
| |
+++ Inferenzregeln |
| |
|
| |
|
| |
Notation: |
| |
|
| |
F1, ..., Fn |
| |
________ |
| |
F |
| |
|
| |
|
| |
Modus ponens (MP): |
| |
|
| |
F, F => G |
| |
________ |
| |
G |
| |
|
| |
|
| |
Modus tolens (MT): |
| |
|
| |
F => G, !G |
| |
_________ |
| |
!F |
| |
|
| |
|
| |
+++ Grenzen |
| |
|
| |
Max hat lange Ohren. Dafür brauchen wir die Prädikatenlogik! |
| |
|
| |
|
| |
FORALL(x) hase(x) -> langohr(x) |
| |
hase(m) |
| |
_______ |
| |
langohr(m) |
| |
|
| |
|
| |
++ PrädikatenLogik |
AussagenLogik
