Introducao a Sistemas Logicos CQC Slides Aula - Faculdade Cotemig

Introducao a Sistemas Logicos Prof Julio Cesar da Silva Slides 6 CQC Texto baseado no Livro Introducao a Logica de Cezar A Mortari Faculdade Cotemig Belo HorizonteMG Prof Julio Cesar da Silva Introducao a Sistemas Logicos 1 60 Sumario 1 Introducao ao CQC Prof Julio Cesar da Silva Introducao a Sistemas Logicos 2 60 DICA DE ESTUDO 1 Faca anotacoes durante a aula 2 Estude todos os dias 10 ou 15 minutos 3 Durante o estudo leia os slides leia as anotacoes e refaca todos os exercıcios 4 Repita um exercıcio ate que vocˆe consiga acertalo sem olhar a resposta antes 5 Somente depois de acertar um exercıcio sem olhar a resposta passe para outro exercıcio 6 Lembrese que estudar e igual a ir a uma academia estude todos os dias e repita os exercıcios ate o dia da prova 7 Se vocˆe repete um exercıcio e acertar sem olhar a resposta entao vocˆe esta preparado ou preparada para a prova Prof Julio Cesar da Silva Introducao a Sistemas Logicos 3 60 Introducao Informal ao CQC Considere o seguinte argumento P1 Chimakonam e filosofo Conclusao Alguem e um filosofo Formalizado no CPC P1 A Conclusao B A B ou A B Intuitivamente este argumento e valido A validade intuitiva do argumento depende justamente de levarmos em consideracao a estrutura interna das suas sentencas Ou seja o sujeito Chimakonam e o alguem que e filosofo Para isso precisamos mudar do CPC para o CQC Prof Julio Cesar da Silva Introducao a Sistemas Logicos 4 60 Introducao Informal ao CQC No CQC teremos um sımbolo que representara os indivıduos os sujeitos que constituem os sujeitos das sentencas bem como sımbolos que representam propriedades que esses indivıduos podem ter por exemplo ser filosofo Teremos tambem sımbolos logicos ja apresentados no CPC isto e os operadores logicos Teremos tambem novos sımbolos logicos para representar todos e algumalguem O argumento formalizado no CQC P1Fc Conclusao xFx Prof Julio Cesar da Silva Introducao a Sistemas Logicos 5 60 CQC Outros exemplos de traducoes para o CQC em comparacao ao CPC Prof Julio Cesar da Silva Introducao a Sistemas Logicos 6 60 Paula para Pensar Traduza as frases abaixo para o CQC 1 Brunno e fısico 2 Rafael e programador 3 Giovanna e desenvolvedora 4 Danilo e Administrador de Banco de dados 5 Adriano e Gestor de Tecnologia da Informacao 6 Leticia e analista de sistemas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 7 60 CQC e conhecimento Uma segunda maneira de usar o CQC alem de ser para analisar a validade de argumentos e para sistematizar o conhecimento que temos a respeito de algum domınio de estudo bem como fazer inferˆencias a respeito desse domınio obtendo etao conhecimento novo Esse conhecimento consiste em proposicoes que falam de indivıduos ou objetos que se supoe existirem e das propriedades que eles tˆem ou deixam de ter e das relacoes em que estao ou deixam de estar Ou seja quando estamos fazendo uma teoria a respeito de um domınio de estudo num sentido bem amplo de teoria Prof Julio Cesar da Silva Introducao a Sistemas Logicos 8 60 CQC e conhecimento Para fazer o que foi listado no slide anterior devemos 1 Delimitar um universo de discurso isto e que objetos ou indivıduos se pretende falar 2 Especificar que propriedades deles e que relacoes entre eles nos interessam estudar 3 Esse processo pode ser chamado de conceitualizacao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 9 60 CQC Definicao A linguagem do calculo de predicados de primeira ordem consiste em 1 um conjunto de constantes individuais 2 para cada numero natural n 0 um conjunto enumeravel de constantes de predicado n arias 3 um conjunto enumeravel de variaveis individuais 4 operadores logicos 5 quantificadores 6 sinais de pontuacao As expressoes 3 4 5 6 sao chamados sımbolos logicos enquanto aquelas em 1 e 2 sao chamadas sımbolos nao logicos Prof Julio Cesar da Silva Introducao a Sistemas Logicos 10 60 Exemplo linguagem do Calculo de Predicados Sentenca Socrates e filosofo Traducao Fs s e uma constante individual que denota Socrates F e uma constante de predicado 1 aria que se aplica UMA VEZ a cada individuo Prof Julio Cesar da Silva Introducao a Sistemas Logicos 11 60 Exemplo linguagem do Calculo de Predicados Sentenca Alguem e filosofo Traducao xFx e o quantificador existencial Existe algo ou Existe alguem x e uma variavel individual F e uma constante de predicado 1 aria que se aplica UMA VEZ a cada individuo Prof Julio Cesar da Silva Introducao a Sistemas Logicos 12 60 Exemplo linguagem do Calculo de Predicados Sentenca Alguem e programador e Todo mundo e inteligente Traducao xFx yIy e o quantificador existencial e e o quantificador universal x e y sao variaveis individuais F e I sao constantes de predicado 1 aria e o operador logico da conjuncao e sao sımbolos de pontuacao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 13 60 CQC Predicados Prof Julio Cesar da Silva Introducao a Sistemas Logicos 14 60 CQC Predicados Prof Julio Cesar da Silva Introducao a Sistemas Logicos 15 60 CQC Predicados Prof Julio Cesar da Silva Introducao a Sistemas Logicos 16 60 Pausa para Pensar Traduza para o CQC as seguintes sentencas 1 Romeo ama Julieta 2 Alguem gosta de chocolate 3 Todo mundo assiste TV 4 Paulo e mais alto do que Antˆonio 5 Carla deu um brinquedo para lucas e Lara Prof Julio Cesar da Silva Introducao a Sistemas Logicos 17 60 CQC Definicao A linguagem do calculo de predicados de primeira ordem consiste em 1 um conjunto de constantes individuais 2 para cada numero natural n 0 um conjunto enumeravel de constantes de predicado n arias 3 um conjunto enumeravel de variaveis individuais 4 operadores logicos 5 quantificadores 6 sinais de pontuacao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 18 60 CQC As chamadas constantes individuais tˆem a funcao de designar indivıduos Uma vez que constantes individuais funcionam como nomes nao se pode usar a mesma constante para dois indivıduos diferentes Usaremos letras minusculas a t admitindo subscritos As variaveis funcionam gramaticalmente como as constantes porem obviamente elas nao sao nomes de indivıduos mas tˆem associado a si um domınio de variacao Usaremos letras minusculas de u ate z com ou sem subscritos As constantes individuais e variaveis individuais da linguagem do CQC sao denominados termos dessa linguagem Prof Julio Cesar da Silva Introducao a Sistemas Logicos 19 60 CQC Ter propriedades nos leva a usar constantes de predicado Usaremos letras maiusculas A T podendo admitir subscritos O sımbolo de predicado e escrito antes da constante individual exemplo Pc Sımbolos de predicado podem representar relacoes entre dois ou mais indivıduos Se forem dois sao predicados de grau 2 se forem trˆes sao predicados de grau 3 assim por diante Tambem chamados de binarios ternarios etc No geral dizemos que temos sımbolos de predicado unarios para propriedades binarios para relacoes entre 2 indivıduos ternarios para relacoes entre trˆes indivıduos n arios ou enarios relacoes entre n indivıduos para n um numero natural Prof Julio Cesar da Silva Introducao a Sistemas Logicos 20 60 Sintaxe do CQC Definicao Se P e um sımbolo de predicado n ario para algum numero natural n e t1 tn sao termos entao Pt1 Ptn e uma formula Formula atˆomica do CQC t1tn tambem sao metavariaveis que indicam termos quaisquer ex Fx Fs Maj etc x s a j sao termos F e predicado Prof Julio Cesar da Silva Introducao a Sistemas Logicos 21 60 CQC Definicao Formula i Se α e uma formula entao α e uma formula ii Se α e β sao formulas entao α β α β α β e α β sao formulas α e β sao metavariaveis usadas para indicar uma formula qualquer Definicao Se x e uma variavel e α e uma formula na qual x ocorre entao xα e xα sao formulas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 22 60 Pausa para Pensar Indique se e ou se nao e uma formula da linguagem do CQC Justifique a sua resposta 1 Gxy 2 Gab 3 axG 4 GPax 5 xGxy 6 yFy 7 Gxy 8 Fss 9 xyPx Fy 10 xyGxy Prof Julio Cesar da Silva Introducao a Sistemas Logicos 23 60 CQC Quantificadores O quantificado e chamado quantificador existencial e corresponde em linguagem natural as expressoes existe pelo menos um alguns algum alguem O quantificado e chamado quantificador universal e corresponde em linguagem natural as expressoes para todo qualquer que seja todos cada Com a introducao dos quantificadores temos entao um terceiro tipo se formula alem das atˆomicassimples e molecularescomposta as formulas gerais que iniciam por um quantificador Prof Julio Cesar da Silva Introducao a Sistemas Logicos 24 60 CQC Quantificadores Todos tˆem P xPx Ninguem tˆem P xPx ou xPx Alguem tˆem P xPx Alguem nao tem P xPx Nem todos tem P xPx ou xPx E possıvel identificar equivalˆencia entre as formulas como por exemplo dizer Alguem nao tem P equivale a Nem todos tˆem P Assim como Todos tˆe P se negado equivale a Alguem nao tem P Uma das maneiras de compreender os quantificadores e associar com as operacoes de conjuntos e os diagramas de Venn Prof Julio Cesar da Silva Introducao a Sistemas Logicos 25 60 CQC Quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 26 60 CQC Quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 27 60 CQC Quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 28 60 CQC Quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 29 60 CQC Quantificadores Sentencas moleculares ou compostas podem ser traduzidas da seguinte maneira Todo A e B xAx Bx Nenhum A e B xAx Bx Algum A e B xAx Bx Algum A nao e B xAx Bx Prof Julio Cesar da Silva Introducao a Sistemas Logicos 30 60 CQC Quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 31 60 CQC Quantificadores Sentenca Existe um peixe azul Parafrase logica Ha ao menos um x que e um peixe e e azul Traducao xPx Ax onde interpretamos P como a propriedade de ser peixe e A como a propriedade de ser azul Sentenca Existe um cachorro e um gato Parafrase logica Algo e um cachorro e algo e um peixe traducao xCx yPy onde interpretamos C como ser cachorro e P como ser peixe Prof Julio Cesar da Silva Introducao a Sistemas Logicos 32 60 CQC Quantificadores Existe um pinguim que mora na Antartida e nao gosta de frio Algum x que e pinguim e que mora na Antartida nao e um animal que gosta de frio xPx Ax Fx onde interpretamos P como ser pinguim A como mora na Antartida e F como gosta de frio Prof Julio Cesar da Silva Introducao a Sistemas Logicos 33 60 CQC Quantificadores Todo peixe vive na agua Para qualquer x se x e um peixe entao x vive na agua xPx Vx onde interpretamos P como ser peixe e V como vive na agua Todos os filhos de Joao sao estudantes Para qualquer x se x e filho de Joao entao x e estudante xFxj Ex onde interpretamos F como um predicado 2ario filho de E como um predicado 1ario ser estudante e j como sendo Joao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 34 60 CQC Quantificadores Nenhum filho adolescente de Joao e estudante Para qualquer x se x e adolescente e e filho de Joao entao x e nao e estudante xAx Fxj Ex Onde interpretamos A como um predicado 1ario ser adolescente F como um predicado 2ario filho de E como um predicado 1ario ser estudante e j como sendo Joao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 35 60 CQC Os gatos e os cachorros sao animais domesticos Para qualquer x que seja gato OU x que seja cachorro entao x e um animal domestico ATENC AO se usarmos o E estaremos assumindo que x pode ser cachorro e gato ao mesmo tempo Na linguagem do CQC nao podemos cometer esse erro logico mesmo sendo comum no portuguˆes xGx Cx Ax Interpretamos os predicados 1ario como G para ser um gato C para ser um gato e A para ser um animal domestico Prof Julio Cesar da Silva Introducao a Sistemas Logicos 36 60 Pausa para Pensar Traduza as sentencas a seguir para a linguagem do CQC usando a interpretacao sugerida 1 Alguns homens nao sao sinceros H para ser homem e S para ser sincero 2 Todas as mulheres sao inteligentes M para ser mulher e I para ser inteligente 3 Nenhum peixe e anfıbio P para ser peixe e A para ser anfıbio 4 Qualquer pessoa que seja persistente pode aprender logica para P ser pessoa T para ser persistente e L para aprender logica Prof Julio Cesar da Silva Introducao a Sistemas Logicos 37 60 CQC observacoes extras Um predicado zeroario nada mais e do que uma letra maiuscula isolada usadas em sentencas sem sujeito isto e nao atribuem algo a alguem Exemplo Esta chovendo Constantes de predicado zeroarias sao tambem chamadas de letras sentenciais O sımbolo de predicado nao faz parte da linguagem do CQC e uma variavel metalinguıstica ou variavel sintatica Prof Julio Cesar da Silva Introducao a Sistemas Logicos 38 60 LPO Linguagem de Primeira Ordem Definicao Uma linguagem de primeira ordem e qualquer subconjunto da linguagem do CQC que inclua todos os sımbolos logicos e pelo menos uma constante de Predicado Em cada domınio de investigacao em que estejamos pretendendo trabalhar em cada teoria que fazemos usamos um subcconjunto da linguagem de primeira ordem Como todas as linguagens de primeira ordem incluem os mesmos sımbolos logicos ao especificar uma delas basta que indiquemos quais sao seus sımbolos nao logicos Prof Julio Cesar da Silva Introducao a Sistemas Logicos 39 60 LPO Linguagem de Primeira Ordem Definicao Seja L uma linguagem de primeira Ordem Dizemos que i Se P e um sımbolo de predicado nario para um numero natural n e t1 tn sao termos entao Pt1 Ptn e uma formula atˆomica ii Se α e uma formula entao α e uma formula molecular iii Se α e β sao formulas entao α β α β α β e α β sao formulas molecular iv Se x e uma variavel e α e uma formula na qual x ocorre entao xα e xα sao formulas gerais v Nada mais e uma formula Prof Julio Cesar da Silva Introducao a Sistemas Logicos 40 60 Subformulas de uma LPO Definicao Sao subformulas imediatas i formula atˆomica nao tˆem subformulas imediatas ii a subformula imediata de α e α iii as sunformulas imediatas de o α β α β α β e α β sao α e β iv a subformula imediata de xα e xα e α Prof Julio Cesar da Silva Introducao a Sistemas Logicos 41 60 Formulas fechadas e Formulas abertas Os quantificadores agem apenas sobre a formula que inicia imediatamente apos a variavel do quantificador O ˆambito de acao de um quantificador e chamado de escopo do quantificador e pode ser como numa formula da forma xα ou xα o escopo do quantificador e α Dizemos que uma ocorrˆencia de uma variavel x e ligada numa formula α se x ou faz parte de um quantificador ou esta no escopo de um quantificador para x em α Dizemos que uma ocorrˆencia de uma variavel x e livre se x numa formula α esteja fora do escopo de qualquer quantificador para x Prof Julio Cesar da Silva Introducao a Sistemas Logicos 42 60 CQC Prof Julio Cesar da Silva Introducao a Sistemas Logicos 43 60 Semˆantica do CQC Quando buscamos apresentar a semˆantica do CQC devemos utilizar as nocoes de estrutura e verdade O papel das estruturas e o de especificar os valores semˆanticos desejados e dessa maneira nos permitir determinar se as formulas sao verdadeiras 1 ou falsas 0 Podemos portanto a partir das estruturas definir consequˆencia logica Prof Julio Cesar da Silva Introducao a Sistemas Logicos 44 60 Semˆantica do CQC Ao construir uma estrutura A para uma linguagem de primeira ordem L a primeira coisa a fazer e determinar o domınio das entidades sobre as quais estamos falando ou seja de terminar que indivıduos existem A esse domınio de entidades denominamos universo ou domınio da estrutura Usaremos letras goticas maiusculas para designar estruturas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 45 60 Semˆantica do CQC O universo UA de uma estrutura A e usualmente definido como um conjunto nao vazio com uma relacao adicional de ser contavel isto e enumeravel Fixado um universo o proximo passo e dizer como interpretar as expressoes basicas de uma linguagem com respeito a ele ou seja como dar a elas um valor semˆantico Isso e feito atraves de uma funcao de interpretacao IA que associa as constantes nao logicas de uma linguagem L certas coisas na estrutura A Prof Julio Cesar da Silva Introducao a Sistemas Logicos 46 60 Semˆantica do CQC Definicao Uma estrutura A para L e um par ordenado U I onde U e um conjunto nao vazio e contavel e I e uma funcao tal que i a toda constante individual c de L I associa um individuo Ic U ii a cada sımbolo de predicado zeroario letra sentencial S de L I associa um valor de verdade IS 1 0 iii a cada sımbolo de predicado unario P de L I associa um subconjunto IP U iv a cada sımbolo de predicado nario P de L I associa um subconjunto IP Un Prof Julio Cesar da Silva Introducao a Sistemas Logicos 47 60 Semˆantica do CQC Definicao Verdade de uma formula α e verdadeira na estrutura A sse Aα 1 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 48 60 Semˆantica do CQC Definicao Seja L uma linguagem de primeira ordem e A uma estrutura para L i AS 1 sse IS 1 onde S e um sımbolo de predicado zeroario ii APt 1 sse It IP onde P e um sımbolo de Predicado unario e t e um parˆametro iii APt1 tn 1 sse It1 Itn IP onde P e um sımbolo de Predicado nario para n 1 e t1 tn sao parˆametros Prof Julio Cesar da Silva Introducao a Sistemas Logicos 49 60 Semˆantica do CQC Definicao Seja L uma linguagem de primeira ordem e A uma estrutura para L iv Aα 1 sse Aα 0 v Aα β 1 sse Aα 1 ou Aβ 1 vi Aα β 1 sse Aα 1 e Aβ 1 vii Aα β 1 sse Aα 0 ou Aβ 1 viii Aα β 1 sse Aα Aβ ix Axα 1 sse Aαxi 1 para todo parˆametro i x Axα 1 sse Aαxi 1 para algum parˆametro i xi Aα 1 sse Ax1 xnα 1 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 50 60 Semˆantica do CQC Na definicao dos slides anteriores note que αxi denota o resultado de substituir as ocorrˆencias livres da variavel x em α pelo nome ou constante i A ultima clausula da definicao acima e a definicao de verdade para uma formula aberta Seja α uma formula aberta tal que x1 xn sejam as suas variaveis livres na ordem em que ocorrem em α Dizemos entao que x1 xnα e o fecho de α O fecho de uma formula aberta e uma formula universal Prof Julio Cesar da Silva Introducao a Sistemas Logicos 51 60 Semˆantica do CQC Definicao Uma formula α e valida ou logicamente verdadeira sse para toda estrutura A Aα 1 Uma formula α e uma contradicao ou logicamente falsa sse para toda estrutura A Aα 0 E finalmente uma formula α e uma contingˆencia sse nao e nem valida nem uma contradicao ou seja para alguma estrutura A Aα 1 e para alguma outra estrutura B Bα 0 Um outro aspecto importante e que no CQC as tabelas verdades nao conseguem lidar com quantificadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 52 60 Semˆantica do CQC Definicao Uma estrutura A e modelo de um conjunto de formulas Γ se para toda formula γ Γ Aγ 1 Ou seja uma estrutura e modelo de um conjunto de formulas se todas as formulas do conjunto sao verdadeiras nessa estrutura Atencao todas Podemos escrever que A e modelo de um conjunto Γ da seguinte maneira A Γ Podemos tambem dizer que uma estrutura e modelo de uma formula A α Prof Julio Cesar da Silva Introducao a Sistemas Logicos 53 60 Semˆantica do CQC Por exemplo o conjunto de formulas a seguir e satisfatıvel Γ Pa Qb Pb xPx Qx Considere a linguagem a b c P Q e uma estrutura Aα U I tal que U 2 3 4 e Ia 2 Ib 3 Ic 3 IP 2 3 e IQ 3 Evidentemente Pa e Pc sao verdadeiras nessa estrutura enquanto Pb e falsa Qc e verdadeira enquanto Qb e falsa Da verdade de Pa e Pc inferimos tambem que xPx Qx e verdadeira nessa estrutura Logo tal estrutura e um modelo co conjunto de formulas Γ listado anteriormente o que tambem faz com que esse conjunto seja satisfatıvel Prof Julio Cesar da Silva Introducao a Sistemas Logicos 54 60 Exercício 1 Seja 𝓛 a linguagem a b P Q M e seja 𝔄 U I uma estrutura para 𝓛 onde U ℕ é o conjunto dos números naturais ou seja 0 1 2 3 e a função interpretação I é como segue Ia 5 Ib 8 IP x ℕ x é par IQ x ℕ x é impar IM x y ℕ² x y Determine os valores de verdade das fórmulas nesta estrutura 1 Qa 2 Pa Mab Pb 3 xPx 4 xPx 5 yMxy 6 Px Qx Prof Júlio Cesar da Silva Introdução a Sistemas Lógicos 55 60 Exercıcio 2 Seja L a linguagem a b c A F G H G e seja B U I uma estrutura para L onde U 0 1 2 3 4 e a funcao interpretacao I e como segue Ia 0 Ib 2 Ic 4 IA verdadeiro IF 0 1 2 IG 2 4 IH 0 1 1 3 4 2 IK 1 1 2 2 2 4 Determine os valores de verdade das formulas nesta estrutura 1 Fa 2 Gb A 3 Hc 4 Kbbc 5 Fa Ga 6 Fa Hab Ga 7 Fa Kbbc 8 yFy 9 yFy 10 xGx 11 xHax Prof Julio Cesar da Silva Introducao a Sistemas Logicos 56 60 Exercıcio 3 Seja L a linguagem a b c A F G H G e seja B U I uma estrutura para L onde U 0 1 2 3 4 e a funcao interpretacao I e como segue Ia 0 Ib 2 Ic 4 IA verdadeiro IF 0 1 2 IG 2 4 IH 0 1 1 3 4 2 IK 1 1 2 2 2 4 Determine os valores de verdade das formulas nesta estrutura 1 xFx Gx 2 xFx Gx 3 Fx xGx 4 xFx yGy 5 xGx 6 xGx Fx 7 Hba xHbx 8 xKxxx 9 zkzab 10 Gx xKxxx 11 xyHxy Prof Julio Cesar da Silva Introducao a Sistemas Logicos 57 60 Referˆencias 1 Para Todxs httpsgithubcomGrupodeEstudosemLogicada UFRNParaTodxsNatal 2 SOUZA Sergio Guedes de org Logica de programacao algorıtmica 1 ed Sao Paulo SP Pearson 2014 Ebook Disponıvel em httpsplataformabvirtualcombrLeitorPublicacao22146pdf0 3 STEIN C S et al Matematica discreta para ciˆencia da computacao 1 ed Sao Paulo SP Pearson 2013 Ebook Disponıvel em httpsplataformabvirtualcombrLeitorPublicacao3824pdf0 4 ASCENCIO Ana Fernanda Gomes CAMPOS Edilene Aparecida Veneruchi de Fundamentos da programacao de computadores algoritmos PASCAL CC padrao ANSI e JAVA 2 ed Sao Paulo Pearson 2012 Ebook Disponıvel em httpsplataformabvirtualcombrLeitorPublicacao3272pdf0 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 58 60 juliocesarcotemigcombr Prof Julio Cesar da Silva Introducao a Sistemas Logicos 59 60 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 60 60