Binäres Gleichungssystem lösen

Neue Frage »

Ari Auf diesen Beitrag antworten »
Binäres Gleichungssystem lösen
Hey ihr,

hab folgendes Problem: möchte ein Gleichungssystem mit 12 binäre Gleichungen lösen, mich interessiert dabei nur die eindeutige Lösbarkeit. Zu Fuß ist mir das Risiko zu groß, einen Fehler zu machen. Mathcad, Derive und Origin hab ich schon mehr oder weniger durchsucht, aber nichts gefunden. Habt ihr einen Rat?

Das Gleichungssystem ist mit reellen Zahlen nicht eindeutig lösbar - dann hab ich argumentiert, dass die Wahrscheinlichkeit, dass Gleichungen mehrfach auftauchen, sich also wiederholen, bei Gleichungen mit binären Zahlen größer ist als bei reellen (gibt eben nur die Zahlen 0 und 1 hinterm Gleichheitszeichen). Etwas präziser hätte ichs aber schon gerne - denn der erste Versuch zu Fuß führte leider zu einer Diagonalenform...
WebFritzi Auf diesen Beitrag antworten »

Was meinst du mit einer "binären Gleichung"?
Ari Auf diesen Beitrag antworten »

Hier mal ein Auszug:



Insgesamt sinds 12 Gleichungen; pro Gleichung tauchen jeweils zwei der acht Unbekannten auf.
WebFritzi Auf diesen Beitrag antworten »

Verstehe ich nicht. Ich sehe dort keine Unbekannten...
Ari Auf diesen Beitrag antworten »

soltle Matrizenform darstellen, wobei "+" da tatsächlich nciht reingehört



so etwas. Im reellen Zahlensystem ergibt sich keine Lösung für mein Gleichungssystem, ich würds aber gern in den geforderten System lösen. Theoretisch würde doch ein nicht lösbares reelles Gleichungssystem ein nicht lösbares binäres Gleichungssystem implizieren. Umgekehrt könnten im reellen System Lösungen existieren, die sich im binären nicht ergeben.
Etwas genauer wäre aber toll smile
AD Auf diesen Beitrag antworten »

Zitat:
Original von Ari
Theoretisch würde doch ein nicht lösbares reelles Gleichungssystem ein nicht lösbares binäres Gleichungssystem implizieren.

Nein, das ist falsch:

Betrachten wir z.B. mal ein nxn-LGLS, d.h. genauso viel Gleichungen wie Variablen. Dann folgt aus "reelle Determinante gleich Null" auch "binäre Determinante gleich Null".

"Determinante gleich Null" ist da aber nicht dasselbe wie unlösbar - sondern nur "nicht eindeutig lösbar". Ein feiner Unterschied!

Bei allgemeinen, nicht quadratischen Gleichungssystemen bieten sich Rangbetrachtungen an, sowohl im Real- als auch Binär-GLS.
 
 
AD Auf diesen Beitrag antworten »

Ok, ein Beispiel:



in keine Lösung; in hingegen die Lösung .
Ari Auf diesen Beitrag antworten »

Danke für die Antwort Arthur!

Kann man also die eindeutige Lösbarkeit eines GLS in nicht mit der eindeutigen Lösbarkeit eines GLS in (bedeutet, dass im Binärsystem gerechnet wird, oder?) vergleichen?

Ich hatte mir das so vorgestellt: Mein GLS hat in keine eindeutige Lösung, weil sich nach im Laufe des Eliminationsverfahrens Gleichungen wiederholen und dann mehr Unbekannte als Gleichungen vorliegen.
Da im binären System nur die Werte 0 und 1 zur Verfügung stehen, könnten sich da sogar mehr Gleichungen wiederholen als in - dein Beispiel zeigt mir nur leider das Gegenteil, womit meine Vorstellung falsch ist traurig
WebFritzi Auf diesen Beitrag antworten »

Also, jetzt bin ich etwas durcheinander. Ari, warum redest du immer vom "binären System"? Eine reelle Zahl bleibt reell. Ob man sie nun dezimal oder binär darstellt, ist dabei egal. Ich denke, es geht hier vielmehr darum, mit welchen Körpern man es zu tun hat. Wenn nicht, dann klärt mich doch bitte auf.
Ari Auf diesen Beitrag antworten »

Ok, der Begriff System ist da wohl auch falsch.
Die eindeutige Lösbarkeit ändert sich ja anscheindend abhängig vom verwendeten Körper (endlich; unendlich). Gibt es da keinen direkten Zusammenhang, wenn das eine nicht eindeutig lösbar ist, dass das andere auch nicht eindeutig lösbar ist?
AD Auf diesen Beitrag antworten »

@Ari

Ich hab das so verstanden, dass es um ein LGLS geht, wo die Einträge von sämtlich Nullen und Einsen sind. Einmal fasst du dieses System in auf, und ein anderes mal in . Dein Hauptschwerpunkt wird wohl bei letzterem liegen, aber du möchtest deine Kenntnisse von ersterem übertragen. Liege ich da richtig?

-------------------------------------------------------------------------------

Machen wir doch mal die oben von mir erwähnten Rangbetrachtungen:

Ein LGLS ist genau dann lösbar, falls gilt - hierbei kennzeichnet die Matrix , wo rechts der Vektor als zusätzliche Spalte angehängt wird.


Was kann man nun zu den Rängen bei Interpretation in vs. sagen?

Da der Rang gleich der Dimension der größten quadratischen regulären Untermatrix ist, so kann man aus

für beliebige quadratischen 0-1-Matrizen

sofort folgern:



und auch

.

Viel mehr dürfte allgemein aber nicht drin sein an Folgerungen. Insbesondere folgt also aus



i.A. auch nicht

,

siehe mein Beispiel eines 3x2-Systems.


EDIT: Copy+Paste-Fehler korrigiert, hat zu meinem Glück keiner vorher gemerkt...
Ari Auf diesen Beitrag antworten »

Hallo Arthur,

vielen Dank für die Antwort! Ist zwar schade, dass es nicht so funktioniert wie ich erst dachte, aber zu Matrizen habe ich jetzt einiges gelernt smile

Danke!!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »