BuK/IIm11/Studenten/sirorose/uebung6

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Reduzierbarkeit ==

=== Aufgabe 1  ===

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

<code id="4fa92fe8aa531">
(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)
     )
  )
)   
</code>

<run id="4fa92fe8aa59b">
(uuchecker "ww")
</run>

=== 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.