Logica Matematica Discreta - Argumento Valido e Raciocinio Dedutivo

Nocoes de Logica QXD0008 Matematica Discreta Prof Lucas Ismaily ismailybfufcbr Universidade Federal do Ceara 1º semestre2024 Topicos desta aula Argumento valido e Raciocınio Dedutivo Conectivos Logicos Tabelasverdade Formulas Equivalentes Conjuntoverdade de um predicado 2 Referˆencias para esta aula Secoes 11 13 21 e 22 do livro Kenneth H Rosen Matematica Discreta e suas Aplicacoes Sexta Edicao Capıtulo 1 do livro Daniel J VELLEMAN How to Prove it A structured approach 3rd Edition Cambridge University Press 3rd Edition 2019 3 Introdução Forma de um argumento seu conteudo Forma de um argumento conceito central na logica dedutiva Argumento sequˆencia de afirmacoes para demonstrar a validade de uma assercao Como saber que a conclusao obtida de um argumento e valida As afirmacoes que compoem o argumento sao aceitas como validas ou podem ser deduzidas de afirmacoes anteriores Em logica forma de um argumento seu conteudo Analise logica nao determina a validade do conteudo de um argumento Ela determina se a verdade de uma conclusao pode ser obtida da verdade de argumentos propostos 5 Raciocınio dedutivo Exemplo 1 1 Hoje ou eu vou para a praia ou eu fico em casa 2 Estou cansado para viajar 3 Portanto ficarei em em casa Premissas itens 1 e 2 Conclusao item 3 Premissas forcam a conclusao Nao podemos afirmar que a conclusao seja verdadeira mas se as premissas forem verdadeiras entao a conclusao tambem o e 6 Raciocınio dedutivo Exemplo 2 1 Ou irei trabalhar hoje ou eu irei trabalhar amanha 2 Vou ficar em casa hoje 3 Portanto irei trabalhar amanha Argumento valido 1 Ou o mordomo ou a governanta e culpada 2 Ou o chofer ou a governanta e culpada 3 Portanto ou o mordomo ou o chofer e culpado Argumento invalido 7 Argumento valido Um argumento e valido quando as premissas nao podem ser verdadeiras sem que a conclusao o seja Voltando aos exemplos anteriores Exemplo 1 P hoje vou para a praia Q hoje fico em casa 1 P ou Q 2 nao P 3 Portanto Q Exemplo 2 P hoje irei trabalhar Q amanha irei trabalhar 1 P ou Q 2 nao P 3 Portanto Q Nao e o conteudo especıfico que importa mas a sua forma logica 8 Conectivos Lógicos Conectivos Logicos Poucas palavras que sao a chave para o entendimento do argumento Nos nossos exemplos ou or e and e naonot AND e OR sao operadores binarios NOT e um operador unario Atencao nem todo uso destes termos na lıngua pode ser traduzido com estes conectivos Por exemplo Joao e Maria sao amigos 10 Proposicao Em toda teoria matematica usamse termos ja definidos na concepcao de novas definicoes Mas como fazer com os termos mais primitivos Termos primitivos ou iniciais nao sao definidos Em logica os termos sentenca verdadeiro e falso sao os termos iniciais nao definidos 11 Proposicao Proposicao e uma sentenca a qual pode ser atribuıdo um valorverdade que pode ser verdadeiro ou falso Entretanto a uma proposicao nunca pode ser atribuıdo verdadeiro e falso simultaneamente ou um terceiro valor A partir de uma proposicao simples construımos proposicoes mais complexas usando os conectivos logicos Ou eu vou trabalhar hoje ou eu vou trabalhar amanha Maria tem um notebook e Joao tem um tablet Eu nao tenho um tablet Precisamos analisar como os conectivos logicos contribuem para o valorverdade final 12 Proposicoes Compostas Nos exemplos usados daqui para frente usaremos letras por exemplo P Q R para representar afirmacoes Os seguintes sımbolos podem ser usados para definir expressoes logicas mais complexas a partir de expressoes mais simples nao P e lido como nao P e e chamado de negacao de P e P Q e lido como P e Q e e chamado de conjuncao de P e Q ou P Q e lido como P ou Q e e chamado de disjuncao de P e Q 13 Proposicoes Compostas e um operador unario e e sao operadores binarios Avaliacao na seguinte ordem 1 negacao 2 conjuncao disjuncao Observacao Alguns autores consideram que a conjuncao tem prioridade sobre a disjuncao enquanto outros definem a mesma prioridade para os dois operadores O melhor e usar parˆentesis para indicar a prioridade evitando esse problema Exemplo P Q P Q P Q R e ambıguo pela dicussao acima Melhor solucao P Q R ou P Q R 14 Tabelasverdade Para uma sentenca ser uma proposicao e necessario ter um valorverdade bem definido isto e V ou F P e Q P Q e verdadeiro apenas quando ambos P e Q sao verdadeiros P Q AND F F F F V F V F F V V V Nao P P e verdadeiro apenas quando P for falso P P NOT F V V F 15 Tabelasverdade P ou Q P Q e falso apenas quando ambos P e Q sao falsos P Q OR F F F F V V V F V V V V Atencao em Matematica o ou e sempre inclusivo Analisar a formula bemformada P Q R pelo metodo com uma coluna para cada passo pelo metodo com cada sımbolo como uma coluna 16 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V F F V F F 17 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V V F V F V V F F F 17 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V V V F V F F V V F F F F F 17 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V V F V F V F V F V V F V F F F F V 17 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V V F F V F V F V V F V V F V V F F F F V F E P Q P xor Q ou exclusivo 17 Proposicoes mais complexas Construa a tabela verdade para a expressao E P Q P Q P Q P Q P Q P Q E V V V V F F V F V F V V F V V F V V F F F F V F E P Q P xor Q ou exclusivo O ponto fundamental em assinalar valoresverdade para proposicoes compostas e que permite o uso da logica para decidir a verdade de uma proposicao usando somente o conhecimento das partes 17 Tautologias e contradicoes Uma tautologia e uma formula que e sempre verdadeira independente dos valoresverdade das afirmacoes que compoem a proposicao Uma contradicao e uma formula que e sempre falsa independente dos valoresverdade das afirmacoes que compoem a proposicao Leis da tautologia P uma tautologia e equivalente a P P uma tautologia e uma tautologia a negacao de uma tautologia e uma contradicao Leis da contradicao P uma contradicao e uma contradicao P uma contradicao e equivalente a P a negacao de uma contradicao e uma tautologia 18 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q 19 Raciocınio dedutivo exemplo O argumento a seguir e valido 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso P Joao e estupido Q Joao e preguicoso 1 P Q P 2 P 3 Q Entao a pergunta e se e verdade que P Q P P Q 19 Raciocınio dedutivo exemplo P Q P Q P P Q F F F V V F V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F F F V F V F V V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F F F F V F F V F V V V V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F V V F F V F F V V V V F V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F V V F V F V F F V F V V V F V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F V V F V V F V F F V F F V V V F V F V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V V F V V V F V F F V F F V V V V F V F V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F F V V F V V V F F V F F V F F V V V V V F V F V V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F O argumento nao e valido 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F O argumento nao e valido Olhando a primeira premissa mais detalhadamente 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F O argumento nao e valido Olhando a primeira premissa mais detalhadamente P Q P Q P P Q F F F F V V V F V V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F O argumento nao e valido Olhando a primeira premissa mais detalhadamente P Q P Q P P Q F F F F F V V V V F V V V V V V 20 Raciocınio dedutivo exemplo P Q P Q P P Q F F V F F F F F F V F V V F V V V F F F V F F V F F V V V V V V F V F V V V V F O argumento nao e valido Olhando a primeira premissa mais detalhadamente P Q P Q P P Q F F F F F V V V V F V V V V V V As duas formulas sao equivalentes 20 Formulas equivalentes possuem sempre o mesmo valorverdade O argumento 1 Ou Joao nao e estupido mas e preguicoso ou ele e estupido 2 Joao e estupido 3 Portanto Joao nao e preguicoso e o mesmo que 1 ou Joao e estupido ou Joao e preguicoso ou ambos 2 Joao e estupido 3 Portanto Joao nao e preguicoso Simplificar formulas buscando formulas equivalentes a original contribui para o entendimento 21 Equivalˆencias bem conhecidas Leis de DeMorgan P Q P Q P Q P Q Leis comutativas P Q Q P P Q Q P Leis associativas P Q R P Q R P Q R P Q R Leis distributivas P Q R P Q P R P Q R P Q P R Leis idempotentes P P P P P P Leis de absorcao P P Q P P P Q P Lei da negacao dupla P P 22 Simplifique a formula Q P P Q P P e equivalente a Q P P Lei de DeMorgan que e equivalente a Q P P Lei da negacao dupla que e equivalente a Q P P Lei associativa que e equivalente a Q P Lei idempotente Q P P Q P 23 Proposicao condicional ou implicacao Sejam P e Q proposicoes Se P entao Q ou P implica Q e representado por P Q P e chamado de hipotese e Q de conclusao Sobre o uso tıpico de uma proposicao condicional ou implicacao Este tipo de sentenca e usado tanto em linguagem natural quanto em raciocınio matematico para dizer que a verdade da proposicao Q conclusao esta condicionada a verdade da proposicao P hipotesepremissa No entanto uma proposicao condicional do ponto de vista matematico e independente de uma relacao causaefeito entre hipotese e conclusao Exemplo Se 48 e divisıvel por 6p entao 48 e divisıvel por 3q 24 Proposicao condicional Tabelaverdade e um conectivo logico binario para o qual podem ser definidos valoresverdade Determinando a tabelaverdade para seentao A unica combinacao em que a sentenca condicional e falsa e quando a hipotese e V e a conclusao e F por definicao P Q P Q V V V V F F F V V F F V Prioridade do conectivo logico Ultimo a ser avaliado em expressoes que contˆem 25 Proposicao condicional Seja a seguinte sentenca que descreve uma promessa Se vocˆe se apresentar para trabalhar na segundafeira pela manha p entao vocˆe tera emprego q Em que situacao o empregador nao falou a verdade ou seja a promessa sentenca e falsa p V q F E se a afirmacao p nao for satisfeita Nao e justo dizer que a promessa e falsa 26 Proposicao condicional Contrapositiva A proposicao contrapositiva de p q e q p Exercıcio Prove que p q q p Exemplo p q Se hoje e Natal entao amanha e segundafeira q p Se amanha nao e segundafeira entao hoje nao e Natal 27 Proposicao condicional Oposta A proposicao oposta de p q e q p Exercıcio p q q p Exemplo p q Se esta chovendo entao o time da casa ganha q p Se o time da casa ganha entao esta chovendo 28 Proposicao condicional Inversa A proposicao inversa de p q e p q Exercıcio p q p q Exemplo Original Se hoje e Natal entao amanha e segundafeira Contrapositiva Se amanha nao e segundafeira entao hoje nao e Natal Oposta Se amanha e segundafeira entao hoje e Natal Inversa Se hoje nao e Natal entao amanha nao e segundafeira 29 Proposicao condicional Somente se A sentenca p somente se q significa que acresecentando verbos p pode ocorrer somente se q ocorre Se q nao ocorre entao p nao pode ocorrer ie Se q entao p Se p entao q ou p q Proposicoes condicionais p somente se p q Exercıcio p somente se q p se q Exercıcio p se q q p 30 Proposicao condicional Bicondicional se e somente se A sentenca bicondicional entre p e q e expressa como p se somente se q E representada por p q E tem a seguinte tabelaverdade P Q P Q F F V F V F V F F V V V O conectivo tem a mesma prioridade do conectivo 31 Proposicao condicional Bicondicional se e somente se Exemplo Este programa esta correto se somente se ele produz a res posta correta para todos os possıveis valores de dados de entrada Reescrevendo como uma conjuncao de duas sentencas seentao Se este programa esta correto entao ele produz a resposta correta para todos os possıveis valores de dados de entrada e Se o programa produz a resposta correta para todos os possıveis valores de dados de entrada entao ele esta correto 32 Proposicao condicional Condicao necessaria Condicao suficiente Sejam r e s afirmacoes r e uma condicao suficiente para s se r entao s A ocorrˆencia de r e suficiente para garantir a ocorrˆencia de s r e uma condicao suficiente para s se nao r entao nao s se s entao r Se r nao ocorrer entao s tambem nao pode ocorrer ie a ocorrˆencia de r e necessaria para se ter a ocorrˆencia de s A frase r e uma condicao necessaria e suficiente para s significa r se e somente se s 33 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Representados por letras ou sımbolos e denominados variaveis Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Representados por letras ou sımbolos e denominados variaveis Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Representados por letras ou sımbolos e denominados variaveis Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Representados por letras ou sımbolos e denominados variaveis Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Proposicoes e variaveis Proposicoes P 2 e um numero primo Q 9 e divisıvel por 5 R Joao tem 2 filhos Necessidade afirmacoes sobre objetos que podem variar Representados por letras ou sımbolos e denominados variaveis Exemplos x y representam numeros inteiros positivos e z representa uma pessoa x e um numero primo Px x e divisıvel por y Qx y z tem x filhos Rz x 34 Implicacoes Proposicoes sem variaveis atribuir um valor logico e natural pois uma proposicao sera sempre verdadeira ou falsa Sentencas com variaveis propriedades esta avaliacao simples nao e mais possıvel Considere Px x e um numero primo Como dizer se Px e falso ou verdadeiro P7 e verdadeiro P8 e falso E agora 35 FIM