Eigenschaften von XBOOLE

Die Leistungsfähigkeit und Vielseitigkeit für Anwendungen ergibt sich aus den Eigenschaften von XBOOLE.

Ternärvektorliste (TVL)

Als grundlegende Datenstruktur werden Ternärvektorlisten verwendet. Eine Ternärvektorliste enthält die Elemente '0', '1' und '-'. Das Strichelement '-' repräsentiert die beiden Elemente '0' und '1'. Ein Ternärvektor (eine Zeile einer TVL) mit s Strichelementen beschreibt 2s Binärvektoren. Ein Ternärvektorliste ist somit eine kompakte Beschreibung einer Menge von Binärvektoren. Die Booleschen Variablen sind den Spalten der Ternärvektorliste zugeordnet.

Orthogonalität

Zwei verschiedene Binärvektoren der gleichen Variablen sind orthogonal zueinander. Zwei Ternärvektoren, die keinen Binärvektor gemeinsam enthalten, werden orthogonale Ternärvektoren genannt. In einer orthogonalen TVL sind alle Paare von Ternärvektoren orthogonal zueinander. XBOOLE verwendet bevorzugt orthogonale Ternärvektorlisten. Vorteile ergeben sich bei der Interpretation einer orthogonalen TVL als Boolesche Funktion.

Verarbeitung von TVL

Ternärvektorlisten dienen nicht nur als Datenstruktur zur Speicherung, sondern können auch direkt verarbeitet werden. Durch eine optimal gewählte Kodierung der drei Ternärelemente mit zwei Booleschen Werten genügen drei Boolesch Operationen zum Test auf Orthogonalität. Ein mehrstufiges Algorithmensystem stellt alle Mengenoperationen zur Verfügung.

Parallele Verarbeitung

Alle Elemente von Ternärvektoren werden parallel verarbeitet, falls die Anzahl der Elemente nicht größer als die Anzahl der Bits eines Maschinenworts ist.

Unbeschränkte Anzahl von Variablen

Ein Ternärvektor kann von mehr Variablen abhängen als Bits in einem Maschinenwort vorhanden sind. Zur Speicherung des Binärvektors werden entsprechend viele Paare von Maschinenwörtern verwendet.

Beschränkt sequentielle Verarbeitung

Es werden nur so viele Paare von Binärvektoren eines Ternärvektors ausgewertet, die zur Ermittlung der gesuchten Eigenschaft erforderlich sind. In vielen Fällen genügt durch die parallele Verarbeitung aller Bits der Maschinenwörter ein Paar von Binärvektoren.

Raumkonzept

XBOOLE verarbeitete die TVL in beliebig vielen Booleschen Räumen, deren Dimensionen (maximale Anzahl von Variablen) durch den Anwender festgelegt werden. In jeden Booleschen Raum erfolgt eine feste Zuordnung der Variablen zu den Spalten der zugehörigen TVLs. Zeitaufwendige Zuordnungen von Variablen entfallen für TVL aus dem gleichen Raum. Die Aufteilung der Variablen auf verschiedene Räume ermöglicht das Lösen von Problemen mit extrem vielen Variablen wobei die Anzahl der Variablen in den einzelnen TVLs beschränkt werden kann.

Fachsystem

Der Speicherbedarf einer TVL ist Apriori unbekannt. XBOOLE verwendet zur Speicherung von TVLs und anderer Objekte Speicherbereiche mit einer festen Größe; diese Speicherbereiche werden Fächer genannt. Jedes XBOOLE-Objekt wird in einem oder mehreren Fächern gespeichert. Die Fächer von gelöschten XBOOLE-Objekten können für nachfolgend gebildete XBOOLE-Objekte wiederverwendet werden ohne das eine Fragmentierung des Speichers entsteht.

Formprädikat einer TVL

Eine TVL kann nicht nur eine Menge von Binärvektoren, sondern auch direkt eine Boolesche Funktion in den vier Grundformen (disjunktive Form, konjunktive Form, Antivalenzform und Äquivalenzform) repräsentieren. Dazu besitzt jede TVL ein Formprädikat. Eine orthogonale TVL einer Funktion in disjunktiver Form beschreibt die gleiche Funktion in Antivalenzform; ein TVL dieser bevorzugen Form wird das Formprädikat ODA zugeordnet. Analog gibt es das Formprädikat OKE, mit dem eine TVL gekennzeichnet wird, die eine Boolesche Funktion in konjunktiver Form oder Äquivalenzform beschreibt.