rosas são vermelhas e violetas são azuis”. qual a negação da proposição acima? escolha uma:

Q: Não é verdade que rosas são vermelhas ou violetas são azuis ou rosas não são vermelhas e violetas são azuis e mesmo que dizer que?

Dizer que Não é verdade que rosas são vermelhas ou violetas são azuis, ou, rosas não são vermelhas e violetas são azuis” é mesmo que dizer que: A. rosas não são vermelhas.

Universidade do Vale do Rio dos Sinos - UNISINOS

Apostila da Disciplina de

Lógica

Prof. João Carlos Gluz São Leopoldo, março de 2009

UNISINOS

Lógica

Apostila 1

Sumário CAPÍTULO 1 LÓGICA PROPOSICIONAL.....................................................................................................................1 1.1. PROPOSIÇÕES E OPERADORES LÓGICOS......................................................................................................1 1.2. IMPLICAÇÃO MATERIAL E EQUIVALÊNCIA LÓGICA.......................................................................................3 1.3. FÓRMULAS E PRECEDÊNCIA......................................................................................................................4 1.4. CONSTRUÇÃO DE TABELAS-VERDADE PARA FÓRMULAS................................................................................5 1.5. TAUTOLOGIAS E CONTRADIÇÕES...............................................................................................................6 1.6. EQUIVALÊNCIAS TAUTOLÓGICAS E LEIS DE DEMORGAN..............................................................................7 1.7. SIMBOLIZAÇÃO DE PROPOSIÇÕES...............................................................................................................8 1.8. EXERCÍCIOS SOBRE PROPOSIÇÕES, FÓRMULAS E TAUTOLOGIAS......................................................................9 CAPÍTULO 2 DEDUÇÃO NA LÓGICA PROPOSICIONAL ......................................................................................11 2.1. ARGUMENTOS VÁLIDOS.........................................................................................................................11 2.2. DEMONSTRAÇÕES..................................................................................................................................12 2.3. REGRAS DE DEDUÇÃO NATURAL............................................................................................................13 2.4. REGRAS HIPOTÉTICAS...........................................................................................................................16 2.5. REGRA DO MÉTODO DEDUTIVO..............................................................................................................18 2.6. TEOREMAS...........................................................................................................................................20 2.7. SIMBOLIZAÇÃO DE ARGUMENTOS VERBAIS...............................................................................................20 2.8. EXERCÍCIOS DE DEDUÇÃO E DEMONSTRAÇÃO...........................................................................................21 CAPÍTULO 3 SENTENÇAS ABERTAS..........................................................................................................................24 3.1. SENTENÇAS ABERTAS COM UMA VARIÁVEL..............................................................................................24 3.2. CONJUNTO-VERDADE DE UMA SENTENÇA ABERTA....................................................................................26 3.3. CONJUNÇÃO SOBRE SENTENÇAS ABERTAS (∧)...........................................................................................27 3.4. DISJUNÇÃO SOBRE SENTENÇAS ABERTAS (∨).............................................................................................30 3.5. NEGAÇÃO DE UMA SENTENÇA ABERTA (¬)..............................................................................................32 3.6. DEMAIS OPERADORES...........................................................................................................................34 3.7. EQUIVALÊNCIAS TAUTOLÓGICAS.............................................................................................................35 3.8. PREDICADOS COM DUAS VARIÁVEIS E SEU CONJUNTO-VERDADE..................................................................36 3.9. PREDICADOS COM N VARIÁVEIS E SEU CONJUNTO-VERDADE.......................................................................37 3.10. EXERCÍCIOS SOBRE SENTENÇAS ABERTAS...............................................................................................38 CAPÍTULO 4 QUANTIFICADORES..............................................................................................................................40 4.1. QUANTIFICADOR UNIVERSAL..................................................................................................................40 4.2. QUANTIFICADOR EXISTENCIAL................................................................................................................42 4.3. VARIÁVEIS QUANTIFICADAS (APARENTES) E VARIÁVEIS LIVRES.................................................................44 4.4. NEGAÇÃO DE FÓRMULAS COM QUANTIFICADORES.....................................................................................45 4.5. QUANTIFICAÇÃO MÚLTIPLA E PARCIAL....................................................................................................45 4.6. COMUTATIVIDADE DE QUANTIFICADORES..................................................................................................46 4.7. SIMBOLIZAÇÃO DE ENUNCIADOS CATEGÓRICOS.........................................................................................46 4.8. EXERCÍCIOS SOBRE QUANTIFICADORES.....................................................................................................48 CAPÍTULO 5 A LÓGICA DE PREDICADOS...............................................................................................................51 5.1. ESTRUTURAS, INTERPRETAÇÃO E SIGNIFICADO DAS FÓRMULAS....................................................................51 5.2. VALIDADE DE UMA FÓRMULA.................................................................................................................54 5.3. REGRAS DE DEDUÇÃO PARA A LÓGICA DE PREDICADOS.............................................................................56 5.4. PARTICULARIZAÇÃO UNIVERSAL..............................................................................................................57 5.5. PARTICULARIZAÇÃO EXISTENCIAL...........................................................................................................58 5.6. GENERALIZAÇÃO UNIVERSAL..................................................................................................................59 5.7. GENERALIZAÇÃO EXISTENCIAL................................................................................................................60 5.8. PROVA POR CONTRA-EXEMPLO...............................................................................................................60

UNISINOS

Lógica

Apostila 1

5.9. EXERCÍCIOS DE LÓGICA DE PREDICADOS..................................................................................................61 APÊNDICES .............................................................................................................................................63 APÊNDICE A - TABELAS VERDADE DOS OPERADORES LÓGICOS.........................................................................63 APÊNDICE B - PROPRIEDADES DAS OPERAÇÕES................................................................................................63 APÊNDICE C - REGRAS DE DEDUÇÃO DE EQUIVALÊNCIA E INFERÊNCIA...............................................................64 APÊNDICE E - REGRAS DE INFERÊNCIA DA LÓGICA DE PREDICADOS...................................................................66 BIBLIOGRAFIA........................................................................................................................................67

iii

UNISINOS

Lógica

Apostila 1

Lista de Figuras FIGURA 1 - INTERSECÇÃO DE CONJUNTOS COMO CONJUNÇÃO LÓGICA........................29 FIGURA 2 - UM EXEMPLO DE INTERSECÇÃO COMO CONJUNÇÃO......................................29 FIGURA 3 - UNIÃO DE CONJUNTOS COMO DISJUNÇÃO LÓGICA..........................................30 FIGURA 4 - UM EXEMPLO DE UNIÃO COMO DISJUNÇÃO........................................................31 FIGURA 5 - COMPLEMENTAÇÃO DE CONJUNTOS E NEGAÇÃO LÓGICA............................32 FIGURA 6 - UM EXEMPLO DE NEGAÇÃO COMO COMPLEMENTAÇÃO...............................33 FIGURA 7 - QUANTIFICAÇÃO UNIVERSAL, DOMÍNIO E CONJUNTO VERDADE ..............41 FIGURA 8 - QUANTIFICAÇÃO EXISTENCIAL, DOMÍNIO E CONJUNTO VAZIO..................43

Lista de Tabelas TABELA 1 - EQUIVALÊNCIAS DA DISJUNÇÃO (∨) E DA CONJUNÇÃO (∧)................................7 TABELA 2 - EQUIVALÊNCIAS DOS OUTROS OPERADORES.......................................................7 TABELA 3 - REGRAS BÁSICAS DE INFERÊNCIA...........................................................................13 TABELA 4 - REGRAS DE INFERÊNCIA DERIVADAS....................................................................14 TABELA 5 - REGRAS DE EQUIVALÊNCIA.......................................................................................15 TABELA 6 - REGRAS DE INFERÊNCIA DA LÓGICA DE PREDICADOS...................................56

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

Capítulo 1 Lógica Proposicional Neste capítulo serão apresentadas definições precisas sobre o que são proposições, fórmulas e tautologias que nos permitirão definir uma linguagem formal para a lógica das proposições, ou seja, nos permitirão criar uma Lógica Proposicional.

1.1. Proposições e Operadores Lógicos Proposição Lógica Intuitivamente, uma proposição lógica (ou apenas uma proposição) é uma frase ou sentença da língua portuguesa (ou de qualquer outro idioma) que pode assumir apenas um de dois valores verdade: ou a frase é verdadeira (ela diz uma verdade) ou ela é falsa (diz uma falsidade). Note que embora as proposições sejam bastante comuns na linguagem natural, porque, por exemplo, todas as afirmações são naturalmente proposições, existem também vários exemplos de frases que não se encaixam na definição acima. Comandos e solicitações, por exemplo, não são exatamente proposições. Quando uma ordem é dada (“feche a porta!”) ou uma solicitação feita (“por favor, me passe o prato”) não há necessariamente um valor verdade por trás destas frases. As proposições são usualmente simbolizadas (representadas) por letras maiúsculas do início do alfabeto: A, B, C, ... Os valores lógicos das proposições são representados de forma resumida usando V para verdadeiro e F para falso. As proposições podem ser simples ou compostas. As proposições compostas são formadas de proposições simples conectadas através de operadores (ou conetivos) lógicos. Estes operadores ou conetivos representam as seguintes operações lógicas, que serão descritas mais adiante: • Conjunção • Disjunção • Negação • Implicação (ou condicional) • Bi-implicação (ou bicondicional) Conjunção de Proposições O conetivo “e” é a forma mais usual de se formarem proposições compostas através da conjunção lógica de proposições. Este conetivo é usado, por exemplo, em sentenças como “gatos são mamíferos e canários são aves”, “3 < 5 e 2+3=5”, etc. A conjunção também pode ser representada por preposições como “mas”, “também” e similares.

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

O símbolo ∧ é usado para representar formalmente a conjunção lógica. Caso A e B sejam proposições, então a fórmula A∧B representa a conjunção lógica das proposições A e B. Exercício: (1.1) Agora responda as seguintes questões: (a) Se A é verdadeira e B verdadeira, que valor você atribuiria a A ∧B? (b) Se A é verdadeira e B falsa, que valor você atribuiria a A ∧B? (c) Se A é falsa e B verdadeira, que valor você atribuiria a A ∧B? (d) Se ambas A e B são falsas, que valor você atribuiria a A ∧B? (e) Construa uma tabela resumindo o resultado das questões (a) até (d). Use V para verdadeiro e F para falso. Mostre em cada linha da tabela a combinação de valores de A, B e de A ∧B. A tabela construída no exercício (1.1) é chamada de tabela-verdade do conetivo (ou operador) lógico ∧. Dica: uma conjunção somente é verdadeira, quando todas as proposições que a compõem são verdadeiras, e é falsa em todos os outros casos. Disjunção de Proposições O símbolo ∨ será empregado para representar um dos significados usuais do conetivo “ou” em frases da linguagem natural. O significado assumido por este símbolo é o do “ou inclusivo” que somente será falso se ambas as sentenças sendo conectadas por ele forem falsas, isto é, A ∨B será falso somente se ambos A e B forem falsos. Diz-se que o símbolo ∨representa a disjunção lógica das proposições A e B. Exercício: (1.2) Construa a tabela-verdade do operador ∨. Dica: uma disjunção somente é falsa, quando todas as proposições que a compõem são falsas, e é verdadeira em todos os outros casos. Negação de uma Proposição Os símbolos ¬ ou ~ serão usados para representar a negação de uma proposição. Neste caso, se A é uma proposição verdadeira então ¬A ou ~A será uma proposição falsa e vice-versa. Ou seja ¬A é a negação lógica de A. (as vezes o símbolo ‘ (apóstrofo) também é usado para simbolizar a negação) Exercício: (1.3) Construa a tabela da negação lógica

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

1.2. Implicação Material e Equivalência Lógica Implicação O símbolo → será usado para representar sentenças como “se chover, então a rua ficará molhada”, ou então “não estudar implica em tirar notas baixas” ou também “não fui ao cinema porque o carro estragou” e sentenças similares. Geralmente estas sentenças podem ser reescritas no formato “Se sentença A, então sentença B” que simbolicamente fica apenas: A → B. A noção que este operador lógico pretende capturar é a de existência de implicação ou de conseqüência entre as sentenças. Dessa forma a sentença B não poderia ser falsa se a sentença A fosse verdadeira, isto é, voltando aos exemplos não faria sentido afirmar “se chover, então a rua ficará molhada” se (A) realmente choveu e (B) a rua não ficou molhada (!?). Isto significa que se considera que a sentença simbolizada por A→B seria falsa somente no caso em que A é verdadeira e B falsa. Nos outros casos a expressão A→B seria verdadeira. Um comentário, entretanto, deve ser feito sobre a definição deste operador: quando a sentença A em A→B é falsa o resultado de A→B é verdadeiro independente de B. Isto apesar de nem sempre parece muito natural, também pode ser aceitável se assumirmos o princípio de que partindo de uma falsidade pode-se até mesmo alcançar alguma verdade. Entretanto, para se evitar conflitos com a relação de implicação lógica este conectivo → é denominado de implicação material (às vezes também é denominado de operador condicional). A proposição A, na fórmula A→B, é denominada de condição (ou antecedente) da implicação material e a proposição B é denominada de conclusão (ou conseqüente) desta implicação. Exercício: (1.4) Com base na discussão acima construa a tabela-verdade de A→B. Dica: uma implicação material A→B somente é falsa, quando a condição A for verdadeira e a conclusão B for falsa. Ela é verdadeira em todos os outros casos. Bi-implicação ou Equivalência Lógica A operação de equivalência lógica de duas proposições é definida de forma que esta operação resulte verdadeira apenas quando estas duas proposições forem iguais (tiverem o mesmo valor lógico). Esta operação é representada pelo símbolo ↔ e é denominada de bi-implicação ou de equivalência lógica (às vezes também denominada de bicondicional). O uso de bi-implicações não é comum na linguagem natural, mas existe uma forma tradicional de se traduzir (transliterar) o operador ↔ para a linguagem natural, através da expressão “se e somente se”. 3

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

A operação A↔B, na verdade, pode ser considerada uma abreviação da seguinte fórmula: (A→B) ∧(B→A) ou seja: (A↔B) = (A→B) ∧(B→A) Exercício: (1.5) Construa a tabela-verdade de (A→B) ∧ (B→A) (e, por conseguinte, também de (A↔B)). Dica: uma bi-implicação material A↔B é verdadeira quando A=B e falsa caso A≠ B.

1.3. Fórmulas e Precedência Uma fórmula é construída pela composição de símbolos de sentenças simples (A, B, ...) e de conetivos lógicos binários (∧,∨,→ e ↔) e unários (¬,~). Também podem ser usados parênteses. A precedência usual é: 1. Fórmulas dentro de parênteses (os mais internos primeiro) 2. ¬, ~ (a negação) 3. ∧(conjunção) 4. ∨(disjunção) 5. → (implicação material) 6. ↔ (bi-implicação ou equivalência lógica) 7. Da esquerda para a direita Uma fórmula que não tenha nenhum erro de sintaxe em sua escrita (por exemplo, não tenha excesso nem falta de parênteses, conectivos ou símbolos estranhos, etc.) é chamada de fórmula bem-formada (wff em inglês). Aqui no texto, entretanto, quando nos referirmos a uma fórmula estaremos assumindo que ela é bem-formada. Exemplos: Supondo que A, B e C são proposições lógicas então as seguintes expressões são fórmulas bem-formadas (ou apenas fórmulas) (A→B) ↔ (B→A) (A ∨¬A) → (B ∧¬B) ¬((A ∧¬B) → ¬C) (A→B) ↔ (¬B → ¬A) ((A ∧B ∧C) ∨¬(¬B ∨A) ∨(A ∧¬C)) → (C ∨¬A) ¬¬(Α ∧ C) Contra-exemplos (erros mais comuns):

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

As seguintes fórmulas apresentam alguns erros bastante comuns de escrita (sintaxe) que podem ocorrer nas fórmulas (do lado é indicado o tipo de erro): (A→B ↔ (B→A) (A ∨¬) → (B ∧¬B) ¬((A ¬B) → ¬C) (∨¬A) → (B ∧¬B) (A ∨¬A) → (B ∧)

falta um fecha parênteses a primeira negação não foi seguida de uma proposição falta um operador lógico entre A e ¬B falta uma proposição no lado esquerdo do operador ∨ falta uma proposição no lado direito do operador ∧

1.4. Construção de Tabelas-Verdade para Fórmulas Uma tabela-verdade mostra, em suas colunas mais a esquerda, todas as combinações de valores lógicos que as proposições de uma dada fórmula podem assumir. A partir destes valores de entrada pode-se “calcular” os valores que esta fórmula irá ter para cada uma destas combinações de valores. Este cálculo é feito passo a passo criando-se colunas intermediárias que ficam posicionadas à direita das colunas de entrada e que contém os valores das sub-fórmulas que compõem a fórmula principal. Na última coluna mais a direita se coloca a coluna que contém os valores finais desta fórmula. Resumindo, para se construir a tabela-verdade de uma fórmula lógica pode-se seguir os seguintes passos: (i) nas colunas à esquerda coloque os símbolos sentenciais simples (A, B, ...), depois (ii) se houverem sentenças simples negadas (¬A, ¬B, ...) coloque-as nas próximas colunas e por fim (iii) seguindo a precedência crie uma coluna para cada fórmula composta (não é necessário repetir as sentenças simples negadas). A última coluna a direita deve ser a expressão ou fórmula final. As sentenças ou símbolos proposicionais simples pertencentes a uma fórmula definem o número de linhas da tabela-verdade para esta fórmula através de uma regra simples: 1 símbolo: A 2 símbolos: A e B 3 símbolos: A, B e C 4 símbolos: A, B, C e D n símbolos: A, B, ...

2 linhas (21 combinações: V e F) 4 linhas (22 combinações: VV, VF, FV, FF) 8 linhas (23 combinações: VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF) 16 linhas (24 combinações) 2n linhas (2n combinações)

A última linha da tabela acima define a regra: para n símbolos proposicionais simples devem existir 2n linhas na tabela para representar as 2n combinações de valores verdade possíveis. Exemplo: O operador de disjunção ∨ é aplicado sobre duas proposições A ∨ B. A tabela-verdade deste operador, usando V para indicar verdadeiro e F para indicar falso (que deveria ter sido construída no exercício 1.1.), é igual a:

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

A V V F F

A ∨B V V V F

B V F V F

Outra forma de representar verdadeiro / falso é através de valores numéricos, 0 significa falso e 1 significa verdadeiro (esta é a forma mais comum usada em álgebra booleana e em circuitos lógicos). Usando esta notação a tabela acima ficaria: A 0 0 1 1

A ∨B 0 1 1 1

B 0 1 0 1

Note que quando se usa 0 e 1 a disposição dos valores verdadeiros e falsos muda. No caso de se usar V e F geralmente se começa com a linha superior toda em V e as demais linhas vão aos poucos sendo preenchidas com F até que na linha inferior todos os valores são F. No caso de se usar 0 e 1 a disposição é exatamente contrária. O reflexo destas diferentes disposições aparece claramente na última coluna. Neste texto somente será usada a primeira representação, com V para verdadeiro e F para falso, que é a forma usual da lógica proposicional. Exercício: (1.6) Agora construa tabelas-verdade para as seguintes fórmulas: (a) (A→B) ↔ (B→A) (b) (A ∨¬A) → (B ∧¬B) (c) ¬((A ∧¬B) → ¬C) (d) (A→B) ↔ (¬B → ¬A) (e) ((A ∧B ∧C) ∨¬¬(¬B ∨A) ∨(A ∧¬C)) → (C ∨¬A)

1.5. Tautologias e Contradições Uma tautologia é uma fórmula que assume apenas o valor V, ou seja, que é sempre verdadeira. Uma tautologia é “intrinsecamente verdadeira” pela sua própria estrutura; ela é verdadeira independente de qualquer valor lógico atribuído as suas letras de proposição. Uma contradição é o oposto de uma tautologia, ou seja, é uma fórmula que assume apenas o valor F independente de qualquer combinação de valores verdade atribuída às proposições lógicas simples que entram em sua composição.

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

No caso da lógica proposicional para demonstrar que uma fórmula é uma tautologia ou uma contradição basta construir sua tabela-verdade. O exercício (1.6.d) (A→B) ↔ (¬B → ¬A) apresentado acima é um exemplo de tautologia (basta conferir sua tabela-verdade). (1.7) Descobrir quais das seguintes fórmulas são tautologias, contradições ou fórmulas contingentes (fórmulas “simples” que não são tautologias ou contradições). (a) A ∨B ↔ B ∨A (b) (A ∨B) ∨C ↔ A ∨(B ∨C) (c) ¬(A ∧B) ↔ ¬A ∧¬B (d) (A ∧B) ∧B ↔ ¬((B ∧A) ∧A)

1.6. Equivalências Tautológicas e Leis de DeMorgan Equivalências Tautológicas Considere que P e Q sejam duas fórmulas lógicas quaisquer e que P↔Q seja uma tautologia, então pela própria definição do conetivo ↔, sempre que P for V numa dada linha da tabela-verdade de P↔Q, a fórmula Q também deverá ser V nesta linha. O mesmo acontece para quando P tem valor F. Neste caso se diz que P e Q são fórmulas equivalentes. Esta propriedade é denotada pelo operador ⇔ de equivalência tautológica entre as fórmulas P e Q, simbolicamente fica P⇔Q. Na tabela a seguir são apresentadas algumas equivalências tautológicas que definem propriedades importantes da disjunção e conjunção: Tabela 1 - Equivalências da Disjunção (∨) e da Conjunção (∧) Propriedade Comutativa Associativa Distributiva Elemento Neutro Complemento Idempotência

Disjunção (∨) A ∨B ⇔ B ∨A (A ∨B) ∨C ⇔ A ∨(B ∨C) A ∨(B∧C) ⇔ (A∨B) ∧(A∨C) A ∨F ⇔ A A ∨¬A ⇔ V A ∨A ⇔ A

Conjunção (∧) A ∧B ⇔ B ∧A (A ∧B) ∧C ⇔ A ∧(B ∧C) A ∧(B∨C) ⇔ (A∧B) ∨(A∧C) A ∧V ⇔ A A ∧¬A ⇔ F A ∧A ⇔ A

Na tabela a seguir são apresentadas algumas equivalências tautológicas que permitem reescrever ou redefinir os outros operadores: Tabela 2 - Equivalências dos outros operadores Dupla Negação Equivalência da Implicação Contraposição Prova Condicional

¬¬A ⇔ A A→B ⇔ ¬A ∨B A→B ⇔ ¬B → ¬A A→(B→C) ⇔ (A ∧B) → C 7

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

Exercício: (1.8) Demonstrar, pelo uso da tabela-verdade, as equivalências tautológicas acima (não precisa repetir as demonstrações para a equivalência comutativa, associativa e contraposição). Leis de De Morgan As equivalências vistas anteriormente permitem efetuar vários tipos de manipulações ou alterações numa fórmula sem que ela altere seu significado. Além destas fórmulas, entretanto, seria interessante que houvesse maneiras de se converter proposições conectadas pelo operador ∨ em proposições conectadas por ∧. Estas equivalências são denominadas Leis de De Morgan em homenagem ao matemático inglês do séc. XIX Augustus De Morgan, que foi o primeiro a enunciá-las. DeMorgan:

Negação da Disjunção ¬(A ∨B) ⇔ ¬A ∧¬B

Negação da Conjunção ¬(A ∧B) ⇔ ¬A ∨¬B

1.7. Simbolização de Proposições A seguir são apresentados alguns exemplos, tanto de passagem de uma fórmula para texto quando de texto para fórmula. Supondo que A = “hoje está chovendo”, B = “hoje faz frio” e C = “hoje vamos para a praia”, então a seguinte fórmula: A ∧B ∧¬C Poderia ser versada para o Português de várias formas diferentes: (a) Hoje está chovendo, hoje faz frio e não é verdade que hoje vamos para a praia. (b) Hoje está chovendo, faz frio e não vamos para a praia. (c) Hoje está chovendo e faz frio, todavia não vamos para a praia. (d) Hoje está chovendo e faz frio, mas não vamos para a praia hoje. A frase (a) que é uma transliteração direta da fórmula A ∧ B ∧ ¬C, embora correta do ponto de vista gramatical, simplesmente não é usada pelo excessivo formalismo. As demais formas são mais usuais (e existem muitas outras equivalentes). Note que a negação quase nunca é colocada no inicio da proposição. Note também que são usadas varias formas de conjunções alem do conetivo “e”: é usada a vírgula no caso (b) e as conjunções adversativas “todavia” e “mas” nos casos (c) e (d). Usando os mesmos significados para os símbolos A, B e C, a fórmula a seguir: (A ∧B) ∨C Poderia ser versada para o Português das seguintes formas: Hoje está chovendo e faz frio, ou hoje vamos para a praia. Ou hoje está chovendo e faz frio, ou hoje vamos para a praia. 8

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

Ou hoje está chovendo e faz frio, ou então hoje vamos para a praia. A fórmula: ¬(Α ∧ B) É um pouco mais complexa de ser versada, por conta da negação de uma sub-fórmula em parênteses, algo simplesmente não usado na linguagem natural. A fórmula poderia ser transliterada no seguinte texto: Não é verdade que hoje está chovendo e fazendo frio. Mas este texto é ambíguo, podendo representar a fórmula ¬Α ∧ B. Uma representação mais razoável da fórmula ¬(Α ∧ B) exigiria a retirada dos parênteses, algo que somente pode ser feito pelo uso das Leis de DeMorgan. Neste caso a fórmula se torna: ¬Α ∨ ¬B Facilmente versada para: Hoje não está chovendo ou hoje não está fazendo frio. A seguir são apresentados exemplos de texto, com sua simbolização equivalente: Se hoje está chovendo, então ou vamos para a praia, ou está fazendo frio. A→(C ∨ B) Hoje não está chovendo, nem fazendo frio, portanto vamos para a praia. (¬A ∧¬B)→C Hoje não vamos para a praia, porque está chovendo e fazendo frio. (A ∧B)→¬C

1.8. Exercícios sobre Proposições, Fórmulas e Tautologias (1.9) Sejam A,B e C as seguintes proposições: A Rosas são vermelhas. B Violetas são azuis. C Açúcar é doce. Escreva as proposições a seguir em notação simbólica: (a) Rosas são vermelhas e violetas são azuis. (b) Rosas são vermelhas, e ou bem violetas são azuis ou bem açúcar é doce. (c) Sempre que violetas são azuis, rosas são vermelhas e açúcar é doce. (d) Rosas são vermelhas apenas se violetas não forem azuis e se açúcar for amargo. (e) Rosas são vermelhas e, se açúcar for amargo, então ou violetas não são azuis ou açúcar é doce. (1.10) Considerando A, B e C com o mesmo significado visto acima, transcreva para o português as seguintes fórmulas: (a) B ∨¬C (b) ¬B ∨(A → C) (c) (C ∧¬A) → B 9

UNISINOS - Lógica

Capítulo 1- Lógica Proposicional

(d) C ∧(¬A ↔ B) (e) ¬(B ∧¬C) → A (1.11) Levando em conta o que aprendeu sobre equivalências e em particular sobre as Leis de De Morgan, escreva a negação das seguintes proposições compostas: (a) Se a comida é boa, então o serviço é excelente. (b) Ou a comida é boa, ou o serviço é excelente. (c) Ou a comida é boa e o serviço é excelente, ou então está caro. (d) Nem a comida é boa, nem o serviço é excelente. (e) Se é caro, então a comida é boa e o serviço é excelente. (1.12) Toda proposição composta é equivalente a uma que use apenas os conetivos de conjunção e negação. Para verificar isto é necessário encontrar fórmulas equivalentes a A ∨ B e A → B usando apenas ∧ e ¬. Estas fórmulas poderiam substituir, respectivamente, qualquer ocorrência de A ∨ B e A → B sem alterar o significado da fórmula original (não é necessário encontrar fórmula equivalente para A ↔ B porque a bi-implicação já foi definida em termos da implicação material). Agora encontre as fórmulas equivalentes a: (a) A ∨B (b) A → B (1.13) O número de linhas numa tabela-verdade de uma fórmula depende do número de proposições simples (A, B, C, ...) que entram nesta fórmula. Responda: (a) A tabela-verdade de uma fórmula com 10 proposições simples têm quantas linhas? (b) A tabela-verdade de uma fórmula com 20 proposições simples têm quantas linhas? (1.14) Você está viajando por um país onde todo habitante ou fala sempre a verdade ou é um mentiroso que sempre mente. Você encontra dois habitantes deste país, Percival e Levelim. Percival lhe diz “Pelo menos um de nós é mentiroso”. Agora responda: Percival é mentiroso ou está dizendo a verdade? E Levelim? Explique sua resposta. (1.15) Montar a tabela-verdade de: (A ∧(B→C)) ∨(¬C ∧¬((A∨B) → ¬A)) (1.16) Verificar se a equivalência é válida: (¬A ∨B) ∨(C → B) ⇔ (A ∧C) → C (1.17) Construa um argumento verbal apropriado para o seguinte argumento formal: (A → (B → C)) ∧(A ∨~D) ∧ B → (D → C) Defina claramente que proposições verbais são simbolizadas por A, B, C e D. (1.18) Construa um argumento verbal apropriado para o seguinte argumento formal: ((A ∨C) → G) ∧(C → (~G ∧~H)) ∧(C ∨B) → (A → B) Defina claramente que proposições verbais são simbolizadas por A, B, C, G e H.

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

Capítulo 2 Dedução na Lógica Proposicional As definições vistas até agora nos permitiram criar uma linguagem formal para a Lógica Proposicional. Estas definições também nos permitiram ver como se pode descobrir o valor-verdade de expressões nestas linguagens através de tabelas-verdade. Porém isso não é tudo que uma linguagem lógica pode nos fornecer. Ainda é necessário definir como são feitos raciocínios ou argumentações nesta linguagem. A lógica formal lida com um tipo particular de argumento, denominado de argumento dedutivo, que nos permite deduzir uma conclusão Q, com base num conjunto de proposições P1 a Pn, onde Q e P1 a Pn representam fórmulas inteiras bem-formadas da lógica proposicional (e não apenas proposições simples).

2.1. Argumentos Válidos Um argumento dedutivo pode ser representado de forma simbólica da seguinte forma: P1 ∧P2 ∧P3 ∧... ∧Pn → Q As proposições P1 a Pn são denominadas de hipóteses ou premissas do argumento. A proposição é denominada de conclusão do argumento. Em termos de língua natural este tipo de simbolismo pode ser lido como: “P1, P2, ... Pn acarretam Q” ou “Q decorre de P1, P2, ... Pn” ou “Q se deduz de P1, P2, ... Pn” ou ainda “Q se infere de P1, P2, ... Pn” Uma interpretação informal do argumento acima poderia levar em conta que Q seria uma conclusão lógica de P1, P2, ... Pn sempre que a verdade das proposições P1, P2, ... Pn implicar na verdade Q, ou seja, apenas quando o condicional: P1 ∧P2 ∧P3 ∧... ∧Pn → Q for verdadeiro. O problema é que esta interpretação poderia afirmar como válido um argumento como: A ∧B → C onde A representa “um dia tem 24 horas”, B representa “bananas são frutas” e C representa “hoje é depois de ontem”. Embora estas três sentenças sejam verdadeiras e portanto, neste caso, A ∧ B → C seja verdadeiro, não existe nenhuma relação real entre elas e portanto não se pode dizer que um argumento na forma tão genérica quanto A ∧B → C seja sempre válido, ou seja, que seja verdadeiro independente do valor verdade das premissas ou da conclusão, mas apenas em função apenas da sua forma. Dessa forma um argumento válido é um argumento onde a fórmula: P1 ∧P2 ∧P3 ∧... ∧Pn → Q é uma tautologia. 11

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

O fato do argumento P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q ser válido é simbolizado através da seguinte expressão: P1, P2, P3, ..., Pn ╞═ Q Esta expressão afirma que a fórmula Q é logicamente implicada pelas premissas P1, P2, P3, ..., Pn. Num argumento válido não interessam os valores verdade das hipóteses nem da conclusão, porque somente a forma do argumento é capaz de garantir sua validade. Por isto ele é denominado de argumento formal e esta é a razão por trás do poder de dedução da lógica formal, que pode verificar a validade ou correção de um argumento sem se ater às proposições que o compõem, isto é, sem se importar com seu significado.

2.2. Demonstrações Para testar se o argumento P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q é uma tautologia poderíamos simplesmente construir a tabela-verdade correspondente ao argumento. Porém, em vez disso, vamos usar um processo baseado na aplicação de regras de dedução (ou regras de inferência) que modificam fórmulas de modo a preservar seu valor lógico. A idéia básica é começar com as premissas P1, P2, ... Pn (supostamente verdadeiras) e tentar aplicar regras de dedução até terminar com a conclusão Q. Esta conclusão teria que ser, então, verdadeira uma vez que os valores lógicos são preservados sob as regras de inferência. Dessa forma uma demonstração formal da lógica proposicional teria a seguinte estrutura: P1 P2 ... Pn F1 F2 ... Fm Q

(hipótese 1) (hipótese 2) (hipótese n) (fórmula obtida aplicando-se uma regra de dedução sobre as fórmulas anteriores) (fórmula obtida aplicando-se uma regra de dedução sobre as fórmulas anteriores) (fórmula obtida aplicando-se uma regra de dedução sobre as fórmulas anteriores) (fórmula obtida aplicando-se uma regra de dedução sobre as fórmulas anteriores)

Neste tipo de argumento a conclusão Q simplesmente é a última forma obtida através da aplicação de uma regra de dedução. A seqüência de fórmulas obtidas por este processo é denominada de seqüência de demonstração ou apenas de demonstração formal da conclusão em função de suas premissas.

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

A seqüência de fórmulas F1, F2, ..., Fm é a prova (ou demonstração) que a conclusão Q se deduz das hipóteses P1, P2, ..., Pn. O fato que existe prova para um argumento P1 ∧ P2 ∧ P3 ∧ ... ∧ Pn → Q é simbolizado através da seguinte expressão: P1, P2, P3, ..., Pn ├─ Q Nota: Muito embora pareça muito mais simples aplicar o método de construção da tabela verdade para verificar a validade de um argumento, o método da demonstração formal se justifica por duas razões: (i) Quando o número de proposições simples é muito grande, por exemplo, com apenas 40 proposições simples seria necessária uma tabela-verdade com aproximadamente 1 TRILHÃO de linhas. (ii) No caso das lógicas mais expressivas como a Lógica de Predicados simplesmente não é possível aplicar o método da tabela-verdade, ou seja, somente nos resta aplicar o método da demonstração formal.

2.3. Regras de Dedução Natural Existem dois tipos básicos de regras de dedução: •

Regras de inferência que se baseiam em implicações tautológicas, ou seja, implicações materiais provadamente tautológicas.

•

Regras de equivalência que se baseiam nas equivalências tautológicas vistas no capítulo 1 e que permitem substituir uma fórmula pela outra, já que ambas são equivalentes.

As regras que são baseadas em implicações que já se tenha demonstrado (por tabelaverdade p.ex.) serem tautológicas serão denominadas de Regras de Inferência. A tabela 3 apresenta as regras básicas de inferência da lógica proposicional. Tabela 3 - Regras Básicas de Inferência Inclusão de Operadores

Exclusão de Operadores

Redução ao absurdo (raa) - ¬I

Dupla negação (dn) - ¬E

│P │... │Q∧¬Q ────── ¬P

¬¬P ──── P

Prova condicional (pc) - →I

Modus Ponens (mp) - →E

│P │... │Q ─────

P P→Q ────── Q

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

P→Q Conjunção(cj) - ∧I

Simplificação(sp) - ∧E

P Q ────── P∧Q

P∧Q ──── P

Adição(ad) - ∨I P ──── P∨Q

Eliminação da disjunção - ∨E

P ──── Q∨P

Introdução da equivalência - ↔I

P∧Q ──── Q

P∨Q P→R Q→R ──────────── R Eliminação da equivalência - ↔E

P→Q Q→P ──────── P↔Q

P↔Q ──── P→Q

P↔Q ──── Q→P

Estas 10 regras são completas no sentido que permitem a manipulação de todos os operadores da lógica proposicional. Do lado esquerdo estão listadas as regras que permitem a inclusão de um dado operador em uma nova fórmula a ser adicionada no decorrer da prova. As regras do lado direito permitem adicionar uma nova prova à demonstração, onde um determinado operador foi eliminado. Além destas regras básicas, existe também um conjunto de regras derivadas que também podem ser usadas em demonstrações. Embora todas as regras derivadas apresentadas na tabela 5 a seguir possam ser substituídas por demonstrações sem o uso delas, elas podem ser bastante úteis em determinados casos, facilitando o processo de demonstração. Tabela 4 - Regras de Inferência Derivadas Modus Tollens (mt)

Silogismo Hipotético (sh)

P → Q ¬Q ──────── ¬P Silogismo Disjuntivo (sd)

P →Q Q →R ───────── P →R Dilema Construtivo (dc)

P ∨Q ¬P ─────── Q

P∨Q P→R Q→S ──────────── R∨S

Exportação (exp)

Inconsistência (inc)

(P ∧Q) → R ──────── P→ (Q → R)

P ¬P ──── Q

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

As regras baseadas em equivalências tautológicas serão simplesmente denominadas de Regras de Equivalência. A seguir é apresentada uma tabela contendo as principais regras de equivalência (conferir com as equivalências tautológicas da seção 1.6): Tabela 5 - Regras de Equivalência Expressão P ∨Q P ∧Q (P ∨Q) ∨R (P ∧Q) ∧R ¬(P ∨Q) ¬(P ∧Q) P →Q P P →Q P P ∨P P ∧(Q ∨R) P ∨(Q ∧R)

Equivale a Q ∨P Q ∧P P ∨(Q ∨R) P ∧(Q ∧R) ¬P ∧¬Q ¬P ∨¬Q ¬P ∨Q ¬(¬P) ¬Q → ¬P P ∧P P (P ∧Q) ∨(P ∧R) (P ∨Q) ∧(P ∨R)

Nome (Abreviação) da Regra Comutatividade (com) Associatividade (ass) De Morgan (dmor) Condicional (cond) Dupla negação (dn) Contraposição (cont) Auto-referência (auto) Auto-referência (auto) Distributividade (dist) Distributividade (dist)

Importante: •

Note que as regras de equivalência são “reversíveis”, isto é, durante uma demonstração também se pode passar de uma fórmula no formato da segunda coluna (Equivale a) para uma fórmula no formato da primeira coluna (Expressão) sem perder a validade lógica.

•

Isto implica que uma regra de equivalência pode ser aplicada tanto na construção de seqüência de demonstração formal de um argumento, quanto na própria modificação de um argumento. Assim, as fórmulas de uma regra de equivalência são intercambiáveis: pode-se substituir uma sub-fórmula de um argumento por outra equivalente sem alterar a validade lógica do mesmo.

•

Porém as regras de inferência não são reversíveis, isto é, somente pode-se passar da situação prevista na primeira coluna (De) para a(s) fórmula(s) da segunda coluna (Pode-se deduzir). O oposto, pela própria natureza da regra, não é permitido.

•

Isto implica que não se pode usar este tipo de regra para alterar o argumento original, apenas se pode utilizá-la na construção de uma seqüência de demonstração.

Exemplos: Excetuando-se as regras de Redução ao Absurdo (raa) e Prova Condicional (pc), todas as demais regras de inferência e de equicalência apresentadas nas tabelas 3, 4 e 5 são de aplicação direta. Nesta seção serão mostrados exemplos de uso destas regras de aplicação direta.

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

Supondo que A→ (B ∧ C) e A são duas hipóteses de um argumento então a seguinte demonstração é válida: 1. 2. 3.

A→ (B ∧C) A B ∧C

hip hip 1, 2 mp

As fórmulas das 2 primeiras linhas são inseridas por conta das hipóteses, enquanto que a fórmula da linha 3 é derivada das fórmulas das linhas 1 e 2 pela regra modus ponens. Usando a lógica proposicional provar o seguinte argumento: A, (B → C), (A ∧B) → (C → D), B├─ D Primeiro as hipóteses do argumento: 1. 2. 3. 4.

A B →C (A ∧B) → (C → D) B

hip hip hip hip

Alguns passos óbvios (que poderão ser úteis ou não): 5. 6. 7.

C A ∧B C →D

2, 4 mp 1, 4 cj 3, 6 mp

E agora, portanto: 8.

5, 7 mp

2.4. Regras Hipotéticas As 6 regras básicas de inferência para a lógica proposicional que tratam da inclusão dos operadores ∧,∨e ↔, além da regras de exclusão da implicação (→E ou Modus Ponens) e da negação (¬E ou Dupla Negação) são de aplicação direta, não necessitando de um raciocínio hipotético para funcionar. Por outro lado as duas regras de inclusão da implicação (→I) e da negação (¬I) necessitam de raciocínios hipotéticos para serem aplicadas. Estes raciocínios são incorporados na prova na forma de demonstrações auxiliares ou hipotéticas, que tem um caráter “temporário”, e que deverão ser descartadas quando a conclusão da demonstração auxiliar for atingida. A forma como os resultados obtidos com a demonstração auxiliar serão usados na prova principal depende da regras de inferência usada. No caso da Redução ao Absurdo (raa), a demonstração auxiliar conseguiu mostrar que a partir de uma fórmula P, usada como hipótese inicial na demonstração auxiliar, foi possível demonstrar uma contradição lógica, isto é, uma fórmula do tipo Q∧¬Q. Neste 16

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

caso a nova fórmula que se pode adicionar na prova principal é ¬P que pode ser assumida como válida, porque caso contrário se chega a uma contradição lógica. Já no caso da Prova Condicional (pc), a demonstração auxiliar mostra que, caso se assuma a fórmula P como hipótese inicial da demonstração auxiliar, então é possível se deduzir uma dada fórmula Q. Se conseguirmos deduzir, a partir de P e das outras hipóteses, uma outra fórmula Q, então a fórmula P→Q pode ser adicionada na seqüência normal de demonstração. Neste caso, a fórmula P→Q adicionada a prova principal resume o fato (provado) que de P se pode deduzir Q. Quando as regras que utilizam raciocínio hipotético são concluídas, então todas as fórmulas que constituem a demonstração auxiliar têm que ser “descartadas” e não mais utilizadas na seqüência normal de demonstração. Somente a fórmula que foi demonstrada através do artifício do raciocínio hipotético pode ser usada na demonstração normal. Exemplos: Prove o seguinte argumento, que equivale a regras do Silogismo Hipotético: P→Q, Q→R ├─ P→R A demonstração é a seguinte e usa a regras de Prova Condicional: 1 2 3 4 5 6

P→Q Q→R │P │Q │R P→R

hip hip hip-pc 1,3 mp 2,4 mp 3-5 pc

Observe que a hipótese da prova condicional (hip-pc) e as fórmulas obtidas a partir dela e das hipóteses normais, foram escritas ao lado da barra vertical │, mais a esquerda que as fórmulas pertencentes a seqüência normal de demonstração. Isto é para deixar claro o caráter temporário destas fórmulas. Um outro exemplo de uso de Prova Condicional é usado na demonstração do seguinte argumento: P ├─ (P→Q)→Q A demonstração é a seguinte: 1 2 3 4

P │ P→Q │Q (P→Q)→Q

hip hip-pc 1,2 mp 2-3 pc

Demonstrações condicionais podem ser “aninhadas” uma dentro da outra se isto for necessário. Isto ocorre, por exemplo, na prova de: 17

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

(P∧Q)→R ├─ P → (Q→R) Cuja demonstração é a seguinte: 1 2 3 4 5 6 7

(P∧Q)→R │P │ │Q │ │P∧Q │ │R │ Q→R P → (Q→R)

hip hip-pc hip-pc 2,3 cj 1,4 mp 3-5 pc 2-6 pc

A regras de Redução ao Absurdo (raa) pode ser usada para provar o seguinte argumento (que é equivalente a regra de Modus Tollens): P→Q, ¬Q ├─ ¬P A demonstração fica: 1 2 3 4 5 6

P→Q ¬Q │P │Q │ Q∧¬Q ¬P

hip hip hip-raa 1,3 mp 2,4 cj 3-5 raa

2.5. Regra do Método Dedutivo Supondo um argumento na seguinte forma: P1, P2, P3, ... , Pn ├─ R → S então pelo uso da regra da Prova Condicional sempre se pode, em vez de usar P1, ..., Pn como hipóteses e tentar inferir R → S, adicionar R como uma hipótese adicional e depois inferir S. Em outras palavras podemos transformar o argumento acima no seguinte argumento: P1, P2, P3, ..., Pn, R ├─ S Isto é uma vantagem, porque nos dá mais uma hipótese, isto é, “munição” adicional para a demonstração. Esta hipótese adicional será identificada como hip-md na seqüência de demonstração. Exemplos: A regra do método dedutivo é útil para provar o seguinte argumento: A → (A → B)├─ A → B Pela regra do método dedutivo este argumento se transforma em:

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

A → (A → B, A ├─ B Agora a demonstração fica: 1 2 3 4

A → (A → B) A A →B B

hip hip-md 1, 2 mp 2, 3 mp

Provar que: ¬A ∨B, B → C ├─ A → C É possível demonstrar a validade deste argumento sem usar a Regra do Silogismo Hipotético (sh), essencialmente demonstrando a própria validade do silogismo hipotético como parte da demonstração (usando, entretanto, uma pequena ajuda da regra do método dedutivo): 1 2 3 4 5 6

¬A ∨B B →C A →B A B C

hip hip 1 cond hip-md 3, 4 mp 2, 5 mp

A Regra do Silogismo Hipotético (sh) afirma que de P→ Q e de Q → R, pode-se inferir P → R. A demonstração do argumento acima usando o silogismo hipotético é muito simples: 1 2 3 4

¬A ∨B B →C A →B A →C

hip hip 1 cond 2, 3 sh

Dicas de Dedução 1. A regra de modus ponens é provavelmente a regra de inferência mais intuitiva.Tente usá-la muitas vezes. 2. Fórmulas na forma ¬(P ∨Q) ou ¬(P ∧Q) dificilmente são úteis numa seqüência de demonstração. Tente usar as leis de DeMorgan para convertê-las, respectivamente, em ¬P ∧¬Q ou ¬P ∨¬Q, separando os componentes individuais de cada fórmula. 3. Fórmulas na forma P ∨Q dificilmente são úteis numa seqüência de demonstração, já que não implicam P nem Q. Tente usar a dupla negação para converter P ∨Q em ¬(¬P) ∨Q e depois usar a regra do condicional para obter ¬P → Q.

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

2.6. Teoremas Um teorema é simplesmente um argumento que não precisa de nenhuma hipótese (ou premissa) para ser válido (ou seja, para ser sempre verdadeiro). Por exemplo, o seguinte argumento é um teorema: ├─ P → P A prova de um argumento sempre parte de uma regra hipotética (ou Redução ao Absurdo - raa - ou Prova Condicional - pc). No caso do teorema acima a prova pode ser feita pela regra da prova condicional: 1│P

hip-pc

2 P→P

pc 1

Note que não há nenhuma hipótese ou premissa para este argumento, a linha 1 já começa pela regra de dedução da prova condicional.

2.7. Simbolização de Argumentos Verbais Considere o argumento: “Se as taxas de juros caírem, o mercado vai melhorar. Ou os impostos federais vão cair, ou o mercado não vai melhorar. As taxas de juros vão cais, portanto os impostos vão cais.” Supondo que as proposições simples usadas no argumento acima são representadas pelos seguintes símbolos: M = “O mercado vai melhorar” J = “A taxa de juros vai cair” I = “Os impostos federais vão cair” Então o argumento verbal acima seria equivalente a seguinte fórmula da lógica proposicional: (J → M) ∧(I ∨¬M) ∧J → I Que pode ser transformado no seguinte argumento formal: J → M, I ∨¬M, J ├─ I Uma demonstração possível da validade deste argumento formal é apresentada a seguir: 1. 2. 3. 4. 5. 6. 7.

J →M I ∨¬M J ¬M ∨I M →I J →I I

hip hip hip 2 com 4 cond 1, 5 sh 3, 6 mp

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

2.8. Exercícios de Dedução e Demonstração (2.1) Justifique cada passo na demonstração do seguinte argumento: A → (B ∨C), ¬B, ¬C ├─ ¬A 1 2 3 4 5 6

A → (B ∨C) ¬B ¬C ¬B ∧¬C ¬(B ∨C) ¬A

(2.2) Justifique cada passo na seguinte demonstração: ¬A, B, B → (A ∨C) ├─ C 1 2 3 4 5 6 7

¬A B B → (A ∨C) A ∨C ¬(¬A) ∨C ¬A → C C

(2.3) Demonstre a validade dos seguintes argumentos formais (prove por dedução usando apenas as regras de dedução básicas, mostradas na tabela 3): (a) C, B → A, C→B ├─ Α (b) ¬A → (B→C), ¬A, B ├─ C (c) (P∧Q)→(R∧S), ¬¬P, Q ├─ S (d) P ├─ P∧P (e) P, ¬¬(P→Q) ├─ Q∨¬Q (f) P∨Q ├─ Q∨P (g) ¬P∨¬Q ├─ ¬(P∧Q) (2.4) Demonstre a validade dos seguintes argumentos formais (prove por dedução usando qualquer uma das regras de inferência e de equivalência apresentadas neste capítulo): (a) ¬A, B → A ├─ ¬B (b) A → B, A → (B → C) ├─ A → C (c) (C → D) → C ├─ (C → D) → D (d) ¬A, A ∨B ├─ B (e) A → (B → C), A ∨¬D, B ├─ D → C (f) A → B, B → (C→ D), A → (B→ C) ├─ A → D (g) A ∧B ├─ ¬(A → ¬B)

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

Use a lógica proposicional para demonstrar a validade dos seguintes argumentos verbais (pode usar qualquer regras de inferência ou equivalência apresentada neste capítulo): (2.5) “Se segurança é um problema, então o controle da informação deve ser aumentado. Se segurança não é um problema, então os negócios via Internet devem aumentar. Portanto, se o controle da informação não for aumentado, os negócios na Internet crescerão.” (sugestão: use S, C e N como símbolos proposicionais). (2.6) “Se o programa é eficiente, executa rapidamente: ou o programa é eficiente ou tem algum bug.” (sugestão: use E,R e B como símbolos proposicionais). (2.7) “A colheita é boa mas não há água suficiente. Se não haver muita chuva ou se não houver muito sol, então haverá água suficiente. Portanto a colheita é boa e há muito sol.” (sugestão: use C, A, V (chuva) e S como símbolos proposicionais). (2.8) “A Rússia era uma potência superior e ou a França não era suficientemente poderosa, ou Napoleão cometeu um erro. Napoleão não cometeu um erro, mas, se o exército não perdeu, então a França era poderosa. Portanto, o exército perdeu e a Rússia era uma potência superior.” (sugestão: use R, F, N e E como símbolos proposicionais). (2.9) “Se meu cliente fosse culpado, a faca estaria na gaveta. Ou a faca não estava na gaveta ou José da Silva viu a faca. Se a faca não estava lá no dia 10 de outubro, então José da Silva não viu a faca. Além disso, se a faca estava lá no dia 10 de outubro, então a faca estava na gaveta e o martelo estava no celeiro. Mas todos sabemos que o martelo não estava no celeiro. Portanto, senhoras e senhores, meu cliente é inocente.” (2.10) Demonstre a validade dos seguintes argumentos formais usando as regras básicas de dedução e (se necessário) as regras derivadas de equivalência e : (a) P ↔ Q, Q ↔ R ├─ P ↔ R (b) P↔Q ├─ ¬P ↔ ¬Q (c) ¬P∨Q ├─ ¬(P ∧¬Q) (d) P → Q, P→¬Q ├─ ¬P (e) (P→Q)∧(P→R) ├─ P → (Q∧R) (f) P → Q ├─ (P∧R) → (Q∧R) (g) P → Q ├─ (P∨R) → (Q∨R) (h) ¬P → P ├─ P (2.11) Usando as regras básicas ou derivadas prove os seguintes teoremas: (a) ├─ P → (Q → (P ∧Q)) (b) ├─ ¬(P ↔ ¬P) (c) ├─ (P → Q) → (¬Q →¬P) (d) ├─ (P ∧Q) ∨(¬P ∨¬Q) (2.12) Demonstrar a validade dos seguintes argumentos: (a) ((A ∧¬B) → ¬C) ∧(D → C) ∧(D ∧E) → ¬(¬B ∧A) (b) (A →¬B) ∧(¬D→(A∧C)) ∧(D→(E∨F)) ∧(¬E∧¬F) → ¬B

UNISINOS - Lógica

Capítulo 2 - Dedução na Lógica Proposicional

UNISINOS - Lógica

Capítulo 4 - Quantificadores

Capítulo 3 Sentenças Abertas

3.1. Sentenças Abertas com uma Variável Intuitivamente, uma sentença aberta pode ser considerada uma frase que contém “espaços em brancos” (as variáveis) que devem ser preenchidos com valores retirados de algum conjunto predeterminado (o domínio das variáveis). Quando algum elemento é retirado deste conjunto e “encaixado” na sentença aberta, então esta sentença deixa de ser aberta e passa a se comportar como uma proposição simples, tendo um valor lógico possível: ou ela é uma sentença que afirma algo verdadeiro (proposição verdadeira) ou uma sentença que afirma algo falso (uma proposição falsa). Diz-se que a sentença é fechada quando isto ocorre. Construir sentenças abertas, definindo domínios apropriados para suas variáveis, é similar a jogar um jogo de montar frases, onde estas frases são formadas a partir de trechos sugeridos pelos participantes. Neste tipo de jogo, por exemplo, um participante, diz o início, um segundo diz o meio e um terceiro têm que sugerir um final engraçado para a frase (mas que também seja consistente com o que já foi dito). No caso do “jogo de montar sentenças abertas” da lógica, é necessário escolher primeiro qual será o domínio das variáveis, ou seja, de onde serão retirados os elementos que se encaixarão na frase aberta. Isto ocorre também nos jogos de montar frases ou palavras, onde tipicamente recorremos às pessoas, coisas, objetos, etc. conhecidos ou onde nos obrigamos a somente usar as palavras presentes num dicionário. Não faz sentido ou, na verdade, simplesmente não é engraçado falarmos sobre pessoas ou coisas que não conhecemos ou entendemos. Como exemplo, vamos supor o conjunto de móveis que podem pertencer a uma sala de aula: estantes, mesas, cadeiras, quadro, computadores (e seus componentes), etc. Este será o domínio A das nossas sentenças. Sabendo qual é o domínio então se pode começar a “montar” as sentenças. Em princípio, quaisquer frases que qualificam ou afirmam propriedades sobre os (possíveis) elementos deste domínio podem ser consideradas sentenças sobre estes elementos. No exemplo, poderíamos ter frases como: (a.1) “A minha mesa não está firme.” (b.1) “Esta é a cadeira que faltava.” (c.1) “A cadeira que falta aqui está sobrando lá no canto.” Estes exemplos apresentam proposições simples, que são sentenças fechadas, sem variáveis. Porém as variáveis poderiam aparecer como espaços: (a.2) “A minha _ _ _ _ não está firme.” 24

UNISINOS - Lógica

Capítulo 4 - Quantificadores

(b.2) “Esta é a _ _ _ _ que faltava.” (c.2) “A _ _ _ _ que falta aqui está sobrando lá no canto.” Um problema com a estrutura das frases acima é que cada “espaço em branco” é um espaço em branco igual aos outros. Quando existe um só espaço em branco na frase, isto é quando uma variável aparece somente num lugar dentro da sentença, então não há ambigüidade. Porém, quando ela aparece em vários lugares é necessário indicar claramente quem é quem em termos de “espaços em branco”. Embora isto ainda não pareça necessário porque estamos lidando apenas com uma variável, vamos ver que o conceito de sentença aberta pode ser (e é) facilmente estendido para sentenças abertas com múltiplas variáveis. A solução é dar “nome” aos espaços em branco, que deixam de ser espaços e passam a ser variáveis: (a.3) “A minha x não está firme.” (b.3) “Esta é a x que faltava.” (c.3) “A x que falta aqui está sobrando lá no canto.” Para os x pertencentes aos móveis da sala de aula. Para completar o processo de simbolização e deixar claro somente a forma das sentenças, sem se preocupar com seu conteúdo (seu significado), são atribuídos símbolos para as afirmações abertas: (a.4) P(x) = “A minha x não está firme.” (b.4) Q(x) “Esta é a x que faltava.” (c.4) R(x) = “A x que falta aqui está sobrando lá no canto.” Que são válidas para o domínio A que é o conjunto de móveis da sala de aula. Dessa forma as sentenças acima podem ser expressas simplesmente como: P(x), Q(x) e R(x) para x∈A. Em termos da língua portuguesa, uma sentença simples é formada basicamente por dois elementos: o sujeito e seu predicado. As sentenças simples da língua portuguesa servem para afirmar alguma propriedade (o predicado) sobre alguma pessoa, objeto ou coisa (o sujeito). Por esta razão sentenças abertas também são denominadas simplesmente de predicados. Já as sentenças abertas formais são normalmente construídas, considerando-se que o sujeito da frase é substituído por uma variável. Também é definido um domínio para esta variável, dizendo quem são os objetos, pessoas, entidades, coisas, etc. que podem ser representados pela variável. O predicado restante passa a ser então a afirmação que está sendo feita sobre algum sujeito do domínio. Em termos formais, uma sentença aberta com uma variável num conjunto A ou simplesmente uma sentença aberta em A, é uma expressão P(x) tal que P(a) é verdadeira (V) ou falsa (F) para todo elemento a pertencente ao conjunto A, ou seja, para todo a∈A. O conjunto A também é chamado de domínio da variável x. Embora, em princípio sentenças abertas possam ser aplicadas a qualquer domínio conhecido (e às vezes até mesmo desconhecido), é muito comum que estas sentenças

UNISINOS - Lógica

Capítulo 4 - Quantificadores

sejam exemplificadas e caracterizadas através de proposições matemáticas, principalmente por causa da precisão e rigor que se consegue obter com exemplos matemáticos. Na verdade, a definição teórica precisa sobre o significado de uma sentença aberta e sobre o significado das construções que podem ser feitas com elas será feita através da Teoria Elementar dos Conjuntos (que também fundamenta a Matemática). Observação: O significado (a semântica) que se atribuirá para as sentenças abertas será dado pela especificação de conjuntos-verdade correspondentes a estas sentenças. Estes conjuntosverdade definirão a extensão correspondente da sentença na Teoria Elementar dos Conjuntos. Mais adiante será visto que a semântica dos predicados ou das operações lógicas pode ser definida sem a necessidade de se recorrer aos conjuntos da Teoria Elementar dos Conjuntos. Entretanto, por agora é melhor utilizar os conceitos familiares desta teoria para estudar o significado das sentenças abertas e os efeitos dos operadores lógicos sobre estas sentenças. Exemplos: São sentenças abertas em N= {1, 2, 3, ... ,n, ...} as seguintes expressões: (d) x+1>8 (e) x é primo

(e) x2 - 5x + 6 = 0 (f) x é divisor de 10

para os x∈N.

3.2. Conjunto-Verdade de uma Sentença Aberta Chama-se conjunto-verdade de uma sentença aberta P(x) num domínio A. o conjunto de todos os elementos a∈A tais que P(a) é uma proposição verdadeira. Formalmente o conjunto-verdade pode ser definido como: VP = {x | x∈A ∧P(x)=V} ou, mais simplesmente como: VP = {x∈A | P(x)} Exemplos: (a) O conjunto-verdade de P(x) = “x+1 > 8” em N={1, 2, 3, ...} (conjunto dos números naturais) é dado por: VP = {x∈N | P(x)} = {x∈N | x+1 > 8}= {8, 9, 10, ... } ⊂ N (b) O conjunto-verdade de P(x) = “x+7 < 8” em N={1, 2, 3, ...} (conjunto dos números naturais) é dado por:

UNISINOS - Lógica

Capítulo 4 - Quantificadores

VP = {x∈N | x+7 < 8}= ∅ ⊂ N (c) O conjunto-verdade de P(x) = “x é divisor de 10” em N={1, 2, 3, ...} (conjunto dos números naturais) é dado por: VP = {x∈N | x é divisor de 10}= {1, 2, 5, 10} ⊂ N (d) O conjunto-verdade de P(x) = “x+5 > 3” em N={1, 2, 3, ...} (conjunto dos números naturais) é dado por: VP = {x∈N | x+5 > 3}= {1, 2, 3, 4, ...} = N ⊂ N Dos exemplos acima se pode tirar algumas conclusões importantes: (i) O conjunto-verdade de uma sentença aberta com uma variável sempre está contido ou (no máximo) é igual ao domínio A da sentença: VP ⊆ A (ii) Se P(x) é uma sentença aberta em A, então três casos podem ocorrer: (ii.1) P(x) é verdadeira para todo x∈A. Neste caso o conjunto-verdade de P(x) é igual ao próprio domínio A. Quando isto ocorre se diz que P(x) exprime uma condição universal ou propriedade universal no conjunto A. (ii.2) P(x) é verdadeira para alguns x∈A. Neste caso o conjunto-verdade de P(x) é um subconjunto próprio do domínio A. Quando isto ocorre se diz que P(x) exprime uma condição possível ou propriedade possível no conjunto A. (ii.3) P(x) não é verdadeira para nenhum x∈A. Neste caso o conjunto-verdade de P(x) é vazio (VP = ∅). Quando isto ocorre se diz que P(x) exprime uma condição impossível ou propriedade impossível no conjunto A. Exercício: (3.1) Determinar o conjunto-verdade em N (conjunto dos números naturais) de cada uma das sentenças abertas a seguir: (a) 2x = 6 (c) x2 - 5x + 6 = 0 (e) x2 - 5x = 0

(b) x-1 5” em A× B. (3.10) Determinar o conjunto-verdade da sentença aberta “x + 3y = 12” em N× N, sendo N o conjunto dos números naturais. (3.11) Determinar o conjunto-verdade da sentença aberta “3 | (x-y)” em AxA, sendo A={2, 3, 4, 5, 6}, onde a | b é a relação “a divide b sem resto”. 38

UNISINOS - Lógica

Capítulo 4 - Quantificadores

(3.12) Determinar o conjunto-verdade em A={1,4,9,10,11} de cada uma das sentenças abertas a seguir: (a) (x+1)∈A (c) x-2 é primo

(b) x+3 é impar (d) x2 - 3x + 2 = 0

(3.13) Determinar o conjunto-verdade em A={-3, -3, -1, 0, 1, 2, 3} de cada uma das seguintes sentenças abertas compostas: (a) (x é par) → (x2 -1 =0) (c) ((x+5)∉A) → (x 0” Determinar VP∧Q, V¬P e V¬Q.

UNISINOS - Lógica

Capítulo 4 - Quantificadores

Capítulo 4 Quantificadores Quantificadores são operadores lógicos aplicados a uma variável e a uma expressão (uma sentença aberta simples ou composta). Os quantificadores foram definidos para capturar conceitos da linguagem natural como: • • • • • •

Para todo mundo ... Não tem ninguém aqui que ... Todos aqui ... Tem alguém que poderia ... Qualquer um que ... Existe pelo menos um de nós ...

Estas orações exprimem afirmações que são verdadeiras para vários elementos do domínio. No caso da lógica de predicados somente são considerados dois tipos de afirmações sobre vários elementos de um domínio: • •

Afirmações universais, que devem ser válidas para todos os elementos de um domínio; Afirmações existenciais, que devem ser válidas para pelo menos um dos elementos do domínio.

Para cada um destes tipos de afirmações, corresponde um diferente tipo de quantificador: • •

Quantificadores universais, para representar as afirmações universais. Quantificadores existenciais, para representar as afirmações existenciais.

4.1. Quantificador Universal O quantificador universal é usado para representar as afirmações universais, que no Português são expressas por orações similares a: • • •

Para todo mundo ... Todos aqui ... Qualquer um que ...

Ele deve ser aplicado sobre uma sentença aberta P(x) definida para um conjunto A. Agora vamos supor que VP seja o conjunto-verdade de P(x). Dessa forma quando V P for igual a A (isto é VP=A) então todos os elementos de A irão satisfazer P(x), ou seja, para

UNISINOS - Lógica

Capítulo 4 - Quantificadores

todos os elementos de A, P(x) deve ser verdadeira. Isto pode ser expresso um pouco mais formalmente como: Para todo x∈A, P(x) é verdadeira, ou ainda, qualquer que seja o x∈A, tem-se que P(x) é verdadeira. Estas afirmações semi-formais, são completamente simbolizadas por: (∀x∈A) (P(x)) que, as vezes é simplificado para: (∀x) (P(x)) quando o domínio A está claro pelo contexto ou é desnecessário. Pela definição que demos acima para a quantificação universal deve ter ficado claro que o significado deste operador, em termos do domínio e do conjunto-verdade de uma sentença P(x), é o de afirmar uma igualdade entre ambos conjuntos, isto é, afirmação: (∀x∈A) (P(x)) é equivalente a dizer que: VP=A ou seja, (∀x∈A) (P(x)) ⇔ VP=A Graficamente esta relação pode ser representada como:

A (∀x∈A) (P(x))

A = VP Figura 7 - Quantificação Universal, Domínio e Conjunto Verdade É importante salientar que enquanto P(x) é uma sentença aberta, a sentença quantificada (∀x∈A) (P(x)) não é mais uma sentença aberta. A quantificação “fecha” uma sentença aberta, transformando-a numa proposição simples que pode ser verdadeira ou falsa no domínio A, dependendo do conjunto-verdade VP ser ou não igual ao domínio A.

UNISINOS - Lógica

Capítulo 4 - Quantificadores

Em outras palavras, dada uma sentença aberta P(x) num domínio, o operador ∀ representa uma operação lógica que transforma a sentença aberta P(x) numa proposição que é verdadeira ou não dependendo de P(x) ser ou não uma condição universal sobre o domínio. Em particular, quando o número de elementos do domínio A é finito, com A={a1,a2,...,an}, então é óbvio que a proposição (∀x∈A) (P(x)) é equivalente à conjunção das n proposições P(a1), P(a2), ..., P(an): (∀x∈A) (P(x)) ⇔ P(a1) ∧P(a2) ∧... ∧P(an) Exemplos: Afirmações universais válidas (verdadeiras): (∀x∈H) (x é mortal), para H o conjunto de seres humanos. (∀x∈N) (x+2 > x), para N o conjunto dos números naturais. (∀x∈A) (x 2x), para N o conjunto dos números naturais. (∀x∈A) (x∈N) , para A={0, 1, 2, 3, -3, 2.5, 4, 0.999, π}

4.2. Quantificador Existencial O quantificador existencial é usado para representar as afirmações existenciais, que no Português são expressas por orações similares a: • • •

Tem alguém que poderia ... Para algum destes ... Existe pelo menos um de nós ...

Ele deve ser aplicado sobre uma sentença aberta P(x) definida para um conjunto A. Agora vamos supor que VP seja o conjunto-verdade de P(x). Dessa forma quando VP não for igual ao conjunto vazio ∅ (isto é VP≠∅ ) então com certeza existe algum elemento de A que irá satisfazer P(x), ou seja, para algum elemento de A, P(x) deve ser verdadeira. Isto pode ser expresso um pouco mais formalmente como: Para algum x∈A, P(x) é verdadeira, ou ainda, existe pelo menos um x∈A, no qual P(x) é verdadeira. Estas afirmações semi-formais, são completamente simbolizadas por: (∃ x∈A) (P(x)) que, as vezes é simplificado para:

UNISINOS - Lógica

Capítulo 4 - Quantificadores

(∃ x) (P(x)) quando o domínio A está claro pelo contexto ou é desnecessário. Pela definição que demos acima para a quantificação existencial deve ter ficado claro que o significado deste operador, em termos do domínio e do conjunto-verdade de uma sentença P(x), é o de afirmar que o conjunto-verdade não pode ser vazio, isto é, afirmação: (∃ x∈A) (P(x)) é equivalente a dizer que: VP ≠ ∅ ou seja, (∃ x∈A) (P(x)) ⇔ VP ≠ ∅ Graficamente esta relação pode ser representada como:

A VP VP ≠ ∅ Figura 8 - Quantificação Existencial, Domínio e Conjunto Vazio Da mesma forma que no caso do quantificador universal, também no caso do quantificador existencial tem-se que, embora P(x) seja uma sentença aberta, a sentença quantificada (∃ x∈A) (P(x)) não é mais uma sentença aberta. A quantificação “fecha” uma sentença aberta, transformando-a numa proposição simples que pode ser verdadeira ou falsa no domínio A, dependendo de VP ser ou não vazio. Em outras palavras, dada uma sentença aberta P(x) num domínio, o operador ∃ representa uma operação lógica que transforma a sentença aberta P(x) numa proposição que é verdadeira ou não dependendo de P(x) ser ou não uma condição possível sobre o domínio. Em particular, quando o número de elementos do domínio A é finito, com A={a1,a2,...,an}, então é óbvio que a proposição (∃ x∈A) (P(x)) é equivalente à disjunção das n proposições P(a1), P(a2), ..., P(an): (∃ x∈A) (P(x)) ⇔ P(a1) ∨P(a2) ∨... ∨P(an) Exemplos: Afirmações existenciais válidas (verdadeiras):

UNISINOS - Lógica

Capítulo 4 - Quantificadores

(∃ x∈H) (x é pai), para H o conjunto de seres humanos. (∃ x∈N) (x+2 > 2x), para N o conjunto dos números naturais. (∃ x∈A) ((500x + 3) ∈A) , para A={0,1,2,3,4} Afirmações existenciais inválidas (falsas): (∃ x∈H) (x é mãe ∧x é homem), para H o conjunto de seres humanos. (∃ x∈N) (x+1 = x), para N o conjunto dos números naturais. Exercício: (4.1) Sendo R o conjunto dos números reais, determinar o valor lógico das seguintes expressões: (a) (∀x∈R) (|x| = x) (c) (∃ x∈R) (|x| = 0) (e) (∀x∈R) (x+1 > x)

(b) (∃ x∈R) (x2 = x) (d) (∃ x∈R) (x + 2 = x) (f) (∀x∈R) (x2 = x)

Para |x| a função módulo de x, que é calculada como: |x| = x, se x ≥ 0 |x| = -x, se x < 0

4.3. Variáveis Quantificadas (Aparentes) e Variáveis Livres Quando um quantificador incide sobre uma variável dentro de uma expressão lógica formada pela composição de sentenças abertas, então se diz que esta variável é uma variável quantificada ou então uma variável aparente. Por outro lado, se uma variável numa dada expressão lógica não tiver nenhum quantificador previamente associada a ela, então se diz que ela é uma variável livre. O termo variável aparente dado as variáveis quantificadas vem do fato que que uma variável quantificada não se comportar realmente como uma variável, ou seja, ela está comprometida pelo quantificador a uma dada associação universal ou existencial com os elementos do domínio. Não se esqueça que uma sentença aberta quantificada não é realmente uma sentença aberta, mas uma proposição lógica fechada que pode ser apenas verdadeira ou falsa. Um princípio simples, mas válido para a manipulação de expressões lógicas ou fórmulas compostas de sentenças quantificadas, afirma que todas as vezes que uma variável quantificada é substituída, em todos os lugares onde aparece numa expressão, por outra variável que não apareça nesta mesma expressão, então a expressão resultante é equivalente. Este princípio garante a equivalência das seguintes fórmulas lógicas: (∀pessoa) (pessoa é mortal) ⇔ (∀x) (x é mortal) ⇔ (∀coisa) (coisa é mortal) ⇔ ... (∃ pessoa) (pessoa foi à Lua) ⇔ (∃ x) (x foi à Lua) ⇔ (∃ coisa) (coisa foi à Lua )⇔ ...

UNISINOS - Lógica

Capítulo 4 - Quantificadores

4.4. Negação de Fórmulas com Quantificadores Qualquer expressão ou fórmula lógica quantificada também pode ser precedida do operador de negação (¬). Por exemplo, considerando o domínio das pessoas atualmente vivas as expressões formais: (∀x) (x fala Inglês) ¬ (∀x) (x fala Inglês) (∃ x) (x foi à Antártida) ¬ (∃ x) (x foi à Antártida) poderiam ser enunciadas, respectivamente, como: Todas as pessoas falam inglês. Nem todas as pessoas falam inglês. Alguém foi a Antártida. Ninguém foi a Antártida. Analisando estas expressões deve ficar claro algumas equivalências intuitivas. Em primeiro lugar afirmar que nem todas as pessoas falam Inglês é claramente equivalente a afirmar que existe alguém que não fala Inglês. Formalizando temos: ¬ (∀x) (x fala Inglês) ⇔ (∃ x) ¬ (x fala Inglês) E em segundo lugar afirmar que ninguém foi à Antártida é obviamente equivalente a afirmar que para todas as pessoas vivas atualmente não é verdade que elas tenham ido à Antártida. Formalizando este argumento temos: ¬ (∃ x) (x foi à Antártida) ⇔ (∀x) ¬ (x foi à Antártida) Está análise pode ser generalizada pelas seguintes regras: (i)

A negação da fórmula (∀x)(P(x)) é equivalente a afirmação de que, pelo menos para um x∈A, tem-se que P(x) é falsa, ou então que ¬P(x) é verdadeira. Portanto deve valer a seguinte equivalência: ¬ (∀x∈A) (P(x)) ⇔ (∃ x∈A) ¬ (P(x))

(ii)

Da mesma forma negar a fórmula (∃ x)(P(x)) equivale a afirmar que para todos os x∈A, a sentença P(x) deve ser falsa, ou então que a sentença ¬P(x) deve ser verdadeira, o que nos leva a seguinte equivalência: ¬ (∃ x∈A) (P(x)) ⇔ (∀x∈A) ¬ (P(x))

4.5. Quantificação Múltipla e Parcial Uma fórmula pode ter tantos quantificadores quanto o número de variáveis diferentes dentro da fórmula. Assim, para R o conjunto dos números reais, são possíveis fórmulas como: (∃ x∈R) (∃ y∈R) (x2 + y2 + 2x + xy > 0) (∃ x∈R) (∀y∈R) (∃ z∈R) (x2 + y2 + z3 - yz + x = 0)

UNISINOS - Lógica

Capítulo 4 - Quantificadores

que estão totalmente quantificadas, isto é, que não tem nenhuma variável sem quantificação Contudo, nem todas as variáveis de uma fórmula precisam estar quantificadas. Quando nem todas as variáveis de uma fórmula estão quantificadas se diz que está fórmula está parcialmente quantificada. Por exemplo as seguintes fórmulas em R o conjunto dos número reais: (∃ x∈R) (x2 + y2 = 0) (∃ x∈R) (∀y∈R) (x2 + y2 + 2z = 0) estão parcialmente quantificadas uma vez que existe pelo menos uma variável em cada fórmula que não foi previamente quantificada. Importante: uma fórmula parcialmente quantificada continua sendo uma sentença aberta nas variáveis que não foram quantificadas.

4.6. Comutatividade de Quantificadores Os quantificadores de uma dada fórmula somente podem ser comutados, de acordo com as seguintes regras: (i) Quantificadores de mesmo tipo podem ser comutados. Portanto a seguinte equivalência é válida: (∃ x) (∃ y) (P(x,y)) ⇔ (∃ y) (∃ x) (P(x,y)) e também é válida a equivalência: (∀x) (∀y) (P(x,y)) ⇔ (∀y) (∀x) (P(x,y)) e outras equivalências similares. (ii) Quantificadores de tipos distintos não podem ser comutados.

4.7. Simbolização de Enunciados Categóricos A combinação das sentenças abertas (predicados) com quantificadores dá origem a Lógica de Predicados (também chamada de Lógica de Primeira Ordem) que será estudada com mais detalhes no próximo capítulo. Porém, esta Lógica de Predicados deve muito de suas características à lógica tradicionalmente estudada nos textos de Filosofia, que trabalha com a noção de enunciados categóricos. Esta lógica tradicional tem suas origens na Lógica Aristotélica e também na Lógica Escolástica, criada pelos filósofos medievais. Um enunciado categórico é uma afirmação (uma frase) da linguagem natural, mas que possui uma estrutura mais ou menos formal. Estes enunciados permitem definir em linguagem natural expressões formadas por quantificadores e predicados. Os componentes básicos que formam um enunciado categórico são os tradicionais elementos estudados na gramática das linguagens naturais: o sujeito e o predicado da frase. Também compõem um enunciado categórico palavras que definem o tipo de quantificação sendo usada no enunciado.

UNISINOS - Lógica

Capítulo 4 - Quantificadores

Existem quatro tipos clássicos de identificados pelas letras A, E, I e O: Tipo A E I O

enunciados

categóricos,

tradicionalmente

Formato Geral do Enunciado Todo S é P Nenhum S é P Algum S é P Algum S não é P

Nestes enunciados S representa o sujeito da frase e P o predicado. O predicado representa sempre uma classe de elementos ou de entidades ao qual o sujeito deve pertencer. Assim, são exemplos válidos de enunciados as seguintes frases, uma para cada tipo de enunciado: (A) Todo ser humano é mortal. (E) Nenhuma fruta é de gosto amargo. (I) Algum pássaro é capaz de nadar. (O) Algum móvel da sala não é feito de madeira. A transformação deste tipo de enunciado para a lógica simbólica é feita levando em conta primeiro que todos os enunciados categóricos forçam que entidades que satisfazem as características ou propriedades do sujeito devem também satisfazer as características ou propriedades do predicado. Por exemplo, ao se enunciar que Todo S é P, na verdade se está afirmando que toda entidade que é S também é P. Isto leva a uma primeira transformação dos enunciados acima em um formato um pouco mais formal, onde estas entidades são indicadas pela variável x: (A’) Todo ser humano é mortal. Todo x que é ser humano, também é mortal. (E’) Nenhuma fruta é amarga. Nenhum x que é fruta também é de gosto amargo. (I’) Algum pássaro é capaz de nadar. Algum x que é pássaro também é capaz de nadar. (O’) Algum móvel da sala não é feito de madeira. Algum x que é móvel da sala também não é feito de madeira. As afirmações acima estão mais próximas da lógica simbólica, mas ainda falta esclarecer alguns detalhes relativos ao tipo de quantificador empregado em cada tipo de enunciado e também ao significado atribuído a palavra “também” usada nas afirmações acima. As palavras “todo” e “algum” usadas acima são referências diretas, respectivamente, aos quantificadores universais (“para todo”) e existencial (“existe pelo menos um”). Porém a forma (E) “Nenhum S é P” não designa diretamente um quantificador, mas

UNISINOS - Lógica

Capítulo 4 - Quantificadores

corresponde, na verdade, a afirmar que todos os x que são S não podem ser P. Isto permite a utilização do quantificador universal para representar o tipo (E). A palavra “também” indica que há uma relação lógica entre a afirmação relativa ao sujeito e a afirmação relativa ao predicado. Neste caso, considera-se que esta relação seja de conseqüência (implicação) lógica no caso das quantificações universais e de conjunção lógica no caso das quantificações existenciais. Levando isto em conta os exemplos acima podem ser transformados nas seguintes afirmações, quase simbólicas: (A”) Todo ser humano é mortal. Para todo x, se x é ser humano, então x é mortal. (E”) Nenhuma fruta é amarga. Para todo x, se x é fruta, então x não é de gosto amargo. (I”) Algum pássaro é capaz de nadar. Existe pelo menos um x tal que x é pássaro e x é capaz de nadar. (O”) Algum móvel da sala não é de madeira. Existe pelo menos um x tal que x é móvel da sala e x não é feito de madeira. O resultado final pode ser totalmente simbolizado, se assumirmos que U seja o conjunto universo (domínio) para os enunciados categóricos acima e que os predicados simbólicos H(x), M(x), F(x), A(x), P(x), N(x), S(x) e D(x) representem, respectivamente, as sentenças abertas “x é ser humano”, “x é mortal”, “x é fruta”, “x é de gosto amargo”, “x é pássaro”, “x é capaz de nadar”, “x é móvel da sala” e “x não é feito de madeira”: (A’”) Todo ser humano é mortal. (∀x∈U)(H(x) → M(x)) (E’”) Nenhuma fruta é amarga. (∀x∈U)(F(x) → ¬A(x)) (I’”) Algum pássaro é capaz de nadar. (∃ x∈U)(P(x) ∧N(x)) (O’”) Algum móvel da sala de aula não é de madeira. (∃ x∈U)(S(x) ∧¬D(x))

4.8. Exercícios sobre Quantificadores (4.2) Dar a negação das seguintes proposições (as mesmas do exercício (4.1)): (a) (∀x∈R) (|x| = x) (c) (∃ x∈R) (|x| = 0) (e) (∀x∈R) (x+1 > x)

(b) (∃ x∈R) (x2 = x) (d) (∃ x∈R) (x + 2 = x) (f) (∀x∈R) (x2 = x)

UNISINOS - Lógica

Capítulo 4 - Quantificadores

Para R o conjunto dos números reais e para |x| a função módulo de x, que é calculada como: |x| = x, se x ≥ 0 |x| = -x, se x < 0 (4.3) Sendo A = {2, 3, ..., 8, 9} dar um contra-exemplo para as afirmações: (a) (∀x∈A) (x + 5 < 12) (c) (∀x∈A) (x2 > 1) (e) (∀x∈A) (0x = 0)

(b) (∀x∈A) (x é primo) (d) (∀x∈A) (x é par) (f) (∀x∈A) (x | 72)

(4.4) Usando os seguintes símbolos: D(x) = “x é um dia” M = “segunda-feira” S(x) = “x está fazendo sol” T = “terça-feira” C(x) = “x está chovendo” formalize os seguintes enunciados no domínio formado pelo conjunto de todas as coisas: (a) Todos os dias está fazendo sol. (b) Em alguns dias não está chovendo. (c) Todo dia que não está fazendo sol está chovendo. (d) Alguns dias está fazendo sol e chovendo. (e) Nenhum dia está fazendo sol e chovendo ao mesmo tempo. (f) Segunda-feira fez sol; portanto, vai fazer sol todos os dias. (g) Choveu na segunda e na terça-feira. (h) Se chover algum dia, então vai fazer sol todos os dias. (4.5) Usando os seguintes símbolos: P(x) = “ x é uma pessoa” T(x) = “ x é um período de tempo” E(x,y) = “x é enganado por y” formalize os seguintes enunciados, no domínio formado pelo mundo inteiro: (a) Você pode enganar algumas pessoas durante todo o tempo. (b) Você pode enganar todas pessoas durante algum tempo. (c) Você não pode enganar todas as pessoas durante todo o tempo. (4.6) Supondo os seguintes símbolos: A(x,y) = “x ama y” j = “João” V(x) = “x é vistoso” c = “Cátia” H(x) = “x é um homem” M(x) = “x é uma mulher” B(x) = “x é bonita” dê versões para o Português para as fórmulas apresentadas abaixo: (a) V(j) ∧A(c,j) (b) (∀x) (H(x) → V(x)) (c) (∀x) (M(x) → (∀y)(A(x,y) → (H(y) ∧V(y)) ) ) (d) (∃ x) (H(x) ∧V(x) ∧A(x,c)) (e) (∃ x) (M(x) ∧B(x) ∧(∀y)(A(x,y) → (V(y) ∧H(y)) ) )

UNISINOS - Lógica

Capítulo 4 - Quantificadores

(f) (∀x) (M(x) ∧B(x)→ A(j,x) ) (4.7) Sendo A = {1,2,3,4,5} determinar o valor lógico (V ou F) de cada uma das seguintes proposições: (a) (∃ x∈A)(x+3=10) (c) (∃ x∈A)(x+3 72)

(b) (∀x∈A)(x+3 x ” e “x < 0” aplicadas aos números naturais.

•

As estruturas B1, B2 e B3 serão formadas pelo domínio B composto de todos os móveis de nossa sala de aula na Universidade com as interpretações IB1, IB2 e IB3 que mapeiam P(x) nos subconjuntos destes móveis que atendem, respectivamente, as seguintes propriedades: “x é preto”, “x é feito de ouro” e “x é de propriedade da Universidade”, onde x é um móvel da sala de aula.

Agora vamos definir algumas interpretações possíveis para esta fórmula, listadas na tabela abaixo: Estrutura

A1 A2

Interpretação Significado de P(x) IA1 x é primo IA2 x+1 > x

(∀x) (P(x)) F V

UNISINOS - Lógica

A3 B1 B2 B3

Capítulo 5 - A Lógica de Predicados

IA3 IB1 IB2 IB3

x x V x

Não é verdade que rosas são vermelhas ou violetas são azuis ou rosas não são vermelhas e violetas são azuis e mesmo que dizer que?

Dizer que “Não é verdade que rosas são vermelhas ou violetas são azuis, ou, rosas não são vermelhas e violetas são azuis” é mesmo que dizer que: A. rosas não são vermelhas.

Como que se escreve rosas são vermelhas violetas são azuis?

Rosas são vermelhas, violetas são azuis. Roses are red, violets are not. Rosas são vermelhas, a violeta é azul. Roses are red violets are blue.

proposição acima escolha

“rosas são vermelhas e violetas são azuis”. qual a negação da proposição acima? escolha uma:

Não é verdade que rosas são vermelhas ou violetas são azuis ou rosas não são vermelhas e violetas são azuis e mesmo que dizer que?

Como que se escreve rosas são vermelhas violetas são azuis?

Postagens relacionadas

Publicidade

ÚLTIMAS NOTÍCIAS

Qual a relação do petróleo com o efeito estufa?

Qual o tipo de microscópio mais indicado na rotina microbiológica?

Qual é o papel de um educador?

Por que os fungos são tão importantes para a indústria de alimentos?

Quando foi lançado o iphone 6

É possível fazer transferência de dinheiro de um banco para outro?

Um acionista ao analisar uma empresa pode estar preocupado em verificar

Sao paulo e rentistas onde assistir

Quais os aspectos que caracterizam o clima organizacional escolar?

Em que o caso Cambridge Analytica importa para jurisdição Digital?

Publicidade

Populer

Publicidade

Sobre

Jurídica

Ajuda

Social