Matemática discretaAula2-Lógicap

Prévia do material em texto

Matemática discreta Aula 2 -
Lógica Matemática
Professor: Iuri Jauris
1º Semestre de 2022
Pontifícia Universidade Católica do Rio Grande do 
Sul - PUCRS
1
Quantificadores e Predicados
O que podemos expressar através das sentenças vistas na aula
1 ainda é um pouco limitado;
Por exemplo, considere sentença: "Para todo x, x > 0" . Esta é
uma sentença verdadeira sobre o conjunto dos inteiros
positivos. Porém ela não pode ser simbolizada
adequadamente somente através de símbolos proposicionais,
parênteses e conectivos lógicos que vimos na aula 1.
Esta sentença contém dois novos elementos, um
quantificador e um predicado.
2
Lógica de Predicados
Proposição aberta: Uma proposição aberta é uma proposição que
depende de uma ou mais variáveis, por exemplo:
+ 1 é maior que .
O valor lógico de uma proposição aberta depende dos valores das
variáveis que nela ocorrem.
Por exemplo, a frase x é maior que é verdadeira se os valores de
x e y forem 7 e 4, mas é falsa se os valores forem 10 e 21.
3
Afim de estabelecer uma notação usual, usaremos letras
minúsculas x, y, z para denotar variáveis e usaremos letras
maiúsculas P, Q, R, . . . , seguidas das variáveis (x, y, z,...) entre
parênteses, para denotar proposições abertas que dependem
dessas variáveis.
Por exemplo, a notação P(x) poderia representar a frase é um
número ;
Q(x, y), por exemplo, poderia representar é maior que .
Os símbolos P(x), Q(x,y), R(y), . . . são chamados de predicados, e
poderão assumir um dos valores lógicos (F ou V).
4
Quantificadores
Os quantificadores são frases como "para todo", "para cada"
ou "para algum", que indicam de alguma forma quantos
objetos irão possuir uma determinada propriedade.
Quantificação universal
O quantificador universal é simbolizado por um A de cabeça-
para-baixo, , e é lido como "para todo", ou "para todos",
ou"para cada" ou para "para qualquer".
Portanto, a sentença "Para todo x, x > 0" pode ser simbolizada
como , onde x > 0 é o predicado, ou seja, é uma
propriedade do x, e x é o quantificador.
5
( 0)x x
Agora observe que, para que seja possível julgar se a frase
"Para todo x, x > 0 tem valor lógico verdadeiro ou falso, ainda é
preciso especificar o domínio de x.
Por exemplo, se o domínio de x for todos os números inteiros, a
afirmação será falsa pois por exemplo x = -2 é um número inteiro e
-2 < 0. Por outro lado se o domínio fosse apenas os inteiros
positivos então a sentença seria verdadeira.
Podemos especificar o domínio dentro da própria notação, para
isto, basta escrever , onde D se refere ao domínio.
Então a expressão significa que para todo número x
pertencente aos conjuntos dos inteiros, x é maior que 0.
6
x D P x
( 0)x xZ
Então o domínio da quantificação (D), e pode ser qualquer
conjunto previamente definido, x pode ser qualquer variável, e P(x)
qualquer proposição que depende dessa variável.
Por definição, a frase é verdadeira se, e somente se,
a proposição P(x) for verdadeira quando substituímos variável x
por qualquer elemento do conjunto D.
Se houver um (ou mais de um) elemento de D que torna P(x) falsa
quando atribuído à variável x, então a frase será
falsa.
7
x D P x
x D P x
Exemplo: se P(x) representa a frase x + 1 é maior que x então a
frase é verdadeira, pois, se substituirmos x por
qualquer número inteiro, a afirmação P(x) será sempre verdadeira.
Por outro lado, se P(x) representa a frase x é um número primo
então a frase é falsa; pois a afirmação P(6) (por
exemplo) é falsa.
Observe que frase a cima será falsa para vários outros valores de x
naturais como 8, 9, 10, 12, ... dentre outros, porém para uma frase
com o quantificador seja falsa, basta que a afirmação
seja falsa para pelo menos um caso do domínio, que a mesma será
falsa como um todo.
8
x P x
x P x
Exercício 1: Sejam N o conjunto dos números naturais, e suponha
que P(x) significa x é par Q(x) significa é divisível por 3 e R(x)
significa é divisível por 4 . Escreva em linguagem natural
(português) cada uma das proposições a seguir, e determine seu
valor-verdade:
9
a) todo número natural é par. (F)
b) todo número natural é par ou divisível por 3. (F), exemplo x = 5
c) todo o número natural, se for par então é divisível por 3. (F),
exemplo x = 4
d) para todo número natural ou o número é par ou divisível por 4. (F),
exemplo x = 3
e) todo o número natural é par e divisível por 4. (F), exemplo x = 3
f) todo o número natural se divisível por 4 é par. (V)
g) todo o número natural se é par não é divisível por 3. (F), exemplo
x = 6
h) para todo número natural se x é par então x+2 também é par (V)
i) para todo número natural se x é divisível por 4 então x+4 também
é divisível por 4 (V)
j) para todo número natural se x é divisível por 3 então x+1 também
é divisível por 3. (F) , exemplo x = 3.
10
Respostas
Quantificação existencial
O quantificador existencial é simbolizado por um E espelhado
, , e é lido como "existe um", ou "para pelo menos um" ou
"para algum".
Portanto, a expressão deve ser lida como; "existe
um x tal que x é maior que zero."
Novamente para que seja possível julgar se a frase anterior
tem valor lógico verdadeiro ou falso, ainda é preciso
especificar o domínio de x.
Nesse casso, se o domínio de interpretação contiver pelo
menos um número positivo, a expressão terá valor-
verdadeiro; caso contrário, ela terá valor falso.
11
( 0)x x
Exemplo: Denotemos por P(x) o predicado x é um número primo .
A proposição é Verdadeira , pois, por exemplo, a
afirmação P(7) 7 é um número é verdadeira, pois 7
pertence ao conjunto dos naturais e é um número primo.
Exemplo: Q(y) é a proposição aberta y é igual a y + 1 então a
frase é falsa; pois, para qualquer número real que
for atribuído a y, a afirmação Q(y) é igual a y + 1 é falsa.
12
x P x
x Q x
Portanto por definição, a frase é verdadeira se,
e somente se, existir pelo menos um elemento de D que, atribuído
à variável x, torna a afirmação P(x) verdadeira. Caso contrário,
. é falsa se, e somente se, não existir nenhum
elemento de D com essa propriedade.
x D P x
x D P x
Exercício 2: Sejam N o conjunto dos números naturais, e suponha
que P(x) significa é Q(x) significa é divisível por 3 e R(x)
significa é divisível por 4 . Escreva em linguagem natural
(português) cada uma das proposições a seguir, e determine seu
valor-verdade:
Exercício 3: Sejam N o conjunto dos números naturais, P(x, y) é +
2 > . Escreva as proposições listadas abaixo em linguagem natural
(português) e atribua o valor-verdade.
13
x
a) Existe ao menos um número natural divisível por 4. (V),
exemplo 4, 8, 12,...
b) Existe ao menos um número natural par ou divisível por 3
(V), exemplo 2, 3, 4, 6...
c) Existe ao menos um número natural que se for par é divisível
por 3. (V), exemplo x = 6
d) Existe ao menos um número natural que se for divisível por 3
então seu sucessor também será. (F)
e) Existe ao menos um número natural que se for par então o
seu sucessor será divisível por 3. (V), exemplo, 2, 8, 14...
14
Respostas
Exercício 2:
15
Respostas
Exercício 3:
a) Existe algum número natural x para qualquer natural y, tal
que x + 2 > y. (F) Pois se por exemplo y = 2 ou 3 ou 4 ou ... é
impossível encontrar um único x que consiga satisfazer a
regra x + 2 > y para todos os valores de y.
b) Existe ao menos um número natural x para algum natural y,
tal que x + 2 > y. (V) por exemplo x = 1 e y = 1 satisfaz
x + 2 > y
c) Existe ao menos um número natural y para qualquer natural
x, tal que x + 2 > y. (V) por exemplo se y = 1, para qualquer x
que for somado com 2 sempre será maior que y = 1
Exercício 4: Considere as seguintes expressões a baixo:
a)
b)
Onde x e y, são ambos números inteiros e Q(x, y) é a propriedade de
x < y. Reescreva cada frase em linguagem natural e de o valor lógico
de cada uma;
Solução
a) "para todo x existe um y, ambos inteiros, tal que x < y ". Essa
afirmação é verdade pois isto apenas indica que, para qualquer
inteiro, existe ao menos um outro inteiro ainda maior.
b) um número inteiro y para todos os inteiros x tal que x < y ".Essa afirmação é falsa pois isto implicaria que seria necessário
existir ao menos algum inteiro y maior do que qualquer outro
inteiro x.
16
,x y Q x y
,y x Q x y
Negação de sentenças predicadas
A negação de sentenças predicadas obedece a uma lógica
semelhante as das sentenças com conectivos lógicos vistos na aula
1. Então ao negarmos uma sentença predicada Verdadeira
teremos uma sentença Falsa e vice-versa.
Para além disso, ao negarmos um quantificador universal, o
mesmo se transformará num quantificador existencial, ao passo
que ao negarmos um quantificador existencial mesmo se
transformará num quantificador universal.
Além disso, lembre que na negação de uma sentença lógica, além
do operador lógico sofrer alteração as proposições existentes
também devem ser negadas. Então, de forma análoga, nas
sentenças predicadas se negarmos uma sentença P(x), por exemplo
x > 2, estaremos agora dizendo portanto ~P(x), que por sua vez
equivale a x 2, para algum domínio definido.
17
Exemplo: Considere a afirmação . O valor
lógico dessa afirmação é falso pois por exemplo para n = 1
teremos 1 + 2 > 3, o que não é verdade. Por outro lado, se
negarmos essa afirmação teremos agora que a afirmação
contrária é verdadeira, isto é , é
verdadeira;
Obs: Cuidado ao tentar fazer a negação de uma sentença
predicada em linguagem natural direto para linguagem
natural!
Exemplo: A negação da sentença é muitas vezes
é erroneamente escrita da forma: é
18
( 2 3)n nN
( 2 3)n nN
A negação da proposição é é na verdade: falso que
tudo seja ou ainda, coisa não é .
Simbolicamente:
Observe que se escrevêssemos é estaríamos
errando a negação da proposição original; simbolicamente ficaria:
De forma equivalente se quiséssemos escrever a negação de
coisa é teríamos que escrever: é ou
ainda é . Simbolicamente temos:
Se escrevêssemos tudo é ou ainda algo que não
é estaríamos errando a negação da proposição original, pois
simbolicamente teríamos:
19
~ ~x A x x A x
~x A x
~ ~x A x x A x
~x A x
Equivalência lógica no cálculo de predicados
Observe que ao negarmos uma fórmula predicada, podemos escrevê-
la de duas maneiras distintas. Por exemplo, ao dizermos que: é falso
que para todo x, dentro de um determinado domínio, valha a
propriedade . Essa sentença seria equivalente a dizer, pelo
menos algum valor de x , dentro de um determinado domínio, tal que a
propriedade P(x) não é válida.
Resumindo, podemos dizer que:
Ou seja, podemos trocar as posições do operador de negação e do
quantificador, desde que também troquemos o tipo de quantificador
( por , e vice-versa). Ressaltamos que estas equivalências valem
para qualquer predicado P e qualquer domínio D,
20
Quantificação sobre o conjunto vazio
A afirmação existe um estudante com mais de duzentos anos que
gosta de física é obviamente falsa; pois nem sequer existem
estudantes com essa idade, muito menos que gostem de física.
Esta afirmação pode ser escrita , onde D é o conjunto
dos estudantes com mais de duzentos anos de idade, e P(x) denota
a afirmação gosta de .
Obs: Se o domínio D é vazio, a afirmação é falsa,
qualquer que seja o predicado P.
Agora Considere agora a afirmação: todos os estudantes com mais de
duzentos anos de idade gostam de física. Qual o valor lógico desta frase?
21
x D P x
x D P x
Na notação anterior, esta afirmação pode ser escrita .
A questão é: qual o valor lógico da afirmação P(x) é verdadeira,
para qualquer elemento x de domínio se o domínio não tem
nenhum elemento?
Quando o domínio D é vazio, a interpretação mais consistente é
considerar a frase verdadeira, qualquer que seja o
predicado P. Dizemos que tais afirmações são verdadeiras por
vacuidade.
Em particular, a frase os estudantes com mais de duzentos
anos de idade gostam de deve ser considerada verdadeira.
22
x D P x
x D P x
Proposições predicadas com quantificadores.
Expressões podem ser construídas combinando-se predicados
com quantificadores, símbolos de agrupamento (parênteses
ou colchetes) e os conectivos lógicos.
Para isso, é necessário satisfazer regras de sintaxe para que
uma expressão seja considerada uma fórmula bem-
formulada (fbf).
Fórmulas bem-formuladas contendo predicados e
quantificadores são chamadas de fbfs predicadas. Muitas
declarações em português podem ser expressas como (fbfs)
predicadas.
23
Por exemplo, papagaio é significa, de fato, que
uma coisa, se esta for um papagaio, então é .
Denotando por P(x) a frase é um e por F(x) é
a proposição pode ser simbolizada como
( x)[P(x F(x)]
Outras variações em português que têm a mesma forma
simbólica são os papagaios são e
papagaio é .
Note que o quantificador é o universal e o conectivo lógico é
o condicional; e estão quase sempre juntos.
24
Simbolização incorreta: A fbf ( x)[P(x)^F(x)] é uma
simbolização incorreta, pois diz que todos no conjunto
universo subentendido como todo o mundo é um
papagaio feio.
Analogamente, um papagaio significa que
Existe alguma coisa que é, ao mesmo tempo, papagaio e
feio . Simbolicamente,
( x)[P(x) ^ F(x)]
LEMBRETE 1:
geralmente é conectado com
geralmente é conectado com ^
25
Exemplo: Usando os símbolos predicados indicados e
quantificadores apropriados, escreva cada frase em português
como uma fbf predicada. (O conjunto universo é o mundo inteiro.)
D(x): x é um dia.
S(x): x é ensolarado.
R(x): x é chuvoso.
M: segunda-feira.
T: terça-feira.
a. Todos os dias são ensolarados.
b. Alguns dias não são chuvosos.
c. Todo dia ensolarado não é chuvoso.
d. Alguns dias são ensolarados e chuvosos.
e. Nenhum dia é, ao mesmo tempo, ensolarado e chuvoso.
f. É sempre um dia ensolarado só se for um dia chuvoso.
g. Nenhum dia é ensolarado.
h. A segunda-feira foi ensolarada; portanto, todos os dias serão
ensolarados.
i. Choveu na segunda e na terça-feira.
j. Se algum dia for chuvoso, então todos os dias serão ensolarados.
26
Solução:
27
LEMBRETE 2:
, se lê ou .
, se lê pelo menos ou
.
OBS: Os advérbios e são
particularmente problemáticos, pois sua colocação em uma
sentença pode alterar completamente o significado. Por exemplo,
1.João ama só Maria.
2.Só João ama Maria.
3.João só ama Maria.
Exemplo: Usando os símbolos predicados J(x) para x é M(x)
para x é e L(x, y) para x ama y vamos escrever a seguir 3
sentenças diferentes ;
28
Possuem significados diferentes!
1.João ama só Maria. (Ou seja João só ama uma coisa no
universo, e essa coisa é Maria)
ou ainda de forma mais explicita
1. Dada alguma coisa, se esta coisa for João, então, se ele
amar alguma coisa, essa coisa será Maria.
( x)(J(x y)(L(x, y M(y)))
2. Só João ama Maria. (Se alguma coisa ama Maria no
universo, então essa coisa é João.)
ou ainda
2. Dada alguma coisa, se esta coisa for Maria, e se alguma
coisa a amar, então essa coisa será João.
( x)(M(x y)(L(y, x J(y)))
29
3. João só ama Maria. (Se João tem alguma
relação/sentimento com Maria, essa relação/sentimento é
apenas e exclusivamente o amor).
ou ainda
3. Dada uma coisa, se esta coisa for João, então, dada outra
coisa, se esta coisa for Maria, então João a ama.
( x)(J(x y)(M(y L(x, y)))
Em cada caso, o consequente do condicional é a palavra que
vem depois do na declaração original em português.
30
A simbolização de uma afirmação em português como uma
fbf predicada é de fato um pouco difícil. Para ajudar a
contornar esta dificuldade veja um resumo com algumas dicas
para a simbolização:
i. Procure palavras-chave que indiquem o tipo de
quantificador. Por exemplo; se aparecer: para todos, ou para
todo, ou para qualquer, ou para cada use um
quantificador universal. Caso contrário, se aparecer: para
algum, ou existe use um quantificador existencial.
ii. Algumas vezes em português há um quantificador universal
. Por exemplo, a frase caçam
pode ser entendida como: os cachorros
caçam .
31
iii. Se você usar um quantificador universal, quase sempre o
conectivo que irá com ele será um condicional.
iv. Se você usar um quantificador existencial, quase sempre o
conectivo que irá com ele será uma conjunção.
v. Qualquer coisa que venha depois deou
será a conclusão de um condicional; ou seja, a
conclusão vem depois de um em uma afirmação do
tipo .
32
Exemplo: Considere os símbolos predicados:
Expresse simbolicamente as declarações em português a seguir;
i. Todos os cachorros perseguem todos os coelhos.
ii. Alguns cachorros perseguem todos os coelhos.
iii. Apenas cachorros perseguem coelhos.
Solução: Para resolver esse problema vamos reescrever as 
proposições;
i. Dada uma coisa qualquer, se esta coisa for um cachorro, então
para qualquer outra coisa, se essa outra coisa for um coelho
então o cachorro irá persegui-lo.
33
ii. Existe uma coisa que é um cachorro e, para qualquer outra coisa,
se essa outra coisa é um coelho, então o cachorro irá persegui-lo.
iii. Dadas duas coisas, se uma for um coelho e a outra persegui-lo,
então essa outra coisa é um cachorro.
Vejamos agora como fica as sentenças em cada caso;
i. .
ii. .
iii. .
34
,x A x y B y C x y
,x A x y B y C x y
,x y B y C x y A x
Exercício 5: Usando os símbolos predicados indicados e
quantificadores apropriados, escreva cada frase em português
como uma fbf predicada. (O conjunto universo é o mundo inteiro.)
B(x): x é uma bola.
R(x): x é redondo(a).
S(x): x é uma bola de futebol.
a.Todas as bolas são redondas.
b.Nem todas as bolas são bolas de futebol.
c.Todas as bolas de futebol são redondas.
d.Algumas bolas não são redondas.
e.Algumas bolas são redondas, mas as bolas de futebol não são.
f.Toda bola redonda é uma bola de futebol.
g.Só bolas de futebol são bolas redondas.
h.Se as bolas de futebol forem redondas, então todas as bolas serão 
redondas.
35
Exercício 6: Usando os símbolos predicados indicados e
quantificadores apropriados, escreva cada frase em português
como uma fbf predicada. (O conjunto universo é o mundo inteiro.)
J(x): x é um juiz
L(x): x é um advogado
W(x): x é uma mulher
C(x): x é um químico
A(x, y): x admira y
a.Existem algumas mulheres advogadas que são químicas.
b.Nenhuma mulher é, ao mesmo tempo, advogada e química.
c.Alguns advogados admiram apenas juízes.
d.Todos os juízes admiram apenas juízes.
e.Só juízes admiram juízes.
f.Todas as mulheres advogadas admiram algum juiz.
g.Algumas mulheres não admiram nenhum advogado.
36
Respostas:
5)
6) 
37