RESOLUÇÃO DE EQUAÇÕES BOOLEANAS:APLICAÇÃO A UM PROBLEMA DE DECISÃOEMPRESARIAL QUALITATIVA• Walter Del Picchia

Professor Titular do Departamento de EngenhariaEletrônica da Escola Politécnica da USP.

* RESUMO: Este trabalho é uma atualização do artigo publi-cado pelo autor na RAE em 1974 e tem por finalidade: a) de-finir o Problema da Decisão Qualitativa (PDQ); b) mostrarcomo certos tipos de problemas lógicos podem ser formuladoscomo PDQs; c) apresentar um método de resolução do PDQ,o qual utiliza resolução de equações booleanas; d) apresentarum processo original de resolução destas equações, o Algorit-mo RQ, facilmente programável em computadores.

Os resultados apresentados são produto de trabalhos de-senvolvidos no antigo Departamento de Engenharia de Ele-tricidade da EPUSP, os quais deram origem a diversas pu-blicações, entre elas 1, 4, 5, 6, 7, 8, 9, 10, 11,20,23, 24, 25,28,29 (veja bibliografia no final do artigo).

Partes deste artigo são adaptações de trechos de livro do

54 Revista de Administração de Empresas

mesmo autor(11), onde se encontram os fundamentos teóri-cos, aplicações, sugestões para novos desenvolvimentos elistagens para microcomputador do SDB/3, um sistema deauxílio à tomada de decisões que resolve o PDQ.

* PALAVRAS-CHAVE: Problemas lógicos, equações boolea-nas, algoritmos numéricos, auxílio à decisão.

* ABSTRACT: The purpose of this paper is: a) to define theQualitative Decision Problem (QDP); b) to show how akind of logical problems can be formulated as QDPs; c) tointroduce a method of resolution of the QDP, which utilizesresolution of boolean equations; d) to introduce the RQ AI-gorithm, which is an original process of resolution of thisequations.

* KEY WORDS: Logical problems, boolean equations, nu-merical algorithms, support to decision.

São Paulo, 33(4):54-65 Jul./Ago. 1993

1. PROBLEMA A RESOLVER

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

Desejamos obter a solução do seguinteproblema (21):

UA diretoria de uma firma manufatu-reira reuniu-se para decidir sobre a polí-tica de seus futuros negócios, em funçãode seus objetivos. Discutiram as relaçõesentre o dinheiro gasto em propaganda, opreço das mercadorias manufaturadas, apercentagem das comissões dos vende-dores e as possíveis mudanças para umtipo mais aperfeiçoado de seus produtos,e também os vários efeitos que suas deci-sões acarretariam quanto ao lucro totalda firma e quanto à quantidade do pro-duto vendido. Os objetivos da firma fo-ram definidos: obter grande lucro e/ ouvender grandes quantidades de artigosmanufaturados, para levar a operação dafábrica à sua máxima capacidade possí-vel. Todos os diretores concordaram noscinco pontos seguintes:

I) Se a política da empresa for, ou aper-feiçoar o produto, ou cortar anúnciosonerosos, ou pagar aos vendedoresuma comissão mais elevada, ou elevaro preço das mercadorias vendidas avarejo, com a venda de um pequenonúmero de artigos, em qualquer dessescasos, então o lucro será pequeno.

11)Se grandes somas forem gastas empropaganda, sem alteração no tipodos produtos, ou se houver mudançapara um tipo mais aperfeiçoado e re-dução na dotação para a propaganda,então não haverá, simultaneamente,um grande volume de vendas e gran-des lucros.

III) Se a firma tiver grande lucro ou seseu volume de vendas for elevado,então o preço dos artigos no varejoserá baixo, e o gasto em propaganda,elevado; ou então o preço da venda avarejo será baixo, com uma pequenadotação para a propaganda, e haveráuma mudança para um tipo melhorde produto, com uma baixa comis-são para os vendedores.

IV) Se o preço de venda a varejo for bai-xo, se não houver corte na despesa

com propaganda e se houver comis-sões elevadas para os vendedores,ou se o preço de venda e as comis-sões forem baixos, com uma mudan-ça para aperfeiçoar o produto, entãouma grande quantidade de artigosserá vendida.

V) Se houver um grande gasto em propa-ganda, com uma mudança para umproduto aperfeiçoado, mas com o pre-ço de venda conservado baixo e commuitos artigos vendidos, então haveráum lucro elevado.

Com essas regras gerais como guia,qual deverá ser a política de tomada dedecisões da diretoria para se atingirem osseguintes objetivos:

a) obter grande margem de lucro;b) obter grande volume de vendas;c) obter simultaneamente grande lucro e

grande volume de vendas?"

Está implícito que as respostas são de-sejadas em função de: aperfeiçoar o pro-duto, gastar muito em propaganda, pagaraltas comissões, elevar o preço de venda.

2. CÁLCULO PROPOSICIONAL EÁLGEBRA BOOLEANA

Para equacionar o problema acima ne-cessitamos introduzir alguns conceitos. Oproblema proposto pertence ao CálculoProposicional clássico e pode ser equa-cionado com auxílio da Álgebra BooleanaBinária.

Nossa resolução se aplica a problemasda lógica que possam ser modelados peloCálculo Proposicional clássico (com ex-tensão para o Cálculo de Predicados).Apesar de limitados (14, 15, 16), o Cálcu-lo Proposicional e o Cálculo de Predica-dos clássicos prestam-se para a análise deinúmeros problemas da vida real.

Embora apreciável esforço esteja sendofeito para o processamento de linguagensnaturais, atualmente a formalização deproblemas constituídos por frases nestaslinguagens exige uma modelagem préviadas frases. As expressões do Cálculo Pro-posicional clássico, adiante estudadas,constituem um possível modelo, uma re-presentação esquematizada destas frases.

© 1974, 1993, Revista de Administração de Empresas / EAESP/ FGV, São Paulo, Brasil. 55

i1~[JREVISITADA

56

E a modelagem tem a finalidade de redu-zir a complexidade delas, facilitando seuentendimento e manipulação.

Por exemplo, as ambigüidades e as ex-ceções às regras presentes na linguagemnatural, embora toleráveis (ou até desejá-veis) num contexto literário, na formula-ção que propomos, devem ser elimina-das, antes de se traduzirem as idéias emexpressões do Cálculo Proposicional clás-sico, para tornar os textos passíveis detratamento formal. É necessário, assim,que seja selecionada (para ser traduzidaem expressões do Cálculo Proposicional)uma única dentre as possíveis interpreta-ções da frase original, e que correspondaà interpretação desejada pelo usuário.

Este processo de modelagem, porém,não é tranqüilo, surgindo inúmeras difi-culdades, tais como: o mesmo texto emlinguagem natural pode dar origem a di-versos significados; as frases necessitamser simplificadas, podendo levar a inter-pretações diferentes das originalmentedesejadas; a riqueza da linguagem é este-rilizada com a necessidade de tornar osenunciados precisos. Além disso, cuida-dos são essenciais para uma "traduçãoadequada" (que represente as intençõesdo usuário).

Desse modo, o problema se coloca napassagem das frases em linguagem natu-ral para as expressões padronizadas doCálculo Proposicional clássico, visto queas várias dificuldades acima citadas ocor-rem nesta passagem. As frases são "tra-duzidas" num certo contexto, de acordocom uma seleção feita pelo usuário entreas possíveis traduções. Estas, às vezes,surpreendem-no, divergindo das inten-ções iniciais e levando a um processo detentativa e erro, até que ele encontre atradução precisa (ou aquela que mais seaproxime do seu desejo inicial).

Lembramos que a Lógica apenas apro-xima a linguagem natural, e que as ex-pressões do Cálculo Proposicional clássi-co constituem uma possível tradução emlinguagem padronizada da leitura dousuário para o texto em estudo. Estas ob-servações são particularmente importan-tes quanto à operação lógica da implica-ção e quanto ao significado do conectivoou (as operações lógicas podem ser estu-dadas em 2, 14, 19,27,32,33); podemosmesmo afirmar que muitos desenvolvi-

mentos mais recentes da Lógica foramfeitos para tentar resolver os problemasque surgem quando se interpretam certasoperações, especialmente a operação im-plicação. Devido a estes problemas, fo-ram criados diversos modelos alternati-vos, tais como: Lógicas Modal, Multiva-lorada, Paraconsistente, Difusa (13, 18,22,30,31).

Após a interpretação das frases em lin-guagem natural para expressões do Cál-culo Proposicional clássico, estas últimas,para efeito de processamento, devem serrepresentadas por meio de expressões al-gébricas booleanas. Tal processo é trivial,unívoco, não apresentando dificuldadesde monta.

A seguir vamos mostrar como o Cálcu-lo Proposicional clássico pode ser equa-cionado em termos da Álgebra BooleanaBinária (3, 12,17,26,33).

A Álgebra Booleana Binária é definidasobre um conjunto A de dois elementos eapresenta três operações l+. . , '}. Essasoperações devem obedecer certas pro-priedades.

Denotando os dois elementos do con-junto A com os símbolos 1 e O, temos:A = {l,O} = conjunto formado pelos ele-mentos 1 e O.

As operações +, . , ' sobre {I,O} obede-cem às seguintes tabelas (x e y represen-tam elementos de A, e podem tomar osvalores 1 ou O): .

1 1 1 11 1

Todas as possíveis combinações de O e1 (valores de x e y) estão presentes nestastabelas.

o Cálculo Proposicional (ou Senten-cial) é estudado em detalhes em (14, 19,27, 32). Nele se estabelecem relações en-tre proposições. Estas são afirmações,não-contraditórias, que podem ser falsasou verdadeiras (Observe-se que estas exi-gências referem-se apenas ao CálculoProposicional clássico, pois, no CálculoProposicional Para consistente, podem

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

existir afirmações contraditórias; e, noCálculo Proposicional Multivalorado, po-dem existir afirmações que não são nemverdadeiras, nem falsas; sugerimos quemétodos similares aos aqui apresentadossejam estendidos a outros tipos de lógi-cas.).

As proposições podem ser relaciona-das, ou operadas, por meio de conectivoslógicos do tipo NÃO, E, E/OU, IMPLI-CA, EQUIVALE.As expressões resultan-tes dessas operações admitem tambémum valor falso ou verdadeiro, determina-do segundo regras vistas a seguir, e sãochamadas proposições compostas (Porrazões detalhadas adiante, o conectivo"ou inclusivo" do Cálculo Proposicional,usualmente grafado OU, será por nós es-crito E/OU).

O Cálculo Proposicional clássico podeser equacionado em termos da ÁlgebraBooleana Binária, definindo-se A como oconjunto formado pelos elementos "pro-posição verdadeira V" e "proposição fal-sa F", ou seja,A = {V,F}.

Desse modo, fazendo as correspon-dências indicadas na tabela a seguir:

V-IF-O

Operação E/OU sobre {V,F}-operação + sobre {l,O}

Operação E sobre {V,F} -operação. sobre {l,O}

Operação NÃO sobre {V,F} -operação' sobre {l,O}

obtemos uma Álgebra Booleana Binária.As tabelas da soma (+), do produto (.) eda complementação (') podem então serreescritas em termos de V e F, e serão,respectivamente, as tabelas que represen-tam as operações E/OU, E e NÃO (x, ysão proposições):

vv vv vv

Por conveniência, de agora em diante,vamos usar indiferentemente os símbolos

V, F, E/OU, E, NÃO ou 1,0 +, . , '. Dessemodo:

z = x E/OU y = x + y = disjunção de xcom y (soma booleana)

w = x E Y = x.y = conjunção de x com y(produto booleano)

v = NÃO x = x'= negação de x (comple-mentação booleana)

z, w, v são proposições compostas.

Note-se que:Se uma das proposições for verdadei-

ra, a disjunção será verdadeira.Se as duas proposições forem verda-

deiras, a conjunção será verdadeira.

Substituindo as proposições básicas(também chamadas átomos) por identifi-cadores (letras) e os conectivos por sím-bolos (tais como +, . , '), podemos obterexpressões algébricas que simbolizam aproposição composta.

Por exemplo, a proposição composta:

"Não houve aula hoje, ou o ônibusatrasou e a passagem está cara", apósser interpretada no Cálculo Proposi-cional clássico, seria traduzida pelaseguinte expressão algébrica:

ai + (b.c)com as proposições básicas:a = houve aula hojeb = o ônibus atrasouc = a passagem está cara

A seguir, é fornecida uma lista de pro-posições compostas e sua tradução emexpressões algébricas da Álgebra Boolea-na Binária. Repetimos que nem sempre atradução do texto é relativamente sim-ples, como no exemplo acima, devido àsambigüidades da linguagem natural.

A tabela 1 apresenta uma lista de tra-duções (21, 33) de expressões do CálculoProposicional (em língua portuguesa) pa-ra expressões algébricas. Nestas expres-sões comparecem variáveis literais (x, y,z, ...) e as operações (+, . , '). Apresenta-mos também alguns símbolos (~, =, I, 81)empregados quando se desejam expres-sões mais compactas. Note-se que, mui-tas vezes, escreveremos abc com o signi-ficando de a.b.c.

57

i1!J~REVISITADA

Tabela 1: Tradução de expressões padronizadas doCálculo Proposicional clássico para expressões álgébricas

Expressões do Cálculo Proposidonal clássico Expressões algébricasx E y E z, x COM V COM z x.v.zx MAS V, x EMBORA V X.yx E/OU y E/OU z x+y+zNAOx x'xSEMy, x COM NAOy x.y'NEMxNEMyNEMz x'.y'.z'NAOx MASy x'.yNAO AMBOS x E y (x.y)'NAO SIMULTANEAMENTE x E y E z (x.y.z)'x IMPLICA v- x ACARRETA ySExENTÃOyx SOMENTE SE Yx É CONDIÇÃO SUFICIENTE PARA Y x' +yySEx x--"yYSOB CONDIÇÃO QUE x y-xyDEVIDOAxyQUANDOxYSEMPRE QUE xy É CONDIÇÃO NECESSÁRIA PARA xy É IMPLICADO POR xx E CONDIÇAO NECESSARIA E SUFICIENTE PARA Y x.y+x'.y'x SE E SOMENTE SE Y x=yx EQUIVALE A yx OU ENTAO YOU ENTAO z xy'z' + x'yz' + x'y'z("UM DELES SOMENTE") xlylzxOUENTAOy x.y' + x'.y

xlyx OU EXCLUSIVO YOU EXCLUSIVO Z xy'z' + x'yz' + x'y'z + xyz("UM NÚMERO íMPAR DELES") xE9y€!)zx OU EXCLUSIVO Y x.y' +x'.yx DIFERENTE DE y x€!)yxEVERDADE x=l, xxEFALSO x=o, x'

Algumas observações sobre a tabela 1 sãooportunas:

Assim, g = x OU y será 1, se x, ou y, ou ambosforem iguais a 1; e h = x OUXy será 1, se x ou y(mas não ambos) forem iguais a 1. O conectivoOU recebe às vezes o nome de OU INCLUSIVO,em contraposição ao OU EXCLUSIVO.Adiante,veremos que h = x (j) y pode ser escrito, em ter-mos das operações +,.,', cornoh = x.y'+ x'y.

Na Lógica Simbólica, à qual pertence o Cál-culo Proposicional clássico, adotou-se para aoperação OU o sentido do item a acima, ou seja,o sentido do OU INCLUSIVOda álgebra Boo-leana (32).

A operação OU EXCLUSIVO,quando apli-cada a apenas dois elementos, traduz conve-nientemente o sentido do ou do item b acima,ou seja, o sentido de "um deles somente". Comefeito, h = x (j) y = xy' + x'y indica que h = 1 se x= 1, ou Y= 1, não podendo serem ambos iguaisa 1. Porém, quando aplicada a mais de dois ele-mentos, corno em p = x (j) y (j) z = x EfJ (y EfJ z) =(x (j) y) (j) z (o OU EXCLUSIVOtem a proprie-dade da associatividade), obtém-se, por mani-pulação algébrica (2, 17, 26, 33), que p = xy'z'+x'yz' + x'y'z + xyz. Ou seja,p = 1se x = 1, ou Y=1, ou z = 1, ou

I - O conectivo OU ENTÃOé urna proposta no-va, merecendo um estudo à parte:

Na Álgebra Booleana, existem as operações+ (OU) e (j) (OU EXCLUSIVO ou OUX), queobedecem às tabelas: Na linguagem natural, a conjunção OU

apresenta diversos significados, corno porexemplo:

a. Em "Dou desconto a professores, ou a enge-nheiros, ou a idosos", entende-se que, per-tencendo a urna só das categorias, ou a qual-quer combinação duas a duas delas, ou àstrês, o desconto estará garantido.

b. Em "Hoje à noite vou ao teatro, ou ao cinema,ou ao estádio", entende-se que hoje à noiteirei a um só dos lugares citados.

58

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

x = y = z = 1, não podendo doisdeles serem simultaneamenteiguais a 1.

Generalizando, a aplicação daoperação OU EXCLUSIVO a n ele-mentos levará à conclusão de que,havendo um número Ímpar de ele-mentos iguais a 1, o resultado será1.

Esta conclusão mostra que estaoperação é inadequada para tradu-zir o sentido do ou do item b aci-ma, pois, na linguagem natural,quando falamos que "vamos ao lu-gar X, ou ao y, ou ao z", nuncaqueremos dizer que vamos a umnúmero ímpar deles!

Para traduzir o sentido do oudo item b (o sentido de "um delessomente"), muito comum na lin-guagem natural, convém definir-mos o conectivo OU ENTÃO (sím-bolo I ) pelas expressões:q = x OU ENTÃO Y = x I Y = xy'+

x'y

r= xOUENTÃOyOUENTÃOz =x IY I z = xy'z} x'yz« x'y' Z

s = ... = x I Y I z I ... I w = xy'z' .w'+x'yz' ..w'+ x'y'z ..w'+ .+x'y'z'"w

Desse modo, q, f, ... S serãoiguais a 1, se e somente se um doselementos operados for igual a 1.

Para maior clareza, o ou doitem a (o OU INCLUSIVO) seráaqui grafado E/OU.

Em resumo, haverá três tipos de ou:

a) E/OU, com o significado de "OUINCLUSIVO"(símbolo +).

Assim: g = x + y + z + ... +w seráigual a 1, desde que pelo menos umdos operandos seja igual a 1 (seráigual a zero só se todos os operandosforem iguais a zero).

b) OU ENTÃO, com o significadode "UM DELES SOMEN-TE "(símbolo I ).

Assim: s = x I Y I z I ... I w seráigual a 1, se e somente se um doselementos operados for igual a 1.

c) OU EXCLUSIVO, com o signifi-cado de "UM NÚMEROÍMPAR DELES"(símbolo Ef».

Em geral, este conectivo não éusado na linguagem, mas é impor-tante na Álgebra Booleana aplica-da a circuitos lógicos (em codifica-ção, filtros etc.)

Assim: p = x Ef> Y Ef> z Ef> ... Ef> wserá igual a 1, se e somente se umnúmero ímpar de elementos opera-dos for igual a 1.

A tabela 2 apresenta as três ope-rações acima descritas, para quatrooperandos.

Notas:

1) Se x, y, w, z forem mutuamenteexclusivos, as operações OUENTÃO e E/OU levam ao mes-mo resultado:xlvlzlw e x e y v z j w

2) Para dois elementos, OU ENTÃOe OU EXCLUSIVO levam aomesmo resultado:x Iy = x Ef> Y = xy'+ x'y(ou x, ou y, mas não ambos)

3) Embora para a operação OU EN-TÃO seja válida a igualdade:(x Iy) I z = x I (y Iz),o resultado é diferente de:x Iy Iz = xy'z' + x'yz' + x'y'z

Portanto, quando se utiliza oconectivo OU ENTÃO, ele não po-de ser aplicado repetidamente,adicionando-se um elemento decada vez, mas deve ser aplicadoem bloco, utilizando-se as expres-sões empregadas em sua defini-ção. Diversamente dos operadoresE/OU, E, OU EXCLUSIVO etc.que são diádicos (operam doiselementos de cada vez), o OU EN-TÃO é um operador n-ádico.

4) Do mesmo modo que na utiliza-ção da função IMPLICAÇÃO (2,14, 32, 33), certos cuidados de-vem ser tomados quando-se em-prega o conectivo OU ENTÃOna tradução de frases da lingua-gem para expressões do CálculoProposicional clássico (ou paraexpressões algébricas), pois, em-bora corretos (ou seja, decorren-tes da definição), certos resulta-dos, num primeiro exame, po-dem contrariar a intuição. Porexemplo, as seguintes expressõessão válidas (veja a tabela 1 paraentendimento dos símbolos):

al a e a Gi a e Ü

a I (a.b) = a Ef> (a.b) = a.b'a I (a + b) = a Ef> (a + b) = a'.b

a Ib I (a.b) = a.b'= a' + b = a Ib

a I b I (a + b) = O

Para verificar o quanto estes re-sultados contrariam a intuição numprimeiro momento, basta se faze-rem as substituições:

a ::;:ir ao teatro

b = ir ao cinema

+ = E/OU

. =E

I=OUENTÃO

Ef> = OU EXCLUSIVO

O = FALSO

II - Prova-se que são válidas as se-

guintes igualdades:

x OU EXCLUSIVO Y = x Ef> Y = xy'+ x'y = (x E NÃO y) E/OU(NÃOxEy)

x IMPLICA Y = x-->y = x ' + Y =NÃO x E/OUy

x EQUIVALE A Y = (x = y) = xy +x'y' = (x E y) E/OU (NÃO x eNÃOy)

III - Conforme foi citado, em nos-so contexto, as ambigüidadespresentes na linguagem natu-ral devem ser eliminadas an-tes de se traduzirem as frasesem expressões do Cálculo Pro-posicional clássico (ou expres-sões algébricas).

Como exemplo de ambigüida-de, o mesmo enunciado em portu-guês : "Ir ao teatro (x) e ir ao cine-ma (y) ou ir ao estádio (z)" podelevar a várias expressões diferen-tes, conforme a intepretação: (x.y)+ z, x.(y + z), (x.y) I z, x.(y I z). Ou-tro exemplo de possíveis interpre-tações diversas, conforme o con-texto, é o seguinte(ll):

A frase: "Andar de bicicleta e acavalo" poderia ser interpretadano Cálculo Proposicional clássico,como:

• Andar de bicicleta E andar a ca-valo (contexto: um artista decirco);

• Andar de bicicleta E/OU andara cavalo (contexto: durante odia);

• Andar de bicicleta OU ENTÃOandar a cavalo (contexto: numcerto instante);

• Andar de bicicleta IMPLICA an-dar a cavalo (contexto: necessi-ta-se da bicicleta para se chegarao cavalo e montá-lo);

• Andar de bicicleta EQUIVALE Aandara cavalo (contexto: parair a um certo local, pode-se uti-lizar um ou outro, equivalente-mente).

As ambigüidades podem serresolvidas pelo usuário, baseando-se na intenção, no sentido das fra-ses, no bom senso e no conheci-mento do contexto no qual o pro-blema está inserido. Isto valeigualmente para se determinarqual o significado dos conectivosou utilizados.

59

i1~lJREVISITADA

Tabela 2: Operações OU, OU ENTÃO, OU EXCLUSIVOpara quatro variáveis

x y Z W g = x+y+z+w S=XlyIZIW p=XEIlyEllZEIlW

o o o o o o o o1 o o o 1 1 1 (i=1=20) 1

2 o o 1 o 1 1 (i=2=21) 1

3 o o 1 1 1 o o4 o 1 o o 1 1 (i=4=22) 1

5 o 1 o 1 1 o o6 o 1 1 o 1 o o7 o 1 1 1 1 o 1

8 1 o o o 1 1 (i=8=23) 1

9 1 o o 1 1 o o10 1 o 1 o 1 o o11 1 o 1 1 1 o 1

12 1 1 o o 1 o o13 1 1 o 1 1 o 1

14 1 1 1 o 1 o 1

15 1 1 1 1 1 o o

60

3. FUNÇÕES BOOLEANAS

Antes de resolver o problema apresen-tado na seção 1, necessitamos de mais al-guns conceitos.

Função booleana de N variáveis a, b, c,..., n é uma correspondência entre cadauma das possíveis combinações de valo-res 0,1 destas variáveis, com um e um sódos valores O ou 1. Esta correspondênciapode ser apresentada por meio da "tabe-la de combinações", vista a seguir.

Para N = 3 variáveis, uma possívelfunção de a, b, c é a função z, especifica-da pela tabela seguinte (as combinaçõesabc são dispostas em ordem de 000 a111).

A seqüência J = 11000110 (que é a colu-na da direita lida no sentido do maior ipara o menor, ou seja, de baixo para ci-ma), desde que se especifique a ordemdas variáveis, define completamente afunção z. Esta seqüência, junto com N(número de variáveis), e as variáveis abc,na ordem utilizada na tabela, recebe onome de Transformada Numérica (TN), efoi a utilização deste conceito que possi-bilitou a dedução do Algoritmo RQ (Aproposta da TN encontra-se em 23, 24 esua formalização em 4, 5,11).

Um modo usual de representar umafunção booleana é a notação de Caldwell,que especifica as posições dos bits 1 naseqüência J.

No exemplo dado temos bits 1 nas po-sições 7, 6, 2, 1. Na notação de Caldwellescreveríamos:

z = 2:(7,6,2,1)

Observe-se que, da notação de Cald-well, podemos facilmente determinar J e,tendo J, podemos determinar facilmentea notação de Caldwell da função.

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

Outro modo usual de representar umafunção é a forma algébrica; neste caso, afunção acima seria escrita:

z = a'.b'.c + a'.b.c' + a.b.c' + a.b.c= b.c' + a.b + a'b'.c

A primeira expressão é obtida direta-mente da tabela e a segunda é deduzidada primeira por manuseio algébrico (2,17,26,33).

Atribuindo a a, b, c os valores da tabe-la de combinações, linha por linha, e efe-tuando as operações de acordo com as ta-belas de +,.,', obtemos a coluna z.

Passar da notação algébrica de z para Jchama-se "transformar z" e passar de Jpara a notação algébrica denomina-se"anti transformar 1", e há métodos pró-prios paras as duas operações(11). Note-se que J depende da ordem em que se co-locam as variáveis a, b, c,... na tabela decombinações.

As igualdades vistas anteriormente,envolvendo as operações E8 (OU EXCLU-SIVO), --+(IMPLICA)e = (EQUIVALE),são obtidas representando algebricamen-te estas funções a partir de suas tabelasde combinações.

4. O PROBLEMA DA DECISÃO QUALITATIVA

O Problema da Decisão Qualitativa noCálculo Proposicional (PDQ) consiste noseguinte: dados um Enunciado En (siste-ma de expressões do Cálculo Proposicio-nal clássico) e uma Questão Q (funçãobooleana de algumas variáveis de En),determinar a Resposta R (função boolea-na de algumas ou todas as variáveis deEn que não comparecem em Q), tal que(En.R)--+Q) = 1 ou, equivalentemente,(En--+(R--+Q)= 1. Ou seja: queremos de-terminar R, tal que, se En e R forem ver-dadeiros, então Q também será verdadei-ra (ou também, se En for verdadeiro en-tão R implica Q). Dado um conjunto derelações não quantificadas entre eventos(proposições), sua resolução permite a

obtenção de outrasrelações entre propo-sições escolhidas -sendo estas seleciona-das dentre aquelasproposições original-mente fornecidas. Emparticular, a partir docitado conjunto de re-lações, o PDQ é útilpara resolver proble-mas lógicos do tipo:como agir em relaçãoa certas proposiçõesescolhidas, para for-çar a ocorrência deuma situação deseja-da envolvendo outrasproposições.

Em (1,11)encontram-se detalhes sobreo Problema da Decisão Qualitativa, alémdos problemas da "Obtenção de todas asteses possíveis"e da "Demonstração deteoremas" no Cálculo Proposicional, comsugestões de extensão para o Cálculo dePredicados. Aqui, mostraremos apenascomo resolver o PDQ a partir da resolu-ção de equações booleanas, nossos desen-volvimentos tendo enfoque operacional,sem preocupação de rigor.

O Problema da Decisão especifica umEnunciado En, função de N variáveis.Inicialmente, a Questão Q é especificadacomo função de algumas dessas variáveis(variáveis dependentes), e a Resposta R,como função de um subconjunto das va-riáveis remanescentes (variáveis inde-pendentes). No caso de existirem, no pro-blema proposto, variáveis ausentes - quenão foram especificadas nem na respostaR, nem na Questão Q-, elas são adotadascomo variáveis da Questão Q (funcionamcomo variáveis brancas, pois Q não de-pende dessas variáveis).

Nosso método de resolução, primeira-mente, transforma o PDQ proposto emexpressões algébricas, constituindo umsistema simultâneo de equações boolea-nas. Como qualquer sistema deste tipopode ser transformado em uma equaçãoequivalente, os algoritmos para resoluçãodestes sistemas, sem perda de generali-dade, são desenvolvidos para a resoluçãode equações equivalentes.

A seguir, a equação equivalente doEnunciado é determinada com as N va-

o PDQ é útil

para resolver problemas

lógicos do tipo: como agir

em relação a certas

proposições escolhidas,

para forçar a ocorrência de

uma situação deseiada.

61

i1~lJREVISITADA

riáveis em ordem talque aquelas que com-parecem em R (as in-dependentes) estejamà direita (veja a seçãoseguinte). Desse mo-do, teremos:

Nosso método de

resolução, primeiramente,

transforma o PDQ proposto

em expressões algébricas,

constituindo um sistema

simultâneo de equações

booleanas.

W(X1, ... ,Xj,Xj+1, ... ,XN) =1 é a equação equi-valente do Enun-ciado;

R = R(xj+1,.••,xN) é fun-ção de N - j variá-veis independen-tes;

Q = Q(xl1•••,xj) é função de j variáveisdependentes.

Após isso, para resolver o PDQ, faze-mos o seguinte;1) Resolvemos a equação equivalente, ob-

tendo as variáveis dependentes x.,....x,(todas elas, mesmo as inicialmente au-sentes em Q) em função das variáveisindependentes xj+1,. ••,XN•

2) Substituimos as expressões das variá-veis dependentes (x1,.••x.), obtidas emfunção das independentes (xj+l1 ••• 'xN),

na função Q = Q(xl1•••,xj). Evidentemen-te, utilizamos apenas as expressões dasvariáveis dependentes das quais Q éfunção. Se obtivermos uma só expres-são, esta será R; se existirem diversassoluções, devemos efetuar o produtobooleano entre elas (para maiores deta-lhes, veja 11).

5. RESOLUÇÃO DO PROBLEMA

Como primeiro passo, vamos escrevero sistema de equações que traduz o pro-blema proposto e transformá-lo numa sóequação equivalente ao sistema.

Adotando as proposições:

A = Aperfeiçoar o produtoB = Gastar muito em propagandaC = Pagar altas comissõesD = Elevar o preço de vendaE = Ter grande volume de vendasF = Ter alto lucro

62

o leitor poderá verificar, consultando aseção 1, que as cinco afirmações ("ver-dades") do Enunciado podem ser escri-tas:

I) (A + B' + C + D). E'--+F'

11) (B.A') I(A.B')--+(E.F)'

111) F + E--+(D'.B)I(D'.B'.A.C')

IV) (D'.B.C)I(D'.C'.A)--+E

V) B.A.D'.E~F

Como sabemos, x-+y (implicação) éequivalente a x' + y. Como as afirmaçõesdo problema são admitidas verdadeiras(base do problema), escreveremos x' + y= 1.Aplicando essa igualdade às implica-ções citadas, por manuseio das expres-sões, obtemos:

I) E + A'.B.C' . D' + F' = 1

11) A'.B' + A.B+ E' + F' = 1

III) E'.F' + B.D' + A.B'.C'.D' = 1

IV) D + A'.C' + B'.C + E = 1

V) A' + B' + D + E'+ F = 1

Se dispomos de várias expressõesiguais a 1, a expressão obtida pelo produ-to booleano de todas as expressões entresi, igualada a 1, é equivalente às expres-sões originais dadas.

Assim, chamando de P, Q, R, S, T àsexpressões à esquerda nas igualdades I,lI, III, IV, V, respectivamente, temos:

P.Q.R.S.T= 1

Efetuando o produto obtemos umafunção de E, F, A, B, C, D. que chamare-mos de w(E,F,A.B,C,D).

Portanto, w(E,F,A,B,C,D)= P.Q.R.S.T= 1

A ordem das variáveis foi escolhida

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

tendo em conta que o problema solicita m q r m q ras variáveis E, F em função das variáveisA,B,C,D. 62 3 14 10 O 10

A função w é chamada função equi- 60 3 12 9 O 9valente ao sistema e pode ser expressana notação de Caldwell. Em geral, o 40 2 8 7 O 7produto pode ser mais facilmente efe-

38 2 6 5 O 5tuado com auxílio da TransformadaNumérica (TN); obtém-se A TN de w e, 36 2 4 4 O 4a partir da mesma, obtém-se a notaçãode Caldwell de w. 20 1 4 3 O 3

No exemplo dado, efetuando o produ- 15 O 15 2 O 2to obtemos, para a equação equivalente:

13 O 13 1 O 1w(E,F,A,B,C,D)= ~(62, 60, 40, 38, 36, 20,

11 O 11 O O O15,13,11, 10,9,7,5,4,3,2, 1, O)

Os detalhes desta multiplicação serãoomitidos aqui, por não serem essenciais à Por exemplo, 62716 = 3, com resto 14.compreensão do método (veja 11).

Ainda, o problema pede, conforme a 11) Ordenam-se os quocientes q de acor-seção 1: do com os restos r correspondentes

(r vai de 2N-j - 1 = 15 a O):

a) F em função de A, B,C, D r q r q(Questão Q1) 15 O 7 O

b) E em função de A, B,C, D 14 3 6 2(Questão Q2)

13 O 5 Oc) E.Fem função de A, B,C, D 12 3 4 2,1, O

(Questão Q3)11 O 3 O

Em seguida, vamos determinar os itens 10 O 2 O

a, b e c de acordo com o roteiro da seção 9 O 1 O4. Para a resolução da equação equivalen-

8 2 O Ote utilizaremos o Algoritmo Resto-Quo-ciente, ou Algoritmo RQ (6, 10,11).

63

o algoritmo

Resto-Quociente

é facilmente

programável em

computadores.

6. APLICAÇÃO DO ALGORITMO RQ

Apresentaremos o algoritmo à medidaque o aplicarmos na resolução do proble-ma proposto.

No problema temos N = 6 variáveis edesejamos duas dessas variáveis (E e F)em função de outras 4 (portanto há 2 va-riáveis dependentes e 4 independentes).Chamando de j o número de variáveisdependentes, temos:I) Dividem-se os números da notação deCaldwell de w por 2N-j = 24 = 16, obtendo-se quocientes q e restos r:

jJ!JlJ REVISITADA

Desse modo, obtemos:

64

III) Determinam-se todas as combinaçõesde quocientes q, tomando um só qpara cada r, na ordem r = 2N-j -1 a O(são as várias seqüências de númerosque se obtém, lendo-se a coluna dadireita da tabela anterior de cima pa-ra baixo).

Resultam três soluções:

Gl = (O 3 O 3 O O O 2 O 2 O 2 O O O O)

G2 = (O 3 O 3 O O O 2 O 2 O 1 O O O O)

G3 = (O 3 O 3 O O O 2 O 2 O O O O O O)

IV) As soluções transformadas são obti-das construindo-se, para cada Gi,uma matriz cujas colunas são os ele-mentos de Gi, expressos em base 2,em colunas escritas de cima parabaixo.

Solução 1) G1:E1: 01010001 01010000F1: 01010000 00000000

Solução 2) G2:E2: 01010001 01000000F2: 01010000 00010000

Solução 3) G3:E3: 01010001 01000000F3: 0101000000000000

variáveis A,8,C,O

Por exemplo, na solução 1, o segundonúmero é 3, o qual em base 2 é 11.

Para obter a Questão Q3, determina-mos E.F nas três soluções encontradas;para isto, basta efetuar o produto boolea-no, bit a bit, nas três soluções acima, ob-tendo-se:

Solução 1, 2 e 3:E.F: 0101000000000000

(solução única)

As Respostas R, conforme citado na se-ção 4, serão determinadas efetuando-se osprodutos das diversas soluções entre si.

Ql = F, R1 = Fl.F2.F3 : 01010000 00000000

Q2 = E, R2 = El.El.E3: 01010001 01000000

Q3 = E.F,R3 : 01010000 00000000

Antitransformando (veja 11), obtemosas Respostas para as três Questões:

a) Questão Q1 = FResposta RI = A.B.D'

b) Questão Q2 = EResposta R2 = A.C'.D'+B.C.D'+A.B.D'

c) Questão Q3 = E.FResposta R3 = A.B.D'

7. INTERPRETAÇÃO DOS RESULTADOS

As Respostas são obtidas "vertendo" asexpressões algébricas dos Ri, utilizando atabela das traduções da seção 2 e substi-tuindo cada letra pela proposição corres-pondente.

Obtemos:

a) Para Ter alto lucro, deve-se Aperfei-çoar o produto E Gastar muito em pro-paganda E NÃO Elevar o preço devenda.

b) Para Ter grande volume de vendas,deve-se Aperfeiçoar o produto E NÃOPagar altas comissões E NÃO Elevar opreço de venda E/OU Gastar muitoem propaganda E Pagar altas comis-sões E NÃO Elevar o preço de vendaE/OU Aperfeiçoar o produto E Gastarmuito em propaganda E NÃO Elevar opreço de venda.

c) Para Ter grande volume de vendas ETer alto lucro, deve-se Aperfeiçoar oproduto E Gastar muito em propagan-da E NÃO Elevar o preço de venda.

Algumas considerações podem ser fei-tas sobre as soluções determinadas:

As Respostas R obtidas para as trêsQuestões (E,F, E.F), resolvem o Problemade Decisão Qualitativa nos três casos:

RESOLUÇÃO DE EQUAÇÕES BOOLEANAS ...

En--->(R->Q)= 1 das Respostas, podemos deduzir quais osvalores que devemos atribuir a A, B, C, Opara obtermos, em cada problema, R = 1e, portanto, Q = 1.

N o caso de o usuário desej ar for-mular outra Questão sobre o mesmoEnunciado, deverá fazê-lo antes daresolução da equação equivalente.Por exemplo, se o problema especifi-casse como Questão (já em linguagemalgébrica) :

Adotando En como verdadeiro, se forassegurado, em cada Resposta, que R = 1,teremos, conseqüentemente, Q = 1.

Nas respostas R, vemos que cada mo-nômio das expressões constitui uma al-ternativa para se obter a respectiva Res-posta igual a 1. Por exemplo, na Respostapara Q2 = E temos três monôrnios, e, por-tanto, três possíveis alternativas:

Q4 = A'.E + A.E'A=l, C=0, 0=0 (com B qualquerj-eRâ=IB==l,C==l,0=0 (com A qualquerj-s Râ=IA=l, B==l,D==O(com C qualquer)--->R2==l com a Resposta em função de C, D, F, a

equação equivalente seria resolvida de-terminando (A,E,B) ==f(C,D,F). ODesse modo, do exame das expressões

BIBLIOGRAFIA1. BRUNAZO FILHO, .A., DEL

PIGGHIA,W. Resolução dll proble-mas de decisão qualitàtiva no cál-culo proposicional utilizando equa-ções booleanas. São Paulo, Depar-tamento de Engenharia de Eletrici-dade da Escola Politécnica daUSP, abr. 1988, 51p.

2. CHINAL, J. Techniques boo-iêenes et cetcuteteuts arithmétj-ques. Paris: nunoc, 1967.

3. DAGHLlAN, J. Lógica eálgebra de Boole. São Paulo: Atlas,1986.

4. DEL PICCHIA, W. A transfor-mada numérica e sua aplicação àsimplificação de funções e à reso-lução de equações booleanas. SãoPaulo, mar. 1971 164 p. Tese (LiCvre Docência) - Escola Politéonica,Universidade de São Paulo.

5. DEL PICCHIA, W.; MAR-TINS, W.W. Tl1enumeticei trans-formo São Paulo, Departamento deEngenharia de Eletricidade da Es-cola Politécnica da USP, mar.1974, 3 v. (Publicações Internas,n. 16 - Basls. 41 p., n. 17 - Slrnpll-ficafion of Boolean functions, 51 p.n. 18 - Resolution of Booteanequaflons, 27 p.)

6. DEL PICCtttA, W. A simp/eand tast algorithm for the tesolu-tion of Boolean ectutions. SãoPaulo, Departamento de Engenha-ria de Eletricidade da Escola Poli-técnica da USP, mar.1974. 18 p,»(Publicação Interna, n. 19),

7. Uma/go-thmo numétici: para o manuseio

de funções booleanas; D problemada substituição. São Pavio, Depar-tamento de Engenharia de Eletrlci:dadeda Escoia Politécnica da

. USP, mar. 1974, 8 a, (PublicaçãoInterna, n. 20). .~'

B.· , Sistemati-'taçãodo tiroMo de máq1inas sé-

" qüenciais, para diferentes elem'en-tos de reafímentação. São Paulo,Departamento de Engentlarla déEletricidade da Escola Politécnicada USP, mar. 1974, 15p. (Publlc<j-ção Interna, [l. 21). .

9. . Resoluçãode equações booleanas; aplicaçãoa um problema de decisão ernpre-sarlal qualitativa. Re"vista de Admi-DistaçJo de Émpresas,. São Paulo,v. 14, n. 4, p. 79-84, jal.lago.1974.

10.' '" A nu.-mertcat algorithi'rl' for the- resolu-tíon of Bool'ean"ecuatíons, IEEETransactions'on Computers~ v.'23,n.9, P. 983-B, Sept. 1974. .

11. ". Méto-dos numéricos para a resoluçãode problemas lógicos. São Paulo:Blücher, 1993..

12; FAURE, E.; PAPIN, M.D.;KAUFMANN, A. Gours de celculsootéien appllqué, Paris; Aibin Mi-'chel,1970. ..

13. Gf1ANA, ~. Eógica para-consistente; una introduzione. Na-poli Lotttedo, 1983.

14. HEGENBERG,L. Lógica: ocálculo sentencial. São Paulo" Her-der, EDUSP, 1972.

15. . L. Lógica:o calculo de predicados. São Pau-lo: Herder, EDUSP, 1973.

16., lógica:exetckios fi ~ dedução no cá/cuiasenteoae: Sã'OPaulo: Pedagógica,1"976.

17, HILL,.F.J.; PETERSON,G.R . .tmroduõsto» to.switctunçtheory ànd logical designo NewYork:Joho Willey, 1968.

18.. HUGHES,. G. E.,CRESS-. WELL, M.J. An tntroauctío» to

modallog[c. London: Methuen,1972.

. 19. KLEENE,S.C. Ma,thematica/'<loçic. New York: John Wiley,.

1967.20. LAPPONI, J.G. Aplicação

. da transformada numérica na re-solução de equações booleanas.~Iectron, v. 7, n. 40, p. 206~12,jül.lago,,1970.

21.LEDLEY, R.S. Digital com-puter and contrai engineering.New Yor~: McGcaw HiJl,1960,

22. MARANÇA, A. P. G. L. Con-trolador;es com aula-sintonia ditu-sa para sistemas de 'engenhariaquímica. São Paulo: Escola PoJ!-técnicaiUniversidade de São Pal)-1011991 i1° p: D.issertaçãô (Mes-trado).

23,'MARTINS, W. W. Contri-buições ao estudo dos circuitosinter(uptores . .são Paulo' EséolaPolitécnica/Un.iversidape deS'ãoPaulo, 1ªparte, i964. 158p.Tese(lIvre Docência). '

24. < • . .• • Contri-buições .ao estudo dO$ circuitosintúruptores. São Paulo: EscolaPolitéc)lica/UniverSidade de São

. Paulo" 1967. 2! parte, 19Ap. Tese(Cátedra~.

Artigo original publicado na RAE de jul, ago. 1974, v,14, n.4, p. 79-84.

25. LógicaLinguística.' Ciência. e Cultura. SãoPaulo, (I parte; V. 36, n. 8, p.1,331-49,,1984; IJ parte: V. 37, n.4, p. 584-600, 1985; 111 parte: v.39), n. 5/6, .489-98,1987.

26. Me CLUSKEY, E. J Logicde"sign principies. EnglewoodCliffs:Pff!ntice Hall, 1986.

27. MENDELSON, E, Introduc-tion to methemstice! logie. NewYork: van Nostrand, 1964.

28. PESSOTA, R.e. C.LP.''Não'Vori'' a tempo real,matematíc•·camente programável. São Paulo:Escola Politénica/Universidade desão Paulo, 1993. 384p. Tese(Doutoramento).

29. ROtONDARO, I. G. A aplí-cação da matemática booleana naobtenção dos sistemas de tunçêe:

.,comporrehtes de um sistema defunções'São Paulo: UniversioadeMackenzie; 1987. 155p. (Tese deDoutorado). '

30. SKALA, H.J. On many va-!uêd logics, !uzzy sets, fuzzy logicsanc their applications. Futzy Setsand Systems, v.i, n. 2, p. 129-49,Abr.1978c

31. SMETS, P.; MANDANI, E.H.; DUSOIS, O.; PRADE, H. Non-stsnaen: 10gic for automated ree-sQning. San Diego: AcadémloPress, 1988.

32. TARSKI, A. Introduction tologic "and to the methodology ofdeductive sciences. New York: Ox-for(j University Press, 1965.

33. WHITESITT, J. E. BoóleanalgejJ[a and its applicatioDs. NewYork: Addison-Wesley! 1962.

65