Logica de predicados

Disponível somente no TrabalhosFeitos
  • Páginas : 10 (2362 palavras )
  • Download(s) : 0
  • Publicado : 18 de abril de 2013
Ler documento completo
Amostra do texto
Logica dos predicados
´

1/24

L´gica dos predicados
o

A l´gica ´ a ciˆncia do racioc´
o
e
e
ınio.
Socrates ´ um homem. Todos os homens s˜o mortais. Logo Socrates ´
e
a
e
mortal.
y p: Socrates ´ um homem.
e
y q : Todos os homens s˜o mortais.
a
y r: Socrates ´ mortal.
e
y Na l´gica proposicional, p ∧ q → r n˜o ´ uma tautologia.
o
ae
y Conclus˜o: o modelo fornecido pelal´gica proposicional n˜o ´ suficientemente
a
o
ae
expressivo.

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´

2/24

Introdu¸˜o
ca

y A l´gica proposicional fornece um modelo do racioc´
o
ınio muito limitado.
y A l´gica dos predicados ´ uma extens˜o da l´gica proposicional bastante
o
e
a
o
expressiva:
– As proposi¸oes ganham parˆmetros etornam-se predicados,

a
– Operadores de quantifica¸ao.


David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´

3/24

Predicados e quantificadores

y A senten¸a
c
Jos´ Saramago escreveu uma pe¸a de teatro.
e
c
´ verdadeira se
e
Existe uma pe¸a de teatro da qual Jos´ Saramago foi autor.
c
e
y “Jos´ Saramago escreveu pt” ´ um predicado: se substituimos ptpor algum
e
e

ıtulo de pe¸a de teatro, a senten¸a torna-se uma proposi¸ao.
c
c

y Outros predicados:
– “a escreveu In Nomine Dei ”.
– “a escreveu pt”.
y Um predicado ´ uma fun¸ao de um certo dom´
e

ınio para os valores booleanos.
Qual o dom´
ınio dos predicados apresentados nesta p´gina ?
a

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´4/24

Quantificador existencial

y ∃pt : pe¸a de teatro • Jos´ Saramago ´ autor de pt.
c
e
e
y “∃” ´ o quantificador existencial.
e
y “∃a : A • P (a)” ´ verdadeira se existe um elemento a de A tal que a proposi¸ao
e

P (a) seja verdadeira.
y “In Nomine Dei ” ´ uma pe¸a de teatro, e Jos´ Saramago ´ autor de In Nomine
e
c
e
e
Dei. Logo, a senten¸a “∃pt : pe¸a de teatro • Jos´Saramago ´ autor de pt” ´
c
c
e
e
e
verdadeira.
y A senten¸a “∃pt : pe¸a de teatro • Marcel Proust ´ autor de pt” ´ falsa.
c
c
e
e
y Aqui “Jos´ Saramago ´ autor de ” e “Marcel Proust ´ autor de ” s˜o dois
e
e
e
a
predicados un´rios.
a
O dom´
ınio de ambos ´ o conjunto das pe¸as de teatro.
e
c

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´5/24

Quantificador universal

y “∀” ´ o quantificador universal.
e
y “∀a : A • P (a)” ´ verdadeira se e somente se, P (a) ´ verdadeira para todo
e
e
elemento a de A.
y “∀c : cidade do Brasil • S˜o Paulo ´ maior que c” ´ verdadeira.
a
e
e
y “∀pt : pe¸a de teatro • Jos´ Saramago ´ autor de pt” ´ falsa.
c
e
e
e
y “∀pt : pe¸a de teatro • ¬( Marcel Proust ´ autor de pt)” ´verdadeira.
c
e
e

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´

6/24

Rela¸˜o entre quantificadores
ca

y O quantificador universal pode ser definido a partir do existencial:
∀x • P (x) = ¬∃x • ¬P (x)
“∀c : cidade do Brasil • S˜o Paulo ´ maior que c”=
a
e
“¬∃c : cidade do Brasil • ¬( S˜o Paulo ´ maior que c)”.
a
e
y E vice-versa:
∃x • P (x) = ¬∀x • ¬P(x).
“∃pt : pe¸a de teatro • Jos´ Saramago ´ autor de pt” =
c
e
e
“¬∀pt : pe¸a de teatro • ¬( Jos´ Saramago ´ autor de pt)”.
c
e
e
y Essas regras aplicam-se tamb´m a quantifica¸oes e predicados com m´ltiplas
e

u
vari´veis:
a
¬∀x • ∃y • P (x, y ) = ∃x • ¬∃y • P (x, y ) = ∃x • ∀y • ¬P (x, y ).

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´

7/24Algumas propriedades de quantificadores

∃x • E (x) ∨ E (x) = ∃x • E (x) ∨ ∃x • E (x)
∃x • (E (x) → E (x)) = (∀x • E (x)) → (∃x • E (x))
∀x • ∀y • E (x, y )

= ∀y • ∀x • E (x, y )

∃x • ∃y • E (x, y )

= ∃y • ∃x • E (x, y )

∀x • E (x) ∧ E (x) = ∀x • E (x) ∧ ∀x • E (x)

David D´harbe, 7 de abril de 2005
e

DIMAp/UFRN

Logica dos predicados
´

8/24

Linguagens de...
tracking img