uebung6

Aus ProgrammingWiki

Archivierte Version vom 2012-05-08T14:38:32+00:00. Aktuelle Version

Reduzierbarkeit

Aufgabe 1

Konstruieren Sie eine Prozedur, welche prüft, ob w die Form uu besitzt.

(define uuchecker
  (lambda (w)
    (cond
      ((odd? (string-length w)) #f)
      ((string=? (substring w 0 (/ (string-length w) 2)) (substring w (/ (string-length w) 2) (string-length w))) #t)
      (else #f)
     )
  )
)

(uuchecker "ww")

Aufgabe 2

Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:

A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A

Verwenden Sie im Beweis die folgenden Aussagen:

A: P' ist entscheidbar. B: P ist reduzierbar auf P'. C: P ist entscheidbar.

uebung6

Reduzierbarkeit

Aufgabe 1

Aufgabe 2

Suche