math is hard, let’s go shopping!

Textos Recentes

last update:

Quando estou ensinando Lógica Aplicada à Computação, eu muitas vezes digo aos alunos que é simples criar um programa que calcula a tabela-verdade de uma fórmula da lógica proposicional. E o cálculo da tabela em si é realmente simples, o problema é como o programa vai representar as fórmulas da lógica. Ou seja, para calcular a tabela-verdade de qualquer fórmula, talvez escolhida pelo usuário, o programa deve ser capaz de representar qualquer fórmula da lógica proposicional.

Começo

Após um ano experimentando com várias ferramentas de geração de sites estáticos, essa é a versão nova do meu site, desta vez usando Hugo.

No post anterior foi mostrado como resolver desafios de lógica no estilo do Teste de Einstein em Prolog. Entretanto, o processo de geração no esquema de geração e teste era bastante ineficiente para problemas mais complexos. O problema é que muitas possibilidades são geradas e descartadas quando é feita a verificação de diferença. Por que não gerar as possibilidades já todas diferentes, eliminando esse teste extra? Em Prolog o predicado select(X, L, R) seleciona o elemento X na lista L, e retira X de L formando o resto R.

Dado que em Prolog é fácil criar estruturas (termos compostos) e fazer buscas sujeitas a certas restrições, é fácil resolver os tais desafios de lógica usando a linguagem. O tipo de desafio de lógica em questão é similar aquele “teste de Einstein” que algumas correntes de email dizem que só meia-dúzia de pessoas no mundo conseguem resolver (o que é uma grande balela). Várias informações (mas não todas) são dadas sobre um conjunto de indivíduos, e é preciso deduzir as informações que faltam para chegar na solução.

O post abaixo foi publicado inicialmente em uma lista de discussão, em resposta ao email de outro participante, que estava em dúvida se a resposta do gabarito de uma questão do POSCOMP 2010 estava correta. A questão está na imagem abaixo, com a resposta do gabarito indicada em vermelho. A questão aí é mais sutil do que parece à primeira vista. O enunciado não fala diretamente sobre como decidir se P != NP é verdade ou não, mas pede para considerar a hipótese P != NP como um problema de decisão a ser resolvido por um algoritmo, ou seja, por algum autômato.

Hoje vi um post no blog da Caelum sobre o lambda-cálculo (ou cálculo lambda) e, aproveitando que estou ensinando programação funcional atualmente, achei interessante escrever algumas ideias com a intenção de complementar o que está lá. O lambda cálculo é um formalismo lógico usado hoje em dia principalmente na teoria das linguagens de programação. Algumas aplicações do lambda cálculo nessa área incluem o projeto e análise de linguagens de programação e sistemas de tipos e a semântica das linguagens de programação.