Aussagenlogik (n-stelliger Junkor)

Question

Stellen Sie sich folgende Situation vor: Sie unterhalten sich auf einer Party mit einem Informatik-Studenten aus einem
höheren Semester. Dieser erzählt Ihnen stolz von seiner neuesten Entdeckung im Rahmen seiner Bachelorarbeit: einen
völlig neuen k-stelligen Junktor in der Aussagenlogik, genannt Humbug-Junktor. Um seine Forschungsergebnisse bis zur
Veröffentlichung geheim zu halten, erzählt er Ihnen allerdings nicht die genaue Semantik. Um Ihren enthusiastischen
Kommilitonen etwas den Wind aus den Segeln zu nehmen, beweisen Sie ihm folgendes:
Der Humbug-Junktor lässt sich ausdrücken als eine Formel, welche ausschließlich die Junktoren ∧ und ¬ verwendet.

Ansatz:
Mein Ansatz wäre jetzt zu zeigen, dass alle Junktoren mit ∧ und ¬ dargestellt werden können und deswegen auch dieser.
Jemand Vorschläge?

Comments

Mein Ansatz wäre jetzt zu zeigen, dass alle Junktoren mit ∧ und ¬ dargestellt werden können

Das ist ein guter Ansatz.

Was bedeutet bei dir Junktor?

---

Folgende Operationen (AND, OR, IMPLIKATION, ÄQUIVALENZ)

---

A ∧ B ist gleichbedeutend mit A ∧ B.

A ∨ B ist gleichbedeutend mit ¬(¬A ∧ ¬B)

A → B ist gleichbedeutend mit ¬(A ∧ ¬B)

A ↔ B ist gleichbedeutend mit ¬(A ∧ ¬B) ∧ ¬(¬A ∧ B)

Damit sind alle deine Junktoren mit ∧ und ¬ dargestellt.

---

Wie kann man das nun in einem Beweis für einen n stelligen Junktor benutzen? Danke

---

Zunächst solltest du deine Vorstellung von dem anpassen, was ein Junktor ist.

Ein Junktor ist eine Abbildung von {0, 1}ⁿ nach {0, 1}.

Bekannt sollte sein, dass alle Junktoren mit n ≤ 2 mittels ∧ und ¬ dargstellt werden können (nicht nur die, die du genannt hast).

Dann bietet sich eine vollständige Induktion über n an.

---

Also könnte ein Induktionsschritt provisorisch so sein, dass man für n $$\leq$$ 2 alle Junktoren mit $$\neg \wedge$$ dargestellt werden können und für n+1 gilt, dass man ein zusätzlichen Schritt hat der =1 ist und somit wieder mit $$\wedge \neg$$ dargestellt werden kann?

---

dass alle Junktoren mit n ≤ 2 mittels ∧ und ¬ dargstellt werden können

Falls das schon bewiesen wurde, dann kann k ≤ 2 als Induktionsanfang verwendet werden. Falls nicht, dann musst du das für den Induktionsanfang beweisen.

Im Induktonsschritt muss bewiesen werden: "Ist k ≥ 2 und können alle k-stelligen Junktoren unter Verwendung von ausschließlich ∧ und ¬ dargestellt werden, dann können auch alle k+1-stelligen Junktoren unter Verwendung von ausschließlich ∧ und ¬ dargestellt werden."

Answer 1

Sei \(B=\{0,1\}\), \(k\geq 2\) und \(f:B^{k+1}\to B\) eine \(k+1\)-stellige Funktion.

Sei \(G_i = \{(a_1,\dots,a_k)\in B^k | f(a_1,\dots,a_k, i)=1)\}\) für jedes \(i\in B\).

Sei \(g_i: B^k \to B\) mit \(g_i(a) = 1 \iff a\in G_i\) für jedes \(i\in B\).

Dann ist

         \(f(v_1,\dots,v_{k+1}) = (g_0(v_1,\dots,v_k) \wedge \neg v_{k+1}) \vee (g_1(v_1,\dots,v_k) \wedge v_{k+1})\).

Comments

gi:Bk→B mit gi(a)=1⟺a∈Gi für jedes i∈B.

Kannst du das erklärungshalber erläutern? Danke

---

G₀ ist die Menge der Tupel aus {0,1}^k, an die man eine 0 anhängen kann damit f den Wert 1 liefert.

G₁ ist die Menge der Tupel aus {0,1}^k, an die man eine 1 anhängen kann damit f den Wert 1 liefert.

g₀ ist die k-stellige boolsche Funktion, die genau für die Tupel den Wert 1 liefert, die in G₀ sind.

g₁ ist die k-stellige boolsche Funktion, die genau für die Tupel den Wert 1 liefert, die in G₁ sind.

---

Könntest du das Ganze nochmal gesamt erklären?

Kann das irgendwie immer noch nicht so ganz nachvollziehen und würde dies gern richtig verstehen.

---

Ein Beispiel:

a1	a2	a3	f(a1,a2,a3)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Dann ist

        G₀ = {(0,0), (0,1), (1,1)}

weil f(0,0,0) = f(0,1,0) = f(1,1,0) = 1 ist. Außerdem ist

        G₁ = {(0,0), (1,1)}
weil f(0,0,1) = f(1,1,1) = 1 ist.

Versuche, das anhand meines letzten Kommentars nachzuvollziehen.

Wahrheitstabellen von g₀ und g₁ sehen wie folgt aus:

a1	a2	g0(a1,a2)	g1(a1,a2)
0	0	1	1
0	1	1	0
1	0	0	0
1	1	1	1

Versuche, auch das anhand meines letzten Kommentars nachzuvollziehen.

Fülle dann folgende Wahrheitstabelle aus.

a1	a2	a3	¬a3	g0(a1,a2)	g0(a1,a2)∧¬a3	g1(a1,a2)	g1(a1,a2)∧a3	(g0(a1,a2)∧¬a3)∨(g1(a1,a2)∧a3)
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Überzeuge dich davon, dass in der letzten Spalte das gleiche steht wie in der letzten Spalte der ersten Tabelle.

---

Verstehe immer noch nicht so ganz, die g Abbildung, versuche gerade die Tabelle auszufüllen.

Was ist dort die Logik eine 1 oder 0 zu erhalten?

Bei g1 hängt man eine 1 ran und guckt ob 1 rauskommt, aber woraus ergeht sich die 1 ?

---

Es ist (0,0) ∈ G₀ weil f(0,0,0) = 1 ist. Deshalb ist g₀(0,0) = 1.

Es ist (0,0) ∈ G₁ weil f(0,0,1) = 1 ist. Deshalb ist g₁(0,0) = 1.

Es ist (0,1) ∉ G₁ weil f(0,1,1) = 0 ist. Deshalb ist g₁(0,1) = 0.

---

Es ist (0,0) ∈ G0 weil f(0,0,0) = 1 ist. Deshalb ist g0(0,0) = 1.

Woraus ergeht sich denn f(0,0,0)=1?

g0(0,0) ∧ 1) ∨(g1(0,0)∧0)

So jetzt noch g0 und g1.

(g0(v1,…,vk)∧¬vk+1)∨(g1(v1,…,vk)∧vk+1) .

---

Die Ergebnisse der 1. Tabelle, sind die frei erfunden und daraus ergibt sich dann die Menge für G0 und G1? also f(a1,a2,a3)

Kann gerade nicht nachvollziehen woher die Werte am Ende dann kommen.

---

Tabelle jetzt hinbekommen, also ist die generelle Idee dahinter, die Variablen bis k-1 auszuwählen.

Dann, zu sehen, diese zuzuordnen zu g0 oder g1

g0 ist dann 1, wenn eine 0 rangehängt wird und der gesuchte Junktor eine 1 rauswirft.

g1 ist dann 1, wenn eine 1 rangehängt wird und der gesuchte Junktor eine 1 rauswirft.

Nehmen also somit alle Fälle für die die Funktion 1 rauswirft und halbieren diese in g0 mit der Negation vom jeweiligen außer Betracht gezogenen Wert.

Dann g1 AND neg a_(außerBetrachtGezogen)

Oder g1 mit dem jeweiligen außer Betracht gezogenen Wert.

g1 And a_(außerBetrachtGezogen)

Verstehe jetzt mehr, danke.

Wie ist die generelle Idee wieso das funktioniert?

Ich weiß, dass wir im Endeffekt, alle ausgegeben 1en nehmen und diese die Funktion ergeben müssen. Da man diese aus allen 1en ermitteln kann.

Dieses Konzept ist mir noch nicht ganz klar. Danke für die Hilfe.

---

Die Ergebnisse der 1. Tabelle, sind die frei erfunden ...

Ja. Das ist ein Beispiel einer boolschen Funktion, deren Funktionsterm ausschließlich mit den Junktoren ∧ und ¬ dargestellt werden soll.

und daraus ergibt sich dann die Menge für G0 und G1?

Ja.

woher die Werte am Ende dann kommen.

Ich weiß nicht, welches Ende du meinst.

die generelle Idee dahinter

Die hast du gut erfasst.

und halbieren diese in g0 ...

Ich verstehe das Verb halbieren in diesem Zusammenhang nicht.

Wie ist die generelle Idee wieso das funktioniert?

Mein Ideen waren ungefähr folgende:

Es muss etwas gezeigt werden für jedes n ∈ ℕ. Also vollständige Induktion.

Der Induktionsanfang ist trivial; dass {∧, ¬} für n = 2 funktional vollständig ist, kann man durch Wahrheitstabellen zeigen.

Für den Induktionsschritt muss ich untersuchen, von n auf n+1 schließen. Also untersuche ich, welche Fälle bei n Variablen auftreten können. Diese Fälle habe ich in G₀ und G₁ aufgeteilt. Der Zusammenbau von f auf G₀ und G₁ war Probieren. Meine Intuition hat mir gesagt, dass das ein Zusammenbau funktionieren müsste.