04 Lógica de Predicados

Prévia do material em texto

Lógica de Predicados
● É útil na verificação formal da correção de 
programas escritos em linguagens de 
programação de alto nível;
● Baseia-se no uso de Quantificadores e 
Predicados.
 
Quantificadores
● São frases que começam com: “Para todo” ou “Existe um”, 
que indicam, de alguma forma, quantos objetos têm 
determinada propriedade;
● O quantificador universal (Para todo) é indicado pelo 
símbolo:  
● O quantificador existencial (Existe um) é indicado pelo 
símbolo: 
● Um quantificador e sua variável são sempre colocados 
entre parênteses;
● Exemplos: (x) (x)
 
Predicados
● São propriedades;
● São representados como um segundo par de parênteses 
associado ao quantificador;
● Exemplo: (x>0)
● Neste exemplo, a propriedade da variável ‘x’ é ser 
positiva, ou seja, esse é o predicado de ‘x’.
 
Quantificadores e Predicados:
wff’s predicativas
● Quantificadores agem sobre predicados;
● Exemplo de wff predicativa: (x)(x>0)
● “Para todo ‘x’, ‘x’ é maior do que ‘0’“;
● Exemplo de wff predicativa: (x)(x>0)
● “Existe um ‘x’ e ‘x’ é maior que ‘0’“.
 
Validade
● O valor verdade de uma wff proposicional 
depende dos valores verdade atribuídos às 
proposições componentes;
● O valor verdade de uma wff predicativa 
depende da interpretação.
 
Lógica de Predicados:
Teorema
● É aquilo que se objetiva verificar;
● Exemplo:
Os programas apresentados a seguir foram 
desenvolvidos para trocar os valores das suas 
variáveis.
Verificar se eles trabalham corretamente.
 
Lógica de Predicados:
Deduções
● Para provar teoremas, devem ser usadas wff’s, 
asserções e argumentos válidos;
● Estes são usados para obter outras wff’s 
válidas até que se obtenha uma wff final.
 
#include <stdio.h>
#include <stdlib.h>
void main()
{
 int pri = 5;
 int seg = 0;
 int temp = 9;
 printf("\n\nPrimeiro valor = %d \n\nSegundo valor = %d \n\n\n\n", pri, seg);
 temp = pri;
 pri = seg;
 seg = temp;
 printf("Primeiro valor = %d \n\nSegundo valor = %d", pri, seg);
 _getche();
}
 
#include <stdio.h>
#include <stdlib.h>
void main()
{
 int pri = 5;
 int seg = 0;
 int temp = 9;
 printf("\n\nPrimeiro valor = %d \n\nSegundo valor = %d \n\n\n\n", pri, seg);
 temp = pri;
 pri = seg;
 seg = temp;
 printf("Primeiro valor = %d \n\nSegundo valor = %d", pri, seg);
 _getche();
}
 
wff’s predicativas
 
 int pri = 5; (pri)(pri=5)
 int seg = 0; (seg)(seg=0)
 int temp = 9; (temp)(temp=9)
“Existe um ‘pri’ e ‘pri’ é igual a ‘5’“;
“Existe um ‘seg’ e ‘seg’ é igual a ‘0’“;
“Existe um ‘temp’ e ‘temp’ é igual a ‘9’“.
 
#include <stdio.h>
#include <stdlib.h>
void main()
{
 int pri, seg, temp;
 printf("\n\nInforme o primeiro valor: \t");
 scanf("%d",&pri);
 printf("\n\nInforme o segundo valor: \t");
 scanf("%d",&seg);
 temp = pri;
 pri = seg;
 seg = temp;
 printf("\n\nPrimeiro valor = %d \n\nSegundo valor = %d", pri, seg);
 _getche();
}
 
#include <stdio.h>
#include <stdlib.h>
void main()
{
 int pri, seg, temp;
 printf("\n\nInforme o primeiro valor: \t");
 scanf("%d",&pri);
 printf("\n\nInforme o segundo valor: \t");
 scanf("%d",&seg);
 temp = pri;
 pri = seg;
 seg = temp;
 printf("\n\nPrimeiro valor = %d \n\nSegundo valor = %d", pri, seg);
 _getche();
}
 
wff’s predicativas
 
 temp = pri; (temp)(temp = pri)
 pri = seg; (pri)(pri = seg)
 seg = temp; (seg)(seg = temp)
“Para todo ‘temp’, ‘temp’ é igual a ‘pri’“
“Para todo ‘pri’, ‘pri’ é igual a ‘seg’“;
“Para todo ‘seg’, ‘seg’ é igual a ‘temp’“.
 
Lógica de Predicados:
Regra de Inferência
● É uma convenção que permite a uma nova wff ser inferida de 
outras wff’s;
● Inferir: fazer inferência sobre; concluir, deduzir;
● Exemplo:
Seja,
 (x)(x = 3),
 (y)(y = 4),
 (z)(z = x+y).
Então,
(z)(z = 7).
 
Lógica de Predicados:
Argumentos Válidos
● Um argumento pode ser, por exemplo, uma 
sequência de wff’s ou de asserções que pode 
ser representada por A1, A2, …, An, seguida de 
uma conclusão S.
A1, A2, …, An → S
 
Lógica de Predicados:
Argumentos Válidos
(Usando Asserções)
Comandos de Atribuição Asserções
{pri = 5; seg = 0; temp = 9}
temp = pri {seg = 0; temp = 5}
pri = seg {pri = 0; temp = 5}
seg = temp {pri = 0; seg = 5}
 
#include <stdio.h>
#include <stdlib.h>
void main()
{
 int pri = 5;
 int seg = 0;
 int temp = 9;
 printf("\n\nPrimeiro valor = %d \n\nSegundo valor = %d \n\n\n\n", pri, seg);
 temp = pri;
 pri = seg;
 seg = temp;
 printf("Primeiro valor = %d \n\nSegundo valor = %d", pri, seg);
 _getche();
}
 
Lógica de Predicados:
Axiomas
● Um axioma é um wff válida;
● Exemplo considerando “pri = seg”:
{F }pri = seg{F},
para o qual “{F }pri” significa substituir pri por seg 
em F.
Neste exemplo, F representa a função main().
pri
seg
pri
seg
 
Programa com
Comando Condicional
void main()
{
 int y = 0;
 int n = 5;
 
 if(n>10)
 {
 y = 100;
 }
 else
 {
 y = n+1;
 }
}
 
Lógica de Predicados:
Regra Condicional de Inferência
Seja:
Q = “int n = 5”
B = “n>10”
P1 = “y = 100”
P2 = “y = n+1”
R = “y = 6”
Então:
{Q.B} P1 {R}
{Q.B’} P2 {R}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20