Lógica de Predicados com Python

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

px

Em Python fica assim:

def P(x):
... return x**2 - 4*x <= 0

Vamos considerar o universo de discurso

xez4×5.png

Agora afirmo que

ax

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:

ands.png

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

ex

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:

ors.png

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:

xen1.png

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

6 pensamentos sobre “Lógica de Predicados com Python

  1. Logan, se voce nao se importa, estarei acompanhando seus escritos de agora em diante.

    Quanto a essa avaliaParaTodo, é o tipo de coisa que ia ficar legal se você parametrizasse o predicado que você quer avaliar. Tipo, em ruby, seria:

    def avaliaParaTodo(univ)
    univ.inject(true) { |result, item| result & yield(item) }
    end

    >>> avaliaParaTodo([1, 2, 3]) { |number| number true
    >>> avaliaParaTodo([1, 2, 3]) { |number| number false

    abraço!

  2. Davi, honrado fica o meu humilde blog.🙂
    Mas tenho de confessar que ainda não sei ler Ruby. /o\

    Lauro, você me fez lembrar que não poder passar métodos/funções como parâmetros é uma das coisas mais imperdoáveis de Java.

    E em relação a esse teu post:
    http://lauro.wordpress.com/2007/01/18/classe-em-python-para-interface-com-o-tomboy-via-d-bus/
    pra fazer a identação eu tive de mudar pra o modo de escrita ‘code’ no wordpress, e colocar vários (e-comercial)nbsp(ponto-e-vírgula). O chato é que se você for editar o post tem de colocar eles novamente. muito sux.

  3. Marcelo… Estou com um plugin no wordpress que faz a identação do código bunitinha e ainda dá um sintax higthligth bacana…

    Chegando em casa eu te passo o nome do plugin, ou se eu esquecer me lembra… =)

    Fazendo , fica tudo de boa.. =)

    [] s

    Danilo Cesar

  4. Pingback: Máquinas de Turing São Dispositivos de Manipulação Simbólica « Head Like a Hole

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s