[obm-l] Funções booleanas

["Domingos Jr." <dopikas@xxxxxxxxxx>]

Este foi um fato discutido numa aula de booleana: os únicos conectivos
necessários para representar todas as expressões possíveis de n variáveis
booleanas são \/ (OU) /\ (E) ¬ (NEGAÇÃO). [nota: pode-se usar parênteses ou
qualquer outra coisa para alterar a precedência desses conectivos]

Eu consegui fazer uma prova disso e achei bem interessante, vou deixar um
espaço em branco pra quem quiser pensar um pouco e discutir idéias e mais
embaixo coloco a minha resposta:











-----
V := verdadeiro, F := falso

caso 1 variável:
    as funções booleanas de 1 variável são f1(X) = V, f2(X) = F, f3(X) = X,
f4(X) = ¬X
f1 e f2 podem ser expressas com os conectivos E e OU e a negação:
f1(X) = X \/ ¬X
f2(X) = X /\ ¬X

suponha que para funções com número de variáveis 1 <= k <= n seja possível
expressá-las somente com os 3 conectivos mencionados.

seja f(X1, X2, ..., X[k+1]) uma função booleana com k+1 variáveis.
    defina g(X1, ..., Xk) = f(X1, X2, ... Xk, V)
              h(X1, ..., Xk) = f(X1, X2, ... Xk, F)

pela hipótese de indução, g e h podem ser expressas através dos 3
conectivos.
f(X1, X2, ..., X[k+1]) = X[k+1] /\ g(X1, ..., Xk) /\ ¬ X[k+1] /\ h(X1, ...,
Xk)

se trocarmos g e h por suas expressões expandidas teremos formado uma
expressão booleana representando f usando somente os 3 conectivos e, sendo
assim, segue por indução para toda função com n >= 1 variáveis booleanas.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================