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
Cálculo - Kenneth Rosen - Matemática Discreta e suas Aplicações - 6ª Edição - Capítulo 11.Desenvolvimento de Programas - Ex. 3