Aula 05 de Lógica

Lógica de Predicados

Vamos estender a lógica proposicional para torná-la mais expressiva. Na lógica proposicional, as fórmulas não dependiam da estrutura das proposições, apenas do modo como estas eram combinadas. Considere, por exemplo, a sentença declarativa:

“Todo estudante é mais novo do que algum professor.”.

Na lógica proposicional, a sentença seria um átomo ou proposição simples. No entanto, a abordagem não captura estruturas mais finas da sentença, como “ser estudante”, “ser professor” ou “ser mais jovem do que alguém”.
Para capturar essa maior expressividade usamos predicados. O predicado E(Carlos) pode ser usado para denotar que Carlos é um estudante; o predicado P(Ricardo) para denotar que Ricardo é um professor e o predicado J(Carlos, Ricardo) para denotar que Carlos é mais jovem que Ricardo.
Os predicados acima estão modificando indivíduos específicos. Isso não ajuda muito na tarefa de descrever a frase que consideramos inicialmente, que fala de alunos e estudantes de uma forma mais geral. Os alunos e professores poderiam ser listados mas isso também não é prático. Então, usamos o conceito de variável que pode ser substituída por um indivíduo ou objeto qualquer. Usando as variáveis x e y, poderíamos escrever:

E(x) : x é um estudante

P(y) : y é um professor

J(x, y) : x é mais jovem do que y.

Ainda não temos uma formalização para os quantificadores “todo” e “algum”. Serão usados os símbolos ∀, que lemos “para todo”; e ∃, que lemos “existe” ou “para algum”. Os quantificadores sempre modificam uma variável. Tendo os predicado, os quantificadores e os conectivos já conhecidos da lógica proposicional, a sentença inicial de exemplo poderia ser escrita como:

∀x(E(x) → (∃y(P(y) ∧ J(x, y)))).

Para avaliar se a fórmula é verdadeira é necessário definir os alunos e professores sobre os quais estamos falando. Considerando a IFPE Afogados da Ingazeira, possivelmente a sentença é verdadeira.

No entanto, o resultado pode ser diferente em um curso de alfabetização para adultos.
Na Lógica de Predicados também trabalhamos com o conceito de função. Considerando a sentença: “Toda criança é mais jovem do que sua mãe”, podemos formalizá-la como

∀x∀y(C(x) ∧ M(y, x) → J(x, y));

usando os predicados:

C(x) : x é uma criança
M(y, x) : y é mãe de x
J(x, y) : x é mais jovem do que y.

As funções muitas vezes simplificam o que está sendo dito. Sabemos que uma criança possui apenas uma mãe, logo, poderíamos usar uma função m(x) que representa a mãe de x e evitaríamos escrever algo mais complicado como o predicado M(y, x). A fórmula seria simplificada como:

∀x(C(x) → J(x, m(x))).

Funções podem ser usadas quando o objeto sobre o qual falamos é definido unicamente, ou seja sem ambiguidade.
Como fizemos com a lógica proposicional, vamos definir formalmente a sintaxe da Lógica de Predicados e em seguida a sua semântica.

O alfabeto da lógica de predicados é formado por:

Símbolos de pontuação “(” e “)”.
Um conjunto V = {x1, x2, . . .} de variáveis.
Um conjunto C = {c1, c2, . . .} de constantes.
Um conjunto P = {P1, P2, . . .} de predicados.
Um conjunto F = {f1, f2, . . .} de funções.
Conectivos ¬, ∨, ∧, →, ∀, ∃.

Cada um dos predicados e funções contém uma aridade, ou seja, um número específico de argumentos.

O quantificador universal é utilizado quando queremos nos referir a todos os elementos de um conjunto. Por exemplo, se afirmamos que “todo número natural par é múltiplo de 2”, podemos reescrever essa afirmação de outra forma, veja: seja a um número natural par, esse número natural pode ser escrito na forma 2n, sendo que n é natural, isto é, para todo a pertencente aos naturais, a = 2n. Para simplificar a notação, podemos substituir o termo para todo por ∀, o qual possui o mesmo significado, podendo ainda ser lido como “qualquer que seja” ou “para cada”. Vejamos outro exemplo: seja n um número natural qualquer, podemos afirmar que:

∀ n ∈ ℕ, n.0=0, 0.n=0

Portanto, independentemente do número natural que escolhermos, o seu produto com zero resultará em zero.

Pode-se representar o quantificador universal "para todo" ou "∀" com o diagrama de Venn abaixo:

O quantificador existencial diferencia-se do universal porque não se refere a todos os elementos de um conjunto. Ele faz referência a pelo menos um elemento pertencente ao conjunto. Por exemplo, posso afirmar que um ônibus escolar só faz determinado trajeto se houver pelo menos um aluno que se dirigirá à escola “Educar o Educando”. Não importa se há mais alunos que irão para essa escola ou mesmo se todos os alunos estudam nessa escola. O fato de haver pelo menos um aluno da escola “Educar o Educando” já é razão suficiente para o motorista fazer o trajeto que o leva à escola. Para expressarmos o quantificador existencial, utilizamos o símbolo ∃, que pode ser lido como “existe um”, “existe pelo menos um”, “algum” ou “existe”.

Vejamos um novo exemplo: existe pelo menos um número natural n que, subtraído de seu quadrado, resulta em 0, isto é:

∃ n ∈ ℕ, n² – n = 0

Essa afirmação é válida para qualquer valor de n? Se escolhermos o valor de 2 para n, teremos 2² – 2 = 4 – 2 = 2. A igualdade não resultará em zero. Os únicos valores básicos para que a igualdade seja verdadeira são n = 1 e n = 0.

Pode-se representar o quantificador universal“existe um”, “existe pelo menos um”, “algum”, “existe” ou "∃" com o diagrama de Venn abaixo:

Há ainda um quantificador de existência e unicidade. Esse quantificador refere-se à existência de um único elemento. Para representar o quantificador de existência, utilizamos o símbolo ∃! e lemos “existe um e um só” ou “existe um único”. Por exemplo, podemos afirmar que existe um único número natural n que, somado com 5, resulte em 6. Podemos escrever:

∃! n ∈ ℕ, n + 5 = 6

Existe um único valor para n que possibilita que essa igualdade seja verdadeira. Esse valor é n = 1 e não há qualquer outro número natural que valide essa equação.

Pode-se representar o quantificador universal“existe um e um só”, “existe um único” ou "∃!" com o diagrama de Venn abaixo:

Onde o subconjunto C é um conjunto unitário.

Quantificador universal negativo: sãoo enunciados da forma ∀X[p(X) → ¬q(X)]. Em termos de conjuntos, um enunciado universal negativo estabelece que os conjuntos p e q são disjuntos. Por exemplo, a sentença “Nenhum homem é extra-terrestre” pode ser traduzida como:

∀X[h(X) → ¬e(X)],

ou seja, para todo X, se X ∈ h então X ∉ e

Pode-se representar o quantificador universal com o diagrama de Venn abaixo:

Alguns exemplos de traduções de sentenças para a lógica de predicados

“Toda cobra é venenosa”: ∀X[cobra(X) → venenosa(X)]
“Os remédios são perigosos”: ∀X[remedio(X) → perigoso(X)]
“Nenhuma bruxa é bela”: ∀X[bruxa(X) → ¬bela(X)]
“Não existe bêbado feliz”: ∀X[bebado(X) → ¬feliz(X)]
“Algumas pedras são preciosas”: ∃X[pedra(X) ∧ preciosa(X)]
“Existem plantas que são carnívoras”: ∃X[planta(X) ∧ carnivora(X)]
“Alguns políticos não são honestos”: ∃X[politico(X) ∧ ¬honesto(X)]
“Há aves que não voam”: ∃X[ave(X) ∧ ¬voa(X)]

 

Universo de Discurso Finito

Suponha que o universo de discurso A = {a1, a2, a3 . . . , an} e um conjunto finito com n elementos.
Nesse caso, a proposição

∀ x ∈ A, p(x),

que é verdadeira se a proposição aberta  p(x) for verdadeira para todo x ∈ A, e equivalente a conjunção:

p(a1) ∧ p(a2) ∧ p(a3) ∧ . . . ∧ p(an).

Dualmente, a proposição

∃ x ∈ A : p(x),

que é verdadeira se p(x) e verdadeira para pelo menos um  x ∈ A, corresponde a disjunção:

p(a1) ∨ p(a2) ∨ p(a3) ∨ . . . ∨ p(an).

Universo de Discurso Vazio

Considere agora o caso em que o universo de discurso não contém nenhum elemento, ou seja, A = ∅. Nesse caso, independente da proposição aberta p ( x ) , tem-se:

∀ x ∈ A, p ( x ) é verdadeira,
∃ x ∈ A : p ( x ) é falsa.

Por exemplo, considere as proposições “Todas as vacas voadoras comem rãs” e “Existe uma vaca voadora que come rãs”. Nesses exemplos, a proposição aberta p ( x ) é verdadeira se a vaca x se alimentar de rãs. O universo de discurso é o conjunto de todas as vacas voadoras, que é vazio, pois não existem vacas voadoras. A afirmação “Todas as vacas voadoras comem rãs” será falsa se encontramos uma vaca voadora que não come rãs. Contudo, como certamente não podemos encontrar uma vaca voadora que não gosta de rã, a afirmação é verdadeira. Similarmente, a proposição “Existe uma vaca voadora que come rãs” é verdadeira se encontramos uma vaca voadora que se alimenta de rãs. Porém, não podemos encontrar tal vaca voadora. Logo, essa proposição é falsa.

Negação de Proposições com Quantificador

As negações das proposições são dadas por:

¬ ∃ x ∈ A : p ( x ) ⇔ ∀ x ∈ A, ¬ p ( x ) .

¬ ∀ x ∈ A, p ( x ) ⇔ ∃ x ∈ A : ¬ p ( x ) .

A proposição “ ∃ x ∈ A : p ( x ) ”, em alguns casos, pode ser verdadeira para um único x ∈ A. Por exemplo, ∃ x ∈ N : x − 1 = 0. Quando isto ocorre, é comum escrever esta proposição da seguinte maneira: “ ∃ ! x ∈ A : p ( x ) ”, que se lê: “existe um único x em A que satisfaz p ( x ) ”, o sı́mbolo ∃ ! denota a existência e unicidade.

Analise a veracidade ou falsidade das seguintes proposições:

∃ ! x ∈ N : x − 1 = 0.

Solução: O número 1 é o único natural que satisfaz a equação x − 1 = 0. Logo, esta proposição é verdadeira.

∃ ! x ∈ Z : x ² − 1 = 0.

Solução: Os números − 1, 1 ∈ Z satisfazem a equação x ² − 1 = 0. Portanto, esta proposição é falsa, pois não temos a unicidade. Já a proposição ∃ x ∈ Z : x ² − 1 = 0 é verdadeira.

∀ x ∈ Z, x² − x − 2 ≠ 0.

Solução: É falsa, pois 2 ∈ Z e 2² − 2 − 2 = 0. Porém, sua negação, dada por: “ ∃ x ∈ Z: x² − x − 2 = 0”, é verdadeira.

∃ x ∈ R : x² + 2x + 2 = 0.

Solução: Note que, ∆ = 2²− 4 ( 1 )( 2 ) = − 4 < 0. Assim sendo, a equação do segundo grau x² + 2x + 2 = 0 não tem solução no conjunto os números reais e, portanto, esta proposição é falsa. Sua negação, dada por “ ∀ x ∈ R, x² + 2x + 2 ≠ 0”, é verdadeira.

∃ x ∈ ℚ : x²= 2.

Solução: Os números irracionais √2 e −√2 são as únicas soluções para a equação x² = 2. Portanto, não existe x racional que satisfaça a referida equação, ou seja, a proposição é falsa. Sua negação, dada por “ ∀ x ∈ Q,x²  ≠ 2”, é verdadeira.

Interpretações e Sutilezas da Linguagem

Nessa seção ilustramos como podemos expressar algumas funções proposicionais quantificadas comuns em português em termos formais. Além disso, ressaltamos alguns detalhes que são comumente adotados na linguagem coloquial. Por fim, apresentamos exemplos de proposições com mais de um quantificador.

Considere a afirmação:

Se a é par, então a² é também par.

Nessa afirmação, muito comum na linguagem coloquial, está implı́cito tanto o universo de discurso como o quantificador universal. Com efeito, o correto seria escrever:

Para todo a ∈ Z, se a é par, então a² também é par.

Em outras palavras, é necessário discriminar onde a proposição acontece.

Considere a afirmação:

“Todos os estudantes de matemática gostam de lógica”.

Essa afirmação envolve o quantificador universal “para todo”. O universo de discurso A é o conjunto de todos os estudantes. A função proposicional p ( x ) é verdadeira se x ∈ A é um estudante de matemática. Nessa afirmação temos também o função proposicional q ( x ) que é verdadeira se x ∈ A gosta de lógica. Podemos pensar, erroneamente, que a afirmação é expressa em termos formais como

∀ x ∈ A, p ( x ) ∧ q ( x ) .

Todavia, corresponde a dizer “Todo estudante é da matemática e gosta de lógica”, que é bem diferente da afirmação inicial. Com efeito, nem todo estudante é da matemática; existem estudantes de medicina, direito, administração, etc. A expressão formal correta para é:

∀ x ∈ A, p ( x ) → q ( x ) .

Em palavras, temos “Para todo estudante, se o estudante é da matemática, então este estudante gosta de lógica”.

Vamos agora considerar a afirmação obtida substituindo o quantificador “para todo” por “existe” no exercicio anterior.

“Alguns estudantes de matemática gostam de lógica”.

Podemos pensar que a afirmação anterior é expressa em termos formais como

∃ x ∈ A : p ( x ) → q ( x ) .

Contudo, essa expressão está errada pois pode acontecer de não haver estudantes de matemática no nosso conjunto de estudantes. Nesse caso, a proposição ∃ x ∈ A : p ( x ) → q ( x ) é verdadeira enquanto que “Alguns estudantes de matemática gostam de lógica” é verdadeira somente se existe pelo menos um estudante de matemática que gosta de lógica. Com efeito, a forma correta de expressar é:

∃ x ∈ A : p ( x ) ∧ q ( x )

que, em palavras, corresponde à dizer: “Existe pelo menos um estudante que é da matemática e gosta de lógica”.

Considere a afirmação:

Seja a um número inteiro. Se a é par, então a² é também par. Na primeira frase, temos que a é um número inteiro fixo mas sem nenhuma caracterı́stica que os difere dos demais números inteiros. Portanto, se vale para ele, vale também para qualquer outro inteiro. Portanto, a palavra “seja” pode ser interpretada como o quantificador universal “para todo”. Nesse caso, a afirmação acima corresponde à: “Para todo a ∈ Z, se a é par, então a² é par”. Esse é um exemplo do conceito amplamente usado no qual temos uma variável que é fixa mas arbitrária.

Seja A e o conjunto de todas as pessoas e p ( x, y ) a proposição que é verdadeira se y é a mãe de x. Por um lado, a proposição

∀ x ∈ A, ∃ y ∈ A : p ( x, y ) ,

corresponde a dizer que toda pessoa possui uma mãe. Note que nesse caso temos uma proposição com dois quantificadores. Por outro lado, a proposição

∃ y ∈ A : ∀ x ∈ A, p ( x, y ) ,

que também possui dois quantificadores, é equivalente a dizer que existe uma pessoa que é mãe de todos. Observe que as duas proposições são totalmente diferentes. Logo, a ordem dos quantificadores altera completamente o significado de uma proposição.

Considere a seguinte afirmação:

“Para todo cão no sofá existe uma pulga no carpete que o mordeu se ele for um cão preto”.

Em linguagem simbólica, essa afirmação corresponde à proposição:

∀ x ∈ A, ∃ y ∈ B : p ( x ) → q ( x, y ) ,

em que A é o conjunto de todos os cães no sofá, B é o conjunto de todas as pulgas no carpete, p ( x ) é a proposição: “x é um cão preto” e q ( x, y ) é a proposição: “a pulga y mordeu o cão x”.
A negação da proposição∀ x ∈ A, ∃ y ∈ B : p ( x ) → q ( x, y ), deduzida usando respectivamente ¬ ∀ x ∈ A, p ( x ) ⇔ ∃ x ∈ A : ¬ p ( x ),  ¬ ∃ x ∈ A : p ( x ) ⇔ ∀ x ∈ A, ¬ p ( x ), a equivalência p → q ⇔ (¬ p ∨ q ) e as Leis de De Morgan, é:

¬ ∀ x ∈ A, ∃ y ∈ B : p ( x ) → q ( x, y )

⇔

∃ x ∈ A : ¬ ∃ y ∈ B : p ( x ) → q ( x, y )

⇔

∃ x ∈ A : ∀ y ∈ B, ¬ p ( x ) → q ( x, y )

⇔

∃ x ∈ A : ∀ y ∈ B, ¬ ¬ p ( x ) ∨ q ( x, y )

⇔

∃ x ∈ A : ∀ y ∈ B, p ( x ) ∧ ¬ q ( x, y ) .

Em palavras, temos a afirmação “Existe um cão no sofá tal que, para toda pulga no carpete, o cão é preto e a pulga não o mordeu”. De forma mais breve, “Existe um cão preto no sofá que não foi mordido por pulgas”. Com base na negação, podemos responder diversas perguntas sobre a afirmação inicial:

(a) O que podemos dizer sobre a veracidade de “Para todo cão no sofá existe uma pulga no carpete que o mordeu se ele for um cão preto” se não há um cão preto no sofá?

Solução:

A proposição é verdadeira pois, para ela ser falsa, deve haver um cão preto que não foi mordido por pulgas.

(b) A proposição ∀ x ∈ A, ∃ y ∈ B : p ( x ) → q ( x, y ) será verdadeira se uma pulga morder todos os cães?

Solução:

Sim, pois q ( x, y ) será verdadeira para todo cão x.

(c) A proposição “Para todo cão no sofá existe uma pulga no carpete que o mordeu se ele for um cão preto” será verdadeira quando houver um cão preto que não foi mordido?

Solução:

Não, pois a negação de ∀ x ∈ A, ∃ y ∈ B : p ( x ) → q ( x, y ) será verdadeira.

(d) O que podemos dizer sobre a veracidade de“Para todo cão no sofá existe uma pulga no carpete que o mordeu se ele for um cão preto” se não há pulgas no carpete?

Solução:

Por falta de informação, essa pergunta não pode ser respondida. Com efeito, temos os seguintes casos:

(i) Se existe pelo menos um cão preto no sofá, então ela será falsa.
(ii) Se não existe nenhum cão preto no sofá, então ela será verdadeira.

Este exemplo ilustra o tipo de questões que devemos ser capaz de responder sobre uma função proposicional com quantificadores.

Exercícios Resolvidos

1- Transforme as afirmações abaixo em proposições lógicas.

Todos os As são Bs: ∀x A(x) ⇒ B(x)

Nenhum A é B: ¬∃x A(x) ∧ B(x)

Alguns As são Bs: ∃x A(x) ∧ B(x)

Alguns As não são Bs: ∃x A(x) ∧ ¬B(x)

Somente os As são Bs: ∀x B(x) ⇒ A(x)

Nem todos os As são Bs
– Alguns As não são Bs: ∃x A(x) ∧ ¬B(x)

Todos os As não são Bs
– Nenhum A é B: ¬∃x A(x) ∧ B(x)

Todas as pessoas gostam de outra pessoa
– ∀x Pessoa(x) ⇒ ∃y Pessoa(y) ∧ Gosta(x,y) ∧ ¬(x=y)

Existe uma pessoa de quem todas as outras pessoas gostam
– ∃x Pessoa(x) ∧ ∀y Pessoa(y) ∧ ¬(x=y) ⇒ Gosta(y,x)

O João frequenta a cadeira de IA ou PE (pode frequentar as duas)
– Frequenta(João,IA) ∨ Frequenta(João,PE)

O Rui frequenta ou a cadeira de IA ou a cadeira de PE (somente uma das duas)
– Frequenta(Rui,IA) ⇔ ¬Frequenta(Rui,PE)

A Ana tem exactamente uma irmã
– ∃x Irmã(x,Ana) ∧ ∀y Irmã(y,Ana) ⇒ x=y

A Ana tem pelo menos duas irmãs
– ∃x,y Irmã(x,Ana) ∧ Irmã(y,Ana) ∧ ¬(x=y)