Sistemas Logicos Slides - Sistemas Dedutivos e Axiomaticos

Introducao a Sistemas Logicos Prof Julio Cesar da Silva Slides 5 Sistemas Dedutivos 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 39 Sumario 1 Sistemas Dedutivos para o CPC Prof Julio Cesar da Silva Introducao a Sistemas Logicos 2 39 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 39 Sistemas Axiomaticos e Sistemas formais Neste nova secao sera apresentado uma outra maneira de definir consequˆencia logica e de provar a validade de formas de argumento que nao envolvem um recurso a semˆantica Tabela Verdade Geralmente em alguns ramos da ciˆencia determinadas proposicoes devem ser confrontadas com a experiˆencia empırica para que sejam consideradas como verdadeiras ou falsas Essa e uma situacao muito especifica nao envolve todas as ciˆencias como as conhecemos atualmente e nao excluem que determinadas sentencas por exemplo da fısica sejam verdadeiras por serem consequˆencias logicas de outras sentencas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 4 39 Sistemas Axiomaticos e Sistemas formais Entretanto para a chamada ciˆencia formal da matematica o confronto com a realidade nao e uma possibilidade factıvel Por exemplo figuras desenhas em um quadro sao apenas aproximacoes da verdadeira Em matematica certas proposicoes sao provadas ou demonstradas ao se mostrar que elas se seguem logicamente de algumas outras cuja verdade ja foi estabelecida Definicoes Axiomas etc Prof Julio Cesar da Silva Introducao a Sistemas Logicos 5 39 Sistemas Axiomaticos e Sistemas formais E necessario que se evite uma regressao ao infinito isto e mostrar que uma proposicao α e verdadeira com base em β1 βi e que por sua vez cada βi poderia ser provado com base em outros γ1 γi e por sua vez cada γi poderia ser provado em outros assim por diante Qualquer uma desses alternativas e de fato inaceitavel Atualmente os sistemas axiomaticos passaram a ser apresentados como sistemas formais de modo que expressoes bemformadas fbfs em uma linguagem artificial sejam as bases para as demonstracoes do sistema em questao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 6 39 Sistemas Axiomaticos e Sistemas formais Um sistema formal F tem quatro componentes basicos i um alfabeto que contem os caracteres da linguagem formal empregada em F ii um conjunto de regras de formacao que caracterizam quais sao as expressoes sequˆencia de caracteres da linguagem de F que sao bemformadas iii um conjunto de axiomas isto e um conjunto de expressoes bemformadas aceitas sem demonstracoes iv um conjunto de regras de transformacao regras de inferˆencia regras de deducao ou regras de producao que nos dizem como obter ou derivar novas expressoes bemformadas a partir dos axiomas e outras expressoes ja derivadas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 7 39 Sistemas Axiomaticos e Sistemas formais Os itens i e ii caracterizam a linguagem do sistema formal um alfabeto e uma gramatica Lembrese das definicoes 1 do CPC o que e ou nao uma formula O item iii sao os axiomas algum conjunto de sentencas da linguagem do sistema o qual pode ser finito ou infinito E nao ha a pretensao de que os axiomas sejam verdades evidentes e indubitaveis mas constituem o ponto de partida da investigacao sobre algum campo do conhecimento Inicialmente trataremos as formulas iniciais como sendo nossas hipoteses de um argumento e nao um sistema especifico Prof Julio Cesar da Silva Introducao a Sistemas Logicos 8 39 Deducao Natural O metodo de deducao natural permite demonstrar a validade de um argumento de maneira mais compacta pois aplica um conjunto de regras de inferˆencia ao conjunto de premissas ou hipoteses gerando conclusoes intermediarias as quais aplicamse novamente as regras ate atingir a conclusao final A esse processo chamamos deduzir derivar ou provar a conclusao a partir do conjunto das premissas e a seu resultado obviamente uma deducao ou derivacao ou prova Prof Julio Cesar da Silva Introducao a Sistemas Logicos 9 39 Exemplo Deducao Natural P Q C Q C D D E E F P E F 1 P Q C P ou H1 2 Q C D P ou H2 3 D E E F P ou H3 4 P P ou H4 5 E P ou H5 6 Q C 14 MP 7 D 26 MP 8 E E F 37 MP 9 E F 58 SD 10 F 59 MP martelo sintatico indica que deve ser feita uma prova por deducao natural para que a formula a frente F seja demonstrada Prof Julio Cesar da Silva Introducao a Sistemas Logicos 10 39 Deducao Natural Uma deducao e construıda da seguinte maneira Primeiro fazemos uma lista das premissas que estao a nosso dispor colocando uma em cada linha e escrevendo P ao lado para indicar que se trata de uma premissa Cada linha em uma derivacao e enumerada e devese ter uma justificativa para a formula que nela se encontra Esse e o motivo de se escrever P ou H Prof Julio Cesar da Silva Introducao a Sistemas Logicos 11 39 Deducao Natural P Q C Q C D D E E F P E F 1 P Q C P ou H1 2 Q C D P ou H2 3 D E E F P ou H3 4 P P ou H4 5 E P ou H5 6 Q C 14 MP 7 D 26 MP 8 E E F 37 MP 9 E F 58 SD 10 F 59 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 12 39 Deducao Natural O segundo passo e empregar alguma regra de inferˆencia que nos permita acrescentar uma nova linha a essa derivacao contendo uma formula que e o resultado da aplicacao da regra a formulas anteriores Nao devemos esquecer que as regras basicas de inferˆencia sao postuladas isto e aceitas sem demonstracao Repito o exemplo a seguir onde desejamos provar o seguinte argumento perceba que as premissas aparecem separadas pela conjuncao e a conclusao a ser provada esta logo depois de Prof Julio Cesar da Silva Introducao a Sistemas Logicos 13 39 Deducao Natural P Q C Q C D D E E F P E F 1 P Q C P ou H1 2 Q C D P ou H2 3 D E E F P ou H3 4 P P ou H4 5 E P ou H5 6 Q C 14 MP 7 D 26 MP 8 E E F 37 MP 9 E F 58 SD 10 F 59 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 14 39 Deducao Natural No exemplo anterior de 1 a 5 temos as premissas ou hipoteses Ja a linha seis e resultante de se aplicar a regra MP modus ponens as linhas 1 e 4 A linha sete por sua vez e resultante de se aplicar MP as linhas 26 O processo segue desta maneira usando oura regra na linha 9 por exemplo ate a linha dez onde esta a prova que desejamos desde o inicio Foi demonstrado que F e de fato uma consequˆencia logica do conjunto de premissas dado Como foi demonstrado Prof Julio Cesar da Silva Introducao a Sistemas Logicos 15 39 Exercıcio 1 Faca a devida montagem da prova apresente as hipoteses numeradas para os argumentos abaixo e diga qual deve ser a conclusao demonstrada ou provada a P Q R P Q b P P Q R P Q c P Q P R Q R R d P Q R P Q R S e Q P R R Q P f P R Q R P Q Q R g A B C C A B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 16 39 Exercıcio 2 Faca a devida montagem da prova apresente as hipoteses numeradas para os argumentos abaixo e diga qual deve ser a conclusao demonstrada ou provada a P Q R S T Q S b P Q R S T Q R c P Q Q P S T S T d P Q R S Q P S Prof Julio Cesar da Silva Introducao a Sistemas Logicos 17 39 Definicao 11 e 12 Definicao Seja Γ um conjunto qualquer de formulas e α uma formula Uma deducao de α a partir de Γ e uma sequˆencia finita δ1 δn de formulas tal que δn α e cada δi 1 i n e uma formula que pertence a Γ ou foi obtida a partir de formulas que aparecem antes na sequˆencia por meio de alguma regra de inferˆencia Definicao Seja Γ um conjunto qualquer de formulas e α uma formulaDizemos que α e consequˆencia logica sintatica de Γ o que denotamos por Γ α se ha uma deducao de α a partir de Γ Prof Julio Cesar da Silva Introducao a Sistemas Logicos 18 39 Nossa primeira regra de deducao MP 1 P Q H1 2 P H2 3 Q 12 MP 1 α β H1 2 α H2 3 β 12 MP 1 H1 2 H2 3 12 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 19 39 Nossa primeira regra de deducao MP 1 P H1 2 P Q H2 3 Q 12 MP 1 α H1 2 α β H2 3 β 12 MP 1 H1 2 H2 3 12 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 20 39 Nossa primeira regra de deducao MP 1 α β H1 2 α H2 3 β 12 MP 1 α H1 2 α β H2 3 β 12 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 21 39 Nossa primeira regra de deducao MP A FORMA da regra 1 H1 2 H2 3 12 MP 1 H1 2 H2 3 12 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 22 39 Pausa para Pensar Resolva as seguintes deducoes caso seja possıvel aplicar a regra MP a A A B B b S S T T c R R M M d B C B C e S T S T f E D E D g A A B B h R R M M i B C B C j S T S T l E D E D m A B C A B C n E E D C D C Prof Julio Cesar da Silva Introducao a Sistemas Logicos 23 39 Nossa segunda regra de deducao MT 1 P Q H1 2 Q H2 3 P 12 MT 1 α β H1 2 β H2 3 α 12 MT 1 H1 2 H2 3 12 MT Prof Julio Cesar da Silva Introducao a Sistemas Logicos 24 39 Nossa segunda regra de deducao MT 1 Q H1 2 P Q H2 3 P 12 MT 1 β H1 2 α β H2 3 α 12 MT 1 H1 2 H2 3 12 MT Prof Julio Cesar da Silva Introducao a Sistemas Logicos 25 39 Nossa segunda regra de deducao MT A FORMA da regra 1 H1 2 H2 3 12 MT 1 H1 2 H2 3 12 MT Prof Julio Cesar da Silva Introducao a Sistemas Logicos 26 39 Pausa para Pensar a B A B A b T S T S c M R M R d B C C B e S T T S f E D D E g B A B A h M R M R i B C C B j S T T S l E D D E m A B C C A B n D C E D C E Prof Julio Cesar da Silva Introducao a Sistemas Logicos 27 39 Tabela das Regras de Inferˆencia REGRA NOME SIGLA α α β β modus ponens MP α β α β modus tollens MT α β α simplificacao SIMP α β β simplificacao SIMP α β α β conjuncao CONJ α α β Adicao AD β β α Adicao AD α β β γ α γ Silogismo Hipotetico SH α β β α Silogismo Disjuntivo SD α β α β Silogismo Disjuntivo SD α β α β Eliminacao da Equivalˆencia EE α β β α Eliminacao da Equivalˆencia EE Prof Julio Cesar da Silva Introducao a Sistemas Logicos 28 39 Pausa para Pensar Escreva a FORMA das regras da tabela do SLIDE anterior isto e da Tabela de Regras de Inferˆencia Prof Julio Cesar da Silva Introducao a Sistemas Logicos 29 39 Tabela das Leis de Equivalˆencia LEI NOME SIGLA α α 0 Contradicao CONT α α 1 Terceiro Excluıdo TE α 1 α Identidade ID α 0 α Identidade ID α α α Idempotentes IP α α α Idempotentes IP α α Dupla Negacao DN α α Dupla Negacao DN α β β α Comutativas COM α β α β De Morgam DM α β α β De Morgam DM α β α β Disjuncao DJ Prof Julio Cesar da Silva Introducao a Sistemas Logicos 30 39 Pausa para Pensar a Escreva a FORMA das regras da tabela do SLIDE anterior isto e da Tabela das Leis de Equivalˆencia b Uma regra de equivalˆencia pode ser lida nas duas direcoes desta maneira se α α entao podemos tambem afirmar que α α Reescreva Tabela das Leis de Equivalˆencia apontando a outra direcao de leitura Prof Julio Cesar da Silva Introducao a Sistemas Logicos 31 39 Agora sim podemos entender tudo P Q C Q C D D E E F P E F 1 P Q C P ou H1 2 Q C D P ou H2 3 D E E F P ou H3 4 P P ou H4 5 E P ou H5 6 Q C 14 MP 7 D 26 MP 8 E E F 37 MP 9 E F 58 SD 10 F 59 MP Prof Julio Cesar da Silva Introducao a Sistemas Logicos 32 39 EX03 Prove o argumento abaixo a P Q R P Q b P P Q R P Q c P Q P R Q R R d P Q R P Q R S e Q P R R Q P f P R Q R P Q Q R g A B C C A B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 33 39 EX04 Demonstre o seguinte argumento a P Q R S T Q S b P Q R S T Q R c P Q Q P S T S T d P Q R S Q P S Prof Julio Cesar da Silva Introducao a Sistemas Logicos 34 39 EX05 Determine se o seguinte argumento e valido Se o Superhomem era capaz e tinha vontade de prevenir o mal ele assim o faria Se o Superhomem nao fosse capaz de prevenir o mal ele seria impotente Se ele nao tivesse vontade de combater o mal ele seria malevolo O superhomem nao previne o mal Se Superhomem existe ele nao e nem impotente nem malevolo Por isso o Superhomem nao existe DICA A Superhomem e capaz de prevenir o mal B Superhomem tem vontade de prevenir o mal C Superhomem previne o mal D Superhomem e impotente E Superhomem e malevolo F Superhomem existe Prof Julio Cesar da Silva Introducao a Sistemas Logicos 35 39 DICA IMPORTANTE Os conteudos vistos neste Slide requerem que um estudo aprofundado Refaca TODOS os exercıcios enquanto estiver com duvida Imprima as paginas 28 e 30 se precisar ter uma folha rapida de consulta Prof Julio Cesar da Silva Introducao a Sistemas Logicos 36 39 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 37 39 juliocesarcotemigcombr Prof Julio Cesar da Silva Introducao a Sistemas Logicos 38 39 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 39 39