skip to main content

kiesler.at
AussagenLogik
Back to Page | Back to History

Difference between revisions

Version 0, 2005-03-07 20:16 Version 1, 2005-03-07 20:38
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