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.

{| border="1" cellpadding="5" cellspacing="0"
!A
!B
!C
!$A \wedge B $
!$A \wedge B \rightarrow C$	
! $\neg C$
! $\neg C \wedge B$
!$ \neg A$
!$ \neg C \wedge B \rightarrow \neg A $
|-
|| 0 || 0 || 0 || 0 || <b style="color: green;">1</b> || 1 || 0 || 1 || <b style="color: green;">1</b>
|-
|| 0 || 0 || 1 || 0 || <b style="color: green;">1</b> || 0 || 0 || 1 || <b style="color: green;">1</b>
|-
|| 0 || 1 || 0 || 0 || <b style="color: green;">1</b> || 1 || 1 || 1 || <b style="color: green;">1</b>
|-
|| 0 || 1 || 1 || 0 || <b style="color: green;">1</b> || 0 || 0|| 1 || <b style="color: green;">1</b>
|-
|| 1 || 0 || 0 || 0 || <b style="color: green;">1</b> || 1 || 0 || 0 || <b style="color: green;">1</b>
|-
|| 1 || 0 || 1 || 0 || <b style="color: green;">1</b> || 0 || 0 || 0 || <b style="color: green;">1</b>
|-
|| 1 || 1 || 0 || 1 || <b style="color: green;">0</b> || 1 || 1 || 0 || <b style="color: green;">0</b>
|-
|| 1 || 1 || 1 || 1 || <b style="color: green;">1</b> || 0 || 0 || 0 || <b style="color: green;">1</b>
|-
|}