OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o aluno será capaz de:

1. Aplicar o algoritmo FND/FNC a expressões concretas para encontrar suas formas normais conjuntiva e disjuntiva.
2. Compreender o uso de interruptores simples e compostos na lógica proposicional.
3. Identificar a estrutura dos interruptores compostos e das caixas pretas.
4. Utilizar a tabela de verdade para resumir informações sobre um dispositivo.
5. Extrair a FND e a FNC de um dispositivo a partir de sua tabela de verdade.
6. Projetar um interruptor composto que tenha o mesmo funcionamento que um dispositivo dado.

ÍNDICE
O ALGORITMO FND/FNC
ALGORITMO PARA OBTER A FORMA NORMAL A PARTIR DAS TABELAS DE VERDADE: CAIXAS PRETAS E INTERRUPTORES COMPOSTOS
EXERCÍCIOS DE EXEMPLO

Embora tenhamos provado que todas as expressões da lógica proposicional são equivalentes a uma forma normal, nada dissemos sobre como encontrar tais formas normais. Para conseguir isso, revisaremos um algoritmo cujo objetivo é gerar expressões em forma normal e, finalmente, revisaremos as aplicações que emergem desses tópicos.

O Algoritmo FND/FNC

O algoritmo FND/FNC é uma série de passos que permitirá encontrar, a partir de qualquer expressão da lógica proposicional, sua expressão equivalente em FND ou FNC (conforme o caso). Ele é realizado da seguinte maneira:

• PASSO 1: Substitua todas as sub-expressões da forma (F\rightarrow G) por (\neg F\vee G), e da mesma forma com (F\leftrightarrow G). Repita este passo até eliminar todas as implicações e duplas implicações da expressão.
• PASSO 2: Elimine as duplas negações e aplique as leis de De Morgan onde for possível. Devem-se aplicar as seguintes substituições
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    Quando não houver mais sub-expressões da forma \neg\neg G, \neg(G \wedge H) nem \neg(G \vee H), continue com o passo 3.

• Passo 3: Este passo se divide em duas partes dependendo se você deseja chegar a uma FND ou a uma FNC
  • Se você deseja chegar a uma FNC:

    Utilize a \vee-distribuição onde for possível. Ou seja, devem-se aplicar as seguintes substituições:

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    Quando não houver mais expressões da forma G\vee(H\wedge K) ou (H\wedge K)\vee G, você terá chegado a uma FNC.

  • Se você deseja chegar a uma FND:

    Utilize a \wedge-distribuição onde for possível. Ou seja, devem-se aplicar as seguintes substituições:

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    Quando não houver mais expressões da forma G\wedge(H\vee K) ou (H\vee K)\wedge G, você terá chegado a uma FND.

Exemplos

Utilize o Algoritmo FND/FNC para as seguintes expressões em suas formas normais conjuntiva e disjuntiva.

1. (A\rightarrow (B\rightarrow A)) [SOLUÇÃO]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [SOLUÇÃO]

Algoritmo para Obter a Forma Normal a partir das Tabelas de Verdade: Caixas Pretas e Interruptores Compostos

O algoritmo FND/FNC nos permite encontrar, para qualquer expressão da lógica proposicional, sua expressão equivalente em forma normal. Mas há situações em que não temos uma expressão inicial com a qual trabalhar em primeiro lugar. Este é o caso quando temos o resultado de uma tabela de verdade de alguma expressão F cuja estrutura proposicional desconhecemos. Explicar isso em palavras é um processo longo; a técnica, no entanto, é muito melhor compreendida mostrando exemplos de como ela se desenvolve, então deixarei alguns exemplos que desenvolverei em vídeo, mas primeiro você deve revisar os seguintes conceitos:

• Cabo: Meio pelo qual uma sinal circula
• Nó: Ponto onde 3 ou mais cabos se encontram.
• Interruptor simples: Dispositivo que admite os estados de ligado (1) e desligado (0), estando sempre em um, e somente um, desses estados. O estado de ligado permite a passagem de um sinal e o estado de desligado o impede.
• Interruptor composto: É um dispositivo composto de interruptores simples e cabos.
• Caixa Preta: É qualquer dispositivo cuja estrutura interna não pode ser observada.

Os interruptores simples são modelados através de variáveis proposicionais, e os compostos mediante expressões da lógica proposicional. Os casos mais simples são os que se obtêm dos conectores de disjunção e conjunção que se mostram a seguir

Esquema da Conjunção

Esquema da Disjunção

Exercícios de Exemplo

1. Um dispositivo é formado por uma caixa preta e 4 interruptores ordenados. A ativação do dispositivo ocorre sob as seguintes condições
   • Condição 1: É ativado se houver dois interruptores consecutivos ligados. Esta condição deixa de funcionar se houver três interruptores consecutivos ligados.
   • Condição 2: É ativado se todos os interruptores estiverem desligados.
   • Exceção: Se as condições anteriores não forem atendidas, o dispositivo desliga.

   a) Resuma esta informação em uma tabela de verdade [SOLUÇÃO]

   b) A partir da tabela de verdade, extraia a FND e a FNC que reproduzam o funcionamento da máquina. [SOLUÇÃO]

   c) Utilize a FNC ou a FND obtida no passo anterior (a mais simples) para projetar um interruptor composto que tenha o mesmo funcionamento que o dispositivo. [SOLUÇÃO]

2. O mesmo que no exercício anterior, só que agora o dispositivo tem 5 interruptores. [DESAFIO PARA O LEITOR]