Quantificadores, Predicados e Validade
Quantificadores e Predicados
●
Fbfs proposicionais tem uma possibilidade limitada de
expressão.
–
●
●
Exemplo: Para todo x, x > 0
Ela não pode ser simbolizada adequadamente
usando-se apenas:
–
letras de proposição,
–
parênteses e
–
conectivos lógicos.
Ela contém dois conceitos novos:
–
Quantificador e
–
Predicado.
2
Quantificadores e Predicados
●
São frases do tipo:
–
para todo
–
para cada
–
Para algum
Frases que dizem quantos objetos tem uma
determinada propriedade
3
Quantificador Universal
●
O quantificador universal é simbolizado como: ∀
Onde lê-se:
●
–
“para todo”, ou
–
“para cada”, ou
–
“para qualquer”.
Então, a sentença:
Para todo x, x > 0
●
Pode ser simbolizada por:
(∀x) (x > 0)
4
Quantificadores e Predicados
(∀x) (x > 0)
●
●
Como deve-se utilizar os parênteses:
–
Primeiro par: deve possuir o quantificador e sua variável declarada;
–
Segundo par: frase onde o quantificador age.
A frase “x > 0” descreve uma propriedade da variável x.
–
●
Uma propriedade também pode ser denominada predicado.
Quando não sabe-se qual o predicado de x, pode-se utilizar:
(∀x) P(x)
●
Onde P(x) é utilizado para representar o predicado não
explicitado que a variável x possa ter
5
Quantificadores e Predicados
●
●
●
O valor lógico (verdadeiro ou falso) da expressão
(∀x) (x > 0) depende do conjunto de objetos que
estamos nos referindo.
Esse conjunto de objetos é chamado de:
–
domínio de interpretação, ou
–
conjunto universo.
O valor lógico de (∀x) (x > 0), por exemplo:
–
Seria verdadeiro se o conjunto universo fosse o conjunto
dos números inteiros positivos;
–
Seria falso se o conjunto universo fosse o conjunto com
todos os números inteiros;
6
Exercícios
Interpretação: conjunto universo e significado de P(x)
●
Qual o valor lógico da expressão (∀x) P(x) em cada uma
das interpretações à seguir?
a)
P(x) é a propriedade que x é amarelo
e o conjunto universo é o conjunto de todos os botões-de-ouro.
b)
P(x) é a propriedade que x é amarelo
e o conjunto universo é o conjunto de todas as flores.
c)
P(x) é a propriedade que x é uma planta
e o conjunto universo é o conjunto de todas as flores.
d)
P(x) é a propriedade que x é positivo ou negativo
e o conjunto universo é o conjunto de todos os inteiros.
7
Quantificador existencial
●
O quantificador existencial é simbolizado como: ∃
Onde lê-se:
●
–
“existe”, ou
–
“há pelo menos um”, ou
–
“existe algum”, ou
–
“para algum”.
Assim, a expressão:
(∃x)(x > 0)
pode ser lida: “existe um x tal que x é maior que zero”.
●
Seu valor lógico também depende da interpretação. Nesse caso,
–
Se o domínio de interpretação (conjunto universo) contiver um número
positivo, a sentença é verdadeira. Caso contrário, é falsa.
8
Exercícios
Interpretação: conjunto universo e significado de P(x)
●
Qual o valor lógico da expressão (∃x)P(x) em cada
uma das interpretações abaixo?
–
P(x) é a propriedade que x é amarelo
e o conjunto universo é o conjunto de todas as flores.
–
P(x) é a propriedade que x é possui asas
e o conjunto universo é o conjunto de todos os carros
.
9
Exercícios
Interpretação: conjunto universo e significado de P(x)
●
Dê uma interpretação para a qual (∀x)P(x) tem o valor verdadeiro.
●
Dê uma interpretação para a qual (∀x)P(x) tem o valor falso.
●
É possível encontrar uma interpretação na qual, ao mesmo tempo,
●
–
(∀x)P(x) seja verdadeiro e
–
(∃x)P(x) seja falso?
É possível encontrar uma interpretação na qual, ao mesmo tempo,
–
(∀x)P(x) seja falso e
–
(∃x)P(x) seja verdadeiro?
10
Predicados
●
Os predicados podem ter mais de uma única
variável.
Podendo ser:
–
unários: envolvendo propriedades de uma
variável;
–
binários: envolvendo propriedades de duas
variáveis;
–
ternários: envolvendo propriedades de três
variáveis;
–
n-ários: envolvendo propriedades de n variáveis.
11
Predicados
●
A expressão com predicado binário abaixo:
(∀x)(∃y)Q(x,y)
●
Pode ser lida como:
Para todo x existe um y tal que Q(x,y)
●
Um exemplo:
Se o conjunto universo são números inteiros e
Q(x,y) é a propriedade x > y
●
Diz-se que para todo inteiro, existe um inteiro maior, então,
o valor lógico é verdadeiro.
12
Predicados
Atenção!!
●
Com a mesma interpretação,
mas ao inverter a expressão para:
(∃y)(∀x)Q(x,y)
●
Diz que:
–
existe um número inteiro que é maior do que qualquer
outro inteiro, ou seja,
com valor lógico falso
●
Isso mostra que a ordem dos quantificadores é
importante.
13
Interpretação
●
Uma interpretação para uma expressão
envolvendo predicados consiste em:
–
Uma coleção de objetos, chamada de conjunto
universo ou domínio da interpretação, que
precisa incluir pelo menos um objeto.
–
A especificação de uma propriedade dos objetos
no domínio para cada predicado na expressão.
–
A atribuição de um objeto particular no conjunto
universo para cada símbolo constante na
expressão.
14
FBFs predicadas
●
●
Expressões podem ser formadas combinandose predicados com
–
quantificadores (∀ e ∃);
–
símbolos de agrupamento (parênteses e
colchetes); e
–
conectivos lógicos (∧, ∨, ¬, …).
Fórmulas Bem Formadas contendo
predicados e quantificadores são chamadas
de fbfs predicadas
15
FBFs predicadas
●
●
Exemplos:
–
P(x) ∨ Q(y);
–
(∀x) [P(x) → Q(x)];
–
(∀x) ( (∃x) [P(x,y) ∧ Q(x,y)] → R(x) );
–
(∃x)S(x) ∨ (∀x)T(y).
Os símbolos de agrupamento indicam o
escopo de um quantificador.
16
Exercícios
●
FBF: (∀x) (∃y) [ S(x,y) ∧ L(y,c) ]
●
Conjunto universo: Todos as cidades do Brasil.
●
S(x,y) é a propriedade: x e y estão no mesmo estado.
●
L(y,z) é a propriedade: o nome da cidade y começa com a
mesma letra da cidade z.
●
“c” é uma constante, onde é atribuído o valor de Caratinga.
●
Questões:
●
–
Qual é o escopo de (∃y)?
–
Qual é o escopo de (∀x)?
–
Qual o valor lógico da fbf apresentada?
17
Exercícios
1. Encontre o valor lógico da fbf
(∃x)( A(x) ∧ (∀y)[B(x,y) → C(y)] )
–
Com a interpretação:
●
●
●
●
Conjunto universo: conjunto de inteiros;
A(x) significa: x > 0;
B(x,y) significa: x > y;
C(x) significa: x <= 0.
2. Crie outra interpretação para dar um valor
lógico oposto ao encontrado.
18