boolesche algebra

Schlangenmensch

Ich habe die Schreibweise mit + und * grade als "US-Schreibweise" gefunden, dass war mir tatsächlich neu.

Fricky667 schrieb:

Konsequenterweise sollte man bei dieser Notation das Minuszeichen als Not-Operator verwenden. Wahrheitswerte Umdrehen ist ja intuitiv gesehen auch sowas wie eine Änderung des "Vorzeichens".

Das sehe ich nicht so. Dann hat man so Sachen wie A*-A = 0, was ja im Körper der reellen Zahlen mit (*,+) nur für A=0 gilt.
Auf der anderen Seite hätte man für "oder" dann A+-A=1, was auch wieder Murks ist.
Da halte ich die Schreibweise mit dem Strich drüber schon für ganz gut.

Fricky667

Schlangenmensch schrieb:

Da halte ich die Schreibweise mit dem Strich drüber schon für ganz gut.

Darüber ließe sich endlos streiten. ich habe auch schon das "not" als "'" gesehen, also not(a) == a'

Schlangenmensch schrieb:

Dann hat man so Sachen wie A*-A = 0, was ja im Körper der reellen Zahlen mit (*,+) nur für A=0 gilt.

"a and (not)a" ist ja auch 0. passt doch. wir sind ja hier nicht bei reals, sondern bei binärzahlen, also der endlichen menge {0,1}.

Btw, wenn wir jetzt schon bei abstrakter Algebra sind: bildet die menge der Binärzahlen mit or (oder mit and) eine Gruppe im sinne der Gruppenaxiome?
in beiden, in einem oder in keinem Fall?
Das ist doch eine interessante Frage ....

Schlangenmensch

Fricky667 schrieb:

"a and (not)a" ist ja auch 0.

Genau, aber wenn wir den Zahlenraum in R schauen, sehen wir A * -A <> 0, außer für A = 0. Das gilt auch für Binärzahlen übrigens, denn eine Binärzahl hat bekanntlich mehr als nur wahr und falsch. Man kann mit Binärzahlen vielmehr alle ganzen Zahlen darstellen.

Und ja, das vorzeichenbehaftete Binärsystem bildet eine additive Gruppe. (Wenn ich jetzt grade kein grundlegende Vorraussetzung vergessen habe)

Fricky667

Schlangenmensch schrieb:

Genau, aber wenn wir den Zahlenraum in R schauen, sehen wir A * -A <> 0, außer für A = 0. Das gilt auch für Binärzahlen übrigens, denn eine Binärzahl hat bekanntlich mehr als nur wahr und falsch.

Okay, sorry für meine Ungenauigkeit. Mit Binärzahl meinte ich den Zahlenraum der Bits und keine Kombination von beliebig vielen davon. Es sind also nur 0 und 1 da, und die Verknüpfungen AND und OR. Ich glaube dass {0,1,or} wie auch {0,1,and} eine Gruppe sind. Jetzt aber nur intuitiv geschätzt, die neutralen Elemente 0 oder 1 sind jedenfalls schonmal da. Mich interessieren eher Grenzfälle, die beweisen, dass es sich eben doch nicht um eine Gruppe handelt.

Schlangenmensch

Was ist denn bei {0,1,or} das neutrale Element und was das inverse Element?

Sagen wir neutrales Element is 0, da

0 or 0 = 0
1 or 0 = 1

Dann muss für das Inverse "i" gelten

1 or i = 0 => Widerspruch, es gibt kein Element das die Forderung erfüllt.
0 or i = 0

Also, keine Gruppe!

Fricky667

Auch ganz wichtig: keine der Operationen + oder * beamt uns aus dem binären Zahlenraum Z[2]. Das sieht gruppentheoretisch gar nicht so schlecht aus.

Schlangenmensch

Und bei"and" siehts auch schlecht aus. Neutrales Element ist die 1. Aber für 0*i = 1 wird daraus nix für das Inverse....

Fricky667

Schlangenmensch schrieb:

Was ist denn bei {0,1,or} das neutrale Element und was das inverse Element?

Sagen wir neutrales Element is 0, da

0 or 0 = 0
1 or 0 = 1

Dann muss für das Inverse "i" gelten

1 or i = 0 => Widerspruch, es gibt kein Element das die Forderung erfüllt.
0 or i = 0

Also, keine Gruppe!

Auf {0,1,or} bezogen:
Das neutrale Element ist: a or 0 = a, also: 0.
und das inverse Element ist: a or (not)a = 1, also 1.

Die Verknüpfung beider ist "0 or 1", also 1. Passt!
Wer von uns liegt nun falsch?

SeppJ

Fricky667 schrieb:

Wer von uns liegt nun falsch?

Du, denn deine Definition des Inversen ist falsch.

Bashar

Wenn man xor statt or als Addition nimmt, erhält man einen Körper. Ohne das: Keine Chance, da es weder bezüglich or noch and Inverse gibt.

inflames2k schrieb:

~~Nö, ich behaupte der erste Teil wird ausgewertet, liefert true und damit ist die Bedingung erfüllt und der zweite Teil wird garnicht erst ausgeführt.~~

Zu früh am morgen, sorry.

Keineswegs, das ist schon richtig so.

Oh, ich hab die Seitenanzahl nicht im Blick gehabt.

Fricky667

Bashar schrieb:

Wenn man xor statt or als Addition nimmt, erhält man einen Körper. Ohne das: Keine Chance, da es weder bezüglich or noch and Inverse gibt.

Bezüglich {0,1, or} ist das inverse Element "a (x) not(a)" == 1
und bezüglich {0,1, and} ist das inverse Element "a (x) not(a)" == 0

Das hat alles nichts mit Xor zu tun, noch muss ein Inverses zwangsläufig eine Änderung des Inputs zur Folge haben. Siehe 0 und 1 im ähnlichen Kontext der Ganzen Zahlen.

Btw, damit etwas ein Körper ist, müssen die Gruppenaxiome erfüllt sein, oder bin ich auf dem Holzweg?

Btw2, Hi Bashar, vor ~10 Jahren warst du für mich einer der Helden dieses Boards, zusammen mit Volkard. Freut mich, dass du noch hier bist.

Bashar

Fricky667 schrieb:

Bashar schrieb:

Wenn man xor statt or als Addition nimmt, erhält man einen Körper. Ohne das: Keine Chance, da es weder bezüglich or noch and Inverse gibt.

Bezüglich {0,1, or} ist das inverse Element "a (x) not(a)" == 1
und bezüglich {0,1, and} ist das inverse Element "a (x) not(a)" == 0

Nope, bezüglich or ist 0 das neutrale Element, es gibt aber kein Element x mit 1 or x = 0, d.h. 1 hat kein inverses.
Bezüglich and analog: 1 ist das neutrale Element, es gibt aber kein Element x mit 0 and x = 1, d.h. 0 hat kein inverses.

Es gibt übrigens bis auf Isomorphie nur eine Gruppe mit 2 Elementen.

Das hat alles nichts mit Xor zu tun

Das war auch nur ergänzend gemeint.

, noch muss ein Inverses zwangsläufig eine Änderung des Inputs zur Folge haben. Siehe 0 und 1 im ähnlichen Kontext der Ganzen Zahlen.

Was meinst du damit?

Btw, damit etwas ein Körper ist, müssen die Gruppenaxiome erfüllt sein, oder bin ich auf dem Holzweg?

Ja, mit xor ist das auch der Fall, wie gesagt. Mit or nicht.

Btw2, Hi Bashar, vor ~10 Jahren warst du für mich einer der Helden dieses Boards, zusammen mit Volkard. Freut mich, dass du noch hier bist.

Danke. Ich schau gelegentlich noch rein.

edit: Das habt ihr ja schon ausführlich durchgekaut auf Seite 2 Guck halt mal bei Wikipedia oder in einem Algebra-Buch deiner Wahl die Axiome an, diese Diskussion hier ist doch völlig überflüssig.

Finnegan

Fricky667 schrieb:

Finnegan schrieb:

Die Elektrotechniker schreiben das gerne mit * und +.

Ich habe von dieser Notation gehört, bin auch E-Techniker, aber bei uns galt sowas damals (vor etwa 15 Jahren) als exotisch.

Auch in der Mathematik kann man sich vorzüglich über Quellcode-Formatierung streiten

Nachdem wir damals einmal für Technische Informatik zur Vereinfachung von digitalen Schaltungen (bevor wir solche Methoden wie Quine–McCluskey kennengelernt haben),
und einmal für die Logik-Vorlesungen bis zum Erbrechen und seitenweise solche Ausdrücke umformen mussten, bin ich zum Fan dieser "exotischen" Notation geworden.
Und auch wenn diese nicht weit verbreitet ist, so ist sie denke ich für die meisten Leute übersichtlicher und lesbarer, was letztendlich genau wie bei Quellcode zu weniger Fehlern führt.
In Logik haben sich bei mir mit " $\lnot\lor\land$ "-Notation damals jedenfalls subjektiv deutlich mehr Fehler eingeschlichen, und ich brauchte spürbar länger für Aufgaben mit vergleichbarer Komplexität.

"Das haben wir schon immer so gemacht" und "das machen alle so" ist jedenfalls für sich kein gutes Argument eine schlechtere Lösung zu wählen.
"Andere können es nicht lesen, weil es keiner so macht" akzeptiere ich da schon eher.

Fricky667 schrieb:

Konsequenterweise sollte man bei dieser Notation das Minuszeichen als Not-Operator verwenden.

Dieser Einwand wurde ja schon diskutiert, daher wollte ich eigentlich nur noch einen praktischen Vorzug des Überstichs einbringen: Dieser kann auch über mehrere Terme laufen und somit die
Aufgabe einer Klammerung übernehmen. Nicht selten hat man solche Kandidaten hier: $\lnot($ <furchtbar langer Ausdruck> $)$ . Oft ist sowas auch mehrfach geschachtelt und geht vielleicht sogar über die ganze Zeile.
Dabei muss ich mir erstmal bewusst werden, dass das, was ich mir gerade ansehe, Teil eines geklammerten Ausdrucks ist, und dieser auch noch invertiert ist. D.h. ich muss mit den Augen eventuell
ziemlich weit nach links und nach rechts scannen um das zu erkennen. Nicht so bei Überstrich-Schreibweise, hier kann ich ohne "Augen-Scan" direkt sehen, zu wie vielen invertierten Klammerungen der
Teilausdruck gehört, auf den ich schaue:

$\overline{ ab + \overline{ cd + \overline{ ef + g + \overline h } } }$

vs.

$\lnot(a \land b \lor \lnot( c \land d \lor \lnot( e \land f \lor g \lor \lnot h)))$

Vielleicht bin ich wirklich ein "Exot", aber ich für meinen Teil checke bei der ersten Variante wesentlich schneller, was "abgeht"

Finnegan