Displaying similar documents to “On some Properties of Boolean Functions and Their Binary Decision Diagrams Върху някои свойства на булевите функции и техните диаграми за двоично решаване”

On maximal QROBDD’s of boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

On maximal QROBDD's of Boolean functions

Jean-Francis Michon, Jean-Baptiste Yunès, Pierre Valarcher (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

Modus ponens on Boolean algebras revisited.

Enric Trillas, Susana Cubillo (1996)

Mathware and Soft Computing

Similarity:

In a Boolean Algebra B, an inequality f(x,x --> y)) ≤ y satisfying the condition f(1,1)=1, is considered for defining operations a --> b among the elements of B. These operations are called Conditionals'' for f. In this paper, we obtain all the boolean Conditionals and Internal Conditionals, and some of their properties as, for example, monotonicity are briefly discussed.

WWW-based Boolean function minimization

Sebastian Tomaszewski, Ilgaz Celik, George Antoniou (2003)

International Journal of Applied Mathematics and Computer Science

Similarity:

In this paper a Boolean minimization algorithm is considered and implemented as an applet in Java. The application is based on the Quine-McCluskey simplification technique with some modifications. The given application can be accessed on line since it is posted on the World Wide Web (WWW), with up to four variables, at the URL http://www.csam.montclair.edu/~antoniou/bs. After extensive testing, the performance of the algorithm has been found to be excellent. The proposed application...

On Boolean modus ponens.

Sergiu Rudeanu (1998)

Mathware and Soft Computing

Similarity:

An abstract form of modus ponens in a Boolean algebra was suggested in [1]. In this paper we use the general theory of Boolean equations (see e.g. [2]) to obtain a further generalization. For a similar research on Boolean deduction theorems see [3].

Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs

Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear...