BuK/IIm14/Studenten/s3adkuce

Wiki-Quelltext dieser Seite.

== Indirekter Beweis ==

==== Aufgabe 1 ====

Beweisen Sie indirekt, dass $x$ eine gerade Zahl ist, wenn $x^2$ mit $x\in{\mathbb N}$ eine gerade Zahl ist.

'''Lösung:'''

''zu zeigen:'' Wenn $x^2$ gerade, dann $x$ gerade (Wenn $2 \mid x^2$, dann $2 \mid x$).

''Beispiele:'' $2^2 = 4$ (gerade), $4^2 = 16$ (gerade), $3^2 = 9$ (ungerade)

''Annahme:'' Wenn $2 \mid x^2$, dann $2 \nmid x$.


''Beweis:'' 

$x \text{ ungerade: } 2k+1\text{, } k \in \N $

$x^2 \text{gerade: } 2z \text{, } z \in \N$

$\Rightarrow (2k+1)^2 = 4k^2 + 4k + 1 \Rightarrow = ungerade, da +1$

$\Rightarrow \unicode{x021AF}$ Widerspruch, da $x^2$ gleichzeitig gerade und ungerade wäre.

==== Aufgabe 2 ====

Beweisen Sie die Aussage, wonach aus der Gültigkeit der Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ die Gültigkeiten von $\overline{A}$ und $\overline{B}$ folgen. Stellen Sie den Sachverhalt in einer
Wahrheitstabelle dar.

'''Lösung:'''

{| border="1" cellpadding="5" cellspacing="0"
!Zeile
!$A$
!$B$
!$C$
!$\overline{A}$
!$\overline{B}$
!$\overline{C}$
!$A \Rightarrow B$
!$B \Rightarrow C$
|-
||1|| W || W || W || F || F || F || W || W 
|-
||2|| W || W || F || F || F || W || W || F
|-
||3|| W || F || W || F || W || F || F || W
|-
||4|| W || F || F || F || W || W || F || W
|-
||5|| F || W || W || W || F || F || W || W
|-
||6|| F || W || F || W || F || W || W || F
|-
||7|| F || F || W || W || W || F || W || W
|-
||8|| F || F || F || W || W || W || W || W
|-
|}


Nur in Zeile 8 folgen aus der Gültigkeit der Aussagen $A \Rightarrow B$, $B \Rightarrow C$ und $\overline{C}$ die Gültigkeiten von $\overline{A}$ und
$\overline{B}$, also wenn $A$, $B$ und $C$ nicht gelten.
{| border="1" cellpadding="5" cellspacing="0"
!Zeile
!$\overline{A}$
!$\overline{B}$
!$\overline{C}$
!$A \Rightarrow B$
!$B \Rightarrow C$
|-
||8|| W || W || W || W || W
|-
|}

==== Aufgabe 3 ====

Was kann man über die Gültigkeit von A und B schließen, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten?
Verwenden Sie die Tabelle aus der vorhergehenden Aufgabenlösung.

'''Lösung:'''

Laut den Zeilen 1, 5 und 7 aus der obigen Tabelle folgt, dass, wenn bekannt ist, dass $A \Rightarrow B$, $B \Rightarrow C$ und $C$ gelten, $A$ und $B$ entweder beide gelten, beide nicht gelten oder nur $B$, aber nicht $A$ gilt.

{| border="1" cellpadding="5" cellspacing="0"
!Zeile
!$A$
!$B$
!$C$
!$A \Rightarrow B$
!$B \Rightarrow C$
|-
||1|| W || W || W || W || W 
|-
||5|| F || W || W || W || W
|-
||7|| F || F || W || W || W
|-
|}

=Kreativaufgabe=
==Das MU-Rätsel (MU puzzle)==
===MIU-System (Douglas R. Hofstadter)===

Die Hauptfrage lautet: Ist MU ein Satz des MIU-Systems?

=====Symbole:=====
 M, I, U

=====Axiom:===== 
MI

=====Regeln:=====

 x verhält sich in diesem Fall als eine Variable (eine String von Symbolen).

(1) Wenn xI ein Satz ist, dann auch xIU.

(2) Wenn Mx ein Satz ist, dann auch Mxx.

(3) In jedem Satz kann III durch U ersetzt werden.

(4) UU kann aus jedem Satz weggelassen werden.

=====Typografische Regeln:=====

 Typografische Regeln sind die Regeln, die in einer leicht verstandlichen Form der Textmanipulation sind.

(1) "Füge an den rechten Teil eines Satzes ein U an, wenn dieser mit I endet."

(2) "Kopiere den Teil eines Satzes, der rechts neben M steht und füge ihn am rechten Ende an."

(3) "Ersetze den Teil eines Satzes durch U, welcher drei aufeinanderfolgende I's besitzt."

(4) "Lösche den Teil eines Satzes, welcher aus zwei aufeinanderfolgende U's besteht."

=====Verwendung der typografischen Regeln:=====

MI $\rightarrow$ MIU $\rightarrow$ MIUIU $\rightarrow$ MIUIUIUIU ... [1,2,2]

MI $\rightarrow$ MII $\rightarrow$ MIIII $\rightarrow$ MUI $\rightarrow$ MUIUI $\rightarrow$ MUIUIUIUI $\rightarrow$ ... [2,2,3,2,2]

		   $\hspace{20mm}\rightarrow$ MIU $\rightarrow$ ... [2,1]

		   $\hspace{20mm}\rightarrow$ MIIIIIIII $\rightarrow$ MUUII$\rightarrow$ MII$\rightarrow$ ... [3,4]

=====Lösung des MU-Rätsels=====

Die Lösung lautet nein. Unabhängig von Anzahl der verwendeten Regeln ist es unmöglich den String MI in den String MU zu wechseln.

Für den Beweis beobachtet man die Invarianz d.H. die Eigenschaft, die sich nicht im Lauf der benutzten Regeln ändert.

In diesem Fall schaut man die Anzahl der I in dem String an. Nur der zweite und dritte Regel ändert diese Anzahl.

Regel Nr. 2 doppelt die Anzahl und Regel Nr. 3 vermindert um 3. Die Invarianz Eigenschaft bedeutet, dass die Anzahl der I nicht durch 3 teilbar ist.

 Am Anfang die Anzahl der I ist 1. 1 ist nicht durch 3 teilbar.
 Verdopplung der Nummer, die nicht durch 3 teilbar ist, macht nicht die Nummer durch 3 teilbar.
 Substraktion der Nummer 3 von der Nummer, die nicht dur 3 teilbar ist, macht auch nicht die Nummer durch 3 teilbar.