Um teorema de Post?

[Francisco Antonio Doria]

Há um teorema, que enuncio:

``Dada uma sequência arbitrária de zeros e uns, de comprimento 2^n, esta sempre pode ser a tabela verdade de uma expressão booleana em n variáveis.''

(A prova é simples.) Este teorema seria de Post. Alguém conhece a prova original?

--

fad

ahhata alati, awienta Wilushati

[Walter Alexandre Carnielli]

Eu acho que isso ja aparece na obra do Boole, mas francamente não sei dizer exatamente onde...

De fato, em termos contemporâneos eh simples- usando polinômios em n variáveis com coeficientes em  Z_2 eh trivial.

--
Você recebeu essa mensagem porque está inscrito no grupo "LOGICA-L" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para logica-l+u...@dimap.ufrn.br.
Para postar nesse grupo, envie um e-mail para logi...@dimap.ufrn.br.
Acesse esse grupo em https://groups.google.com/a/dimap.ufrn.br/group/logica-l/.
Para ver essa discussão na Web, acesse https://groups.google.com/a/dimap.ufrn.br/d/msgid/logica-l/CA%2BuR7BJH6fxXNYJbgK-rrSqx8WM6X1XE%3D6_Yf6qG8n0P%3D0389A%40mail.gmail.com.