109
edits
Changes
Jump to navigation
Jump to search
→Minimização de Expressões Booleanas e Circuitos
== '''Minimização de Expressões Booleanas e Circuitos''' ==
Nossa função para encontrar a soma da expansão de produtos de uma função booleana pode levar a circuitos ineficientes, porque o número de portas requeridas para implementá-los diretamente pode ser muito bem superior ao número que é realmente necessário. No entanto, o número de funções booleanas distintas de n variáveis (em que n é um inteiro positivo) é finito - de fato, é igual a <math>2^{2^{n}}</math>, como mostrado no texto - é fácil visualizar que o número de expressões booleanas distintas sobre n variáveis é infinito.Algumas formas do Princípio da Casas dos Pombos nos obriga a concluir que algumas funções booleanas têm muitas - na verdade, infinitamente muitas - representações distintas através de expressões booleanas.Da perspectiva de projeto de circuito, portanto, o que é necessário é um método para ''minimizar'' um circuito, no sentido em que se deseja, dado um circuito, encontrar um circuito equivalente que usa o menor número de portas quanto possível.A fim de fazer o Maple fazer isso para nós, devemos traduzir o problema da linguagem pictórica de diagramas de circuitos para uma descrição algébrica envolvendo expressões booleanas, reconhecendo que um diagrama de circuito é uma representação pictórica de uma expressão booleana equivalente, onde em uma porta lógica simples representa-se um dos operadores padrões booleanos: '''and''', '''or''' e '''not'''.Para tornar isso um pouco mais concreto, vamos ver um exemplo simples. A expressão booleana ''xy + xȳ'' que, representada na sintaxe de Maple, parece<pre>e := (x &and y) &or (x &and ¬ y);</pre>pode ser minimizada atarvés da utilização de Maple da seguinte forma<pre>with(logic):distrib(x &and (y &or ¬ y));</pre>que mostra que as expressões ''x ( y + ȳ ) and xy + xȳ'' representam a mesma função booleana. Porém ''y + ȳ = 1'', para qualquer y<pre>bequal(y &or ¬ y, true);</pre>de modo que ''x ( y + ȳ )'' simplifica ainda mais para x.O truque consiste em detectar, para uma determinada expressão booleana, as oportunidades para eliminar variáveis, ou reduzir o número de '''MinTerm''', usando as propriedades algébricas de operadores booleanos. Para o exemplo simples acima, este foi muito fácil, e Maple apenas nos permitiu provar que nossas suposições estavam corretas. Mas expressões que são apenas um pouco mais complicadas podem exigir muito mais para detectar tais simplificações. O que precisamos é algo que vai nos permitir trabalhar na direção oposta à que foi tomada acima, ou seja, dada a expressão original, podemos realmente encontrar uma expressão mais simples a que é equivalente? Além disso, podemos encontrar uma que é mínima?Felizmente, o pacote de '''logic''' de Maple proporciona um minimizador de circuito que cuida de tudo isso para nós. Ele é chamado '''bsimp'''. Para usar esse método, você deve carregar o pacote '''logic''' primeiro em sua sessão Maple, ou chamá-lo pelo nome completo '''logic[bsimp]'''.Claro, o Maple não fala diretamente em termos de portas e circuitos. Para solicitar ao Maple para minimizar um circuito, você deve falar a linguagem algébrica de Maple, especificando a expressão booleana equivalente.Por exemplo, para simplificar o exemplo anterior<pre>e := (x &and y) &or (x &and ¬ y);</pre>você pode digitar<pre>with(logic): # load 'bsimp'bsimp(e);</pre>Você pode aplicar '''bsimp''' a qualquer expressão booleana formada usando os operadores booleanos inertes do pacote '''logic'''. Vamos ver como Maple lida com alguns exemplos mais complicados.<pre>with(logic):e := (w &and x &and y &and (¬ z)) &or (w &and (¬ x) &and y &and z) &or (w &and (¬ x) &and y &and (¬ z)) &or ((¬ w) &and x (¬ y) &and z) &or ((¬ w) &and (¬ x) &and y &and z) &or ((¬ w) &and (¬ x) &and (¬ y) &and z);</pre>O procedimento '''bsimp''' é muito complexo, e usa um algoritmo de Quine-McCluskey baseado na representação de expressões booleanas como conjuntos. Estas estruturas de dados, embora muito natural para Maple, não correspondem muito bem com a descrição dada no texto.
== '''Condições Indiferentes''' ==
== '''Cálculos e Explorações''' ==
== '''Exercícios e Projetos''' ==
