Escreva programas com as entradas e saídas abaixo.
Dados os valores de uma função booleana de n variáveis, em que n é um inteiro positivo, construa a expansão em soma de produtos desta função.

Passo 1

O enunciado pede um programa que, dado um inteiro positivo n e os 2^n valores de uma função booleana f\colon\{0,1\}^n\to\{0,1\} (na ordem lexicográfica dos vetores de entrada), construa sua expansão canônica em soma de produtos, ou seja
f(x_1,\dots,x_n)\;=\;\bigvee_{\substack{\text{todas as entradas}\f=1}}\;\Bigl(\bigwedge_{i=1}^{n}\text{lit}_i\Bigr),
onde cada \text{lit}_i é x_i se o bit for 1 ou \overline{x_i} se for 0.

Passo 2

Geramos todas as combinações binárias de comprimento n em ordem lexicográfica, associando-as aos índices 0,1,\dots,2^n-1. Cada índice em binário de n bits indica uma atribuição (b_1,\dots,b_n).

Passo 3

Para cada índice k\) de \(0\) a \(2^n-1\), se o valor correspondente \(f_k\) for \(1\), construímos o mintermo \[m_k = \bigwedge_{i=1}^{n} \begin{cases} x_i, & \text{se o \(i-ésimo bit de k for 1},\ \overline{x_i}, & se o i-ésimo bit de k for 0. \end{cases}]

Passo 4

Reunimos todos os mintermos m_k com operadores \lor. Se não houver mintermos (isto é, se f for sempre zero), a expressão é a constante 0. Se houver mintermos para todas as 2^n combinações (isto é, f for sempre um), a expressão é a constante 1.

Resposta

função ExpansãoSomaDeProdutos(n, \(f_vals\)):
 // n: número de variáveis
 // \(f_vals\): vetor de tamanho \(2^n\) com valores 0 ou 1
 termos ← lista vazia
 para k de 0 até \(2^n\) - 1 faça:
 se \(f_vals\)[k] \(=1\) então:
 bits ← representação binária de k em n bits
 \(lit_linha\) ← lista vazia
 para i de 1 até n faça:
 se bits[i] \(=1\) então
 \(lit_linha\).adicionar("x₍" + i + "₎")
 senão
 \(lit_linha\).adicionar("¬x₍" + i + "₎")
 fim para
 \(m_k\) ← "(" + juntar(\(lit_linha\), " ∧ ") + ")"
 termos.adicionar(\(m_k\))
 fim se
 fim para

 se termos estiver vazia então
 retorne "0"
 senão
 retorne juntar(termos, " ∨ ")
 fim se

Exercícios de Livros Relacionados