Introducao a Sistemas Logicos - CQC e Aplicacoes da Logica

Introducao a Sistemas Logicos Prof Julio Cesar da Silva Slides 7 CQC Texto baseado no Livro Introducao a Logica de Cezar A Mortari SEP Faculdade Cotemig Belo HorizonteMG Prof Julio Cesar da Silva Introducao a Sistemas Logicos 1 47 Sumario 1 CQC e Aplicacoes da Logica Prof Julio Cesar da Silva Introducao a Sistemas Logicos 2 47 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 47 CQC Prolog e IA Observe a seguinte arvore genealogica Prof Julio Cesar da Silva Introducao a Sistemas Logicos 4 47 CQC Prolog e IA Sua representacao esta na forma de um grafo que e uma estrutura de dados presente em Banco de Dados do tipo NoSQL Nessa estrutura os dados sao nome de pessoas que possuem a relacao de serem pais maes e filhos Sara e Mae de Isaque Abraao e pai de Isaque Portanto Isaque e filho de Sara e de Abraao Se ha informacao se ha relacao e existe um argumento entao podemos usar a logica o CQC e estruturas para fazer um modelo logico e consequentemente um modelo computacional Prof Julio Cesar da Silva Introducao a Sistemas Logicos 5 47 CQC Prolog e IA Seja L a linguagem P F M e seja B U I uma estrutura para L onde U Sara Abraao Isaque Ismael Esau Jac o Jos e e a funcao interpretacao I e como segue IP Sara Isaque Abraao Isaque Abraao Ismael Isaque Esau Isaque Jac o Jac o Jos e IF Sara IM Abraaoo Isaque Ismael Esau Jac o Jos e Nosso domınio U sera o banco de dados P sera a relacao binaria progenitor isto e Sara Isaque significa que Sara e progenitora de Isaque F para o predicado ser feminino e M para ser masculino Prof Julio Cesar da Silva Introducao a Sistemas Logicos 6 47 CQC Prolog e IA Podemos agora traduzir o nosso modelo para a linguagem Prolog que e usada para representar o conhecimento em projetos de Inteligˆencia Artificial Prof Julio Cesar da Silva Introducao a Sistemas Logicos 7 47 CQC Prolog e IA Podemos agora perguntar quem do domınio e mulher por meio da formula xFx traduzido para o Prolog Prof Julio Cesar da Silva Introducao a Sistemas Logicos 8 47 CQC Prolog e IA Podemos perguntar quem no domınio e pai ou mae ou seja progenitor de Isaque Comecamos com xyPxy definimos uma interpretacao para y como Iy Isaque Traduzindo para Prolog Prof Julio Cesar da Silva Introducao a Sistemas Logicos 9 47 CQC Prolog e IA E com base nas informacoes que no Prolog chamamos de FATOS podemos criar REGRAS que sao formulas que dependem dos fatos Por exemplo saber se alguem e mae ou se alguem e filho xyPxy Fx Mxy Qualquer que seja x e y SE x e progenitor de y E x e feminino ENTAO x e mae de y Introduzimos M para significar ser mae xyzPzx Pzy Ixy Qualquer que seja x y z SE z e progenitor de x E z e progenitor de y ENTAO x e y sao irmaos Introduzimos I para significar ser irmao de Traduzido para Prolog veja os slides seguintes Prof Julio Cesar da Silva Introducao a Sistemas Logicos 10 47 CQC Prolog e IA Prof Julio Cesar da Silva Introducao a Sistemas Logicos 11 47 CQC Prolog e IA Prof Julio Cesar da Silva Introducao a Sistemas Logicos 12 47 CQC Prolog e IA Prof Julio Cesar da Silva Introducao a Sistemas Logicos 13 47 Pausa para Pensar 1 Vocˆe consegue criar uma formula para ser a regra de que alguem e o pai de outra pessoa como fizemos com mae 2 Vocˆe consegue criar uma formula para ser a regra de que alguem e tio de outra pessoa Prof Julio Cesar da Silva Introducao a Sistemas Logicos 14 47 Teoria dos Modelos As vezes escrevemos ou falamos uma sentenca S que nao expressa nada verdadeiro ou falso pois falta alguma informacao crucial sobre o que as palavras significam Exemplo xyx y Se adicionarmos essa informacao de forma que S passe a expressar uma declaracao verdadeira ou falsa dizemos que estamos interpretando S e a informacao adicionada e chamada de uma interpretacao de S Exemplo x e y sao numeros naturais de tal maneira que um numero implica outro numero como no caso do sucessor Prof Julio Cesar da Silva Introducao a Sistemas Logicos 15 47 Logica Binaria e Sistemas Digitais Um sistema digital e o conjunto de aparelhos usados para lidar com informacoes logicas ou com quantidades fısicas de forma digital Para isso e comum usarmos o sistema numerico binario tambem conhecido como sistema de base 2 que consiste em dois possıveis valores de tensao simbolizados pelos numeros 0 e 1 ou nıvel logico baixo e nıvel logico alto respectivamente Isso ocorre devido ao fato de que nao seria viavel projetar dispositivos eletrˆonicos capazes de operar com muitos nıveis de tensao Apesar disso em algumas situacoes e necessario converter as saıdas digitais binarias em valores com base decimal como na utilizacao de calculadoras e computadores Prof Julio Cesar da Silva Introducao a Sistemas Logicos 16 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 17 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 18 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 19 47 Logica Binaria e Sistemas Digitai Prof Julio Cesar da Silva Introducao a Sistemas Logicos 20 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 21 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 22 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 23 47 Logica Binaria e Sistemas Digitais Prof Julio Cesar da Silva Introducao a Sistemas Logicos 24 47 Pausa para Pensar 1 Como devemos tecnicamente dizer que xyx y x possui um valor de verdade 2 Qual a relacao que existe entre a resposta da questao 1 e o conceito de estrutura de uma linguagem de primeira ordem Vocˆe consegue exemplificar 3 O que significa os valores de entrada e de saıda de uma porta logica 4 Com base na sua resposta da questao 3 a logica das portas logicas poderia ser nao binaria Justifique Prof Julio Cesar da Silva Introducao a Sistemas Logicos 25 47 Teoria dos Modelos Se a interpretacao I acontecer de fazer com que S afirme algo verdadeiro dizemos que I e um modelo de S ou que I satisfaz S simbolizado por I S Outra forma de dizer que I e um modelo de S e dizer que S e verdadeira em I e assim temos a nocao de verdade na teoria dos modelos que e a verdade em uma interpretacao particular Exemplo xx 0 x onde x deve ser interpretado como um numero natural e 0 como o numero natural 0 Essa sentenca e verdadeira na interpretacao sugerida ou seja que todo numero natural somado com 0 e igual a si mesmo Prof Julio Cesar da Silva Introducao a Sistemas Logicos 26 47 Teoria dos Modelos Essas nocoes sao uteis para analisar a forca de linguagens de consulta de banco de dados por exemplo linguagem SQL Podemos pensar nos possıveis estados de um banco de dados como estruturas e uma consulta simples de SimNao tornase uma sentenca que elicia a resposta Sim se o banco de dados for um modelo dela e Nao caso contrario Se uma linguagem de consulta de banco de dados nao e redutıvel a outra entao a primeira pode expressar alguma consulta que nao pode ser expressa na segunda Prof Julio Cesar da Silva Introducao a Sistemas Logicos 27 47 CQC e Provas Matematicas Podemos aplicar a deducao do CPC no CQC Pa Qab Cq Qab Cq Dc Dc E E Fba Pa E Fba 1 Pa Qab Cq P 2 Qab Cq Dc P 3 Dc E E Fba P 4 Pa P 5 E P 6 Qa Cq 14 MP 7 Dc 26 MP 8 E E Fba 37 MP 9 E Fba 58 SD 10 Fba 59 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 28 47 CQC e Provas Matematicas Para lidar com os quantificadores vamos precisar de algumas novas regras de inferˆencia Quantificador universal Eliminacao do Universal E Informalmente se alguma formula vale para todos os indivıduos entao vale para um certo indivıduo em particular xα αxc onde αxc e o resultado da substituicao em α de todas as ocorrˆencias livres da variavel x por uma constante c qualquer Se houver mais de um quantificador cada um devese eliminar um de cada vez Prof Julio Cesar da Silva Introducao a Sistemas Logicos 29 47 CQC e Provas Matematicas Quantificador universal Introducao do Universal I Informalmente como a deducao anterior vale para um indivıduo qualquer nao fazemos nenhuma suposicao especial a respeito dele essa deducao tem um carater geral A regra tem a seguinte formulacao αc xαcx onde αc e uma formula contendo alguma ocorrˆencia de uma certa constante c e xαcx e o resultado da substituicao em αc de todas as ocorrˆencias da constante c pela variavel x Prof Julio Cesar da Silva Introducao a Sistemas Logicos 30 47 CQC e Provas Matematicas Ainda em relacao a regra anterior i a constante c nao ocorre em nenhuma premissa e em nenhuma hipotese que esteja valendo na linha onde α ocorre ii c seja substitutıvel por x em α Prof Julio Cesar da Silva Introducao a Sistemas Logicos 31 47 CQC e Provas Matematicas Quantificador existencial Introducao do Existencial I Informalmente se alguma formula vale para um indivıduo em particular entao existe alguem a respeito em que essa formula e verdadeira αc xαcx onde αc e uma formula contendo alguma ocorrˆencia de uma constante c e αcx e o resultado da substituicao em α de uma ou mais das ocorrˆencias da constante c pela variavel x desde e claro que c seja substituıvel por x em α Ao contrario das regras para o quantificador universal nao se exige que todas as ocorrˆencias da constante c sejam substituıdas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 32 47 CQC e Provas Matematicas Quantificador existencial Eliminacao do Existencial E E uma regra de carater hipotetico e o ponto de partida e que existe algum indivıduo com alguma propriedade entao deverıamos poder concluir algo de um indivıduo particular xα αxc β β onde α e uma formula contendo alguma ocorrˆencia de uma variavel x e αxc e o resultado da substituicao em α de todas as ocorrˆencias da variavel x por alguma constante c Prof Julio Cesar da Silva Introducao a Sistemas Logicos 33 47 CQC e Provas Matematicas Uma regra derivada para quantificadores Regra de intercˆambio de quantificadores IQ Tratase de apenas uma regra que vem em duas versoes e cuja formulacao e a seguinte xα xα xα xα Prof Julio Cesar da Silva Introducao a Sistemas Logicos 34 47 CQC e Provas Matematicas Definicao Uma teoria formalizada de primeira ordem T e um conjunto qualquer de sentencas de uma linguagem de primeira ordem As formulas que pertencem a uma teoria T sao chamadas de axiomas de T Onde T e uma teoria vamos denotar por ThT o conjunto de todas as sentencas que sao consequˆencia logica de T Isto e ThT σT σ As sentencas que pertencem ao conjunto ThT para alguma teoria T sao chamados de teoremas de T Prof Julio Cesar da Silva Introducao a Sistemas Logicos 35 47 CQC e Provas Matematicas Vamos agora examinar uma teoria bastante conhecida aquela que procura formalizar a aritmetica dos numeros naturais Na interpretacao pretendida da teoria o universo do discurso serao os numeros naturais isto e o conjunto N 0 1 2 3 4 5 A linguagem sera constituıda de um sımbolo constante 0 de sımbolos para as funcoes binarias soma e produto e para a funcao sucessor e de um sımbolo para a relacao menor que Ou seja LN 0 s Prof Julio Cesar da Silva Introducao a Sistemas Logicos 36 47 CQC e Provas Matematicas Na interpretacao pretendida a constante 0 denota o numero zero Os outros numeros podem ser obtidos aplicandose a 0 a funcao sucessor Assim 1 e s0 2 e ss0 3 e sss0 e assim por diante Para simplificar vamos eliminar os parˆenteses que vˆe apos o sımbolo funcional s quando o termo entre parˆenteses iniciar com s As motivacoes para formalizar uma teoria da aritmetica devem ser obvias temos uma estrutura cujo universo e o conjunto dos numeros naturais e uma serie de sentencas verdadeiras a respeito dela Para evitar o fato de serem infinitas a serie de sentencas verdadeiras optamos tambem por sua axiomatizacao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 37 47 CQC e Provas Matematicas Nossa teoria axiomatica que denotaremos por N e formada pelo seguinte conjunto de axiomas nao logicos N1 xsx 0 N2 xysx sy x y N3 xx 0 x N4 xyx sy sx y N5 xx 0 0 N6 xyx sy x y x N7 xx 0 N8 xyx sy x y x y N9 xyx y x y y x Prof Julio Cesar da Silva Introducao a Sistemas Logicos 38 47 CQC e Provas Matematicas Alguns comentarios sobre esses axiomas O primeiro diz que nenhum numero e o seu proprio sucessor enquanto o segundo garante que se os sucessores de dois numeros sao idˆenticos entao os numeros sao na verdade o mesmo Note que a implicacao em N2 vale na outra direcao Os axiomas N3 e N4 especificam algumas das propriedades basicas da adicao mas nao todas Em N3 temos que a soma de qualquer numero com zero resulta no proprio numero N4 afirma que se somamos algum numero x com o sucessor de algum y o resultado sera o sucessor da soma de x e y Prof Julio Cesar da Silva Introducao a Sistemas Logicos 39 47 CQC e Provas Matematicas Os axiomas N5 e N6 especificam algumas das propriedades basicas da multiplicacao novamente mas nao todas Em N5 o analogo de N3 afirmase o que acontece se multiplicarem algum numero por zero N6 similarmente a N4 trata da multiplicacao de um numero pelo sucesso de outro Finalmente o axioma N7 afirma que nenhum numero e menor que 0 e com N8 e N9 define as caracterısticas da relacao x e menor que y Prof Julio Cesar da Silva Introducao a Sistemas Logicos 40 47 CQC e Provas Matematicas De posse desses axiomas podemos demonstrar alguns teoremas de N Por exemplo N 2 1 3 1 xyx sy sx y N4 2 yss0 sy sss0 y 1 Exss0 3 ss0 s0 sss0 0 2 Ey0 4 xx 0 x N3 5 ss0 0 ss0 4 Exss0 6 ss0 s0 sss0 35 E Prof Julio Cesar da Silva Introducao a Sistemas Logicos 41 47 CQC e Provas Matematicas Vamos por passos analisar o slide anterior Na linha 1 escrevemos simplesmente o axioma N4 Um axioma e como uma premissa em uma deducao podendo ser inserido em qualquer linha dela Dois usos de eliminacao do universal nos deixaram com a formula na linha 3 primeiro trocamos x por ss0 obtendo a formula na linha 2 depois trocamos y por 0 Na linha 4 outra vez um axioma e um uso de E substituindo x por ss0 nos deixou com a linha 5 continua no proximo slide Prof Julio Cesar da Silva Introducao a Sistemas Logicos 42 47 CQC e Provas Matematicas O truque agora para obter a linha 6 foi o uso de eliminacao da identidade A formula da linha 5 diz que a expressao ss0 s0 e idˆentica a ss0 O que fizemos foi pegar a formula da linha 3 ss0 s0 sss0 0 e substituir a ocorrˆencia de ss0 0 por ss0 Isso resulta em ss0 s0 sss0 e de acordo com nossa convencao de eliminar os parˆenteses da funcao sucesso sss0 e a mesma coisa que sss0 Assim ficamos na linha 6 com ss0 s0 sss0 ou seja 2 1 3 que e o que desejavamos Prof Julio Cesar da Silva Introducao a Sistemas Logicos 43 47 CQC e Provas Matematicas Argumento Final do professor Logica e a disciplina do pensamento estruturado onde podemos construir elaboradas solucoes a partir de elementos mais simples Em qualquer curso de exatas envolvendo computacao algoritmo e programacao ela nos oferece duas visoes 1 Explica como os elementos mais basicos como circuitos digitais e linhas de codigo funcionam 2 Treina a nossa mente para pensar situacoes complexas e consequentemente elaborar solucoes passo a passo Computacao portanto e um investimento em aperfeicoar a capacidade de pensar e de orientar os pensamentos para solucoes de problemas complexos Prof Julio Cesar da Silva Introducao a Sistemas Logicos 44 47 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 45 47 juliocesarcotemigcombr Prof Julio Cesar da Silva Introducao a Sistemas Logicos 46 47 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 47 47