7.2

[Erdös-Index 97]

Mein Vorschlag zu dem Thema:

A | non-A || A ^ A | A v A | A = A
f | t || f | f | t
t | f || t | t | t

Einzeln entspricht offensichtlich keiner der Junktoren dem non-A.
Meine Argumentation betreffend zusammengesetzter Funktionen ist folgende:
Interessant ist hier nur der Fall A = t
(F sei Element der Menge {{A ^ A},{A v A},{A = A}})
^ : A ^ A ist t für A = t. Die anderen beiden Funktionen sind bei A = t ebenfalls immer t, deswegen ist F ^ F auch immer t.
v : Alle 3 Grundfunktionen sind bei A = t ebenfalls t, also ist F v F auch immer t.
= : Da alle 3 Grundfunktionen bei A = t t sind, ist auch F = F immer t.

In keinem Fall ist es also möglich, mit den gegebenen Junktoren ein f bei A = t zu erzeugen wie es in non-A der Fall ist.
War das jetzt ein Beweis durch Induktion?

[mauerblümchen]

Mein Vorschlag zu dem Thema:

A | non-A || A ^ A | A v A | A = A
f | t || f | f | f
t | f || t | t | t

ich glaube das die NEXOR verknüpfung die werte liefert
A = A
t
t
aber das ist nicht das eigetnlich, ich glaube es muss zusätzlich gezeigt werden, wenn ich A mit f oder t verknüpfe, da dies ja eigentlich nichts an einer einstelligen operation ändert, oder?

[Erdös-Index 97]

Nexor, laut Skriptum auch bekannt als "genau dann wenn" liefert immer t zurück, wenn beide Aussagenvariablen den gleichen Wert haben. Bei A = A ist dies immer der Fall, A = A ist also immer t http://hades.gothic.at/iforum/images/smilies/wink.gif.

[Old Thrashbarg]

Dann solltest du das aber in deinem oberen Post ändern. Für A=A gehören dann 2x true in die Spalte
Sonst hab ichs auch so

[Erdös-Index 97]

danke für den hinweis

[ein_stein2000]

i habs auch so durch logische überlegung ... aber keine ahnung, ob das ein induktionsbeweis ist (wie es in der angabe steht) ...

[Studigel]

Ich hab den "Induktionsbeweis" mal so aufgestellt. Ich weiß aber nicht ob das wirklich als Beweis durchgeht.

A^AvA=A
A=A ist immer true (in weiterer Folge 1)

A^Av1
Av1 ist immer 1

A^1
ist immer A

QED

[FlatAlex]

Ich hab mir folgendes ueberlegt:

Ich soll blabla zeigen durch die Ueberlegung, dass keine einstellige Funktion ueber {f, t}, die aus AND, OR und NEXOR zusammengesetzt ist, der Negation entspricht.

Sei a \in {f, t} und ° \in {AND, OR, NEXOR}, -a sei das Komplement von a. Ich muss also zeigen, dass
a ° a GDW -a widerlegbar \forall ° \in {AND, OR, NEXOR}

Induktion ueber die Laenge der Formel, also die Anzahl der Operatoren (ich hoffe das ist die Laenge, sollte aber an der Loesung nicht viel aendern):

Induktions-Anfang:
n=1:
a ° a GDW -a widerlegbar \forall ° \in {AND, OR, NEXOR}

Induktions-Voraussetzung:
a °_1 a ... a °_n a GDW -a
widerlegbar \forall °_i \in {AND, OR, NEXOR} (mit i = 1 bis n)

Induktions-Schluss:
a °_1 a ... a °_(n+1) a GDW -a
widerlegbar \forall °_i \in {AND, OR, NEXOR} (mit i = 1 bis n+1)

Ist nun a °_(n+1) a = a, so koennen wir den Ausdruck ersetzen
und die Voraussetzung anwenden. Da aber

a °_(n+1) a GDW -a
widerlegbar \forall °_(n+1) \in {AND, OR, NEXOR}

ist auch die ganze Formel widerlegbar.



Hoffe ich hab mich nicht irgendwie bloed vertan.

MfG,
Alex

[mr-schinken]

Ist nun a °_(n+1) a = a, so koennen wir den Ausdruck ersetzen
und die Voraussetzung anwenden. Da aber

a °_(n+1) a GDW -a
widerlegbar \forall °_(n+1) \in {AND, OR, NEXOR}

ist auch die ganze Formel widerlegbar.



Ist nun a °_(n+1) a = a, so koennen wir den Ausdruck ersetzen

naja das ist doch nicht fuer alle 3 operatoren erfuellt. A NEXOR A ist ja immer true.

ich weiss nicht ob das jetzt den beweis zerstoert oder nicht, aber irgendwie kommt es mir dadurch etwas hand waving vor.

[grassi3000]

Ich hab mal ne Frage so nebenbei: Wo steht denn die Theorie hinter dieser vollständigen Induktion im Skriptum. Ich finds net.

Oder muss ich das, was wir in Mathe zur Induktion gelernt haben ummünzen?

[Erdbeere]

Ich hab mal ne Frage so nebenbei: Wo steht denn die Theorie hinter dieser vollständigen Induktion im Skriptum. Ich finds net.

Oder muss ich das, was wir in Mathe zur Induktion gelernt haben ummünzen?Ich habe s.68 und s.69 geschaut...
3.14 Definition und 3.15 Beispiel..
Vielleicht das hilft dir..:D

[grassi3000]

Mhm ... leider nicht ...

ich versteh nicht, wie ich das mit einer vollständigen Induktion machen soll...

[FlatAlex]

naja das ist doch nicht fuer alle 3 operatoren erfuellt. A NEXOR A ist ja immer true.
Eben, denn weil es *immer* true ist, koennen wir einen Fall finden, in dem a NEXOR a = a ist (naemlich fuer a=t), auf den sich in weiterer Folge die Voraussetzung anwenden laesst, womit wir die Formel widerlegt haetten.

[naf]

für dieses beispiel ist glaub ich nich die vollständige induktion im mathematischen sinn gemeint sondern eher die logische variante:

http://de.wikipedia.org/wiki/Induktion_(Mathematik)

http://de.wikipedia.org/wiki/Induktion_(Logik)

[grassi3000]

Wenn ich mir die erklärung der logischen Induktion durchlese, dann müsste es bei dem Beispiel doch reichen, wenn ich mir eine kombination aus den verschiedenen operatoren hernehme, und dann auf das allgemeine schließe.

Bin ich hier auf dem richtigen weg?

[FlatAlex]

Glaub ich aber schon, dass da die mathematische Induktion gefragt ist, denn zum einen passt logische Induktion hier gar nicht, und zum anderen steht sogar "Induktion nach der Groeße der entsprechenden Formeln", das hoert sich fuer mich schon sehr verdaechtig an.

[Variable]

Induktions-Schluss:
a °_1 a ... a °_(n+1) a GDW -a
widerlegbar \forall °_i \in {AND, OR, NEXOR} (mit i = 1 bis n+1)

Ist nun a °_(n+1) a = a, so koennen wir den Ausdruck ersetzen
und die Voraussetzung anwenden. Da aber

a °_(n+1) a GDW -a
widerlegbar \forall °_(n+1) \in {AND, OR, NEXOR}

ist auch die ganze Formel widerlegbar.

[/QUOTE]
@flatAlex , wie kommst du auf den induktions schluss ?
bzw was meinst du mit GDW

und naja wenn etwas wiederlegbar ist ist es ja laut def. auch erfüllbar
müsstest du nicht unerfüllbarkeit beweisen ?

[FlatAlex]

GDW = genau dann, wenn, also NEXOR

Und aehm, ich soll zeigen, dass keine einstellige Funktion ueber {f, t}, die aus AND, OR und NEXOR zusammengesetzt ist, der Negation entspricht. Eine Funktion die dieser entspraeche, muesste aequivalent der Negation sein, also mit NEXOR verknuepft IMMER t ergeben. Gut, so eine Fkt zu finden ist aber unmoeglich laut Angabe, wie sieht also eine Funktion aus, die *nicht* der Negation entspricht: genau, die Aequivalenz ist *widerlegbar*, sie muss nicht unerfuellbar sein, denn es reicht, wenn sie in manchen Faellen andere Funktionswerte annimmt.

[Variable]

GDW = genau dann, wenn, also NEXOR

ah...


Eine Funktion die dieser entspraeche, muesste aequivalent der Negation sein, also mit NEXOR verknuepft IMMER t ergeben.


was meinst du damit ?
warum muss die funktion (ich nehm mal an eine kombi aus den drei gegebenen funktionen ) verknuepft mit NEXOR immer t ergeben.....?

[FlatAlex]

Na weil sie sonst nicht die Negation ersetzen koennte, es kann ja nur eine Funktion eine andere ersetzen wenn die beiden aequivalent sind, d.h. wenn die Wahrheitstafeln gleich sind. Wenn auch nur eine Zeile nicht uebereinstimmt (Aequivalenz widerlegbar), so kommt die Funktion schon nicht mehr als Ersatz in Frage.

[Variable]

versteh um zu zeigen das das ganze nicht funktional vollständig is muss immer true rauskommen ...wenn true und false rauskommen ( bei einer zweizeiligen wahrheitstabelle) wär es ja bewiesen, was ja nicht das ziel is
richtig ?

[maitscha]

wer nicht mit-chattet ist selber schuld ;) server: frost.htu.tuwien.ac.at, channel: #theoinf1

[FlatAlex]

nein nein, genau verkehrt herum

also nochmal:

Zwei Funktionen sind aequivalent, wenn sie NEXOR verknuepft immer t ergeben. Wenn sie aequivalent sind, kann eine die andere ersetzen. Ein kleines Beispiel: die Funktion a NAND a ist aequivalent zu -a, denn

a | a NAND a | -a | (a NAND a) NEXOR -a
----------------------------------------
f | t | t | t
t | f | f | t

Diese zwei Funktionen sind also aequivalent und ich kann die eine mit der anderen nachbilden.

Weil das bei uns *nicht* der Fall ist, dass wir NOT durch eine andere Funktion nachbilden koennen, muss sich der Wahrheitsverlauf unserer Funktion von dem von NOT in *mindestens einer* Zeile unterscheiden, das heisst die zwei Funktionen NEXOR verknuepft mindestens einmal f sein.

Klar?

[konsch]

Hallo!

Also ich weiss nicht genau, wie der Beweis jetzt formal sein muss.

Logisch ist ja folgendes:

A !A | (A n !A) | (A v !A) | (A = !A)
t f | f | w | f
f t | f | w | f


Daraus sieht man ja schon, dass die Negation NIE aus diesen Funktionen gebildet werden kann, da die Ergebnisse immer gleich sind. Oder?

Aber wie muss nun die "Induktion nach der Grösse entsprechender Formeln" aussehen :confused:

[stichri]

also wir stellen mal unsere lösungen vom montag online.
haben meistens die seitenzahl dazugeschrieben wo's im skriptum steht
hoffe ihr könnts lesen...


http://websrv.netparknet.at/oejab/chris/uni/theoinf/UE7/7_2.jpg

alle lösungen für UE7
http://websrv.netparknet.at/oejab/chris/uni/theoinf/UE7/

anna & chris

[Veronika]

So ists in der Übung gemacht worden:

Induktionsanfang:
n=0 (n=Anzahl der Funktionen), Ergebnis: A

Induktionshypothese:
A n-mal verknüpft ergibt immer A oder t (siehe Wahrheitstabelle, im Fall von A ist f, dann A=A ergibt t), also nie not-A

A A^A AvA A=A not-A
__________________________________
t t t t f
f f f t t

Induktionsbeweis: laut untenstehenden Wahrheitstabellen gibt jede weitere Verknüpfung (also die n+1. Verknüpfung) wieder nur A oder t. und nie not-A

^ | A t
________
A | A A

t |A t

v | A t
_______
A |A t

t |t t

= | A t
________
A |t A

t |A t