00:00:00
[Música]
00:00:10
Olá alunas e alunos do curso de
00:00:13
fundamentos matemáticos para computação
00:00:15
nesta vídeo aula eu vou falar da lógica
00:00:17
de predicados começar apresentando
00:00:19
regras de dedução considerando a
00:00:21
particularização Universal e a
00:00:24
particularização existencial depois
00:00:26
apresentar a generalização Universal e
00:00:29
existencial por último Vamos eu vou
00:00:31
ilustrar o uso dessas regras através de
00:00:33
exemplos bom é diferente da lógica
00:00:37
proposicional que poderíamos provar a
00:00:39
validade de um argumento usando por
00:00:41
exemplo uma tabela verdade na lógica de
00:00:44
predicado nós utilizamos um sistema mais
00:00:46
formal sistema de regras de dedução para
00:00:49
partir dessas hipóteses e chegar à
00:00:51
conclusão desejada para isso tá sistema
00:00:53
ele deve ser correto no sentido de que
00:00:56
apenas argumentos válidos vão ser
00:00:58
demonstráveis né e as hipó verdadeiras
00:01:02
dentro de um domínio de interpretação
00:01:04
vão levar com a aplicação das regras de
00:01:06
dedução a conclusões que também são
00:01:09
verdadeiras dentro desse domínio de
00:01:11
interpretação então também se trata de
00:01:13
um sistema que é completo no sentido de
00:01:15
que todo argumento válido ele deve ser
00:01:18
demonstrado demonstrado
00:01:21
Além disso ele busca ser tratado no
00:01:24
sentido da gente conseguir realizar a
00:01:26
pele deduções com um conjunto aplicando
00:01:28
um conjunto mínimo de regras bom
00:01:32
as regras de equivalência e as regras de
00:01:35
inferência que vimos lá nas lojas na
00:01:37
lógica proporcional ainda vão fazer
00:01:39
parte desse sistema de loja de formal de
00:01:43
dedução na lógica de predicados tá então
00:01:46
por exemplo aqui nós temos essa esse
00:01:49
argumento na lógica de predicados onde
00:01:51
podemos identificar que essa hipótese e
00:01:54
essa aqui então temos duas hipóteses se
00:01:57
observamos é sendo essa hipótese
00:01:59
verdadeira e essa aqui também verdadeira
00:02:02
esse antecedente válido nos leva a
00:02:06
inferir que esse consequente aqui também
00:02:09
é válido que é a regra de motos que
00:02:12
vimos sendo aplicada na linha 1 e 2 bom
00:02:16
mas a abordagem geral
00:02:19
na para Se provar algo em lógica de
00:02:22
predicado é tentar trazer dessa lógica
00:02:25
de predicado para um esquema de lógica
00:02:27
proposicional para situações
00:02:28
particulares então é retirar os
00:02:31
modificadores e manipular a gente faz
00:02:33
isso retirando os quantificadores e
00:02:35
manipulando as fórmulas bem informadas
00:02:37
sem esses codificadores e depois a gente
00:02:40
retorna com eles dependendo da conclusão
00:02:42
que a gente quer chegar para isso então
00:02:44
nós vamos fazer esse processo de
00:02:46
retirada e Retorno dos quantificadores é
00:02:48
o que nós estamos chamando aqui de
00:02:50
particularização Universal e existencial
00:02:52
e generalização Universal e existencial
00:02:56
então no caso da particularização
00:02:58
Universal nós começamos dizendo que se
00:03:02
uma propriedade válida para todos os
00:03:04
elementos do domínio ela vai ser válida
00:03:06
por um caso particular então por exemplo
00:03:08
se P de x é
00:03:11
o aluno X é alto e ter tudo é um aluno
00:03:16
Então tudo é alto porque tá dizendo aqui
00:03:19
que para todo x aluno ele é alto
00:03:22
Então esse T ele pode ser como Eu
00:03:25
mencionei o Túlio um elemento constante
00:03:27
desse domínio ou pode ser uma variável
00:03:30
só que aí temos que considerar algumas
00:03:32
restrições por exemplo se ter formou uma
00:03:34
variável ela não deve estar no escopo de
00:03:36
um quantificador para ter eu não vou
00:03:39
poder usar como uma variável por um caso
00:03:42
específico uma variável que já está
00:03:44
sendo quantificada anteriormente bom
00:03:48
começando com o caso simples todos os
00:03:50
Homens São Mortais Sócrates é humano
00:03:52
portanto Sócrates é mortal como vimos na
00:03:55
última aula vamos representar isso aqui
00:03:57
com predicados no caso MX é mortal hdx é
00:04:02
humano e s para identificar o Sócrates
00:04:05
dentro desse domínio bom
00:04:08
todos os Homens São Mortais então para
00:04:10
todo x se ele é homem então ele é mortal
00:04:13
então é a maneira da gente interpretar
00:04:15
isso aqui representar essa esse
00:04:17
argumento conforme já vimos na última
00:04:20
aula ponto e Sócrates é humano então
00:04:24
aqui particularizamos essa propriedade
00:04:26
para Sócrates portanto
00:04:30
Sócrates é mortal agora que
00:04:33
representamos o argumento usando lógica
00:04:37
de predicados vamos deduzir bom a minha
00:04:41
hipótese nesse caso vai ser para todo x
00:04:43
h x implica em MX e HS ocorre Beleza o
00:04:49
que eu vou fazer retirar usar na nossa
00:04:52
estratégia Nossa abordagem geral retirar
00:04:55
o quantificador Universal então eu
00:04:57
particularizo se ela é válida para todo
00:05:00
mundo ela vai ser válida por Sócrates e
00:05:04
eu escolhi o software justamente porque
00:05:05
eu já tenho uma propriedade relacionada
00:05:07
a ele se isso aqui é válido para todo
00:05:09
mundo então vai ser Válido por Sócrates
00:05:11
através da particularização Universal e
00:05:14
agora eu aplico modo disponíveis na
00:05:16
linha dois e três deduzindo que Sócrates
00:05:19
é mortal é mortal certo na linha 4 bom
00:05:24
dessa forma
00:05:27
nós vimos um caso aqui onde não tinha
00:05:31
nenhuma restrição a ser observada agora
00:05:34
se ter for uma variável ele não deve
00:05:36
estar no escopo de um quantificador para
00:05:38
ter por exemplo um exemplo aqui de uso
00:05:42
incorreto seria nós temos aqui para
00:05:44
todos x existe o x top P XY ocorre
00:05:47
beleza para todo x eu quero
00:05:49
particularizar aí eu vou e particularizo
00:05:51
para o y só que o y já tá sendo
00:05:54
quantificado aqui então essa
00:05:56
particularização Universal ela tá
00:05:58
incorreta nesse um exemplo mais palpável
00:06:01
disso se pxy fosse x menor que Y bom
00:06:06
para todo x existe um Y tal que pxy
00:06:09
ocorre isso é verdade
00:06:11
mas se nesse processo de dedução eu
00:06:14
tentasse inferir isso por exemplo usando
00:06:17
constantes ou usando variáveis Ok
00:06:21
deixando claro que essas variáveis estão
00:06:24
seguindo isso aqui então eu tô
00:06:26
considerando todo B é maior que a por
00:06:28
exemplo a mais um agora se eu
00:06:32
particularizo por um Y que é um Y que já
00:06:35
tá sendo usado uma variável livre que já
00:06:37
tá sendo usado em outro modificador eu
00:06:39
caio numa situação como essa que vai ser
00:06:41
falsa
00:06:42
na particularização existencial
00:06:46
eu tenho que se existe a propriedade é
00:06:50
válida para pelo menos algum elemento
00:06:51
esse elemento é a por exemplo eu posso
00:06:54
dizer que ele é o elemento A então a é
00:06:57
uma variável ou um símbolo constante
00:07:00
Qual que é a restrição deve ser a
00:07:03
primeira regra a usar então em geral
00:07:05
aqui o que se diz é o seguinte quando a
00:07:08
gente vai
00:07:09
aplicar a particularização existencial
00:07:12
numa demonstração o ideal é que ela seja
00:07:15
feita primeiro então que nem aqui eu
00:07:17
tenho duas hipóteses um envolvendo
00:07:19
quantificador Universal e outro
00:07:21
envolvendo um quantificadores
00:07:22
existencial eu vou particularizar para
00:07:25
esse aqui primeiro para evitar problemas
00:07:28
na frente por exemplo se essa
00:07:30
propriedade aqui existe o y que atende
00:07:33
essa propriedade e eu falar que esse Y é
00:07:36
o a
00:07:37
que é levada para a eu sei que agora eu
00:07:40
posso por exemplo afirmar que se para
00:07:42
todo x essa propriedade válida ela vai
00:07:45
ser válida para o ar que eu
00:07:47
particularizei aqui
00:07:49
então eu aplico a particularização
00:07:51
universal para essa mesma constante e
00:07:54
agora cair um esquema
00:07:58
de lógica entre aspas e proposicional no
00:08:01
sentido que agora eu tô trabalhando com
00:08:03
algo definido posso aplicar modos pôneis
00:08:06
deduzir o que de a
00:08:10
e pronto tenho a minha a dedução final
00:08:13
na generalização Universal
00:08:17
eu aqui eu tenho que tomar mais cuidado
00:08:19
no sentido de que eu vou de um caso
00:08:21
particular falar que é válido para todo
00:08:24
mundo para isso então eu vou ter que ter
00:08:27
restrições tomar cuidado com restrições
00:08:29
relacionadas ao predicado Então nesse
00:08:33
caso por exemplo não pode ter sido não
00:08:37
pode ter sido deduzida de hipóteses e
00:08:39
onde X é uma variável livre e não pode
00:08:42
ter sido deduzida via equivalência de
00:08:45
uma fórmula bem formular Não desista
00:08:47
também é uma variável Então eu tenho que
00:08:49
dar uma muito cuidado na generalização a
00:08:52
partir de uma variável Livre
00:08:55
começar por um caso onde vai ser válido
00:08:58
eu tenho aqui essa argumento eu separo
00:09:02
hipótese hipótese certo
00:09:06
particularizou a linha usa
00:09:09
particularização Universal na linha 1 ok
00:09:11
uso na linha 2 tranquilo aplica o
00:09:15
modsponentes na linha 3 e 4 e agora
00:09:17
Observe eu posso generalizar para o
00:09:21
pediatra porque porque esse esse quediar
00:09:25
o uso desse q de a ele não tá sendo
00:09:28
feito a partir de variáveis Livres o x
00:09:31
aqui tá quantificado para o x aqui nessa
00:09:36
relação de implicação tá quantificado
00:09:38
quando eu obtive o pediaque o pediar a
00:09:41
mesma coisa tá quantificado não são
00:09:44
variáveis que estão livres
00:09:46
Então nesse contexto eu posso retomar
00:09:49
generalização Universal adicionar
00:09:53
generalização Universal aqui no PX bom
00:09:58
eu não vou poder fazer isso se o x for
00:10:01
uma variável livre e qual que seria esse
00:10:04
contexto eu tenho aqui a hipótese PX é
00:10:07
verdadeira repare eu tenho hipótese P de
00:10:09
X é verdadeira onde x eu não tô dizendo
00:10:11
que X é o João é uma constante X é uma
00:10:15
variável livre eu não quantifiquei essa
00:10:18
variável como é que se eu não
00:10:20
quantifiquei essa variável como é que eu
00:10:21
posso afirmar que ela vai valer essa
00:10:23
propriedade vai valer para qualquer tipo
00:10:24
de x
00:10:26
Então você está incorreto tá um outro
00:10:29
exemplo aqui né onde Eu Não Posso
00:10:32
deduzir e equivalência a partir de uma
00:10:34
fórmula bem informada no X é variável
00:10:36
livre então aqui nesse caso a gente tem
00:10:39
essa propriedade que x y e observem que
00:10:42
o que que eu faço aqui eu tenho
00:10:48
eu vou partir da linha 1 eu aplico a
00:10:52
particularização Universal E aí eu tenho
00:10:55
aqui o x Mas eu deixei o x não como uma
00:10:58
constante uma variável livre eu retirei
00:11:00
o quantificador
00:11:03
tudo bem só que agora o que que eu faço
00:11:06
eu pego o meu existe Y substitui por uma
00:11:09
constante A então eu tô dizendo agora
00:11:12
que esse x variável ali
00:11:14
variável livre está se relacionando com
00:11:17
esse a caso particular de quando existe
00:11:19
um livro
00:11:21
Beleza agora eu vou dizer que esse x se
00:11:24
relaciona com o a Qualquer que seja esse
00:11:26
x isso nem sempre vai ser verdadeiro tá
00:11:30
porque o que diz a foi obtida via
00:11:32
particularização existencial no passo 2
00:11:35
onde x era uma variável livre aqui
00:11:39
tá nesse caso o que que acontece Vamos
00:11:42
tentar dar um exemplo mais claro eu
00:11:44
tenho aqui um existe Y que x y supor que
00:11:48
seja x + y = 0 é verdadeiro eu sei que
00:11:52
isso aqui vai ser válido para um X que
00:11:55
seja igual a menos y agora quando eu
00:11:59
particularizo para a isso só passa a
00:12:03
valer para x igual a menos a E aí como
00:12:05
que desse ponto dessa particularização
00:12:08
com x variável livre eu vou agora
00:12:11
generalizar que para todo x isso vai
00:12:15
valer Isso só vai valer para x igual a
00:12:17
menos a
00:12:18
tá bom e a generalização
00:12:22
existencial a generalização existencial
00:12:25
eu tenho que ela já é mais leve digamos
00:12:29
assim de p de x ou P de a de um X uma
00:12:32
variável livre ou pedia a um valor
00:12:35
constante Eu Posso deduzir o que existe
00:12:37
pelo menos um X que seja x livre mas tem
00:12:41
pelo menos um caso
00:12:42
para esse x que ele ocorre que PX ocorre
00:12:45
beleza Qual seria a restrição nesse caso
00:12:48
para ir de pa para ir de pa no caso da
00:12:52
Constante para existe x não pode
00:12:54
aparecer em PA ou seja Considerando o pa
00:12:58
aqui que o pa pode estar representando
00:12:59
um predicado que não é só um na área
00:13:02
binário
00:13:03
Então nesse caso
00:13:06
vamos ilustrar como exemplo mais simples
00:13:09
aqui ó eu tenho que para todo x p x
00:13:11
implica em existe um XP x meio Óbvio Mas
00:13:15
vamos justificar isso a minha hipótese
00:13:18
para todo x existe
00:13:20
particular isso particularização
00:13:22
Universal com x variável livre aqui no
00:13:25
caso só que tudo bem Tem uma variável
00:13:28
livre eu posso agora dizer que existe
00:13:31
pelo menos Justiça ao que precisa corre
00:13:34
sem problema agora o caso que não
00:13:38
satisfaz uma das restrições
00:13:41
eu tenho aqui um predicado binário agora
00:13:43
a y o y é uma variável Y variável livre
00:13:48
e o ar é uma constante então eu vou e
00:13:52
digo que existe um Y
00:13:56
relacionada a esse agora já que o a
00:13:59
ocorre Então existe um Y tal que isso
00:14:01
aqui ocorre não
00:14:04
né porque o meu Y ele já aparecia aqui
00:14:08
na propriedade já parecia na propriedade
00:14:12
Então dessa forma eu caí de novo naquele
00:14:15
caso se eu tenho um pxy X se for pedir y
00:14:21
zero oky verdadeiro mas se for pedir Y
00:14:25
já é falso certo
00:14:29
Bom agora eu vou apresentar uma série de
00:14:32
exemplos aplicando as regras começar por
00:14:35
alguns exemplos de uso incorreto Por
00:14:38
exemplo você pode querer aplicar Como Eu
00:14:41
mencionei né retirar o quantificadores
00:14:43
existencial dessa forma o que não
00:14:46
estaria Ok por quê Porque a gente está
00:14:49
tirando o fato da propriedade de existir
00:14:52
um X para propriedade b e existe um X
00:14:55
para propriedade que não quer dizer que
00:14:58
seu particularizo para o p Eu também tô
00:15:02
particularizando porque nesse caso
00:15:04
porque eu tenho que existe um a que
00:15:07
satisfaz PX beleza mas não
00:15:10
necessariamente o mesmo ar que satisfaz
00:15:12
a propriedade que Então nesse caso o
00:15:16
ideal aqui era ter um P.A e PB porque
00:15:19
não necessariamente
00:15:21
p e que vão ser satisfeitas para o mesmo
00:15:24
objeto elemento a desse domínio tá então
00:15:28
o escopo do primeiro computador
00:15:29
existencial não pode ser estendido ao
00:15:32
resto da Fórmula bem formulada
00:15:34
outro exemplo aqui é por exemplo Eu
00:15:38
mencionei vamos retirar então o
00:15:40
quantificadores existencial primeiro
00:15:41
sempre que possível porém aqui nesse
00:15:44
caso ele tá dentro do escopo desse para
00:15:47
todo x
00:15:49
existe um Y tal que XY ocorre então eu
00:15:53
não posso primeiro particularizar para o
00:15:57
existencial nesse caso então
00:15:59
quantificadores essencial no Passo 1 não
00:16:01
está à frente ele está dentro de um
00:16:04
contexto desse para todo X então isso
00:16:06
aqui também não tá correto bom agora
00:16:10
para a gente aplicar um pouquinho as
00:16:12
regras observem que eu vou um exemplo
00:16:15
bem simples aqui eu tenho essa hipótese
00:16:17
e vou agora destrinchar aqui separando
00:16:19
os codificadores então eu começo
00:16:23
particularizando o PX PX que nesse caso
00:16:27
vai ficar que a nesse caso válido porque
00:16:30
o para todo x se refere
00:16:33
PX e que X então se existe um a se
00:16:37
existe se vale para todo x vai existir
00:16:40
para um a
00:16:42
PPA e que a porque aqui eu tô para todo
00:16:46
se refere essas duas essas duas
00:16:49
propriedades simultaneamente
00:16:51
com isso eu posso agora aplicar
00:16:53
simplificação e deduzir que pa se isso
00:16:57
aqui é verdadeiro p a é verdadeiro que a
00:17:00
é verdadeiro dessa forma agora eu posso
00:17:03
retornar com quantificador é universal
00:17:07
então eu posso generalizar usar
00:17:10
generalização Universal já que o ar não
00:17:13
foi deduzido a partir de uma variável
00:17:15
livre então
00:17:17
eu posso generalizar para o p posso
00:17:21
generalizar porque e compor através de
00:17:24
uma conjunção a partir da linha 5 e 6
00:17:28
um outro exemplo aqui eu tenho S
00:17:31
hipótese existe x tal qrx ocorre essa
00:17:35
segunda hipótese que na verdade é uma
00:17:37
negação de tudo que tá aqui dentro do
00:17:40
existe x tal que RX e SX ocorre eu tô
00:17:45
negando isso Observe que A negação se
00:17:47
aplica tudo nesse caso Então a primeira
00:17:50
coisa que eu faço é aplicar aquele
00:17:52
equivalência que nós vimos na última
00:17:54
aula de negar uma expressão Em lógica de
00:17:58
predicado onde nesse caso nós negamos o
00:18:01
quantificador que sendo existencial
00:18:03
passa a ser Universal e o predicado
00:18:06
relacionado como aparece aqui na linha 3
00:18:09
dessa forma agora eu posso começar a
00:18:12
remover os quantificadores eu começo
00:18:16
pela linha 1 fazendo nesse caso né eu
00:18:19
tenho uma existencial e um Universal eu
00:18:21
começo pela existencial particularizando
00:18:24
para a depois
00:18:27
eu particularizo para o Universal usando
00:18:30
esse mesmo a sendo que aqui agora eu
00:18:34
posso por exemplo aplicar a lei de
00:18:36
Morgan na linha 5 e em seguida a regra
00:18:44
a equivalência condicional então eu
00:18:46
tenho que isso aqui eu nego primeiro
00:18:49
termo troco pela implicação mantém o
00:18:52
segundo termo agora eu posso aplicar
00:18:54
modos phones na linha 4 e 7 deduzindo s
00:18:59
a negado e se ocorre Não Há tal que essa
00:19:04
negada é verdadeira eu vou poder dizer
00:19:06
que existe um X tal que SX negado ocorre
00:19:11
nesse caso também não estou violando
00:19:14
nenhuma das restrições relacionadas não
00:19:17
temos aqui contexto de nenhuma variável
00:19:19
livre por exemplo
00:19:21
bom
00:19:22
dessa forma todos os conceitos exemplos
00:19:25
apresentados Aqui foram baseados no que
00:19:29
é descrito na sessão 1.4 do material
00:19:31
básico Eu recomendo que vocês leiam
00:19:35
Espero que tenham entendido e nos
00:19:37
encontramos na próxima aula muito
00:19:39
obrigado
00:19:39
[Música]
