In this episode, we bring together our knowledge of logic operations, truth tables, and boolean expressions to prove some basic properties of Boolean algebra.

We are familiar with algebraic laws such as multiply zero by anything, and we get zero. In this episode, we see how a Boolean expression containing a constant, a duplicated signal, or a signal being combined with its inverse will simplify…always.

Because many students have trouble when trying to simplify Boolean expressions, we’re going to dedicate another episode to examples of simplification. We’re also going to show how sometimes, there’s more than one way to crack an egg.

<p>The lattice of varieties of distributive pseudo-complemented lattices is completely described, viz. a chain of type W + 1. Moreover, each variety is determined by a single equation in addition to those equations which define distributive pseudo-complemented lattices. Characterizations of distributive pseudo-complemented lattices satisfying a certain equation are given which turn out to be generalizations of L. Nachbin's result for Boolean algebras and the results for Stone algebras obtained by G. Gratzer-E. '11. Schmidt and J. C. Varlet. </p> / Thesis / Doctor of Philosophy (PhD)

No description available.

No description available.

A new algorithm is presented for a guaranteed absolute minimal solution to the problem of Boolean Logic Minimization in its most generalized form of multi-output function with arbitrary cost criterion. The proposed algorithm is shown to be tighter than the Quine-McCluskey method in its ability to eliminate redundant prime implicants, making it possible to simplify the cyclic tables. In its final form, the proposed algorithm is truly concurrent in generation of prime implicants and construction of minimal forms. A convenient and efficient technique is used for identifying existing prime implicants. Branch-and-bound method is employed to restrict the search tree to a cost cut-off value depending on the definition of cost function specified. A most generalized statement of the algorithm is formulated for manual as well as computer implementation and its application is illustrated with an example. A program written in Pascal, for classical diode-gate cost function as well as PLA-area cost function, is developed and tested for an efficient computer implementation. Finally, various advantages of the proposed approach are pointed out by comparing it with the classical approach of Quine-McCluskey method. / Master of Science

Este trabalho apresenta a composição funcional (CF) como um novo paradigma para realização da síntese lógica de blocos combinacionais. CF usa uma abordagem ascendente para sintetizar funções Booleanas, sendo capaz de avaliar os custos das funções intermediárias e explorando dessa forma um grande número de combinações diferentes de funções candidatas. Há vantagens interessantes quando comparado à abordagem descendente da decomposição funcional. CF apresenta grande flexibilidade para criar algoritmos com resultados ótimos ou subótimos para diferentes aplicações. A estratégia proposta apresenta bons resultados para síntese de funções Booleanas visando diferentes tecnologias. CF é baseado nos seguintes princípios: (1) representação de funções lógicas como um par ligado com representações funcional e estrutural; (2) o algoritmo começa de um conjunto de funções iniciais; (3) funções mais simples são associadas para criar funções mais complexas; (4) existe uma ordem parcial que permite o uso da programação dinâmica; (5) um conjunto de funções permitidas pode ser mantido para reduzir o tempo de execução/consumo de memória. Este trabalho apresenta algoritmos de composição funcional para fatoração Booleana, incluindo fatoração ótima, fatoração considerando o operador OU-exclusivo, computação de cadeias mínimas de decisão e síntese de funções considerando somente portas lógicas majoritárias e inversores. / This work presents functional composition (FC) as a new paradigm for combinational logic synthesis. FC is a bottom-up approach to synthesize Boolean functions, being able to evaluate the cost of intermediate sub-functions, exploring a larger number of different candidate combinations. These are interesting advantages when compared to the top-down behavior of functional decomposition. FC presents great flexibility to implement algorithms with optimal or suboptimal results for different applications. The proposed strategy presents good results for the synthesis of Boolean functions targeting different technologies. FC is based on the following principles: (1) the representation of logic functions is done by a bonded pair of functional and structural representations; (2) the algorithm starts from a set of initial functions; (3) simpler functions are associated to create more complex ones; (4) there is a partial order, enabling dynamic programming; (5) a set of allowed functions can be used in order to reduce execution time/memory consumption. This work presents functional composition algorithms for Boolean factoring, including optimal factoring, Boolean factoring considering the exclusive-OR operator, minimum decision chain computation and synthesis of functions considering only majority and inverter logic gates.

Στη διατριβή αυτή θα ασχοληθούμε με την Μπουλιανή ανάλυση σαν μια κατ'ευθείαν γενίκευση της μη συμβατικής ανάλυσης του Robinson, δηλ. της θεωρίας των Υπεργινομένων και τις εφαρμογές της στη θεωρία των Ασαφών συνόλων. / --

Boolean satisfiability (SAT) is the problem of determining whether there exists an assignment of the Boolean variables to the truth values such that a given Boolean formula evaluates to true. SAT was the first example of an NP-complete problem. Only two decades ago SAT was mainly considered as of a theoretical interest. Nowadays, the picture is very different. SAT solving becomes mature and is a successful approach for tackling a large number of applications, ranging from artificial intelligence to industrial hardware design and verification. SAT solving consists of encodings and solvers. In order to benefit from the tremendous advances in the development of solvers, one must first encode the original problems into SAT instances. These encodings should not only be easily generated, but should also be efficiently processed by SAT solvers. Furthermore, an increasing number of practical applications in computer science can be expressed as constraint satisfaction problems (CSPs). However, encoding a CSP to SAT is currently regarded as more of an art than a science, and choosing an appropriate encoding is considered as important as choosing an algorithm. Moreover, it is much easier and more efficient to benefit from highly optimized state-of-the-art SAT solvers than to develop specialized tools from scratch. Hence, finding appropriate SAT encodings of CSPs is one of the most fascinating challenges for solving problems by SAT. This thesis studies SAT encodings of CSPs and aims at: 1) conducting a comprehensively profound study of SAT encodings of CSPs by separately investigating encodings of CSP domains and constraints; 2) proposing new SAT encodings of CSP domains; 3) proposing new SAT encoding of the at-most-one constraint, which is essential for encoding CSP variables; 4) introducing the redundant encoding and the hybrid encoding that aim to benefit from both two efficient and common SAT encodings (i.e., the sparse and order encodings) by using the channeling constraint (a term used in Constraint Programming) for SAT; and 5) revealing interesting guidelines on how to choose an appropriate SAT encoding in the way that one can exploit the availability of many efficient SAT solvers to solve CSPs efficiently and effectively. Experiments show that the proposed encodings and guidelines improve the state-of-the-art SAT encodings of CSPs.