AbstractsPhilosophy & Theology

The problem of factoring and decomposing Boolean functions is Σ-complete 2 for general functions. Efficient and exact algorithms can be created for an existing class of functions known as read-once, disjoint-support decomposable and read-polarity-once functions. A factored form is called read-once (RO) if each variable appears only once. A Boolean function is RO if it can be represented by an RO form. For example, the function represented by = 1 2+ 1 3 4+ 1 3 5 is a RO function, since it can be factored into = 1( 2+ 3( 4+ 5)). A Boolean function f(X) can be decomposed using simpler subfunctions g and h, such that ( )=ℎ( ( 1), 2) being X1, X2 ≠ ∅, and X1 ∪ X2 = X. A disjoint-support decomposition (DSD) is a special case of functional decomposition, where the input sets X1 and X2 do not share any element, i.e., X1 ∩ X2 = ∅. Roughly speaking, DSD functions can be represented by a read-once expression where the exclusive-or operator (⊕) can also be used as base operation. For example, = 1( 2⊕( 4+ 5)). A read-polarity-once (RPO) form is a factored form where each polarity (positive or negative) of a variable appears at most once. A Boolean function is RPO if it can be represented by an RPO factored form. For example the function = 1̅̅̅ 2 4+ 1 3+ 2 3 is RPO, since it can factored into =( 1̅̅̅ 4+ 3),( 1+ 2). This dissertation presents four new algorithms for synthesis of Boolean functions. The first contribution is a synthesis method for read-once functions based on a divide-and-conquer strategy. The second and third contributions are two algorithms for synthesis of DSD functions: a top-down approach that checks if there is an OR, AND or XOR decomposition based on sum-of-products, product-of-sums and exclusive-sum-of-products inputs, respectively; and a method that runs in a bottom-up fashion and is based on Boolean difference and cofactor analysis. The last contribution is a new method to synthesize RPO functions which is based on the analysis of positive and negative transition sets. Results show the efficacy and efficiency of the four proposed methods. O problema de fatorar e decompor funções Booleanas é Σ-completo 2 para funções gerais. Algoritmos eficientes e exatos podem ser criados para classes de funções existentes como funções read-once, disjoint-support decomposable e read-polarity-once. Uma forma fatorada é chamada de read-once (RO) se cada variável aparece uma única vez. Uma função Booleana é RO se existe uma forma fatorada RO que a representa. Por exemplo, a função representada por = 1 2+ 1 3 4+ 1 3 5 é uma função RO, pois pode ser fatorada em = 1( 2+ 3( 4+ 5)). Uma função Booleana f(X) pode ser decomposta usando funções mais simples g e h de forma que ( )=ℎ( ( 1), 2) sendo X1, X2 ≠ ∅, e X1 ∪ X2 = X. Uma decomposição disjunta de suporte (disjoint-support decomposition – DSD) é um caso especial de decomposição funcional, onde o conjunto de entradas X1 e X2 não compartilham elementos, i.e., X1 ∩ X2 = ∅. Por exemplo, a função = 1 2̅̅̅ 3+ 1 2 3̅̅̅ 4̅̅̅+ 1 2̅̅̅ 4 é DSD, pois existe uma decomposição tal… Advisors/Committee Members: Reis, Andre Inacio.