001 CAP1

Prévia do material em texto

Caṕıtulo 1
Introdução à Matemática Discreta e
Lógica Formal
Edmilson Marmo Moreira
Universidade Federal de Itajubá - UNIFEI
Instituto de Engenharia de Sistemas e Tecnologias da Informação - IESTI
“A maravilhosa disposição e harmonia do universo só pode ter tido origem segundo
o plano de um Ser que tudo sabe e tudo pode. Isto fica sendo a minha última e
mais elevada descoberta”.
Isaac Newton
1 Considerações Iniciais
Este curso tem por objetivo apresentar os principais conceitos da Matemática Dis-
creta. Praticamente qualquer estudo em Computação e Informática, teórico ou aplicado,
exige como pré-requisito conhecimentos de diversos tópicos de matemática. Tal fato é
normalmente explicitado na maioria dos livros de Computação e Informática, sendo que
alguns possuem um caṕıtulo espećıfico no qual tais tópicos são brevemente ou resumida-
mente introduzidos (MENEZES, 2005).
As Diretrizes Curriculares do MEC para cursos de Computação e Informática afirmam
que: “a matemática, para a área da computação, deve ser vista como uma ferramenta
a ser usada na definição formal de conceitos computacionais (linguagens, autômatos,
métodos etc). Os modelos formais permitem definir suas propriedades e dimensionar suas
instâncias, dadas suas condições de contorno” (MEC, 2005).
Neste contexto, o aluno, acompanhando satisfatoriamente o conteúdo deste curso, irá:
1. Desenvolver a sua capacidade de ler, compreender e construir argumentos matemá-
ticos;
2. Obter uma visão abrangente de uma parte significativa da Computação e Informá-
tica;
3. Estudar como trabalhar com estruturas discretas, que são estruturas matemáticas
abstratas, usadas para representar objetos discretos e o relacionamento entre estes
1
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 2
objetos. Estas estruturas incluem conjuntos, permutações, relações, grafos, árvores
e máquinas de estado finito.
4. Aplicar os conceitos básicos da Matemática Discreta como uma ferramenta mate-
mática para investigações e aplicações precisas em Computação e Informática;
5. Abordar problemas aplicados e enfrentar com naturalidade novas tecnologias.
2 O que é Matemática Discreta?
A matemática discreta é a parte da matemática devotada ao estudo dos objetos
discretos. O sentido da palavra discreta está relacionado à elementos distintos não conec-
tados (ROSEN, 2003).
Os tipos de problemas que são resolvidos usando a matemática discreta incluem:
• Quantas formas existem para escolher uma password em um sistema computacional?
• Qual a probabilidade de se ganhar na loteria?
• Existe um link entre dois computadores numa rede?
• Qual é o menor caminho entre duas cidades usando um determinado sistema de
transporte?
• Como pode ser classificado uma lista de números inteiros em ordem crescente?
• Quantos passos são necessários para fazer esta ordenação?
• Como pode ser provado que um algoritmo de ordenação faz seu trabalho correta-
mente?
• Como pode ser projetado um circuito que adiciona dois inteiros?
• Quantos endereços válidos existem na Internet?
A matemática discreta possui técnicas necessárias para resolver estes tipos de proble-
mas.
De forma geral, a matemática discreta é usada sempre que objetos são contados,
quando relacionamentos entre conjuntos são estudados e quando processos envolvendo
um número finito de passos são analisados. Neste contexto, segundo Hunter (2011), ela
pode ser dividida em torno de cinco tipos de pensamentos matemáticos:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 3
• lógico;
• relacional;
• recursivo;
• quantitativo; e
• anaĺıtico.
Durante este curso, cada item destes será desenvolvido e aprofundado.
A principal razão para o crescimento da importância da matemática discreta é que
as informações são armazenadas e manipuladas em computadores em uma forma discreta
(ROSEN, 2003).
Este caṕıtulo apresenta algumas das noções fundamentais de lógica simbólica. Os
prinćıpios da lógica muitas vezes são úteis para o entendimento do significado preciso dos
enunciados e também ajudam no desenvolvimento de importantes métodos de racioćınio.
Embora a lógica simbólica não seja usada explicitamente nos caṕıtulos subsequentes, o seu
estudo dá o embasamento necessário para compreender as pedras angulares da matemática
que são: as definições, os teoremas e as provas. As definições especificam com precisão
os conceitos do foco de interesse, os teoremas afirmam exatamente o que é verdadeiro
sobre esses conceitos, e as provas demonstram, de maneira irrefutável, a verdade dessas
asserções.
3 Álgebra de Proposições
Definição 3.1 (Proposição) Proposição é uma Sentença que pode ser significativamente
classificada como verdadeira ou falsa.
Exemplos:
1. Duzentos é igual a cinquenta.
2. Existem formas de vida em outros planetas do universo.
3. A Terra é redonda.
A validade ou falsidade de uma proposição é chamada de seu valor verdade.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 4
Algumas proposições são compostas, isto é, compõem-se de subproposições e vários
conectivos.
Exemplos:
1. As rosas são vermelhas e as violetas são azuis.
2. Carlos está doente ou velho.
3. Hoje irá chover ou não irá chover.
Uma propriedade fundamental de uma proposição composta é que seu valor verdadeiro
é completamente determinado pelo valor verdade de cada uma das subproposições e pelo
modo pelo qual estão ligadas para formar uma proposição completa.
As proposições serão designadas por letras minúsculas, com ou sem ı́ndices inferiores.
3.1 Conjunção
Duas proposições quaisquer podem ser combinadas pela palavra “e” para formar uma
proposição composta, chamada de conjunção das proposições originais.
Definição 3.2 (Conjunção) Sejam p e q proposições. Então, a proposição composta “p
e q” chama-se conjunção de p e q. Usa-se o śımbolo p ∧ q para representar a conjunção
p e q, que são os fatores da expressão. O valor verdade de p ∧ q será verdadeiro se
ambos fatores forem verdade; caso contrário, o valor verdade de p ∧ q será falso.
Exemplo:
1. Seja p “Está chovendo” e seja q “O Sol está brilhando”. Assim, p ∧ q corresponde à
proposição “Está chovendo e o Sol está brilhando”.
Um meio conveniente de estabelecer o valor verdade de uma proposição composta
é através de uma representação esquemática denominada tabela-verdade. A tabela
seguinte representa a proposição p ∧ q:
p q p ∧ q
V V V
V F F
F V F
F F F
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 5
3.2 Disjunção
Duas proposições quaisquer também podem ser combinadas pela palavra “ou” para
formar uma proposição composta, chamada de disjunção das proposições originais.
Definição 3.3 (Disjunção) Sejam p e q proposições. Então, a proposição composta “p
ou q” denomina-se disjunção de p e q e escreve-se, simbolicamente, p∨q. O valor verdade
da proposição p∨q satisfaz a seguinte propriedade: se p é verdadeiro ou se q é verdadeiro,
ou ambos são verdadeiros, então p ∨ q será verdadeiro; caso contrário, p ∨ q será falso.
Exemplo:
1. Seja p “Pedro estudou inglês na universidade” e seja q “Pedro morou nos Estados
Unidos”. Assim, p ∨ q corresponde à proposição “Pedro estudou inglês na universi-
dade ou morou nos Estados Unidos”.
A seguir a tabela-verdade de p ∨ q:
p q p ∨ q
V V V
V F V
F V V
F F F
A disjunção é também denominada disjunção inclusiva, visto ser necessário que
apenas uma das proposições seja verdadeira para que a proposição composta resultante
seja verdade. Há, porém, uma variação deste operador denominada disjunção exclusiva.
Definição 3.4 (Disjunção exclusiva) Sejam p e q proposições. Então a proposição
composta “p ou exclusivo q” denomina-se disjunção exclusiva de p e q e escreve-se, sim-
bolicamente, p Y q. Nadisjunção exclusiva, se p é verdadeiro ou se q é verdadeiro, mas
não ambos, então p Y q será verdadeiro; caso contrário p Y q será falso.
A tabela-verdade seguinte apresenta os valores posśıveis de p Y q:
p q p Y q
V V F
V F V
F V V
F F F
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 6
3.3 Condicional
Muitas proposições, especialmente em matemática, são da forma “Se p então q”. Tais
proposições são chamadas proposições condicionais ou implicações.
Definição 3.5 (Condicional) Sejam p e q proposições. Então a proposição composta
“se p, então q” é chamada uma implicação ou proposição condicional e representa-se sim-
bolicamente por p→ q. O condicional p→ q é verdadeiro a menos que p seja verdadeiro
e q seja falso.
Em outras palavras, a definição do condicional p→ q estabelece que uma proposição
verdadeira não pode implicar numa proposição falsa. O condicional p→ q também pode
ser lido como:
• p implica em q;
• p somente se q;
• p é suficiente para q;
• q é necessário a p.
Exemplo:
1. A proposição “Fogo é uma condição necessária para fumaça” pode ser reformulada
como “Se há fumaça, então há fogo”. O antecedente é “há fumaça”, e o consequente
é “há fogo”.
O condicional p→ q também pode ser expresso na forma de uma tabela-verdade:
p q p→ q
V V V
V F F
F V V
F F V
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 7
3.4 Bicondicional
Outra proposição comum é da forma “p se, e somente se, q”. Tais proposições são
chamadas proposições bicondicionais e representam os casos em que é desejável considerar
uma implicação e sua rećıproca em conjunto, constituindo uma só proposição.
Definição 3.6 (Bicondicional) Sejam p e q proposições. A proposição “p se, e somente
se, q” chama-se uma proposição bicondicional. É definida como a conjunção das impli-
cações p → q e q → p. Portanto, “p se, e somente se, q” significa (p → q) ∧ (q → p).
Usa-se a notação p↔ q para representar uma proposição bicondicional. Desta forma, se
p e q possuem o mesmo valor, então p↔ q é verdadeiro, caso contrário p↔ q é falso.
Esse conectivo também é conhecido como equivalência.
Exemplo:
1. Seja p“Fogo é uma condição necessária para fumaça”e q“Toda vez que existe fumaça
existe fogo” então p↔ q é “Existe fumaça se, e somente se, existe fogo”.
A seguir a tabela-verdade de p↔ q:
p q p↔ q
V V V
V F F
F V F
F F V
3.5 Negação
Dada uma proposição p qualquer, uma outra proposição, chamada negação de p, pode
ser formada escrevendo-se “É falso que ...” antes de p ou, se posśıvel, inserindo em p a
palavra “não”.
Definição 3.7 (Negação) Seja p uma proposição. Então a proposição “não p” é cha-
mada a negação de p, sendo representada simbolicamente por ∼ p. Assim, se p é verda-
deiro, então ∼ p é falso; caso contrário, ∼ p é verdadeiro.
Exemplo:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 8
1. Seja p “Paris está na França” então ∼ p pode ser escrita como: “É falso que Paris
esteja na França” ou “Paris não está na França”.
Por se tratar de um operador unário, a tabela-verdade de ∼ p possui apenas 2 linhas:
p ∼ p
V F
F V
4 Fórmulas Bem Formadas
Pode-se encadear sentenças, seus conectivos e os parênteses (ou colchetes) para obter
novas expressões, tal como: (p→ q) ∨ (q → p). Naturalmente existem algumas regras de
sintaxe (regras sob as quais as cadeias são válidas). Por exemplo, “∨∧ → pq” não deve
ser considerada uma cadeia válida. Expressões que formam cadeias válidas são chamadas
de fórmulas bem formadas ou wffs (well-formed-formulas).
As well-formed-formulas da linguagem Lógica Proposicional são constrúıdas, de forma
indutiva, conforme as regras a seguir:
• todo śımbolo de verdade é uma fórmula;
• todo śımbolo proposicional é uma fórmula;
• se H é uma fórmula, então (∼ H), a negação de H, é uma fórmula;
• se H e G são fórmulas, então a disjunção de H e G, dada por (H ∧ G), é uma
fórmula;
• se H e G são fórmulas, então a conjunção de H e G, dada por (H ∨ G), é uma
fórmula;
• se H e G são fórmulas, então a implicação de H e G, dada por (H → G), é uma
fórmula;
• se H e G são fórmulas, então a bi-implicação de H e G, dada por (H ↔ G), é uma
fórmula.
Para reduzir o número de parênteses necessários em uma wff, estipula-se uma ordem
na qual os conectivos são aplicados. Esta ordem de precedência é:
1. Conectivos dentro de parênteses, dos mais internos para os mais externos
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 9
2. ∼
3. ∧
4. ∨
5. →
6. ↔
Isso significa que a expressão p∨ ∼ q significa p∨(∼ q) e não ∼ (p∨q). Analogamente,
p ∨ q → r significa (p ∨ q)→ r e não p ∨ (q → r).
É evidente que nem todos os conectivos apresentados para definir as wffs do cálculo
proposicional são necessários, uma vez que proposições contendo os śımbolos → e ↔
podem ser substitúıdas por expressões equivalentes usando apenas os śımbolos ∨, ∧ e
∼. Neste contexto, um conjunto de conectivos lógicos diz-se completo se toda a wff do
cálculo proposicional é equivalente a uma wff onde figuram apenas conectivos do conjunto
{∼,∨,∧,→,↔}, que é, por definição, também completo.
5 Tautologias e Contradições
Uma wff, cujos valores verdade são sempre verdadeiros, é chamada tautologia. Uma
wff, cujos valores verdade são sempre falsos, é chamada contradição.
Quando uma wff composta na forma P ↔ Q é uma tautologia, os valores-verdade de
P e Q conferem para todas as colunas da tabela-verdade. Neste caso, P e Q são chamadas
de wff equivalentes e denotadas por P ≡ Q (o śımbolo ⇔ também pode ser usado para
representar esta equivalência: P ⇔ Q).
Frequentemente, ocorre o fato de uma proposição ser enunciada de tal modo que
fica dif́ıcil determinar seu significado na forma em que se apresenta. Nestas situações,
é conveniente encontrar um outro enunciado “equivalente” da proposição, que seja mais
facilmente compreenśıvel.
Definição 5.1 (Proposições equivalentes) Duas proposições se dizem equivalentes se
têm os mesmos valores verdade em todos os casos posśıveis. Usa-se a notação P ≡ Q
para indicar o fato de P e Q serem equivalentes.
Exemplos:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 10
1. As equivalências da tabela seguinte representam algumas leis fundamentais:
Propriedades Equivalências
Comutativas: p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p
Associativas: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributivas: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
de Identidade: p ∨ F ≡ p p ∧ V ≡ p
Complementares: p∨ ∼ p ≡ V p∧ ∼ p ≡ F
Idempotentes: p ∨ p ≡ p p ∧ p ≡ p
Leis de De Morgan: ∼ (p ∨ q) ≡∼ p∧ ∼ q ∼ (p ∧ q) ≡∼ p∨ ∼ q
Dupla Negação: ∼∼ p ≡ p
2. Outras equivalências relevantes:
Nome Equivalência
Implicação: (p→ q) ≡∼ p ∨ q
Contraposição: (p→ q) ≡ (∼ q →∼ p)
Prova condicional: p→ (q → r) ≡ (p ∧ q)→ r
6 Argumentos Válidos
Um argumento é uma coleção finita A1, A2, . . . , An de proposições (simples ou com-
postas), seguidas por uma proposição A. Denota-se um argumento pela notação:
A1, A2, . . . , An ∴ A
Cada uma das proposições A1, A2, . . . , An é chamada uma premissa do argumento e
a proposição A é chamada de conclusão do argumento. Esta definição é geral e não exige
que as premissas sejam verdadeiras. Obviamente, na prática o interesse é por premissas
que possuam valor verdade verdadeiro.
Definição 6.1 (Argumento válido) Denomina-se argumento válido toda a sequência
de proposições A1, A2, . . . , An na qual sempre que as premissas são verdadeiras a conclusão
também é verdadeira e, tal que, a conjunção das premissas implica a conclusão, isto é:
(A1 ∧ A2 ∧ . . . ∧ An) ∴ A
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 11
De certa forma, como em qualquer argumento, o que está em questão não é a verdade
ou falsidadedas premissas, mas a validade da inferência. Uma vez admitida a verdade das
premissas, necessariamente, as conclusões serão verdadeiras, desde que suas demonstrações
sejam todas argumentos válidos.
Para testar a validade de um argumento, procede-se da seguinte forma:
1. Constrói-se a tabela-verdade de A1 ∧ A2 ∧ . . . ∧ An
2. Constrói-se a tabela-verdade de A
3. Comparam-se as tabelas, se na mesma linha ocorrer V F (nesta ordem), não há
implicação e o argumento é falho; caso contrário, haverá implicação e o argumento
é válido.
Exemplo:
1. Considerando o argumento: p → q, p ∴ q. Para decidir se o argumento é válido
basta proceder conforme o critério já estabelecido, ou seja, constrói-se a tabela-
verdade das premissas e da conclusão verificando se existe implicação em cada linha
da tabela:
p q p→ q (p→ q) ∧ p p→ q, p ∴ q
V V V V V
V F F F V
F V V F V
F F V F V
Como pode ser observado na tabela, não existem V e F nas colunas [(p→ q)∧ p] e q,
respectivamente nesta ordem. Desta forma, o argumento é uma tautologia e, portanto, é
válido.
Um exemplo deste tipo de argumento é:
• Se hoje é sábado, então eu não preciso ir à escola.
• Hoje é sábado
• Conseqüentemente: eu não vou à escola.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 12
7 Regras de Dedução para a Lógica Proposicional
As regras de dedução para a lógica proposicional são basicamente de dois tipos, equi-
valências e inferências. As regras de equivalência permitem que wffs individuais sejam
reescritas mantendo o mesmo valor lógico, enquanto as regras de inferência permitem a
dedução de novas wffs a partir de wffs anteriores na sequência de demonstração.
Como já foi apresentado, as regras de equivalência dizem que se determinados pares
de wffs são equivalentes, ou seja, se P ≡ Q, então P ↔ Q é uma tautologia e, além disso,
a proposição P pode ser substitúıda pela proposição Q em qualquer wff sem mudança do
seu valor lógico. As regras de equivalência, portanto, preservam os valores lógicos.
7.1 Regras de Inferência
A utilização de tabelas-verdades possibilita a validação de qualquer tipo de argumento.
Entretanto, conforme o número de variáveis aumenta, o uso de tabelas-verdade se torna
impraticável. Por exemplo, para a validação de um argumento de 6 variáveis, o que é
bastante comum, seria necessário construir uma tabela verdade com 64 linhas, ou seja
26 combinações. Um método mais eficiente para demonstrar, verificar ou testar a
validade de um dado argumento, consiste em deduzir a conclusão A a partir das premissas
A1, A2, . . . , An, mediante o uso de certas regras de inferência. Desta forma, a inferência
é o processo pelo qual se chega a uma proposição com base em outras proposições aceitas
como ponto de partida do processo.
Ao contrário das regras de equivalência, as regras de inferência não funcionam em
ambas as direções, pois equivalem a uma expressão condicional. Apesar disso, as regras
de inferência preservam os valores lógicos. Por exemplo, seja o argumento P → Q,P ∴ Q
e supondo que P e P → Q sejam ambas wff verdadeiras em uma sequência de demons-
tração. Então, Q é dedut́ıvel dessas duas wffs pela regra de inferência conhecida como
modus ponens. Se P e P → Q são ambas verdadeiras, então, pela tabela-verdade para o
condicional, Q também é verdadeira.
As regras de dedução representam receitas para transformar wffs. Uma regra só pode
ser aplicada quando a wff tiver exatamente a forma descrita na regra.
A seguir algumas das principais regras de inferência:
1. União: p, q ∴ p ∧ q
2. Adição: p ∴ p ∨ q
3. Modus ponens: (p→ q), p ∴ q
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 13
4. Modus tollens: (p→ q),∼ q ∴∼ p
5. Simplificação: p ∧ q ∴ p
6. Silogismo hipotético: (p→ q), (q → r) ∴ (p→ r)
7. Silogismo disjuntivo: (p ∨ q),∼ p ∴ q
8. Dilema construtivo: (p→ q), (r → s), (p ∨ r) ∴ (q ∨ s)
9. Dilema destrutivo: (p→ q), (r → s), (∼ q∨ ∼ s) ∴ (∼ p∨ ∼ r)
10. Absorção: p→ q ∴ p→ (p ∧ q)
11. Simplificação disjuntiva: (p ∨ q), (p∨ ∼ q) ∴ p
7.2 Técnicas Dedutivas - Prova Direta
Diz-se que uma proposição A é formalmente dedut́ıvel (consequência) de certas pro-
posições dadas (premissas) quando, e somente quando, for posśıvel formar uma sequência
de proposições A1, A2, . . . , An de tal modo que:
1. An é exatamente A;
2. Para qualquer valor de i (i = 1, 2, 3, . . . , n), Ai ou é uma das premissas ou constitui a
conclusão de um argumento válido formado a partir das proposições que a precedem
na sequência.
A proposição A no caso de ser formalmente dedut́ıvel é denominada teorema e a
sequência formada chama-se prova ou demonstração do teorema.
Exemplos:
1. Provar ∼ s dadas as premissas: t, t→∼ q,∼ q →∼ s
Demonstração:
1. t Premissa
2. t→∼ q Premissa
3. ∼ q →∼ s Premissa
4. ∼ q Modus ponens, 1 e 2
5. ∼ s Modus ponens, 3 e 4
c.q.d.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 14
2. Provar r∨ ∼ s dadas as premissas: s ∧ q, t→∼ q,∼ t→ r
Demonstração:
1. s ∧ q Premissa
2. t→∼ q Premissa
3. ∼ t→ r Premissa
4. q Simplificação, 1
5. ∼ (∼ q) Dupla negação, 4
6. ∼ t Modus tollens, 2 e 5
7. r Modus ponens, 3 e 6
8. r∨ ∼ s Adição, 7
c.q.d.
7.3 Prova Condicional
Uma prova condicional surge quando se deseja provar α → β dada as premissas
A1, A2, . . . , An. Fazendo a conjunção das premissas igual a A, trata-se de mostrar que é
válido o argumento: A ∴ α→ β.
A forma de se construir uma prova condicional surge do prinćıpio da exportação.
Para se mostrar este prinćıpio utiliza-se a equivalência notável: p → q ≡∼ p ∨ q. Então,
tem-se:
A→ (α→ β) ≡ ∼ A ∨ (α→ β) ≡
∼ A ∨ (∼ α ∨ β) ≡ (∼ A∨ ∼ α) ∨ β ≡
∼ (A ∧ α) ∨ β ≡ (A ∧ α)→ β
Portanto, se (A ∧ α) → β for uma tautologia, isto é, se A ∧ α ∴ β, ou seja, se for
posśıvel deduzir β de A ∧ α, também será uma tautologia a proposição equivalente e,
portanto, A ∴ (α→ β) é dedut́ıvel de A.
Dessas considerações, segue-se a Técnica da Prova Condicional: para demonstrar
a validade do argumento cuja conclusão tem forma condicional α → β, introduz-se α
como premissa provisória e deduz-se β.
Exemplos:
1. Provar r →∼ p dadas as premissas: p→ q, r →∼ q
Demonstração:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 15
1. p→ q Premissa
2. r →∼ q Premissa
3. r Premissa provisória
4. ∼ q Modus ponens, 2 e 3
5. ∼ p Modus tollens, 1 e 4
6. r →∼ p Prova condicional, 3 e 5
c.q.d.
2. Provar a→ b dadas as premissas: a ∨ j → g, j → (∼ g∧ ∼ h), j ∨ b
Demonstração:
1. a ∨ j → g Premissa
2. j → (∼ g∧ ∼ h) Premissa
3. j ∨ b Premissa
4. a Premissa provisória
5. a ∨ j Adição, 4
6. g Modus ponens, 1 e 5
7. j →∼ (g ∨ h) Equivalência, 2
8. g ∨ h Adição, 6
9. ∼ [∼ (g ∨ h)] Dupla negação, 8
10. ∼ j Modus tollens, 7 e 9
11. b Silogismo disjuntivo, 3 e 10
12. a→ b Prova condicional, 4 e 11
c.q.d.
7.4 Prova Bicondicional
A prova de um argumento cuja conclusão é uma proposição da forma bicondicional
α ↔ β é semelhante a prova condicional, com a diferença de que é feita em duas partes
distintas. Então, dada uma proposição α ↔ β, primeiro prova-se α → β e, a seguir,
prova-se β → α, concluindo-se pela validade do argumento.
Exemplo:
1. Provar a↔ v dadas as premissas: t→ a, v → t, a→ m, v∨ ∼ m
Demonstração:
1a Parte:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 16
1. t→ a Premissa
2. v → t Premissa
3. a→ m Premissa
4. v∨ ∼ m Premissa
5. a Premissa provisória
6. m Modus ponens, 3 e 5
7. v Silogismo disjuntivo, 4 e 6
8. a→ v Prova condicional, 5 e 7
2a Parte:
1. t→ a Premissa
2. v → t Premissa
3. a→ m Premissa
4. v∨ ∼ m Premissa
9. v Premissa provisória
10. t Modus ponens, 2 e 5
11. a Modus ponens, 1 e 6
12. v → a Prova condicional, 5 e 7
Conclusão:
13. (a→ v) ∧ (v → a) União, 8 e 12
14. a↔ v Premissa
c.q.d.
7.5 Prova Indireta ou Por Redução ao Absurdo
A partir de uma contradição pode-sededuzir qualquer proposição. Ou seja, a partir
da contradição p∧ ∼ p pode-se deduzir uma proposiçao α qualquer:
p∧ ∼ p ∴ α
De fato: p∧ ∼ p ≡ F
1. p∧ ∼ p Premissa
2. p Simplificação, 1
3. ∼ p Simplificação, 1
4. p ∨ α Adição, 2
5. α Silogismo disjuntivo, 3 e 4
c.q.d.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 17
Seja, agora, provar α a partir das premissas A1, A2, . . . , An, sequência essa que será
denominada A. A partir das premissas A e ∼ α procura-se deduzir α a partir delas, isto
é, verifica-se se A∧ ∼ α ∴ α.
Pelo prinćıpio da exportação, tem-se:
A∧ ∼ α→ α ≡ A→ (∼ α→ α)
Esta última proposição consitui-se uma tautologia se ocorrer a seguinte implicação:
A⇒ (∼ α→ α), isto é, A ∴∼ α→ α
∼ α→ α ≡∼ (∼ α) ∨ α ≡ α ∨ α ≡ α
∴ A⇒ α e A∧ ∼ α⇒ α
Exemplos:
1. Provar r dadas as premissas: ∼ p→ r,∼ r → q,∼ (p ∧ q)
Demonstração:
1. ∼ p→ r Premissa
2. ∼ r → q Premissa
3. ∼ (p ∧ q) Premissa
4. ∼ r Premissa provisória
5. q Modus ponens, 2 e 4
6. ∼ p∨ ∼ q De Morgan, 3
7. ∼ (∼ q) Dupla negação, 5
8. ∼ p Silogismo disjuntivo, 6 e 7
9. r Moduns ponens, 1 e 8
10. (r∧ ∼ r) União, 4 e 9
11. r Prova indireta, 4 a 10
c.q.d.
Observação: da mesma forma como encontrou-se a contradição (r∧ ∼ r) para provar
r, pode-se encontrar a contradiação (q∧ ∼ q) para provar ∼ p, ou seja, a contradição
procurada pode envolver ou não a mesma variável da proposição a ser provada.
2. Provar ∼ p dadas as premissas: ∼ q ∨ r, p→∼ r, q
Demonstração:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 18
1. ∼ q ∨ r Premissa
2. p→∼ r Premissa
3. q Premissa
4. ∼ (∼ p) Premissa provisória
5. p Dupla negação, 4
6. ∼ r Modus ponens, 2 e 5
7. ∼ q Silogismo disjuntivo, 1 e 6
8. q∧ ∼ q União, 3 e 7
9. ∼ p Prova indireta, 8
c.q.d.
8 Quantificadores
O que pode ser expresso através das wffs das seções anteriores é muito limitado. Por
exemplo, considerando a sentença “Para todo x, x > 0” como uma sentença verdadeira
sobre inteiros positivos, ela não pode ser simbolizada adequadamente através de śımbolos
proposicionais, parênteses e conectivos lógicos.
Exemplos:
1. p : 3 + 5 ≤ 11, V (p) = V
2. q : x+ 5 ≤ 11, V (q) =?
Nos exemplos anteriores, a proposição p é verdadeira, ao passo que nada pode ser
afirmado sobre o valor lógico na proposição q, que somente será conhecido quando x for
identificado. Neste caso, diz-se que a proposição q é uma sentença aberta ou função
proposicional. Nas sentenças abertas, os śımbolos x, y, entre outros, são chamados
variáveis.
Definição 8.1 (Conjunto Universal) Chama-se conjunto universal (da variável) ao
conjunto das possibilidades lógicas que podem substituir a variável na sentença, sendo
denotado por U.
Cada elemento de U chama-se valor da variável. U às vezes é tacitamente imposto
pelo contexto, mas pode também ser escolhido pelo agente de estudo em questão.
Exemplos:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 19
1. Seja a sentença aberta: x + 5 ≤ 11. Pode-se impor que o conjunto universo da
variável seja N ou Z ou Q ou R ou o conjunto U = {1, 3, 5, 7, . . .}
2. Seja a sentença aberta: “O planeta x é o maior planeta do Sistema Solar”. O conjunto
universo da variável x é, pelo contexto, dado pelo conjunto dos planetas conhecidos
do Sistema Solar: U = {Mercúrio, Vênus, Terra, Marte, Júpiter, Saturno, Urano,
Netuno}.
Além da definição de conjunto universal, outra definição importante é a de conjunto
verdade.
Definição 8.2 (Conjunto verdade) Conjunto verdade (da sentença) é o conjunto dos
valores da variável para os quais a sentença é verdadeira. Denota-se este conjunto por V.
Exemplos:
1. Dada a sentença: x+ 5 ≤ 11, x ∈ R, o seu conjunto verdade é V = {x ∈ R | x ≤ 6}.
2. O conjunto verdade da sentença aberta: “O planeta x é o maior planeta do Sistema
Solar” é V = {Júpiter}.
8.1 Quantificador Universal
No exemplo “Para todo x, x > 0” existem dois novos elementos, um quantificador
e um predicado. Os quantificadores são frases como “para todo”, “para cada” ou “para
algum”, que indicam de alguma forma quantos objetos têm uma determinada propriedade.
O quantificador universal é simbolizado por um A de cabeça-para-baixo, ∀, e é lido
“para todo”, “para todos”, “para cada” ou “para qualquer”. Portanto, a sentença “Para
todo x, x > 0” pode ser simbolizada como:
(∀x)(x > 0) ou ∀xx > 0 ou ∀x, x > 0
No primeiro tipo de representação, um quantificador e sua variável são colocados entre
parênteses. O segundo par de parênteses indica que o quantificador age sobre a expressão
interna, que no caso é “x > 0”. A frase “x > 0” descreve a propriedade da variável x, que
é ser positiva. Uma propriedade também é chamada de predicado.
Usa-se a notação P (x) para representar algum predicado não especificado ou pro-
priedade que x possa ter. Portanto, a sentença original é um exemplo da forma mais
geral:
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 20
(∀x)P (x)
O valor verdade da expressão (∀x)P (x) depende do domı́nio dos objetos sob os quais
está sendo interpretada a expressão.
Exemplos:
1. Seja M o conjunto dos seres humanos. Assim, “Todos os seres humanos são mortais”
pode ser escrito da seguinte maneira:
(∀x ∈M)(x é mortal)
2. A proposição (∀n ∈ N)(n + 4 > 3), onde N é o conjunto dos números naturais, é
verdadeira desde que:
{n | n+ 4 > 3} = {0, 1, 2, 3, . . .} = N
3. A proposição (∀ ∈ N)(n+ 2 > 8) é falsa desde que:
{n | n+ 2 > 8} = {7, 8, 9, . . .} 6= N
8.2 Quantificador Existencial
O quantificador existencial é simbolizado por um E espelhado, ∃, e é lido como “existe
um”, “para pelo menos um” ou “para algum”. Portanto, a expressão:
(∃x)(x > 0)
deve ser lida como “existe um x tal que x é maior que zero”.
Exemplos:
1. A proposição (∃ ∈ N)(n+4 < 7) é verdadeira desde que {n | n+4 < 7} = {1, 2} 6= ∅
2. A proposição (∃n)(n+ 6 < 4), é falsa pois {n | n+ 6 < 4} = ∅
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 21
8.3 Negação de Proposições que Contêm Quantificadores
A negação da proposição “Todos os seres humanos são mortais” lê-se “Não é verdade
que todos os seres humanos sejam mortais”; em outras palavras, existe pelo menos um
homem que não é mortal. Simbolicamente, M designa o conjunto dos seres humanos, o
que foi dito anteriormente pode ser escrito da seguinte forma:
∼ (∀x ∈M)(x é mortal) ≡ (∃x ∈M)(x não é mortal)
Além disso, se P (x) designa “x é mortal”, o que foi dito acima pode ser escrito como:
∼ (∀x ∈M)P (x) ≡ (∃x ∈M) ∼ P (x)
Existe um teorema análogo para a negação de uma proposição que contém o quanti-
ficador existencial.
∼ (∀x ∈ A)P (x) ≡ (∃x ∈ A) ∼ P (x)
∼ (∃x ∈M)P (x) ≡ (∀x ∈M) ∼ P (x)
Exemplo:
1. A negação da proposição “Para todos os números naturais n, n+2 > 8” é equivalente
à proposição “Existe um n tal que n+ 2 ≤ 8”. Em outras palavras:
∼ (∀ ∈ N)(n+ 2 > 8) ≡ (∃ ∈ N)(n+ 2 ≤ 8)
8.4 Contra-exemplo
Pelo Teorema de De Morgan ∼ (∀x ∈ A)P (x) ≡ (∃x ∈ A) ∼ P (x). Desse modo,
mostrar que uma proposição (∀x)P (x) é falsa, é equivalente a mostrar que (∃x) ∼ P (x)
é verdadeiro, isto é, que existe um elemento x′ tal que P (x′) é falso. Tal elemento x′ é
chamado de contra-exemplo da proposição (∀x)P (x).
Exemplo:
1. A proposição (∀x ∈ Z)(| x |6= 0) é falsa, pois o número 0 é um contra-exemplo.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 22
8.5 Funções Proposicionais Contendo Mais de Uma Variável
Os predicados vistos até aqui, envolvendo propriedades de uma única variável, são
predicados unários. Eles podem ser binários, quando envolvem propriedades de duas
variáveis; ternários, quando envolvem propriedades de três variáveis; ou, de forma geral,
n-ários, quando envolvem propriedades de n variáveis.
Exemplos:
1. A expressão (∀x)(∃y)Q(x, y) é lida como “para todo x existe um y tal que Q(x, y)”.
Supondo Q(x, y) sendo a propriedade de x < y no domı́niodos números inteiros, isto
indica que, para qualquer inteiro, existe um inteiro ainda maior. O valor verdade
desta expressão é verdadeiro.
2. A expressão (∃x)(∀y)Q(x, y) na mesma propriedade do exemplo anterior indica que
existe um inteiro y que é maior que qualquer inteiro x. O valor verdade desta
expressão é falso.
9 Exerćıcios
1. Determine o verdadeiro valor de cada uma das seguintes proposições compostas:
(a) Se 3 + 2 = 7 então 4 + 4 = 8.
(b) Não é verdade que 2 + 2 = 5 se, e somente se, 4 + 4 = 10.
(c) Paris está na Inglaterra ou Londres está na França.
(d) Não é verdade que 1 + 1 = 3 ou 2 + 1 = 3.
(e) É falso que se Paris está na Inglaterra, então Londres está na França.
2. Qual os valores verdade das seguintes sentenças:
(a) 8 é par ou 6 é ı́mpar.
(b) 8 é par e 6 é ı́mpar.
(c) 8 é ı́mpar ou 6 é ı́mpar.
(d) 8 é ı́mpar e 6 é ı́mpar.
(e) Se 8 é ı́mpar, então 6 é par.
(f) Se 8 é par, então 6 é ı́mpar
(g) Se 8 é ı́mpar, então 6 é par.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 23
(h) Se 8 é ı́mpar e 6 é par, então 8 < 6.
3. Achar a tabela-verdade de cada uma das proposições:
(a) ∼ p ∧ q.
(b) ∼ (p→∼ q).
(c) (p ∧ q)→ (p ∨ q).
(d) ∼ (p ∧ q)∨ ∼ (p↔ q).
(e) [(p→ q) ∧ p]→ q].
(f) p↔ (q → r).
(g) (p∧ ∼ p)→ q.
(h) [p ∧ (q ∨ r)] ∧ [q ∧ (p ∨ r)].
4. Verificar, por tabelas verdade, que a negação de p ∧ q, p ∨ q, p → q e p ↔ q é
logicamente equivalente a, respectivamente, ∼ p∨ ∼ q, ∼ p∧ ∼ q, p∧ ∼ q e p↔∼ q
ou ∼ p↔ q.
5. Use os resultados dos dois últimos exerćıcios para simplificar cada uma das seguintes
proposições:
(a) ∼ (p∨ ∼ q).
(b) ∼ (∼ p→ q).
(c) ∼ (p∧ ∼ q).
(d) ∼ (∼ p∧ ∼ q).
(e) ∼ (∼ p↔ q).
(f) ∼ (∼ p→∼ q).
6. Suponha que se defina um novo conector, denotado por ∗, tal que p ∗ q é verdade
quando q é verdade e p é falso e é falso em todos os outros casos. Construa as
tabelas verdade para:
(a) p ∗ q.
(b) q ∗ p.
(c) (p ∗ q) ∗ p.
7. Verifique se cada uma das seguintes expressões é uma tautologia:
(a) p→ p ∧ q.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 24
(b) p→ p ∨ q.
8. Determinar se a expressão composta (p ∨ q) ∨ [∼ (p ∧ q)] é uma tautologia, uma
contradição ou uma contingência.
9. Simplifique as proposições abaixo, utilizando expressões equivalentes, sem alterar o
valor verdade da expressão:
(a) p ∨ (q∧ ∼ p).
(b) ∼ [p ∨ (q∧ ∼ r)] ∧ q.
(c) ∼ (∼ p∧ ∼ q).
(d) (p ∧ r) ∨ [∼ r ∧ (p ∨ q)].
10. Verificar se ∼ (a↔∼ b) implica tautologicamente as seguintes formas abaixo:
(a) a ∨ b→∼ a
(b) ∼ a↔∼ b ∧ a
(c) a→∼ b∧ ∼ a↔∼ b
(d) ∼ a∧ ∼ b∨ ∼ a→∼ a↔∼ b
11. Prove que p ∧ q logicamente implica em p↔ q.
12. Prove que a operação de disjunção inclusiva pode ser escrita em termos das operações
de conjunção e negação.
13. Prove que a operação condicional se distribui na operação de conjunção.
14. Prove que a operação de disjunção exclusiva pode ser escrita em termos dos três
operadores básicos ∧,∨ e ∼.
15. O sinal proposicional ↓ é chamado de negação conjunta: p ↓ q lê-se “Nem p nem q”.
Pede-se:
(a) Construir uma tabela verdade para p ↓ q
(b) Provar que os três operadores básicos ∧,∨ e ∼ podem ser expressos em termos
do sinal ↓ da seguinte maneira:
i. ∼ p ≡ p ↓ p
ii. p ∧ q ≡ (p ↓ p) ↓ (q ↓ q)
iii. p ∨ q ≡ (p ↓ q) ↓ (p ↓ q)
16. Determinar se cada um dos conjuntos abaixo é um conjunto completo de conectivos:
{∼,∨,∧}, {∼,∧}, {∼,∨}, {∼,→}, {V,→}
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 25
17. Determinar os valores lógicos das proposições abaixo, justificando os casos em que
os dados forem insuficientes:
(a) ∼ p→ (q∨ ∼ r), sabendo que V (r) = F .
(b) (p↔ q) ∨ (q →∼ p), sabendo que V (q) = F .
(c) p ∧ [∼ q → (r ∧ s)], sabendo que V (p) = F .
(d) p→ (q ∧ s), sabendo que V (p) = V .
(e) ∼ p ∨ r)→ (q → s), sabendo que V (q) = F .
(f) (p→ r) ∧ s, sabendo que V (r) = V .
(g) p→ (r ∨ s), sabendo que V (r) = V .
(h) (p ∧ q)↔ r, sabendo que V (q) = V .
(i) [(p→ q) ∧ p]→∼ p, sabendo que V (p) = F .
(j) p→ (∼ q ∧ r), sabendo que V (q) = V e V (r) = V .
18. Prove que o seguinte argumento é válido:
p→∼ q, r → q, r ∴∼ p
19. Provar t dadas as premissas:
p→ q, t∨ ∼ s,∼ s→ p,∼ q
20. Para as premissas dadas determinar uma conclusão apropriada para que o argumento
seja válido:
(a) p→∼ q, q.
(b) p→∼ q, r → q.
(c) p→∼ q,∼ p→ r.
(d) p→∼ q, r → p, q.
21. Justifique as passagens nas deduções abaixo:
(a)
1. (r →∼ t) ∧ (s→ r) Premissa
2. s Premissa
3. s→ r
4. r
5. r →∼ t
6. ∼ t
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 26
(b)
1. ∼ s→ a ∧ b Premissa
2. ∼ c∧ ∼ s Premissa
3. ∼ m→∼ b Premissa
4. m ∧ a→∼ e Premissa
5. ∼ s
6. a ∧ b
7. b
8. m
9. a
10. m ∧ a
11. ∼ e
(c)
1. s ∨ t Premissa
2. a→ b Premissa
3. (a→ x)→∼ s Premissa
4. b→ x Premissa
5. a→ x
6. ∼ s
7. t
8. t∧ ∼ s
(d)
1. b→ c Premissa
2. ∼ d ∧ g Premissa
3. a→ d Premissa
4. a ∨ b Premissa
5. c ∨ d
6. ∼ d
7. c
8. c ∧ a ∨ b
(e)
1. z Premissa
2. k → (z → y) Premissa
3. ∼ x ∨ k Premissa
4. x
5. k
6. z → y
7. y
8. x→ y
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 27
(f)
1. c→∼ f Premissa
2. a→ d ∧ f Premissa
3. ∼ d∨ ∼ b Premissa
4. a
5. d ∧ f
6. d
7. ∼ b
8. f ∧ d
9. f
10. ∼ c
11. ∼ b∧ ∼ c
12. ∼ (b ∨ c)
13. a→∼ (b ∨ c)
22. Demonstrar que os argumentos abaixo são válidos:
(a) (a ∧ b)→ (a→ (d ∧ e)), (a ∧ b) ∧ c ∴ e
(b) e→∼ f ∧ g,∼ (b ∧ c)→ f, e, b→ a ∧ h ∴ a
(c) (a→ b) ∧ (c→ d), (f → b) ∧ (b→ m), b→ c, ((a→ d) ∧ (f → m))→ a ∨ f ∴
d ∨m
(d) a→ b, c→∼ b ∴ c→∼ a
(e) ∼ d ∨ a, b, a→ (b→ c) ∴ d→ c
23. Provar os argumentos abaixo, utilizando a técnica da redução ao absurdo:
(a) a→ b, c∨ ∼ b,∼ (a ∧ c) ∴∼ a
(b) a→∼ b, e→∼ a, b ∨ e ∴∼ a
(c) b→ c↔∼ d,∼ d→ b,∼ c→∼ d ∴ c
(d) a→ e ∨ f, e→∼ a, c→∼ f ∴∼ (a ∧ c)
24. Determine o valor verdade para cada uma das seguintes proposições (considere o
conjunto universal como sendo o conjunto dos números reais):
(a) (∀x)(| x |= x)
(b) (∃x)(x2 = x)
(c) (∀x)(x+ 1 > x)
(d) (∃x)(x+ 2 = x)
(e) (∃x)(| x |= 0)
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 28
25. Negue as proposições do exerćıcio anterior.
26. Seja A = {1, 2, 3, 4, 5}. Determine o valor verdade de cada uma das proposições
seguintes:
(a) (∃x ∈ A)(x+ 3 = 10)
(b) (∀x ∈ A)(x+ 3 < 10)
(c) (∃x ∈ A)(x+ 3 < 5)
(d) (∀x ∈ A)(x+ 3 ≤ 7)
27. Negue cada uma das proposições do exerćıcio anterior.
28. Seja o conjunto universal {1, 2, 3}. Determinar o valor verdade de cada uma das
seguintes proposições:
(a) (∃x)(∀y)(x2 < y + 1)
(b) (∀x)(∃y)(x2 + y2 < 12)
(c) (∀x)(∀y)(x2 + y2 < 12)
(d) (∃x)(∀y)(∃z)(x2 + y2 < 2z2)
(e) (∃x)(∃y)(∀z)(x2 + y2 < 2z2)
29. Qual a regra de inferência utilizada em cada argumento dado a seguir:
(a) Se Gauss é o autor do livro, então o livro é de Matemática. Mas, o livro não é
de matemática. Portanto, Gauss não é o autor do livro.
(b) Se a firma falir, todos os seus ativos têm que ser confiscados. A firma faliu.
Segue que todos os seus bens devem ser confiscados.
(c) O cachorro tem pêlo sedoso e adora latir. Portanto, o cachorro adora latir.
(d) Se Paulo é um bom nadador, então ele é um bom corredor. Se Paulo é um bom
corredor, então ele é um bom ciclista. Portanto, se Paulo é um bom nadador,
então ele é um bom ciclista.
30. Para os itens abaixo, decida que conclusão, se é que há alguma, pode ser inferida
das hipóteses dadas e justifique sua resposta.
(a) Se o carro foi envolvido em um acidente onde o motorista fugiu, então a pintura
deve ter descascado. Mas a pintura não está descascada.
(b) Ou o tempo vai ficar ruim, ou sairemos a tempo. Se o tempo ficar ruim, então
o vôo pode ser cancelado.
(c) Se a conta fosse enviada hoje, você seria pago amanhã. Você será pago amanhã.
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 29
(d) A grama precisa ser cortada e as árvores precisam ser podadas. Se a grama
precisa ser cortada, então precisamos varrer as folhas.
31. Usando lógica proposicional, mostre que os argumentosseguintes são válidos:
(a) Se o programa é eficiente, executa rapidamente: ou o programa é eficiente ou
tem algum bug. No entanto, o programa não executa rapidamente. Logo, ele
tem um bug.
(b) Se Maria é a mais popular, ela será eleita. Se Maria é a mais popular, então
Carlos vai renunciar. Portanto, se Maria é a mais popular, ela será eleita e
Carlos renunciará.
(c) A colheita é boa mas não há água suficiente. Se houver muita chuva ou se não
houver muito sol, então haverá água suficiente. Portanto, a colheita é boa e há
muito sol.
(d) Se o anúncio for bom, o volume de vendas aumentará. Ou o anúncio é bom,
ou a loja vai fechar. O volume de vendas não vai aumentar. Portanto, a loja
vai fechar.
32. Seja Apq designando p ∧ q e seja Np designando ∼ p. Reescreva as seguintes pro-
posições usando A e N em lugar de ∧ e ∼.
(a) p∧ ∼ q
(b) ∼ (∼ p ∧ q)
(c) ∼ p ∧ (∼ q ∧ r)
(d) ∼ (p∧ ∼ q) ∧ (∼ q∧ ∼ r)
33. Reescreva as seguintes proposições usando ∧ e ∼ em lugar de A e N .
(a) NApq
(b) ANpq
(c) ApNr
(d) ApAqr
(e) AApqr
(f) ANpAqNr
(g) NAANpqr
(h) ANApAqpAANqrp
Matemática Discreta - Notas de Aula - Caṕıtulo 01 - 30
Referências
GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação: Um
tratamento moderno de Matemática Discreta. 5a. ed. Rio de Janeiro: Livros Técnicos e
Cient́ıficos Editora S.A. 597 p.
HUNTER, D. J. Fundamentos da Matemática Discreta. 1a. ed. Rio de Janeiro: Elsevier,
2011.
MEC. Diretrizes Curriculares para Cursos de Computação e Informática. [S.l.], 2005.
MENEZES, P. B. Matemática Discreta para Computação e Informática. 2a. ed. Porto
Alegre: Sagra Luzzatto Editora, 2005.
PINTO, J. S. Tópicos de Matemática Discreta. [S.l.], 2005.
ROSEN, K. H. Discrete Mathematics and Its Applications. 5th. ed. New York: McGraw
Hill, 2003.
SOUZA, J. N. de. Lógica para Ciência da Computação. 1a. ed. Rio de Janeiro: Elsevier,
2010.