Na lógica de predicados, as regras de dedução permitem partir de hipóteses com quantificadores e chegar a conclusões verdadeiras dentro de um domínio. A ideia central é manipular quantificadores para reduzir problemas a situações puramente proposicionais (sem quantificadores). Dois casos centrais são:
Para provar algo em lógica de predicados, muitas vezes “retiramos” os codificadores (quantificadores) e manipulamos as fórmulas como se fossem proposicionais, usando apenas as regras de dedução da lógica proposicional. Depois, reintroduzimos os quantificadores conforme a conclusão desejada. A ideia é: em uma demonstração, começamos aplicando as regras de instânciação (para um indivíduo específico) e, ao final, generalizamos. Exemplo: a partir de ∀x(Hx → Mx) e Hb (Socrates é humano) deduzimos Hb → Mb, e com Hb aplicamos Modus Ponens para obter Mb (Socrates é mortal).
A generalização universal (∀-Intro) permite passar de uma fórmula com variável livre para uma generalização sobre todo x, mas apenas quando x não ocorre livremente em hipóteses não encerradas (ou seja, não depende de um objeto específico). A generalização existencial (∃-Intro) permite obter ∃x Φ(x) a partir de Φ(t). Há também restrições adicionais para evitar sleight of hand com escopos de quantificadores (ex.: não generalizar a partir de uma variável livre que depende de uma hipótese aberta). Além disso, negação de quantificadores segue equivalências usuais: ¬∀x Φ(x) ↔ ∃x ¬Φ(x) e ¬∃x Φ(x) ↔ ∀x ¬Φ(x).
Observações úteis: - Utilize a particularização universal apenas para termos que não violam o escopo de variáveis livres (evite usar uma constante que já esteja sob quantificação). - Use a particularização existencial com um novo símbolo constante que não tenha aparecido previamente. - Ao aplicar ∀-Intro, garanta que a variável não esteja livre em hipóteses não encerradas. - Evite generalizar a partir de uma expressão que depende de uma variável livre situada dentro de uma hipótese suspensa.
Sobre a regra de particularização universal (∀-Elim), assinale a alternativa correta.
Resposta correta: B) De ∀x Φ(x) deduz Φ(t) para qualquer termo t válido no domínio.
Justificativa: Instanciação universal permite aplicar Φ(x) a um termo específico t que pertença ao domínio de discurso.
Sobre a regra de generalização universal (∀-Intro), assinale a alternativa correta.
Resposta correta: B) ∀-Intro requer que x não ocorra livremente em hipóteses não encerradas.
Justificativa: A generalização universal só é válida quando a variável ligada x não depende de uma hipótese aberta; caso contrário, a generalização pode ser inválida.
Sobre cuidados e restrições no uso de quantificadores, assinale a alternativa correta.
Resposta correta: B) ∃-Intro pode depender de um termo livre que aparece dentro de uma hipótese; cuidado com o escopo ao combinar com outras regras.
Justificativa: Ao introduzir ∃x Φ(x) a partir de Φ(t), é essencial que t não viole condições de escopo ou dependência de hipóteses não encerradas.
Considere as premissas: ∀ 𝑥 ( 𝑃 ( 𝑥 ) → 𝑄 ( 𝑥 ) ) ∀x(P(x)→Q(x)) ∃ 𝑥 𝑃 ( 𝑥 ) ∃xP(x) Qual alternativa descreve corretamente como concluir: ∃ 𝑥 𝑄 ( 𝑥 ) ∃xQ(x)
Resposta correta: B) Dado ∀x (P(x) → Q(x)) e ∃x P(x), usa-se ∃-Elim com uma constante nova c para obter P(c) e Q(c); então se aplica ∃-Intro para ∃x Q(x).
Justificativa: A demonstração correta do enunciado envolve introdução/exploração de um witness pela regra de ∃-Elim, seguido por instância de P(c) → Q(c) e obtenção de Q(c), culminando em ∃x Q(x).
Olá,<|pt|> a Luanas e Amunos do Conselho Fundamentos Matemáticos para a Computação.
Nesta video-áulio, eu vou falar da lógica de predicaros.
Começá apresentando regros de dedução, considerando a particularização universal e a particularização existencial, depois apresentar a generação universal e existencial.
Por último, eu vou instrar a uso dessas regras através de exemplos.
Bom, diferente da lógica proposicional que podíamos provar a validade de um argumento usando, por exemplo, uma tabela de idade, na lógica de predicados nós utilizamos um sistema de forma ou um sistema de rebre de dedução para partir dessas hipóteses e chegar a conclusão desejada.
Para isso, o tassistema deve ser correto no sentido de que apenas há com menos valedos vão ser demonstrávios, e as hipóteses verdadeiras dentro de um domínio de interpretação vão levar a aplicação das regras de dedução a conclusão que também são verdadeiras dentro desse domínio de interpretação.
Então também se trata de um sistema que é completo no sentido de que todo argumento vale do que deve ser demonstrado.
Além disso, ele busca ser tratável no sentido de que conseguimos realizar até as deduções no conjunto aplicando o convinto de regras.
As regras de equivalência e as regras de diferença que vêm no jovem na lógica proposicional ainda vão fazer parte desse sistema de lógica de forma ou de dedução na lógica de predicados.
Então, por exemplo, aqui nós temos esse argumento na lógica de predicados onde podemos identificar aqui essa hipóteses e essa aqui.
Então temos duas hipóteses.
Se observarmos, é sendo essa hipóteses verdadeira e essa implicação aqui também verdadeira.
Esse antecedente válido nos leva a inferir que esse consequente aqui também é válido, que é a regra de nossos póteses que vêm sendo aplicada na linha 1 e 2.
Mas a abordagem geral para se provar algo em lógica de predicados é tentar trazer dessa lógica de predicado para o esquema de lógica proposicional para as situações particulares.
Então é retirar os codificadores e manipulando.
A gente faz isso retirando os codificadores e manipulando as formas bem formados sem esses codificadores.
Depois, a gente retorna com eles e dependendo da conclusão que a gente quer chegar.
Para isso, nós vamos fazer esse processo de retirar, de retorno dos codificadores.
Nós estamos chamando de partícula deização universal e existencial e generalização universal e existencial.
Então, no caso da partícula deização universal, nós começamos dizendo que, se uma propriedade válida para todos os elementos do domínio, ela vai se revar e dá por um caso particular.
Então, por exemplo, se pdx é o aluno x é alto e t é um aluno, então, o t h é alto.
Porque está dizendo aqui que para todo x, o aluno é alto.
Então, este t pode ser, como eu mencionei o t h, um elemento constante desse domínio, ou pode ser uma variável.
Só que aí tem de que considerar algumas restrições.
Por exemplo, se t for uma variável, ela não deve estar no escopo de um pontificador para ter.
Eu não vou poder usar como uma variável, por um caso específico, uma variável que já está sendo quantificada anteriormente.
Bom, começando com um caso simples.
Todos os homens são mortais sócrates é humano, portanto sócrates é mortal.
Como vimos na última aula, vamos representar isso aqui, com predicados, no caso, o mxx é mortal, hxx é humano.
E esse para eventificar o sócrates desse domínio.
Bom, todos os homens são mortais, então, para todo x, se ele é homem, então, ele é mortal.
Então, é a maneira de interpretar isso aqui, representar esse argumento, como, como já vimos na última aula.
Ponto e sócrates é humano.
Então, aqui, particularizamos essa propriedade para sócrates.
Portanto, sócrates é mortal.
Agora, aqui, representamos o argumento usando lógica de predicados, vamos deduzir.
Bom, a minha hipótese, nesse caso, vai ser para todo x, hx, impliquim, mx, e hx ocorre.
Beleza.
O que eu vou fazer? Retirar, usando a nossa estratégia, nossa abordagem geral, retirar o quantificador universal.
Então, eu particularizo.
Se ela é válida para todo mundo, ela vai ser válida para o sócrates.
E eu escolhi o sócrates justamente, porque eu já tenho uma propriedade relacionada a ele.
Se isso é válido para todo mundo, então, vai ser válido para o sócrates, através da particularização universal.
E agora eu aplico modos pónios na linha 2 e 3, deduzindo que sócrates é mortal.
É mortal, certo, na linha 4.
Bom, dessa forma, nós vimos um caso aqui onde não tinha nenhuma restrição a ser observada.
Agora, se ter fome a variável, ele não deve estar no escopo de um quantificador para ter.
Por exemplo, um exemplo aqui de uso incorreto seria, nós temos aqui para todo x, existe o x, tal que px, e o só ocorre.
Beleza, para todo x, eu quero particularizar.
Aí, eu vou ir particularizo para o íbselo.
Só que o íbselo já está sendo quantificado aqui.
Então, essa particularização universal, ela está incorreta.
Mesmo um exemplo mais palpável disso, se px, e o só, fosse x menor que íbselo, bom, para todo x, existe um íbselo, tal que px, e o só ocorre.
Isso é verdade.
Mas, nesse processo de dedução, eu tentasse inferir isso.
Por exemplo, usando constantes ou usando variáveis, ok, deixando claro que essas variáveis estão seguindo isso aqui.
Então, eu estou considerando todo b, maior que a, por exemplo, a mais 1.
Agora, se eu particularizo para um íbselo, que é um íbselo que já está sendo usado em uma variável livre, que já está sendo usado em outro quantificador, eu caio numa situação como essa, que vai ser falsa.
Bom, na particularização existencial, eu tenho que, se existe a propriedade avaliada, para pelo menos algum elemento, esse elemento é a, por exemplo, eu posso dizer que ele é a, pelo elemento a.
Então, há uma variável ou um símbolo constante.
Qualquer restrição deve ser a primeira regra a usar.
Então, em geral, aqui, o que se diz é o seguinte, quando a gente vai aplicar a particularização existencial numa demonstração, o ideal é que ela seja feita primeiro.
Então, que nem aqui, eu tenho 2 hipóteses, não envolveram o quantificador universal e outro envolveram o quantificador essencial.
Eu vou particularizar para esse aqui primeiro, para evitar problemas na frente.
Por exemplo, se essa propriedade aqui é desistiuido, que atende essa propriedade, e eu falo que, se isso é o A, que é leválida para a, eu sei que agora, eu posso, por exemplo, afirmar que, se para todo x essa propriedade válida, ela vai ser válida para o A que eu particularizei aqui.
Então, eu aplico a particularização universal para essa mesma constante, e agora reparei caí no esquema de lógica, tem trecho, por exemplo, proposicional, no sentido que agora eu estou trabalhando com algo definido, posso aplicar modos ponens, deduzir o que é de A.
E pronto, tenho a minha dedução final.
Na generalização universal, eu tenho que tomar mais cuidado, no sentido de que eu vou de um caso particular, falar que é válido para todo mundo.
Para isso, então, eu vou ter que ter restrições, tomar cuidado com restrições relacionadas ao predicado.
Nesse caso, por exemplo, não pode ter sido o praticoro, não pode ter sido deduzida de hipótese onde x é uma variável livre, e não pode ter sido deduzida via equivalência de uma fórmula performal onde x também é uma variável livre.
Então, eu tenho que estar uma muito cuidada na generalização, a partir de uma variável livre.
Começar por um caso onde vai ser válido.
Eu tenho aqui essa argumento, eu separo hipótese, hipótese, certo? Particularizo universal, a linha usa a particularização universal na linha 1, ok, uso na linha 2, tranquilo, aplica modos ponens na linha 13 e 4, e agora observe, eu posso generalizar porque de A, porque, porque esse, esse que é de A, o uso desse que é de A, ele não está sendo feito a partir de variáveis livres.
O x aqui está quantificado para o x aqui, nessa relação de implicação, está quantificado quando eu obtive o que é de A aqui.
O pd A, a mesma coisa, está quantificado, não são variáveis que estão livres.
Então, nesse contexto, eu posso retomar a generalização universal.
A adicionar a generalização universal aqui no pd x.
Bom, eu não vou poder fazer isso se o x for uma variável livre.
E qual seria esse contexto? Eu tenho aqui hipótese, pd x é verdadeira, repare.
Eu tenho hipótese, pd x é verdadeira, onde x é não trizando que x é um João, é uma constante, o x é uma variável livre.
Eu não contifiquei essa variável.
Como é que se eu não contifiquei essa variável, como é que eu posso afirmar aquela variável na lei, essa propriedade, que vai valer para qualquer tipo x? Então, isso está incorreto.
Um outro exemplo aqui, onde eu não posso deduzir, que valência a partir de uma fórmula bem fórmula, não é uma variável livre.
Então, nesse caso, a gente tem essa propriedade que é de x, e observa que o que eu faço aqui? Eu tenho.
.
.
Eu vou.
.
.
parte da linha 1, eu aplico a particularização universal.
E aí, eu tenho aqui o x, mas eu deixei o x não, como uma constante uma variável livre.
Eu retirei o quantificador.
Tudo bem? Só que agora, o que eu faço? Eu pego, o meu existe, só substituo para uma constante A.
Então, eu estou dizendo agora que esse x variável e.
.
.
Solão? Variável livre, está se relacionando com esse A, caso particular de quando existe um íbito.
Beleza.
Agora, eu vou dizer que esse x se relaciona com A, qualquer que seja esse x.
Isso nem sempre vai ser verdadeiro.
Porque o que x foi obtido à via, a particularização extensional no passo 2, onde x era uma variável livre aqui.
Nesse caso, o que que acontece? Vamos tentar dar um exemplo mais clara.
Eu tenho aqui um x, um x, e um suponho que seja x, mas y é igual a zero.
É verdadeiro.
Eu sei que isso aqui vai ser válido para um x, que seja igual a menos y.
Agora, quando eu particularizo para A, isso só passa a valer para x igual a menos A.
E aí, como que desse ponto dessa particularização com x variável livre, eu vou agora generalizar que para todo x, isso vai valer.
Isso só vai valer para x igual a menos A.
E a generalização extensional.
A generalização extensional, eu tenho que ela já é mais leve, digamos assim, de px, o pd ádio, x é uma variável livre, o pd á é um valor constante, eu posso deduzir o que? Que existe pelo menos um x, seja, cix livre, as tempelulmendas um caso, para esse x que ele ocorre, que px ocorre.
Beleza.
Qual seria a restação nesse caso? Para ir de pA, para ir de pA, do caso da constante, para existe px, não pode aparecer em pA, ou seja, considerando o pA, o que o pA pode estar representando um predicado que não é só um nave, de nave, ter nário, em nero.
Então, nesse caso, vamos ilustrar, com um exemplo mais simples aqui, eu tenho que para todos os x px impliquem, existe um x px, meio óbvio, mas vamos justificar isso.
A minha hipótese para todo x, existe px, particulariz, particularização universal, com x variável livre aqui no caso, só que tudo bem, tem uma variável livre, eu posso agora dizer que existe pelo menos um x, tal que o px ocorre, sem problema.
Agora, o caso em que não satisfaz uma das restrições, eu tenho aqui um predicado binário agora, a y, o y é uma variável y, a variável livre, e o a é uma constante.
Então, eu vou e digo que existe um y, relacionado a esse a agora, já que o a ocorre, então, existe um y, não toque isso aqui ocorre, não.
Porque o meu y, ele já aparecia aqui na propriedade, já aparecia na propriedade.
Então, dessa forma, eu caio de novo naquele caso.
Se eu tenho px, o que é y, o que é x, se eu for px, zero, o que é y, o que é y, verdadeiro, mas se for px, o y já é falso, certo? Bom, agora eu vou apresentar uma série de exemplos, aplicando as regras, começaram por alguns exemplos de uso incorreto.
Por exemplo, você pode querer aplicar, como eu mencionei, retirar o continuador existencial dessa forma, porque não estaria ok, porque a gente está tirando o fato de dar propriedade, de existir o x para a propriedade p, e existir o x para a propriedade que não quer dizer que, se eu particularizo para o p, eu também estou particularizando por que nesse caso? Porque eu tenho que existir um x, satisfaz px, beleza, mas não necessariamente o mesmo x, satisfaz a propriedade que, então nesse caso, o ideal aqui era ter o pA e pB, porque não necessariamente a p, que é vão ser satisfeitas para um mesmo objeto, elemento a desse domínio, então, o escopo do primeiro continuador existencial não pode ser estendido ao resto da fórmula bem formulada.
Outro exemplo aqui, é, por exemplo, eu mencionei, e vamos retirar, então, o continuador existencial primeiro sempre que possível.
Porém, aqui nesse caso, ele está dentro do escopo, desse para todo x, existe um y toque, que x, y ocorre, então eu não posso primeiro particularizar para o ex-extencial nesse caso.
Então, o continuador extensional no passo 1 não está à frente, ele está dentro do contexto desse para todo x, então isso aqui também não está correto.
Bom, agora, para gente aplicar um pouquinho as regras, observem que eu vou, não exerPro bem simples aqui, eu tenho as repórtese, e vou agora distrinchar aqui separando os contificadores.
Então, eu começo particularizando o ProPX, que x, que nesse caso vai ficar P, aí que há nesse caso, o vale do porquê, o para todo x se refere, a Px é que x.
Então, se existe um y, se existe, se vale para todo x, vai existir para um a, P, P, A, e que há? Porque aqui eu estou, o para todo se refere a essas duas, essas duas, para treinar simultaneamente.
Com isso, eu posso agora aplicar, a simplificação, e deduzir que Px, isso aqui é verdadeiro, P, A é verdadeiro, que A é verdadeiro.
Dessa forma, agora, eu posso retornar com o contificador no universal.
Então, eu posso generalizar os a, generalização universal, já que o A não foi deduzido a partir de uma variável livre.
Então, eu posso generalizar ProP, posso generalizar ProQ, e compor a através de uma conjunção, a partir da linha 5 e 6.
Um outro exemplo aqui, porque tem S potas, e existe x, que é x.
Eu corre essa segunda hipótese, e que na verdade, é uma negação de tudo que está aqui dentro.
Do existe x, tal que Rx, e Sx, eu corre.
Eu estou negando isso, você sabe que a negação se aplica tudo.
Nesse caso, então, a primeira coisa que eu faço é aplicar aquela equivalência que nós vimos no ultimalo, de negar uma expressão inógica de predicado, onde, nesse caso, nós negamos o quantificador que sendo o existencial passa a seu universal e o predicado relacionado, como aparece aqui na linha 3.
Dessa forma, agora, eu posso começar a remover os quantificadores.
Então, eu começo pela linha 1 fazendo, nesse caso, eu tenho um existencial e o universal, eu começo pelo existencial, particularizando para a, depois, eu particularizo para o universal, usando esse mesmo a, sendo que, aqui, agora, eu posso, por exemplo, aplicar a lei de demógar, na linha 5, e, em seguida, a equivalência condicional.
Então, eu tenho que isso aqui, porque nego primeiro termo, troca o opo e na implicação, mantém o segundo termo.
Agora, eu posso aplicar modos pôrninhos na linha 4 e 7, deduzindo esta ligada.
E se ocorre uma tal que esta ligada, é verdadeira, eu vou poder dizer que existe um x tal que esta x negada, concorra, nesse caso, também não estou violando nenhuma da gestrição relacionada, e não temos aqui contexto de nenhum novo alívio, por exemplo.
Bom, dessa forma, todos os conceitos, exemplos apresentados aqui, estão se foram baseados no que é descrito, na seção 1.
4 do material base, que eu recomendo que vocês leiam.
Espero que tenham entendido, e nos encontramos na próxima aula.
Muito obrigado.