Apostila lógica matemática

IFMG Campus Formiga Matemática Discreta
Notas de Aula 1: Lógica, Predicados, Quantiﬁcadores e Inferência
Prof. Diego Mello 2o. Semestre 2012
Sumário
1 Introdução 3
2 Lógica Proposicional 3
3 Proposições 3
3.1 Deﬁnições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Notação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Conectivos Lógicos 5
4.1 Negação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Conjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Disjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.4 Disjunção Exclusiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.5 Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.6 Bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.7 Resumo: Tabelas Verdade dos Conectivos Lógicos . . . . . . . . . . . . . . . . . . . . 13
4.8 Tabela Verdade para Proposições Compostas . . . . . . . . . . . . . . . . . . . . . . 134.9 Precedência de Operadores Lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.10 Linguagem Natural vs. Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.11 Lógica e Operações Bit a Bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Equivalências Proposicionais 19
5.1 Tautologia, Contradição e Contingência . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Equivalências Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Equivalências Importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4 Construindo novas equivalências lógicas . . . . . . . . . . . . . . . . . . . . . . . . . 22
6 Predicados e Quantiﬁcadores 24
6.1 Limitações da lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.3 Quantiﬁcadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3.1 Quantiﬁcador Universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3.2 Quantiﬁcador Existencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.3.3 Resumo dos quantiﬁcadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6.3.4 Quantiﬁcador de Unicidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1

6.3.5 Quantiﬁcadores com Restrição de Domínio . . . . . . . . . . . . . . . . . . . . 31
6.3.6 Precedência de Quantiﬁcadores . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6.3.7 Equivalências Lógicas Envolvendo Quantiﬁcadores . . . . . . . . . . . . . . . 32
6.3.8 Negação de Quantiﬁcadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.4 Quantiﬁcadores Aninhados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.4.1 Declarações Envolvendo Quantiﬁcadores Aninhados . . . . . . . . . . . . . . . 35
6.4.2 Negação de Quantiﬁcadores Aninhados . . . . . . . . . . . . . . . . . . . . . . 38
7 Regras de Inferência 38
7.1 Argumentos Válidos em Lógica Proposicional . . . . . . . . . . . . . . . . . . . . . . 39
7.2 Regras e Inferência para Proposições Lógicas . . . . . . . . . . . . . . . . . . . . . . 43
7.2.1 Modus Ponens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.2.2 Modus Tollens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.2.3 Disjunção Aditiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.2.4 Simpliﬁcação Conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
7.2.5 Silogismo Disjuntivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
7.2.6 Silogismo Hipotético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7.2.7 Conjunção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
7.2.8 Resolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.2.9 Resumo das Regras de Inferência . . . . . . . . . . . . . . . . . . . . . . . . . 49
7.3 Construindo Argumentos por meio de Regras de Inferência . . . . . . . . . . . . . . . 51
7.4 Regras de Inferência para Quantiﬁcadores . . . . . . . . . . . . . . . . . . . . . . . . 53
7.5 Regras de Inferência para Proposições e Declarações Quantiﬁcadas . . . . . . . . . . 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, Quantiﬁcadores e In-
ferência’ da disciplina de Matemática Discreta do curso de Ciência da Computação do Insituto
Federal de Minas Gerais - Campus Formiga. Ela é baseada no conteúdo dos livros referenciados
neste documento.
Este documento serve apenas como referência para acompanhamento das aulas, e não substitui a
necessidade de leitura e estudo da bibliograﬁa oﬁcial do curso. Muitos dos exemplos, tabelas e
diagramas contidos no documento foram extraídos e/ou adaptados dos livros contidos na seção de
referências bibliográﬁcas.
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, como
por exemplo nas linguagens de computador (execução lógica das instruções de um programa de
computador), inteligência artiﬁcial (sistemas especialistas) e projeto de computadores (álgebra de
Boole 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 regras
são usadas para distinguir os argumentos matemáticos válidos e inválidos.
3 Proposições
3.1 Deﬁnições
Em primeiro lugar, devemos deﬁnir o termo proposição.
Deﬁnição 1 (Proposição). Uma proposição é uma sentença declarativa que é verdadeira ou
falsa , 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 ser
consideradas 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). O
valor verdade de uma proposição é denotado por V (ou 1) se uma proposição for verdadeira, ou
F (ou 0) se uma proposição for falsa. Normalmente usam-se as letras p, q , r, s, ... para indicar
variá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, pois
nã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 vezes
denominados de conectivos lógicos). A estas novas proposições denominados de proposições
compostas.
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ão
p’);
• 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, deﬁnindo e exempliﬁcando cada um deles.
4.1 Negação
Deﬁnição 2 (Negação). Seja p uma proposição. A negação de p, indicada por ¬ p ou ¯ p, é a
sentença ‘não é o caso de p’, é lida como ‘não p’. O valor verdade da negação de p ( ¬ p) é o oposto
do valor verdade de p.
Uma tabela verdade é uma tabela que contém as proposições nas colunas, e as possibilidades de
valores-verdade nas linhas. É comum expressar os resultados de uma proposição composta por meio
de tabelas verdade, que permitem analisar seus valores-verdade. Deste ponto em diante apresenta-
remos a tabela verdade de cada conectivo lógico.
Segundo a Deﬁnição 2, para uma dada proposição p, temos a seguinte tabela verdade, cujo resultado
de ¬ p é apresentados na Tabela 1.
Tabela 1: Tabela verdade para a negação de p
p ¬ p
0 1
1 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
Deﬁniçã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 caso
contrário.
De acordo com a Deﬁnição 3, somente quando p e q assumem valores V ou 1 é que o resultado
da proposição composta p ∧ q vale 1. Isto posto, a Tabela 2 representa a tabela verdade para o
conectivo lógico de conjunção (
∧
).
Tabela 2: Tabela verdade para a conjunção ( p∧q )
p q p∧q
0 0 0
0 1 0
1 0 0
1 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
Deﬁnição 4 (Disjunção). Sejam p e q proposições. A disjunçao de p e q , indicada por p∨ p, é a
proposição ‘ p ou q ’. A proposição p∨q é falsa se p e q são ambas falsas, e verdadeira caso contrário.
Pela Deﬁnição 4, para que a proposição composta p∨q assuma valor verdadeiro basta que uma das
proposições primitivas ( p ou q ) seja verdadeira. Assim, a tabela verdade para o conectivo lógico de
disjunção (
∨
) é apresentada a seguir, na Tabela 3.
6

Tabela 3: Tabela verdade para a disjunção ( p∨q )
p q p∨q
0 0 0
0 1 1
1 0 1
1 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
Deﬁniçã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 é verdadeira
exatamente 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 Deﬁnição 5, quando apenas uma das propo-
sições primitivas ( p ou q ) assume valor verdadeiro. A Tabela 4 sumariza os possíveis resultados da
disjunção exclusiva de p e q .
Tabela 4: Tabela verdade para a disjunção exclusiva ( p⊕q )
p q p⊕q
0 0 0
0 1 1
1 0 1
1 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
Deﬁnição 6 (Condicional). Sejam p e q proposições. A proposição condicional p → q é a
proposiçã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 Deﬁnição 6, a proposição composta p → q assume valor falso apenas quando a
proposição p é verdadeira e q é falsa. Neste tipo de construção, a proposição p é denominada de
hipó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 1
0 1 1
1 0 0
1 1 1
Em Ciência da Computação, as estruturas condicionais If-Then e If-Then-Else estão presentes
na maioria das linguagem de programação estruturadas. Essa estrutura tem alguma relação com a
proposiçã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 do
valor 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ção
do programa para outra linha ou imprimindo algum resultado. Aqui, q não assume o papel de
proposição lógica que estamos discutindo, mas sim como uma instrução. Quando lidamos com uma
estrutura 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 for
verdadeiro, ou executará r se p for falso.
Além deste contexto, a proposição condicional p → q é usada como regra essencial no raciocínio
matemá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 é suﬁciente para q
• p é uma condição suﬁciente 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 exempliﬁcar, sejam as proposições
9

• p: Maria tira nota 10 no exame ﬁnal
• 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 ﬁnal, então terá conceito A
• Maria vai receber conceito A quando tirar nota 10 no exame ﬁnal
• Maria tirar nota 10 no exame ﬁnal é suﬁciente para que Maria receba o conceito A
• Para receber o conceito A, é suﬁciente que Maria tire nota 10 no exame ﬁnal
• Maria vai receber conceito A, a menos que não tire nota 10 no exame ﬁnal
Nos casos apresentados como exemplo, as proposições foram usadas em linguagem natural onde
existe uma relação entre a hipótese e a conclusão. Entretanto, quando as proposições p e q são
combinadas na proposição p → q , não é necessário haver uma relação causal entre a hipótese
e 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 expressas
na sua tabela verdade forem satisfeitas (ver Tabela 5). Isto ocorre porque o conceito matemático
de 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 feira
pois a conclusão 2 + 3 = 6 é falsa, e pela tabela verdade a única possibilidade de que p → r resulte
em 1 é dada pela atribuição de valores-verdade 0 tanto para a hipótese quanto para a conclusão (se p é 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 → q
p q ¬ p ¬q p → q q → p ¬q → ¬ p ¬ p → ¬q
0 0 1 1 1 1 1 1
0 1 1 0 1 0 1 0
1 0 0 1 0 1 0 1
1 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 como
també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
Deﬁniçã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 o
mesmo valor verdade, e falsa caso contrário. As proposições bicondicionais também são chamadas
de bi-implicações.
Pela Deﬁnição 7, a proposição p ↔ q é verdadeira apenas quando p e q são ambas verdadeiras, ou
ambas falsas. Quando p e q possuem valores-verdade opostos, então essa proposição assume valor
0. 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 1
0 1 0
1 0 0
1 1 1
Outras formas de se ler a proposição p ↔ q :
• p é necessária e suﬁciente para q
• se p, então q e vice-versa
• p se e somente se q
• p é necessário e suﬁciente para q
• p sse q
Note que, pela deﬁniçã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ógicos
p q ¬ p p∧q p∨q p⊕q p → q p ↔ q
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
1 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 para
cada proposição composta que ocorre na proposição composta srcinal, de forma que a última co-
luna corresponde à proposição composta srcinal.
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 é VV , VF , FV e FF , de forma que a tabela verdade terá 4 linhas. As
duas primeiras colunas conterão os valores-verdade das variáveis p e q . A Tabela 9 apresenta esta
situação.
Tabela 9: Passo 1: Inserir as variáveis proposicionais primitivas
p q
1 1
1 0
0 1
0 0
A próxima etapa consiste em identiﬁcar qual será a próxima proposição composta que deve ser
determinada. 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 ﬁnal é dado na
Tabela 10.
13

Tabela 10: Passo 2: Adicionando a coluna ¬q
p q ¬q
1 1 0
1 0 1
0 1 0
0 0 1
Na próxima etapa, iremos determinar os valores-verdade da proposição ( p∨¬q ). Incluiremos uma
nova 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 1
1 0 1 1
0 1 0 0
0 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-verdade
da proposição ( p∧q ), que podem ser obtidos diretamente da Tabela 8, operação de conjunção de
duas 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 1
1 0 1 1 0
0 1 0 0 0
0 0 1 1 0
Por ﬁm, chegamos à proposição composta srcinal, 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 os
valores-verdade já determinados para a hipótese ( p∨¬q ) e conclusão ( p∧q ), e com base na tabela
verdade da proposição condicional (→) apresentada na Tabela 8 chegamos à tabela verdade ﬁnal
para 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 1
1 0 1 1 0 0
0 1 0 0 0 1
0 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 que
devem ser avaliadas na interpretação de uma proposição composta. A ordem de precedência destes
operadores é dada a seguir, na Tabela 14.
Tabela 14: Ordem de precedência dos conectivos lógicos
Operador 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ões
ló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 linguagem
lógica
• (t ∧ ¬u) → s: Se o dia estiver ensolarado e não estiver nevando, então João sairá pra
caminhar lá fora
• t → (¬u → s): Se o dia estiver ensolarado, então se não estiver nevando João sairá para
caminhar lá fora
• ¬(s ↔ (u∨ t)): João não irá caminhar lá fora se e somente se estiver nevando ou o dia
estiver 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ê tiver
menos do que 1,20 metros de altura a menos que você tenha 16 anos de idade.’ Podemos fazer a
traduçã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ógicas
elimina as ambiguidades. Isso é muito importante na atividade de especiﬁcação de sistemas de
hardware e software de forma que um sistema em desenvolvimento use tais especiﬁcações. Propo-
sições compostas podem, dessa forma, serem empregadas com este propósito.
Uma especiﬁcação de sistema deve ser consistente, i.e., não conter especiﬁcações conﬂitantes que
possam ser usadas para derivar uma contradição. Se as especiﬁcaçõ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 especiﬁcações de sistema são consistentes:
• A mensagem de diagnóstico é armazenada no buﬀer ou ela é retransmitida
• A mensagem de diagnóstico não é armazenada no buﬀer
• Se a mensagem de diagnóstico é armazenada no buﬀer, então ela é retransmitida
A veriﬁcação de consistência de um sistema passa pela sua tradução em expressões lógicas. Sejam
as proposições primitivas
• p: A mensagem de diagnóstico é armazenada no buﬀer
• q : A mensagem de diagnóstico é retransmitida
As três especiﬁcações acima podem ser traduzidas como:
• A mensagem de diagnóstico é armazenada no buﬀer ou ela é retransmitida: p∨q
• A mensagem de diagnóstico não é armazenada no buﬀer: ¬ p
• Se a mensagem de diagnóstico é armazenada no buﬀer, então ela é retransmitida p → q
Veriﬁcando a consistência das três especiﬁcações por meio da tabela verdade:
Tabela 15: Tabela Verdade para as especiﬁcações ( p∨q ), (¬ p) e ( p → q )
p q p∨q ¬ p p → q
1 1 1 0 1
1 0 1 0 0
0 1 1 1 1
0 0 0 1 1
Uma atribuição de valores que torna as três especiﬁcaçõ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 especiﬁcação de sistema apresentado é consis-
tente. ◭
Exemplo:
A especiﬁcação do sistema apresentado no exemplo anterior se mantém consistente se adicionarmosuma nova especiﬁcação ‘A mensagem de diagnóstico não é transmitida’?
17

Tabela 16: Tabela Verdade para as especiﬁcações ( p∨q ), (¬ p) e ( p → q ) e (¬q )
p q p∨q ¬ p p → q ¬q
1 1 1 0 1 0
1 0 1 0 0 1
0 1 1 1 1 0
0 0 0 1 1 1
Faremos tal veriﬁcação recorrendo novamente à tabela verdade, que agora contempla a proposição
(¬q ). A tabela verdade desta especiﬁcação de sistemas é dada a seguir, na Tabela 16.
Pelos valores-verdade encontrados na Tabela 16, observamos que não existe nenhuma atribuição de
valores de p e q que satisfaçam as quatro especiﬁcações apresentadas. Isto posto, concluímos que
esta especiﬁcaçã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 é um
símbolo com dois valores possíveis: 0 e 1, que pode ser interpretado como V e F. Uma variável
booleana é aquela que admite apenas dois valores: verdadeiro ou falso. Uma variável booleana pode
ser 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 tabela
verdade destes conectivos lógicos se aplica às operações bit a bit.
Deﬁnição 8 (String). Uma string de bits é uma sequência de zero ou mais bits. O tamanho da
string é 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 S 1:
1011011101 e S 2: 0010101111.
S 1 1 0 1 1 0 1 1 1 0 1
S 2 0 0 1 0 1 0 1 1 1 1
S 1 OR S 2 1 0 1 1 1 1 1 1 1 1
S 1 AND S 2 0 0 1 0 0 0 1 1 0 1
S 1 XOR S 2 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 mesmos
valores-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 deﬁnir formalmente o conceito de equivalência, devemos formalizar a classiﬁcação das
proposições de acordo com seus possíveis valores-verdade.
5.1 Tautologia, Contradição e Contingência
Deﬁnição 9 (Classiﬁcação). Uma proposição composta que é sempre verdadeira, independente dos
valores-verdade das proposições que nela ocorrem, é denominada de tautologia . Uma proposição
composta que é sempre falsa é chamada de contradição. Uma proposição composta que não é nem
uma 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 proposicional
e dos conectivos lógicos de conjunção e disjunção, conforme ilustra a tabela verdade expressa na
Tabela 17.
Tabela 17: Tabela Verdade para as proposições ( p∨¬ p) e ( p∧¬ p)
p
¬
p p
∨¬
p p
∧¬
p
0 1 1 0
1 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 1
0 1 0 0 1
1 0 0 0 1
1 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 0
0 1 0 1 0 0
1 0 0 1 0 0
1 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 → ¬ p
p ¬ p p → ¬ p
0 1 1
1 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
Deﬁniçã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 logicamente
equivalentes.
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

Pela simpliﬁcação, temos que ( p∨q )∧¬(¬ p∧q ) ≡ p. ◭
6 Predicados e Quantiﬁcadores
6.1 Limitações da lógica proposicional
A lógica proposicional nem sempre consegue expressar adequadamente o signiﬁcado das proposi-
ções em linguagem matemática e em linguagem natural, visto que formulas proposicionais tem uma
possibilidade limitada de expressão.
Para exempliﬁcar, 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 conectivos
lógicos, como ﬁzemos até o presente momento.
Isto ocorre porque elas contém elementos novos (‘para todo’, ‘para cada’, ‘para algum’) que são
ligados ao conceito de predicados e quantiﬁcadores. Quantiﬁcadores 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 signiﬁcado de uma
grande faixa de declarações deste tipo que nos permite raciocinar e explorar relacionamentos entre
objetos.
6.2 Predicados
Deﬁniçã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 aﬁrmações matemá-
ticas, programas de computadores e especiﬁcação de sistemas.
Sentenças que possuem variáveis não são nem verdadeiras nem falsas enquanto não se especiﬁcar
um 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 Deﬁnições 12 e 13.
Deﬁnição 12 (Sentença Aberta). Dado um conjunto A = ∅, uma sentença aberta em A é uma
expressã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.
Deﬁniçã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 o
predicado 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 atribui
um 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 aﬁrmações que envolvam mais de uma variável. Por exemplo, considere a
aﬁrmaçã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,...,x
n) e é denomi-
nada de função proposicional P para a n-upla (x1,x2,...,x
n), e P é denominado de predicado
n-ário.
Por ﬁm, ainda existe a negação de uma sentença aberta, que consiste na aplicação do operador
lógico de negação sob a sentença, i.e., ¬P (x). Por exemplo, se P (x) é uma função proposicional
que declara que ‘o número x + 2 é um inteiro par’, então ¬P (x)’ deve ser interpretado como a
declaraçã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 Quantiﬁcadores
Quando atribuímos valores às variáveis de uma função proposicional, a sentença resultante torna-se
uma proposição e assume um valor verdade. Entretanto, existe outra maneira de se criar proposi-
ções a partir de funções proposicionais, denominada quantiﬁcação.
A quantiﬁcação permite-nos dizer que um dado predicado P é verdadeiro para um conjunto de
elementos.
A área da lógica que estuuda os predicados e quantiﬁcadores é denominada de cálculo de predi-
cados.
6.3.1 Quantiﬁcador Universal
Algumas aﬁrmações matemáticas referem-se à uma propriedade que é verdadeira para todos os
valores que uma variável pode assumir em um determinado domínio/universo do discurso. A
quantiﬁcação universal de P (x) para um domínio particular é a proposição que aﬁrma que P (x)
é verdadeiro para todos os valores de x neste domínio. O domínio deve sempre ser especiﬁcado
26

quando um quantiﬁcador universal for usado.
Deﬁnição 14 (Quantiﬁcação Universal). Uma quantiﬁcação universal de P (x) é a declaração
do tipo ‘ P (x) para todos os valores de x no domínio’
A notação ∀xP (x) denota uma quantiﬁcação universal de P (x)
O símbolo ∀ é denominado quantiﬁcador universal . A notação ∀xP (x) é lida como ‘para todo
xP (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 quantiﬁcação
universal ∀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úmeros
inteiros ( Z)
A quantiﬁcaçã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 quantiﬁcação ∀xP (x) no domínio dos
números reais ( R)?
Ao substituir a variável x por qualquer número real na sentença aberta P (x), sempre tomaremos
proposições que são verdadeiras. Como P (x) é verdadeiro para todos os números reais, temos que
a quantiﬁcaçã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 quantiﬁcadas é
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 ‘x
2
< 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 conjunto
domínio é A = {1,2,3,4}. Como P (4) é falso, então a quantiﬁcaçã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) : x
2≥ 0
• S (x) : x
2
−
3
≥
0
A quantiﬁcação ∀x[Q(x) → S (x)] é verdadeira ou falsa?
Esta sentença pode ser traduzida como: ‘para todo número real, se x
2≥ 0, então x
2−3 ≥ 0’. Para
mostrar que esta declaração é falsa, basta apresentarmos um contra-exemplo, isto é, um valor de x
para 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. Encontramos
um caso onde [Q(x) → S (x)] é falso; logo a declaração ∀x[Q(x) → S (x)] é falsa porque existe pelo
menos um valor de x para o qual [Q(x) → S (x)] é falso. ◭
Exemplo:
Qual o valor verdade de ∀x(x
2≥ 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 x
2≥ x,
para todos os inteiros.
No entanto, se o domínio for o conjunto dos números reais R, então existem contra-exemplos que
mostram que a quantiﬁcação universal é falsa. Para exempliﬁcar, sejam dois contra-exemplos os
números
1/2 e
1/3, que pertencem aos números reais e onde

1
2

2
≥

1
2

, ou

1
3

2
≥

1
3

. Isso ocorrerá
para qualquer número contido no intervalo (0,1). ◭
6.3.2 Quantiﬁcador Existencial
Muitas sentenças matemáticas aﬁrmam que existe um elemento que possui uma certa propriedade.
Tais sentenças podem ser expressas usando-se quantiﬁcação existencial. Por meio delas, formamos
uma proposição que é verdadeira se e somente se P (x) é verdadeiro para pelo menos um valor de x
do domínio.
28

Deﬁnição 15 (Quantiﬁcação Existencial). A quantiﬁcaçã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 quantiﬁcação existencial de P (x). O símbolo ∃ é denominado
quantiﬁcador existencial .
A quantiﬁcação existencial ∃xP (x) é lida como ‘existe um x tal que P (x)’, ou ‘existe pelo menos
um 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 quantiﬁcação
existencial
∃
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 valor
verdade da quantiﬁcaçã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 quantiﬁcaçã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): x
2−3x−4 = 0
Veriﬁcar se a quantiﬁcação ∃x[P (x)∧Q(x)] é verdadeira ou falsa.
Para que a quantiﬁcação apresentada seja verdadeira, devemos apresentar pelo menos um caso em
que 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 valores
que tornam P (4) : (4) ≥ 0 verdadeiro, e Q(4) : (4)
2−3(4)−4 = 0 também verdadeiro.
Logo, concluímos que a quantiﬁcação ∃x[P (x)∧Q(x)] é verdadeira. ◭
6.3.3 Resumo dos quantiﬁcadores
Diante dos resultados apresentados nas sub-seções anteriores, podemos resumir as situações em quecada quantiﬁcador é verdadeiro ou falso na Tabela 26.
29

Tabela 26: Resumo: quantiﬁcadores 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 a
do 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 a
do domínio para o qual ¬P (a) é falso e
P (a) é verdadeiro
6.3.4 Quantiﬁcador de Unicidade
Deﬁnição 16 (Quantiﬁcação de Unicidade). O quantiﬁcador de unicidade, também conhecido
como quantiﬁcador de singularidade, declara que ‘existe um único x tal que P (x) é verdadeiro’,
denotado pelo símbolo ∃! ou ∃1.
A notação ∃!xP (x) aﬁrma que ‘existe um único x tal que P (x).
Exemplo:
Seja a sentença aberta P (x) : x
2
= 4. Veriﬁcar 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(x
2
= 4) é verdadeira, pois o número 2 é o único número
do conjunto N que, quando elevado ao quadrado, resulta em 4.
No domínio dos inteiros, a proposição ∃!x(x
2
= 4) é falsa, pois os números 2 e −2 do conjunto Z
possuem quadrado igual a 4. ◭
Exemplo:
Veriﬁcar o valor-verdade das seguintes quantiﬁcaçõ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 é inﬁnito, logo existem inﬁnitos números
deste domínio que são pares: {2,4,6,8,10,...}. ◭
6.3.5 Quantiﬁcadores com Restrição de Domínio
Pode-se restringir o domínio de um quantiﬁcador utilizando-se uma notação abreviada, onde a con-
dição que a variável deve satisfazer é incluída após o quantiﬁcador.
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] = 0) ◭
Exemplo:
Sejam as sentenças abertas, com domínio no conjunto R:
•
∀
x < 0(x
2
> 0), interpretado como ‘o quadrado de um número negativo é positivo’, que
poderia ser declarado da seguinte maneira: ∀x(x < 0 → x
2> 0)
• ∀y = 0(y
3= 0), interpretado como ‘o cubo de um número real não nulo é não nulo’, que
poderia ser declarado como ∀y(y = 0 → y
3= 0)
• ∃z > 0(z
2
= 2), interpretado como ‘existe uma raiz quadrada positiva de 2’, cuja declaração
equivale a ∃z(z > 0∧z
2
= 2)
◭
Note que:
• a restrição de uma quantiﬁcação universal é o mesmo que uma quantiﬁcação universal de uma
sentença condicional.
• a restrição de uma quantiﬁcação existencial é o mesmo que a quantiﬁcação existencial de uma
conjunção.
31

6.3.6 Precedência de Quantiﬁcadores
Os quantiﬁcadores ∀ 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 Quantiﬁcadores
Deﬁnição 17 (Equivalência em Quantiﬁcadores). Sentenças envolvendo quantiﬁcadores e predica-
dos são logicamente equivalentes se e somente se elas tem a mesma tabela verdade, não importa
quais 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-
ﬁcadores 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 equivalentes
para um mesmo domínio A.
Para mostrar que as sentenças são logicamente equivalentes, devemos mostrar que elas possuem os
mesmos 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ça
P (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ínio
A. Se P (a) e Q(a) são verdadeiros, então a sentença P (a) ∧ Q(a) também será verdadeira para
qualquer 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 quantiﬁ-
cação universal sobre a conjunção, visto que tanto uma forma quando a outra resultam nos mesmos
valores verdade.
A Tabela 27 apresenta algumas equivalências e implicações lógicas importantes referentes à quanti-
ﬁcadores:
Tabela 27: Equivalências e Implicações Lógicas sobre Sentenças Quantiﬁcadas
Expressã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 Quantiﬁcadores
É comum considerar a situação de negar uma expressão quantiﬁcada. Por exemplo, seja a declara-
ção ‘Todo estudante na sua classe teve aulas de cálculo’, representada pela quantiﬁcaçã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 de
cá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 quantiﬁcação universal equivale à quantiﬁcação existencial da
negação da função proposicional srcinal: ¬∀xP (x) ≡ ∃x¬P (x).
Pode ser que se torne necessário negar uma quantiﬁcação existencial. Seja a sentença ‘Existe um
estudante 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 classe
que teve aulas de cálculo’, que equivale a dizer que ‘Todo estudante desta classe não teve aulas de
cálculo’. Formalmente, a negação da quantiﬁcação existencial equivale à quantiﬁcação universal da
negação da função proposicional srcinal: ¬∃xP (x) ≡ ∀x¬P (x).
As negações de quantiﬁcadores são chamadas de leis de De Morgan para quantiﬁcadores, e
estão resuminadas na Tabela 28.
33

Tabela 28: Leis de De Morgan para Quantiﬁcadores
Negação Sentença Equivalente
Quando a negação é verda-
deira
Quando a negação é falsa
¬∃xP (x) ∀x¬P (x) Para todo x, P (x) é falsa
Existe 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 ’Existe
um 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íticos
nã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 srcinal é 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(x
2
> x) e ∃x(x
2
= 2)?
A negação de ∀x(x
2
> x) equivale à ∃x¬(x
2
> x), que pode ser reescrita como ∃x(x
2≤ x). A
negação de ∃x(x
2
= 2) equivale à ∀x¬(x
2
= 2), que pode ser reescrita como ∀x(x
2= 2).
Em ambos os casos, os valores-verdade destas proposições dependem do conjunto numérico que
corresponde ao domínio. Por exemplo se o domínio da sentença ∀x(x
2= 2) for o conjunto Z, então
a 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) : ‘x
2
= 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)) signiﬁca ‘Para cada inteiro x, 2x+1 = 5 ou x
2= 9’. ◭
6.4 Quantiﬁcadores Aninhados
Até o presente momento, os quantiﬁcadores foram usados para mostrar como podem ser usados
em sentenças matemáticas, assim como podem ser usados para traduzir a linguagem natural para
expressões lógicas.
A partir de agora, introduziremos o conceito de quantiﬁcadores aninhados (agrupados).
6.4.1 Declarações Envolvendo Quantiﬁcadores Aninhados
Dois quantiﬁcadores estão aninhados se um está no escopo do outro, onde o quantiﬁcador mais
interno é tratado como uma função proposicional. Para exempliﬁcar, ∀x∃y(x+ y = 0) é o mesmo
que ∀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 aﬁrma 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 quantiﬁcações ∃y∀xQ(x,y) e
∀x∃yQ(x,y), com x ∈ R e y ∈ R.
A quantiﬁcação ∃y∀x(x+y = 0) representa a aﬁrmação ‘existe um número real y para todo número
real x para o qual x + y = 0. Como não existe nenhum número real y que, somado à todo real x
resulta em zero, então a sentença ∃y∀xQ(x,y) é falsa.
Já a quantiﬁcação ∀x∃y(x+y = 0) expressa a aﬁrmação ‘para todo real x, existe um número real y
para o qual x+y = 0’. Essa sentença é verdadeira, pois para cada x, existe um y = −x cuja soma
x+y resulta em 0. ◭
35

A Tabela 29 resume o signiﬁcado das quantiﬁcações com duas variáveis, indicando as situações
em que o valor verdade da quantiﬁcação é verdadeiro, e as situações onde a quantiﬁcação assume
valor-verdade falso.
Tabela 29: Quantiﬁcadores com Duas Variáveis
Sentença Quando é verdadeira Quando é falsa
∀x∀yP (x,y)
P (x,y) é verdadeira para todo
par x,y
Existe um par x,y para o qual
P (x,y) é falsa
∀
y
∀
xP (x,y)
P (x,y) é verdadeira para todo
par x,y
Existe um par x,y para o qual
P (x,y) é falsa
∀x∃yP (x,y)
Para todo x existe um y para o
qual 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 o
qual P (x,y) é falsa
∃x∃yP (x,y)
Existe um par x,y para o qual
P (x,y) é verdadeira
P (x,y) é falsa para todo par x,y
∃y∃xP (x,y)
Existe um par x,y para o qual
P (x,y) é verdadeira
P (x,y) é falsa para todo par x,y
Neste último exemplo ﬁca claro que a ordem em que os quantiﬁcadores aparecem determina a
verdade sobre a declaração. Segue mais um exemplo, desta vez envolvendo três variáveis e três
quantiﬁcadores, onde a ordem afeta a verdade da declaração:
Exemplo:
SejaS (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 quantiﬁcação ∀x∀y∃zS (x,y,z) pode ser expressa em linguagem natural como ‘para todo real x e
y, existe um real z para o qual x+y = z’, que é verdadeira visto que a soma de dois números reais
resulta em um número real.
Já a quantiﬁcação ∃z∀x∀yS (x,y,z) é interpretada em linguagem natural como ‘existe um número
real z tal que para todo real x e y, x + y = z’. Como inexiste tal número, então a quantiﬁcação
correspondente é falsa. ◭
Sentenças matemáticas também podem traduzidas em lógica por meio de quantiﬁcadores. Os pró-
ximos dois exemplos ilustram essa tradução, passo a passo, da declaração inicial até o reﬁnamento
ﬁnal.
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 quantiﬁcadores. Ela seria algo
do tipo: ‘Para cada dois números inteiros, se ambos são positivos, então o resultado da soma destes
dois inteiros é positivo.’.
O próximo passo do reﬁnamento consiste em incluir variáveis. Teríamos ‘Para todos os inteiros
positivos x e y, x+y é positivo’.
Por ﬁm, 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 quantiﬁcação, a expressão acima pode ser representada de outra maneira
ainda:
∀x∀y(x+y > 0), com x,y ∈ Z
+
A declaração ‘A soma de dois inteiros positivos é sempre positivo’ foi traduzida em termos formais
como ∀x∀y(x+y > 0), com x,y ∈ Z
+
. ◭
Deﬁnição 18 (Inverso Multiplicativo). O inverso multiplicativo de um número real x é um
nú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 aﬁrmação da seguinte maneira: ‘Para cada número real x, exceto zero, x tem um
inverso multiplicativo.
Em seguida, acrescentamos um pouco mais de formalismo na declaração usando a Deﬁnição 18 para
melhorar ainda mais a declaração sobre o que é um inverso multiplicativo: ‘Para cada número real
x, se x = 0, então existe um número real y tal que xy = 1’. Essa última declaração é suﬁciente para
uma tradução direta da sentença em
∀x((x = 0) → ∃y(xy = 1))
A declaração ‘Cada número real, exceto 0, tem um inverso multiplicativo’ foi traduzida em termos
formais em ∀x((x = 0) → ∃y(xy = 1)), com x,y ∈ R. ◭
O próximo caso exempliﬁca como traduzir uma quantiﬁcaçã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 consiste
em 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 um
computador ou existe um aluno y tal que y tem um computador e y é amigo de x’.
De uma maneira menos formal, essa declaração signiﬁca que cada aluno da escola ou tem um com-
putador ou tem um amigo que tem um computador. ◭
6.4.2 Negação de Quantiﬁcadores Aninhados
As negações de declarações quantiﬁcadas com quantiﬁcadores aninhados podem ser feitas aplicando-
se sucessivamente as regras para negar declarações envolvendo um único quantiﬁcador.
Exemplo:
Expresse a negação da declaração quantiﬁcada ∀x∃y(xy = 1) tal que a negação precede a declaração.
Usaremos os resultados da Tabela 28 para negação de quantiﬁcadores para aplicar a negação da
sentença srcinal. 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 a
quantiﬁcação ∃y. A negação de ∃x¬∃y(xy = 1) resulta, portanto, em ∃x∀y¬(xy = 1)
Para ﬁnalizar, podemos substituir a negação ¬(xy = 1) por (xy = 1). Após as sucessivas aplicações
de negação sobre cada quantiﬁcador e sobre a função proposicional, concluímos que ∀x∃y(xy = 1)
resulta em ∃x∀y(xy = 1). ◭
7 Regras de Inferência
Todos os fundamentos de lógica apresentados até o presente momento possuem um objetivo muito
especial 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 ﬁnal do argumento, deve seguir da verdade
das sentenças precedentes do argumento (das premissas).
Diante disto, temos que um argumento é valido se e somente se é impossível que todas as premissas
sejam 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-
tiﬁcadas, em ambos os casos com objetivo de produzir argumentos válidos. As regras de inferência
usando os quantiﬁcadores 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 é veriﬁcar se a conclusão ‘você pode efetuar login na rede’ é verdadeira com
base 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 de
inferência .
Deﬁnição 19 (Argumento). Um argumento é uma sequência de aﬁrmaçõ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 ﬁnal, são denominadas premissas, enquanto que a proposição ﬁnal é denominada conclusão.
Um argumento é válido se a verdade de todas as suas premissas implicam em uma conclusão
verdadeira.
Exemplo:
‘Está chovendo ou está nevando’
‘Não está nevando’
Portanto,
‘Está chovendo’ ◭
39

Pela Deﬁnição 19 temos que um argumento com premissas p1,p2,...,p
n e conclusão q é válido
quando ( p1 ∧ p2 ∧···∧ p
n) → q é uma tautologia.
Para analizar um argumento, substituímos as proposições (i.e., sentenças aﬁrmativas) por variáveis
proposicionais (i.e., p, q , r, ...). Isso transforma um argumento em uma forma de argumento. A
validade de um argumento advém da validade da forma do argumento.
Deﬁnição 20 (Forma de Argumento). Em lógica proposicional, uma forma de argumento é uma
sequê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 a
conclusã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, seguida
por 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 veriﬁcar se uma forma de argumento é válida, podemos usar o seguinte procedimento, descritono Algoritmo 1:
Algoritmo 1 Veriﬁca a validade de uma forma de argumento
1: Identiﬁque as premissas e a conclusão da forma de argumento
2: Construa a tabela verdade, destacando as premissas e a conclusão
3: 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 then
5: A forma de argumento é válida
6: else
7: A forma de argumento é inválida
8: 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 → q p
∴ 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 0
0 1 1 0 1 1
1 0 0 0 1 0
1 1 1 1 1 1
3. Segundo a Deﬁnição 20 e o Algoritmo 1, o argumento é válido se ambas as premissas p e p → q
e a conclusão q são verdadeiras. Identiﬁcamos as linhas onde as premissas e conclusão são
verdadeiras.
41

proposição com quatro variáveis lógicas, existem 16 diferentes combinações de valores-verdade; para
uma 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 2
n
linhas
diferentes 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 uso
de tabelas verdade, é por meio de formas de argumento mais simples denominadas de regras de
inferência. Tais regras são usadas como elementos básicos para construir formas de argumento
válidas mais complexas.
7.2.1 Modus Ponens
A tautologia [( p → q )∧ p] → q é a base da regra de inferência denominada modus ponens (do
latim, método de aﬁrmar). Essa tautologia leva à seguinte forma de argumento válida :
p → q
p
∴ q
onde ∴ é lido como ‘portanto’. Nesta notação, as premissas são escritas em colunas, seguidas por
uma barra horizontal, seguida por uma linha que começa com o símbolo portanto (∴), seguido da
conclusã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 → q
p
∴ q
p q p → q p ( p → q )∧ p [( p → q )∧ p] → q q
0 0 1 0 0 1 0
0 1 1 0 0 1 1
1 0 0 1 0 1 0
1 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á nevando
hoje’ 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
>

3
2

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
>

3
2

2
Na forma de argumento deste exemplo, as premissas são representadas pelas proposições p e p → q
enquanto que conclusão é q . Essa forma é a forma conhecida como modus ponens , que é sabido ser
vá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 seguinte
forma 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 ¬ p
0 0 1 1 1 1 1
0 1 1 0 0 1 1
1 0 0 1 0 1 0
1 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 0
0 1 0 1 1
1 0 1 1 1
1 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 Simpliﬁcação Conjuntiva
A regra de inferência denominada de simpliﬁcação conjuntiva é aquela que possui a forma
p∧q
∴ p
A Tabela 33 mostra os valores-verdade para a simpliﬁcação conjuntiva.
Tabela 33: Regra de inferência simpliﬁcação conjuntiva e sua tabela-verdade
Forma do argumento
p∧q
∴ p
p q p∧q ( p∧q ) → p p
0 0 0 1 0
0 1 0 1 0
1 0 0 1 1
1 1 1 1 1
46

p
∴ p∨q
p → ( p∨q ) Disjunção Aditiva
p∧q
∴ q
( p∧q ) → p Simpliﬁcação Conjuntiva
p
q
∴ 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 ser
aplicadas de forma a provar este resultado.
Mais adiante veremos outra aplicação importante em ciência da computação e, em especial, em
matemá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ável
proposicional à 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):
Identiﬁcaçã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, que
sã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
Idetiﬁcaçã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 Quantiﬁcadores
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 envolvendo
quantiﬁcadores. São elas: instanciação universal, generalização universal, instanciação existencial e
generalizaçã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íﬁco, a partir do domínio. Em outras pala-
vras, quando nós aﬁrmamos que a escolha do elemento c é arbitrária, nós estamos aﬁrmando que
nã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 construir
raciocínios incorretos quando usando generalização universal, tomando como verdade considerações
que não podem ser garantidas para um elemento c arbitrário do domínio.
Outra regra de inferência importante em declarações quantiﬁcadas consiste na regra denominada
instanciação existencial. Ela nos permite concluir que existe um elemento c do domínio para o
qual 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 ser
aquele 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 ﬁm, existe a generalização existencial. Por meio dela nós concluímos que ∃xP (x) se houver
um 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 quantiﬁcadas.
Tabela 42: Inferência sobre Declarações Quantiﬁcadas
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

(c) ∴ T (a)∧¬L(a)
(g) ∴ ¬L(a) Simpliﬁcaçã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 Quantiﬁcadas
Nas deduções apresentadas nos exemplos da seção de regras de inferência para declarações quanti-
ﬁcadas observamos o uso das regras de inferência de instanciação e generalização juntamente com
regras de inferência que operam sobre proposições.
Em especial, a combinação de regra de generalização universal de declarações quantiﬁcadas e modus
ponens de proposições são usadas frequentemente em deduções. Devido a este fato, esta combinação
possui 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, (n
2
< 2
n
)’ é uma aﬁrmação
verdadeira. Mostre que 100
2
< 2
100
.
Sejam as propriedades P (x) : n > 4 e Q(x) : n
2
< 2
n
. As premissas da aﬁrmação acima podem ser
formalizadas na seguinte sentença ∀x∈ Z(P (x) → Q(x)). Assuma que tal sentença seja verdadeira.
Idetiﬁcaçã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 gerar
a regra de inferência modus tollens universal para combinações de declarações quantiﬁcadas e
proposiçõ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 de
aula. 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 que
forem 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) 2
n≥ 100.
Exercício 3. Dê a negação das seguintes proposições:
(a) Jeniﬀer 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 Jeniﬀer.
Exercício 4. Sejam p, q e r as proposições:
p: ‘Você ﬁca gripado’
q : ‘Você perde a prova ﬁnal’
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∧···∧ p
n−1∧ p
n
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áﬁcos 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 veriﬁcar as equivalências a seguir. Nos casos em que se
tratarem de equivalências famosas, identiﬁque-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 ou
contingê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ão
o 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á executado
mais rápido e terá mais linhas de código’.
Exercício 13. Seja P (x) a função proposicional que declara que x = x
2
. Se o domínio consiste no
conjunto 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 quantiﬁcadores, 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 ﬁlmes 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(x
2
= 2)
60

(b) ∃x∈ Z(x
2
= 2)
(c) ∀x∈ R(x
2
+ 2 ≥ 1)
(d) ∃x ∈ R(x
2
= −1)
(e) ∃x∈ C(x
2
= −1)
(f) ∀x ∈ R(x
2= x)
Exercício 17. Determinar o valor lógico das sentenças quantiﬁcadas, 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(x
2
+x = 6), com D = {1,2,3}
Exercício 18. Reescrever cada uma das declarações abaixo, negando-as. Determine o valor verdade
da negação.
(a) ∃x ∈ R(x
2
= 2)
(b) ∃x∈ Z(x
2
= 2)
(c) ∀x∈ R(x
2
+ 2 ≥ 1)
(d) ∃x ∈ R(x
2
= −1)
(e) ∃x∈ C(x
2
= −1)
(f) ∀x ∈ R(x
2= 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(x
2
+ 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 aﬁrmações dadas a seguir, assinale a declaração correta que
representa a negação da declaração srcinal:
(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 é o
conjunto 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 quantiﬁcadores 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(x
2
= y)
(g) ∀x(x
2
> 0)
(h) ∃x∀y(y = 0 → xy = 1)
(i) ∀x(x = 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((x
2
= 1) → (x = 0))
(f) ∃x((x
2
= 1)∧(x < 0))
Exercício 25. Dê a negação das seguintes sentenças quantiﬁcadas:
(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 = 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≤ y
2
) quando o conjunto domínio
das 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 do
uso das equivalências lógicas apresentadas neste documento. Caso alguma equivalência lógica sobre
proposições condicionais seja necessária, pesquisar e completar o exercício.
Exercício 27. Veriﬁque 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 desconto
diminuirá ou o comércio interno não irá aumentar.’
(b) ‘A colheita é boa, mas não há água suﬁciente. Se tivéssemos bastante água ou não tivesse
bastante sol, então haveria água suﬁciente. 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ão
estava na cidade. Se ocorreu um crime, o sr. Krasov estava na cidade. Logo, José não pegou as
joias’.
(d) ‘Se o produto for conﬁável, a parcela de mercado irá aumentar. Ou o produto é conﬁável, ou os
custos irão subir. A parcela de mercado não irá aumentar. Portanto, os custos irão subir.’
Exercício 28. Identiﬁque 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 eu
responder todos os exercícios, eu irei entender todo o material. Assim, se eu trabalhar a noite toda
neste dever de casa, então eu entenderei o material.
(c) Steve trabalhará em uma companhia de computadores neste verão. Logo, Steve trabalhará em
uma 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ência
dadas a seguir:
(a)
p → q
q → r
∴ p → r
(b)
p∧q
∴ p
(c)
p∨q
¬ p∨r
∴ q ∨r
(d)
p
∨
q
¬q
∴ p
(e)
¬q
p → 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 a
demonstraçã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 a
loteria’.
(b) ‘Se eu comer comida apimentada, então eu terei pesadelos. Eu tenho pesadelos se trovejar
enquanto 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. Estava
ensolarado 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 verdade
sobre as premissas levam à conclusão.
(a) ‘Cada um dos 93 estudantes desta classe possuem um computador pessoal. Todo mundo que
possui um computador pessoal pode usar um editor de textos. Assim, Zeke, um estudante desta
classe, 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 um
conversível vermelho tomou pelo menos uma multa por velocidade. Portanto, alguém que estuda
neste curso tomou uma multa por velocidade’.
64

Exercício 33. Derive u das seguintes premissas:
p → (q ∧r)
(q ∧r) → s
s → (t∨(¬t → u))
p
¬t
Exercício 34. Derive (r∧s) das seguintes premissas:
¬¬ p
q → (r∧s)
t → ¬¬q
t∨¬ p
Exercício 35. Derive ( p∨q )∧( p∧r) das seguintes premissas:
( p∨q ) → r
r∧ p
Exercício 36. Aplique regras de inferência sobre as sentenças abaixo para mostrar que a verdade
sobre 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, se
a 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 torno
do sol, então, se a Lua gira em torno da Terra, ou Ptomoleu ou Copérnico tinham razão. Copérnico
tinha razão se Ptolomeu não tinha razão. Nem Ptolomeu nem Copérnico tinham razão. Logo, a
Lua não gira em torno da Terra.
Exercício 37. Traduza os argumentos na forma de argumento correspondente, e determine sua
validade. 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 é um
papagaio. 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 tem
bom 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 sua
validade. 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ão
cor-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 mais
perigosos 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 ﬂores-do-campo. Logo, pessoas românticas gostam de ﬂores-do-
campo. Notação: P : x é uma pessoa romântica, L: x é inspirado pela Lua, R: x gosta de rosas,
F : x gosta de ﬂores-do-campo.
Referências
[Rosen, K. H.] Matemática Discreta e suas Aplicações, Tradução da 6a. Edição em Inglês. Editora
Mc-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. Editora
LTC. ISBN: 978-85-216-1422-7
[Menezes, P. B.] Matemática Discreta para Computação e Informática, 2a. Edição. Editora Sagra
Luzzatto.
[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 em
www.dcc.ufmg.br/~loureiro/md/md_0Introducao.pdf. Acessado em Set/2012.
[Menezes, P. B.] Slides sobre matemática discreta. Disponível em
ftp://ftp.inf.ufrgs.br/pub/blauth/Discretas/Mat_Discreta2.pdf. Acessado em
Set/2012.
66

Apostila lógica matemática

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Apostila lógica matemática

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 44

Slide 45

Slide 46

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Pray For The Peace Of Jerusalem and You Will Prosper

Don_t_Waste_Your_Life_God.....powerpoint

VILLASUR_FACTORS_TO_CONSIDER_IN_PLATING_SALAD_10-13.pdf

Fertility awareness methods for women in the society

Chapter 5 Arithmetic Functions Computer Organisation and Architecture

syakira bhasa inggris (1) (1).pptx.......