Anwendungsgebiete mehrwertiger Logik

Transcrição

Anwendungsgebiete
mehrwertiger Logik
P. H. Schmitt: Nichtklassische Logiken – p.1
Anwendungsgebiete
•
Unabhängigkeitbeweise,
•
Modellierung undefinierter Funktions- und Prädikatswerte in der
Spezifikation und Verifikation von Programmen,
•
Semantik natürlicher Sprache, z.B. zur Modellierung von
Präsuppositionen,
•
in der Theorie der logischen Programmierung zur deklarativen
Beschreibung der operationalen Semantik der Negation,
•
Modellierung elektronischer Schaltkreise,
•
zur Modellierung von Vagheit und Unbestimmtheit, z.B. in der
Theorie der Intervallarithmetik.
Das Axiomensystem K1
Ax1
Ax2
Ax3
Ax4
Ax5
Ax6
Ax7
Ax8
Ax9
Ax10
Ax11
Ax12
Ax13
Ax14
Ax15
p1 ⇒ (p2 ⇒ p1 )
((p1 ⇒ p2 ) ⇒ p1 ) ⇒ p1
(p1 ⇒ p2 ) ⇒ ((p2 ⇒ p3 ) ⇒ (p1 ⇒ p3 ))
(p1 ∧ p2 ) ⇒ p1
(p1 ∧ p2 ) ⇒ p2
(p1 ⇒ p2 ) ⇒ ((p1 ⇒ p3 ) ⇒ p1 ⇒ p2 ∧ p3 ))
p1 ⇒ (p1 ∨ p2 )
p2 ⇒ (p1 ∨ p2 )
(p1 ⇒ p3 ) ⇒ ((p2 ⇒ p3 ) ⇒ p1 ∨ p2 ⇒ p3 ))
(p1 ≈ p2 ) ⇒ (p1 ⇒ p2 )
(p1 ≈ p2 ) ⇒ (p2 ⇒ p1 )
(p1 ⇒ p2 ) ⇒ ((p2 ⇒ p1 ) ⇒ p1 ≈ p2 ))
(p1 ⇒ p2 ) ⇒ (¬p2 ⇒ ¬p1 )
p1 ⇒ ¬¬p1
¬¬p1 ⇒ p1
Axiomensystem K1
Die Axiome Ax1 bis Ax15 zusammen mit der Modus-ponens-Regel
H, H ⇒ G
G
bilden ein vollständiges Axiomensystem für die klassische
Aussagenlogik.
Unabhängigkeit
Ein Axiomensystem K heißt unabhängig, wenn für jedes Axiom
A ∈ K, in der Ableitungsrelation `K\{A} , die durch dieselben Regeln
und die um A verminderte Axiomenmenge von K gegeben ist, die
Formel A nicht herleitbar ist, d.h.
6`K\{A} A.
Wir zeigen exemplarisch, daß Ax2 unabhängig ist von den restlichen
Axiomen in K1 .
Beweisansatz
Wir suchen nach einer Eigenschaft E , so daß:
•
alle Axiome in K1 außer Ax2 besitzen die Eigenschaft E ,
•
Ax2 besitzt nicht die Eigenschaft E ,
•
besitzen H und H ⇒ G die Eigenschaft E , dann besitzt auch G
die Eigenschaft E .
Hier definieren wir E durch:
Eine Formel A hat Eigenschaft E , wenn A eine Tautologie in der
dreiwertigen Logik LK1 ist.
Die Logik LK1
⇒ 1 u 0
≈ 1 u 0
p ¬p
1
u
0
1
u
0
1
u
0
1 u 0
1 1 u
1 1 1
1 u 0
u 1 u
0 u 1
∧ 1 u 0
∨ 1 u 0
1
u
0
1
u
0
1 u 0
u u 0
0 0 0
0
u
1
1 1 1
1 u u
1 u 0
Ax1 ist eine LK1 -Tautologie
Angenommen es gäbe eine Belegung v, so daß v(Ax1) kein
ausgezeichneter Wahrheitswert ist, d.h. v(Ax1) ∈ {u, 0}.
Die Wahrheitstabelle für ⇒ zeigt, daß es hierfür zwei Möglichkeiten
gibt:
v(p1 ) = u und v(p2 ⇒ p1 ) = 0
aus v(p2 ⇒ p1 ) = 0 folgt v(p1 ) = 0 und v(p2 ) = 1 Widerspruch
oder
v(p1 ) = 1 und v(p2 ⇒ p1 ) ∈ {u, 0}
aus v(p2 ⇒ p1 ) ∈ {u, 0} folgt v(p1 ) ∈ {u, 0} Widerspruch
Ax2 ist keine LK1 -Tautologie
p1
p2
p1 ⇒ p 2
(p1 ⇒ p2 ) ⇒ p1
Ax2
1
1
1
1
1
1
u
u
1
1
1
0
0
1
1
u
1
1
u
1
u
u
1
u
1
u
0
u
1
u
0
1
1
0
1
0
u
1
0
1
0
0
1
0
1
zu Erinnerung:
Ax2 = ((p1 ⇒ p2 ) ⇒ p1 ) ⇒ p1 .
Modus Ponens erhält Eigenschaft
Zu zeigen:
Modus Ponens erhält LK1 -Tautologieeigenschaft
H, H ⇒ G
G
Ist v(H) = 1, so folgt aus der Wahrheitstafel für ⇒,
daß v(H ⇒ G) = 1 nur gelten kann, wenn auch v(G) = 1.
VDM
VDM (Vienna Development Method) ist eine Methode zur formalen
Spezifikation und Entwicklung von Systemen.
Korrespondenz der VDM-Logik mit L3
VDM (nach Jones90)
L3
true
∗
false
∧, ∨
¬
⇒
⇔
1
u
0
∧, ∨ min, max
¬ starke Negation
→ starke Implikation
↔ starke Äquivalenz
Dreiwertige Gleichheit in VDM
A =3 B
B∈N B≡∗
A∈N
A=B
∗
A≡∗
∗
∗
Zum Universum N der wird das Element ∗ hinzugenommen.
Außerdem wird ein neues Element ∗ zur Menge B der Boolschen
Werte hinzugefügt.
[ mn ]
=
(
das kleinste k ∈ N mit k × m ≥ n m 6= 0
∗
(
[n − m] =
sonst
n−m
∗
falls n ≥ m
sonst
Logik mit partiellen Funktionen
Die Formel
n
∀n, m([ ] = [m − n] → 5n = 5m2 − 5nm)
m
hat in der klassischen Logik den Wahrheitswert 0,
denn für m = 0 und n = 1 ist die Prämisse der Implikation wahr, da ja
1
[ ] = ∗ = [0 − 1]
0
Aber die rechte Seite der Implikation führt zu der Ungleichung
5 6= 0
In VDM erhält sie den Wahrheitswert u = ∗ .
Logik mit partiellen Funktionen
Hat umgekehrt eine Implikation
∀~n( f1 (~n) = f2 (~n) ⇒ g1 (~n) = g2 (~n))
den Wahrheitswert u, so gilt immer noch für alle ~n, für die alle f i (~n)
und gi (~n) definiert sind
f1 (~n) = f2 (~n) → g1 (~n) = g2 (~n)
im 2-wertigen Sinn.
Kombinatorischer Schaltkreis
Beispiel
y
I1
d
a
b
G1
G3
h
g
G5
G4
c
k
i
G6
z
I2
G2
e
f
Die Logik L
4
D
Die vierwertige Logik LD4 besitzt die Wahrheitswerte
{1, 0, D, D}
Semantik:
Sei C ein Schaltkreis und FM ein Fehlermodell. Leitungen a der
Schaltung C werden als logische Variable aufgefasst.
aC ∈ {0, 1} sei der Wert von a bei korrekter Schaltung C,
aF ∈ {0, 1} sei der Wert von a in C mit Fehler FM .
Der Wahrheitswert in LD4 berechnet sich wie folgt:
a4 = 1 falls aC = 1 und aF
a4 = 0 falls aC = 0 und aF
a4 = D falls aC = 1 und aF
a4 = D falls aC = 0 und aF
=1
=0
=0
=1
Wahrheitstabellen für L
NAND 0 1 D D
4
D
NOR 0 1 D D
0
1 1 1 1
0
1 0 D D
1
1 0 D D
1
0 0 0 0
D
1 D D 1
D
D 0 D 0
D
1 D 1 D
D
D 0 0 D
X
0 1 D D
NOTX 1 0 D D
Beschreibung des Schaltkreises
durch Boolesche Gleichungen
d = ¬a
h = ¬(y ∨ g)
e
= ¬b
i
f
= ¬(d ∨ e)
k = ¬(h ∨ i)
g = ¬(d ∨ b)
z
= ¬(d ∨ c)
= ¬( f ∧ k)
Testgenerierung
LD4 -Gleichungen zur Testgenerierung
{1, 0, D, D}
{1, 0, D, D}
{1, 0, D, D}
{1, 0, D, D}
{1, 0, D, D}
{1, 0, D, D}
{1, 0, D, D}
e
f
g
h
i
k
z
=
=
=
=
=
=
=
¬b
¬(d ∨ e)
¬(d ∨ b)
¬(y ∨ g)
¬(d ∨ c)
¬(h ∨ i)
¬( f ∧ k)
{1}a
{1, 0}b
{1, 0}c
{1, 0}y
{D, D}z
{D}d
Beobachtung
Die Testmuster für einen kombinatorischen Schaltkreis
mit einem Fehler
sind genau
die erfüllenden Belegungen des zugehörigen L D4 -Gleichungssystems.
Beispiel: sequentieller Schaltkreis
D
y
I1
d
a
b
G1
G3
h
g
G5
G4
c
k
i
G6
z
I2
G2
e
f
Konjunktion in der Logik von Muth
Disjunktion in der Logik von Muth
Negation in der Logik von Muth

Anwendungsgebiete mehrwertiger Logik

Transcrição

Documentos relacionados

Hinterschaft und 2 breite Vorderschäfte für FN Bockdoppelflinte Mod

Mehrwertige Logiken

iQ-Company - Logbuch, Fish M, orange

Fall 12- Angabe

Protokoll vom 18.08.2008 - Kaiserpfalz Realschule Ingelheim

pdf

Philosophische Erkenntnistheorie löst

RBF STAHL-Wechselsystem, Kal. 22LR für Glock Mod. 17, 17L,22

Zurück auf Los

Suunto - Batterie Kit , Suunto Stinger - Joy-Venture