UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” FACULDADE DE ENGENHARIA CÂMPUS DE ILHA SOLTEIRA JOSÉ VIRGÍLIO DE OLIVEIRA JÚNIOR OTIMIZAÇÃO DE FUNÇÕES LÓGICAS MAJORITÁRIAS UTILIZANDO PROGRAMAÇÃO LINEAR INTEIRA BINÁRIA E QUANTIFICAÇÃO DE PRIMITIVAS Ilha Solteira 2021 PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA JOSÉ VIRGÍLIO DE OLIVEIRA JÚNIOR OTIMIZAÇÃO DE FUNÇÕES LÓGICAS MAJORITÁRIAS UTILIZANDO PROGRAMAÇÃO LINEAR INTEIRA BINÁRIA E QUANTIFICAÇÃO DE PRIMITIVAS Dissertação apresentada à Faculdade de Engenharia de Ilha Solteira – UNESP como parte dos requisitos para obtenção do título de Mestre em Engenharia Elétrica. Área de Conhecimento: Automação. Prof. Dr. Alexandre César Rodrigues da Silva. Orientador Ilha Solteira 2021 AGRADECIMENTOS Aos meus pais José e Nilsa pelo apoio e compreensão sempre presentes. Ao Professor Dr. Alexandre César Rodrigues da Silva pelo apoio, credibilidade e confiança concedidos a longa data. Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) pelo atencioso suporte financeiro. Aos colegas Evandro e Willian do Laboratório de Processamento de Sinais e Sistemas Digitais pela companhia e discussões técnicas. A todos os professores do Departamento de Engenharia Elétrica e servidores da FEIS que propiciam o ambiente favorável ao desenvolvimento e progresso dos alunos. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001. RESUMO A tecnologia semicondutora tem sido a base dos circuitos lógicos digitais da computação moderna. O uso de portas lógicas dos padrões AND e NAND tem direcionado o projeto e implementação destes circuitos. Recentes pesquisas em nanotecnologia têm explorado horizontes para o aumento da velocidade e eficiência de circuitos digitais, diminuindo sua escala de integração. Rompendo um paradigma, as portas lógicas majoritárias têm sido utilizadas no projeto destes circuitos, substituindo suas antecessoras clássicas. Um dos grandes desafios destas tecnologias é a simplificação e a otimização destes circuitos lógicos. Neste trabalho, formula-se a otimização de funções booleanas empregando funções majoritárias primitivas através de um problema de programação linear inteira binária, por meio do desenvolvimento de um software. Resultados obtidos mostram que o método apresentado é compacto e promissor. Adicionalmente, apresenta-se a dedução para a função polinomial que determina a quantidade de funções majoritárias primitivas como função da quantidade de variáveis e sua representatividade dentre todas as funções. Palavras-chave: Otimização de circuitos lógicos. Lógica majoritária. Funções primitivas. Programação linear inteira. Linguagem Python. CPLEX. ABSTRACT Semiconductor technology has been the basis of the digital logic circuits of modern computing. The use of AND and NAND standards logic gates has guided the design and implementation of these circuits. Recent research in nanotechnology has explored horizons for increasing the speed and efficiency of digital circuits, decreasing their scale of integration. Breaking a paradigm, the majority logic gates have been used in the design of these circuits, replacing their classic predecessors. One of the great challenges of these technologies is the simplification and optimization of these logic circuits. In this work, the optimization of Boolean functions is formulated using primitive majority functions through a problem of binary integer linear programming, through the development of an software. Results obtained show that the developed method is compact and promising. In addition, presents the deduction of the polynomial function which determines the number of primitive majority functions as a function of the number of variables and its representativeness among all functions. Keywords: Optimization of logic circuits. Majority logic. Primitive functions. Integer linear programming. Python language. CPLEX. LISTA DE FIGURAS Figura 1 – Mapas de Karnaugh das funções 𝐹𝐹1 e 𝐹𝐹2. 26 Figura 2 – Representação esquemática das três portas lógicas fundamentais. 27 Figura 3 – Circuito lógico combinacional para as funções 𝐹𝐹1 e 𝐹𝐹2. 28 Figura 4 – Circuito lógico combinacional da porta XOR. 29 Figura 5 – Mapa de Karnaugh da função majoritária de 3 entradas. 31 Figura 6 – Circuito lógico combinacional para a função majoritária de 3 entradas. 32 Figura 7 – Variações da porta lógica majoritária de 3 entradas. 34 Figura 8 – Funções booleanas com portas lógicas majoritárias. 34 Figura 9 – Circuito lógico combinacional para a função majoritária de 5 entradas. 36 Figura 10 – Gráfico da função polinomial que representa 𝑝𝑝(𝑛𝑛). 46 Figura 11 – Gráfico da função 𝑝𝑝′(𝑛𝑛) do crescimento de 𝑝𝑝(𝑛𝑛). 47 Figura 12 – Gráfico da função 𝑝𝑝(𝑛𝑛) abrangendo 126 casos. 49 Figura 13 – Quantidade de primitivas para 𝑛𝑛 variando de 3 a 32. 49 Figura 14 – Circuito lógico combinacional da função 𝐹𝐹. 53 Figura 15 – Diagrama de conjuntos representando as operações AND e OR. 57 Figura 16 – Diagrama de mintermos do produto das funções 𝐹𝐹 e 𝐺𝐺. 58 Figura 17 – Diagrama de mintermos da soma das funções 𝐹𝐹 e 𝐺𝐺. 58 Figura 18 – Circuito lógico combinacional majoritário de 5 níveis. 60 Figura 19 – Distribuição das restrições numa função arbitrária. 62 Figura 20 – Conjunto de mintermos das 3 primitivas que compõem a função 𝐹𝐹. 62 Figura 21 – Conjunto de mintermos dos produtos, duas a duas, das 3 primitivas que compõem a função 𝐹𝐹. 63 Figura 22 – Mapeamento de mintermos da função 𝐹𝐹. 63 Figura 23 – Fluxograma para o programa MPL01. 72 Figura 24 – Circuito majoritário otimizado para o somador completo. 77 Figura 25 – Circuito majoritário otimizado com múltiplas saídas para o somador completo. 77 Figura 26 – Tempos de execução para a otimização de todas as funções de 3 variáveis. 78 Figura 27 – Comparativo gráfico entre os tempos de execução do MPL01. 79 LISTA DE TABELAS Tabela 1 – As três operações básicas da álgebra booleana. 18 Tabela 2 – Teoremas da álgebra booleana. 20 Tabela 3 – Tabela-verdade referente à demonstração do Teorema B.11. 21 Tabela 4 – Tabelas-verdades das funções 𝐹𝐹1 e 𝐹𝐹2. 21 Tabela 5 – Mintermos e maxtermos para 3 variáveis. 23 Tabela 6 – Tabela-verdade da função majoritária de 3 entradas. 31 Tabela 7 – Principais axiomas e teoremas da lógica majoritária. 33 Tabela 8 – Demonstração do Teorema M.16. 33 Tabela 9 – Tabela-verdade da função majoritária de 5 entradas. 35 Tabela 10 – Funções majoritárias primitivas para 𝑛𝑛 = 3 variáveis. 38 Tabela 11 – Funções majoritárias primitivas para 𝑛𝑛 = 4 variáveis. 39 Tabela 12 – Quantidade de primitivas de cada grupo para uma função majoritária com 3 entradas e 𝑛𝑛 variáveis. 46 Tabela 13 – Quantidade de funções primitivas para até 126 variáveis. 48 Tabela 14 – Quantidade de primitivas, quantidade de funções e relação de proporção para 𝑛𝑛 variando de 3 a 32 variáveis. 51 Tabela 15 – Tabela-verdade da função 𝐹𝐹. 54 Tabela 16 – Exemplificação dos níveis de funções majoritárias. 59 Tabela 17 – Coeficientes 𝑎𝑎𝑖𝑖𝑖𝑖 para o PLI de funções com 3 variáveis. 64 Tabela 18 – Coeficientes de custo das primitivas de 3 variáveis. 67 Tabela 19 – Tabela-verdade do somador completo. 75 Tabela 20 – Tempos de execução do programa MPL01. 79 LISTA DE SIGLAS E ABREVIATURAS API Application Programming Interface CI Circuito Integrado CMOS Complementary Metal-Oxide Semicondutor DOcplex IBM Decision Optimization CPLEX Modeling for Python FPGA Field Programmable Gate Array MIG Majority-Inverter Graph MLP01 Majority Linear Programming 0 or 1 MOSFET Metal-Oxide Semiconductor Field-Effect Transistor MPC Majority Primitives Combination PDS Processador Digital de Sinais PLD Programmable Logic Device PLI Problema de Programação Linear Inteira POS Product of Sums QCA Quantum-dot Cellular Automata RAM Random Access Memory SET Single Electron Tunneling SOP Sum of Products TBJ Transistor Bipolar de Junção TPL Tunneling Phase Logic TTL Transistor-Transistor Logic SUMÁRIO 1 INTRODUÇÃO 13 1.1 A LÓGICA MAJORITÁRIA E OS PROCESSOS DE OTIMIZAÇÃO 14 2 ÁLGEBRA BOOLEANA E CIRCUITOS COMBINACIONAIS 18 2.1 FUNÇÃO BOOLEANA E TABELA VERDADE 19 2.2 MINTERMOS, MAXTERMOS E FORMA VETORIAL 22 2.3 SIMPLIFICAÇÃO DE FUNÇÕES BOOLEANAS 25 2.4 CIRCUITOS LÓGICOS COMBINACIONAIS 27 3 LÓGICA MAJORITÁRIA 30 3.1 A FUNÇÃO MAJORITÁRIA 30 3.2 LÓGICA MAJORITÁRIA E PORTAS LÓGICAS MAJORITÁRIAS 32 3.3 FUNÇÕES MAJORITÁRIAS PRIMITIVAS 36 4 ANÁLISE QUANTITATIVA DAS FUNÇÕES MAJORITÁRIAS PRIMITIVAS 42 4.1 QUANTIDADE TOTAL DE FUNÇÕES PRIMITIVAS POR GRUPO 42 4.2 QUANTIDADE TOTAL DE FUNÇÕES PRIMITIVAS 45 4.3 REPRESENTATIVIDADE DAS FUNÇÕES PRIMITIVAS 50 5 OTIMIZAÇÃO DE FUNÇÕES MAJORITÁRIAS 53 5.1 PROBLEMA DE PROGRAMAÇÃO LINEAR 54 5.2 PROPRIEDADES DAS OPERAÇÕES AND e OR 56 5.3 NÍVEIS DAS FUNÇÕES MAJORITÁRIAS 59 5.4 RESTRIÇÕES PARA O PLI BINÁRIO 60 5.5 FUNÇÃO OBJETIVO E PLI BINÁRIO COMPLETO 65 6 ALGORITMO MLP01 70 6.1 ESTRUTURA GERAL DO SOFTWARE 70 6.2 UTILIZANDO O SOLUCIONADOR CPLEX 71 6.3 DESCRIÇÃO DO FUNCIONAMENTO DO MLP01 72 7 TESTES E RESULTADOS 74 7.1 EXEMPLOS DE APLICAÇÃO DO MLP01 74 7.2 RESULTADOS DE IMPLEMENTAÇÃO DO MLP01 77 7.3 CONSIDERAÇÕES A RESPEITO DO MLP01 79 8 CONCLUSÃO 82 REFERÊNCIAS 83 13 1 INTRODUÇÃO Devido ao advento da tecnologia semicondutora, o CI (Circuito Integrado) é responsável pelo imenso avanço da computação digital. O constante desenvolvimento da tecnologia CMOS (Complementary Metal-Oxide Semicondutor) nos últimos anos, fez com que continuassem surgindo modernos dispositivos encapsulados na forma de um CI. Estes dispositivos estão mais rápidos, ocupando menores espaços físicos, requisitando tensões menores, consumindo baixa potência e dispondo de uma imensa escala de integração. Atualmente, pode-se encontrar milhões de transistores num único CI, que pode ser programado para se criar sistemas extremamente sofisticados (JAIN, 2010). A tecnologia CMOS representou uma grande revolução tecnológica. No entanto, esta tecnologia tem atingido algumas de suas limitações de implementação. Isso tem impedido o aumento na densidade destes componentes em seu espaço físico de ocupação. Consequentemente, pesquisas têm sido desenvolvidas nos últimos anos, de modo a obter-se novas tecnologias capazes de contemplar esta lacuna (WANG; NIAMAT; VEMERU; ALAM; KILLIAN, 2015). Exemplos destas tecnologias são a QCA (Quantum-dot Cellular Automata), SET (Single Electron Tunneling) e TPL (Tunneling Phase Logic). Todas ainda em fase de pesquisa e desenvolvimento, atuam em nível nanotecnológico e baseiam-se em lógica majoritária. Diferentemente, a tecnologia CMOS utiliza-se da lógica booleana clássica. Em se tratando da tecnologia QCA, tem-se uma nova forma de computação em nano escala. Desta forma, pode-se representar informações binárias baseadas numa distribuição espacial da configuração de elétrons em moléculas químicas (QADIR; AHMAD; WANI; PEER, 2013). Na tecnologia SET tem-se a expectativa de reduzir o tamanho dos circuitos digitais feitos de silício. Espera-se controlar os elétrons, de forma individual, nos circuitos projetados (REHAN, 2007). Para o caso da tecnologia TPL, tem-se a informação binária representada pela fase dos elétrons portadores da informação, não mais se utilizando os valores de tensão (FAHMY; KIEHL, 1999). 14 Na década de 1950, dispositivos eletrônicos conhecidos como parametrons e diodos Esaki já eram utilizados para desempenhar a função de portas lógicas majoritárias. Como uma nova alternativa para execução destas portas lógicas, Wigington (1959) utilizou fontes permanentes de tensão senoidal para transportar níveis lógicos binários através da fase dos sinais de tensão. Por exemplo, uma fase em torno da frequência 0 representava o nível lógico 0 e uma fase em torno da frequência 𝜋𝜋 representava o nível lógico 1. Interações entre três destas fontes de tensão eram capazes de reproduzir o comportamento majoritário de uma porta lógica de 3 entradas. Como pioneiro na descrição e no uso da lógica majoritária, Lindaman (1960) sinaliza a importância desta nova metodologia como uma evolução para o desenvolvimento da computação. Foi proposto um teorema de conversão capaz de converter funções booleanas em funções majoritárias. A aplicação de portas lógicas majoritárias foi explorada como uma nova forma de simplificação e otimização de circuitos lógicos combinacionais. Percebendo a necessidade de uma nova notação no contexto algébrico, Cohn e Lindaman (1961) criam uma nova simbologia contemplando a lógica majoritária. Deste modo, a lógica majoritária torna-se uma extensão da álgebra booleana. São propostos uma série de axiomas que facilitam a manipulação de expressões majoritárias e as interligam com expressões algébricas booleanas clássicas. Assim, funções booleanas podem ser escritas exclusivamente na forma majoritária. O intuito deste trabalho não é abordar nem discutir as tecnologias e linhas de pesquisa que abordam o caráter físico de sua implementação. Serão abordados tópicos relativos aos métodos matemáticos e computacionais que podem ser empregados nos processos de minimização e otimização dos projetos de circuitos lógicos combinacionais que se utilizem de portas lógicas majoritárias. 1.1 A LÓGICA MAJORITÁRIA E OS PROCESSOS DE OTIMIZAÇÃO Funções booleanas possuem correspondência direta com os circuitos lógicos combinacionais. Deste modo, minimizar estas funções significa diminuir os custos de 15 produção e execução do projeto de sistemas digitais. Dentre os métodos mais consagrados de minimização de funções booleanas, destacam-se os métodos tabulares do Mapa de Karnaugh, proposto por Karnaugh (1953) e o método de Quine- McCluskey, proposto por McCluskey (1956). Dentre os métodos computacionais, obteve destaque, por exemplo, o programa ESPRESSO proposto por Brayton, Vincentelli, McMullen e Hatchel (1984). Quando se aplicam os métodos tradicionais de minimização, os resultados obtidos são funções booleanas na forma clássica. Portanto, estes métodos não podem ser aplicados em correspondência direta com as funções no formato majoritário. Deste modo, se fazem necessários a pesquisa e o desenvolvimento de novos métodos capazes de otimizar funções booleanas, obtendo-as no padrão de funções lógicas majoritárias. Nos últimos anos, surgiram inovações e sofisticações dentro da estrutura da lógica majoritária, visando sua melhor compreensão e aplicabilidade. Amaru et al. (2014) apresentam o uso do MIG (Majority-Inverter Graph). Trata-se de um sistema gráfico em forma de árvore para a descrição de expressões e circuitos majoritários. Assim, tanto uma função booleana quanto uma função majoritária podem ser descritas graficamente através de uma rede de nós e ramificações, facilitando suas análises e permitindo uma melhor analogia com a aplicação de métodos de simplificação. Visando uma nova nomenclatura para as funções majoritárias, Wang et al. (2015) apresentam uma concepção inédita para a simplificação de funções booleanas. É proposto que toda função booleana pode ser descrita como sendo uma composição de funções majoritárias elementares. Estas funções, denominadas primitivas, podem ser expressas de forma majoritária com 3 termos. Este fato torna-se referência para o surgimento de vários métodos para síntese e otimização de funções empregando a lógica majoritária. Desta forma, funções mais complexas puderam ser expressas como uma composição de funções mais simples. Conjuntamente, foi proposto o primeiro algoritmo de síntese utilizando as primitivas. Através do Mapa de Karnaugh de uma função booleana, o conjunto de células de seus mintermos devem ser deslocados até se adequarem aos Mapas de Karnaugh das primitivas. Estas podem fazer parte da composição de funções majoritárias que representarão a função inicial. 16 Dentro do contexto de uma nova nomenclatura e da noção de funções primitivas, Chattopadhyay et al. (2016) reapresentam toda a estruturação axiomática e os teoremas envolvendo a lógica majoritária. Tem-se agora uma abordagem matemática mais sintática e objetiva, onde os teoremas são subdivididos em categorias bem determinadas e muitas identidades demonstradas, de modo a facilitar a compreensão e sintetização de funções booleanas através de funções majoritárias. Considerado um algoritmo eficiente para a otimização de funções, o exact_mig foi desenvolvido por Soeken, et. al (2017). Visa a chamada síntese exata, que corresponde à forma mais simplificada e otimizada de uma função expressa na forma majoritária de 3 entradas. Utiliza-se de estruturas do tipo MIG e recebe como entrada um vetor que representa a função que se pretende otimizar. Conjuntamente, é usado um solucionador de satisfatibilidade. O algoritmo retorna uma função majoritária composta por primitivas. Em decorrência de sua complexidade, é indicado para funções de até 6 variáveis. Também utilizando-se do conceito de primitivas, Ferraz (2018) desenvolveu o algoritmo MPC (Majority Primitives Combination). Com critérios de custo próprios, incluindo aqueles utilizados pelo exact_mig, o algoritmo recebe como entrada um vetor proveniente de uma tabela verdade. Então é produzida uma função majoritária de 3 entradas composta por primitivas. Em muitos casos, obteve-se resultados melhores que os obtidos no exact_mig, quando se utilizam os dois outros critérios de custo. Por se tratar de um algoritmo exaustivo, o MPC é indicado para até 5 variáveis com no máximo 4 níveis. Baseando-se ainda nas primitivas de uma função majoritária de 3 entradas, Muniz (2019) desenvolve o algoritmo MK4. Com critérios de custo semelhantes aos utilizados no exact_mig e no MPC, também recebe como entrada um vetor proveniente de uma tabela verdade. A otimização é baseada na busca de primitivas, que quando compostas apresentam os mesmos mintermos da função original. Desenvolvido para até 4 variáveis, o MK4 apresentou parte de seus resultados com qualidade superior aos obtidos pelo exact_mig, quando se utilizam seus próprios critérios de custo. Embora as pesquisas de otimização concentrem-se em funções majoritárias de 3 entradas, pesquisas recentes já abordam funções de 5 entradas. Chu, Haaswijk, 17 Soeken, Xia, Wang e De Micheli (2019) propuseram um algoritmo de minimização de funções booleanas para a síntese exata. É baseado nas propriedades de simetria das funções majoritárias com 5 entradas e visa um número mínimo de operações. Neste trabalho apresenta-se uma forma não exaustiva de minimização de funções booleanas utilizando programação linear inteira binária. Obteve-se resultados simplificados com o uso de funções primitivas com funções majoritárias de 3 entradas. Também foi feita a dedução de uma função matemática capaz de fornecer a quantidade de primitivas para quaisquer quantidades de variáveis em funções majoritárias de 3 entradas. 18 2 ÁLGEBRA BOOLEANA E CIRCUITOS COMBINACIONAIS Em 1854, o matemático George Boole descreveu como o ser humano toma decisões lógicas a partir de circunstâncias verdadeiras ou falsas. Desenvolveu um sistema que se utiliza de símbolos e operações matemáticas para descrever estas decisões e circunstâncias. A este sistema atribuiu-se o nome de Álgebra Booleana. Deste modo, proposições e suas interações são representadas por variáveis e símbolos (WIDMER; MOSS; TOCCI, 2018). A álgebra booleana de interesse nesta pesquisa é aquela cujo conjunto universo é formado apenas por dois elementos numéricos: 0 e 1, chamadas constantes booleanas. As operações fundamentais definidas na álgebra booleana são a adição (ou disjunção, também chamada de “OU” ou “OR”), a multiplicação (ou conjunção, também chamada de “E” ou “AND”) e a negação (ou inversão ou complementação, também chamada de “NÃO” ou “NOT”). A negação de uma variável 𝑋𝑋 será representada com as simbologias 𝑋𝑋� ou 𝑋𝑋′. Na Tabela 1 são apresentadas as 3 operações fundamentais da álgebra booleana. Tabela 1 – As três operações básicas da álgebra booleana. X Y X̅ Y̅ X + Y X ∙ Y 0 0 1 1 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 1 Fonte: Elaboração do próprio autor. 19 2.1 FUNÇÃO BOOLEANA E A TABELA VERDADE Utilizando-se das constantes booleanas do conjunto {0, 1} e das operações entre variáveis booleanas, podem ser estabelecidas relações biunívocas entre estas variáveis. A este modelo de relação dá-se o nome de função booleana (ROSEN, 2019). Na Equação (1) exemplifica-se uma função booleana 𝐹𝐹 das variáveis 𝑋𝑋, 𝑌𝑌 e 𝑍𝑍. As funções booleanas podem representar o comportamento de um sistema e possuem a característica de sempre assumirem o valor de uma das duas constantes do conjunto {0, 1} . Devido a maneira como foi definida, a álgebra booleana é constituída por vários teoremas. Na Tabela 2 são apresentados alguns dos teoremas mais representativos da álgebra booleana, onde 𝑋𝑋, 𝑌𝑌 e 𝑍𝑍 são variáveis booleanas. 𝐹𝐹: {0, 1} → {0, 1}; 𝐹𝐹 = 𝑋𝑋 ∙ 𝑌𝑌 ∙ �̅�𝑍 + 𝑋𝑋� ∙ 𝑌𝑌� + 𝑍𝑍 (1) A maioria dos teoremas mostrados na Tabela 2 podem ser interpretados como axiomas, devido a seu caráter fundamental. Alguns dos teoremas podem ser demonstrados utilizando outros teoremas prévios. Por exemplo, o Teorema B.16 pode ser demonstrado utilizando, sucessivamente, os Teoremas B.13, B.6 e B.15. Na Equação (2) tem-se a demonstração do teorema B.16. Outra forma para demonstrar os teoremas é utilizando o conceito de Tabela-Verdade. 𝑋𝑋 ∙ (𝑋𝑋 + 𝑌𝑌) = 𝑋𝑋 ∙ 𝑋𝑋 + 𝑋𝑋 ∙ 𝑌𝑌 = 𝑋𝑋 + 𝑋𝑋 ∙ 𝑌𝑌 = 𝑋𝑋 (2) Nos projetos de sistemas lógicos, uma tabela-verdade descreve o comportamento de uma função lógica, listando todos os arranjos possíveis das entradas e todas as possibilidades de saída decorrentes destas entradas (WAKERLY, 2006). Pode-se demonstrar os teoremas da Tabela 2 utilizando um método conhecido por “demonstração por exaustão” ou “indução perfeita”. Trata-se de verificar a validade 20 da expressão testando todos os casos possíveis. Utilizando este método, apresenta- se na Tabela 3 a demonstração do Teorema B.11 através da completa exaustão de sua tabela-verdade. Observa-se que a função foi confirmada para todos os 8 arranjos possíveis. Tabela 2 – Teoremas da álgebra booleana. ORDEM TEOREMA B.1 X + 0 = X B.2 X + 1 = 1 B.3 X ∙ 0 = 0 B.4 X ∙ 1 = X B.5 X + X = X B.6 X ∙ X = X B.7 X + X̅ = 1 B.8 X ∙ X̅ = 0 B.9 X + Y = Y + X B.10 X ∙ Y = Y ∙ X B.11 X + Y + Z = (X + Y) + Z = X + (Y + Z) B.12 X ∙ Y ∙ Z = (X ∙ Y) ∙ Z = X ∙ (Y ∙ Z) B.13 X ∙ (Y + Z) = X ∙ Y + X ∙ Z B.14 X + Y ∙ Z = (X + Y) ∙ (X + Z) B.15 X + X ∙ Y = X B.16 X ∙ (X + Y) = X B.17 X + X̅ ∙ Y = (X + Y) B.18 X ∙ (X̅ + Y) = X ∙ Y B.19 X ∙ Y + X ∙ Y̅ = X B.20 (X + Y) ∙ (X + Y̅) = X B.21 X ∙ Y + X̅ ∙ Z = (X + Z) ∙ (X̅ + Y) B.22 (X + Y) ∙ (X̅ + Z) = X ∙ Z + X̅ ∙ Y B.23 X ∙ Y + X̅ ∙ Z + Y ∙ Z = (X + Y) ∙ (X̅ + Z) B.24 (X + Y) ∙ (X̅ + Z) ∙ (Y + Z) = (X + Y) ∙ (X̅ + Z) B.25 X + Y + Z + ... = (X + Y) + Z + ... B.26 X ∙ Y ∙ Z ∙ ... = (X ∙ Y) ∙ Z ∙ ... B.27 (X ∙ Y)' = X̅ + Y̅ B.28 (X + Y)' = X̅ ∙ Y̅ 21 B.29 (X ∙ Y ∙ Z ∙ ...)' = X̅ + Y̅ + Z̅ + ... B.30 (X + Y + Z + ...)' = X̅ ∙ Y̅ ∙ Z̅ ∙ ... Fonte: Adaptado de (Jain, 2010). Tabela 3 – Tabela-verdade referente à demonstração do teorema B.11. X Y Z X + Y + Z (X + Y) + Z X + (Y + Z) 0 0 0 0 + 0 + 0 = 0 (0 + 0) + 0 = 0 + 0 = 0 0 + (0 + 0) = 0 + 0 = 0 0 0 1 0 + 0 + 1 = 1 (0 + 0) + 1 = 0 + 1 = 1 0 + (0 + 1) = 0 + 1 = 1 0 1 0 0 + 1 + 0 = 1 (0 + 1) + 0 = 1 + 0 = 1 0 + (1 + 0) = 0 + 1 = 1 0 1 1 0 + 1 + 1 = 1 (0 + 1) + 1 = 1 + 1 = 1 0 + (1 + 1) = 0 + 1 = 1 1 0 0 1 + 0 + 0 = 1 (1 + 0) + 0 = 1 + 0 = 1 1 + (0 + 0) = 1 + 0 = 1 1 0 1 1 + 0 + 1 = 1 (1 + 0) + 1 = 1 + 1 = 1 1 + (0 + 1) = 1 + 1 = 1 1 1 0 1 + 1 + 0 = 1 (1 + 1) + 0 = 1 + 0 = 1 1 + (1 + 0) = 1 + 1 = 1 1 1 1 1 + 1 + 1 = 1 (1 + 1) + 1 = 1 + 1 = 1 1 + (1 + 1) = 1 + 1 = 1 Fonte: Elaboração do próprio autor. No transcorrer deste capítulo utilizou-se um sistema lógico aleatório representado pela tabela-verdade mostrada na Tabela 4. 𝐹𝐹1 e 𝐹𝐹2 são funções das variáveis 𝑋𝑋 , 𝑌𝑌 e 𝑍𝑍 e podem assumir apenas as constantes booleanas 0 e 1 . Nas tabelas-verdades estão expressas todas as possibilidades para este sistema. Tabela 4 – Tabelas-verdades das funções 𝐹𝐹1 e 𝐹𝐹2. X Y Z F1 F2 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 22 1 1 0 0 0 1 1 1 0 1 Fonte: Elaboração do próprio autor. 2.2 MINTERMOS, MAXTERMOS E FORMA VETORIAL Considere um sistema digital com 𝑛𝑛 variáveis e os 2𝑛𝑛 arranjos de constantes booleanas contidas nas linhas de sua tabela-verdade. A cada arranjo está associada uma função representada pelo produto destas 𝑛𝑛 variáveis, podendo estar na forma complementada ou não, que recebe o nome de mintermo. De forma semelhante, cada função representada pela soma destas 𝑛𝑛 variáveis, podendo estar na forma complementada ou não, recebe o nome de maxtermo (KOHAVI; JHA, 2010). Cada mintermo representa uma função das 𝑛𝑛 variáveis e é formado pela correspondência direta com o arranjo correspondente da tabela-verdade. Se o valor da variável é 1, a representação do mintermo é na forma não complementada e se o valor for 0 estará na forma complementada. De forma análoga, se o valor da variável é 0, ela aparece no maxtermo na forma não complementada e se o valor for 1 aparece na forma complementada. Todos os mintermos assumem o valor 1 para os respectivos valores de variáveis. Analogamente, todos os maxtermos assumem o valor 0 para os respectivos valores de variáveis. Para cada arranjo expresso numa linha da tabela- verdade há 1 mintermo e 1 maxtermo correspondentes. Consequentemente, há um total de 2𝑛𝑛 mintermos e 2𝑛𝑛 maxtermos para um sistema de 𝑛𝑛 variáveis. Partindo da tabela-verdade, tem-se que qualquer variável de saída poderá ser representada através de uma função booleana definida pela soma de seus mintermos, ou seja, na forma SOP (Sum of Products). Da mesma forma, qualquer variável de saída poderá ser representada através de uma função booleana definida pelo produto de seus maxtermos, ou seja, na forma POS (Product of Sums). Portanto, cada valor 1 presente na coluna da variável de saída indicará a presença do mintermo correspondente e cada valor 0 presente na coluna da variável de saída indicará a presença de um maxtermo correspondente. Para ilustrar estes 23 conceitos, na Tabela 5 são mostrados todos os mintermos e maxtermos para o sistema descrito por 3 variáveis, que corresponde ao sistema descrito na Tabela 4. As posições dos mintermos e maxtermos são ordenadas de 0 até (2𝑛𝑛 − 1), num total de 2𝑛𝑛 posições. A partir de suas tabelas-verdades, pode-se obter as funções de saída 𝐹𝐹1 e 𝐹𝐹2 como soma de produtos e produto de somas, conforme é apresentado nas Equações (3), (4), (5) e (6). Tabela 5 – Mintermos e maxtermos para 3 variáveis. X Y Z MINTERMO MAXTERMO ORDEM 0 0 0 X̅ ∙ Y̅ ∙ Z̅ X + Y + Z 0 0 0 1 X̅ ∙ Y̅ ∙ Z X + Y + Z̅ 1 0 1 0 X̅ ∙ Y ∙ Z̅ X + Y̅ + Z 2 0 1 1 X̅ ∙ Y ∙ Z X + Y̅ + Z̅ 3 1 0 0 X ∙ Y̅ ∙ Z̅ X̅ + Y + Z 4 1 0 1 X ∙ Y̅ ∙ Z X̅ + Y + Z̅ 5 1 1 0 X ∙ Y ∙ Z̅ X̅ + Y̅ + Z 6 1 1 1 X ∙ Y ∙ Z X̅ + Y̅ + Z̅ 7 Fonte: Elaboração do próprio autor. 𝐹𝐹1 = ∑ {0, 1, 2, 3, 5}𝑚𝑚 = 𝑋𝑋� ∙ 𝑌𝑌� ∙ �̅�𝑍 + 𝑋𝑋� ∙ 𝑌𝑌� ∙ 𝑍𝑍 + 𝑋𝑋� ∙ 𝑌𝑌 ∙ �̅�𝑍 + 𝑋𝑋� ∙ 𝑌𝑌 ∙ 𝑍𝑍 + 𝑋𝑋 ∙ 𝑌𝑌� ∙ 𝑍𝑍 (3) 𝐹𝐹1 = ∏ {4, 6, 7}𝑀𝑀 = (𝑋𝑋� + 𝑌𝑌 + 𝑍𝑍) ∙ (𝑋𝑋� + 𝑌𝑌� + 𝑍𝑍) ∙ (𝑋𝑋� + 𝑌𝑌� + �̅�𝑍) (4) 𝐹𝐹2 = ∑ {0, 4, 7}𝑚𝑚 = 𝑋𝑋� ∙ 𝑌𝑌� ∙ �̅�𝑍 + 𝑋𝑋 ∙ 𝑌𝑌� ∙ �̅�𝑍 + 𝑋𝑋 ∙ 𝑌𝑌 ∙ 𝑍𝑍 (5) 𝐹𝐹2 = ∏ {1, 2, 3, 5, 6}𝑀𝑀 = (𝑋𝑋 + 𝑌𝑌 + �̅�𝑍) ∙ (𝑋𝑋 + 𝑌𝑌� + 𝑍𝑍) ∙ (𝑋𝑋 + 𝑌𝑌� + �̅�𝑍) ∙ ∙ (𝑋𝑋� + 𝑌𝑌 + �̅�𝑍) ∙ (𝑋𝑋� + 𝑌𝑌� + 𝑍𝑍) (6) 24 Num sistema com uma quantidade de variáveis 𝑄𝑄𝑣𝑣𝑣𝑣𝑣𝑣 igual a 𝑛𝑛, qualquer função conterá 2𝑛𝑛 elementos 0 ou 1 em sua coluna da tabela-verdade. De forma equivalente, para qualquer função, a soma da quantidade de mintermos 𝑄𝑄𝑚𝑚 com a quantidade 𝑄𝑄𝑀𝑀 de maxtermos será 2𝑛𝑛 , conforme é mostrado na Equação (7). A pesquisa desenvolvida neste trabalho se utiliza dos mintermos, de modo em seu transcorrer não serão abordados os maxtermos. 𝑄𝑄𝑣𝑣𝑣𝑣𝑣𝑣 = 𝑛𝑛 ⟹ 𝑄𝑄𝑚𝑚 + 𝑄𝑄𝑀𝑀 = 2𝑛𝑛 (7) Numa tabela-verdade, a cada função (ou variável de saída) está associada uma coluna contendo 2𝑛𝑛 elementos, relativos às 𝑛𝑛 variáveis de entrada. Assim, cada variável de saída está associada a uma matriz coluna com 2𝑛𝑛 elementos. Da mesma forma, cada variável de saída está associada a uma matriz linha (ou, simplesmente, vetor linha) que é a matriz transposta da matriz coluna proveniente da tabela-verdade. Esta matriz linha será nomeada de forma vetorial. Na Equação (8) são apresentadas as formas vetoriais das funções 𝐹𝐹1 e 𝐹𝐹2, relativas ao sistema que foi representado na Tabela 4. 𝐹𝐹1 = [1 1 1 1 0 1 0 0]; 𝐹𝐹2 = [1 0 0 0 1 0 0 1] (8) A forma vetorial indica quais mintermos compõem a função de saída, relativa às 𝑛𝑛 variáveis. Além disso, se a forma vetorial possui uma quantidade 𝑞𝑞 de elementos, há uma correspondência biunívoca entre 𝑞𝑞 e 𝑛𝑛 . Ou seja, a própria quantidade de elementos da forma vetorial de uma função booleana indica a quantidade de variáveis possíveis da entrada do sistema. Esta relação biunívoca entre 𝑞𝑞 e 𝑛𝑛 é apresentada na Equação (9). Na equação (10) é exemplificado o caso de sistemas com 3 variáveis de entrada. Assim, tem-se na forma vetorial um modo compacto de representar uma função booleana, dispensando a extensão visual de uma tabela-verdade. Ou seja, a 25 quantidade de variáveis do sistema e todos os arranjos possíveis são intrínsecos à forma vetorial da função. 𝑞𝑞 = 2𝑛𝑛 ⟹ log2 𝑞𝑞 = log2 2𝑛𝑛 = 𝑛𝑛 ⟹ 𝑛𝑛 = log2 𝑞𝑞 (9) 𝑞𝑞 = 8 ⟹𝑛𝑛 = log2 8 = log2 23 = 3 ⟹ 𝑛𝑛 = 3 (10) 2.3 SIMPLIFICAÇÃO DE FUNÇÕES BOOLEANAS As funções booleanas obtidas a partir de uma tabela verdade, como as mostradas nas Equações (3), (4), (5) e (6) para representar 𝐹𝐹1 e 𝐹𝐹2, não estão em suas formas mais simples e compactas. Devem ser utilizados métodos de simplificação que possam eliminar redundâncias como a mostrada na Equação (11), proveniente dos mintermos 0 e 1 da forma de SOP da função 𝐹𝐹1. Na simplificação desta expressão foram utilizados, respectivamente, os Teoremas B.13, B.7 e B.4. 𝑋𝑋� ∙ 𝑌𝑌� ∙ �̅�𝑍 + 𝑋𝑋� ∙ 𝑌𝑌� ∙ 𝑍𝑍 = (𝑋𝑋� ∙ 𝑌𝑌�) ∙ (�̅�𝑍 + 𝑍𝑍) = (𝑋𝑋� ∙ 𝑌𝑌�) ∙ 1 = 𝑋𝑋� ∙ 𝑌𝑌� (11) Um dos métodos mais consagrados de minimização para funções booleanas é o Mapa de Karnaugh. Um mapa de Karnaugh é uma estrutura geométrica na forma de quadro que representa uma função booleana mapeando seus valores, provenientes de uma tabela verdade (KARNAUGH, 1953). A cada valor da coluna da função de saída corresponde uma célula do mapa, de modo que a uma função de 𝑛𝑛 variáveis corresponde um mapa com 2𝑛𝑛 células. Associam-se células adjacentes em quantidade de potência de 2, com formato retangular, de modo a remover redundâncias e obter a função minimizada. Na Figura 1 estão representados os mapas de Karnaugh das funções 𝐹𝐹1 e 𝐹𝐹2, relativas as Equações (3) e (5), respectivamente. Aqui utilizou-se a análise na forma de SOP, não abordando a forma POS, que é equivalente. No mapa, as posições dos 26 mintermos são dispostas de forma que duas células adjacentes difiram em apenas 1 variável. As bordas do mapa são virtualmente conectadas às bordas opostas, também podendo ser associadas na simplificação. Para o caso da função 𝐹𝐹1, podem ser associadas as células dos mintermos 0, 1, 2 e 3 num retângulo de dimensões 21 por 21 e as células dos mintermo 1 e 5 num retângulo de dimensões 21 por 20. Para o caso da função 𝐹𝐹2, podem ser associadas as células dos mintermos 0 e 4 num retângulo de dimensões 21 por 20 e a célula do mintermo 7 num retângulo de dimensões 20 por 20. Para cada retângulo destacado, elimina-se da parcela original da SOP as variáveis que assumiram os valores 0 e 1 no Figura 1 – Mapas de Karnaugh das funções 𝐹𝐹1 e 𝐹𝐹2. Fonte: Elaboração do próprio autor. mesmo retângulo. Mantem-se na parcela as variáveis que assumirem apenas o valor 1 e sua negação caso assuma o valor 0 no retângulo. Naturalmente, se no mapa existirem apenas retângulos com dimensões 20 por 20, então o método não pode simplificar a função. Na equação (12) são mostradas as funções 𝐹𝐹1 e 𝐹𝐹2 minimizadas após o uso do mapa de Karnaugh. 𝐹𝐹1 = 𝑋𝑋� + 𝑌𝑌� ∙ 𝑍𝑍; 𝐹𝐹2 = 𝑌𝑌� ∙ �̅�𝑍 + 𝑋𝑋 ∙ 𝑌𝑌 ∙ 𝑍𝑍 (12) 27 2.4 CIRCUITOS LÓGICOS COMBINACIONAIS Com o surgimento das válvulas e transistores, foi possível desenvolver uma correspondência física entre a álgebra booleana e os circuitos eletrônicos. Um CI é uma estrutura inteiramente construída numa única planta de silício. Resistores, capacitores, diodos e transistores estão interligados de forma integrada nessa minúscula estrutura. Inicialmente, utilizava-se o TBJ (Transistor Bipolar de Junção) e atualmente as tecnologias mais modernas utilizam-se dos transistores do tipo MOSFET (Metal-Oxide Semiconductor Field-Effect Transistor), permitindo uma extrema escala de integração em dispositivos com lógica fixa e nos de lógica programável (FLOYD, 2015). A tecnologia MOSFET permitiu o desenvolvimento de CI’s para os mais diversos propósitos. Dispõe-se de microprocessadores, microcontroladores, PDS (Processador Digital de Sinais), FPGA (Field Programmable Gate Array), memórias do tipo RAM (Random Access Memory), dispositivos PLD (Programmable Logic Device), dentre outros. Cada um destes dispositivos pode operar corretamente em virtude dos minúsculos circuitos eletrônicos que os compõe. Fundamentalmente, no interior de cada um destes dispositivos há uma enorme quantidade de funções booleanas implementadas fisicamente com o uso de portas lógicas. Uma porta lógica representa fisicamente uma operação booleana através de um circuito eletrônico. As portas lógicas são a base dos sistemas digitais. As entradas e as saídas assumem valores de tensão de nível baixo ou alto que correspondem às constantes booleanas 0 e 1, respectivamente (FRANCO, 2015). Na Figura 2 são apresentadas as três portas lógicas fundamentais. Figura 2 – Representação esquemática das três portas lógicas fundamentais. Fonte: Elaboração do próprio autor. 28 Um circuito lógico combinacional é constituído de portas lógicas nas quais, em cada instante, as saídas são funções exclusivamente das entradas. Assim, este circuito não possui memória e não dispõem de realimentação. Uma grande quantidade de sistemas é composta por circuitos lógicos combinacionais (SEDRA; SMITH; CARUSONE; GAUDET, 2020). Utilizando-se de portas lógicas, é possível projetar os circuitos lógicos combinacionais apresentados na Figura 3, que representam as funções booleanas de 𝐹𝐹1 e 𝐹𝐹2, que foram descritas na Equação (12). Neste circuito combinacional existe uma Figura 3 – Circuito lógico combinacional para as funções 𝐹𝐹1 e 𝐹𝐹2. Fonte: Elaboração do próprio autor. porta lógica AND de 3 entradas. Também é possível projetar portas lógicas mais complexas utilizando as portas fundamentais. Para ilustrar este fato, na Equação (13) é descrita a função XOR (disjunção exclusiva) e na Figura 4 é mostrado o circuito lógico combinacional que implementa esta função com portas fundamentais. 𝑋𝑋⨁𝑌𝑌 = 𝑋𝑋 ∙ 𝑌𝑌� + 𝑋𝑋� ∙ 𝑌𝑌 (13) 29 Figura 4 – Circuito lógico combinacional da porta XOR. Fonte: Elaboração do próprio autor. 30 3 LÓGICA MAJORITÁRIA Para que se possa desenvolver a lógica majoritária é preciso contextualizar os termos maioria e majoritário. Considere um conjunto formado por 𝑒𝑒 elementos pertencentes ao conjunto {0, 1} , sendo 𝑒𝑒 ímpar e 𝑒𝑒 ≥ 3 . A maioria dentre os 𝑒𝑒 elementos é o valor que está presente em maior quantidade. Nesta definição, não se pode obter a maioria de um conjunto unitário nem de uma quantidade par de elementos, justificando as restrições impostas sobre 𝑒𝑒. Dentro do contexto da álgebra booleana, uma função que tem por imagem a maioria dos valores das variáveis de seu domínio é uma função majoritária. Daqui em diante será usado o termo “função majoritária” para referir-se a qualquer função que esteja lidando com a maioria de um conjunto de elementos booleanos. Comercialmente, existe o CI MC14530B que disponibiliza um par de circuitos que executam a maioria de 5 entradas (MOTOROLA, 1995). Este CI é baseado na tecnologia TTL (Transistor-Transistor Logic). Naturalmente, como este CI é concebido com portas lógicas tradicionais, não se enquadra na lógica majoritária proposta. 3.1 A FUNÇÃO MAJORITÁRIA Na época de suas pesquisas, Lindaman (1960) e Cohn e Lindaman (1961) não dispunham da nanotecnologia e realizavam suas abordagens em circuitos de tecnologia semicondutora. Porém a abordagem booleana desenvolvida na época pode ser feita da mesma forma atualmente. Na Tabela 6 é apresentada a tabela- verdade para a função majoritária de 3 entradas. Será utilizada a notação 𝑀𝑀(𝑋𝑋,𝑌𝑌,𝑍𝑍) proposta por Chattopadhyay et al. (2016) para indicar uma função majoritária de 3 entradas nas variáveis 𝑋𝑋, 𝑌𝑌 e 𝑍𝑍. A partir da Tabela 6, pode-se obter a forma vetorial da função maioria, que é mostrada na Equação (14). 𝑀𝑀(𝑋𝑋,𝑌𝑌,𝑍𝑍) = [0 0 0 1 0 1 1 1] (14) 31 Tabela 6 – Tabela-verdade da função majoritária de 3 entradas. X Y Z M(X, Y, Z) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 Fonte: Elaboração do próprio autor. Através da tabela-verdade ou da forma vetorial, pode-se construir o mapa de Karnaugh da função majoritária, que é mostrado na Figura 5. A minimização obtida com o mapa leva a função simplificada indicada na Equação (15). A expressão representa uma relação fundamental poderosa na lógica majoritária para funções de 3 entradas e 𝑛𝑛 variáveis. Figura 5 – Mapa de Karnaugh da função majoritária de 3 entradas. Fonte: Elaboração do próprio autor. 𝑀𝑀(𝑋𝑋,𝑌𝑌,𝑍𝑍) = 𝑋𝑋 ∙ 𝑌𝑌 + 𝑋𝑋 ∙ 𝑍𝑍 + 𝑌𝑌 ∙ 𝑍𝑍 (15) 32 Partindo da função da Equação (15) e usando 3 portas lógicas AND e 1 porta lógica OR, pode-se projetar o circuito lógico combinacional correspondente, que é apresentado na Figura 6. Assim, tem-se a função majoritária de 3 entradas implementada com a tecnologia semicondutora MOSFET. Consequentemente, pode- se criar a porta lógica majoritária numa FPGA, por exemplo. Figura 6 – Circuito lógico combinacional para a função majoritária de 3 entradas. Fonte: Elaboração do próprio autor. 3.2 LÓGICA MAJORITÁRIA E PORTAS LÓGICAS MAJORITÁRIAS Como pode ser observado na relação fundamental da Equação (15), toda função majoritária equivale a uma função booleana correspondente. Sendo assim, todos os teoremas da álgebra booleana mostrados na Tabela 2 se aplicam às funções majoritárias. De fato, o domínio e o contradomínio de uma função majoritária continuam sendo o conjunto {0, 1}, formado pelas constantes booleanas. Na Tabela 7 são apresentados os principais axiomas e teoremas propostos por Cohn e Lindaman (1961) e Chattopadhyay et al. (2016). Cada teorema pode ser demonstrado algebricamente utilizando a relação fundamental ou por indução perfeita. Como exemplo, demonstra-se o teorema M.10 de forma algébrica, conforme é indicado na Equação (16). Em seguida, demonstra-se por exaustão o Teorema M.16, conforme mostrado na Tabela 8. 33 Tabela 7 – Principais axiomas e teoremas da lógica majoritária. ORDEM AXIOMA OU TEOREMA M.1 M(0, 0, 0) = 0 M.2 M(0, 0, 1) = 0 M.3 M(1, 1, 1) = 1 M.4 M(1, 1, 0) = 1 M.5 M(X, 0, 0) = 0 M.6 M(X, 1, 1) = 1 M.7 M(X, X̅, 0) = 0 M.8 M(X, X̅, 1) = 1 M.9 M(X, X, Y) = X M.10 M(X, X̅, Y) = Y M.11 M(X, Y, Z) = M(Y, Z, X) = M(Z, X, Y) M.12 M(X, Y, M(Z, Y, W) ) = M(W, Y, M(Z, Y, X) ) M.13 M(X, Y, M(Z, W, K)) = M(M(X, Y, Z), M(X, Y, W), M(X, Y, K)) M.14 M̅(X, Y, Z) = M(X̅, Y̅, Z̅) M.15 M(X, Y, 0) = X ∙ Y M.16 M(X, Y, 1) = X + Y Fonte: Elaboração do próprio autor. 𝑀𝑀(𝑋𝑋,𝑋𝑋�,𝑌𝑌) = 𝑋𝑋 ∙ 𝑋𝑋� + 𝑋𝑋 ∙ 𝑌𝑌 + 𝑋𝑋� ∙ 𝑌𝑌 = 0 + (𝑋𝑋 + 𝑋𝑋�) ∙ 𝑌𝑌 = 0 + 1 ∙ 𝑌𝑌 = 0 + 𝑌𝑌 = 𝑌𝑌 (16) Tabela 8 – Demonstração do teorema M.16. X Y M(X, Y, 1) X + Y 0 0 M(0, 0, 1) = 0 0 + 0 = 0 0 1 M(0, 1, 1) = 1 0 + 1 = 1 1 0 M(1, 0, 1) = 1 1 + 0 = 1 1 1 M(1, 1, 1) = 1 1 + 1 = 1 Fonte: Elaboração do próprio autor. 34 Na Figura 7 é apresentado o símbolo esquemático de uma porta majoritária básica de 3 entradas que executa a operação fundamental indicada na Equação (14) e suas três variações possíveis. Na Figura 8 é mostrado como se podem implementar as 3 funções booleanas básicas, AND, OR e NOT com as portas majoritárias. Figura 7 – Variações da porta lógica majoritária de 3 entradas. Fonte: Elaboração do próprio autor. Figura 8 – Funções booleanas com portas lógicas majoritárias. Fonte: Elaboração do próprio autor. Pode-se realizar uma análise semelhante para o caso de uma função majoritária de 𝑒𝑒 = 5 entradas. Na Tabela 9 é apresentada a tabela-verdade para esta função. Efetuando a minimização, obtém-se a função simplificada indicada na Equação (17). Então, a partir desta equação, pode-se projetar o circuito lógico combinacional para esta função, que é mostrado na Figura 9. Assim, como pode ser 35 Tabela 9 – Tabela-verdade da função majoritária de 5 entradas. X Y Z W K M(X, Y, Z, W, K) 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 Fonte: Elaboração do próprio autor. 36 observado, a estrutura torna-se bem mais complexa com 5 variáveis, razão pela qual, inclusive, muitas pesquisas continuam concentrando-se em funções majoritárias de 3 entradas. Todavia, pesquisas como as de Chu et al. (2019) começam a ser realizadas abordando funções majoritárias de 5 entradas. 𝑀𝑀(𝑋𝑋, 𝑌𝑌, 𝑍𝑍, 𝑊𝑊, 𝐾𝐾) = 𝑋𝑋 ∙ 𝑌𝑌 ∙ 𝑍𝑍 + 𝑋𝑋 ∙ 𝑌𝑌 ∙ 𝑊𝑊 + 𝑋𝑋 ∙ 𝑌𝑌 ∙ 𝐾𝐾 + 𝑋𝑋 ∙ 𝑍𝑍 ∙ 𝑊𝑊 + 𝑋𝑋 ∙ 𝑍𝑍 ∙ 𝐾𝐾 + 𝑋𝑋 ∙ 𝑊𝑊 ∙ 𝐾𝐾 + + 𝑌𝑌 ∙ 𝑍𝑍 ∙ 𝑊𝑊 + 𝑌𝑌 ∙ 𝑍𝑍 ∙ 𝐾𝐾 + 𝑌𝑌 ∙ 𝑊𝑊 ∙ 𝐾𝐾 + 𝑍𝑍 ∙ 𝑊𝑊 ∙ 𝐾𝐾 (17) Figura 9 – Circuito lógico combinacional para a função majoritária de 5 entradas. Fonte: Elaboração do próprio autor. 3.3 FUNÇÕES MAJORITÁRIAS PRIMITIVAS Qualquer função booleana de 𝑛𝑛 variáveis pode ser expressa na forma de uma função majoritária de 3 entradas ou uma composição destas funções (WANG et al., 2015). Para ilustrar este fato, na Equação (18) é apresentada uma função booleana que pode ser expressa com uma única função majoritária e na Equação (19) é apresentada uma função booleana que para ser expressa requer uma composição de duas funções majoritárias. 37 [1 1 0 1 1 1 0 1] = 𝐴𝐴 + 𝐵𝐵� = 𝑀𝑀(1,𝐴𝐴,𝐵𝐵�) (18) [0 0 0 0 0 0 0 1] = 𝐴𝐴 ∙ 𝐵𝐵 ∙ 𝐶𝐶 = 𝑀𝑀(0,𝐴𝐴,𝑀𝑀(0,𝐵𝐵,𝐶𝐶)) (19) Estando isolada ou na forma de uma composição, cada função majoritária básica da expressão final terá o formato 𝑀𝑀(𝐸𝐸1,𝐸𝐸2,𝐸𝐸3), onde todas as entradas 𝐸𝐸1, 𝐸𝐸2 e 𝐸𝐸3 pertencem ao conjunto {0, 1,𝐴𝐴, �̅�𝐴,𝐵𝐵,𝐵𝐵� ,𝐶𝐶,𝐶𝐶̅,𝐷𝐷,𝐷𝐷�,𝐸𝐸,𝐸𝐸� ,𝐹𝐹,𝐹𝐹� ,𝐺𝐺, �̅�𝐺, … }, que inclui todas as variáveis que sejam necessárias. Cada uma destas funções básicas recebe o nome de função majoritária primitiva (WANG et al., 2015). Na Tabela 10 são apresentadas todas as 40 funções majoritárias primitivas para 𝑛𝑛 = 3 variáveis. Neste trabalho, para funções referentes a 𝑛𝑛 variáveis, utiliza-se a notação 𝑃𝑃𝑖𝑖 para indicar a função majoritária primitiva de posição 𝑗𝑗, sendo 1 ≤ 𝑗𝑗 ≤ 𝑝𝑝(𝑛𝑛), sendo 𝑝𝑝(𝑛𝑛) a quantidade total de primitivas. Assim, para que 𝑃𝑃𝑖𝑖 seja uma função primitiva, deve ser atendida a equivalência indicada na Equação (20) e a posição 𝑗𝑗 segue a metodologia indicada na Equação (21), que foi utilizada para se obter a lista de primitivas da Tabela 10. Para listar e ordenar quaisquer primitivas para funções de 𝑛𝑛 variáveis, utilizou-se a metodologia de verificar todas as possibilidades de entradas na função 𝑀𝑀(𝐸𝐸1,𝐸𝐸2,𝐸𝐸3), descartando as funções repetidas. Destaca-se que a primitiva só será expressa utilizando uma função majoritária se for necessário. Nos casos apresentados na Equação (22), como exemplos de primitivas para funções de 3 variáveis, dispensa-se o uso de uma função majoritária. Neste critério de ordenação, a variável invertida vem depois de todas as outras não invertidas e a posição 𝐸𝐸1 é a mais significativa. Também se admite que é mais favorável a presença do mínimo de inversores na função primitiva, de modo que se utilizam equivalências como a mostrada na Equação (23), onde utiliza-se a propriedade M.14 vista na Tabela 7. Deste modo, também se pode obter, ordenadamente, todas as 90 funções majoritárias primitivas para funções de 𝑛𝑛 = 4 variáveis que são apresentadas na Tabela 11. A ordenação hierárquica utilizada na obtenção das primitivas para 𝑛𝑛 = 4 variáveis foi {0, 1, 𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷, �̅�𝐴, 𝐵𝐵� , 𝐶𝐶̅, 𝐷𝐷�}. 38 Tabela 10 – Funções majoritárias primitivas para 𝑛𝑛 = 3 variáveis. ÍNDICE FORMA MAJORITÁRIA ÍNDICE FORMA MAJORITÁRIA P1 0 P21 M(1, A, B) P2 1 P22 M(1, A, C) P3 A P23 M(1, A, B̅) P4 B P24 M(1, A, C̅) P5 C P25 M(1, B, C) P6 A̅ P26 M(1, B, A̅) P7 B̅ P27 M(1, B, C̅) P8 C̅ P28 M(1, C, A̅) P9 M(0, A, B) P29 M(1, C, B̅) P10 M(0, A, C) P30 M̅(0, A, B) P11 M(0, A, B̅) P31 M̅(0, A, C) P12 M(0, A, C̅) P32 M̅(0, B, C) P13 M(0, B, C) P33 M(A, B, C) P14 M(0, B, A̅) P34 M(A, B, C̅) P15 M(0, B, C̅) P35 M(A, C, B̅) P16 M(0, C, A̅) P36 M(A, B̅, C̅) P17 M(0, C, B̅) P37 M(B, C, A̅) P18 M̅(1, A, B) P38 M(B, A̅, C̅) P19 M̅(1, A, C) P39 M(C, A̅, B̅) P20 M̅(1, B, C) P40 M̅(A, B, C) Fonte: Elaboração do próprio autor. 𝑃𝑃𝑖𝑖 = 𝑀𝑀(𝐸𝐸1,𝐸𝐸2 ,𝐸𝐸3) ⟺ {𝐸𝐸1,𝐸𝐸2,𝐸𝐸3} ⊂ {0, 1,𝐴𝐴, �̅�𝐴,𝐵𝐵,𝐵𝐵� ,𝐶𝐶,𝐶𝐶̅,𝐷𝐷,𝐷𝐷�,𝐸𝐸,𝐸𝐸� ,𝐹𝐹,𝐹𝐹� ,𝐺𝐺, �̅�𝐺, … } (20) 𝑃𝑃𝑖𝑖 ∈ {𝑀𝑀(0, 0, 0),𝑀𝑀(0, 0, 1),𝑀𝑀(0, 0,𝐴𝐴), … ,𝑀𝑀(𝐶𝐶̅,𝐶𝐶̅, �̅�𝐴),𝑀𝑀(𝐶𝐶̅,𝐶𝐶̅,𝐵𝐵�),𝑀𝑀(𝐶𝐶̅,𝐶𝐶̅,𝐶𝐶̅)} (21) 𝑃𝑃3 = 𝑀𝑀(0, 1,𝐴𝐴) = 𝑀𝑀(0,𝐴𝐴,𝐴𝐴) = 𝑀𝑀(1,𝐴𝐴,𝐴𝐴) = 𝑀𝑀(𝐴𝐴, 0,𝐴𝐴) = 𝑀𝑀(𝐴𝐴,𝐴𝐴,𝐴𝐴) = 𝐴𝐴 (22) 𝑃𝑃18 = 𝑀𝑀(0, �̅�𝐴,𝐵𝐵�) = 𝑀𝑀�(1,𝐴𝐴,𝐵𝐵) (23) 39 Tabela 11 - Funções majoritárias primitivas para 𝑛𝑛 = 4 variáveis. (continua) ÍNDICE FORMA MAJORITÁRIA ÍNDICE FORMA MAJORITÁRIA P1 0 P46 M(1, C, D) P2 1 P47 M(1, C, A̅) P3 A P48 M(1, C, B̅) P4 B P49 M(1, C, D̅) P5 C P50 M(1, D, A̅) P6 D P51 M(1, D, B̅) P7 A̅ P52 M(1, D, C̅) P8 B̅ P53 M̅(0, A, B) P9 C̅ P54 M̅(0, A, C) P10 D̅ P55 M̅(0, A, D) P11 M(0, A, B) P56 M̅(0, B, C) P12 M(0, A, C) P57 M̅(0, B, D) P13 M(0, A, D) P58 M̅(0, C, D) P14 M(0, A, B̅) P59 M(A, B, C) P15 M(0, A, C̅) P60 M(A, B, D) P16 M(0, A, D̅) P61 M(A, B, C̅) P17 M(0, B, C) P62 M(A, B, D̅) P18 M(0, B, D) P63 M(A, C, D) P19 M(0, B, A̅) P64 M(A, C, B̅) P20 M(0, B, C̅) P65 M(A, C, D̅) P21 M(0, B, D̅) P66 M(A, D, B̅) P22 M(0, C, D) P67 M(A, D, C̅) P23 M(0, C, A̅) P68 M(A, B̅, C̅) P24 M(0, C, B̅) P69 M(A, B̅, D̅) P25 M(0, C, D̅) P70 M(A, C̅, D̅) P26 M(0, D, A̅) P71 M(B, C, D) P27 M(0, D, B̅) P72 M(B, C, A̅) P28 M(0, D, C̅) P73 M(B, C, D̅) P29 M̅(1, A, B) P74 M(B, D, A̅) P30 M̅(1, A, C) P75 M(B, D, C̅) 40 Tabela 11 - Funções majoritárias primitivas para 𝑛𝑛 = 4 variáveis. (conclusão) ÍNDICE FORMA MAJORITÁRIA ÍNDICE FORMA MAJORITÁRIA P31 M̅(1, A, D) P76 M(B, A̅, C̅) P32 M̅(1, B, C) P77 M(B, A̅, D̅) P33 M̅(1, B, D) P78 M(B, C̅, D̅) P34 M̅(1, C, D) P79 M(C, D, A̅) P35 M(1, A, B) P80 M(C, D, B̅) P36 M(1, A, C) P81 M(C, A̅, B̅) P37 M(1, A, D) P82 M(C, A̅, D̅) P38 M(1, A, B̅) P83 M(C, B̅, D̅) P39 M(1, A, C̅) P84 M(D, A̅, B̅) P40 M(1, A, D̅) P85 M(D, A̅, C̅) P41 M(1, B, C) P86 M(D, B̅, C̅) P42 M(1, B, D) P87 M̅(A, B, C) P43 M(1, B, A̅) P88 M̅(A, B, D) P44 M(1, B, C̅) P89 M̅(A, C, D) P45 M(1, B, D̅) P90 M̅(B, C, D) Fonte: Elaboração do próprio autor. Na definição de função majoritária primitiva, Wang et al. (2015) divide o conjunto de todas as primitivas em 5 subconjuntos, cada qual com características próprias. Primeiramente, tem-se o subconjunto C (Constant), formado pelas duas constantes booleanas: 0 e 1 . As constantes booleanas dispensam o uso de uma função majoritária. O segundo subconjunto é S (Single), formado pelas funções que representam uma variável ou sua inversa. Por exemplo, fazem parte do conjunto S as primitivas 𝐴𝐴 e �̅�𝐴. As primitivas do conjunto S também dispensam o uso da função majoritária. O AND é o terceiro subconjunto, formado por primitivas que equivalem ao produto de duas variáveis, inclusive inversas: 𝑀𝑀(0,𝐴𝐴,𝐵𝐵) e 𝑀𝑀�(1,𝐵𝐵,𝐶𝐶̅), por exemplo. O quarto subconjunto é OR, formado por primitivas que equivalem à soma de duas variáveis, inclusive inversas: 𝑀𝑀(1,𝐴𝐴,𝐵𝐵) e 𝑀𝑀(1,𝐵𝐵,𝐶𝐶̅) , por exemplo. Como último 41 subconjunto tem-se o T (Three), formado por primitivas que representam a maioria de 3 variáveis distintas, inclusive inversas: 𝑀𝑀(𝐴𝐴,𝐵𝐵,𝐶𝐶) e 𝑀𝑀�(𝐴𝐴,𝐵𝐵� ,𝐶𝐶), por exemplo. Todos os 5 subconjuntos de primitivas são disjuntos. Sendo 𝑃𝑃 o conjunto de todas as funções majoritárias primitivas relativas a 𝑛𝑛 variáveis, tem-se que 𝑃𝑃 é a reunião de todos estes 5 subconjuntos, conforme mostrado na equação (24), visto que nenhum destes 5 possui elementos comuns entre si. 𝑃𝑃 = 𝐶𝐶 ∪ 𝑆𝑆 ∪ 𝐴𝐴𝐴𝐴𝐷𝐷 ∪ 𝑂𝑂𝑂𝑂 ∪ 𝑇𝑇 𝑒𝑒 𝐶𝐶 ∩ 𝑆𝑆 ∩ 𝐴𝐴𝐴𝐴𝐷𝐷 ∩ 𝑂𝑂𝑂𝑂 ∩ 𝑇𝑇 = ∅ (24) Neste ponto, ressalta-se que o número de entradas 𝑒𝑒 refere-se a quantas entradas possuem a função majoritária (e, correspondentemente, quantas entradas possui sua porta lógica). A quantidade de variáveis 𝑛𝑛 refere-se a quantas variáveis possui o barramento de dados do sistema e que podem ser requisitadas pela função. Daqui em diante será mencionado apenas o valor de 𝑛𝑛, pois a quantidade de entradas será sempre 𝑒𝑒 = 3. 42 4 ANÁLISE QUANTITATIVA DAS FUNÇÕES MAJORITÁRIAS PRIMITIVAS Quando estabelece o conceito de função majoritária primitiva, Wang et al. (2015) apresenta uma forma para se obter algebricamente e listar a quantidade de 90 primitivas para a função majoritária de 3 entradas e 4 variáveis. Observa-se que algoritmos computacionais têm sido utilizados para encontrar e listar as quantidades de primitivas para mais de 4 variáveis e que não se tem avaliado o que ocorreria se a quantidade de variáveis continuar aumentando. Neste capítulo, apresenta-se a forma que foi desenvolvida para se obter a função 𝑝𝑝(𝑛𝑛) que fornece a quantidade total de funções majoritárias primitivas de 3 entradas e quaisquer 𝑛𝑛 variáveis. Apresenta-se também uma análise algébrica quantitativa desta função. Este procedimento desenvolvido baseia-se na obtenção das quantidades de funções primitivas dos grupos C, S, AND, OR e T através de uma análise combinatória de todas as possibilidades. 4.1 QUANTIDADE TOTAL DE FUNÇÕES PRIMITIVAS POR GRUPO Qualquer que seja a quantidade de variáveis da função majoritária de 3 entradas, só existem duas constantes booleanas: 0 e 1. Sendo assim, a quantidade de funções primitivas 𝑝𝑝𝐶𝐶(𝑛𝑛) do conjunto C será sempre igual a 2, conforme apresentado na Equação (25). Para 𝑛𝑛 variáveis, existem 𝑛𝑛 funções primitivas identidades, uma para cada variável. Também existem 𝑛𝑛 funções primitivas referentes às identidades inversas, uma para cada variável. Assim, a quantidade de funções primitivas 𝑝𝑝𝑆𝑆(𝑛𝑛) do grupo S pode ser obtido, conforme é mostrado na Equação (26). 𝑝𝑝𝐶𝐶(𝑛𝑛) = 1 + 1 ⟹ 𝑝𝑝𝐶𝐶(𝑛𝑛) = 2 (25) 𝑝𝑝𝑆𝑆(𝑛𝑛) = 𝑛𝑛 + 𝑛𝑛 ⟹ 𝑝𝑝𝑆𝑆(𝑛𝑛) = 2𝑛𝑛 (26) 43 No grupo AND as funções primitivas assumem o formato 𝑀𝑀(0,𝐸𝐸2,𝐸𝐸3), onde 𝐸𝐸2,𝐸𝐸3 ≠ 0; 𝐸𝐸2 ,𝐸𝐸3 ≠ 1; 𝐸𝐸2 ≠ 𝐸𝐸3 e 𝐸𝐸2 ≠ 𝐸𝐸�3. Estas restrições garantem que não ocorram redundâncias como, por exemplo, as mostradas na Equação (27). A quantidade de funções deste grupo é exatamente a quantidade de combinações da forma {𝐸𝐸2 ,𝐸𝐸3} que atendam às restrições. Trata-se de um caso de combinação e não de uma permutação, pois a ordem em que se escolhem os elementos 𝐸𝐸2 e 𝐸𝐸3 não é relevante (DETEMPLE; WEBB, 2014). Na Equação (28) é mostrado o uso da propriedade comutativa da função majoritária, justificando o uso da combinação e não da permutação. Deste modo, deve-se obter todas as combinações dos 2𝑛𝑛 elementos do grupo S, tomados 2 a 2, excluindo-se os 𝑛𝑛 casos nos quais tem-se 𝐸𝐸3 = 𝐸𝐸�2 , que conduziriam à primitiva 0, conforme mostrado na Equação (29). Assim, na Equação (30) tem-se a quantidade 𝑝𝑝𝐴𝐴𝐴𝐴𝐴𝐴(𝑛𝑛) de funções primitivas para o grupo AND. 𝑀𝑀(0, 0,𝐸𝐸3) = 0 ∈ 𝐶𝐶; 𝑀𝑀(0, 1,𝐸𝐸3) = 𝐸𝐸3 ∈ 𝑆𝑆; 𝑀𝑀(0,𝐸𝐸2,𝐸𝐸2) = 𝐸𝐸2 ∈ 𝑆𝑆 (27) 𝑀𝑀(0,𝐸𝐸2,𝐸𝐸3) = 𝑀𝑀(0,𝐸𝐸3,𝐸𝐸2) (28) 𝐸𝐸3 = 𝐸𝐸�2 ⟹ 𝑀𝑀(0,𝐸𝐸2,𝐸𝐸3) = 𝑀𝑀(0,𝐸𝐸2,𝐸𝐸�2) = 0 ∈ 𝐶𝐶 (29) 𝑝𝑝𝐴𝐴𝐴𝐴𝐴𝐴(𝑛𝑛) = � 2𝑛𝑛 2 �− 𝑛𝑛 = (2𝑛𝑛)! (2𝑛𝑛 − 2)! ∙ 2! − 𝑛𝑛 = 2𝑛𝑛 ∙ (2𝑛𝑛 − 1) ∙ (2𝑛𝑛 − 2)! (2𝑛𝑛 − 2)! ∙ 2 − 𝑛𝑛 = = 𝑛𝑛(2𝑛𝑛 − 1) − 𝑛𝑛 ⟹ 𝑝𝑝𝐴𝐴𝐴𝐴𝐴𝐴(𝑛𝑛) = 2𝑛𝑛2 − 2𝑛𝑛 (30) Para o grupo OR as funções primitivas assumem a forma 𝑀𝑀(1,𝐸𝐸2,𝐸𝐸3), onde 𝐸𝐸2,𝐸𝐸3 ≠ 0; 𝐸𝐸2 ,𝐸𝐸3 ≠ 1; 𝐸𝐸2 ≠ 𝐸𝐸3 e 𝐸𝐸2 ≠ 𝐸𝐸�3. Estas restrições garantem que não ocorram redundâncias como, por exemplo, as mostradas na Equação (31). Da mesma forma que no grupo AND, deve-se obter todas as combinações da forma {𝐸𝐸2, 𝐸𝐸3} que atendam às condições. Na Equação (32) é apresentada a justificativa do emprego da 44 combinação e não da permutação. Neste caso, também há uma quantidade de combinações de 2𝑛𝑛 elementos do grupo S, tomados 2 a 2, excluindo-se os 𝑛𝑛 casos nos quais tem-se 𝐸𝐸3 = 𝐸𝐸�2 , que conduziriam à primitiva 1 , conforme mostrado na Equação (33). Assim, a quantidade de funções primitivas 𝑝𝑝𝑂𝑂𝑂𝑂(𝑛𝑛)do grupo OR é apresentado na Equação (34). 𝑀𝑀(1, 0,𝐸𝐸3) = 𝐸𝐸3 ∈ 𝑆𝑆; 𝑀𝑀(1, 0,𝐸𝐸3) = 𝐸𝐸3 ∈ 𝑆𝑆; 𝑀𝑀(1,𝐸𝐸2,𝐸𝐸2) = 𝐸𝐸2 ∈ 𝑆𝑆 (31) 𝑀𝑀(1,𝐸𝐸2,𝐸𝐸3) = 𝑀𝑀(1,𝐸𝐸3,𝐸𝐸2) (32) 𝐸𝐸3 = 𝐸𝐸�2 ⟹ 𝑀𝑀(1,𝐸𝐸2,𝐸𝐸3) = 𝑀𝑀(1,𝐸𝐸2,𝐸𝐸�2) = 1 ∈ 𝐶𝐶 (33) 𝑝𝑝𝑂𝑂𝑂𝑂(𝑛𝑛) = � 2𝑛𝑛 2 � − 𝑛𝑛 = (2𝑛𝑛)! (2𝑛𝑛 − 2)! ∙ 2! − 𝑛𝑛 = 2𝑛𝑛 ∙ (2𝑛𝑛 − 1) ∙ (2𝑛𝑛 − 2)! (2𝑛𝑛 − 2)! ∙ 2 − 𝑛𝑛 = = 𝑛𝑛(2𝑛𝑛 − 1) − 𝑛𝑛 ⟹ 𝑝𝑝𝑂𝑂𝑂𝑂(𝑛𝑛) = 2𝑛𝑛2 − 2𝑛𝑛 (34) No grupo T as funções primitivas assumem o formato 𝑀𝑀(𝐸𝐸1, 𝐸𝐸2, 𝐸𝐸3), em que 𝐸𝐸1,𝐸𝐸2,𝐸𝐸3 ≠ 0, 1 ; 𝐸𝐸1,𝐸𝐸2 ≠ 𝐸𝐸3,𝐸𝐸�3 e 𝐸𝐸1 ≠ 𝐸𝐸2,𝐸𝐸�2 . Tais restrições garantem que não ocorram redundâncias como, por exemplo, as mostradas na Equação (35). A quantidade de funções deste grupo é exatamente a quantidade de combinações da forma {𝐸𝐸1,𝐸𝐸2,𝐸𝐸3} que atendam às restrições. Deve-se obter todas as combinações dos 2𝑛𝑛 elementos do grupo S, tomados 3 a 3, excluindo-se os 𝑛𝑛(2𝑛𝑛 − 2) casos de combinações do tipo {𝐸𝐸1, 𝐸𝐸�1, 𝐸𝐸3} , nas quais 𝐸𝐸2 = 𝐸𝐸�1 , que violam as restrições e produzem funções do grupo S, conforme é mostrado na Equação (36). Assim, na equação (37) é apresentada a quantidade de funções primitivas 𝑝𝑝𝑇𝑇(𝑛𝑛) para o grupo T. 𝑀𝑀(0, 𝐸𝐸2 , 𝐸𝐸3) ∈ 𝐴𝐴𝐴𝐴𝐷𝐷; 𝑀𝑀(1, 𝐸𝐸2, 𝐸𝐸3) ∈ 𝑂𝑂𝑂𝑂; 𝑀𝑀(𝐸𝐸1, 𝐸𝐸2, 𝐸𝐸2) = 𝐸𝐸2 ∈ 𝑆𝑆 (35) 45 𝐸𝐸2 = 𝐸𝐸�1 ⟹ 𝑀𝑀(𝐸𝐸1,𝐸𝐸2,𝐸𝐸3) = 𝑀𝑀(𝐸𝐸1,𝐸𝐸�1,𝐸𝐸3) = 𝐸𝐸3 ∈ 𝑆𝑆 (36) 𝑝𝑝𝑇𝑇(𝑛𝑛) = � 2𝑛𝑛 3 � − 𝑛𝑛(2𝑛𝑛 − 2) = (2𝑛𝑛)! (2𝑛𝑛 − 3)! ∙ 3! − 2𝑛𝑛2 + 2𝑛𝑛 = 2𝑛𝑛(2𝑛𝑛 − 1)(2𝑛𝑛 − 2)(2𝑛𝑛 − 3)! (2𝑛𝑛 − 3)! ∙ 3 ∙ 2 −2𝑛𝑛2 + 2𝑛𝑛 = 𝑛𝑛(2𝑛𝑛 − 1)(2𝑛𝑛 − 2) 3 − 2𝑛𝑛2 + 2𝑛𝑛 = 4 3𝑛𝑛 3 − 2𝑛𝑛2 + 2 3𝑛𝑛 − 2𝑛𝑛2 + 2𝑛𝑛 ⟹ ⟹ 𝑝𝑝𝑇𝑇(𝑛𝑛) = 4 3𝑛𝑛 3 − 4𝑛𝑛2 + 8 3𝑛𝑛 (37) 4.2 QUANTIDADE TOTAL DE FUNÇÕES PRIMITIVAS Somando-se todas as quantidades de primitivas dos grupos C, S, AND, OR e T, obtém-se a quantidade total de funções majoritárias primitivas de 3 entradas e 𝑛𝑛 variáveis, conforme é apresentado na Equação (38). Na Tabela 12 são mostradas todas as quantidades de primitivas para todos os grupos. 𝑝𝑝(𝑛𝑛) = 𝑝𝑝𝐶𝐶(𝑛𝑛) + 𝑝𝑝𝑆𝑆(𝑛𝑛) + 𝑝𝑝𝐴𝐴𝐴𝐴𝐴𝐴(𝑛𝑛) + 𝑝𝑝𝑂𝑂𝑂𝑂(𝑛𝑛) + 𝑝𝑝𝑇𝑇(𝑛𝑛) = 2 + 2𝑛𝑛 + (2𝑛𝑛2 − 2𝑛𝑛) + +(2𝑛𝑛2 − 2𝑛𝑛) + 4 3𝑛𝑛 3 − 4𝑛𝑛2 + 8 3𝑛𝑛 ⟹ 𝑝𝑝(𝑛𝑛) = 4 3𝑛𝑛 3 + 2 3𝑛𝑛 + 2 (38) Como pode ser observado na Equação (38), a função que determina a quantidade de primitivas é de natureza polinomial. Trata-se de uma função polinomial de grau 3, com ausência do termo de grau 2. Este polinômio possui um zero real 𝑛𝑛 = −1, permitindo decompor 𝑝𝑝(𝑛𝑛) na forma fatorada mostrada na equação (39). Assim, pode-se encontrar os outros dois zeros, que são complexos conjugados: 𝑛𝑛 = 1/2− �√5/2�𝑗𝑗 e 𝑛𝑛 = 1/2 + �√5/2�𝑗𝑗. O gráfico da função 𝑝𝑝(𝑛𝑛) é apresentado na Figura 10. 46 Tabela 12 – Quantidade de primitivas de cada grupo para uma função majoritária com 3 entradas e 𝑛𝑛 variáveis. GRUPO QUANTIDADE DE PRIMITIVAS C 2 S 2n AND 2n2 - 2n OR 2n2 - 2n T 4/3 n3 - 4n2 + 8/3 n TOTAL 4/3 n3 + 2/3 n + 2 Fonte: Elaboração do próprio autor. 𝑝𝑝(𝑛𝑛) = 4 3 𝑛𝑛3 + 2 3 𝑛𝑛 + 2 = (𝑛𝑛 + 1)� 4 3 𝑛𝑛2 − 4 3 𝑛𝑛 + 2� (39) Figura 10 – Gráfico da função polinomial que representa 𝑝𝑝(𝑛𝑛). Fonte: Elaboração do próprio autor. n p(n) 47 Pode-se analisar o crescimento da função 𝑝𝑝(𝑛𝑛) a partir de sua derivada primeira 𝑝𝑝′(𝑛𝑛), que é a função quadrática indicada na Equação (40). O gráfico de 𝑝𝑝′(𝑛𝑛) é mostrado na Figura 11. Nota-se no gráfico que 𝑝𝑝′(𝑛𝑛) < 0,∀ 𝑛𝑛 < 0 e que 𝑝𝑝′(𝑛𝑛) ≥ 0,∀ 𝑛𝑛 ≥ 0. Como para o caso das funções majoritárias sempre ocorre 𝑛𝑛 ≥ 3, tem-se que, para o domínio de aplicação, 𝑝𝑝(𝑛𝑛) será uma função sempre crescente e localizada no primeiro quadrante. Na Tabela 13 são apresentadas as quantidades de funções primitivas para até 126 variáveis e na Figura 12 é mostrado o gráfico correspondente a este intervalo. 𝑝𝑝(𝑛𝑛) = 4 3 𝑛𝑛3 + 2 3 𝑛𝑛 + 2 ⟹ 𝑝𝑝′(𝑛𝑛) = 4𝑛𝑛2 + 2 3 (40) Figura 11 – Gráfico da função 𝑝𝑝′(𝑛𝑛) do crescimento de 𝑝𝑝(𝑛𝑛). Fonte: Elaboração do próprio autor. Deve-se notar que o domínio de interesse de aplicação da função 𝑝𝑝(𝑛𝑛) é {𝑛𝑛 ∈ ℕ:𝑛𝑛 ≥ 3}. Ou seja, 𝑛𝑛 é um número natural maior ou igual a 3. Na Figura 13 é apresentado um gráfico para 3 ≤ 𝑛𝑛 ≤ 32 variáveis. Sendo assim, como pode-se observar, a região de interesse da função é do tipo discreta e crescente. Deve-se observar que todos os 30 pontos deste gráfico discreto também estão presentes nos gráficos da função polinomial das Figuras 10 e 12. p’(n) n 48 Tabela 13 – Quantidade de funções primitivas para até 126 variáveis. n p(n) n p(n) n p(n) n p(n) 3 40 34 52430 65 366212 96 1179714 4 90 35 57192 66 383374 97 1216964 5 172 36 62234 67 401064 98 1254990 6 294 37 67564 68 419290 99 1293800 7 464 38 73190 69 438060 100 1333402 8 690 39 79120 70 457382 101 1373804 9 980 40 85362 71 477264 102 1415014 10 1342 41 91924 72 497714 103 1457040 11 1784 42 98814 73 518740 104 1499890 12 2314 43 106040 74 540350 105 1543572 13 2940 44 113610 75 562552 106 1588094 14 3670 45 121532 76 585354 107 1633464 15 4512 46 129814 77 608764 108 1679690 16 5474 47 138464 78 632790 109 1726780 17 6564 48 147490 79 657440 110 1774742 18 7790 49 156900 80 682722 111 1823584 19 9160 50 166702 81 708644 112 1873314 20 10682 51 176904 82 735214 113 1923940 21 12364 52 187514 83 762440 114 1975470 22 14214 53 198540 84 790330 115 2027912 23 16240 54 209990 85 818892 116 2081274 24 18450 55 221872 86 848134 117 2135564 25 20852 56 234194 87 878064 118 2190790 26 23454 57 246964 88 908690 119 2246960 27 26264 58 260190 89 940020 120 2304082 28 29290 59 273880 90 972062 121 2362164 29 32540 60 288042 91 1004824 122 2421214 30 36022 61 302684 92 1038314 123 2481240 31 39744 62 317814 93 1072540 124 2542250 32 43714 63 333440 94 1107510 125 2604252 33 47940 64 349570 95 1143232 126 2667254 Fonte: Elaboração do próprio autor. 49 Figura 12 – Gráfico da função 𝑝𝑝(𝑛𝑛) abrangendo 126 casos. Fonte: Elaboração do próprio autor. Figura 13 – Quantidade de primitivas para 𝑛𝑛 variando de 3 a 32. Fonte: Elaboração do próprio autor. p(n) n 50 4.3 REPRESENTATIVIDADE DAS FUNÇÕES PRIMITIVAS Analisando a Tabela 13, pode-se observar a evolução da quantidade 𝑝𝑝(𝑛𝑛) de funções majoritárias primitivas com o aumento da quantidade 𝑛𝑛 de variáveis. Para realizar uma comparação efetiva entre a quantidade de primitivas dentro do universo de todas as 2(2𝑛𝑛) funções existentes, pode-se definir a relação de proporção 𝑟𝑟 indicada pela Equação (41), que também representa uma função de 𝑛𝑛. 𝑟𝑟(𝑛𝑛) = 𝑝𝑝(𝑛𝑛) 2(2𝑛𝑛) ⟹ 𝑟𝑟(𝑛𝑛) = 4 3 𝑛𝑛3 + 2 3 𝑛𝑛 + 2 2(2𝑛𝑛) (41) Pesquisas atuais nos processos de otimização de funções majoritárias ainda contemplam menos de 10 variáveis, inclusive pela enorme quantidade de funções possíveis com esta quantidade. Para ilustrar matematicamente este estudo, foi realizada a análise quantitativa de todas as funções possíveis com até 32 variáveis, obtendo-se os dados apresentados na Tabela 14. Como pode ser observado, com o aumento do número de variáveis 𝑛𝑛, a quantidade de funções possíveis cresce muito mais rapidamente que a quantidade de primitivas. De fato, comparando a derivada primeira de 𝑝𝑝(𝑛𝑛) que foi apresentada na Equação (40) com a derivada primeira mostrada na Equação (42), observa-se que 𝑓𝑓 é amplamente mais crescente que 𝑝𝑝. 𝑓𝑓(𝑛𝑛) = 2(2𝑛𝑛) ⟹ 𝑓𝑓′(𝑛𝑛) = (𝑙𝑙𝑛𝑛22) ∙ 2(2𝑛𝑛+𝑛𝑛) (42) Como consequência, observa-se que a proporção 𝑟𝑟 é altamente decrescente. Pode-se mostrar que o valor 𝑟𝑟 aproxima-se de zero com o crescimento de 𝑛𝑛 calculando o limite indicado na Equação (43). Quando o limite da relação entre duas funções deriváveis leva a uma indeterminação, este limite será o limite da relação entre as derivadas destas funções, se este limite existir (LEITHOLD, 1994). Este é um 51 dos Teoremas de L’Hôpital e foi aplicado para o cálculo do limite de 𝑟𝑟 quando 𝑛𝑛 → +∞. Derivou-se as funções por 4 ordens até eliminar-se a indeterminação. Para não sobrecarregar o texto, as derivadas de 2(2𝑛𝑛) foram deixadas implícitas. Tabela 14 – Quantidade de primitivas, quantidade de funções e relação de proporção para 𝑛𝑛 variando de 3 a 32 variáveis. VARIÁVEIS PRIMITIVAS FUNÇÕES PROPORÇÃO n = 3 40 256 0,15625000 n = 4 90 65536 0,00137329 n = 5 172 4294967296 0,00000004 n = 6 294 1,84467 ∙ 1019 0,00000000 n = 7 464 3,40282 ∙ 1038 0,00000000 n = 8 690 1,15792 ∙ 1077 0,00000000 n = 9 980 1,34078 ∙ 10154 0,00000000 n = 10 1342 1,79769 ∙ 10308 0,00000000 n = 11 1784 3,23170 ∙ 10616 0,00000000 n = 12 2314 1,04439 ∙ 101233 0,00000000 n = 13 2940 1,09078 ∙ 102466 0,00000000 n = 14 3670 1,18973 ∙ 104932 0,00000000 n = 15 4512 1,41546 ∙ 109864 0,00000000 n = 16 5474 2,00353 ∙ 1019728 0,00000000 n = 17 6564 4,01412 ∙ 1039456 0,00000000 n = 18 7790 1,61132 ∙ 1078913 0,00000000 n = 19 9160 2,59634 ∙ 10157826 0,00000000 n = 20 10682 6,74098 ∙ 10315652 0,00000000 n = 21 12364 4,54408 ∙ 10631305 0,00000000 n = 22 14214 2,06486 ∙ 101262610 0,00000000 n = 23 16240 4,26366 ∙ 102525220 0,00000000 n = 24 18450 1,81788 ∙ 105050441 0,00000000 n = 25 20852 3,30468 ∙ 1010100883 0,00000000 n = 26 23454 1,09209 ∙ 1020201766 0,00000000 n = 27 26264 1,19267 ∙ 1040403532 0,00000000 n = 28 29290 1,42246 ∙ 1080807064 0,00000000 n = 29 32540 2,02339 ∙ 10161614128 0,00000000 n = 30 36022 4,09410 ∙ 10323228257 0,00000000 52 n = 31 39744 1,67616 ∙ 10646456514 0,00000000 n = 32 43714 2,80953 ∙ 101292913028 0,00000000 Fonte: Elaboração do próprio autor. lim 𝑛𝑛→+∞ 𝑟𝑟(𝑛𝑛) = lim 𝑛𝑛→+∞ 𝑝𝑝(𝑛𝑛) 𝑓𝑓(𝑛𝑛) = lim 𝑛𝑛→+∞ 4 3𝑛𝑛 3 + 2 3𝑛𝑛 + 2 2(2𝑛𝑛) = lim 𝑛𝑛→+∞ 4𝑛𝑛2 + 2 3 𝑑𝑑 𝑑𝑑𝑛𝑛 [2(2𝑛𝑛)] = lim 𝑛𝑛→+∞ 8𝑛𝑛 𝑑𝑑 𝑑𝑑𝑛𝑛2 [2(2𝑛𝑛)] = lim 𝑛𝑛→+∞ 8 𝑑𝑑 𝑑𝑑𝑛𝑛3 [2(2𝑛𝑛)] = lim 𝑛𝑛→+∞ 0 𝑑𝑑 𝑑𝑑𝑛𝑛4 [2(2𝑛𝑛)] ; lim 𝑛𝑛→+∞ 0 = 0; lim 𝑛𝑛→+∞ 2(2𝑛𝑛) = +∞⟹ ⟹ lim 𝑛𝑛→+∞ 𝑑𝑑 𝑑𝑑𝑛𝑛4 �2(2𝑛𝑛)� = +∞ ∴ lim 𝑛𝑛→+∞ 𝑟𝑟(𝑛𝑛) = 0 (43) Deste modo, observa-se que, com o aumento do número 𝑛𝑛 de variáveis, a quantidade 𝑝𝑝(𝑛𝑛) de funções primitivas torna-se desprezível se comparada à quantidade total 𝑓𝑓(𝑛𝑛) de funções. Este fato contribui para que se continue investindo em pesquisas que se utilizem das funções majoritárias primitivas nos métodos de otimização de funções. 53 5 OTIMIZAÇÃO DE FUNÇÕES MAJORITÁRIAS Considere uma função arbitrária 𝐹𝐹 = 𝑀𝑀(𝐴𝐴,𝐵𝐵� ,𝑀𝑀�(1,𝐴𝐴,𝐶𝐶̅)) . O circuito lógico combinacional majoritário desta função é mostrado na figura 14. Utilizando os teoremas da álgebra booleana e da lógica majoritária, podemos encontrar a função booleana correspondente, conforme é demonstrado na Equação (44). A partir da função booleana, monta-se a tabela-verdade apresentada na Tabela 15. A matriz transposta do vetor coluna de 𝐹𝐹 fornece a forma vetorial da função, mostrada na Equação (45). Figura 14 – Circuito lógico combinacional da função 𝐹𝐹. Fonte: Elaboração do próprio autor. 𝐹𝐹 = 𝑀𝑀�𝐴𝐴,𝐵𝐵� ,𝑀𝑀�(1,𝐴𝐴,𝐶𝐶̅)� = 𝑀𝑀�𝐴𝐴,𝐵𝐵� ,𝑀𝑀(0, �̅�𝐴,𝐶𝐶)� = 𝑀𝑀(𝐴𝐴,𝐵𝐵� ,𝐴𝐴 ∙ 𝐶𝐶̅) = 𝐴𝐴 ∙ 𝐵𝐵� + 𝐴𝐴 ∙ (𝐴𝐴 ∙ 𝐶𝐶̅) + +𝐵𝐵� ∙ (𝐴𝐴 ∙ 𝐶𝐶̅) = 𝐴𝐴 ∙ 𝐵𝐵� + (𝐴𝐴 ∙ 𝐴𝐴) ∙ 𝐶𝐶̅ + (𝐴𝐴 ∙ 𝐵𝐵�) ∙ 𝐶𝐶̅ = 𝐴𝐴 ∙ 𝐵𝐵� + (𝐴𝐴 ∙ 𝐵𝐵�) ∙ 𝐶𝐶̅ + 𝐴𝐴 ∙ 𝐶𝐶̅ = = 𝐴𝐴 ∙ 𝐵𝐵� ∙ (1 + 𝐶𝐶̅) + 𝐴𝐴 ∙ 𝐶𝐶̅ = 𝐴𝐴 ∙ 𝐵𝐵� ∙ 1 + 𝐴𝐴 ∙ 𝐶𝐶̅ ⟹ 𝐹𝐹 = 𝐴𝐴 ∙ 𝐵𝐵� + 𝐴𝐴 ∙ 𝐶𝐶̅ (44) 𝐹𝐹 = [0 0 0 0 1 1 1 0] = 𝑀𝑀(𝐴𝐴,𝐵𝐵� ,𝑀𝑀�(1,𝐴𝐴,𝐶𝐶̅)) (45) 54 Tabela 15 – Tabela-verdade da função 𝐹𝐹. A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Fonte: Elaboração do próprio autor. Nesta seção e nas anteriores, mostrou-se como se obter uma função booleana a partir de uma função majoritária. O procedimento inverso é complexo, justificando as pesquisas neste contexto. São necessárias outras metodologias para se partir de uma tabela-verdade e chegar a uma função majoritária correspondente e que seja otimizada. Apresenta-se na próxima seção uma forma de tratar esta situação como um problema de programação linear inteira binária. 5.1 PROBLEMA DE PROGRAMAÇÃO LINEAR Um problema de programação linear tem por finalidade otimizar uma função linear, encontrando seu valor máximo ou seu valor mínimo. Um conjunto formado por igualdades lineares e, ou, desigualdades lineares restringem e orientam a busca pela solução (BAZARAA; JARVIS; SHERALI, 2010). Para um caso geral de minimização, na Equação (46) é apresentada uma forma padronizada da descrição de um problema de programação linear. A função linear 𝑧𝑧 é chamada de função objetivo e os coeficientes 𝑐𝑐𝑖𝑖 são os coeficientes de custo da função objetivo. As 𝑛𝑛 variáveis 𝑥𝑥𝑖𝑖 são as variáveis de decisão e as 𝑚𝑚 + 𝑛𝑛 inequações lineares são as restrições. É no conjunto de restrições que se 55 estabelece o conjunto domínio de validade do problema. A função objetivo estabelece o conjunto imagem do problema. O valor mais adequado dentro da imagem indicará a melhor solução do domínio para o problema. Para 0 ≤ 𝑖𝑖 ≤ 𝑚𝑚 e 0 ≤ 𝑗𝑗 ≤ 𝑛𝑛 , os coeficientes 𝑐𝑐𝑖𝑖 , 𝑎𝑎𝑖𝑖𝑖𝑖 e 𝑏𝑏𝑖𝑖 são quaisquer números reais, decorrentes da natureza do problema analisado. As restrições de igualdades podem ser obtidas das desigualdades utilizando-se variáveis de folga. ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 𝑚𝑚𝑖𝑖𝑛𝑛 𝑧𝑧 = �𝑐𝑐𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 𝑠𝑠𝑠𝑠𝑗𝑗𝑒𝑒𝑖𝑖𝑠𝑠𝑠𝑠 𝑎𝑎: �𝑎𝑎1𝑖𝑖𝑥𝑥𝑖𝑖 = 𝑏𝑏1 𝑛𝑛 𝑖𝑖=1 �𝑎𝑎2𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 = 𝑏𝑏2 �𝑎𝑎3𝑖𝑖𝑥𝑥𝑖𝑖 = 𝑏𝑏3 𝑛𝑛 𝑖𝑖=1 ⋮ �𝑎𝑎𝑚𝑚𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 = 𝑏𝑏𝑚𝑚 𝑥𝑥𝑖𝑖 ≥ 0,∀ 1 ≤ 𝑗𝑗 ≤ 𝑛𝑛 (46) Um PLI (Problema de Programação Linear Inteira) é um problema de programação linear onde ao menos uma das variáveis de decisão deve ser um número inteiro. Quando todas as variáveis estão restritas aos valores 0 ou 1, então tem-se um PLI do tipo 0−1 ou binário (CHEN; BATSON; DANG, 2010). A estrutura mostrada na Equação (47) representa uma modelagem clássica deste problema. Tem-se 𝑐𝑐𝑖𝑖 ∈ ℤ+;𝑎𝑎𝑖𝑖𝑖𝑖 , 𝑏𝑏𝑖𝑖 ∈ ℤ; 0 ≤ 𝑖𝑖 ≤ 𝑚𝑚 e 0 ≤ 𝑗𝑗 ≤ 𝑛𝑛. 56 ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 𝑚𝑚𝑖𝑖𝑛𝑛 𝑧𝑧 = �𝑐𝑐𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 𝑠𝑠𝑠𝑠𝑗𝑗𝑒𝑒𝑖𝑖𝑠𝑠𝑠𝑠 𝑎𝑎: �𝑎𝑎1𝑖𝑖𝑥𝑥𝑖𝑖 = 𝑏𝑏1 𝑛𝑛 𝑖𝑖=1 �𝑎𝑎2𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 = 𝑏𝑏2 �𝑎𝑎3𝑖𝑖𝑥𝑥𝑖𝑖 = 𝑏𝑏3 𝑛𝑛 𝑖𝑖=1 ⋮ �𝑎𝑎𝑚𝑚𝑖𝑖𝑥𝑥𝑖𝑖 𝑛𝑛 𝑖𝑖=1 = 𝑏𝑏𝑚𝑚 𝑥𝑥𝑖𝑖 ∈ {0, 1},∀ 1 ≤ 𝑗𝑗 ≤ 𝑛𝑛 𝑎𝑎𝑖𝑖𝑖𝑖 , 𝑏𝑏𝑖𝑖 ∈ ℤ (47) 5.2 PROPRIEDADES DAS OPERAÇÕES AND e OR Como descrito no Capítulo 2, uma função booleana pode ser biunivocamente identificada por seus mintermos. Portanto, dado um conjunto de mintermos, pode-se representar uma única função booleana e, da mesma forma, dada uma função booleana, esta representa um único conjunto de mintermos. Deste modo, a forma vetorial de uma função contém seus mintermos muito bem posicionados e identificados. Considere duas funções booleanas 𝐹𝐹 e 𝐺𝐺, representadas pela soma de seus mintermos ou, simplesmente, representadas por seus mintermos indicados em suas formas vetoriais. A operação AND entre essas duas funções fornece uma função produto cujos mintermos são exatamente os mintermos comuns às duas funções. A operação OR entre essas duas funções fornece uma função soma cujos mintermos são exatamente todos os mintermos contidos nas duas funções. Esta propriedade pode ser visualizada no diagrama de conjuntos apresentado na Figura 15, onde 𝐹𝐹 e 𝐺𝐺 são duas funções, subconjuntos do conjunto de todas as 2𝑛𝑛 funções possíveis de 𝑛𝑛 variáveis. O conjunto de mintermos da função (𝐹𝐹 ∙ 𝐺𝐺) é a 57 intersecção entre os conjuntos de mintermos das funções 𝐹𝐹 e 𝐺𝐺, conforme é mostrado na Equação (48), sendo 𝑚𝑚𝑋𝑋 o conjunto de mintermos da função 𝑋𝑋. O conjunto dos mintermos da função (𝐹𝐹 + 𝐺𝐺) é a reunião entre os conjuntos de mintermos de 𝐹𝐹 e 𝐺𝐺, conforme é mostrado na Equação (49). Figura 15 – Diagrama de conjuntos representando as operações AND e OR. Fonte: Elaboração do próprio autor. 𝑚𝑚(𝐹𝐹∙𝐺𝐺) = 𝑚𝑚𝐹𝐹 ⋂ 𝑚𝑚𝐺𝐺 (48) 𝑚𝑚(𝐹𝐹+𝐺𝐺) = 𝑚𝑚𝐹𝐹 ⋃ 𝑚𝑚𝐺𝐺 (49) As mesmas propriedades das operações AND e OR descritas para os conjuntos de mintermos de duas funções booleanas se aplicam também, individualmente, a cada mintermo de uma posição correspondente. Para ilustrar estas propriedades, considere as funções 𝐹𝐹 e 𝐺𝐺 arbitrárias pertencentes ao conjunto de funções de 4 variáveis e descritas por suas formas vetoriais indicadas na Equação (50). A constante 1 indica a presença do mintermo da posição correspondente e a constante 0 representa a ausência do mintermo. A função (𝐹𝐹 ∙ 𝐺𝐺) pode ser obtida pelo produto dos mintermos de cada posição, conforme é ilustrado na Figura 16, de modo que a função resultante contém apenas os mintermos que coexistem nas funções 𝐹𝐹 e 𝐺𝐺. A função (𝐹𝐹 + 𝐺𝐺) pode ser obtida 58 pela soma dos mintermos de cada posição, conforme é ilustrado na Figura 17, de modo que a função resultante contém todos os mintermos das funções 𝐹𝐹 e 𝐺𝐺. Na Equação (51) são mostradas as formas vetoriais das funções resultantes. 𝐹𝐹 = [1 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1] 𝑒𝑒 𝐺𝐺 = [1 0 0 1 1 1 1 0 0 0 1 1 1 0 1 1 ] (50) Figura 16 – Diagrama de mintermos do produto das funções 𝐹𝐹 e 𝐺𝐺. Fonte: Elaboração do próprio autor. Figura 17 – Diagrama de mintermos da soma das funções 𝐹𝐹 e 𝐺𝐺. Fonte: Elaboração do próprio autor. 𝐹𝐹 ∙ 𝐺𝐺 = [1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1] 𝑒𝑒 𝐹𝐹 + 𝐺𝐺 = [1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1] (51) 59 5.2 NÍVEIS DAS FUNÇÕES MAJORITÁRIAS Quando se desenvolve um método para converter uma função booleana em sua forma majoritária tem-se por objetivo encontrar uma função ou composição de funções majoritárias onde os argumentos sejam funções primitivas. Entenda-se que os elementos 𝑋𝑋 , 𝑌𝑌 e 𝑍𝑍 são os argumentos da função majoritária 𝑀𝑀(𝑋𝑋,𝑌𝑌,𝑍𝑍) . Na pesquisa desenvolvida propõe-se uma metodologia capaz de obter funções majoritárias de várias variáveis e com até dois níveis de composição. Na Tabela 16 são apresentados exemplos de funções majoritárias de vários níveis. Tabela 16 – Exemplificação dos níveis de funções majoritárias. NÍVEIS EXEMPLO 0 A 1 M(0, A, B) 2 M(A, B, M(1, B, C̅)) 3 M(1, M̅(A, B, C), M(0, A, M(D, E, F))) 4 M(A, B, M(0, C̅, M(1, M(1, D, E), M(0, E, F)))) 5 M(0, A, M(A, B, M(1, C, M(1, M(1, D, E), M(1, F, A̅))))) Fonte: Elaboração do próprio autor. A quantidade de níveis de uma função majoritária está vinculada ao grau de sua composição. Por exemplo, a função de 5 níveis apresentada na Tabela 16 provém de uma composição quíntupla da função majoritária, conforme é mostrado na Equação (52). De forma análoga, a quantidade de níveis é identificada num circuito pela quantidade máxima de portas lógicas majoritárias conectadas em série. Na Figura 18 ilustra-se o circuito lógico combinacional da função de 5 níveis da Tabela 16. Como pode ser observado, há dois caminhos em série com 5 portas lógicas. 𝑀𝑀5(𝑋𝑋,𝑌𝑌,𝑍𝑍) = 𝑀𝑀 ∘𝑀𝑀 ∘𝑀𝑀 ∘ 𝑀𝑀 ∘ 𝑀𝑀(𝑋𝑋,𝑌𝑌,𝑍𝑍) (52) 60 Figura 18 – Circuito lógico combinacional majoritário de 5 níveis. Fonte: Elaboração do próprio autor. Nesta pesquisa foram abordadas apenas funções com até 2 níveis de composição. Funções majoritárias com 0 nível correspondem às funções primitivas dos grupos C e S. Todas as funções de 1 nível referem-se às funções primitivas dos grupos AND, OR e T. Seja 𝐹𝐹 uma função de 𝑛𝑛 variáveis que possa ser representada por 2 níveis na forma majoritária. Assim, 𝐹𝐹 assume a forma indicada na Equação (53), que é uma aplicação direta da Equação (15). 𝑓𝑓𝑘𝑘, com 0 ≤ 𝑘𝑘 ≤ 2𝑛𝑛−1 representa todos elementos da forma vetorial de 𝐹𝐹 . 𝑃𝑃𝑣𝑣 , 𝑃𝑃𝑠𝑠 e 𝑃𝑃𝑡𝑡 são funções majoritárias primitivas distintas, com 1 ≤ 𝑟𝑟, 𝑠𝑠, 𝑠𝑠 ≤ 𝑝𝑝(𝑛𝑛) e 𝑝𝑝(𝑛𝑛) é a quantidade de primitivas para funções de 𝑛𝑛 variáveis. 𝐹𝐹 = [𝑓𝑓0, 𝑓𝑓1, … ,𝑓𝑓2𝑛𝑛−2, 𝑓𝑓2𝑛𝑛−1] = 𝑀𝑀(𝑃𝑃𝑣𝑣 ,𝑃𝑃𝑠𝑠,𝑃𝑃𝑡𝑡) = 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑠𝑠 + 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑡𝑡 + 𝑃𝑃𝑠𝑠 ∙ 𝑃𝑃𝑡𝑡 (53) 5.4 RESTRIÇÕES PARA O PLI BINÁRIO Uma análise da Equação (53) vinculada ao que foi descrito na Seção 5.2 permite concluir que todos os mintermos da função [𝑓𝑓0,𝑓𝑓1, … ,𝑓𝑓2𝑛𝑛−2 ,𝑓𝑓2𝑛𝑛−1] devem ser os mesmos da função 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑠𝑠 + 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑡𝑡 + 𝑃𝑃𝑠𝑠 ∙ 𝑃𝑃𝑡𝑡 e, consequentemente, devem ser os mesmos mintermos da função 𝑀𝑀(𝑃𝑃𝑣𝑣 ,𝑃𝑃𝑠𝑠,𝑃𝑃𝑡𝑡) . Com base nestas observações, demonstra-se que é possível formular o processo de obtenção de funções majoritárias de 2 níveis como um PLI binário, onde as 𝑝𝑝(𝑛𝑛) variáveis binárias referem-se a presença ou não das 𝑝𝑝(𝑛𝑛) primitivas na função 𝑀𝑀(𝑃𝑃𝑣𝑣 ,𝑃𝑃𝑠𝑠,𝑃𝑃𝑡𝑡). 61 Se a função 𝐹𝐹 é composta por um mintermo na posição 𝑘𝑘, ou seja, 𝑓𝑓𝑘𝑘 = 1, então na mesma posição 𝑘𝑘 a função 𝑀𝑀(𝑃𝑃𝑣𝑣 ,𝑃𝑃𝑠𝑠,𝑃𝑃𝑡𝑡) também possui este mintermo. Desta forma, ao menos duas das primitivas devem assumir o valor 1 na posição 𝑘𝑘 de modo que a soma de produtos 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑠𝑠 + 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑡𝑡 + 𝑃𝑃𝑠𝑠 ∙ 𝑃𝑃𝑡𝑡 assuma o valor 1. Sendo assim, a soma de todas as variáveis relativas às funções primitivas com valor 1 na posição 𝑘𝑘 deve ser maior ou igual a 2. Esta modalidade de restrição é ilustrada na Equação (54), onde tem-se 1 ≤ 𝑖𝑖 ≤ 2𝑛𝑛. 𝑎𝑎𝑖𝑖1𝑥𝑥1 + 𝑎𝑎𝑖𝑖2𝑥𝑥2 + 𝑎𝑎𝑖𝑖3𝑥𝑥3 + ⋯+ 𝑎𝑎𝑖𝑖𝑖𝑖𝑥𝑥𝑖𝑖 + ⋯+ 𝑎𝑎𝑖𝑖𝑖𝑖(𝑛𝑛)𝑥𝑥𝑖𝑖(𝑛𝑛) ≥ 2 (54) Se a função 𝐹𝐹 não contém o mintermo da posição 𝑘𝑘, ou seja, 𝑓𝑓𝑘𝑘 = 0, então na mesma posição 𝑘𝑘 a função 𝑀𝑀(𝑃𝑃𝑣𝑣 ,𝑃𝑃𝑠𝑠,𝑃𝑃𝑡𝑡) também não possui este mintermo. Desta forma, apenas uma das primitivas pode assumir o valor 1 na posição 𝑘𝑘 de modo que a soma de produtos 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑠𝑠 + 𝑃𝑃𝑣𝑣 ∙ 𝑃𝑃𝑡𝑡 + 𝑃𝑃𝑠𝑠 ∙ 𝑃𝑃𝑡𝑡 assuma o valor 0. Sendo assim, a soma de todas as variáveis relativas às funções primitivas com valor 0 na posição 𝑘𝑘 deve ser menor ou igual a 1. Esta modalidade de restrição é ilustrada na Equação (55), onde tem-se 1 ≤ 𝑖𝑖 ≤ 2𝑛𝑛. Portanto, cada presença do elemento 1 na forma vetorial da função produz uma restrição do tipo desigualdade “≥ 2" e cada presença do elemento 0 na forma vetorial da função produz uma restrição do tipo desigualdade “≤ 1". Na Figura 19 é mostrado um diagrama da escolha dos dois padrões de restrições para a função arbitrária 𝐹𝐹 = [0 0 0 0 1 0 1 1]. 𝑎𝑎𝑖𝑖1𝑥𝑥1 + 𝑎𝑎𝑖𝑖2𝑥𝑥2 + 𝑎𝑎𝑖𝑖3𝑥𝑥3 + ⋯+ 𝑎𝑎𝑖𝑖𝑖𝑖𝑥𝑥𝑖𝑖 + ⋯+ 𝑎𝑎𝑖𝑖𝑖𝑖(𝑛𝑛)𝑥𝑥𝑖𝑖(𝑛𝑛) ≤ 1 (55) 62 Figura 19 – Distribuição das restrições numa função arbitrária. Fonte: Elaboração do próprio autor. Seja o exemplo de otimizar a função de 3 variáveis 𝐹𝐹 = �̅�𝐴 ∙ 𝐶𝐶 + 𝐵𝐵 ∙ 𝐶𝐶 , cuja forma vetorial é [0 0 0 0 1 0 1 1]. A solução majoritária otimizada para 𝐹𝐹 é mostrada na Equação (56). É uma função de 2 níveis e tendo 3 funções majoritárias primitivas como argumentos. Na Figura 20 são mostrados os mapeamentos dos mintermos destas primitivas. Na Figura 21 são apresentadas as operações AND entre as primitivas, duas a duas, e na Figura 22 é mostrado o resultado da operação OR entre as 3 operações AND. Observe que o resultado obtido é exatamente a forma vetorial inicial do problema. 𝐹𝐹 = �̅�𝐴 ∙ 𝐶𝐶 + 𝐵𝐵 ∙ 𝐶𝐶 = [0 0 0 0 1 0 1 1] = 𝑀𝑀(𝐶𝐶, �̅�𝐴,𝑀𝑀(0,𝐵𝐵,𝐶𝐶)) (56) Figura 20 – Conjunto de mintermos das 3 primitivas que compõem a função 𝐹𝐹. Fonte: Elaboração do próprio autor. 63 Figura 21 – Conjunto de mintermos dos produtos, duas a duas, das 3 primitivas que compõem a função 𝐹𝐹. Fonte: Elaboração do próprio autor. Figura 22 – Mapeamento de mintermos da função 𝐹𝐹. Fonte: Elaboração do próprio autor. Os coeficientes 𝑎𝑎𝑖𝑖𝑖𝑖 provenientes dos dois padrões de restrições apresentados nas Equações (54) e (55) assumem apenas os valores 1 ou 0, conforme a função primitiva 𝑃𝑃𝑖𝑖 contenha ou não contenha, respectivamente, o mintermo da posição 𝑘𝑘, associado ao elemento 𝑓𝑓𝑘𝑘 da função que se pretende converter. Para ilustrar o fato, na Tabela 17 são mostrados todos os coeficientes 𝑎𝑎𝑖𝑖𝑖𝑖 , 1 ≤ 𝑖𝑖 ≤ 8, para o PLI que representa as funções de 3 variáveis. Assim, para este PLI, cada uma das 8 restrições padrão será formada por 𝑝𝑝(𝑛𝑛) = 40 parcelas do tipo 𝑎𝑎𝑖𝑖𝑖𝑖𝑥𝑥𝑖𝑖. Cada coluna 𝑓𝑓𝑘𝑘 , 0 ≤ 𝑘𝑘 ≤ 7 da Tabela 17 representa os 40 coeficientes da i-ésima restrição do tipo “≥ 2” ou “≤ 1”. 64 Tabela 17 – Coeficientes 𝑎𝑎𝑖𝑖𝑖𝑖 para o PLI de funções com 3 variáveis. j f0 f1 f2 f3 f4 f5 f6 f7 j f0 f1 f2 f3 f4 f5 f6 f7 1 0 0 0 0 0 0 0 0 21 0 1 1 1 0 1 1 1 2 1 1 1 1 1 1 1 1 22 0 1 0 1 1 1 1 1 3 0 1 0 1 0 1 0 1 23 1 1 0 1 1 1 0 1 4 0 0 1 1 0 0 1 1 24 1 1 1 1 0 1 0 1 5 0 0 0 0 1 1 1 1 25 0 0 1 1 1 1 1 1 6 1 0 1 0 1 0 1 0 26 1 0 1 1 1 0 1 1 7 1 1 0 0 1 1 0 0 27 1 1 1 1 0 0 1 1 8 1 1 1 1 0 0 0 0 28 1 0 1 0 1 1 1 1 9 0 0 0 1 0 0 0 1 29 1 1 0 0 1 1 1 1 10 0 0 0 0 0 1 0 1 30 1 1 1 0 1 1 1 0 11 0 1 0 0 0 1 0 0 31 1 1 1 1 1 0 1 0 12 0 1 0 1 0 0 0 0 32 1 1 1 1 1 1 0 0 13 0 0 0 0 0 0 1 1 33 0 0 0 1 0 1 1 1 14 0 0 1 0 0 0 1 0 34 0 1 1 1 0 0 0 1 15 0 0 1 1 0 0 0 0 35 0 1 0 0 1 1 0 1 16 0 0 0 0 1 0 1 0 36 1 1 0 1 0 1 0 0 17 0 0 0 0 1 1 0 0 37 0 0 1 0 1 0 1 1 18 1 0 0 0 1 0 0 0 38 1 0 1 1 0 0 1 0 19 1 0 1 0 0 0 0 0 39 1 0 0 0 1 1 1 0 20 1 1 0 0 0 0 0 0 40 1 1 1 0 1 0 0 0 Fonte: Elaboração do próprio autor. Estas duas modalidades de restrições que foram apresentadas nas Equações (54) e (55) ainda permitem que, numa possível solução, menos de 3 primitivas sejam selecionadas (1 ou 2) e também que sejam selecionadas mais de 3 primitivas (4, por exemplo). No entanto, o modelo inicial do problema prevê exatamente a seleção de 3 funções primitivas. Deste modo, deve-se incluir uma restrição adicional determinando que a soma de todas as variáveis seja igual a 3, garantindo a execução correta do modelo do problema e que apenas 3 funções primitivas sejam selecionadas. Esta restrição é ilustrada na Equação (57). 65 𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 + ⋯+ 𝑥𝑥𝑖𝑖 + ⋯+ 𝑥𝑥𝑖𝑖(𝑛𝑛) = 3 (57) Naturalmente, como trata-se de um PLI binário, as variáveis 𝑥𝑥𝑖𝑖 só podem assumir os valores 0 ou 1, exigindo as restrições representadas pela Equação (58), que finalizam as restrições do problema. Deste modo, um PLI modelado para funções de 𝑛𝑛 variáveis possui 2𝑛𝑛 restrições de desigualdade (1 para cada um dos 2𝑛𝑛 elementos da forma vetorial, indicadas pelas Equações (54) e (55)), 1 restrição de igualdade (indicada pela Equação (57)) e 𝑝𝑝(𝑛𝑛) restrições binárias (1 para cada variável, indicadas pela Equação (58)). Portanto, a quantidade 𝑞𝑞𝑣𝑣(𝑛𝑛) de restrições para um PLI para funções de 𝑛𝑛 variáveis é representado pela Equação (59). 𝑥𝑥𝑖𝑖 ∈ {0, 1} ⟺ 0 ≤ 𝑥𝑥𝑖𝑖 ≤ 1 𝑒𝑒 𝑥𝑥𝑖𝑖 ∈ ℤ; ∀ 1 ≤ 𝑗𝑗 ≤ 𝑝𝑝(𝑛𝑛) (58) 𝑞𝑞𝑣𝑣(𝑛𝑛) = 2𝑛𝑛 + 𝑝𝑝(𝑛𝑛) + 1 (59) 5.5 FUNÇÃO OBJETIVO E PLI BINÁRIO COMPLETO A restrição indicada pela Equação (56) garante que, caso seja factível (tenha solução), o PLI selecione apenas 3 funções primitivas, ou seja, apenas 3 das 𝑝𝑝(𝑛𝑛) variáveis 𝑥𝑥𝑖𝑖 assumam o valor 1 e todas as outras [𝑝𝑝(𝑛𝑛)− 3] variáveis assumam o valor 0. A função objetivo constitui o elemento capaz de estabelecer a melhor solução dentre aquelas factíveis. Na modelagem em questão, trata-se de um caso de minimização, haja visto que se pretende projetar um circuito que tenha o menor volume físico com a melhor eficiência. Cada PLI minimiza uma função objetivo, cujo valor representa a soma de todos os custos das três funções primitivas utilizadas na composição de sua forma majoritária. Para quaisquer que sejam essas primitivas, foram estabelecidas sete 66 variações de custo, relativas à presença de constantes, uso de porta majoritária, quantidade de variáveis e quantidade de inversores, conforme é listado a seguir. 1. Custo 1: A primitiva utilizada pertence ao grupo C. Por exemplo, 0; 2. Custo 2: A primitiva é do grupo S e não inversa. Por exemplo, 𝐴𝐴; 3. Custo 5: A primitiva é do grupo S inversa. Por exemplo, �̅�𝐴; 4. Custo 11: Neste caso, a primitiva é uma função majoritária tendo como entradas uma constante e duas variáveis não inversas. Por exemplo, 𝑀𝑀(0,𝐴𝐴,𝐵𝐵); 5. Custo 23: Neste caso, a primitiva é uma função majoritária tendo como entradas três variáveis não inversas. Por exemplo, 𝑀𝑀(𝐴𝐴,𝐵𝐵,𝐶𝐶); 6. Custo 47: A primitiva é uma função majoritária contendo apenas um único inversor ou numa variável de entrada ou na saída. Por exemplo, 𝑀𝑀(0,𝐴𝐴,𝐵𝐵�); 7. Custo 95: A primitiva é uma função majoritária contendo dois inversores ou na saída e numa variável de entrada ou em duas variáveis de entrada. Por exemplo, 𝑀𝑀(𝐴𝐴,𝐵𝐵� ,𝐶𝐶̅). Como exemplo de aplicação, os coeficientes de custo para as funções majoritárias primitivas de 3 variáveis são apresentados na Tabela 18. Com exceção dos custos de valores 1 e 2, os valores de custo obedecem de forma ordenada ao critério mostrado na Equação (60). Isso garante que não se selecione uma primitiva de maior custo em detrimento a outras duas de menores custos, se esta também atender à solução do problema. 𝑐𝑐𝑖𝑖 = 2 ∙ 𝑐𝑐𝑖𝑖−1 + 1,∀ 3 ≤ 𝑗𝑗 ≤ 7 (60) Estando definidos os coeficientes de custo, a função objetivo do PLI binário é apresentada na Equação (61). A determinação dos valores de 𝑐𝑐𝑖𝑖 com base no critério mostrado na Equação (60) pode ser justificado pelo exemplo apresentado na Equação (62). 67 Tabela 18 – Coeficientes de custo das primitivas de 3 variáveis. (continua) Pj PRIMITIVA FORMA VETORIAL CUSTO P1 0 00000000 1 P2 1 11111111 1 P3 A 01010101 2 P4 B 00110011 2 P5 C 00001111 2 P6 A̅ 10101010 5 P7 B̅ 11001100 5 P8 C̅ 11110000 5 P9 M(0, A, B) 00010001 11 P10 M(0, A, C) 00000101 11 P11 M(0, A, B̅) 01000100 47 P12 M(0, A, C̅) 01010000 47 P13 M(0, B, C) 00000011 11 P14 M(0, B, A̅) 00100010 47 P15 M(0, B, C̅) 00110000 47 P16 M(0, C, A̅) 00001010 47 P17 M(0, C, B̅) 00001100 47 P18 M̅(1, A, B) 10001000 47 P19 M̅(1, A, C) 10100000 47 P20 M̅(1, B, C) 11000000 47 P21 M(1, A, B) 01110111 11 P22 M(1, A, C) 01011111 11 P23 M(1, A, B̅) 11011101 47 P24 M(1, A, C̅) 11110101 47 P25 M(1, B, C) 00111111 11 P26 M(1, B, A̅) 10111011 47 P27 M(1, B, C̅) 11110011 47 P28 M(1, C, A̅) 10101111 47 P29 M(1, C, B̅) 11001111 47 P30 M̅(0, A, B) 11101110 47 68 Tabela 18 – Coeficientes de custo das primitivas de 3 variáveis. (conclusão) Pj PRIMITIVA FORMA VETORIAL CUSTO P31 M̅(0, A, C) 11111010 47 P32 M̅(0, B, C) 11111100 47 P33 M(A, B, C) 00010111 23 P34 M(A, B, C̅) 01110001 47 P35 M(A, C, B̅) 01001101 47 P36 M(A, B̅, C̅) 11010100 95 P37 M(B, C, A̅) 00101011 47 P38 M(B, A̅, C̅) 10110010 95 P39 M(C, A̅, B̅) 10001110 95 P40 M̅(A, B, C) 11101000 47 Fonte: Elaboração do próprio autor. Assim, tem-se duas funções majoritárias que representam uma mesma função. O PLI modelado deve escolher a função de menor custo e isso pode ser feito atribuindo um valor maior que o dobro do custo de um grupo anterior, de modo que uma primitiva mais complexa não seja selecionada em relação a uma mais simples. 𝑧𝑧 = �𝑐𝑐𝑖𝑖𝑥𝑥𝑖𝑖 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 , 𝑐𝑐𝑖𝑖 ∈ {1, 2, 5, 11, 23, 47, 95} (61) [0 0 0 0 0 0 0 1] = 𝑀𝑀(�̅�𝐴,𝑀𝑀(0,𝐴𝐴,𝐵𝐵),𝑀𝑀(0,𝐴𝐴,𝐶𝐶)) = 𝑀𝑀(0,𝐵𝐵,𝑀𝑀(0,𝐴𝐴,𝐶𝐶)) (62) Definida a função objetivo e todas as restrições, o PLI binário assume o modelo representado pela Equação (63). Independentemente da quantidade 𝑛𝑛 de variáveis, 𝑐𝑐𝑖𝑖 assumirá apenas um dos 7 valores estabelecidos. Para ilustrar este fato, considere 69 o PLI para funções de 𝑛𝑛 = 8 variáveis. Na Equação (64) apresenta-se o coeficiente de custo relativo para uma das funções primitivas mais complexas. ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎧ 𝑚𝑚𝑖𝑖𝑛𝑛 𝑧𝑧 = �𝑐𝑐𝑖𝑖𝑥𝑥𝑖𝑖 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 , 𝑐𝑐𝑖𝑖 ∈ {1, 2, 5, 11, 23 ,47 ,95} 𝑠𝑠𝑠𝑠𝑗𝑗𝑒𝑒𝑖𝑖𝑠𝑠𝑠𝑠 𝑎𝑎: �𝑎𝑎1𝑖𝑖𝑥𝑥𝑖𝑖 ⟨≥ | ≤⟩ 𝑏𝑏1 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 �𝑎𝑎2𝑖𝑖𝑥𝑥𝑖𝑖 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 ⟨≥ | ≤⟩ 𝑏𝑏2 �𝑎𝑎3𝑖𝑖𝑥𝑥𝑖𝑖 ⟨≥ | ≤⟩ 𝑏𝑏3 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 ⋮ �𝑎𝑎(2𝑛𝑛)𝑖𝑖𝑥𝑥𝑖𝑖 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 ⟨≥ | ≤⟩ 𝑏𝑏(2𝑛𝑛) 𝑎𝑎𝑖𝑖𝑖𝑖 ∈ {0, 1} 𝑒𝑒 𝑏𝑏𝑖𝑖 ∈ {1, 2}, 1 ≤ 𝑖𝑖 ≤ 2𝑛𝑛 �𝑥𝑥𝑖𝑖 = 3 𝑖𝑖(𝑛𝑛) 𝑖𝑖=1 𝑥𝑥𝑖𝑖 ∈ {0, 1},∀ 1 ≤ 𝑗𝑗 ≤ 𝑝𝑝(𝑛𝑛) (63) 𝑃𝑃𝑖𝑖 = 𝑀𝑀(𝐹𝐹, �̅�𝐺,𝐻𝐻�) ⟹ 𝑐𝑐𝑖𝑖 = 95 (64) 70 6 ALGORITMO MLP01 No Capítulo 5 apresentou-se uma forma de modelar a otimização majoritária a partir de um problema de programação linear inteira do tipo 0 e 1. Para o caso mais simples, com funções de 3 variáveis, o PLI contém 40 variáveis. Isso já torna sua solução manual impraticável, de modo a requerer imperativamente o uso de aparato computacional. Neste capítulo é apresentado o software MLP01 (Majority Linear Programming 0 or 1), capaz de receber uma função de entrada em sua forma vetorial e produzir como saída sua função majoritária otimizada correspondente. 6.1 ESTRUTURA GERAL DO SOFTWARE Fundamentalmente, o MLP01 transforma, se necessário, uma função booleana de entrada num modelo de PLI binário, que possa ser interpretado e resolvido por um solucionador. Em sua composição foi escolhido o solucionador CPLEX (IBM, 2020). Para o desenvolvimento do software MLP01 foi utilizada a linguagem de programação Python, em sua versão 3.7.4. A linguagem Python é de alto nível e possibilita velocidade e integração entre sistemas com mais eficiência, agrega produtividade e baixos custos de manutenção. Previamente, antes da concepção do MLP01, foram desenvolvidas três ferramentas computacionais de apoio, também utilizando a linguagem Python. A primeira é capaz de transformar uma função de um formato majoritário literal para o formato booleano clássico, como o exemplo mostrado na Equação (65). Essa ferramenta permitiu analisar o comportamento de diversos padrões de combinações de funções primitivas em vários níveis. 𝑀𝑀(𝑃𝑃1,𝑃𝑃2,𝑀𝑀(𝑃𝑃3,𝑃𝑃4,𝑃𝑃5)) = 𝑃𝑃1 ∙ 𝑃𝑃2 + 𝑃𝑃1 ∙ 𝑃𝑃3 ∙ 𝑃𝑃4 + 𝑃𝑃1 ∙ 𝑃𝑃3 ∙ 𝑃𝑃5 + 𝑃𝑃1 ∙ 𝑃𝑃4 ∙ 𝑃𝑃5 + + 𝑃𝑃2 ∙ 𝑃𝑃3 ∙ 𝑃𝑃4 + 𝑃𝑃2 ∙ 𝑃𝑃3 ∙ 𝑃𝑃5 + 𝑃𝑃2 ∙ 𝑃𝑃4 ∙ 𝑃𝑃5 (65) 71 A segunda ferramenta fornece uma lista de todas as funções primitivas, de forma ordenada, sua quantidade e suas formas vetoriais. Tem capacidade para até 26 variáveis (todas as 26 letras do alfabeto). Isso facilitou a criação das tabelas 10, 11, 15 e 16, e tornou-se parte do MLP01. A última ferramenta é capaz de converter uma função do formato majoritário para o formato vetorial, como pode ser visto no exemplo de 4 variáveis mostrado na equação (66). Também tem capacidade para até 26 variáveis. Pode ser usada para criar vetores de teste e também ratificar as soluções obtidas pelo software MPL01. 𝑀𝑀(0,𝐴𝐴,𝑀𝑀�(1,𝐶𝐶̅,𝐷𝐷)) = [ 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 ] (66) 6.2 UTILIZANDO O SOLUCIONADOR CPLEX Para solucionar o PLI modelado pelo MLP01, foi utilizado o software IBM ILOG CPLEX Optimization Studio, em sua versão acadêmica 12.9.0. O CPLEX é um solucionador de última geração capaz de construir e solucionar problemas de programação linear com eficiência e robustez. Possui integração com diversas linguagens de programação (IBM, 2020). No desenvolvimento do MLP01 foi utilizada uma API (Application Programming Interface) de integração entre o CPLEX e a linguagem Python, chamada DOcplex (IBM Decision Optimization CPLEX Modeling for Python). Esta API é uma biblioteca composta por dois módulos e permite modelar um PLI na linguagem Python e acessar o solucionador CPLEX internamente, sem precisar executá-lo externamente. Estruturalmente, o uso do DOcplex requer como entradas os tipos de variáveis, a função objetivo e as restrições. Isso é feito de forma simples através de comandos disponibilizados pela API. No programa MLP01 são declaradas 𝑝𝑝(𝑛𝑛) variáveis, valor que corresponde àquele obtido na Equação (38). Como só podem ser do tipo 0 ou 1, as variáveis são declaradas como binárias. Uma série de outros comandos do DOcplex permitem obter um relatório completo a respeito das possíveis soluções do problema modelado. 72 6.3 DESCRIÇÃO DO FUNCIONAMENTO DO MLP01 O programa MPL01 recebe uma função em sua forma vetorial e prepara um banco de dados que possa ser modelado, caso seja necessário, que é transferido para o solucionador CPLEX, utilizando sua API DOcplex. De forma fundamental, o programa deve produzir a função de entrada no seu formato majoritário e de menor custo. Na Figura 23 é apresentado o fluxograma relativo ao funcionamento do MLP01. Quando executado, o programa aguarda que seja fornecida a entrada de uma função na forma vetorial, equivalente a um vetor de 2𝑛𝑛 bits. Caso seja inserida uma entrada inválida, será requisitada uma nova entrada, até que esta seja válida. Uma vez que a entrada esteja validada, é determinado o número 𝑛𝑛 de variáveis a partir da quantidade de elementos do vetor, utilizando-se a relação que foi apresentada na Equação (10). Havendo capacidade de processamento, admite-se 3 ≤ 𝑛𝑛 ≤ 26. Figura 23 – Fluxograma para o programa MPL01. Fonte: Elaboração do próprio autor. 73 Determinado o valor de 𝑛𝑛, são construídas listas indexadas de todas as 𝑝𝑝(𝑛𝑛) funções majoritárias primitivas para 𝑛𝑛 variáveis, nas suas formas vetorial e majoritária. Também são criadas a função objetivo e os atributos para a conversão de solução de um PLI para a forma majoritária. Este banco de dados está disposto em 4 arquivos armazenados no sistema. Se a entrada vetorial corresponder a uma das funções primitivas, essa será detectada e apresentada ao usuário na forma majoritária, sem que haja necessidade de se modelar um PLI. Em seguida, o programa reinicia aguardando uma nova entrada. Se o vetor de entrada não corresponder a uma das primitivas, então será modelado um PLI. São criadas todas as restrições do problema, também armazenadas em um arquivo no sistema. Se o problema for factível, o solucionador CPLEX apresentará uma solução e o programa fará sua conversão para a forma majoritária e retornará ao início para uma nova entrada. Caso o problema seja infactível, o programa emite um aviso e retorna ao início aguardando um novo vetor de entrada. 74 7 TESTES E RESULTADOS Todos os testes e resultados pa