Nur Äquivalenz, Negation und Konjunktion verfügbar

Gregor

Kalkülfan schrieb:

Mit der Disjunktiven Normalform kann man ja alle anderen Wahrheitsfunktionen simulieren. Ich habe mich jetzt gefragt, ob auch das Dreigespann {Negation, Äquivalenz, Konjunktion} möglicherweise in der Lage ist, alle übrigen Wahrheitsfunktionen (ohne Zuhilfenahme von Disjunktion oder Kontravalenz) zu simulieren? a) Kann man das beweisen, dass das geht? b) Falls ja, WIE kann man das beweisen?

1. Es geht.
2. Man kann es ganz einfach beweisen, indem man alle 16 Funktionen in eine Wahrheitswerttabelle aufschreibt und das entsprechende Äquivalent aus Konjunktion und Negation daneben. (Äquivalenz brauchst Du nicht.)

wenn du nur AND,NOT und Äquivalenz einsetzen möchtest, geht das auch.
Äquivalenz ist sogar wieder überflüssig.

Man muss also nur überlegen, wie man OR zusammenbekommt.
Dabei gilt

a OR b = NOT ( NOT(a) AND NOT(b) )

Bashar

Man kann auch nur mit Äquivalenz auskommen, denke ich.

Besten Dank für die Tipps!
Ich konnte mir das schwer vorstellen, dass man nur aus 2 Junktoren alle anderen simulieren kann. Womöglich reicht auch {EQV,NOT}? Das wäre toll!
thx

SG1

Bashar schrieb:

Man kann auch nur mit Äquivalenz auskommen, denke ich.

Wie soll denn das gehen? (F <=> F) ist 'ne Tautologie, ((F <=> F) <==> F) ist wieder aequivalent zu F - und was grossartig anderes kann man doch nicht bauen, oder?

Bashar

F <==> 0 ist die Negation von F, damit kann man sicher was anstellen. OK, vielleicht zählt 0 als nullärer Operator, dann reicht Äquivalenz allein nicht.

SG1

Selbst dann seh ich nicht, wie Du was anderes ausser Kontradiktion, Tautologie, <=> und XOR darstellen willst.

CStoll

Mit Äquivalenz bzw. XOR alleine wirst du nicht auskommen. Aber wenn du dein Sortiment wirklich auf einen Junktor reduzieren willst, habe ich zwei andere Kandidaten für dich: NAND und NOR - damit kannst du alle anderen booleschen Funktionen bilden:

NOT a   = a NAND a             = a NOR a
a AND b = NOT (a NAND b)       = (NOT a) NOR (NOT b)
a OR b  = (NOT a) NAND (NOT b) = NOT (a NOR b)

Jester

Wirklich nett ist auch das Gespann aus XOR und AND. Wenn man AND als Multiplikation und XOR als Addition im Körper mit 2 Elementen auffasst (also 1+1=0), dann kann man Aussagen mit n Variablen als Polynom mit n Variablen hinschreiben und zum Auswerten einfach einsetzen. Konjunktion zweier Formeln ist dann das Produkt und XOR die Summe. Wenn man das noch ein bißchen weiter treibt kommt man zur Ringnormalform.

Bashar

Jester schrieb:

Wirklich nett ist auch das Gespann aus XOR und AND.

Ups, genau das meinte ich. Auch bekannt als Zhegalkin-Polynome oder einfach Antivalente Normalform. Was mit XOR geht, geht auch mit XNOR (NXOR?), hab ich mir gedacht (soweit müsste es noch stimmen), aber das AND hab ich unterschlagen.

Gibt es bezüglich der Kontravalenz, d.h. XOR bzw. 'ausschließendes ODER'
irgend welche genauen Regelungen bezüglich der Priorität des Junktors, d.h. ob er 'Vorrang' vor gewissen anderen Junktoren hat (ähnlich wie Konjunktion VOR Disjunktion ausgewertet werden soll, wenn keine Klammern da sind?)?

Beispiel:

p XOR q AND r // Was kommt zuerst? (p XOR q) oder (q AND r)

p OR q XOR r // Hier auch unklar: Hat das einschließende oder das
// ausschließende Oder Vorrang bei der Auswertung?

Danke, wenn es jemand weiß!