·

Ciência da Computação ·

Lógica Matemática

Send your question to AI and receive an answer instantly

Ask Question

Preview text

Introducao a Sistemas Logicos Prof Julio Cesar da Silva Slides 4 Aplicacoes do CPC Texto baseado no Livro Fundamentos Matematicos para a Ciˆencia da Computacao Faculdade Cotemig Belo HorizonteMG Prof Julio Cesar da Silva Introducao a Sistemas Logicos 1 28 Sumario 1 Calculo Proposicional Classico Aplicacoes Prof Julio Cesar da Silva Introducao a Sistemas Logicos 2 28 DICA DE ESTUDO Enquanto o professor explica cada um dos Slides tenha em maos algum meio de fazer anotacoes Pode ser um caderno ou algum programa que permita deixar comentarios no PDF Tenha em maos tambem algum local documento digital ou caderno para resolver os exercıcios Dicas de anotacoes em PDF httpsupdfcombrannotatepdfpdfannotator Prof Julio Cesar da Silva Introducao a Sistemas Logicos 3 28 Validade de Argumentos Relembrando 1 Um argumento e um grupo de sentencas que exprime um raciocınio 2 Uma das sentencas chamada de conclusao e o ponto final do raciocınio e corresponde aquilo que se conclui 3 As outras chamadas de premissas sao o ponto inicial do raciocınio e representam as informacoes das quais se parte para chegar a conclusao Prof Julio Cesar da Silva Introducao a Sistemas Logicos 4 28 Validade de Argumentos Um exemplo de argumento Ou foi o mordomo ou foi o jardineiro Premissa 1 Nao foi o mordomo Premissa 2 Foi o jardineiro Conclusao O sımbolo e lido como portanto e indica a conclusao A primeira premissa deve ser compreendida como Se foi o morno entao nao foi o jardineiro ou como um novo conectivo OU Exclusivo Prof Julio Cesar da Silva Introducao a Sistemas Logicos 5 28 Ou Exclusivo Tabela Verdade vA B 1 sse vA 1 e vB 0 ou vA 0 e vB 1 TABELA VERDADE A B A B 1 1 0 1 0 1 0 1 1 0 0 0 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 6 28 Validade de Argumentos Relembrando A ideia e que um argumento seja a expressao de um raciocınio cujo ponto de partida sao as premissas e o ponto de chegada e a conclusao Por isso dizemos que a conclusao seguese ou e uma consequˆencia das premissas Entao acreditar que as premissas sao verdadeiras nos da um motivo incontestavel para acreditar que a conclusao tambem deve ser verdadeira Um argumento que possui essa propriedade e chamado de valido Sua conclusao e consequˆencia ou se segue das premissas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 7 28 Definicao 10 Definicao Seja Γ um conjunto de formulas e α uma formula Dizemos que α e uma consequˆencia tautologica de Γ ou que Γ implica tautologicamente α se para toda valoracao v tal que v Γ vα 1 Ou seja Γ α α e consequˆencia tautologica de Γ se α tiver o valor 1 em toda valoracao que for modelo de Γ Prof Julio Cesar da Silva Introducao a Sistemas Logicos 8 28 Validade de Argumentos Um exemplo de argumento Ou foi o mordomo ou foi o jardineiroA B Nao foi o mordomo A Foi o jardineiro B Argumento traduzido para o CPC conforme definicao 1 Como um argumento e conjunto de proposicoes ou sentencas sendo que a conclusao seguese dele entao Γ A B A e Γ B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 9 28 Pausa para Pensar Como podemos verificar se a conclusao B seguese semˆanticamente do seguinte conjunto de premissas Γ Γ A B A e Γ B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 10 28 Pausa para Pensar Um argumento que tiver muitas premissas ao ser traduzido para o CPC tera um conjunto de formulas com muitas letras sentenciais por exemplo A B C D E F Isso e um problema para que possamos verificar se alguma conclusao seguese das premissas Prof Julio Cesar da Silva Introducao a Sistemas Logicos 11 28 Pausa para Pensar Um argumento que tiver muitas premissas ao ser traduzido para o CPC tera um conjunto de formulas com muitas letras sentenciais por exemplo A B C D E F Isso e um problema para que possamos verificar se alguma conclusao seguese das premissas Pelo teorema de completude se uma formula e valida existe uma prova para ela por tablˆos ou por tabelas verdades e mais cedo ou mais tarde um procedimento de prova um algoritmo ou procedimento efetivo como construir as tabelas vai encontrala A questao e esse mais cedo ou mais tarde nao ha um mecanismo que sempre ache essa prova em tempo razoavel Prof Julio Cesar da Silva Introducao a Sistemas Logicos 12 28 Traducao para o CPC REFERˆENCIA PARA TRADUC AO Expressao em Portuguˆes Conectivo Logico Expressao Logica e mas tambem alem disso Conjuncao A B ou Disjuncao A B Se A entao B Condicional A B A implica B Condicional A B A logo B Condicional A B A so se B Condicional A B A somente B Condicional A B B seguese de A Condicional A B A se somente se B Bicondicional A B A e condicao necessaria para B Bicondicional A B A e condicao necessaria e suficiente para B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 13 28 Traducao para o CPC REFERˆENCIA PARA TRADUC AO Expressao em Portuguˆes Conectivo Logico Expressao Logica nao A Negacao A E falso que A Negacao A Nao e verdade que A Negacao A Prof Julio Cesar da Silva Introducao a Sistemas Logicos 14 28 Aplicando a negacao REFERˆENCIA PARA TRADUC AO Proposicao Negacao Correta Negacao Errada Vai chover amanha E falso que va chover amanha Vai chover amanha Nao vai chover Amanha Pedro e alto Pedro nao e alto Pedro e baixo Pedro e alto E falso que Pedro e alto Pedro e baixo Prof Julio Cesar da Silva Introducao a Sistemas Logicos 15 28 Conectivos Ordem de Precedˆencia Uma formula do CPC cuja sintaxe esta correta A B e tambem chamada de uma formula bem formada ou formulada ou fbf Para reduzir o numero de parˆenteses necessarios em uma fbf estipulamos uma ordem de aplicacao ou ordem de precedˆencia 1 Para conectivos dentro de varios parˆentese efetuase primeiro as expressoes dentro dos parˆenteses 2 3 4 5 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 16 28 Algumas Equivalˆencias Tautologicas Corrigido Equivalˆencias Tautologicas α β β α α β β α α β γ α β γ α β γ α β γ α β γ α β α γ α β γ α β α γ α 0 α α 1 α α α 1 α α 0 1a Linha Comutatividade 2a Linha Associatividade 3a Linha Distributividade 4a Linha Elemento neutro 5a Linha Complementos α β γ sao metavariaveis Prof Julio Cesar da Silva Introducao a Sistemas Logicos 17 28 Algumas Equivalˆencias Tautologicas Equivalˆencias Tautologicas α β α β α β α β α β α β α β α β α β α β β α α β α β β α α α α α β 1 1a Linha Condicional 2a Linha De Morgan ou Lei De Morgan 3a Linha Bicondicional 4a Linha Dupla Negacao 5a Linha Uma contradicao implica qualquer coisa como sendo tautologia α β sao metavariaveis Prof Julio Cesar da Silva Introducao a Sistemas Logicos 18 28 Pausa para Pensar Analise as equivalˆencias abaixo e diga quais sao equivalˆencias de fato e quais nao sao sem utilizar as tabelas verdades a A A b A B A B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 19 28 Aplicando Tautologia if FSaida FEntrada FSaida FEntrada Pressao 1000 FSaida 1 else FEntrada 1 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 20 28 Aplicando Tautologia if FSaida FEntrada FSaida FEntrada Pressao 1000 FSaida 15 else FEntrada 15 A FSaida FEntrada B Pressao 1000 if A A B FSaida 15 else FEntrada 15 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 21 28 Aplicando Tautologia Equivalˆencias Tautologicas A A B A A B De Morgan A A A B Distributiva 0 A B Complemento A B 0 Comutativa A B Elemento Neutro A B Prof Julio Cesar da Silva Introducao a Sistemas Logicos 22 28 Aplicando Tautologia A FSaida FEntrada B Pressao 1000 if A A B FSaida 15 else FEntrada 15 if FSaida FEntrada FSaida FEntrada Pressao 1000 FSaida 15 else FEntrada 15 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 23 28 Aplicando Tautologia A FSaida FEntrada B Pressao 1000 if A B FSaida 15 else FEntrada 15 if FSaida FEntrada Pressao 1000 FSaida 15 else FEntrada 15 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 24 28 Aplicando Tautologia Codigo Original if FSaida FEntrada FSaida FEntrada Pressao 1000 FSaida 1 else FEntrada 1 Codigo Otimizado if FSaida FEntrada Pressao 1000 FSaida 15 else FEntrada 15 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 25 28 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 26 28 juliocesarcotemigcombr Prof Julio Cesar da Silva Introducao a Sistemas Logicos 27 28 Prof Julio Cesar da Silva Introducao a Sistemas Logicos 28 28