Logik-Rätsel maschinell lösen

knivil

cooky451 schrieb:

z.B. für 9 Kugeln:

a = {1, 2, 3}, b = {4, 5, 6}, c = {7, 8, 9}

a != b
a == c

4 != 5
4 != 6

-> 4

Das ganze Ding nennt sich constraint programming. a,b,c sind deine Domains, gefolgt von den Nebenbedingungen. Geschicktes Suchen in Algorithmenform fuehrt dann zur Loesung.

Wobei Spielregeln bei denen man gewinnen und verlieren kann ist doch quasi das Gleiche, das gucke ich mir mal an.

Habe in meinem Seminar/Praktikum/whatever: General Game Playing http://www.eclipseclp.org/ benutzt, geht ganz gut. Nach diesen Stichworten im Netzt einfach suchen.

volkard

JFB schrieb:

Der Tipp von volkard ist überdies sehr nützlich (wenngleich ich das Buch in Teilen unnötig aufgebläht gefunden habe).

Ich habe geschwelgt. Und gelernt. Viel. Grandios…
Und erst die Hälfte kapiert. me silly.

Ist aber definitiv kein Nachschlagewerk, was im Schrank stehen muss. Hälfte reicht ja. Vielleicht sollten wir einen GEB-Pool bilden. Man liest es meist nicht zweimal, fürchte ich. Und falls doch, kann man es ja nochmal ordern.
JFB hat anscheinend eins frei. Da ist es nur noch eine Sache des Portos.

Ich mag mich noch noch trennen, weil es so geil war, und ich es eigentlich am nächsten Wochenende wieder anfangen will, und dann am nächsten, am nächsten, ein endloses Band.

edit: Vielleicht auch einen größeren Pool. TAOCP muß man auch lesen aber nicht stehen haben.

nachtfeuer

volkard schrieb:

Ich habe geschwelgt. Und gelernt. Viel. Grandios…
Und erst die Hälfte kapiert. me silly.

Ist aber definitiv kein Nachschlagewerk, was im Schrank stehen muss. Hälfte reicht ja. Vielleicht sollten wir einen GEB-Pool bilden. Man liest es meist nicht zweimal, fürchte ich. Und falls doch, kann man es ja nochmal ordern.
JFB hat anscheinend eins frei. Da ist es nur noch eine Sache des Portos.

Ich mag mich noch noch trennen, weil es so geil war, und ich es eigentlich am nächsten Wochenende wieder anfangen will, und dann am nächsten, am nächsten, ein endloses Band.

Man kann es eigentlich auch beim Buchhändler um die Ecke bestellen, und am nächsten Tag abholen, die haben ja Großhändler wie z.B. http://www.libri.de/shop/action/productDetails/1339897/douglas_r_hofstadter_goedel_escher_bach_ein_endloses_geflochtenes_band_3423300175.html

Als ich das Buch das erste mal durchgesehen hatte, fand ich es gar nicht so prickelnd. Das lag aber hauptsächlich an dem KI-Teil, die Bilder vom Escher kannte ich zur Genüge und Gödel hatte ich damals eh schon ganz intuitiv verstanden, das war nur eine formale Bestätigung, nichts wirklich neues. Aber die Art und Weise, wie Gödel an den Beweis heran ging, war, schon beeindruckend.

..und irgendwo ist auch wieder klar, dass so vieles auf die Arbeiten von Cantor zurückgeht, und das ist irgendwie schade, dass solche Bücher wie gesammelte Aufsätze von Cantor nicht aktuell bleiben (weil sie so grundlegend und einflußreich sind und didaktisch möglicherweise auch verständlicher, da ja original (mit etwas Glück).

Man könnte sich natürlich auch extra Logik-Bücher besorgen, wie
http://www.amazon.de/Einführung-mathematische-Logik-Moderne-Mathematik/dp/3525405405/
http://www.amazon.de/Haskell-Logic-Maths-Programming-Computing/dp/0954300696/

Und ein neueres Buch von Format ist sicher auch das hier:
http://www.amazon.de/Grenzen-Mathematik-Reise-Kerngebiete-mathematischen/dp/382742559X/
(oder das hier? )
http://www.amazon.de/Das-Geheimnis-transzendenten-Zahlen-Einführung/dp/3827422744/
(hmm...oder doch dann lieber sowas hier, ganz allgemeiner Natur..)
http://www.amazon.de/Die-Entdeckung-Unteilbaren-Quanten-Quarks/dp/3827424844/
(wäre dann aber gar nicht mehr so richtig logisch? nachvollziehbar? Kirre?

cooky451

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

nachtfeuer

cooky451 schrieb:

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

Ob das auch wirklich wahr ist, und das mit Sicherheit und welcher Sicherheit und unter welchen Bedingungen. Wahrheiten, die wir auswendig kennen, oder fleißig geübt haben, stehen erstmal im Zweifel.
Wie wäre es z.B. mit x + 5 = 3? Auch nicht unmöglich. Und versuch mal x + 3 mit Binärzahlen, die kennen gar keine 3.
Auf welche Zahlenmenge bezieht sich deine Aussage, auf welche kann man sie anwenden?
Warum sollte 1 + 1 = 2 sein?

Und...gibt es die Menge aller Mengen oder nicht?

cooky451

Also Fragestellungen wie warum 1 + 1 = 2 sind würde ich erstmal als trivial ansehen, genau so wie den Rest den du geschrieben hast. Das legt doch die Grammatik bereits fest. Ob 2 jetzt 2 oder 10 oder was auch immer ist, interessiert doch gar nicht. Dass es das Ergebnis von 1 + 1 gibt, das mag weniger trivial sein, bzw. dass jede Addition mit natürlichen Zahlen wieder eine natürliche Zahl ergibt.

nachtfeuer schrieb:

Und...gibt es die Menge aller Mengen oder nicht?

Hehe, das war dann die einzig interessante Frage. Hatten wir aber schon mal. Wie war das? Für jedes Element soll entscheidbar sein, ob eine Menge es enthält oder nicht. Bei der Menge die alle Mengen enthält, die nicht sich selbst enthalten, ist somit nicht entscheidbar ob sie sich selbst enthält oder nicht. Daher müssen wir entweder festlegen, dass alle Mengen sich enthalten, oder dass keine Menge sich selbst enthalten darf. Und weil die Mathematiker zu faul sind immer Ausnahmeregelungen zu basteln, nimmt man letzteres. Und daher gibt es auch nicht die Menge aller Mengen. Joa, ich hoffe ich habe das noch halbwegs zusammen bekommen.

Aber das Beispiel mit x + 1 = 3 war absichtlich gewählt. Es scheint natürlich trivial, und das war gewollt. Ein Algorithmus könnte solche Aufgaben lösen, nicht aber ein (einfacher) Taschenrechner. Daher habe ich mich gefragt, ob es genau solche Probleme auch in der Logik gibt, und wie diese formuliert werden.

hustbaer

cooky451 schrieb:

Hm.. Bücher zur Logik, interessant. Was ist denn eine typische Fragestellung der Logik, wenn eine typische Frage der Mathematik wäre, ein x zu finden, das die Gleichung x + 1 = 3 erfüllt?

Ich würde "Wem gehört der Fisch?" als klassische Logik-Aufgabe ansehen.

SeppJ

Antoras schrieb:

@SeppJ

SeppJ schrieb:

Um herauszufinden, ob die Fehlkugel schwerer oder leichter ist, vergleichst du zuerst die eine Hälfte der Kugeln mit der anderen. Dann nimmst du die schwerere Hälfte und vergleichst wieder zwei Hälften von dieser Hälfte.

Der erste Satz ist so weit ok. Am Beispiel 3,4,2 > 1,7,6 würde man rechts mit links vergleichen. Ich sehe jetzt nicht wie ich die schwere Hälfte unterteilen kann und wieder herausbekomme wie das Verhältnis zueinander ist. Woher kommt die Information wie 3,4,2 zueinander stehen? Die muss ich doch erst anhand der anderen Beispiele ermitteln. Oder habe ich deine Idee jetzt falsch verstanden?

Ok, nehmen wir dein Kugelbeispiel, die 4. Kugel ist leichter. Ich erweitere es sogar auf 16 Kugeln, damit wir uns die Sonderbehandlung von N ungerade ersparen und damit man wenigstens mal sieht, dass das Verfahren effizient ist.
Ich wiege:
1,2,3,4,5,6,7,8 : 9,A,B,C,D,E,F,G.
zweite Hälfte ist schwerer. Schlussfolgerung: Noch keine, aber die Information ist später nützlich.
Ich wiege:
9,A,B,C : D,E,F,G
beide gleich schwer. Schlussfolgerung: die Fehlkugel ist leichter als die anderen und sie ist in 1-8.
Ich wiege:
1,2,3 : 6,7,8
beide gleich schwer. Schlussfolgerung: Die Fehlkugel ist in 4,5
Ich wiege:
4 : 5
zweite Hälfte ist schwerer. Schlussfolgerung: Die Fehlkugel ist 4.

Auf dein altes Beispiel übertragen (1-7) ist die Methode sogar trivial:
Ich wiege:
1,2,3 : 5,6,7
beide gleich schwer. Schlussfolgerung: Die Fehlkugel ist 4.

Ein bisschen modifiziert, die Fehlkugel sei 5 und sie sei leichter. Dann geht mein Algortihmus:
Ich wiege:
1,2,3 : 5,6,7
erste Hälfte ist schwerer. Schlussfolgerung: 4 ist keine Fehlkugel
Ich wiege:
1 : 3
beide gleich schwer: Schlussfolgerung: 1,3 sind keine Fehlkugeln
ich wiege:
2 : 3
beide gleich schwer: Schlussfolgerung: 2 ist keine Fehlkugel und die Fehlkugel ist leichter als die anderen.
Ich wiege:
5 : 7
zweite Hälfte ist schwerer: Schlussfolgerung: 5 ist die Fehlkugel.

Hier sieht man, dass mein Algorithmus für kleine N leicht umständlich werden kann.

@volkard: Ja, die erste Hälfte war ein Erlebnis. Aber irgendwann verliert sich der Autor IMHO einfach in einer Unmenge von (mal mehr, mal weniger passenden) Analogien und Querbezügen, sodass es fürchterlich schwer wird, irgendwie seinem Punkt noch zu folgen (auch das ironischerweise eine seltsame Art der Selbstbezüglichkeit ;))

cooky451

hustbaer schrieb:

Ich würde "Wem gehört der Fisch?" als klassische Logik-Aufgabe ansehen.

Ne, da hast du etwas nicht verstanden. Die Frage ist generell nicht zu beantworten, du hast das wohl mit "Wie teuer ist der Fisch?" verwechselt. :p

hustbaer

Also ich meine das da
http://de.wikipedia.org/wiki/Zebrar�tsel

Wobei ich Fisch statt Zebra in Erinnerung hatte.
Und wieso soll das nicht zu beantworten sein?