IFMG Campus Formiga Matemática Discreta

Notas de Aula 1: Lógica, Predicados, Quantificadores e Inferência

Prof. Diego Mello 2o. Semestre 2012

Sumário

1 Introdução 3

2 Lógica Proposicional 3

3 Proposições 33.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33.2 Notação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Conectivos Lógicos 54.1 Negação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54.2 Conjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.3 Disjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.4 Disjunção Exclusiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.5 Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84.6 Bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.7 Resumo: Tabelas Verdade dos Conectivos Lógicos . . . . . . . . . . . . . . . . . . . . 134.8 Tabela Verdade para Proposições Compostas . . . . . . . . . . . . . . . . . . . . . . 134.9 Precedência de Operadores Lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.10 Linguagem Natural vs. Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154.11 Lógica e Operações Bit a Bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5 Equivalências Proposicionais 195.1 Tautologia, Contradição e Contingência . . . . . . . . . . . . . . . . . . . . . . . . . 195.2 Equivalências Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205.3 Equivalências Importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225.4 Construindo novas equivalências lógicas . . . . . . . . . . . . . . . . . . . . . . . . . 22

6 Predicados e Quantificadores 246.1 Limitações da lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246.2 Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246.3 Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

6.3.1 Quantificador Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266.3.2 Quantificador Existencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.3.3 Resumo dos quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296.3.4 Quantificador de Unicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1

6.3.5 Quantificadores com Restrição de Domínio . . . . . . . . . . . . . . . . . . . . 316.3.6 Precedência de Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . 326.3.7 Equivalências Lógicas Envolvendo Quantificadores . . . . . . . . . . . . . . . 326.3.8 Negação de Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.4 Quantificadores Aninhados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356.4.1 Declarações Envolvendo Quantificadores Aninhados . . . . . . . . . . . . . . . 356.4.2 Negação de Quantificadores Aninhados . . . . . . . . . . . . . . . . . . . . . . 38

7 Regras de Inferência 387.1 Argumentos Válidos em Lógica Proposicional . . . . . . . . . . . . . . . . . . . . . . 397.2 Regras e Inferência para Proposições Lógicas . . . . . . . . . . . . . . . . . . . . . . 43

7.2.1 Modus Ponens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447.2.2 Modus Tollens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457.2.3 Disjunção Aditiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2.4 Simplificação Conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2.5 Silogismo Disjuntivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.2.6 Silogismo Hipotético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487.2.7 Conjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487.2.8 Resolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497.2.9 Resumo das Regras de Inferência . . . . . . . . . . . . . . . . . . . . . . . . . 49

7.3 Construindo Argumentos por meio de Regras de Inferência . . . . . . . . . . . . . . . 517.4 Regras de Inferência para Quantificadores . . . . . . . . . . . . . . . . . . . . . . . . 537.5 Regras de Inferência para Proposições e Declarações Quantificadas . . . . . . . . . . 56

8 Exercícios de Fixação 58

2

1 Introdução

Este documento contém as notas de aula sobre o tema ‘Lógica, Predicados, Quantificadores e In-ferência’ da disciplina de Matemática Discreta do curso de Ciência da Computação do InsitutoFederal de Minas Gerais - Campus Formiga. Ela é baseada no conteúdo dos livros referenciadosneste documento.

Este documento serve apenas como referência para acompanhamento das aulas, e não substitui anecessidade de leitura e estudo da bibliografia oficial do curso. Muitos dos exemplos, tabelas ediagramas contidos no documento foram extraídos e/ou adaptados dos livros contidos na seção dereferências bibliográficas.

2 Lógica Proposicional

A lógica é considerada a base de todo o raciocínio matemático – e também do raciocínio automa-tizado. Em virtude disso, ela é empregada em diversos campos da Ciência da Computação, comopor exemplo nas linguagens de computador (execução lógica das instruções de um programa decomputador), inteligência artificial (sistemas especialistas) e projeto de computadores (álgebra deBoole e sua relação com as portas lógicas que compõem os circuitos digitais de um computador).

A lógica é também o mecanismo que usamos para construir declarações matemáticas. Suas regrassão usadas para distinguir os argumentos matemáticos válidos e inválidos.

3 Proposições

3.1 Definições

Em primeiro lugar, devemos definir o termo proposição.

Definição 1 (Proposição). Uma proposição é uma sentença declarativa que é verdadeira oufalsa, mas não ambas.

Exemplo:

• Brasília é a capital do Brasil

• 100 + 200 = 300

• 2 + 2 = 3

◭

3

Destas, as primeiras duas proposições são verdadeiras, enquanto que a terceira proposição é falsa.

Nem toda sentença é uma proposição. Para ser uma proposição, uma sentença deve ser uma sen-tença declarativa. Questionamentos, exclamações, ordens e sentenças deste tipo não podem serconsideradas como proposições porque não são nem verdadeiras nem falsas.

Exemplo:

• Que horas são?

• Que cidade bonita!

• Acorde e faça seus exercícios.

• x+ 1 = 2

• x+ y = z

◭

3.2 Notação

Usam-se letras para denotar variáveis proposicionais (i.e., variáveis que denotam proposições). Ovalor verdade de uma proposição é denotado por V (ou 1) se uma proposição for verdadeira, ouF (ou 0) se uma proposição for falsa. Normalmente usam-se as letras p, q, r, s, ... para indicarvariáveis proposicionais.

Exemplo:

• p: Santiago é a capital do Chile

• q: 5 + 2 = 7

• r: Hoje é sexta-feira

◭

As declarações precedentes representadas pelas letras p, q e r são declarações primitivas, poisnão tem jeito de quebrá-las em declarações mais simples.

Entretando, o matemático inglês George Boole criou um mecanismo onde novas proposições po-dem ser construídas a partir de proposições existentes, aplicando-se operadores lógicos (por vezesdenominados de conectivos lógicos). A estas novas proposições denominados de proposiçõescompostas.

Dessa forma, novas proposições podem ser criadas de duas maneiras, a saber:

4

• Transformando uma proposição p em uma proposição ¬p, que denota sua negação (lê-se ‘nãop’);

• Combinando duas ou mais proposições em uma proposição composta, usando um dos conec-tivos lógicos: conjunção, disjunção, implicação ou operador bicondicional.

4 Conectivos Lógicos

Formalizaremos cada um dos operadores lógicos a seguir, definindo e exemplificando cada um deles.

4.1 Negação

Definição 2 (Negação). Seja p uma proposição. A negação de p, indicada por ¬p ou p̄, é asentença ‘não é o caso de p’, é lida como ‘não p’. O valor verdade da negação de p (¬p) é o opostodo valor verdade de p.

Uma tabela verdade é uma tabela que contém as proposições nas colunas, e as possibilidades devalores-verdade nas linhas. É comum expressar os resultados de uma proposição composta por meiode tabelas verdade, que permitem analisar seus valores-verdade. Deste ponto em diante apresenta-remos a tabela verdade de cada conectivo lógico.

Segundo a Definição 2, para uma dada proposição p, temos a seguinte tabela verdade, cujo resultadode ¬p é apresentados na Tabela 1.

Tabela 1: Tabela verdade para a negação de pp ¬p0 11 0

Exemplo:

• p: Matemática discreta é fundamental para Ciência da Computação

• ¬p: Matemática discreta não é fundamental para Ciência da Computação

◭

5

4.2 Conjunção

Definição 3 (Conjunção). Sejam p e q proposições. A conjunção de p e q, indicada por p ∧ q,é a proposição ‘p e q’. A proposição p ∧ q é verdadeira quando p e q são verdadeiras, e falsa casocontrário.

De acordo com a Definição 3, somente quando p e q assumem valores V ou 1 é que o resultadoda proposição composta p ∧ q vale 1. Isto posto, a Tabela 2 representa a tabela verdade para oconectivo lógico de conjunção (∧).

Tabela 2: Tabela verdade para a conjunção (p ∧ q)p q p ∧ q

0 0 00 1 01 0 01 1 1

Exemplo:

• p: Brasília é a capital do Brasil

• p: Hoje é sexta feira

• p ∧ q: Brasília é a capital do Brasil e hoje é sexta-feira

◭

4.3 Disjunção

Definição 4 (Disjunção). Sejam p e q proposições. A disjunçao de p e q, indicada por p∨ p, é aproposição ‘p ou q’. A proposição p∨q é falsa se p e q são ambas falsas, e verdadeira caso contrário.

Pela Definição 4, para que a proposição composta p∨ q assuma valor verdadeiro basta que uma dasproposições primitivas (p ou q) seja verdadeira. Assim, a tabela verdade para o conectivo lógico dedisjunção (∨) é apresentada a seguir, na Tabela 3.

6

Tabela 3: Tabela verdade para a disjunção (p ∨ q)

p q p ∨ q

0 0 00 1 11 0 11 1 1

Exemplo:

• p: Brasília é a capital do Brasil

• p: Hoje é sexta feira

• p ∨ q: Brasília é a capital do Brasil ou hoje é sexta-feira

◭

4.4 Disjunção Exclusiva

Definição 5 (Disjunção Exclusiva). Sejam p e q proposições. A disjunção exclusiva de p e q(também denominada ou exclusivo), indicada por p ⊻ q ou p⊕ q, é a proposição que é verdadeiraexatamente quando apenas uma das proposições p ou q forem verdadeiras, e falsa caso contrário.

A proposição p⊕ q assume valor verdadeiro, segundo a Definição 5, quando apenas uma das propo-sições primitivas (p ou q) assume valor verdadeiro. A Tabela 4 sumariza os possíveis resultados dadisjunção exclusiva de p e q.

Tabela 4: Tabela verdade para a disjunção exclusiva (p⊕ q)p q p⊕ q

0 0 00 1 11 0 11 1 0

Exemplo:

• p: Brasília é a capital do Brasil

7

• p: Hoje é sexta feira

• p⊕ q: Ou Brasília é a capital do Brasil, ou hoje é sexta-feira, mas não ambas

◭

4.5 Condicional

Definição 6 (Condicional). Sejam p e q proposições. A proposição condicional p → q é aproposição ‘se p, então q’, ou ‘p implica q’. A proposição p → q é falsa quando p é verdadeira e qé falsa, caso contrário p → q é verdadeira.

De acordo com a Definição 6, a proposição composta p → q assume valor falso apenas quando aproposição p é verdadeira e q é falsa. Neste tipo de construção, a proposição p é denominada dehipótese, premissa ou antecedente, enquanto que a proposição q é denominado de conclusão,consequência ou consequente.

A tabela verdade que expressa os valores-verdade deste tipo de proposição é dada a seguir, na Ta-bela 5.

Tabela 5: Tabela verdade para a proposição condicional (p → q)p q p → q

0 0 10 1 11 0 01 1 1

Em Ciência da Computação, as estruturas condicionais If-Then e If-Then-Else estão presentesna maioria das linguagem de programação estruturadas. Essa estrutura tem alguma relação com aproposição condicional p → q.

Nela, a hipótese p geralmente representa uma expressão condicional, como por exemplo, x ≤ 15.Essa expressão torna-se uma declaração lógica que admite valores-verdade 0 ou 1, dependendo dovalor que a variável x assume em um determinado ponto da execução do programa.

Neste contexto, a conclusão q consiste na ‘declaração a ser executada’, direcionando a execuçãodo programa para outra linha ou imprimindo algum resultado. Aqui, q não assume o papel deproposição lógica que estamos discutindo, mas sim como uma instrução. Quando lidamos com umaestrutura do tipo ‘If p, Then q’, o computador executará q apenas se a expressão lógica p assumir

8

valor verdadeiro; caso contrário o programa saltará para a próxima instrução no código do pro-grama. Para estruturas do tipo ‘If p Then q Else r’, o programa avaliará p e executará q se p forverdadeiro, ou executará r se p for falso.

Além deste contexto, a proposição condicional p → q é usada como regra essencial no raciocíniomatemático; logo uma variedade de interpretações estão associadas à este tipo de construção.

Exemplo:

• p: NONONO é eleito

• q: NONONO vai reduzir os impostos

• p → q: Se NONONO for eleito, então NONONO vai reduzir os impostos

◭

Outras formas de interpretar a proposição p → q:

• Se p, então q

• p é suficiente para q

• p é uma condição suficiente para q

• p somente se q

• p é necessário para q

• p é condição necessária para q

• q se p

• q quando ocorrer p

• uma condição necessária para p é q

• q a menos que ¬p

• p implica q

• p apenas se q

• q sempre que p

• q segue de p

Para exemplificar, sejam as proposições

9

• p: Maria tira nota 10 no exame final

• q: Maria recebe o conceito A

Existem diversas maneiras de se interpretar a proposição p → q de maneira verbal. Vejamos algu-mas destas formas:

• Se Maria tirar nota 10 no exame final, então terá conceito A

• Maria vai receber conceito A quando tirar nota 10 no exame final

• Maria tirar nota 10 no exame final é suficiente para que Maria receba o conceito A

• Para receber o conceito A, é suficiente que Maria tire nota 10 no exame final

• Maria vai receber conceito A, a menos que não tire nota 10 no exame final

Nos casos apresentados como exemplo, as proposições foram usadas em linguagem natural ondeexiste uma relação entre a hipótese e a conclusão. Entretanto, quando as proposições p e q sãocombinadas na proposição p → q, não é necessário haver uma relação causal entre a hipótesee conclusão para que a implicação p → q seja verdadeira.

Exemplo:

• p: Hoje é sexta feira

• q: 2 + 3 = 5

• r: 2 + 3 = 6

• p → q: Se hoje é sexta-feira, então 2 + 3 = 5

• p → r: Se hoje é sexta-feira, então 2 + 3 = 6

◭

Do ponto de vista matemático, a proposição p → q é verdadeira sempre que as condições expressasna sua tabela verdade forem satisfeitas (ver Tabela 5). Isto ocorre porque o conceito matemáticode condicional é mais geral do que o usado em linguagem natural; tal conceito de condicional éindependente das relações causa-efeito entre a hipótese e a conclusão.

No exemplo acima, a proposição p → q é verdadeira porque a conclusão é verdadeira (de fato,2+3 = 5). Já a proposição p → r somente pode assumir valor verdadeiro se hoje não for sexta feirapois a conclusão 2 + 3 = 6 é falsa, e pela tabela verdade a única possibilidade de que p → r resulteem 1 é dada pela atribuição de valores-verdade 0 tanto para a hipótese quanto para a conclusão (sep é 0 e r é 0, então p → r resulta em 1).

10

Existem três proposições condicionais relacionadas à proposição p → q que ocorrem muito frequen-temente em lógica proposicional, e cujos resultados são de interesse do estudante. São elas:

1. Oposta de p → q: é a proposição q → p

2. Contrapositiva de p → q: é a proposição ¬q → ¬p

3. Inversa de p → q: é a proposição ¬p → ¬q

Acompanhe a tabela verdade destas proposições, cujos resultados são apresentados na Tabela 6.Pela tabela, temos que os mesmos valores-verdade ocorrem nas proposições condicional e contrapo-sitiva (destacadas em azul), assim como nas proposições oposta e inversa (destacadas em vermelho).

Tabela 6: Tabela verdade para as proposições oposta, contrapositiva e inversa de p → qp q ¬p ¬q p → q q → p ¬q → ¬p ¬p → ¬q0 0 1 1 1 1 1 10 1 1 0 1 0 1 01 0 0 1 0 1 0 11 1 0 0 1 1 1 1

Mais adiante veremos que duas proposições que possuem os mesmos valores-verdade são denomina-das de equivalentes; logo as proposições condicional e contrapositiva são equivalentes, assim comotambém são equivalentes as proposições oposta e inversa.

Exemplo:Sejam as proposições:

• p: Hoje é Páscoa

• q: Amanha é segunda-feira

Temos:

• condicional p → q: Se hoje é Páscoa, então amanhã é segunda feira

• contrapositiva ¬q → ¬p: Se amanhã não é segunda-feira, então hoje não é Páscoa.

• oposta q → p: Se amanhã é segunda-feira, então hoje é Páscoa

• inversa ¬p → ¬q: Se hoje não é Páscoa, então amanhã não é segunda-feira.

◭

11

4.6 Bicondicional

Definição 7 (Bicondicional). Sejam p e q proposições. A proposição bicondicional p ↔ q éa proposição ‘p se e somente se q’. A proposição p ↔ q é verdadeira sempre que p e q tem omesmo valor verdade, e falsa caso contrário. As proposições bicondicionais também são chamadasde bi-implicações.

Pela Definição 7, a proposição p ↔ q é verdadeira apenas quando p e q são ambas verdadeiras, ouambas falsas. Quando p e q possuem valores-verdade opostos, então essa proposição assume valor0. A Tabela 7 resume os valores-verdade possíveis de uma proposição bicondicional.

Tabela 7: Tabela verdade para a proposição bicondicional (p ↔ q)p q p ↔ q

0 0 10 1 01 0 01 1 1

Outras formas de se ler a proposição p ↔ q:

• p é necessária e suficiente para q

• se p, então q e vice-versa

• p se e somente se q

• p é necessário e suficiente para q

• p sse q

Note que, pela definição, p ↔ q equivale à (p → q) ∧ (q → p).

Exemplo:

• p: Você pode tomar um avião

• q: Você comprou uma passagem aérea

• p ↔ q: Você pode tomar um avião se e somente se você comprou uma passagem aérea

◭

12

4.7 Resumo: Tabelas Verdade dos Conectivos Lógicos

Tabela 8: Tabela verdade de todos os conectivos lógicosp q ¬p p ∧ q p ∨ q p⊕ q p → q p ↔ q

0 0 1 0 0 0 1 10 1 1 0 1 1 1 01 0 0 0 1 1 0 01 1 0 1 1 0 1 1

4.8 Tabela Verdade para Proposições Compostas

A tabela verdade para proposições compostas pode ser determinada incluindo uma coluna paracada proposição composta que ocorre na proposição composta original, de forma que a última co-luna corresponde à proposição composta original.

Exemplo:Construa a tabela verdade para a seguinte proposição composta: (p ∨ ¬q) → (p ∧ q)

Esta proposição envolve apenas duas variáveis proposicionais, p e q. A combinação dos valores-verdade para duas variáveis é V V , V F , FV e FF , de forma que a tabela verdade terá 4 linhas. Asduas primeiras colunas conterão os valores-verdade das variáveis p e q. A Tabela 9 apresenta estasituação.

Tabela 9: Passo 1: Inserir as variáveis proposicionais primitivasp q

1 11 00 10 0

A próxima etapa consiste em identificar qual será a próxima proposição composta que deve serdeterminada. No caso da proposição (p∨¬q) → (p∧ q), a próxima proposição deve ser a proposição¬q, que é necessária para determinar os valores-verdade de (p∨¬q). Adicionamos mais uma colunaà tabela verdade, e determinamos o valor de ¬q segundo a Tabela 8. O resultado final é dado naTabela 10.

13

Tabela 10: Passo 2: Adicionando a coluna ¬qp q ¬q1 1 01 0 10 1 00 0 1

Na próxima etapa, iremos determinar os valores-verdade da proposição (p ∨ ¬q). Incluiremos umanova coluna para esta proposição, e determinamos seus valores-verdade consultando a tabela ver-dade da operação lógica de disjunção entre duas proposições (ver Tabela 8). O resultado obtido éapresentado na Tabela 11.

Tabela 11: Passo 3: Adicionando a coluna (p ∨ ¬q)p q ¬q (p ∨ ¬q)1 1 0 11 0 1 10 1 0 00 0 1 1

Já temos os valores-verdade da hipótese da proposição (p ∨¬q) → (p ∧ q). Precisamos agora deter-minar a conclusão. Incluiremos mais uma coluna na tabela verdade, que receberá os valores-verdadeda proposição (p ∧ q), que podem ser obtidos diretamente da Tabela 8, operação de conjunção deduas proposições. Os resultados obtidos são apresentados a seguir, na Tabela 12.

Tabela 12: Passo 4: Adicionando a coluna (p ∧ q)

p q ¬q (p ∨ ¬q) (p ∧ q)

1 1 0 1 11 0 1 1 00 1 0 0 00 0 1 1 0

Por fim, chegamos à proposição composta original, i.e., (p ∨ ¬q) → (p ∧ q). Para obter os valores-verdade para esta proposição, devemos adicionar uma nova coluna com este conteúdo, consultar osvalores-verdade já determinados para a hipótese (p ∨ ¬q) e conclusão (p ∧ q), e com base na tabelaverdade da proposição condicional (→) apresentada na Tabela 8 chegamos à tabela verdade finalpara a proposição composta (p ∨ ¬q) → (p ∧ q), cujos resultados são dados pela Tabela 13.

14

Tabela 13: Passo 5: Adicionando a coluna (p ∨ ¬q) → (p ∧ q)

p q ¬q (p ∨ ¬q) (p ∧ q) (p ∨ ¬q) → (p ∧ q)

1 1 0 1 1 11 0 1 1 0 00 1 0 0 0 10 0 1 1 0 0

◭

4.9 Precedência de Operadores Lógicos

Assim como na algebra, os conectivos lógicos possuem precedência, isto é, existem prioridades quedevem ser avaliadas na interpretação de uma proposição composta. A ordem de precedência destesoperadores é dada a seguir, na Tabela 14.

Tabela 14: Ordem de precedência dos conectivos lógicosOperador Prioridade

¬ 1∧ 2∨ 3→ 4↔ 5

4.10 Linguagem Natural vs. Proposições

A linguagem natural, em geral, permite escrever sentenças ambiguas. Traduzir sentenças em lingua-gem em proposições compostas acaba com essa ambiguidade. Uma vez traduzidas em expressõeslógicas, podemos analisar seus valores-verdade, manipulá-las e aplicar regras de inferência para ra-ciocinar sobre tais sentenças.

Exemplo:

Sejam s, t e u proposições primitivas tais que

• s: João sai para caminhar lá fora

• t: O dia está ensolarado

• u: Está nevando

15

Possíveis traduções em linguagem natural para as proposições compostas escritas em linguagemlógica

• (t ∧ ¬u) → s: Se o dia estiver ensolarado e não estiver nevando, então João sairá pracaminhar lá fora

• t → (¬u → s): Se o dia estiver ensolarado, então se não estiver nevando João sairá paracaminhar lá fora

• ¬(s ↔ (u ∨ t)): João não irá caminhar lá fora se e somente se estiver nevando ou o diaestiver ensolarado

Possíveis traduções em linguagem lógica para as proposições compostas escritas em linguagem na-tural

• João sairá pra caminhar se e somente se o dia estiver ensolarado: s ↔ t

• Se estiver nevando e o dia não estiver ensolarado, então João não sairá para caminhar láfora: (u ∧ ¬t) → ¬s

• Está nevando mas João irá caminhar lá fora mesmo assim: u ∧ s

◭

Exemplo:

Seja a sentença em linguagem natural: ‘Você não pode andar de montanha russa se você tivermenos do que 1,20 metros de altura a menos que você tenha 16 anos de idade.’ Podemos fazer atradução desta sentença em proposições compostas da seguinte maneira. Sejam as primitivas

• q: Você pode andar de montanha russa

• r: Você tem menos do que 1,20 m de altura

• s: Você tem mais de 16 anos de idade

Então, a sentença em linguagem natural pode ser traduzida em proposições lógicas como: (r∧¬s) →¬q, ou ainda (¬r ∨ s) → q ◭

Conforme mencionado, a tradução das sentenças de linguagem natural para proposições lógicaselimina as ambiguidades. Isso é muito importante na atividade de especificação de sistemas dehardware e software de forma que um sistema em desenvolvimento use tais especificações. Propo-sições compostas podem, dessa forma, serem empregadas com este propósito.

Uma especificação de sistema deve ser consistente, i.e., não conter especificações conflitantes quepossam ser usadas para derivar uma contradição. Se as especificações não forem consistentes, pode

16

ser que não haja uma forma de desenvolver um sistema que atenda a todas elas.

Exemplo:

Determine se estas especificações de sistema são consistentes:

• A mensagem de diagnóstico é armazenada no buffer ou ela é retransmitida

• A mensagem de diagnóstico não é armazenada no buffer

• Se a mensagem de diagnóstico é armazenada no buffer, então ela é retransmitida

A verificação de consistência de um sistema passa pela sua tradução em expressões lógicas. Sejamas proposições primitivas

• p: A mensagem de diagnóstico é armazenada no buffer

• q: A mensagem de diagnóstico é retransmitida

As três especificações acima podem ser traduzidas como:

• A mensagem de diagnóstico é armazenada no buffer ou ela é retransmitida: p ∨ q

• A mensagem de diagnóstico não é armazenada no buffer: ¬p

• Se a mensagem de diagnóstico é armazenada no buffer, então ela é retransmitida p → q

Verificando a consistência das três especificações por meio da tabela verdade:

Tabela 15: Tabela Verdade para as especificações (p ∨ q), (¬p) e (p → q)

p q p ∨ q ¬p p → q

1 1 1 0 11 0 1 0 00 1 1 1 10 0 0 1 1

Uma atribuição de valores que torna as três especificações verdadeiras é observada na Tabela 15,quando a proposição p é falsa (i.e., atribui-se valor 0 para p) e a proposição p é verdadeira (i.e.,atribui-se valor 1 para q). Dessa forma, vemos que a especificação de sistema apresentado é consis-tente. ◭

Exemplo:A especificação do sistema apresentado no exemplo anterior se mantém consistente se adicionarmosuma nova especificação ‘A mensagem de diagnóstico não é transmitida’?

17

Tabela 16: Tabela Verdade para as especificações (p ∨ q), (¬p) e (p → q) e (¬q)p q p ∨ q ¬p p → q ¬q1 1 1 0 1 01 0 1 0 0 10 1 1 1 1 00 0 0 1 1 1

Faremos tal verificação recorrendo novamente à tabela verdade, que agora contempla a proposição(¬q). A tabela verdade desta especificação de sistemas é dada a seguir, na Tabela 16.

Pelos valores-verdade encontrados na Tabela 16, observamos que não existe nenhuma atribuição devalores de p e q que satisfaçam as quatro especificações apresentadas. Isto posto, concluímos queesta especificação de sistema é inconsistente. ◭

4.11 Lógica e Operações Bit a Bit

A representação da informação em um computador digital é feita usando-se bits. Um bit é umsímbolo com dois valores possíveis: 0 e 1, que pode ser interpretado como V e F. Uma variávelbooleana é aquela que admite apenas dois valores: verdadeiro ou falso. Uma variável booleana podeser representada por um bit.

Uma operação binária é um cômputo que corresponde à aplicação dos conectivos lógicos ∨, ∧ e ⊕,denominados de OR, AND e XOR nas linguagens de programação, à um ou mais bits. A mesma tabelaverdade destes conectivos lógicos se aplica às operações bit a bit.

Definição 8 (String). Uma string de bits é uma sequência de zero ou mais bits. O tamanho dastring é o número de bits da string.

Exemplo:Encontre as strings de bits que resultam das operações OR, AND e XOR aplicadas sobre as strings S1:1011011101 e S2: 0010101111.

S1 1 0 1 1 0 1 1 1 0 1S2 0 0 1 0 1 0 1 1 1 1

S1 OR S2 1 0 1 1 1 1 1 1 1 1S1 AND S2 0 0 1 0 0 0 1 1 0 1S1 XOR S2 1 0 0 1 1 1 0 0 1 0

◭

18

5 Equivalências Proposicionais

Conforme já foi mencionado neste documento, se duas proposições compostas possuem os mesmosvalores-verdade, então elas são equivalentes. Isso permite, por exemplo, que se substitua uma pro-posição composta por outra equivalente na construção de argumentos matemáticos.

Antes de definir formalmente o conceito de equivalência, devemos formalizar a classificação dasproposições de acordo com seus possíveis valores-verdade.

5.1 Tautologia, Contradição e Contingência

Definição 9 (Classificação). Uma proposição composta que é sempre verdadeira, independente dosvalores-verdade das proposições que nela ocorrem, é denominada de tautologia. Uma proposiçãocomposta que é sempre falsa é chamada de contradição. Uma proposição composta que não é nemuma tautologia, nem uma contradição, é denominada contingência.

Exemplo:Tautologias e contradições podem ser construídas com o uso de apenas uma variável proposicionale dos conectivos lógicos de conjunção e disjunção, conforme ilustra a tabela verdade expressa naTabela 17.

Tabela 17: Tabela Verdade para as proposições (p ∨ ¬p) e (p ∧ ¬p)p ¬p p ∨ ¬p p ∧ ¬p0 1 1 01 0 1 0

◭

Exemplo:A proposição composta p ∧ q → (p ↔ q) é uma tautologia (ver Tabela 18)

Tabela 18: Tabela Verdade para a proposição p ∧ q → (p ↔ q)p q p ∧ q p ↔ q p ∧ q → (p ↔ q)

0 0 0 1 10 1 0 0 11 0 0 0 11 1 1 1 1

19

◭

Exemplo:A proposição composta (p ∧ q) ∧ ¬(p ∨ q) é uma contradição (ver Tabela 19)

Tabela 19: Tabela Verdade para a proposição (p ∧ q) ∧ ¬(p ∨ q)p q p ∧ q p ∨ q ¬(p ∨ q) (p ∧ q) ∧ ¬(p ∨ q)

0 0 0 0 1 00 1 0 1 0 01 0 0 1 0 01 1 1 1 0 0

◭

Exemplo:A proposição composta p → ¬p é uma contingência (ver Tabela 20).

Tabela 20: Tabela Verdade para a proposição p → ¬pp ¬p p → ¬p0 1 11 0 0

◭

As tautologias e contradições tem fundamental importância quando usadas em métodos de prova,que veremos adiante na disciplina.

5.2 Equivalências Lógicas

Definição 10 (Equivalência). As proposições compostas p e q são chamadas logicamente equiva-

lentes se p ↔ q é uma tautologia. A notação p ≡ q indica que as proposições p e q são logicamenteequivalentes.

Denominados de algebra de proposições o uso das tabelas verdade das proposições para desen-volver a idéia de quando duas entidades são essencialmente as mesmas.

20

Uma das formas de verificar se duas proposições p e q são equivalentes consiste em usar a tabelaverdade. Elas serão equivalentes se as colunas que fornecem seus valores-verdade forem idênticas.

Exemplo:Sejam as proposições p → q e ¬q → ¬p. Mostre, pela tabela verdade, que estas proposições sãologicamente equivalentes (ver resultado na Tabela 21).

Tabela 21: Tabela verdade para as proposições p → q e ¬q → ¬pp q ¬p ¬q (p → q) (¬q → ¬p) (p → q) ↔ (¬q → ¬p)0 0 1 1 1 1 10 1 1 0 1 1 11 0 0 1 0 0 11 1 0 0 1 1 1

Assim, a proposição condicional (p → q) e sua contrapositiva (¬q → ¬p) são equivalentes. ◭

Exemplo:Mostre que as proposições ¬(p ∨ q) e ¬p ∧ ¬q são equivalentes1.

Faremos isto construindo a tabela verdade destas proposições, cujos resultados são apresentadosna Tabela 22. Incluiremos também uma nova proposição composta ¬(p ∨ q) ↔ (¬p ∧ ¬q), quemostraremos ser uma tautologia por meio de seus valores-verdade.

Tabela 22: Tabela verdade para as proposições ¬(p ∨ q) e (¬p ∧ ¬q)p q ¬p ¬q p ∨ q ¬(p ∨ q) ¬p ∧ ¬q ¬(p ∨ q) ↔ (¬p ∧ ¬q)0 0 1 1 0 1 1 10 1 1 0 1 0 0 11 0 0 1 1 0 0 11 1 0 0 1 0 0 1

A Tabela 22 mostra que a proposição ¬(p ∨ q) possui os mesmos valores-verdade da proposição(¬p∧¬q). Pela Definição 10, temos que ¬(p∨ q) ↔ (¬p∧¬q) é uma tautologia, logo as proposições¬(p ∨ q) e (¬p ∧ ¬q) são equivalentes. ◭

Exemplo:Mostre que p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r) são equivalentes2.

1Essa equivalência é uma das duas Leis de De Morgan2Propriedade distributiva da disjunção sobre a conjunção

21

Faremos isso construíndo a tabela verdade, cujos resultados são dados na Tabela 23.

Tabela 23: Tabela verdade para as proposições p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r)

p q r q ∧ r p ∨ (q ∧ r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r) [p ∨ (q ∧ r)] ↔ [(p ∨ q) ∧ (p ∨ r)]

0 0 0 0 0 0 0 0 10 0 1 0 0 0 1 0 10 1 0 0 0 1 0 0 10 1 1 1 1 1 1 1 11 0 0 0 1 1 1 1 11 0 1 0 1 1 1 1 11 1 0 0 1 1 1 1 11 1 1 1 1 1 1 1 1

◭

5.3 Equivalências Importantes

Existem algumas equivalências importantes muito usadas na simplificação de expressões lógicas.Este documento lista tais equivalências na Tabela 24.

Tabela 24: Equivalências lógicas importantesPropriedade Equivalência lógica

Identidadep ∧ 1 ≡ pp ∨ 0 ≡ p

Dominaçãop ∨ 1 ≡ 1p ∧ 0 ≡ 0

Idempotentep ∨ p ≡ pp ∧ p ≡ p

Dupla Negação¬(¬p) ≡ p

Comutativap ∨ q ≡ q ∨ pp ∧ q ≡ q ∧ p

Propriedade Equivalência lógica

Associativa(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Distributivap ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

Leis de De Morgan¬(p ∨ q) ≡ ¬p ∧ ¬q¬(p ∧ q) ≡ ¬p ∨ ¬q

Absorçãop ∨ (p ∧ q) ≡ pp ∧ (p ∨ q) ≡ p

Negação ou Inversap ∨ ¬p ≡ 1p ∧ ¬p ≡ 0

5.4 Construindo novas equivalências lógicas

As equivalências lógicas podem ser usadas para construir equivalências lógicas adicionais, uma vezque uma proposição composta pode ser substituída por outra proposição composta que é equivalente

22

sem alterar os valores-verdade da proposição original.

Exemplo:Mostre que a proposição composta ¬(p ∨ (¬p ∧ q)) e ¬p ∧ ¬q são equivalentes.

Expressão Propriedade aplicada Resulta em¬(p ∨ (¬p ∧ q)) Lei de De Morgan ≡ ¬p ∧ ¬(¬p ∧ q)≡ ¬p ∧ ¬(¬p ∧ q) Lei de De Morgan ≡ ¬p ∧ (¬¬p ∨ ¬q)≡ ¬p ∧ (¬¬p ∨ ¬q) Dupla Negação ≡ ¬p ∧ (p ∨ ¬q)≡ ¬p ∧ (p ∨ ¬q) Distributiva ≡ (¬p ∧ p) ∨ (¬p ∧ ¬q)≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) Inversa ≡ 0 ∨ (¬p ∧ ¬q)≡ 0 ∨ (¬p ∧ ¬q) Identidade ≡ ¬p ∧ ¬q≡ ¬p ∧ ¬q

Após a aplicação sucessiva de equivalências, mostramos que ¬(p ∨ (¬p ∧ q)) e ¬p ∧ ¬q são equiva-lentes e possuem os mesmos valores-verdade. Outra maneira de demonstrar essa equivalência é aconstrução da tabela verdade destas expressões lógicas. Para o caso deste exemplo, ver Tabela 25.

Tabela 25: Tabela verdade para as proposições ¬(p ∨ (¬p ∧ q)) e ¬p ∧ ¬qp q ¬p ¬q ¬p ∧ ¬q ¬p ∧ q p ∨ (¬p ∧ q) ¬(p ∨ (¬p ∧ q))

0 0 1 1 1 0 0 10 1 1 0 0 1 1 01 0 0 1 0 0 1 01 1 0 0 0 0 1 0

Com isso, fica demonstrado que ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q ◭

Exemplo:

Dadas as proposições primitivas p e q, existe alguma forma de expressar a proposição composta(p ∨ q) ∧ ¬(¬p ∧ q), i.e., podemos encontrar uma proposição mais simples que seja equivalente àproposição composta dada?

Expressão Propriedade aplicada Resulta em(p ∨ q) ∧ ¬(¬p ∧ q) Lei de De Morgan ≡ (p ∨ q) ∧ (¬¬p ∨ ¬q)≡ (p ∨ q) ∧ (¬¬p ∨ ¬q) Dupla Negação ≡ (p ∨ q) ∧ (p ∨ ¬q)≡ (p ∨ q) ∧ (p ∨ ¬q) Distributiva de ∨ sobre ∧ ≡ p ∨ (q ∧ ¬q)≡ p ∨ (q ∧ ¬q) Inversa ≡ p ∨ 0≡ p ∨ 0 Identidade ≡ p≡ p

23

Pela simplificação, temos que (p ∨ q) ∧ ¬(¬p ∧ q) ≡ p. ◭

6 Predicados e Quantificadores

6.1 Limitações da lógica proposicional

A lógica proposicional nem sempre consegue expressar adequadamente o significado das proposi-ções em linguagem matemática e em linguagem natural, visto que formulas proposicionais tem umapossibilidade limitada de expressão.

Para exemplificar, sejam as sentenças:

• ‘Para todo x, x > 0’

• ‘Todo computador conectado à rede do LAB01 está com vírus’

• ‘Existe um aluno da classe de matemática discreta que não passou em Cálculo I’

Suponha que cada uma das sentenças declaradas acima sejam verdadeiras. Não é possível simboli-zar tais sentenças adequadamente usando apenas variáveis proposicionais, parênteses e conectivoslógicos, como fizemos até o presente momento.

Isto ocorre porque elas contém elementos novos (‘para todo’, ‘para cada’, ‘para algum’) que sãoligados ao conceito de predicados e quantificadores. Quantificadores são frases do tipo ‘para todo’,‘para cada’, ‘para algum’, que relacionam quantos objetos possuem uma determinada propriedade.

Para estes casos, a lógica de predicados pode ser usada para expressar o significado de umagrande faixa de declarações deste tipo que nos permite raciocinar e explorar relacionamentos entreobjetos.

6.2 Predicados

Definição 11 (Predicado). Uma propriedade ou relacionamento entre objetos é denominado pre-

dicado. A descrição de um predicado em lógica é denominada de fórmula.

Sejam as declarações:

• x > 3

• x = y + 3

24

• x+ y = z

• O computador x está sob ataque de um intruso

• O computador x está funcionando adequadamente

Diversas sentenças que envolvem variáveis são encontradas com frequência em afirmações matemá-ticas, programas de computadores e especificação de sistemas.

Sentenças que possuem variáveis não são nem verdadeiras nem falsas enquanto não se especificarum valor para elas (logo, sentenças com variáveis não são proposições).

Referimos à sentenças do tipo ‘O número x+ 2 é um inteiro par’ como sentença aberta, que seráformalizada a seguir, nas Definições 12 e 13.

Definição 12 (Sentença Aberta). Dado um conjunto A 6= ∅, uma sentença aberta em A é umaexpressão P (x) de modo que, para cada a ∈ A, P (a) é uma proposição. Dado a ∈ A, tem-se P (a)verdadeiro ou falso.

Definição 13 (Sentença Aberta). Uma sentença é uma sentença aberta se:

1. Ela contém uma ou mais variáveis, e

2. Ela não é uma proposição, mas

3. Ela torna-se uma proposição quando suas variáveis são substituídas por certos valores permis-síveis.

Na declaração ‘x > 3’, podemos dividí-la em duas partes: o sujeito (neste caso, a variável x) e opredicado da declaração (neste caso, a propriedade que o sujeito da declaração deve ter, ou seja, ‘émaior do que 3’). Em termos de notação, denotamos a declaração ‘x é maior do que 3’ por P (x),onde P denota o predicado ‘é maior do que 3’ e x é a variável ao qual o predicado se aplica.

A declaração P (x) é dita ser o valor da função proposicional P em x. Uma vez que se atribuium valor para a variável x, a declaração P (x) torna-se uma proposição que possui valores-verdade.

Exemplo:Seja P (x) a declaração ‘x > 3. Qual é o valor verdade de P (4) e P (2)?

Obtemos P (4) pela substituição de x = 4 e P (2) pela substituição de x = 2 na declaração ‘x > 3’.Assim, P (4) é verdadeira, enquanto que P (2) é falsa. ◭

25

Podemos trabalhar com afirmações que envolvam mais de uma variável. Por exemplo, considere aafirmação ‘x = y+3’. Podemos indicá-la por Q(x, y), em que x e y são variáveis e Q é o predicado.Quando determinamos valores para as variáveis x e y, a sentença aberta Q(x, y) torna-se uma pro-posição e possui valores-verdade.

Exemplo:Seja Q(x, y): os números y + 2, x− y e x+ 2y são inteiros pares.

Temos:

• Q(4, 2): os números 4, 2 e 8 são inteiros pares: VERDADEIRO

• Q(5, 2): os números 4, 3 e 9 são inteiros pares: FALSO

• Q(10, 3): os números 5, 7 e 16 são inteiros pares: FALSO

◭

Em geral, uma sentença que envolva n variáveis pode ser denotada por P (x1, x2, . . . , xn) e é denomi-nada de função proposicional P para a n-upla (x1, x2, . . . , xn), e P é denominado de predicadon-ário.

Por fim, ainda existe a negação de uma sentença aberta, que consiste na aplicação do operadorlógico de negação sob a sentença, i.e., ¬P (x). Por exemplo, se P (x) é uma função proposicionalque declara que ‘o número x + 2 é um inteiro par’, então ¬P (x)’ deve ser interpretado como adeclaração ‘o número x+ 2 não é um inteiro par’. Diante desta sentença aberta, temos que P (7) éfalso, enquanto que ¬P (7) é verdadeiro.

6.3 Quantificadores

Quando atribuímos valores às variáveis de uma função proposicional, a sentença resultante torna-seuma proposição e assume um valor verdade. Entretanto, existe outra maneira de se criar proposi-ções a partir de funções proposicionais, denominada quantificação.

A quantificação permite-nos dizer que um dado predicado P é verdadeiro para um conjunto deelementos.

A área da lógica que estuuda os predicados e quantificadores é denominada de cálculo de predi-cados.

6.3.1 Quantificador Universal

Algumas afirmações matemáticas referem-se à uma propriedade que é verdadeira para todos osvalores que uma variável pode assumir em um determinado domínio/universo do discurso. Aquantificação universal de P (x) para um domínio particular é a proposição que afirma que P (x)é verdadeiro para todos os valores de x neste domínio. O domínio deve sempre ser especificado

26

quando um quantificador universal for usado.

Definição 14 (Quantificação Universal). Uma quantificação universal de P (x) é a declaraçãodo tipo ‘P (x) para todos os valores de x no domínio’

A notação ∀xP (x) denota uma quantificação universal de P (x)

O símbolo ∀ é denominado quantificador universal. A notação ∀xP (x) é lida como ‘para todoxP (x)’ ou ‘para cada xP (x).

Um elemento para o qual xP (x) é falso é denominado de contra-exemplo de ∀xP (x).

Seja A o conjunto domínio de uma sentença aberta. Se A = ∅, entende-se que a quantificaçãouniversal ∀x ∈ A(S) é verdadeira, não importa qual seja a sentença S.

Exemplo:Seja a sentença aberta ‘R(x): 2x é um inteiro par’ cujo domínio/universo é o conjunto de númerosinteiros (Z)

A quantificação universal ∀xR(x) é verdadeira, pois independente que qual valor inteiro seja subs-tituído na variável x (par ou ímpar), o resultado sempre será par. ◭

Exemplo:Seja a sentença aberta ‘x+ 1 > x. Qual é o valor verdade da quantificação ∀xP (x) no domínio dosnúmeros reais (R)?

Ao substituir a variável x por qualquer número real na sentença aberta P (x), sempre tomaremosproposições que são verdadeiras. Como P (x) é verdadeiro para todos os números reais, temos quea quantificação universal ∀xP (x) é verdadeira. ◭

Seja P (x) uma função proposicional. Uma sentença ∀x(Px) é falsa se e somente se P (x) não ésempre verdadeiro para as variáveis x no seu domínio.

Uma das maneiras de fazê-lo consiste em apresentar um contra-exemplo para a declaração ∀xP (x).Veremos adiante que buscar por contra-exemplos em proposições universalmente quantificadas éimportante no estudo da matemática discreta, em especial nas provas por contra-exemplo.

Exemplo:Qual o valor verdade de ∀xP (x), em que P (x) é a proposição ‘x2 < 10 e o domínio consiste noconjunto dos inteiros positivos que não excedem 4?

27

A declaração ∀xP (x) é equivalente à conjunção P (1) ∧ P (2) ∧ P (3) ∧ P (4), visto que o conjuntodomínio é A = {1, 2, 3, 4}. Como P (4) é falso, então a quantificação universal ∀x(P (x)) também éfalsa. ◭

Exemplo:Sejam as sentenças abertas, cujo universo compreende todos os números reais (R).

• Q(x) : x2 ≥ 0

• S(x) : x2 − 3 ≥ 0

A quantificação ∀x[Q(x) → S(x)] é verdadeira ou falsa?

Esta sentença pode ser traduzida como: ‘para todo número real, se x2 ≥ 0, então x2 − 3 ≥ 0’. Paramostrar que esta declaração é falsa, basta apresentarmos um contra-exemplo, isto é, um valor de xpara o qual [Q(x) → S(x)] seja falso.

Substituindo-se x por 1, temos Q(1) : (1)2 ≥ 0, verdadeiro, e S(1) : (1)2−3 ≥ 0, falso. Encontramosum caso onde [Q(x) → S(x)] é falso; logo a declaração ∀x[Q(x) → S(x)] é falsa porque existe pelomenos um valor de x para o qual [Q(x) → S(x)] é falso. ◭

Exemplo:Qual o valor verdade de ∀x(x2 ≥ x) se o conjunto domínio for:(a) o conjunto Z?(b) o conjunto R?

Se o conjunto domínio for o conjunto dos números inteiros Z, então é sempre verdade que x2 ≥ x,para todos os inteiros.

No entanto, se o domínio for o conjunto dos números reais R, então existem contra-exemplos quemostram que a quantificação universal é falsa. Para exemplificar, sejam dois contra-exemplos osnúmeros 1/2 e 1/3, que pertencem aos números reais e onde

(

12

)2 6≥(

12

)

, ou(

13

)2 6≥(

13

)

. Isso ocorrerápara qualquer número contido no intervalo (0, 1). ◭

6.3.2 Quantificador Existencial

Muitas sentenças matemáticas afirmam que existe um elemento que possui uma certa propriedade.Tais sentenças podem ser expressas usando-se quantificação existencial. Por meio delas, formamosuma proposição que é verdadeira se e somente se P (x) é verdadeiro para pelo menos um valor de xdo domínio.

28

Definição 15 (Quantificação Existencial). A quantificação existencial de P (x) é a proposição‘existe um elemento x do domínio tal que P (x).

Usa-se a notação ∃xP (x) para a quantificação existencial de P (x). O símbolo ∃ é denominadoquantificador existencial.

A quantificação existencial ∃xP (x) é lida como ‘existe um x tal que P (x)’, ou ‘existe pelo menosum x tal que P (x)’, ou ainda, ’para algum x, P (x)’.

Seja A o conjunto domínio de uma sentença aberta S. Se A = ∅, entende-se que a quantificaçãoexistencial ∃x ∈ A(S) é falsa, não importa qual seja a sentença S.

Exemplo:Seja P (x) a expressão x > 3, cujo domínio é o conjunto dos números reais (R). Qual é o valorverdade da quantificação existencial ∃xP (x)?

Como a sentença x > 3 é verdadeira para pelo menos alguns números reais (por exemplo, para{4, 5, 6, . . . ...}, então a quantificação ∃xP (x) é verdadeira. ◭

Exemplo:Sejam as seguintes sentenças abertas, no domínio dos números reais (R)

• P (x): x ≥ 0

• Q(x): x2 − 3x− 4 = 0

Verificar se a quantificação ∃x[P (x) ∧Q(x)] é verdadeira ou falsa.

Para que a quantificação apresentada seja verdadeira, devemos apresentar pelo menos um caso emque a proposição [P (x) ∧Q(x)] seja verdadeira.

Por tratar-se de uma proposição composta por meio de um conectivo de conjunção, para que a sen-tença aberta [P (x)∧Q(x)] seja verdadeira, ambas as sentenças P (x) e Q(x) devem ser verdadeiras.Dentre os possíveis valores que x pode admitir dentro do conjunto R, o número 4 é um dos valoresque tornam P (4) : (4) ≥ 0 verdadeiro, e Q(4) : (4)2 − 3(4) − 4 = 0 também verdadeiro.

Logo, concluímos que a quantificação ∃x[P (x) ∧Q(x)] é verdadeira. ◭

6.3.3 Resumo dos quantificadores

Diante dos resultados apresentados nas sub-seções anteriores, podemos resumir as situações em quecada quantificador é verdadeiro ou falso na Tabela 26.

29

Tabela 26: Resumo: quantificadores universal e existencial

Sentença Quando é Verdadeiro Quando é Falso

∃xP (x)Para algum (pelo menos um) no domínio,P (a) é verdadeiro

Para todo a no domínio, P (a) é falso

∀xP (x)Para toda a substituição de a do domínio,P (a) é verdadeiro

Existe pelo menos uma substituição de ado domínio para o qual P (a) é falso

∃x¬P (x)Para pelo menos uma escolha de a no do-mínio, P (a) é falso tal que ¬P (a) seja ver-dadeiro

Para toda substituição de a no domínio,P (a) é verdadeiro

∀x¬P (x)Para toda substituição de a no domínio,P (a) é falso e sua negação ¬P (a) é verda-deiro

Existe pelo menos uma substituição de ado domínio para o qual ¬P (a) é falso eP (a) é verdadeiro

6.3.4 Quantificador de Unicidade

Definição 16 (Quantificação de Unicidade). O quantificador de unicidade, também conhecidocomo quantificador de singularidade, declara que ‘existe um único x tal que P (x) é verdadeiro’,denotado pelo símbolo ∃! ou ∃1.

A notação ∃!xP (x) afirma que ‘existe um único x tal que P (x).

Exemplo:Seja a sentença aberta P (x) : x2 = 4. Verificar a veracidade da sentença no domínio:(a) dos números naturais (N)(b) dos números inteiros (Z).

No domínio dos naturais, a proposição ∃!x(x2 = 4) é verdadeira, pois o número 2 é o único númerodo conjunto N que, quando elevado ao quadrado, resulta em 4.

No domínio dos inteiros, a proposição ∃!x(x2 = 4) é falsa, pois os números 2 e −2 do conjunto Z

possuem quadrado igual a 4. ◭

Exemplo:Verificar o valor-verdade das seguintes quantificações de unicidade, no domínio dos números natu-rais (N):

∃!n(n < 1): verdadeira, pois apenas o número 0 satisfaz a condição

∃!n(n! < 10): falsa, pois os fatoriais de 0, 1, 2 e 3 são todos menores que 10.

30

∃!n(n+ 1 > n): falsa, pois para quaisquer número natural, n+ 1 é sempre maior do que n.

∃!n(2n é par): falsa, pois o conjunto dos números naturais é infinito, logo existem infinitos númerosdeste domínio que são pares: {2, 4, 6, 8, 10, . . . }. ◭

6.3.5 Quantificadores com Restrição de Domínio

Pode-se restringir o domínio de um quantificador utilizando-se uma notação abreviada, onde a con-dição que a variável deve satisfazer é incluída após o quantificador.

Exemplo:Seja V = {1, 2, . . . , 30}, e seja A[1..30] um array tal que para cada índice i entre 1 e 30, A[i] =

i * i - 1. Para os elementos A[1], A[2], . . . , A[30], Escreva os predicados que dizem:

a) Cada entrada no array é não negativa: ∀i ∈ V (A[i] ≥ 0)

b) O valor A[30] é o maior valor: ∀i ∈ V (A[i] ≤ A[30])

c) Cada entrada de A é não nula: ∀i ∈ V (A[i] 6= 0) ◭

Exemplo:Sejam as sentenças abertas, com domínio no conjunto R:

• ∀x < 0(x2 > 0), interpretado como ‘o quadrado de um número negativo é positivo’, quepoderia ser declarado da seguinte maneira: ∀x(x < 0 → x2 > 0)

• ∀y 6= 0(y3 6= 0), interpretado como ‘o cubo de um número real não nulo é não nulo’, quepoderia ser declarado como ∀y(y 6= 0 → y3 6= 0)

• ∃z > 0(z2 = 2), interpretado como ‘existe uma raiz quadrada positiva de 2’, cuja declaraçãoequivale a ∃z(z > 0 ∧ z2 = 2)

◭

Note que:

• a restrição de uma quantificação universal é o mesmo que uma quantificação universal de umasentença condicional.

• a restrição de uma quantificação existencial é o mesmo que a quantificação existencial de umaconjunção.

31

6.3.6 Precedência de Quantificadores

Os quantificadores ∀ e ∃ tem precedência sobre todos os conectivos lógicos do cálculo proposicional.

Exemplo:A notação ∀xP (x) ∧Q(x) é a conjunção de ∀xP (x) com Q(x), ou seja, (∀xP (x)) ∧Q(x) ◭

6.3.7 Equivalências Lógicas Envolvendo Quantificadores

Definição 17 (Equivalência em Quantificadores). Sentenças envolvendo quantificadores e predica-dos são logicamente equivalentes se e somente se elas tem a mesma tabela verdade, não importaquais predicados são substituídos nestas sentenças e que domínio é usado para variáveis nestas fun-ções proposicionais.

Usamos a notação S ≡ T para dizer que duas declarações S e T que envolvem predicados e quanti-ficadores são logicamente equivalentes.

Exemplo:Mostre que a sentença ∀x(P (x)∧Q(x)) e a sentença ∀xP (x)∧∀xQ(x) são logicamente equivalentespara um mesmo domínio A.

Para mostrar que as sentenças são logicamente equivalentes, devemos mostrar que elas possuem osmesmos valores verdade, independente do domínio e dos predicados P e Q.

As sentenças são equivalentes se mostrarmos que (i) se ∀x(P (x)∧Q(x)) é verdadeira, então ∀xP (x)∧∀xQ(x) também é verdadeira; em seguida mostramos que (ii) se ∀xP (x) ∧ ∀xQ(x) é verdadeira,então ∀x(P (x) ∧Q(x)) também será verdadeira.

(i): suponha que ∀x(P (x) ∧ Q(x)) é verdadeira. Então, para um elemento a ∈ A, a sentençaP (a)∧Q(a) é verdadeira; logo P (a) é verdadeira e Q(a) é verdadeira. Se P (a) e Q(a) são verdadei-ras para todo a ∈ A, então ∀xP (x) é verdadeira e ∀xQ(x) é verdadeira. Se ambas são verdadeiras,então ∀xP (x) ∧ ∀xQ(x) é também verdadeira.

(ii): suponha que ∀xP (x) ∧ ∀xQ(x) é verdadeira. Se a sentença é verdadeira, então as sentenças∀xP (x) e ∀xQ(x) são ambas verdadeiras. Se a sentença ∀xP (x) é verdadeira, então P (a) é verda-deira para a ∈ A. O mesmo ocorre com Q(a), visto que ∀xQ(x) para qualquer valor do domínioA. Se P (a) e Q(a) são verdadeiros, então a sentença P (a) ∧ Q(a) também será verdadeira paraqualquer elemento do domínio A. Concluímos então que ∀x(P (x) ∧Q(x)) é verdadeira.

Como (i) e (ii) ocorrem, concluímos que ∀x(P (x) ∧Q(x)) ≡ ∀xP (x) ∧ ∀xQ(x). ◭

32

Obtivemos um resultado interessante deste exemplo, que mostra que podemos distribuir a quantifi-cação universal sobre a conjunção, visto que tanto uma forma quando a outra resultam nos mesmosvalores verdade.

A Tabela 27 apresenta algumas equivalências e implicações lógicas importantes referentes à quanti-ficadores:

Tabela 27: Equivalências e Implicações Lógicas sobre Sentenças QuantificadasExpressão Tipo Equivalência/Implicação

∃x(P (x) ∧Q(x)) → ∃xP (x) ∧ ∃xQ(x)∃x(P (x) ∨Q(x)) ↔ ∃xP (x) ∨ ∃xQ(x)∀x(P (x) ∧Q(x)) ↔ ∀xP (x) ∧ ∀xQ(x)∀xP (x) ∨ ∀xQ(x) → ∀x(P (x) ∨Q(x))

6.3.8 Negação de Quantificadores

É comum considerar a situação de negar uma expressão quantificada. Por exemplo, seja a declara-ção ‘Todo estudante na sua classe teve aulas de cálculo’, representada pela quantificação universal∀xP (x) onde P (x) consiste na declaração ‘x teve aulas de cálculo’.

A negação desta proposição é ‘Não é o caso que todo estudante na sua classe teve aulas decálculo’, que equivale a dizer que ‘Existe um estudante na sua classe que não teve aula de cálculo’.Em termos formais, a negação da quantificação universal equivale à quantificação existencial danegação da função proposicional original: ¬∀xP (x) ≡ ∃x¬P (x).Pode ser que se torne necessário negar uma quantificação existencial. Seja a sentença ‘Existe umestudante desta classe que não teve aulas de cálculo’, descrito formalmente como ∃xP (x), onde P (x)declara que ‘x teve aulas de cálculo’.

A negação da proposição existencial é ‘Não é o caso de que existe um estudante desta classeque teve aulas de cálculo’, que equivale a dizer que ‘Todo estudante desta classe não teve aulas decálculo’. Formalmente, a negação da quantificação existencial equivale à quantificação universal danegação da função proposicional original: ¬∃xP (x) ≡ ∀x¬P (x).

As negações de quantificadores são chamadas de leis de De Morgan para quantificadores, eestão resuminadas na Tabela 28.

33

Tabela 28: Leis de De Morgan para Quantificadores

Negação Sentença EquivalenteQuando a negação é verda-deira

Quando a negação é falsa

¬∃xP (x) ∀x¬P (x) Para todo x, P (x) é falsaExiste um x para o qual P (x)é verdadeira

¬∀xP (x) ∃x¬P (x)Existe um x para o qual P (x)é falsa

Para todo x, P (x) é verda-deira.

Exemplo:Qual é a negação de ‘Existe um político honesto’?

Seja H(x) uma função proposicional que diz que ‘x é um político honesto’. A declaração ’Existeum político honesto’ é expressa por ∃xH(x), no domínio de todos os políticos.

A negação ¬∃xH(x) equivale à expressão ∀x¬xH(x), que pode ser expressa por ‘Todos os políticosnão são honestos’, ou ‘Todos os políticos são desonestos’. ◭

Exemplo:Qual é a negação de ‘Todos os brasileiros comem churrasco’?

Seja C(x) uma função proposicional que diz que ‘x come churrasco’. A senteça original é represen-tada por ∀xC(x), cuja negação ¬∀xC(x) equivale à ∃x¬C(x).

Em linguagem natural, essa expressão pode ser dita como ‘Existe um brasileiro que não come chur-rasco’, ou ainda ‘Alguns brasileiros não comem churrasco’. ◭

Exemplo:Quais as negações das proposições ∀x(x2 > x) e ∃x(x2 = 2)?

A negação de ∀x(x2 > x) equivale à ∃x¬(x2 > x), que pode ser reescrita como ∃x(x2 ≤ x). Anegação de ∃x(x2 = 2) equivale à ∀x¬(x2 = 2), que pode ser reescrita como ∀x(x2 6= 2).

Em ambos os casos, os valores-verdade destas proposições dependem do conjunto numérico quecorresponde ao domínio. Por exemplo se o domínio da sentença ∀x(x2 6= 2) for o conjunto Z, entãoa sentença será verdadeira porque não existe nenhum inteiro que elevado ao quadrado resulta em 2;já se o domínio for o conjunto R, então a sentença será falsa porque

(√2)2

= 2. ◭

Exemplo:Seja P (x) : ‘2x+1 = 5’ e Q(x) : ‘x2 = 9’. Faça a negação da declaração ∃x(P (x)∧Q(x)) e dê uma

34

interpretação da sentença resultante em linguagem natural.

A negação da sentença ∃x(P (x) ∧ Q(x)) é dada por ∀x¬(P (x) ∧ Q(x)). Pela lei de De Morgan,∀x¬(P (x) ∧Q(x)) equivale à ∀x(¬P (x) ∨ ¬Q(x)).

Em linguagem natural, ∀x(¬P (x)∨¬Q(x)) significa ‘Para cada inteiro x, 2x+1 6= 5 ou x2 6= 9’. ◭

6.4 Quantificadores Aninhados

Até o presente momento, os quantificadores foram usados para mostrar como podem ser usadosem sentenças matemáticas, assim como podem ser usados para traduzir a linguagem natural paraexpressões lógicas.

A partir de agora, introduziremos o conceito de quantificadores aninhados (agrupados).

6.4.1 Declarações Envolvendo Quantificadores Aninhados

Dois quantificadores estão aninhados se um está no escopo do outro, onde o quantificador maisinterno é tratado como uma função proposicional. Para exemplificar, ∀x∃y(x+ y = 0) é o mesmoque ∀xQ(x), em que Q(x) é ∃yP (x, y) e P (x, y) é x+ y = 0.

Exemplo:Traduza a sentença ∀x∀y((x > 0) ∧ (y < 0) → (xy < 0)) para linguagem natural.

A sentença afirma que ‘para todo real x e para todo real y, se x > 0 e y < 0, então xy < 0’; ou‘para números reais x e y, se x é positivo e y é negativo, então o produto xy é negativo’; ou ainda‘o produto de um número positivo po um número negativo é sempre negativo’. ◭

Exemplo:Seja Q(x, y) a sentença x + y = 0. Quais os valores verdade das quantificações ∃y∀xQ(x, y) e∀x∃yQ(x, y), com x ∈ R e y ∈ R.

A quantificação ∃y∀x(x+y = 0) representa a afirmação ‘existe um número real y para todo númeroreal x para o qual x + y = 0. Como não existe nenhum número real y que, somado à todo real xresulta em zero, então a sentença ∃y∀xQ(x, y) é falsa.

Já a quantificação ∀x∃y(x+ y = 0) expressa a afirmação ‘para todo real x, existe um número real ypara o qual x+ y = 0’. Essa sentença é verdadeira, pois para cada x, existe um y = −x cuja somax+ y resulta em 0. ◭

35

A Tabela 29 resume o significado das quantificações com duas variáveis, indicando as situaçõesem que o valor verdade da quantificação é verdadeiro, e as situações onde a quantificação assumevalor-verdade falso.

Tabela 29: Quantificadores com Duas VariáveisSentença Quando é verdadeira Quando é falsa

∀x∀yP (x, y)P (x, y) é verdadeira para todopar x,y

Existe um par x, y para o qualP (x, y) é falsa

∀y∀xP (x, y)P (x, y) é verdadeira para todopar x,y

Existe um par x, y para o qualP (x, y) é falsa

∀x∃yP (x, y)Para todo x existe um y para oqual P (x, y) é verdadeira

Existe um x tal que P (x, y) éfalsa para todo y

∃x∀yP (x, y)Existe um x tal que P (x, y) é ver-dadeira para todo y

Para todo x, existe um y para oqual P (x, y) é falsa

∃x∃yP (x, y)Existe um par x, y para o qualP (x, y) é verdadeira

P (x, y) é falsa para todo par x, y

∃y∃xP (x, y)Existe um par x, y para o qualP (x, y) é verdadeira

P (x, y) é falsa para todo par x, y

Neste último exemplo fica claro que a ordem em que os quantificadores aparecem determina averdade sobre a declaração. Segue mais um exemplo, desta vez envolvendo três variáveis e trêsquantificadores, onde a ordem afeta a verdade da declaração:

Exemplo:Seja S(x, y, z) a declaração ‘x+y = z’. Quais são os valores verdade das declarações ∀x∀y∃zS(x, y, z)e ∃z∀x∀yS(x, y, z), com x, y, z ∈ R?

A quantificação ∀x∀y∃zS(x, y, z) pode ser expressa em linguagem natural como ‘para todo real x ey, existe um real z para o qual x+ y = z’, que é verdadeira visto que a soma de dois números reaisresulta em um número real.

Já a quantificação ∃z∀x∀yS(x, y, z) é interpretada em linguagem natural como ‘existe um númeroreal z tal que para todo real x e y, x + y = z’. Como inexiste tal número, então a quantificaçãocorrespondente é falsa. ◭

Sentenças matemáticas também podem traduzidas em lógica por meio de quantificadores. Os pró-ximos dois exemplos ilustram essa tradução, passo a passo, da declaração inicial até o refinamentofinal.

Exemplo:Traduza a declaração ‘A soma de dois inteiros positivos é sempre positivo’ em uma expressão lógica.

36

Primeiramente reescrevemos a sentença de forma que o domínio e quantificadores. Ela seria algodo tipo: ‘Para cada dois números inteiros, se ambos são positivos, então o resultado da soma destesdois inteiros é positivo.’.

O próximo passo do refinamento consiste em incluir variáveis. Teríamos ‘Para todos os inteirospositivos x e y, x+ y é positivo’.

Por fim, a tradução da última sentença em uma expressão lógica é quase direta, e resulta em:

∀x∀y((x > 0) ∧ (y > 0) → (x+ y > 0)), com x, y ∈ Z

Se mudarmos o domínio da quantificação, a expressão acima pode ser representada de outra maneiraainda:

∀x∀y(x+ y > 0), com x, y ∈ Z+

A declaração ‘A soma de dois inteiros positivos é sempre positivo’ foi traduzida em termos formaiscomo ∀x∀y(x+ y > 0), com x, y ∈ Z

+. ◭

Definição 18 (Inverso Multiplicativo). O inverso multiplicativo de um número real x é umnúmero real y tal que xy = 1.

Exemplo:Traduza a declaração ‘Cada número real, exceto 0, tem um inverso multiplicativo’ para uma expres-são lógica.

Reescrevemos a afirmação da seguinte maneira: ‘Para cada número real x, exceto zero, x tem uminverso multiplicativo.

Em seguida, acrescentamos um pouco mais de formalismo na declaração usando a Definição 18 paramelhorar ainda mais a declaração sobre o que é um inverso multiplicativo: ‘Para cada número realx, se x 6= 0, então existe um número real y tal que xy = 1’. Essa última declaração é suficiente parauma tradução direta da sentença em

∀x((x 6= 0) → ∃y(xy = 1))

A declaração ‘Cada número real, exceto 0, tem um inverso multiplicativo’ foi traduzida em termosformais em ∀x((x 6= 0) → ∃y(xy = 1)), com x, y ∈ R. ◭

O próximo caso exemplifica como traduzir uma quantificação aninhada em linguagem natural.

37

Exemplo:Sejam as funções proposicionais C(x): ‘x tem um computador’ e A(x, y): ‘x e y são amigos’. Tra-duza a expressão lógica ∀x(C(x)∨ (∃y(C(y)∧A(x, y))) onde o domínio das variáveis x e y consisteem todos os alunos da escola.

A expressão lógica dada acima expressa a idéia de que, ‘para cada aluno x da escola, x tem umcomputador ou existe um aluno y tal que y tem um computador e y é amigo de x’.

De uma maneira menos formal, essa declaração significa que cada aluno da escola ou tem um com-putador ou tem um amigo que tem um computador. ◭

6.4.2 Negação de Quantificadores Aninhados

As negações de declarações quantificadas com quantificadores aninhados podem ser feitas aplicando-se sucessivamente as regras para negar declarações envolvendo um único quantificador.

Exemplo:Expresse a negação da declaração quantificada ∀x∃y(xy = 1) tal que a negação precede a declaração.

Usaremos os resultados da Tabela 28 para negação de quantificadores para aplicar a negação dasentença original. Pela tabela, a negação de ¬∀x∃y(xy = 1) resulta em ∃x¬∃y(xy = 1).

A sentença resultante ainda pode ser trabalhada. Podemos aplicar novamente a negação sobre aquantificação ∃y. A negação de ∃x¬∃y(xy = 1) resulta, portanto, em ∃x∀y¬(xy = 1)

Para finalizar, podemos substituir a negação ¬(xy = 1) por (xy 6= 1). Após as sucessivas aplicaçõesde negação sobre cada quantificador e sobre a função proposicional, concluímos que ∀x∃y(xy = 1)resulta em ∃x∀y(xy 6= 1). ◭

7 Regras de Inferência

Todos os fundamentos de lógica apresentados até o presente momento possuem um objetivo muitoespecial em matemática discreta: a construção de provas.

Em matemática, provas são argumentos válidos que estabelecem a verdade de sentenças matemáti-cas. Entendemos por argumentos uma sequência de declarações que terminam com uma conclusão.Por válido nós entendemos que a conclusão, ou sentença final do argumento, deve seguir da verdadedas sentenças precedentes do argumento (das premissas).

Diante disto, temos que um argumento é valido se e somente se é impossível que todas as premissassejam verdadeiras e a conclusão seja falsa.

38

Para deduzir novas sentenças a partir de sentenças pré-existentes, utilizamos regras de inferência.Regras de inferência são ‘modelos’ para construir argumentos válidos. Elas são, de fato, as ferra-mentas básicas para estabelecer a verdade sobre declarações.

Regras de inferência se aplicam tanto a sentenças em lógica proposicional quanto a sentenças quan-tificadas, em ambos os casos com objetivo de produzir argumentos válidos. As regras de inferênciausando os quantificadores existencial e universal possuem papel fundamental na elaboração de pro-vas em matemática e ciência da computação.

7.1 Argumentos Válidos em Lógica Proposicional

Considere a seguinte sequência de proposições

• ‘Se você tem uma senha, então voce pode efetuar login na rede’

• ‘Você tem uma senha’

Portanto,

• ‘Você pode efetuar login na rede’.

Suponha que a intenção é verificar se a conclusão ‘você pode efetuar login na rede’ é verdadeira combase na veracidade das premissas ‘se você tem uma senha, então você pode efetuar login na rede’ e‘você tem uma senha’. O mecanismo que nos permite responder a esta pergunta chama-se regra deinferência.

Definição 19 (Argumento). Um argumento é uma sequência de afirmações para demonstrar a va-lidade de uma declaração.

Um argumento em lógica proposicional é uma sequência de proposições. Todas, exceto a propo-sição final, são denominadas premissas, enquanto que a proposição final é denominada conclusão.

Um argumento é válido se a verdade de todas as suas premissas implicam em uma conclusãoverdadeira.

Exemplo:‘Está chovendo ou está nevando’‘Não está nevando’Portanto,‘Está chovendo’ ◭

39

Pela Definição 19 temos que um argumento com premissas p1, p2, . . . , pn e conclusão q é válidoquando (p1 ∧ p2 ∧ · · · ∧ pn) → q é uma tautologia.

Para analizar um argumento, substituímos as proposições (i.e., sentenças afirmativas) por variáveisproposicionais (i.e., p, q, r, . . . ). Isso transforma um argumento em uma forma de argumento. Avalidade de um argumento advém da validade da forma do argumento.

Definição 20 (Forma de Argumento). Em lógica proposicional, uma forma de argumento é umasequência de proposições compostas envolvendo variáveis proposicionais.

Uma forma de argumento pode ser válida ou inválida. Uma forma de argumento é válida quando,para qualquer substituição de variáveis proposicionais, se as premissas são verdadeiras então aconclusão é também verdadeira.

Exemplo:Sejam os argumentos:

‘Está chovendo ou está nevando’‘Não está nevando’Portanto,‘Está chovendo’

‘O aluno é aprovado em cálculo ou o aluno é reprovado em cálculo’‘O aluno não foi reprovado em cálculo’Portanto,‘O aluno foi aprovado em cálculo’

Embora estes argumentos possuam ‘conteúdos’ diferentes, eles possuem a mesma ‘forma’:p ∨ q¬q∴ p

, onde ∴ é lido como ‘portanto’.

Nesta notação, as premissas são escritas em colunas, seguidas por uma barra horizontal, seguidapor uma linha que começa com o símbolo de portanto (∴), seguido pela conclusão. ◭

Exemplo:Sejam os argumentos:

‘Se você tem uma senha, então voce pode efetuar login na rede’‘Você tem uma senha’Portanto,‘Você pode efetuar login na rede’.

40

‘Se você tem carteira de motorista, então você pode dirigir um carro’‘Você tem carteira de motorista’Portanto,‘Você pode dirigir um carro’.

Embora estes argumentos possuam ‘conteúdos’ diferentes, eles possuem a mesma ‘forma’:p → q

p

∴ q◭

Para verificar se uma forma de argumento é válida, podemos usar o seguinte procedimento, descritono Algoritmo 1:

Algoritmo 1 Verifica a validade de uma forma de argumento1: Identifique as premissas e a conclusão da forma de argumento2: Construa a tabela verdade, destacando as premissas e a conclusão3: Encontre as linhas da tabela verdade onde todas as premissas são verdadeiras (linhas críticas)4: if em todas as linhas críticas a conclusão é verdadeira then5: A forma de argumento é válida6: else7: A forma de argumento é inválida8: end if

Exemplo:Sejam as proposições p: ‘você tem uma senha’, q: ‘você pode efetuar login na rede’ e p → q ‘se vocêtem uma senha, então voce pode efetuar login na rede’. Determine se a seguinte forma de argumento

p → qp

∴ q

é válida.

1. Premissas: p e p → q, conclusão: q

2. Tabela verdade desta forma de argumento

p q p → q (p → q) ∧ p ((p → q) ∧ p) → q q

0 0 1 0 1 00 1 1 0 1 11 0 0 0 1 01 1 1 1 1 1

3. Segundo a Definição 20 e o Algoritmo 1, o argumento é válido se ambas as premissas p e p → qe a conclusão q são verdadeiras. Identificamos as linhas onde as premissas e conclusão sãoverdadeiras.

41

p q p → q (p → q) ∧ p ((p → q) ∧ p) → q q

0 0 1 0 1 00 1 1 0 1 11 0 0 0 1 01 1 1 1 1 1

4. Na única linha crítica desta tabela verdade, todas as premissas são verdadeiras, e a conclusãoé também verdadeira. Isto posto, temos que a forma de argumento apresentada é válida.

Observe que, pela Definição 19, as premissas p1, p2, . . . , pn e a conclusão q são verdadeirasquando (p1 ∧ p2 ∧ · · · ∧ pn) → q é uma tautologia.

Pela tabela verdade deste exemplo, confirmamos este fato já que ((p → q) ∧ q) → q é umatautologia.

p q p → q (p → q) ∧ p ((p → q) ∧ p) → q q

0 0 1 0 1 00 1 1 0 1 11 0 0 0 1 01 1 1 1 1 1

◭

Exemplo:Seja o argumento:

‘Se o dia está ensolarado, então vou jogar bola ou não vou fazer a lição’‘Se eu for jogar bola, então o dia está ensolarado e vou fazer a lição’Portanto,‘Se o dia está ensolarado, então vou fazer a lição’.

Determine se o argumento é válido.

Traduzindo o argumento na sua forma de argumento:

p → q ∨ ¬rq → p ∧ r

∴ p → r

Verificando a validade do argumento, pelo Algoritmo 1:

1. Identificando as premissas: (p → q ∨ ¬r) e (q → p ∧ r).

42

2. Tabela verdade da forma de argumento

p q r ¬r q ∨ ¬r p ∧ r p → q ∨ ¬r q → p ∧ r [(p → q ∨ ¬r) ∧ (q → p ∧ r)] → (p → r) p → r

0 0 0 1 1 0 1 1 1 1

0 0 1 0 0 0 1 1 1 1

0 1 0 1 1 0 1 0 1 1

0 1 1 0 1 0 1 0 1 1

1 0 0 1 1 0 1 1 0 0

1 0 1 0 0 1 0 1 1 1

1 1 0 1 1 0 1 0 1 0

1 1 1 0 1 1 1 1 1 1

3. Identificar as linhas críticas. Destacamos em azul as linhas críticas em que as premissas econclusão são verdadeiras, e em vermelho as linhas em que as premissas são verdadeiras, masa conclusão é falsa.

4. Pelos resultados da tabela, concluímos que o argumento é inválido, pois existe pelo menosuma atribuição de valores nas variáveis proposicionais p, q e r que leva à premissas verdadeirascom conclusão falsa. Além disso, [(p → q∨¬r)∧ (q → p∧r)] → (p → r) não é uma tautologia.

◭

7.2 Regras e Inferência para Proposições Lógicas

Podemos sempre usar tabelas verdade para mostrar que uma forma de argumento é válida: fazemosisso mostrando que se as premissas são verdadeiras, então a conclusão também deve ser verdadeira.

Porém, essa abordagem pode ser entediante, já que se uma forma de argumento envolvendo muitasvariáveis lógicas terá uma tabela verdade com uma quantidade exponencial de linhas. Isso ocorre emfunção da possibilidade de cada uma das variáveis lógicas assumir o valor 0 ou 1. Para exemplificar,seja a Figura 1 que ilustra a atribuição de valores-verdade para uma proposição composta de quatrovariáveis lógicas, nomeadas p, q, r e s.

Figura 1: Árvore de possibilidades para as variáveis p, q, r e s

p

r

q

s

1 1

1 0

001 0 1 0 1 101010101

0 0 1 0 1 0

1 0 1 0

Com apenas uma variável lógica, existem 2 combinações de valores-verdade possíveis; para umaproposição com duas variáveis lógicas, existem 4 combinações de valores-verdade possíveis; em uma

43

proposição com quatro variáveis lógicas, existem 16 diferentes combinações de valores-verdade; parauma proposição com dez variáveis lógicas, haverão 1024 combinações diferentes de valores verdade.De maneira mais geral, para uma proposição composta com n variáveis lógicas, haverão 2n linhasdiferentes devido às possibilidades de atribuição de valores-verdade a cada uma das n variáveis.

Assim, não é nada prático provar que um argumento é válido usando tabelas verdade para propo-sições compostas por muitas variáveis.

Existe uma alternativa para mostrar a validade de uma forma de argumento, sem recorrer ao usode tabelas verdade, é por meio de formas de argumento mais simples denominadas de regras deinferência. Tais regras são usadas como elementos básicos para construir formas de argumentoválidas mais complexas.

7.2.1 Modus Ponens

A tautologia [(p → q) ∧ p] → q é a base da regra de inferência denominada modus ponens (dolatim, método de afirmar). Essa tautologia leva à seguinte forma de argumento válida:

p → qp

∴ q

onde ∴ é lido como ‘portanto’. Nesta notação, as premissas são escritas em colunas, seguidas poruma barra horizontal, seguida por uma linha que começa com o símbolo portanto (∴), seguido daconclusão.

A tabela verdade dessa regra de inferência será apresentada a Tabela 30.

Tabela 30: Regra de inferência modus ponens e sua tabela-verdade

Forma do argumento

p → qp

∴ q

p q p → q p (p → q) ∧ p [(p → q) ∧ p] → q q

0 0 1 0 0 1 00 1 1 0 0 1 11 0 0 1 0 1 01 1 1 1 1 1 1

Em particular, modus ponens diz que ‘se uma sentença condicional e sua hipótese são ambas ver-dadeiras, então a conclusão também será verdadeira’.

Exemplo:Sejam a declaração condicional ‘se nevar hoje, então iremos esquiar’, e sua hipótese ‘está nevandohoje’ verdadeiras. Assim, pelo modus ponens, temos que a conclusão da sentença condicional ‘nós

44

iremos esquiar’ é verdadeira. ◭

Exemplo:

Seja o argumento: ‘se√2 > 3

2 , então(√

2)2

>(

32

)2. Sabemos que

√2 > 3/2. Logo,

(√2)2

> (3/2)2’.

Determine se o argumento é válido e se a conclusão é verdadeira.

Sejam as proposições p:√2 > 3

2 e q:(√

2)2

>(

32

)2

Na forma de argumento deste exemplo, as premissas são representadas pelas proposições p e p → qenquanto que conclusão é q. Essa forma é a forma conhecida como modus ponens, que é sabido serválida. O argumento é, portanto, válido.

No entanto, uma das premissas do argumento é falsa. Isto posto, temos que a conclusão do argu-mento será falsa, embora a ‘forma’ do argumento seja válida. ◭

7.2.2 Modus Tollens

A regra de inferência conhecida como modus tollens (do latim, modo de negar) tem a seguinteforma de argumento válida

p → q¬q∴ ¬p

A tabela-verdade para a regra de inferência modus tollens é apresentada na Tabela 31.

Tabela 31: Regra de inferência modus tollens e sua tabela-verdade

Forma do argumento

p → q¬q∴ ¬p

p q p → q ¬q (p → q) ∧ ¬q [(p → q) ∧ ¬q] → ¬p ¬p0 0 1 1 1 1 10 1 1 0 0 1 11 0 0 1 0 1 01 1 1 0 0 1 0

Exemplo:‘Se Zeus é humano, então Zeus é mortal’‘Zeus não é mortal’Portanto‘Zeus não é humano’ ◭

45

7.2.3 Disjunção Aditiva

A regra de inferência denominada disjunção aditiva consiste em argumentos organizados da se-guinte forma de argumento válida:

p

∴ p ∨ q

A tabela-verdade dessa regra de inferência é apresentada na Tabela 32.

Tabela 32: Regra de inferência disjunção aditiva e sua tabela-verdade

Forma do argumento

p

∴ p ∨ q

p q p p → (p ∨ q) p ∨ q

0 0 0 1 00 1 0 1 11 0 1 1 11 1 1 1 1

Neste tipo de construção, se p é verdadeiro, então p ∨ q é verdadeiro para qualquer proposição q.Esta regra de inferência é útil quando se deseja fazer generalizações.

Exemplo:‘Está abaixo de zero agora’Portanto‘Está abaixo de zero agora ou está chovendo agora’ ◭

7.2.4 Simplificação Conjuntiva

A regra de inferência denominada de simplificação conjuntiva é aquela que possui a forma

p ∧ q

∴ p

A Tabela 33 mostra os valores-verdade para a simplificação conjuntiva.

Tabela 33: Regra de inferência simplificação conjuntiva e sua tabela-verdade

Forma do argumento

p ∧ q

∴ p

p q p ∧ q (p ∧ q) → p p

0 0 0 1 00 1 0 1 01 0 0 1 11 1 1 1 1

46

Esta regra de inferência é usada para fazer particularizações: ‘se p e q são verdadeiros, então p, emparticular, é verdadeiro’.

Exemplo:‘Está abaixo de zero e chovendo agora’Portanto‘Está abaixo de zero’. ◭

7.2.5 Silogismo Disjuntivo

A regra de inferência denominada de silogismo disjuntivo é aquela que têm a forma válida

p ∨ q¬q∴ p

ou

p ∨ q¬p∴ q

A Tabela 34 e a Tabela 35 mostram os valores-verdade para a regra de inferência silogismo disjuntivo.

Tabela 34: Regra de inferência silogismo disjuntivo e sua tabela-verdade

Forma do argumento

p ∨ q¬q∴ p

p q ¬q p ∨ q (p ∨ q) ∧ ¬q [(p ∨ q) ∧ ¬q] → p p

0 0 1 0 0 1 00 1 0 1 0 1 01 0 1 1 1 1 11 1 0 1 0 1 1

Tabela 35: Regra de inferência silogismo disjuntivo e sua tabela-verdade

Forma do argumento

p ∨ q¬q∴ p

p q ¬p p ∨ q (p ∨ q) ∧ ¬p [(p ∨ q) ∧ ¬p] → q q

0 0 1 0 0 1 00 1 1 1 1 1 11 0 0 1 0 1 01 1 0 1 0 1 1

Exemplo:‘Está chovendo ou está nevando’‘Não está nevando’Portanto‘Está chovendo’ ◭

47

Estas forma de argumento são empregadas quando se têm uma situação em que existem somenteduas possibilidades e uma delas pode ser excluída, o que faz com que a outra prevaleça.

7.2.6 Silogismo Hipotético

Esta regra de inferência, denominada de silogismo hipotético, possui a formap → qq → r

∴ p → r

Os valores-verdade desta regra de inferência é apresentado na Tabela 36.

Tabela 36: Regra de inferência silogismo hipotético e sua tabela-verdade

Forma do argumento

p → qq → r

∴ p → r

p q r p → q q → r [(p → q) ∧ (q → r)] → (p → r) p → r

0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 0 1 01 0 1 0 1 1 11 1 0 1 0 1 01 1 1 1 1 1 1

É usado para argumentos que encadeiam sentenças do tipo se-então, onde o primeiro implica oúltimo.

7.2.7 Conjunção

A regra de inferência denominada conjunção consiste na apresentação de argumentos na seguinteforma de argumento

pq

∴ p ∧ q

Para essa regra de inferência apresentaremos a Tabela 37, que mostra os valores verdade dessa regra.

Tabela 37: Regra de inferência conjunção e sua tabela-verdade

Forma do argumento

pq

∴ p ∧ q

p q [(p) ∧ (q)] → p ∧ q p ∧ q

0 0 1 00 1 1 01 0 1 01 1 1 1

48

7.2.8 Resolução

A regra de inferência resolução consiste na forma de argumento apresentada da seguinte maneira

p ∨ q¬p ∨ r

∴ q ∨ r

A tabela-verdade para essa regra de inferência tem seus resultados apresentados na Tabela 38.

Tabela 38: Regra de inferência resolução e sua tabela-verdade

Forma do argumento

p ∨ q¬p ∨ r

∴ q ∨ r

p q r ¬p p ∨ q ¬p ∨ r [(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r) q ∨ r

0 0 0 1 0 1 1 0

0 0 1 1 0 1 1 1

0 1 0 1 1 1 1 1

0 1 1 1 1 1 1 1

1 0 0 0 1 0 1 0

1 0 1 0 1 1 1 1

1 1 0 0 1 0 1 1

1 1 1 0 1 1 1 1

7.2.9 Resumo das Regras de Inferência

A Tabela 39 resume as regras de inferência mais importantes para lógica proposicional.

Tabela 39: Regras de Inferência

Regra de Inferência Tautologia Nomenclatura

p → qp

∴ q[(p) ∧ (p → q)] → q Modus Ponens

p → q¬q∴ ¬p [(¬q) ∧ (p → q)] → ¬p Modus Tollens

p → qq → r

∴ p → r[(p → q) ∧ (q → r)] → (p → r) Silogismo Hipotético

p ∨ q¬q∴ p

[(p ∨ q) ∧ (¬q)] → p Silogismo Disjuntivo

49

p

∴ p ∨ qp → (p ∨ q) Disjunção Aditiva

p ∧ q

∴ q(p ∧ q) → p Simplificação Conjuntiva

pq

∴ p ∧ q[(p) ∧ (q)] → (p ∧ q) Conjunção

p ∨ q¬p ∨ r

∴ q ∨ r[(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r) Resolução

50

7.3 Construindo Argumentos por meio de Regras de Inferência

Em muitas situações nós nos deparamos com situações onde deve-se avaliar a validade de um ar-gumento que possui muitas premissas. Para estes casos, o uso de regras de inferência devem seraplicadas de forma a provar este resultado.

Mais adiante veremos outra aplicação importante em ciência da computação e, em especial, emmatemática discreta, que consiste na construção de provas.

Exemplo:Mostre que as hipóteses ‘se você me enviar um email, então eu terminarei de escrever o programa’,‘se você não me enviar um email, então eu irei dormir mais cedo’, ‘se eu dormir mais cedo hoje,levam à conclusão ‘se eu não terminar de escrever o programa, eu acordarei revigorado”.

Primeiro, transformaremos os argumentos acima em formas de argumento, atribuíndo uma variávelproposicional à cada um dos argumentos. Isso resulta em:

• p: Você me enviará um email.

• q: Eu terminarei de escrever o programa.

• r: Eu irei dormir mais cedo.

• s: Eu acordarei revigorado.

Tradução dos fatos para premissas:(a): p → q(b): ¬p → r(c): r → s

Tradução da conclusão:(d): ¬q → s

Deduções de (a), (b), (c) para chegar a conclusão (d):

Identificação Expressão Dedução(a) p → q Premissa(b) ¬p → r Premissa(c) r → s Premissa(a) p → q(d) ∴ ¬q → ¬p Contrapositiva de (a)(d) ¬q → ¬p(b) ¬p → r(e) ∴ ¬q → r Silogismo hipotético de (b) e (e)(e) ¬q → r(c) r → s(f) ∴ ¬q → s Silogismo hipotético de (e) e (c) levam à (f)

51

De acordo com as deduções lógicas aplicadas sobre as premissas, conclui-se que se eu não termi-nar de escrever o programa, então acordarei revigorado. ◭

Exemplo:[Loureiro, A. A. F.] Você está saindo para a escola de manhã e percebe que não está usando osóculos. Ao tentar descobrir onde estão os óculos, você começa a pensar sobre os seguintes fatos, quesão verdadeiros:

• Se meus óculos estão na mesa da cozinha, então eu os ví pela manhã

• Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na cozinha

• Se eu estava lendo o jornal na sala de estar, então meus óculos estão na mesa do café

• Eu não vi meus óculos no café da manhã

• Se eu estava lendo um livro na cama, então meus óculos estão no criado mudo

• Se eu estava lendo o jornal na cozinha, então meus óculos estão na mesa da cozinha

Argumentos:

• p: Os meus óculos estão na mesa da cozinha

• q: Eu ví os meus óculos pela manhã

• r: Eu estava lendo jornal na sala de estar

• s: Eu estava lendo jornal na cozinha

• t: Meus óculos estão na mesa do café

• u: Eu estava lendo um livro na cama

• v: Meus óculos estão no criado mudo

Tradução dos fatos em premissas(a): p → q(b): r ∨ s(c): r → t(d): ¬q(e): u → v(f): s → p

Deduções de (a), (b), (c), (d), (e) e (f) para levar à uma conclusão desconhecida

Idetificação Expressão Dedução

52

(a) p → q Premissa(b) r ∨ s Premissa(c) r → t Premissa(d) ¬q Premissa(e) u → v Premissa(f) s → p Premissa(a) p → q(d) ¬q(g) ∴ ¬p Modus Tollens

(f) s → p(g) ¬p(h) ∴ ¬s Modus Tollens

(b) r ∨ s(h) ¬s(i) ∴ r Silogismo Disjuntivo(c) r → t(i) r(j) ∴ t Modus Ponens

Pelo resultado das deduções aplicadas sobre as formas de argumento descritas neste exemplo,concluí-se que os óculos foram esquecidos na mesa do café. ◭

7.4 Regras de Inferência para Quantificadores

Na seção anterior, apresentamos o conceito de regras de inferência para proposições lógicas. Na pre-sente seção apresentaremos as regras de inferência mais importantes para declarações envolvendoquantificadores. São elas: instanciação universal, generalização universal, instanciação existencial egeneralização existencial.

A instanciação universal consiste na regra de inferência que declara que, dado a premissa ∀xP (x),

P (c) é verdadeiro para um membro particular do domínio (isto é,∀xP (x)

∴ P (c)). Usamos esta regra

de inferência para concluir a partir da declaração ‘Todas as cidades de MG são bacanas’ que ‘For-miga é uma cidade bacana’, visto que Formiga é um elemento do domínio de todas as cidades de MG.

Já a generalização universal consiste na regra de inferência que declara que ∀xP (x) é verdadeiro

dado a premissa que P (c) é verdadeiro para todo elemento c no domínio (isto é,P (c)

∴ ∀xP (x)para

um elemento c arbitrário do domínio).

O elemento c escolhido deve ser arbitrário, e não específico, a partir do domínio. Em outras pala-vras, quando nós afirmamos que a escolha do elemento c é arbitrária, nós estamos afirmando quenão temos controle sobre qual elemento do domínio será escolhido e, desta forma, não podemos

53

fazer nenhuma consideração sobre c que não esteja relacionada ao conjunto domínio.

A generalização universal é usada implicitamente na demonstração de teorema e provas sobre propo-sições matemáticas, sendo raramente explícita. Deve-se, no entanto, ter cuidado para não construirraciocínios incorretos quando usando generalização universal, tomando como verdade consideraçõesque não podem ser garantidas para um elemento c arbitrário do domínio.

Outra regra de inferência importante em declarações quantificadas consiste na regra denominadainstanciação existencial. Ela nos permite concluir que existe um elemento c do domínio para oqual P (c) é verdadeira desde que ∃xP (x) seja uma declaração verdadeira.

Neste caso, não podemos selecionar um elemento c arbitrariamente; o elemento c escolhido deve seraquele que torna P (c) verdadeira. Geralmente não se sabe qual dos elementos do domínio corres-ponde ao elemento c, apenas sabemos que ele existe. Uma vez que ele existe, damos à ele o nome

de c e continuamos a dedução. Essa regra de inferência é formalizada por∃xP (x)

∴ P (c)para algum

elemento c.

Por fim, existe a generalização existencial. Por meio dela nós concluímos que ∃xP (x) se houverum elemento c do domínio para o qual sabemos que P (c) é verdadeiro. Em outras palavras, se sa-bemos que existe um elemento c para o qual P (c) é verdadeiro, então ∃xP (x) também é verdadeiro.

Em notação de inferência,P (c)

∴ ∀xP (c)para algum elemento c. A Tabela 42 resume as regras de

inferência para declarações quantificadas.

Tabela 42: Inferência sobre Declarações Quantificadas

Regra de Inferência Nomenclatura

∀xP (x)

∴ P (c)Instanciação Universal

P (c)

∴ ∀xP (x)para um c arbitrário Generalização Universal

∃xP (x)

∴ P (c)para algum c Instanciação Existencial

P (c)

∴ ∃xP (c)para algum c Generalização Existencial

54

Exemplo:Mostre que as premissas ‘Todos da turma de matemática discreta estão matriculados no curso deCiência da Computação’ e ‘Marla é uma aluna da turma de matemática discreta’ implica na con-clusão ‘Marla está matriculada no curso de Ciência da Computação’.

Vamos denotar D(x) a propriedade ‘x está na turma de matemática discreta’ e C(x) como a pro-priedade ‘x está matriculado em um curso de Ciência da Computação’. Então as premissas são∀x(D(x) → C(x)) e D(Marla), e a conclusão é C(Marla). Vamos mostrar que a dedução daspremissas leva à conclusão esperada usando as regras de inferência comentadas nesta seção do do-cumento.

Idetificação Expressão Dedução(a) ∀x(D(x) → C(x)) Premissa(b) D(Marla) Premissa(a) ∀x(D(x) → C(x)) Premissa(c) ∴ D(Marla) → C(Marla) Instanciação Universal de (a)(c) D(Marla) → C(Marla)(b) D(Marla) Premissa(d) ∴ C(Marla) Modus Ponens de (c) e (b)

Segundo a dedução apresentada sobre ∀x(D(x) → C(x)) e D(Marla), chegamos à conclusão que aafirmação C(Marla) é verdadeira. ◭

Exemplo:Mostre que as premissas ‘Um estudante da turma não leu o livro’, e ‘Todo mundo da classe passouno exame’ implica em ‘Alguem que passou no exame não leu o livro’.

Sejam T (x) ‘x é um estudante da turma’, L(x) ‘x leu o livro’ e P (x) ‘x passou no exame’. Logo,as premissas são ∃x(T (x) ∧ ¬L(x)) e ∀x(T (x) → P (x)). A conclusão obtida mediante dedução apartir das premissas é dada a seguir:

Idetificação Expressão Dedução(a) ∃x(T (x) ∧ ¬L(x)) Premissa(b) ∀x(T (x) → P (x)) Premissa(a) ∃x(T (x) ∧ ¬L(x)) Premissa(c) ∴ T (a) ∧ ¬L(a) Instanciação Existencial de (a)(c) T (a) ∧ ¬L(a)(d) ∴ T (a) Simplificação Conjuntiva de (c)(b) ∀x(T (x) → P (x)) Premissa(e) ∴ T (a) → P (a) Instanciação Existencial de (b)(e) T (a) → P (a)(d) T (a)(f) ∴ P (a) Modus Ponens de (e) e (d)

55

(c) ∴ T (a) ∧ ¬L(a)(g) ∴ ¬L(a) Simplificação conjuntiva de (c)(f) P (a)(g) ¬L(a)(h) ∴ P (a) ∧ ¬L(a) Conjunção de (f) e (g)(h) P (a) ∧ ¬L(a)(i) ∴ ∃x(P (x) ∧ ¬L(x)) Generalização Existencial de (h)

Logo, da dedução acima concluímos que ‘alguém que passou no exame não leu o livro’. ◭

7.5 Regras de Inferência para Proposições e Declarações Quantificadas

Nas deduções apresentadas nos exemplos da seção de regras de inferência para declarações quanti-ficadas observamos o uso das regras de inferência de instanciação e generalização juntamente comregras de inferência que operam sobre proposições.

Em especial, a combinação de regra de generalização universal de declarações quantificadas e modusponens de proposições são usadas frequentemente em deduções. Devido a este fato, esta combinaçãopossui a denominação especial de modus ponens universal . A regra de inferência diz que se∀x(P (x) → Q(x)) é verdadeiro, e se P (a) é verdadeiro para algum elemento particular a do domínio,então Q(a) também deve ser verdadeiro:

∀x(P (x) → Q(x))P (a)

∴ Q(a), onde a é um elemento particular do domínio

A forma modus ponens universal é frequentemente usada em argumentos matemáticos.

Exemplo:Assuma que ‘Para todo inteiro positivo n, se n é maior do que 4, (n2 < 2n)’ é uma afirmaçãoverdadeira. Mostre que 1002 < 2100.

Sejam as propriedades P (x) : n > 4 e Q(x) : n2 < 2n. As premissas da afirmação acima podem serformalizadas na seguinte sentença ∀x ∈ Z(P (x) → Q(x)). Assuma que tal sentença seja verdadeira.

Idetificação Expressão Dedução(a) ∀x ∈ Z(P (x) → Q(x)) Premissa(b) P (100) Premissa(a) ∀x ∈ Z(P (x) → Q(x))(b) P (100)(c) ∴ Q(100) Modus Ponens Universal de (a) e (b)

Logo, pela regra de inferência modus ponens universal temos que Q(100) é verdadeiro. ◭

56

Da mesma forma, pode-se combinar uma generalização universal e a regra modus tollens para gerara regra de inferência modus tollens universal para combinações de declarações quantificadas eproposições. Essa regra de inferência tem a forma

∀x(P (x) → Q(x))¬Q(a)

∴ ¬P (a), onde a é um elemento particular do domínio

57

8 Exercícios de Fixação

Exercício 1. Escreva a tabela verdade para todos os conectivos lógicos apresentados nesta nota deaula. Use os resultados encontrados como apoio para resolver e responder os exercícios da lista.

Exercício 2. Quais destas sentenças são proposições? Dê os valores verdade para as sentenças queforem proposições.(a) Boston é a capital de Massachusetts(b) Miami é a capital da Florida(c) 2 + 3 = 5(d) x+ 2 = 11(e) Responda esta questão.(f) A lua é feita de queijo.(g) 2n ≥ 100.

Exercício 3. Dê a negação das seguintes proposições:(a) Jeniffer e Teja são amigos.(b) Existem 13 itens em uma dúzia de padeiro.(c) 121 é um quadrado perfeito.(d) Steve tem mais de 100 GB livres em seu notebook.(e) Zack bloqueia emails e textos de Jeniffer.

Exercício 4. Sejam p, q e r as proposições:

p: ‘Você fica gripado’q: ‘Você perde a prova final’r: ‘Você conclui o curso’

Expresse cada uma das proposições em linguagem natural.(a) p → q(b) q → ¬r(c) (p → ¬r) ∨ (q → ¬r)(d) (p ∧ q) ∨ (¬q ∧ r)(e) ¬q ↔ r(f) p ∨ q ∨ r

Exercício 5. Determine se cada uma das declarações condicionais é verdadeira ou falsa.(a) Se 1 + 1 = 2, então 2 + 2 = 5(b) Se 1 + 1 = 3, então 2 + 2 = 4(c) Se 1 + 1 = 3, então 2 + 2 = 5(d) Se macacos podem voar, então 1 + 1 = 3(e) Se 1 + 1 = 3, então unicórnios existem(f) Se 2 + 2 = 4, então 1 + 2 = 3

58

Exercício 6. Quantas linhas aparecem na tabela verdade das seguintes proposições?(a) (q → ¬p) ∨ (¬p → ¬q)(b) (p ∨ ¬t) ∧ (p ∨ ¬s)(c) (p → r) ∨ (¬s → ¬t) ∨ (¬u → v)(d) p1 ∧ p2 ∧ p3 ∧ · · · ∧ pn−1 ∧ pn

Exercício 7. Construa uma tabela verdade para cada uma das proposições compostas:(a) (p → q) ↔ (¬q → ¬p)(b) (p ↔ q)⊕ (¬p ↔ ¬q)(c) [(p → q) → r] → s(d) (p → q) ∨ (¬p → r)(e) ¬p → (q → r)

Exercício 8. Circuitos combinacionais também podem ter sua saída representada por meio de pro-posições compostas. Pesquise sobre os símbolos gráficos que representam as portas lógicas AND,OR, e NOT e dê uma expressão que represente a saída dos circuitos combinatórios a seguir.

Figura 2: Circuitos Exercício 8

(a) (b)

(c) (d)

Exercício 9. Construa circuitos combinacionais cuja saída seja dada pela seguinte expressão:(a) (p ∧ ¬r) ∨ (¬q ∧ r)(b) [(¬p ∨ ¬r) ∧ ¬q] ∨ [¬p ∧ (q ∨ r)]

Exercício 10. Use tabelas verdade para verificar as equivalências a seguir. Nos casos em que setratarem de equivalências famosas, identifique-as.(a) (p ∨ q) ≡ (q ∨ p)(b) ¬(p ∧ q) ≡ (¬p ∨ ¬q)(c) p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r(d) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)(e) [(p ∧ ¬q) → 0] ≡ (p → q)

59

Exercício 11. Diga se as proposições compostas dadas a seguir são tautologias, contradições oucontingências.(a) [(p → q) ∧ (q → r)] → (p → r)(b) (p → q) ↔ (¬p ∨ q)(c) p ∧ q → ¬p(d) [p → (q → s)] ↔ [(p ∧ q) → r](e) (¬q → ¬p) → (p → q)(f) ¬(p ∧ ¬q) → r

Exercício 12. Mostre que o seguinte argumento é válido: ‘Se usarmos a linguagem assembly, entãoo programa será executado mais rapidamente. Se usarmos a linguagem assembly, o programa terámais linhas de código. Portanto, se usarmos a linguagem assembly, então o programa será executadomais rápido e terá mais linhas de código’.

Exercício 13. Seja P (x) a função proposicional que declara que x = x2. Se o domínio consiste noconjunto dos números inteiros, quais são os valores verdade de(a) P (0)?(b) P (1)?(c) P (2)?(d) P (−1)?(e) ∃xP (x)?(f) ∀xP (x)?

Exercício 14. Traduza as seguintes sentenças em expressões lógicas envolvendo quantificadores, dêa negação da sentença correspondente e traduza-a para linguagem natural.(a) Alguns motoristas não obedecem o limite de velocidade.(b) Todos os filmes indianos são sérios.(c) Ninguém pode guardar um segredo.(d) Existe alguém na classe que não tem uma boa atitude.(e) Todo pássaro pode voar.

Exercício 15. Traduza as declarações em linguagem natural, onde C(x) é ‘x é um coelho’, e S(x)é ‘x salta’, onde o domínio consiste no conjunto de todos os animais.(a) ∀x(C(x) → S(x))(b) ∀x(C(x) ∧ S(x))(c) ∃x(C(x) → S(x))(d) ∃x(C(x) ∧ S(x))

Exercício 16. Determine o valor verdade de cada uma das declarações.(a) ∃x ∈ R(x2 = 2)

60

(b) ∃x ∈ Z(x2 = 2)(c) ∀x ∈ R(x2 + 2 ≥ 1)(d) ∃x ∈ R(x2 = −1)(e) ∃x ∈ C(x2 = −1)(f) ∀x ∈ R(x2 6= x)

Exercício 17. Determinar o valor lógico das sentenças quantificadas, considerando o conjunto do-mínio D informado.(a) ∀x(|x| = x), com D = R

(b) ∃x(x+ 3 = 10), com D = {1, 2, 3, 4, 5}(c) ∃x(4x− 3 = 1− 2x), com D = R

(d) ¬∀x(x2 + x = 6), com D = {1, 2, 3}

Exercício 18. Reescrever cada uma das declarações abaixo, negando-as. Determine o valor verdadeda negação.(a) ∃x ∈ R(x2 = 2)(b) ∃x ∈ Z(x2 = 2)(c) ∀x ∈ R(x2 + 2 ≥ 1)(d) ∃x ∈ R(x2 = −1)(e) ∃x ∈ C(x2 = −1)(f) ∀x ∈ R(x2 6= x)

Exercício 19. Negar as sentenças.(a) Todos os homens são maus.(b) Existe pescador que não é mentiroso.(c) ∃x ∈ R(x2 + 5 = 2x)(d) Existe y tal que, para todo x, x+ y ≥ 7(e) Para todo x, existe y tal que x+ y < 3

Exercício 20. Para cada uma das afirmações dadas a seguir, assinale a declaração correta querepresenta a negação da declaração original:

(a) Algumas pessoas gostam de Matemática.✷ Algumas pessoas não gostam de Matemática.✷ Todo mundo não gosta de Matemática.✷ Todo mundo gosta de matemática.(b) Todo mundo gosta de sorvete.✷ Ninguém gosta de sorvete.✷ Todo mundo não gosta de sorvete.✷ Alguém não gosta de sorvete.

61

(c) Todo mundo é alto e magro.✷ Alguém é baixo e gordo.✷ Ninguém é alto e magro.✷ Alguém é baixo ou gordo.(d) Alguns retratos são velhos ou apagados.✷ Nenhum retrato está velho ou apagado.✷ Alguns retratos não estão velhos ou apagados.✷ Todos os retratos não estão velhos e não estão apagados.

Exercício 21. Qual o valor verdade de cada uma das expressões a seguir, onde o domínio é oconjunto Z e e as funções proposicionais O(x), L(x) e G(x) expressam O(x): ‘x é ímpar’, L(x):‘x < 10’ e G(x): ‘x > 9’.(a) ∃xO(x)(b) ∃x(L(x) ∧G(x))(c) ∀x(L(x) → O(x))(d) ∀x(L(x) ∨G(x))

Exercício 22. Use proposições, predicados e quantificadores para mais de uma variável para ex-pressar as declarações abaixo.(a) A soma dos quadrados de dois inteiros é maior ou igual ao quadrado da soma.(b) O valor absoluto do produto de dois inteiros é o produto de seus valores absolutos.(c) Há um estudante na classe que fala Esperanto.(d) A média de dois inteiros positivos é positiva.(e) O produto de dois inteiros negativos é negativo.

Exercício 23. Qual o valor verdade das expressões a seguir, onde x, y ∈ Z?(a) ∀x∃y(x+ y = x)(b) ∀x∃y(x+ y = 0)(c) ∃y∀x(x+ y = x)(d) ∃y∀x(x+ y = 0)(e) ∀x∀y((x < y) ∨ (y < x))(f) ∃x∃y(x2 = y)(g) ∀x(x2 > 0)(h) ∃x∀y(y 6= 0 → xy = 1)(i) ∀x(x 6= 0 → ∃y(xy = 1))

Exercício 24. Traduza as seguintes expressões lógicas em linguagem natural. Assuma x, y, z ∈ R.(a) ∀x∃y(x < y)(b) ∀x∀y∃z(xy = z)(c) ∀x∀y∃z(x = y + z)

62

(d) ∀x∀y((x ≥ 0) ∧ (y < 0) → (x− y > 0))(e) ∃x((x2 = 1) → (x 6= 0))(f) ∃x((x2 = 1) ∧ (x < 0))

Exercício 25. Dê a negação das seguintes sentenças quantificadas:(a) ∀x∀y((x ≥ 0) ∧ (y < 0) → (x− y > 0))(b) ∀x∃y(x < y)(c) ∃y∀x(x+ y = x)(d) ∃x∃y(x+ y 6= y + x)(e) ∀x∀y∃z(xy = z)(f) ∀x∀y∃z(z = (x+ y)/2)

Exercício 26. Determine o valor verdade da declaração ∃x∀y(x ≤ y2) quando o conjunto domíniodas variáveis consiste no conjunto:(a) R

(b) R+

(c) Z

(d) R∗

(e) {1, 2, 3, 4, 5}

Importante: os próximos exercícios são referentes à regras de inferência, e podem necessitar douso das equivalências lógicas apresentadas neste documento. Caso alguma equivalência lógica sobreproposições condicionais seja necessária, pesquisar e completar o exercício.

Exercício 27. Verifique se os argumentos apresentados a seguir são válidos:(a) ‘Se a taxa para importação diminuir, o comércio interno irá aumentará. Ou a taxa de descontodiminuirá ou o comércio interno não irá aumentar.’(b) ‘A colheita é boa, mas não há água suficiente. Se tivéssemos bastante água ou não tivessebastante sol, então haveria água suficiente. Portanto, a colheita é boa e há bastante sol’.(c) ‘Se José pegou as jóias, ou a sra. Krasov mentiu, então ocorreu um crime. O sr. Krasov nãoestava na cidade. Se ocorreu um crime, o sr. Krasov estava na cidade. Logo, José não pegou asjoias’.(d) ‘Se o produto for confiável, a parcela de mercado irá aumentar. Ou o produto é confiável, ou oscustos irão subir. A parcela de mercado não irá aumentar. Portanto, os custos irão subir.’

Exercício 28. Identifique as regras de inferência usadas nos argumentos abaixo.(a) Se estiver chuvoso, a piscina estará fechada. Está chuvoso. Logo, a piscina está fechada.(b) Se eu trabalhar a noite toda neste dever de casa, eu responderei todos os exercícios. Se euresponder todos os exercícios, eu irei entender todo o material. Assim, se eu trabalhar a noite todaneste dever de casa, então eu entenderei o material.(c) Steve trabalhará em uma companhia de computadores neste verão. Logo, Steve trabalhará emuma companhia de computadores ou estará na praia durante o verão.

63

Exercício 29. Crie argumentos em linguagem natural que sigam o formato das regras de inferênciadadas a seguir:

(a)

p → qq → r

∴ p → r

(b)p ∧ q

∴ p

(c)

p ∨ q¬p ∨ r

∴ q ∨ r

(d)

p ∨ q¬q∴ p

(e)

¬qp → q

∴ ¬p

Exercício 30. Use inferência para deduzir a conclusão a partir das hipóteses abaixo:(a) Hipóteses: ‘Randy trabalha duro, então ele é chato. Se Randy é chato, então ele não irá conse-guir um trabalho’. Conclusão: ‘Randy não irá conseguir o trabalho’.(b) Hipóteses: ‘Se não chover e não houver neblina, então a corrida de barcos será mantida e ademonstração do salva-vidas ocorrerá. Se a corrida de barcos for mantida, então o troféu será en-tregue. O troféu não foi entregue’. Conclusão: ‘Choveu’.

Exercício 31. Usando as hipóteses apresentadas a seguir, deduza a conclusão.(a) ‘Eu sou esperto ou sortudo. Eu não sou sortudo. Se eu sou sortudo, então eu irei ganhar aloteria’.(b) ‘Se eu comer comida apimentada, então eu terei pesadelos. Eu tenho pesadelos se trovejarenquanto eu durmo. Eu não tenho pesadelos’.(c) ‘Se eu tirar o dia de folga, ou chove ou neva. Eu tiro terça-feira ou quinta-feira de folga. Estavaensolarado na terça-feira. Não nevou na quinta-feira.’.

Exercício 32. Aplique regras de inferência sobre as sentenças abaixo para mostrar que a verdadesobre as premissas levam à conclusão.(a) ‘Cada um dos 93 estudantes desta classe possuem um computador pessoal. Todo mundo quepossui um computador pessoal pode usar um editor de textos. Assim, Zeke, um estudante destaclasse, pode usar um editor de texto’.(b) ‘Todos de New Jersey vivem à 30 km do oceano. Alguém em New Jersey nunca viu o oceano.Logo, alguem que vive a 30 km do oceano nunca viu o oceano’.(c) ‘Linda, uma estudante deste curso, tem um conversível vermelho. Todo mundo que possui umconversível vermelho tomou pelo menos uma multa por velocidade. Portanto, alguém que estudaneste curso tomou uma multa por velocidade’.

64

Exercício 33. Derive u das seguintes premissas:p → (q ∧ r)(q ∧ r) → ss → (t ∨ (¬t → u))p¬t

Exercício 34. Derive (r ∧ s) das seguintes premissas:¬¬pq → (r ∧ s)t → ¬¬qt ∨ ¬p

Exercício 35. Derive (p ∨ q) ∧ (p ∧ r) das seguintes premissas:(p ∨ q) → rr ∧ p

Exercício 36. Aplique regras de inferência sobre as sentenças abaixo para mostrar que a verdadesobre as premissas levam à conclusão.(a) Se Stefan está doente, Mathias não vai à escola. Se Mathias está doente, Stefan não vai à escola.Stefan e Mathias vão à escola. Logo, nem Stefan nem Mathias estão doentes.(b) Se a Lua gira em torno da Terra e a Terra gira em torno do sol, então Copérnico tinha razão.Se Copérnico tinha razão, então Ptolomeu não tinha razão. A Terra gira em torno do sol. Logo, sea Lua gira em torno da Terra, Ptomoleu não tinha razão.(c) Se a Lua gira em torno da Terra, então a Terra gira em torno do Sol. Se a Terra gira em tornodo sol, então, se a Lua gira em torno da Terra, ou Ptomoleu ou Copérnico tinham razão. Copérnicotinha razão se Ptolomeu não tinha razão. Nem Ptolomeu nem Copérnico tinham razão. Logo, aLua não gira em torno da Terra.

Exercício 37. Traduza os argumentos na forma de argumento correspondente, e determine suavalidade. Use a notação sugerida para traduzir as sentenças.(a) Todo papagaio é vermelho. Currupaco é um papagaio. Logo, currupaco é vermelho. Notação: c:Currupaco, P : x é um papagaio, R: x é vermelho.(b) Nenhuma arara é vermelha. Todos os papagaios são vermelhos. Logo, nenhuma arara é umpapagaio. Notação: A: x é uma arara.(c) Todo papagaio é vermelho ou verde. Currupaco não é verde. Logo, se Currupaco é um papagaio,então ele é vermelho. Notação: G: x é verde.(d) Todos amam todos. Logo, Romeu ama Julieta e Julieta ama Romeu. Notação: r: Romeu, j:Julieta, L: x ama y.(e) Todos os papagaios amam Julieta. Quem ama Julieta detesta Romeu. Quem detesta Romeu tembom gosto. Logo, todos os papagaios tem bom gosto. Notação: D: x detesta y, B: x tem bom gosto.

65

Exercício 38. Traduza os argumentos na forma de argumento correspondente, e determine suavalidade. Use a notação sugerida para traduzir as sentenças.(a) Todo papagaio é vermelho. Existem papagaios. Logo, existem coisas vermelhas. Notação: P : xé papagaio, R: x é vermelho.(b) Nenhum papagaio é cor-de-laranja. Algumas aves são papagaio. Logo, algumas aves não sãocor-de-laranja. Notação: B : x é uma ave, L: x é laranja.(c) Qualquer um que seja mais perigoso que Natasha é mais perigoso que Boris. Há espiões maisperigosos que Natasha. Logo, há espiões mais perigosos que Boris. Notação: b: Boris, n, Natasha,E : x é espião, D: x é mais perigoso que y.(d) As pessoas românticas são inspiradas pela Lua. Quem é inspirado pela Lua não gosta de rosas.Mas todos gostam ou de rosa ou de flores-do-campo. Logo, pessoas românticas gostam de flores-do-campo. Notação: P : x é uma pessoa romântica, L: x é inspirado pela Lua, R: x gosta de rosas,F : x gosta de flores-do-campo.

Referências

[Rosen, K. H.] Matemática Discreta e suas Aplicações, Tradução da 6a. Edição em Inglês. EditoraMc-Graw Hill Brasil, ISBN 978-85-7726-036-2, 2009.

[Gersting, J. L.] Fundamentos Matemáticos para Ciência da Computação, 5a. Edição. EditoraLTC. ISBN: 978-85-216-1422-7

[Menezes, P. B.] Matemática Discreta para Computação e Informática, 2a. Edição. Editora SagraLuzzatto.

[Scheinerman, E. R.] Matemática Discreta: Uma Introdução, 1a. edição Editora Thompson, ISBN-13: 978-85-2210-291-4, 2003.

[Grimaldi, R. P.] Discrete and Combinatorial Mathematics: An Applied Introduction, 3rd. edition.Adison Wesley, ISBN: 0-201-54983-2, 1994.

[Haggard, G., Schlipf, J. e Whitesides, S.] Discrete Mathematics for Computer Science. Thompson,ISBN: 0-534-49501-X, 2006.

[Daghlian, J.] Lógica e Álgebra de Boole, 4a. Edição. Editora Atlas, ISBN: 798-85-224-1256-3,2008.

[Mortari, C. A.] Introdução à Lógica, 1a. Edição. Editora Unesp, ISBN: 85-7139-337-0, 2001.

[Loureiro, A. A. F.] Slides sobre matemática discreta. Disponível emwww.dcc.ufmg.br/~loureiro/md/md_0Introducao.pdf. Acessado em Set/2012.

[Menezes, P. B.] Slides sobre matemática discreta. Disponível emftp://ftp.inf.ufrgs.br/pub/blauth/Discretas/Mat_Discreta2.pdf. Acessado emSet/2012.

66