Du befindest dich hier: Aussagenlogik / Evaluierung einer Formel unter einer Interpretation

Mögliche Ersparnis

(Aussagenlogik Kapitel 5.3)

Wie wir gesehen haben, können wir teilweise Evaluierungsschritte einsparen, wenn wir die Überlegungen zur Bewertung der Junktoren bei der Bewertung einer Formel beachten.

Wir müssen uns jedoch im Klaren darüber sein, dass die mögliche Ersparnis abhängig ist von

• der Reihenfolge, in der wir die Atome bewerten

  ---

  Beispiel - Benötigte Schritte zur Evaluierung einer Formel (1)

  Betrachten wir wieder die Formel und Interpretation aus dem Beispiel des vorherigen Kapitels zur Evaluierung einer Formel

  • γ = (p->q)&(p&q->r)->(p->r)

  • I = { p→ 1 , q→ 0 , r→ 1 }

  bewerten die atomaren Formeln jedoch diesmal in einer anderen Reihenfolge

  • [ p , q , r ]

  
  

  Schritt 1: Wir evaluieren die 1. atomare Formel - p		Schritt Teilformel Bewertung (p->q)&(p&q->r)->(p->r) p->r (p->q)&(p&q->r) p&q->r p&q p->q rr qq 1 ppp 1
  Schritt 2: Wir prüfen die nicht bewerteten Teilformeln auf Bewertbarkeit. Wie wir sehen, lässt sich keine der Teilformeln bewerten. Also evaluieren wir die 2. atomare Formel - q.		Schritt Teilformel Bewertung (p->q)&(p&q->r)->(p->r) p->r (p->q)&(p&q->r) p&q->r p&q p->q rr 2 qq 0 1 ppp 1
  Schritt 3: Wir evaluieren die bewertbaren Teilformeln: p&q p->q		Schritt Teilformel Bewertung (p->q)&(p&q->r)->(p->r) p->r (p->q)&(p&q->r) p&q->r 3 p&q 0 3 p->q 0 rr 2 qq 0 1 ppp 1
  Schritt 4: Da I(p&q) = 0 und die Implikation wahr ergibt, wenn die Prämisse falsch ist, können wir sofort I(p&q->r) = 1 bewerten. Da I(p->q) = 0 und die Konjunktion falsch ist, sobald ein Argument falsch ist, können wir sofort I((p->q)&(p&q->r)) = 0 bewerten.		Schritt Teilformel Bewertung (p->q)&(p&q->r)->(p->r) p->r 4 (p->q)&(p&q->r) 0 4 p&q->r 1 3 p&q 0 3 p->q 0 rr 2 qq 0 1 ppp 1
  Schritt 5: Da wir aus dem vorherigen Schritt wissen, dass I((p->q)&(p&q->r)) = 0, dies die Prämisse von γ ist, und die Implikation wahr ist, wenn die Prämisse falsch ist, können wir sofort γ bewerten, und sind fertig.		Schritt Teilformel Bewertung 5 (p->q)&(p&q->r)->(p->r) 1 p->r 4 (p->q)&(p&q->r) 0 4 p&q->r 1 3 p&q 0 3 p->q 0 rr 2 qq 0 1 ppp 1

  
  Haben wir uns im vorherigen Kapitel die Bewertung von 5 Teilformeln erspart, sind es jetzt, durch die andere Reihenfolge der Betrachtung der atomaren Formeln, nur 2!

  ---

• und der Interpretation

  ---

  Beispiel - Benötigte Schritte zur Evaluierung einer Formel (2)

  Nehmen wir diesmal die Formel und die Reihenfolge der Bewertung der Atome aus dem Beispiel des vorherigen Kapitels zur Evaluierung einer Formel

  • γ = (p->q)&(p&q->r)->(p->r)

  • [ r , p , q ]

  betrachten jedoch eine andere Interpretation

  • I = { p→ 1 , q→ 0 , r→ 0 }

  so benötigt die Bewertung folgende Schritte:
  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  	p->r
  	(p->q)&(p&q->r)
  	p&q->r
  	p&q
  	p->q
  1	rr	0
  	qq
  	ppp

  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  	p->r
  	(p->q)&(p&q->r)
  	p&q->r
  	p&q
  	p->q
  1	rr	0
  	qq
  2	ppp	1

  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  3	p->r	0
  	(p->q)&(p&q->r)
  	p&q->r
  	p&q
  	p->q
  1	rr	0
  	qq
  2	ppp	1

  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  3	p->r	0
  	(p->q)&(p&q->r)
  	p&q->r
  	p&q
  	p->q
  1	rr	0
  4	qq	0
  2	ppp	1

  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  3	p->r	0
  	(p->q)&(p&q->r)
  	p&q->r
  5	p&q	0
  5	p->q	0
  1	rr	0
  4	qq	0
  2	ppp	1

  
  

  Schritt	Teilformel	Bewertung
  	(p->q)&(p&q->r)->(p->r)
  3	p->r	0
  6	(p->q)&(p&q->r)	0
  6	p&q->r	1
  5	p&q	0
  5	p->q	0
  1	rr	0
  4	qq	0
  2	ppp	1

  
  

  Schritt	Teilformel	Bewertung
  7	(p->q)&(p&q->r)->(p->r)	1
  3	p->r	0
  6	(p->q)&(p&q->r)	0
  6	p&q->r	1
  5	p&q	0
  5	p->q	0
  1	rr	0
  4	qq	0
  2	ppp	1

  
  
  Wie wir sehen, mussten wir in diesem Fall alle Teilformeln evaluieren!

  ---

• zurück zu Evaluierung einer Formel
• zum Seitenanfang
• weiter zu interaktiv üben! - Evaluierung einer Formel unter einer Interpretation

. .