Nesta tarefa, você deverá implementar um programa que otimiza expressões booleanas. Uma expressão booleana é alguma sequência de símbolos, variáveis e operadores em alguma das seguintes formas:

• T representando o valor verdadeiro constante;

• F representando o valor falso constante;

• letra minúscula representando uma variável;

• (exp1&exp2) representando o operador lógico E entre duas expressões booleanas;

• (exp1|exp2) representando o operador lógico OU entre duas expressões booleanas;

• !exp representando o operador lógico NÃO de uma expressão booleana.

Antes de simplificar a expressão, você deve padronizar as expressões de forma que o operador de negação NÃO apareça apenas antes de constantes ou variáveis. Para isso, você deve aplicar os Teoremas de De Morgan recursivamente, além de remover a dupla negação. Assim,

• !(exp1|exp2) deve ser alterado para (!exp1&!exp2),

• !(exp1&exp2) deve ser alterado para (!exp1|!exp2) e

• !!exp deve ser alterado para exp.

Por exemplo, ao ser padronizada, a expressão

!((!a&b)|c)

deve ser alterada para

((a|!b)&!c)

Posteriormente, você deve simplificar a expressão booleana de forma que ela tenha uma forma mais simples, mas equivalente. Isso é feito aplicando-se uma ou mais regras de simplificação dentre as descritas abaixo. Por exemplo, podemos simplificar a expressão

((x|T)|(y&F))

em uma forma mais curta

(T|F)

e, logo depois, para apenas

T

Nesse exemplo, podemos descobrir o valor da expressão mesmo sem saber o valor de x ou de y. Mas é claro que nem todas as expressões podem ser reduzidas a um valor constante. Por exemplo, a expressão ((x|y)&!z) não pode ser transformada com nenhuma das regras de simplificação abaixo. Nesse caso, dizemos que a expressão é irredutível ou, algumas vezes, que ela está otimizada.

As regras de simplificação a serem aplicadas são as seguintes:

• (T&exp) deve ser simplificada para exp,

• (F&exp) deve ser simplificada para F,

• (T|exp) deve ser simplificada para T,

• (F|exp) deve ser simplificada para exp,

• !T deve ser simplificada para F,

• !F deve ser simplificada para T,

• (exp1&exp2) deve ser simplificada para exp1 se exp1 e exp2 forem equivalentes,

• (exp1|exp2) deve ser simplificada para exp1 se exp1 e exp2 forem equivalentes.

As regras simétricas também devem ser aplicadas para os operadores binários. Por exemplo, (exp&T) deve ser simplificada para exp. Para verificar se duas expressões exp1 e exp2 são equivalentes, deve-se verificar se elas têm as formas de algumas das linhas da tabela abaixo e se a condição correspondente é satisfeita:

Note que essas não são todas as regras de simplificação possíveis e também poderíamos considerar outros critérios para verificar expressões equivalentes. Nesta tarefa, no entanto, você deve se restringir às regras listadas.

Escreva um programa otimizar que otimiza uma expressão booleana de acordo com as regras de simplificação acima.

Entrada

A entrada contém uma única expressão booleana como descrita acima. Não há espaços nas expressões dos arquivos de teste. Observe que apenas expressões ou subexpressões com operadores binários são parentesados e que todas expressões ou subexpressões binárias são parentesadas. Por exemplo, temos

• T ao invés de (T) e F ao invés de (F),
• x ao invés de (x),
• (x&y) ao invés de x&y,
• !x ao invés de !(x) ou (!x).

Uma dica: como uma expressão booleana é definida recursivamente, a árvore binária correspondente à expressão da entrada pode ser construída por uma função de leitura recursiva (inclusive lendo caractere a caractere, sem precisar guardar toda a entrada antes).

((!((k|e)&F)|!k)&((T&k)|g))

Saída

A saída contém três linhas: a primeira linha contém a expressão booleana dada na entrada; a segunda linha contém a expressão pré-processada usando as regras de De Morgan e remoção de dupla negação; e a terceira linha contém a expressão otimizada. As expressões devem ser escritas no mesmo formato que a expressão dada na entrada.

((!((k|e)&F)|!k)&((T&k)|g))
((((!k&!e)|!F)|!k)&((T&k)|g))
(k|g)

Critérios

Você deverá utilizar uma árvore binária para representar a expressão booleana. Assim, você deve construir a árvore correspondente à expressão dada na entrada, modificar essa árvore para aplicar as regras de simplificação descritas e percorrer a árvore para imprimir a expressão de saída.

Submissão

Você pode fazer esta tarefa individualmente ou em dupla! O objetivo é que vocês tenham a oportunidade de projetar algoritmos e escrever programas em pares. Assim vocês podem trocar ideias e se ajudar mutuamente. Caso queira fazer esta tarefa em dupla, então siga algumas regrinhas:

1. Antes de começar a tarefa, converse e combine com um@ colega. Amb@s devem colaborar ativamente em todos os momentos da elaboração desta tarefa, incluindo ideias, projeto do algoritmo e escrita do código. Não é permitido dividir as atividades para cada um fazer uma parte separadamente.

2. Apenas um estudante deve submeter a tarefa e solicitar a correção aos monitores, mas ambos devem editar o arquivo de configuração dupla.txt fornecido no repositório para indicar o RA da dupla. O monitor corrigirá o código apenas do repositório do RA indicado nesse arquivo e registrará a nota para os dois estudantes no sistema.

3. Tome cuidado para que sua dupla tenha acesso apenas aos arquivos desta tarefa. É proibido compartilhar ou mostrar arquivos de outras tarefas com a dupla, ou quaisquer arquivos das tarefas com terceiros. Vocês sempre podem pedir ajuda a monitor@s!

Se você preferir fazer esta tarefa individualmente, então edite o arquivo dupla.txt para que ele contenha apenas seu RA.

← Anterior Voltar Próximo →