BuK/IIm14/Studenten/s3ankrau1/Vorlesung5

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
'''Konstruieren sie eine Prozedur, welche prüft ob $w$ die Form $uu$ besitzt!''' 

<code id="5589462c1c7f4">
function pruefew(w){
	var anzahlA = 0;
	var anzahlB = 0;
	var anzahlC = 0;
	
	var charArray = w.split('');
	var sortedCharArray = w.split('');
	
	if(charArray.length!=0){
		sortedCharArray.sort();
		
		for(var i = 0; i<charArray.length; i++){
			if(charArray[i]!=sortedCharArray[i]){
				return '#f';
			}
		}			
		
		for(var i = 0; i<charArray.length; i++){
			if(charArray[i]=='a'){
				anzahlA++;
			}
			else if(charArray[i]=='b'){
				anzahlB++;
			}
			else{
				anzahlC++;
			}
		}
		
		if(anzahlA==anzahlB){
			if(anzahlB==anzahlC){
				return '#t';
			}
			else{
				return '#f';
			}
		}
		else{
			return '#f';
		}
	}
	else{
		return '#f';
	}
}
</code>
<run id="5589462c1c868">pruefew("aaabbbccc")</run>


----


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.

-----------------------------------

Gegeben ist:

$A \wedge B \Rightarrow C$ 

und

$\neg C \wedge B \Rightarrow \neg A$

Mit Hilfe der Wahrheitstabelle kann die Äquivalenz gezeigt werden:

{| border="1" cellpadding="5" cellspacing="0"
!$A$
!$B$
!$C$
!$E=A \wedge B$
!$F=E\Rightarrow C$
!$G=\neg C \wedge B$
!$H = G \Rightarrow \neg A$
!$I = F \Leftrightarrow H$
|-
||0||0||0||0||1||0||1||1
|-
||1||0||0||0||1||0||1||1
|-
|style="background-color:#3ADF00" | 0|| style="background-color:#3ADF00" | 1|| style="background-color:#3ADF00" | 0|| style="background-color:#3ADF00" | 0|| style="background-color:#3ADF00" | 1|| style="background-color:#3ADF00" | 1|| style="background-color:#3ADF00" | 1|| style="background-color:#3ADF00" | 1
|-
||0||0||1||0||1||0||1||1
|-
||1||1||0||1||0||1||0||1
|-
||1||0||1||0||1||0||1||1
|-
||0||1||1||0||1||0||1||1
|-
|style="background-color:#3ADF00"|1|| style="background-color:#3ADF00"| 1|| style="background-color:#3ADF00"| 1|| style="background-color:#3ADF00"| 1|| style="background-color:#3ADF00"| 1|| style="background-color:#3ADF00"| 0|| style="background-color:#3ADF00"| 1|| style="background-color:#3ADF00"|1
|-
|}


In Zeile 8 ist die Bestätigung des 1. Satzes $A \wedge B \Rightarrow C$. Aus der 3. Zeile ist die einzige Belegung für die Aussage $\neg C \wedge B \Rightarrow \neg A$ zu finden, wobei in dem Fall $\neg A$ gilt und somit der 2. Satz bestätigt ist.


----


Zeigen Sie die Unentscheidbarkeit von $L_{Σ^∗} := \{\langle M \rangle | L(M) = Σ^∗\}$ durch Reduktion des Halteproblems.