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.

This thesis considers algorithmic and structural aspects of high-dimensional convex sets with respect to the standard Gaussian measure. Among our contributions, (i) we introduce a notion of "influence" for convex sets that yields the first quantitative strengthening of Royen's celebrated Gaussian correlation inequality; (ii) we investigate the approximability of general convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution; and (iii) we give the first lower bounds for testing convexity and estimating the distance to convexity of an unknown set in the black-box query model. Our results and techniques are inspired by a number of fundamental ingredients and results---such as the influence of variables, noise sensitivity, and various extremal constructions---from the analysis of Boolean functions in complexity theory.

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, δηλ. της θεωρίας των Υπεργινομένων και τις εφαρμογές της στη θεωρία των Ασαφών συνόλων. / --