boolesche Funktionen vergleichen

[Stoni1001]

Hallo,

Ich habe eine Problemstellung, die ich im Moment nicht lösen kann, ich hoffe es kann mir hier wer weiterhelfen..

Generell hab ich 2 boolesche Ausdrücke gegeben. beide Ausdrücke können bis zu 2 variablen beinhalten, deren werte ich nicht kenne.
für die Variablen dürfen nur positive ganzzahlige werte eingesetzt werden.

Beispiel 1:

Ausdruck 1: a=0
Ausdruck 2: a+b>1,5

Ich muss jetzt herausfinden ob es für die Variablen werte gibt, damit beide Ausdrücke der Wahrheit entsprechen.
Die Werte sind für mich jedoch nicht relevant. Ich muss einfach herausfinden, ob sich die 2 Ausdrücke nicht logisch gegenseitig ausschließen.

Beispiel 1:

Ergebnis: true
Werte(a=0,b=2,b=3,b=4 ...)


Beispiel 2:

Ausdruck 1: (a+b > 1,5)
Ausdruck 2: (a=0 and b=0)

Ergebnis: false
Ausruck 2 schränkt bereits auf die Werte (a=0,b=0) ein, somit kann der 1. Ausdruck nie true zurück liefern.

Ich hoff meine Problemstellung ist soweit gut verständlich. Bin für jede Anregung offen.
danke

[Panthrax]

Wenn Du die Ausdrücke nicht verstehen willst oder kannst, bleibt nur durchprobieren, d.h. wenigstens eine Lösung zu finden. Wobei die die Grenzen durch die Datentypen gesetzt sind, aber eigentlich unendlich sind. Grobkonzept, die gefundene Lösung wird verworfen:

Delphi-Quellcode:

type
  TAusdruck = function (const X, Y: Cardinal): Boolean;

function LösungMöglich(const A1, A2: TAusdruck): Boolean;
var
  X1, X2, Y1, X2: Cardinal;
begin
  for X1 := Low(Cardinal) to High(Cardinal) do
    for Y1 := Low(Cardinal) to High(Cardinal) do
      for X2 := Low(Cardinal) to High(Cardinal) do
        for Y2 := Low(Cardinal) to High(Cardinal) do
          if A1(X1, Y1) and A2(X2, Y2) then
            Exit(True);
  Result := False;
end;

[Stoni1001]

kk danke.. werd das gleich mal so umsetzen

[Panthrax]

Ich hoffe, Dir steht ein leistungsstarker Rechner zur Verfügung.

[JasonDX]

Zitat von Panthrax:

Delphi-Quellcode:

type
  TAusdruck = function (const X, Y: Cardinal): Boolean;

function LösungMöglich(const A1, A2: TAusdruck): Boolean;
var
  X1, X2, Y1, X2: Cardinal;
begin
  for X1 := Low(Cardinal) to High(Cardinal) do
    for Y1 := Low(Cardinal) to High(Cardinal) do
      for X2 := Low(Cardinal) to High(Cardinal) do
        for Y2 := Low(Cardinal) to High(Cardinal) do
          if A1(X1, Y1) and A2(X2, Y2) then
            Exit(True);
  Result := False;
end;

Das ist knapp übers Ziel hinausgeschossen. So wie ich das verstanden habe, sucht er ein Wertepaar (x, y) sodass f1(x, y) und f2(x, y) hält. Deine Lösung sucht zwei verschiedene Wertepaare, welche jeweils eine Funktion erfüllen müssen, d.h. du untersuchst nur insgesamt, ob die Funktionen getrennt voneinander erfüllbar sind. Folglich lässt sich der Aufwand für die Berechnung etwas verringern:

Delphi-Quellcode:

type
  TAusdruck = function (const x, y: Cardinal): Boolean;

function LösungMöglich(const f1, f2: TAusdruck): Boolean;
var
  x, y: Cardinal;
begin
  for x := Low(Cardinal) to High(Cardinal) do
    for y := Low(Cardinal) to High(Cardinal) do
      if f1(x, y) and f2(x, y) then
        Exit(True);
  Result := False;
end;

greetz
jason

[Panthrax]

Zitat von JasonDX:

Das ist knapp übers Ziel hinausgeschossen.

Allerdings. So im Eifer des Gefechts...

[sx2008]

Wenn man sich klarmacht, dass eine Gleichung mit zwei Unbekannten (in der 1. Potenz) einer Geraden entspricht und eine Ungleichung einer Fläche neben einer Geraden entspricht, dann könnte man versuchen für diese Geraden und/oder Flächen einen Schnittpunkt, -Linie oder -Fläche zu finden.
Für ein Programm ist das aber nicht so einfach...
Man kann sich auf jeden Fall Anregungen von der Linearen Optimierung holen.

[Panthrax]

Zitat von sx2008:

Man kann sich auf jeden Fall Anregungen von der Linearen Optimierung holen.

Ohne Kenntnis der Ausdrücke, kann man das nicht:

Delphi-Quellcode:

function Ausdruck1(const X, Y: Integer): Boolean;
begin
  Result := (X and $FF00) = Y;
end;

function Ausdruck2(const X, Y: Integer): Boolean;
begin
  Result := (X and $00FF) = Y;
end;

Boolsche Ausdrücke sind diskret.
Boolsche Ausdrücke mit zwei Variablen sind potentiell auch zweiter Ordnung.

[Reinhard Kern]

Zitat von sx2008:

Wenn man sich klarmacht, dass eine Gleichung mit zwei Unbekannten (in der 1. Potenz) einer Geraden entspricht und eine Ungleichung einer Fläche neben einer Geraden entspricht, dann könnte man versuchen für diese Geraden und/oder Flächen einen Schnittpunkt, -Linie oder -Fläche zu finden.
Für ein Programm ist das aber nicht so einfach...
...

Hallo,

solang alles linear ist (nicht etwa a³+b²=0), was der Fragesteller nicht klar definiert hat, könnte man das weiterverfolgen:

Beide Gleichungen auf Geradengleichung umformen (Ungleichungen als Gleichungen) und Fallunterscheidungen machen, sind nicht so viele:

Geraden schneiden sich -> gibt es mindestens eine gemeinsame Lösung (muss die ganzzahlig sein??)

wenn nicht, müssen die Geraden parallel sein oder eine Gleichung liefert nur einen Punkt als Lösung.

Gruss Reinhard

[HERMES]

Wenn man es nicht selber implementieren muss würde ich einen SMT solver verwenden

guckst du hier: http://en.wikipedia.org/wiki/Satisfi...odulo_Theories