Ultimamente tenho me divertido revendo algumas coisas de lógica e no momento estou em predicados e quantificadores. Resolvi testar esses conceitos (de forma bem simples) usando Python, assim vou compartilhar minha idéia de diversão com o mundo.
Considere a frase “Marcelo dorme 4 horas por noite”, “Marcelo” é o sujeito e “dorme 4 horas por noite” é o predicado, a lógica de predicados expressa o predicado da afirmação como uma função proposicional onde uma variável representa o sujeito. Estabelecemos que P(x) significa “x dorme 4 horas por noite”, e podemos substituir x por qualquer sujeito, bem não qualquer sujeito e sim algum que esteja no universo de discurso, que nesse caso poderia ser “todos os alunos de computação”. A função P(x) pode ser verdadeira ou falsa, dependendo da qualidade de vida do aluno de computação que substituir x na função.
A outra parte são os quantificadores, que são o universal e o existencial. Usando a função P(x) e o universo de discurso declarados acima, com o quantificador universal posso afirmar que “todos os alunos de computação dormem 4 horas por noite”, ou usar o existencial e afirmar que “existe pelo menos um aluno de computação que dorme 4 horas por noite”. Para ser verdadeira a proposição quantificada universalmente precisa ser verdade para todos os casos do universo de discurso, já para a proposição quantificada existencialmente, basta que exista um caso verdadeiro para tornar verdadeira a proposição. Pelo menos essa semana posso afirmar que a segunda proposição é verdadeira, infelizmente. :-\
Agora vamos à programação. Em termos algorítmicos a verificação das proposições quantificadas é feita com um loop sobre os elementos do universo de discurso, se a proposição testada for quantificada universalmente o loop pára quando encontrar um resultado falso, que invalida a proposição, se for quantificada existencialmente, ele pára ao encontrar um resultado verdadeiro, que valida a proposição.
Vou usar um exemplo matemático pra facilitar. Considere a função P(x) significando
Em Python fica assim:
def P(x):
... return x**2 - 4*x <= 0
Vamos considerar o universo de discurso
Agora afirmo que
que é lida como “para qualquer valor de x (dentro do universo de discurso) P(x) é verdadeira”. Ora, P(x) é falsa para x=-1, o que torna falsa a proposição de que P(x) é verdadeira para qualquer valor de x. Expresso logicamente para o universo de discurso declarado acima fica:
A avaliação de “para todo” em Python:
def avaliaParaTodo(univ):
... res = True
... for x in univ:
...... res = res and P(x)
...... if not res:
......... return False
... return res
Daí testamos para o universo de discurso (usando range)
>>> avaliaParaTodo(range(-4,5))
False
Vejamos agora o existencial
que é lida como “existe ao menos um valor de x para o qual P(x) é verdadeira”. Com apenas um caso verdadeiro, como x=2, provamos a veracidade da expressão. Também pode ser expresso como:
Em Python:
def avaliaExiste(univ):
... res = False
... for x in univ:
...... res = res or P(x)
...... if res:
......... return True
... return res
Avaliando:
>>> avaliaExiste(range(-4,5))
True
Vamos mudar o universo de discurso um pouco, passando a usar o números naturais em lugar dos inteiros:
Agora o teste de ambos os casos, universal e existencial, resulta em verdade:
>>> avaliaParaTodo(range(0,5))
True
>>> avaliaExiste(range(0,5))
True
A coisa pode ficar mais elaborada com funções proposicionais com mais de um argumento, permitindo quantificações como “para todo x existe um y”, que algorítmicamente seria expressa com dois loops aninhados.
Depois disso tudo você pode querer mandar para sua namorada uma representação em lógica de predicados de “x ama y” ou algo assim. As mulheres adoram.
Referências:
Ah, e as fórmulas foram produzidas no OpenOffice.org Math
LogicParser 0.7 Hosted on Zooomr
