Matemática Discreta
Matemática Discreta
Matemática Discreta
Licenciatura em Matemática
MATEMÁTICA DISCRETA
Fortaleza | CE
2017
© Copyright 2017 Instituto Federal de Educação, Ciência e Tecnologia do Ceará
Direitos reservados e protegidos pela Lei n. 9.610, de 19 de fevereiro de 1998.
É proibida a reprodução total ou parcial sem autorização expressa do IFCE.
207 p.
ISBN 978-85-475-0056-6
1. Lógica. 2.Contagem (Matemática). 3. Grafos - Teoria. I. Castro, Jânio Kléo de Sousa. II. Título
CDD 511.3
O IFCE empenhou-se em identicar todos os responsáveis pelos direitos autorais das imagens e dos textos
reproduzidos neste livro. Se porventura or constatada omissão na identicação de algum material,
dispomo-nos a efetuar, futuramente, os possíveis acertos.
Sumário
Apresentação 6
Referências 205
Matemática Discreta
Aula 1
7
Olá! Esta é a nossa primeira aula. Nela, faremos um breve passeio na história da
Lógica, apontando em que contexto ela surgiu, quais estudiosos contribuíram para
o seu desenvolvimento e que ramos da Matemática e de áreas ans se utilizam das
teorias da Lógica para desenvolver suas próprias teorias. Esperamos, assim, reconhecer
a importância da Lógica como linguagem formal para a Matemática e sua aplicação em
qualquer área que exija raciocínios elaborados, bem como em casos práticos do nosso
dia a dia.
Objetivos
Aula 1
Tópico 1
8
OBJETIVOS
Reconhecer a Lógica em uma perspectiva de valor histórico
Compreender a importância da Lógica e de seu ensino
Neste tópico, faremos um breve passeio histórico, desde a criação da Lógica por
Aristóteles até o seu desenvolvimento e perspectiva nos dias atuais, a m de mostrar a
você, caro(a) aluno(a), a importância da Lógica Matemática para a própria Matemática
como também para outras áreas que se utilizam de suas bases teóricas.
Tradicionalmente, diz-
Lógica deriva do termo se que a Lógica é a ciência
grego logos (λόγος), que
do raciocínio ou que está
possui vários signicados
preocupada com o estudo
em português, sendo
os mais básicos e do raciocínio. São objetos de
usados inicialmente “palavra” e “verbo”. estudo da Lógica os métodos
São também frequentemente associados e princípios usados para
ao termo signicados como: “estudo”, decidir pela validez ou não das
“discurso”, “linguagem”, “princípio”, “ideia” conclusões e pela correção
e “explicação”. À época de lósoos gregos ou não dos raciocínios. Para
como Heráclito (535 – 475 a.C.), logos passou
Aristóteles, a Lógica seria uma
a ter o sentido mais amplo de “pensamento”
ferramenta para a busca da
e “razão” (GALINARI, 2011; CABRAL, 2013;
http://queconceito.com.br/logos; https:// verdade (ABE; SCALZITTI; SILVA
pt.wikipedia.org/wiki/Logos). FILHO, 2001; PEREIRA, 2001;
MUNDIM, 2002).
Matemática Discreta
Segundo Copi (1978, p. 19), “O estudo da lógica é o estudo dos métodos e
princípios usados para distinguir o raciocínio correto do incorreto”. Salmon (1978, p.
13), por sua vez, arma que “A lógica trata, portanto, de argumentos e inerências. Um
de seus propósitos básicos é apresentar métodos capazes de identicar os argumentos
logicamente válidos, distinguindo-os dos que não são logicamente válidos”.
A Lógica é útil a qualquer área que exija raciocínios elaborados, bem como em
casos práticos do nosso dia a dia. Conforme Figura 1, o conhecimento básico de Lógica
é indispensável, por exemplo, para estudantes de Matemática, Filosoa, Ciências,
Línguas ou Direito, dentre outras áreas.
Aula 1 | Tópico 1
Seu aprendizado auxilia os estudantes no raciocínio, na compreensão de
conceitos básicos e na vericação ormal de provas, preparando para o entendimento
dos conteúdos de tópicos mais avançados.
Matemática Discreta
Um pouco mais sobre os fundamentos da Lógica, sua história
e classicações podem ser visto nos livros:
ABE, Jair Minoro; SCALZITTI, Alexandre e DA SILVA FILHO,
João Inácio. Introdução à Lógica para a Ciência da Computação. São Paulo:
Editora Arte & Ciência, 2001.
DA COSTA, Newton Carneiro Afonso. Ensaio sobre os Fundamentos da
Lógica. 3. ed. São Paulo: Hucitec, 2008.
COPI, Irving Marmer. 2. ed. Introdução à Lógica. Tradução de Álvaro Cabral.
São Paulo: Mestre Jou, 1978.
SALMON, Wesley C. Lógica. 4. ed. Tradução Leonidas Hegenberg e Octanny 11
Silveira da Mota. Rio de Janeiro: Zahar, 1978.
Ou pesquisando nos sítios:
http://www.pucsp.br/~logica
http://www.filorbis.pt/filosofia/Hist.htm
https://sites.google.com/site/filosofarliberta/areas-disciplinas-da-filosofia/
logica
http://fabiopestanaramos.blogspot.com.br/2011/10/introducao-logica-
aristotelica.html
Fonte: http://pt.freeimages.com/search/robot/3
Aula 1 | Tópico 1
Embora a lógica seja um tema com ricas conexões interdisciplinares e que
se percebe até mesmo nas conversas informais ou na leitura de jornais ou revistas,
seu ensino, em particular a nível básico, enrenta sérias diculdades, como sugere a
ilustração a seguir.
12
Do que expomos até aqui, ca evidenciado que uma das principais funções
da Lógica Matemática é servir de fundamento ao raciocínio matemático, evitando
ambiguidades e contradições por possibilitar determinar, com absoluta precisão e
rigor, quando um raciocínio matemático é válido e quando ele não o é, ou seja, ela
Matemática Discreta
fornece técnicas adequadas para a análise de argumentos. Nesse contexto, está
pressuposta a ideia de provas ou demonstrações – essencial para sua formação como
professor de Matemática, bem como são fornecidas as bases para a compreensão e
resolução de problemas.
Além de ser uma ferramenta básica que nos auxilia na apropriação de objetos
matemáticos (denições, representações, teoremas e demonstrações), a Lógica é um
poderoso recurso na organização do pensamento humano.
Aula 1 | Tópico 1
Tópico 2
14
OBJETIVOS
Compreender a distinção entre argumentos dedutivos e indutivos
Desenvolver a capacidade de elaboração de discursos corretos
Você já sabe, prezado(a) cursista, que a lógica é uma ferramenta para a busca
da verdade através da argumentação, sendo sua unção principal a identicação de
argumentos logicamente válidos e sua distinção daqueles que não são logicamente
válidos, ou seja, a análise dos raciocínios quanto à sua correção ou não.
Matemática Discreta
Exemplo 1
1. A lua é quadrada.
2. A neve é branca.
3. (eπ ) 2 ≠ e 2π .
4. sen π = 1 .
Exemplo 2
Você deve estar notando que em nenhum desses casos faz sentido questionar se
é uma proposição verdadeira ou falsa.
premissas: p1 , p2 , , pn , n ≥ 1
Argumento
conclusão: c
Aula 1 | Tópico 2
Argumento dedutivo: aquele em que as premissas fornecem uma prova
conclusiva da veracidade da conclusão. Diz-se que um argumento dedutivo é válido
quando suas premissas, se verdadeiras, fornecem provas convincentes para sua
conclusão, ou seja, quando a conclusão for verdadeira sempre que as premissas sejam
verdadeiras; caso contrário, o argumento dedutivo é dito inválido ou não válido.
DEDUTIVOS INDUTIVOS
Matemática Discreta
Exemplo 3
Aula 1 | Tópico 2
Exemplo 4
Matemática Discreta
De acordo com Copi (1978), a palavra “falácia” é usada de múltiplas maneiras,
sendo um de seus usos correto o que se lhe dá para designar qualquer ideia equivocada
ou falsa crença. Copi (1978, p. 73) acrescenta que, no estudo da lógica, se costuma
reservar o nome de “falácia” para os “argumentos ou raciocínios que, embora
incorretos, podem ser psicologicamente persuasivos”, ou seja, com aparência de
correção, mas que, quando examinados cuidadosamente, não o são.
Aula 1 | Tópico 2
Tópico 3
Operações lógicas
sobre as proposições
20
OBJETIVOS
Conhecer os princípios que regem o cálculo proposicional
Conhecer as principais operações com proposições
Você já sabe que uma proposição é uma sentença declarativa que pode ser
verdadeira ou falsa, ou seja, cujo valor lógico ou valor de verdade pode ser a verdade
(V) ou a falsidade (F). Neste tópico, com vistas a consolidar a Lógica como linguagem
formal para a Matemática, ampliaremos a discussão sobre proposições, que são os
elementos básicos dessa linguagem. Veremos os conectivos para compor novas
proposições a partir de outras mais simples e deniremos as principais operações
lógicas com proposições.
Matemática Discreta
As proposições compostas são chamadas também fórmulas
proposicionais ou simplesmente fórmulas. As proposições
componentes de uma proposição composta podem ser, elas
mesmas, proposições compostas.
Exemplo 5
1. p : a Terra é plana.
2. q : sen π = 0 .
3. r : Fortaleza é a capital do Ceará. 21
4. S : o sol brilha e a lua refete a luz.
5. T : os homens são mortais ou as pedras são seres vivos.
6. U : se 3 < π e o número 8 é cubo perfeito, então 25 é um número primo.
Aula 1 | Tópico 3
Provavelmente, prezado(a) aluno(a), você já deve saber que, ao proferimos
um discurso na língua natural, necessitamos de conexões apropriadas de ideias.
A materialização dessas conexões é realizada por partículas da linguagem comumente
chamadas conectivos. De modo análogo, na Matemática, precisamos de conectivos
que interliguem sentenças para gerar outras sentenças mais complexas (mais ricas em
signicados).
Exemplo 6
A: O número 2 é par e 5 é ímpar.
B: Um triângulo ABC é escaleno ou isósceles.
C: Neste ano, não houve inverno (esta proposição deriva da proposição “Neste
ano, houve inverno”).
D: Se sabe Matemática, então faça Medicina.
E: Um triângulo é retângulo se, e somente se, satisfaz o Teorema de Pitágoras.
Matemática Discreta
As operações obedecem a
A tabela-verdade
algumas regras de um tipo de cálculo,
de uma proposição
chamado de cálculo proposicional,
fornece os valores
que são semelhantes às regras sobre
lógicos dessa
proposição para cada conjuntos (como interseção, união,
atribuição de valores lógicos às suas etc.). Vamos, agora, conhecer cada
proposições componentes. uma das operações denidas por
meio dos conectivos acima e as suas
correspondentes tabelas-verdade.
Considerando as igualdades
p ¬p
¬V = F e ¬F = V,
temos que V(¬p) = ¬ V(p). V F
F V
Fonte: DEaD | IFCE.
Exemplo 7
a) p : Fortaleza é a capital do Ceará.
¬p : Fortaleza não é a capital do Ceará.
Note que V(p ) = V e V(¬p ) = F e a relação V(¬p) = ¬V(p) é vericada, pois
V(¬p) = F = ¬V = ¬V(p).
b) q : sen π
( 2) = 0 .
¬q : sen (π ) ≠ 0 .
2
Então, V(q) = F e V(¬q) = V
Aula 1 | Tópico 3
Na linguagem do dia a dia, a negação de uma armação (pelo menos nos casos
mais simples) costuma ser feita antepondo o advérbio não ao verbo da proposição,
como em (a) do Exemplo 7, correto? Entretanto, há outras formas de construir a
negação, por exemplo, antepondo expressões como “não é verdade que” ou “é falso
que” à proposição que se deseja negar. Veja essas formas no exemplo seguinte:
Exemplo 8
r : Pedro é eletricista.
¬r : Não é verdade que Pedro é eletricista.
ou,
24 ¬r : É falso que Pedro é eletricista.
2. Conjunção de proposições
Matemática Discreta
Tabela 3 − Tabela-verdade da conjunção
V ∧ V = V, V ∧ F = F, V V V
F ∧ V=F e F ∧ F = F,
V F F
temos que V( p ∧ q ) = V(p) ∧ V(q).
F V F
F F F
Exemplo 9
a) p : 2 é par.
q : 2 < 3.
p ∧ q : 2 é par e 2 < 3.
Temos: V(p) = V e V(q) = V. Logo, V( p ∧ q ) = V(p) ∧ V(q) = V ∧ V = V.
b) p : um quadrado é equilátero.
q : 7 é par.
p ∧ q : um quadrado é equilátero e 7 é par.
Temos: V(p) = V e V(q) = F. Logo, V( p ∧ q ) = V(p) ∧ V(q) = V ∧ F = F.
c) p : π é racional.
q : 2 é irracional.
p ∧ q : π é racional e 2 é irracional.
Temos: V(p) = F e V(q) = V. Logo, V( p ∧ q ) = V(p) ∧ V(q) = F ∧ V = F.
d) p : sen 0 > 2.
q : π > 5.
p ∧ q : sen 0 > 2 e π > 5.
Temos: V(p) = F e V(q) = F. Logo, V( p ∧ q ) = V(p) ∧ V(q) = F ∧ F = F.
3. Disjunção de proposições
Aula 1 | Tópico 3
Tabela 4 − Tabela-verdade da disjunção
p q p∨q
Considerando as igualdades
V V V
V ∨ V = V, V ∨ F = V,
F ∨ V=V e F ∨ F = F, V F V
temos que V( p ∨ q ) = V(p) ∨ V(q).
F V V
F F F
Exemplo 10
a) p : A Lua é o nosso satélite natural.
q : A Terra é um planeta.
p ∨ q : A Lua é o nosso satélite natural ou a Terra é um planeta.
Temos: V(p) = V e V(q) = V. Logo, V( p ∨ q ) = V(p) ∨ V(q) = V ∨ V = V.
b) p : 1 é um número natural.
q : –2 é um número natural.
p ∨ q : 1 é um número natural ou –2 é um número natural.
Temos: V(p) = V e V(q) = F. Logo, V( p ∨ q ) = V(p) ∨ V(q) = V ∨ F = V.
c) p : 11 é divisível por 3.
q : 5 < 10.
p ∨ q : 11 é divisível por 3 ou 5 < 10.
Temos: V(p) = F e V(q) = V. Logo, V( p ∨ q ) = V(p) ∨ V(q) = F ∨ V = V.
d) p : um triângulo é um quadrilátero.
q : todo triângulo é isósceles.
p ∨ q : um triângulo é um quadrilátero ou todo triângulo é isósceles.
Temos: V(p) = F e V(q) = F. Logo, V( p ∨ q ) = V(p) ∨ V(q) = F ∨ F = F.
Bem, depois de estudar tudo isso, evidentemente, você já sabe o que é a negação
de uma proposição e o que signica a conjunção e a disjunção de duas proposições
e conhecem também as tabelas-verdade dessas proposições, correto? Nesse caso,
passaremos agora às denições das proposições condicional e bicondicional. Continue
atento, pois será necessária bastante atenção para compreendê-las e para identicar
suas tabelas-verdade.
Matemática Discreta
4. Proposição condicional
Considerando as igualdades
p q p→q 27
V → V = V, V → F = F, V V V
F → V = V e F → F = V, V F F
temos que V( p → q ) = V(p) → V(q).
F V V
F F V
Fonte: DEaD | IFCE.
Exemplo 11 A condicional “ p → q ”
é verdadeira sempre que
a) p : Euler morreu cego.
V(p) = F ou que V(q) = V.
q : Pitágoras era lósoo.
p → q : Se Euler morreu cego,
então Pitágoras era lósoo.
Temos : V(p) = V e V(q) = V. Logo, V( p → q ) = V(p) → V(q) = V → V = V.
c) p : 2 > 5.
q : 3 é real.
p → q : Se 2 > 5, então 3 é real.
Temos : V(p) = F e V(q) = V. Logo, V( p → q ) = V(p) → V(q) = F → V = V.
Aula 1 | Tópico 3
d) p : –1 é um número natural.
q : 3 é um número par.
p → q : Se –1 é um número natural, então 3 é um número par.
Temos : V(p) = F e V(q) = F. Logo, V( p → q ) = V(p) → V(q) = F → F = V.
28
Na condicional p→q, a proposição p é chamada antecedente
e a proposição q é chamada consequente da condicional.
Além disso, uma proposição condicional “ p→q ” não arma
que a proposição consequente q é deduzida da proposição
antecedente p.
Portanto, quando se diz, por exemplo:
2 é um número par → os patos nadam.
Não se quer dizer, de modo algum, que o fato de patos nadarem é uma consequência
do número 2 ser par. Ela arma unicamente uma relação entre os valores lógicos
de p e de q, conforme a tabela-verdade da condicional.
5. Proposição bicondicional
Matemática Discreta
Tabela 6 − Tabela-verdade da bicondicional
Considerando as igualdades
p q p↔q
Considerando as igualdades V V V
V ↔ V = V, V ↔ F = F, V F F
F↔V=F e F ↔ F = V,
temos que V( p ↔ q ) = V(p) ↔ V(q). F V F
F F V
Fonte: DEaD | IFCE.
29
A bicondicional “ p ↔ q
Vejamos alguns exemplos:
” é verdadeira sempre que
Exemplo 12 V(p) = V(q) e é falsa
sempre V(p) ≠ V(q).
a) p : O futebol é uma
paixão brasileira.
q : A bola de futebol é redonda.
p ↔ q : O futebol é uma paixão brasileira se, somente se, a bola de futebol for
redonda.
Temos : V(p) = V e V(q) = V. Logo, V( p ↔ q ) = V(p) ↔ V(q) =
V ↔ V = V.
b) p : π > 3.
π
q : tg = 0
2
π
p ↔ q : π > 3 se, somente se, tg = 0 .
2
Temos : V(p) = V e V(q) = F. Logo, V( p ↔ q ) = V(p) ↔ V(q) = V ↔ F = F.
c) p : Um triângulo é um quadrilátero.
q : Um quadrado é um quadrilátero.
p ↔ q : Um triângulo é um quadrilátero se, somente se, um quadrado for
quadrilátero.
Temos : V(p) = F e V(q) = V. Logo, V( p ↔ q ) = V(p) ↔ V(q) =
= F ↔ V = F.
Aula 1 | Tópico 3
d) p : 2 é ímpar.
q : 3 é par.
p ↔ q : 2 é ímpar se, somente se, 3 é par.
Temos : V(p) = F e V(q) = F. Logo, V( p ↔ q ) = V(p) ↔ V(q) = F ↔ F = V.
Nesta aula inicial, zemos uma breve introdução ao estudo da Lógica, conhecendo
um pouco de sua história e sua importância não apenas para a própria Matemática
como também para outras áreas. Vimos, ainda, como identicar argumentos corretos
e apresentamos as principais operações do cálculo proposicional.
Matemática Discreta
1. (Extraído de COPI, Irving. Introdução à Lógica. São Paulo: Mestre Jou, 1978).
Em certa comunidade mítica, os políticos sempre mentem e os não políticos
falam sempre a verdade. Um estrangeiro encontra-se com três nativos e
pergunta ao primeiro deles se é um político. Este responde à pergunta. O
segundo nativo informa, então, que o primeiro nativo negou ser um político.
Mas o terceiro nativo arma que o primeiro nativo é, realmente, um político.
Quais desses três nativos eram políticos?
a) (3 + 4) 2 = 32 + 42 ou 246 é múltiplo de 6.
b) cos(600 ) = 0,5 e π = 3,14 .
c) Se (−3) 4 = 34 , então −2 ≤ −3 .
d) tg(450 ) ≠ 1 se, e somente se, 2 > 2.
a) V( p ∧ q ) = F e V( p ∨ q ) = V.
b) V( p → q ) = V e V( p ∨ q ) = V.
c) V( p ↔ q ) = V e V( p ∧ q ) = F.
d) V( p → q ) = V e V( p ↔ q ) = F.
Pratique
5. Considere as proposições:
Matemática Discreta
1. Somente um dos nativos, o primeiro ou o terceiro, é um político.
2.
a) Argumento indutivo fraco
b) F
c) F
d) V
4.
a) V( p ) = V e V( q ) = F ou V( p ) = F e V( q ) = V
b) V( p ) = V e V( q ) = V ou V( p ) = F e V( q ) = V
c) V( p ) = F e V( q ) = F
d) V( p ) = F e V( q ) = V
5.
a)
i) 2 não é um número irracional; F
ii) Natal é a capital de Pernambuco e 2 não é um número irracional; F
iii) Se Natal não é a capital de Pernambuco, então 2 é um número
irracional; V
iv) Natal é a capital de Pernambuco se, e somente se, 2 é um número
irracional; F
b)
i) ¬p; V
ii) ¬(p∧q); V
iii) ¬q →p ; V
iv) ¬p ↔q; V
Pratique
Aula 2
Tabelas-verdade, proposições
especiais e relações entre proposições
34
Caro(a) aluno(a), na Aula 1, iniciamos o cálculo proposicional apresentando as
tabelas-verdade das operações básicas: negação, conjunção, disjunção, condicional
e bicondicional. Agora, você já está apto a construir tabelas-verdade de proposições
mais complexas, obtidas pela combinação de conectivos.
Objetivos
Matemática Discreta
Tópico 1
Tabelas-verdade
de proposições compostas
35
OBJETIVOS
Construir tabelas-verdade de proposições compostas
Deduzir valores lógicos de proposições compostas
Exemplo 1
P ( p, q ) = ¬( p ∨ q )
Q ( p , q ) = ¬p ∧ ( p ↔ q )
R ( p, q, r ) = ( p → q ) ∨ ( p → r )
S ( p, q, r , s ) = ( p ∧ q ) ↔ ( r ∨ s )
Exemplo 2
Dadas as proposições P composta das proposições simples p1 e q1 , e Q composta
das proposições simples p2 , q2 e r2 , ou seja, dadas P ( p1 , q1 ) e Q ( p2 , q2 , r2 ) , podemos
Aula 2 | Tópico 1
construir uma proposição α pela combinação das proposições P e Q . Temos, então,
α ( P, Q) ou mais especicamente,
α ( P ( p1 , q1 ), Q( p2 , q2 , r2 )) .
Podemos sempre
O valor lógico de
36 pensar numa proposição
proposições compostas é
composta P qualquer como
fortemente determinado
obtida pela combinação de pelos valores lógicos de
uma quantidade nita n de suas componentes, bem como pelo modo
proposições simples p1, p2 , ..., como estas se combinam (ou seja, depende
pn, ou seja, P ( p1 , p2 ,..., pn ) também dos conectivos que as determinam).
. Considerando que o número
de modos de combinar as
proposições p1 , p2 , ..., pn , por meio dos conectivos, para obter P, seja nito e
lembrando que, pelo Princípio do Terceiro Excluído, só há duas possibilidades para os
valores lógicos de cada proposição pi , temos que são também nitas as possibilidades
de se combinarem os valores lógicos das proposições simples para determinar o valor
lógico correspondente da proposição composta.
Matemática Discreta
A demonstração desse teorema é uma aplicação direta do Teorema Fundamental
da Contagem ou Teorema Multiplicativo, que será visto posteriormente nesta disciplina.
Destaco para você que não há uma regra geral para a ordem de atribuições
de valores lógicos às proposições componentes na construção de tabelas-verdade
de proposições compostas. Apresentaremos aqui a forma descrita em Alencar Filho
(2002, p. 30).
Natabela-verdadedeumaproposiçãoP,chamaremosascolunascorrespondentes
às suas proposições simples componentes de entradas da tabela, e a coluna com os
valores lógicos correspondentes de P de saída da tabela. Além das entradas e da saída,
ao construir a tabela-verdade de uma proposição, é comum proceder-se construindo,
a partir das tabelas-verdades das operações básicas do cálculo proposicional, colunas
intermediárias (tantas quanto forem necessárias) das proposições compostas que são
“pedaços” de P, até se conseguir obter a coluna de P. Para facilitar a compreensão,
vejamos alguns exemplos:
Aula 2 | Tópico 1
Exemplo 3
p q ¬p ¬p ∨ q R ( p, q ) = ¬(¬p ∨ q )
V V F V F
V F F F V
F V V V F
F F V V F
38 Fonte: DEaD | IFCE.
Exemplo 4
Construa a tabela-verdade da proposição composta
S ( p, q, r ) = ( p ∨ q ) → ( q ∧ r ) .
Tabela 8 − Tabela-verdade de S ( p, q, r ) = ( p ∨ q ) → ( q ∧ r )
p q r p∨q q∧r S ( p, q, r ) = ( p ∨ q ) → ( q ∧ r )
V V V V V V
V V F V F F
V F V V F F
V F F V F F
F V V V V V
F V F V F F
F F V F F V
F F F F F V
Fonte: DEaD | IFCE.
Matemática Discreta
tabela, para isso, formamos as
colunas correspondentes às três A construção de
proposições simples componentes. tabelas-verdade é
um importante passo
Os grupos de valores V e F se
para que se possa
alternam nessas colunas de 4 em 4
vericar a validade
para a 1ª proposição simples, p, de 2
de argumentos, bem como para se
em 2 para a 2ª proposição simples,
observar relações existentes entre certas
q, e de 1 em 1 para a 3ª proposição,
proposições.
r. Em seguida, recorremos às
tabelas-verdade das operações de
conjunção e disjunção para formar a quarta e a quinta colunas. Finalmente, usando
a tabela-verdade da operação de condicional, determinamos a “saída” da tabela, ou
39
seja, formamos a coluna relativa aos valores lógicos da proposição composta dada S.
(i) ( p ∨ q ) ∧ r e (ii) p ∨ (q ∧ r )
¬ ∧e∨ → ↔
(conjunção e
(negação) (condicional) (bicondicional)
disjunção)
conectivo conectivo
mais fraco mais forte
Aula 2 | Tópico 1
Desse modo, a proposição
p∨q ↔ r → s
p ∨ (q ↔ r → s ) ou p ∨ ((q ↔ r ) → s )
( p ∨ q ↔ r ) → s ou ( p ∨ (q ↔ r )) → s .
( p ∧ q ) ∧ r e ¬(¬p ) ,
p ∧ q ∧ r e ¬(¬p ) .
Exemplo 5
Matemática Discreta
Além da tabela-verdade, podemos também representar os valores lógicos de
uma proposição P (presentes na coluna de saída da tabela-verdade), associados a
cada atribuição de valores lógicos às proposições componentes de P (presentes nas
colunas de entrada da tabela-verdade), de forma mais abreviada, por meio da notação
de funções. Consequentemente, podemos representar as entradas de uma tabela-
verdade e suas correspondentes saídas por meio de diagramas de fechas.
Aula 2 | Tópico 1
Exemplo 6
Tabela 10 − Tabela-verdade de P ( p, q ) = p ∧ ( p → q ) → q
p q p→q p ∧ ( p → q) p ∧ ( p → q) → q
V V V V V
V F F F V
F V V F V
F F V F V
42 Fonte: DEaD | IFCE.
Veremos, mais adiante, que essa proposição, chamada de regra modus ponens,
está relacionada com a implicação lógica ( ⇒ ). Note que ela tem uma característica
especial: a última coluna de sua tabela-verdade, que encerra o valor lógico da
proposição, só contém o valor lógico verdade (V). No tópico seguinte, você, prezado(a)
aluno(a), verá que esse tipo de proposição é chamada tautologia.
Nesse caso temos
P(VV) = V, P(VF) = V, P(FV) = V e P(FF) = V
ou, abreviadamente,
P(VV, VF, FV, FF) = VVVV.
Matemática Discreta
Caro(a) aluno(a), concluiremos este tópico apresentando, através de exercícios
resolvidos, formas de determinar o valor lógico de uma proposição composta, para
certa atribuição de valores lógicos às suas proposições simples componentes, sem
necessitar construir sua tabela-verdade. Esse conhecimento será de grande utilidade
nas demonstrações de validade ou não de argumentos.
Exercício resolvido 1
Determine o valor lógico da proposição composta P ( p, q ) = ¬p ↔ q para o
caso de o valor lógico de p ser V (verdade) e o de q ser F (falsidade).
Solução 43
Temos que
V ( P ) = V (¬p ↔ q ) = V (¬ p ) ↔ V ( q ) = ¬ V ( p ) ↔ V ( q ) = ¬ V ↔ F = F ↔ F = V .
Assim, o valor lógico de P ( p, q ) é V.
Exercício resolvido 2
Considerando as proposições
Solução
Inicialmente, precisamos usar conhecimentos de Matemática do Ensino Médio
para determinar os valores lógicos das proposições p, q e r. Do fato que a função seno
é limitada, com −1 ≤ sen( x) ≤ 1 para todo x, V ( p ) = F . Por sua vez, a constituição
dos conjuntos numéricos e o conceito de números primos, nos dão que V (q ) = F e
V (r ) = V . Desse modo, temos
V (Q) = V ( p ∨ r → q ∧ r ) = V ( p ∨ r ) → V (q ∧ r ) = V ( p ) ∨ V (r ) → V (q ) ∧ V (r )
= F∨ V →F∧ V = V →F =F
Aula 2 | Tópico 1
Exercício resolvido 3
R ( p, q ) = ( p → q ) ↔ ( p ∧ (¬q )) .
Solução
Temos que
V ( R ) = V (( p → q ) ↔ ( p ∧ (¬q )))
= V ( p → q ) ↔ V ( p ∧ (¬q ))
44 = ( V ( p ) → V (q )) ↔ ( V ( p ) → V (¬q ))
= ( V ( p ) → V (q )) ↔ ( V ( p ) → (¬V (q )))
= ( V → V ) ↔ ( V → (¬V )) = ( V → V ) ↔ ( V → F) = V ↔ F = F
Desde que, pela ordem de precedência o conectivo “↔” é mais forte que
os conectivos “→” e “∧”, a proposição R ( p, q ) do “Exercício resolvido 3” é uma
bicondicional e, por supressão de parêntesis, pode ser escrita simplesmente como
R ( p , q ) = p → q ↔ p ∧ ¬q .
Matemática Discreta
Tópico 2
Tautologias, contradições
e contingências
45
OBJETIVOS
Reconhecer tautologias e contradições
Identificar contingências e seus valores lógicos
Aula 2 | Tópico 2
Exemplo 7
A proposição ¬( p ∧ ¬p ) é uma tautologia, como pode ser visto em sua tabela-
verdade.
Tabela 11 − Tabela-verdade de ¬( p ∧ ¬p )
p ¬p p ∧ ¬p ¬( p ∧ ¬p )
V F F V
F V F V
Fonte: DEaD | IFCE.
Exemplo 8
A coluna de saída da tabela-verdade de p ∨ ¬p só apresenta o valor lógico V
(verdade).
Tabela 12 − Tabela-verdade de p ∨ ¬p
p ¬p p ∨ ¬p
V F V
F V V
Fonte: DEaD | IFCE.
Tabela 13 − Tabela-verdade de p → q ↔ ¬q → ¬p
p q ¬p ¬q p→q ¬q → ¬p p → q ↔ ¬q → ¬p
V V F F V V V
V F F V F F V
F V V F V V V
F F V V V V V
Fonte: DEaD | IFCE.
Matemática Discreta
Conforme veremos no Tópico 3, esse exemplo indica que uma condicional p → q
e sua contrapositiva ¬q → ¬p têm tabelas-verdade idênticas, por isso a bicondicional
entre elas é uma tautologia.
p q r ¬q p∧r ¬q ∨ r p ∧ r → ¬q ∨ r
V V V F V V V 47
V V F F F F V
V F V V V V V
V F F V F V V
F V V F F V V
F V F F F F V
F F V V F V V
F F F V F V V
Fonte: DEaD | IFCE.
Agora que você sabe o que é uma tautologia, vamos dar a denição de
contradição, outro tipo de proposição composta cujo valor lógico não depende dos
valores lógicos das proposições componentes.
Aula 2 | Tópico 2
Exemplo 11 (Alencar Filho, 2002, p. 46)
p ¬p p ∧ ¬p
V F F
F V F
Fonte: DEaD | IFCE.
Exemplo 12
A proposição p ↔ ¬p é contraválida. Com efeito, sua tabela-verdade é
Tabela 16 − Tabela-verdade de p ↔ ¬p
p ¬p p ↔ ¬p
V F F
F V F
Fonte: DEaD | IFCE.
Exemplo 13
A proposição p → q ↔ p ∧ ¬q é uma contradição. A coluna de saída de sua
tabela-verdade só apresenta o valor lógico F (falsidade).
Tabela 17 − Tabela-verdade de p → q ↔ p ∧ ¬q
p q p→q ¬q p ∧ ¬q p → q ↔ p ∧ ¬q
V V V F F F
V F F V V F
F V V F F F
F F V V F F
Fonte: DEaD | IFCE.
Matemática Discreta
Exemplo 14
A coluna de saída da tabela-verdade de ¬p ∧ ( p ∧ ¬q ) só apresenta o valor
lógico F (falsidade).
Tabela 18 − Tabela-verdade de ¬p ∧ ( p ∧ ¬q )
p q ¬p ¬q p ∧ ¬q ¬p ∧ ( p ∧ ¬q )
V V F F F F
V F F V V F
F V V F F F
F F V V F F 49
Fonte: DEaD | IFCE.
Aula 2 | Tópico 2
p → q ↔ p ∧ ¬q do Exemplo 13 por substituição da proposição p por ¬t ∨ u e
da proposição q por t ∧ v . Nesse caso, suprimindo parêntesis, a proposição obtida
poderia ser escrita por ¬t ∨ u → t ∧ v ↔ (¬t ∨ u ) ∧ ¬(t ∧ v ) .
50
Na última coluna da tabela-
Uma contingência
verdade de uma contingência,
é também chamada
devem ocorrer os valores lógicos
proposição contingente ou
proposição indeterminada. V e F, cada um pelo menos uma
vez.
Exemplo 15
A proposição p ∨ q → p ∧ q é uma contingência, conforme pode ser visto em
sua tabela-verdade.
Tabela 19: Tabela-verdade de p∨q → p∧q
Matemática Discreta
Tópico 3
Implicações lógicas
e equivalências lógicas
51
OBJETIVOS
Conhecer as relações de implicação lógica e de equivalência lógica
Conhecer propriedades das implicações e das equivalências
Exemplo 16
Aula 2 | Tópico 3
Tabela 20 − Tabelas-verdade de ¬p e p ↔ q
p q ¬p p↔q
V V F V
V F F F
F V V F
F F V V
Fonte: DEaD | IFCE.
Exemplo 17
52 As proposições p e q → p são dependentes, como pode ser visto de suas
tabelas verdades.
p q q→ p
V V V
V F V
F V F
F F V
Fonte: DEaD | IFCE.
Matemática Discreta
Outras formas equivalentes de dizer que P implica Q ( P ⇒ Q ) são
Exemplo 18
O teorema seguinte
Toda proposição
estabelece uma relação entre
implica uma tautologia
a implicação lógica e certa
e somente uma
proposição condicional. Sua contradição implica
demonstração pode ser vista em uma contradição.
Alencar Filho (2002, p. 52).
Aula 2 | Tópico 3
Corolário 2.1 Sejam p1 , p2 , ..., pn proposições simples
dadas. Se P ( p1 , p2 , ..., pn ) ⇒ Q ( p1 , p2 , ..., pn ) , então
temos também P ( p1′, p2′ , ..., pn′ ) ⇒ Q ( p1′, p2′ , ..., pn′ )
quaisquer que sejam as proposições simples ou compostas
p1′, p2′ , ..., pn′ .
Exercício resolvido 4
Usando tabela-verdade, prove que p ∧ q ⇒ p ∨ q .
Solução
Vamos construir a tabela-verdade da condicional p ∧ q → p ∨ q .
V V V V V
V F F V V
F V F V V
F F F F V
Fonte: DEaD | IFCE.
Exercício resolvido 5
Verique, usando tabela-verdade, se a proposição p ↔ ¬q implica ou não a
proposição ¬p → ¬q .
Solução
Vamos construir a tabela-verdade da condicional ( p ↔ ¬q ) → (¬p → ¬q ) .
Matemática Discreta
Tabela 24 − Tabela-verdade de ( p ↔ ¬q ) → (¬ p → ¬ q )
p q ¬p ¬q p ↔ ¬q ¬p → ¬q ( p ↔ ¬q ) → (¬ p → ¬ q )
V V F F F V V
V F F V V V V
F V V F V F F
F F V V F V V
1. Refexiva: P ⇒ P ;
2. Transitiva: Se P ⇒ Q e Q ⇒ R , então P ⇒ R .
Associada à implicação P ⇒ Q
(P implica Q) está a implicação A implicação ¬Q ⇒ ¬P
diz a mesma coisa que
¬Q ⇒ ¬P (a negação de Q implica a
a implicação P ⇒ Q ,
negação de P).
ou seja, a implicação
¬Q ⇒ ¬P nada mais é do que a implicação
Na Aula 4, você, caro(a) aluno(a),
P ⇒ Q dita com outras palavras, ou vista
perceberá que muitas armações de um ângulo diferente. Portanto,
(resultados) na Matemática são
P ⇒ Q se, e somente se, ¬Q ⇒ ¬P .
apresentadas na forma
H (Hipótese) ⇒ T (Tese).
Aula 2 | Tópico 3
Nesses casos, e em muitasoutras situações, é muito comum substituira implicação
H ⇒ T por ¬T ⇒ ¬H , a m de tornar seu signicado mais claro ou manejável.
Agora que você já sabe o que é uma implicação lógica, passemos à denição de
equivalência lógica.
Exemplo 19
p ¬p ¬¬p
V F V
F V F
Exemplo 20
Matemática Discreta
Tabela 26 − Tabelas-verdade de p → q e ¬p ∨ q
p q ¬p p→q ¬p ∨ q
V V F V V
V F F F F
F V V V V
F F V V V
Exercício resolvido 6
Usando tabela-verdade, mostre a equivalência p → p ∧ q ⇔ p → q , a qual é
chamada Regra de Absorção.
Solução
Vamos construir a tabela-verdade da bicondicional p → p ∧ q ↔ p → q .
Aula 2 | Tópico 3
Tabela 27 − Tabela-verdade de p→ p∧q ↔ p→q
Exercício resolvido 7
Verique, usando tabela-verdade, que a proposição p ↔ q é equivalente à
conjunção das duas condicionais p → q e q → p , ou seja, mostre que p ↔ q e
( p → q ) ∧ (q → p ) são equivalentes.
Solução
Vamos construir as tabelas-verdade das proposições p↔q e
( p → q) ∧ (q → p) .
Tabela 28 − Tabelas-verdade de p ↔ q e ( p → q) ∧ (q → p)
p q p→q q→ p p↔q ( p → q) ∧ (q → p)
V V V V V V
V F F V F F
F V V F F F
F F V V V V
Os símbolos “↔ ” e “
Portanto, as tabelas-verdade
⇔ ” não possuem o
de p ↔ q e ( p → q ) ∧ (q → p )
mesmo signicado
são idênticas. Logo, as proposições
lógico. Portanto, cuidado
p ↔ q e ( p → q ) ∧ (q → p ) são
para não confundi-
equivalentes ou, simbolicamente,
los. Enquanto o primeiro representa uma
p ↔ q ⇔ ( p → q) ∧ (q → p) .
operação entre proposições dando origem a
É fácil notar que a relação de uma nova proposição — a bicondicional —,
equivalência goza das propriedades o segundo indica apenas uma relação entre
seguintes: duas proposições dadas – a equivalência.
Matemática Discreta
1. Refexiva: P ⇔ P ;
2. Simétrica: Se P ⇔ Q , então Q ⇔ P ;
3. Transitiva: Se P ⇔ Q e Q ⇔ R , então P ⇔ R .
A⇔ B. 59
A demonstração de tais armações consiste em demonstrar as duas implicações:
A⇒ B e B⇒ A.
Voltemos agora à condicional P → Q . Associada a ela, existem algumas outras
proposiçõescondicionaiscorrelacionadasequetêmpapelfundamentalnacomunicação
em Matemática. Vejamos, na próxima denição, quais são essas condicionais e, no
teorema seguinte, como elas estão relacionadas.
Exemplo 21
Dadas as proposições:
“Se A e B são ângulos opostos pelo vértice, então A e B são ângulos de medidas
iguais”.
Aula 2 | Tópico 3
Contrária: ¬P → ¬Q , que é “Se A e B não são ângulos opostos pelo vértice,
então A e B são ângulos de medidas diferentes”.
P Q ¬P ¬Q P→Q Q→P ¬P → ¬Q ¬Q → ¬P
V V F F V V V V
V F F V F V V F
F V V F V F F V
F F V V V V V V
Matemática Discreta
Prezado(a) aluno(a), nesta
aula, você teve a oportunidade
P→Q é dita
de construir as tabelas-verdade direta em relação
de várias proposições compostas. às suas proposições
Você deve ter percebido que este associadas.
conhecimento permitiu identicar
A contrária ¬P → ¬Q de P → Q é
tautologias, contradições e também chamada inversa de P → Q .
contingências, bem como vericar A contrapositiva de P → Q é a contrária
quando duas proposições estão da recíproca de P → Q , sendo também
relacionadas por meio das relações chamada de contra-recíproca.
de implicação ou de equivalência.
61
Na próxima aula, trataremos de sentenças abertas e de quanticadores.
Aula 2 | Tópico 3
1. Construa as tabelas-verdade das seguintes proposições
a)
( p ↔ q ) ∧ ( q → ¬p )
b) ( p ↔ ¬q ) → (¬ p ↔ q )
c) ¬( p ∧ q ) ↔ ¬( p ∨ ¬r )
a) Redução ao absurdo: p → q ⇔ ( p ∧ ¬q ) → ¬p
b) Negação da condicional: ¬( p → q ) ⇔ p ∧ ¬q
c) Negação da bicondicional: ¬( p ↔ q ) ⇔ ( p ∧ ¬q ) ∨ (¬p ∧ q )
Matemática Discreta
1.
a) FFFV
b) VVVV
c) VVFFVFVF
2.
a) Contraválida.
b) Contingente.
c) Tautológica.
63
3.
a) Da tabela-verdade, a condicional p→ p∨q é uma tautologia. Logo,
pelo Teorema 2.3, segue-se que ocorre a implicação p ⇒ p ∨ q . Outra
orma de tirar essa mesma conclusão é por meio da Denição 2.5.
Aula 2 | Tópico 3
Aula 3
64
Caro(a) aluno(a), esta é a nossa terceira aula. Você já ouviu falar em sentenças
abertas e quanticadores? Bem, aqui trataremos desses dois temas que estão bem
presentes nas armações e demonstrações da Matemática, azendo parte da
linguagem e notação comumente utilizadas nesta área.
Objetivos
Matemática Discreta
Tópico 1
65
OBJETIVOS
Conhecer sentença aberta com uma variável
Determinar conjuntos-verdade de sentenças abertas com uma
variável
Ao introduzirmos novos
símbolos na linguagem do Cálculo As equações e
Proposicional, é possível tratarmos de as inequações
sentenças mais gerais e complexas. É matemáticas são
o que faz a LPO. Além de ser dotada exemplos clássicos de
aplicações da LPO.
de uma linguagem mais rica, ela tem
várias aplicações importantes para a
Matemática e para outras áreas, especialmente para as Ciências Exatas.
Exemplo 1
p: 10 > 3
q: x 2 − 3 x = 0
Aula 3 | Tópico 1
É fácil perceber que a sentença p é uma proposição cujo valor lógico é
V(p) = V. Já a sentença q carece de valor lógico, ou seja, não é possível atribuir um valor
lógico a q . Portanto, q não é uma proposição. Para sermos mais precisos, devemos
dizer que o valor lógico de q será conhecido apenas quando x or identicado, ou
seja, V(q) será conhecido para cada atribuição de valor a x , podendo ser verdade ou
falsidade, dependendo de tal atribuição. Assim:
Exemplo 2
1. x 2 − 7 x + 10 = 0 .
2. Ela é aluna do curso de Licenciatura em Matemática.
3. Ele e ela formam um lindo casal.
Novamente aqui não temos como dizer o valor lógico dessas sentenças, a menos
que os objetos desconhecidos em cada uma delas, “ x ” em (1), “ela” em (2) e “ele” e
“ela” em (3), sejam identicados.
A seguir, denimos de modo mais ormal sentença aberta com uma variável.
Posteriormente, estenderemos essa denição para sentenças abertas com duas ou
mais variáveis.
Matemática Discreta
Em uma sentença aberta, as
Uma sentença aberta
variáveis representam objetos que
com uma variável em
não estão identicados no universo
A é também chamada
considerado (“ x ”, “ele”, “ela”,
função proposicional
“alguém”, “algo”, etc.), e os valores com uma variável em A
das variáveis (também chamados ou simplesmente função proposicional em
constantes) representam objetos A ou ainda condição em A.
identicados do universo (“José”,
“Maria”, “o ponto A”, etc.).
( ( ) )
proposição verdadeira V P ( a ) = V . Simbolicamente,
VP = {a | a ∈ A ∧ V ( P (a )) = V}
Aula 3 | Tópico 1
De um modo mais simples, o conjunto-verdade de uma sentença aberta P ( x )
em A é dado por:
VP = {a | a ∈ A ∧ P (a )} , ou ainda, por VP = {a ∈ A | P (a )} .
Exemplo 3
68 Seja = {1, 2, 3, ...} o conjunto dos números naturais. As seguintes expressões
são sentenças abertas com uma variável em :
1. P ( x ) : 2 x + 1 < 12
2. Q ( x ) : 2 x = x 2
3. R ( x ) : x é divisor de 10
4. S ( x) : x é quadrado perfeito
2. VQ = {a ∈ | 2a = a 2 } = {2, 4}
Exercício resolvido 1
Determine o conjunto-verdade de cada uma das seguintes sentenças abertas
com uma variável:
Matemática Discreta
Solução
Sabemos que não existe número inteiro x cujo quadrado seja igual a 2 (na verdade,
os únicos números cujo quadrado é igual a 2 são − 2 e 2 que não são inteiros). Por
outro lado, desde que o quadrado de um número real qualquer seja maior ou igual a 0,
sua soma com 3 é também maior ou igual a 0. Portanto, temos
1. VP = {a ∈ | a 2 = 2} = ∅ e 2. VQ = {a ∈ | a 2 + 3 ≥ 0} =
Neste tópico, vimos o que são sentenças abertas com uma variável e
determinamos os conjuntos-verdade de algumas delas. No tópico seguinte,
estenderemos esses conceitos para sentenças abertas com várias variáveis. Até lá!
Aula 3 | Tópico 1
Tópico 2
Sentenças abertas
com mais de uma variável
70
OBJETIVOS
Conhecer sentenças abertas com mais de uma variável
Determinar conjuntos-verdade de sentenças abertas com mais de
uma variável
Matemática Discreta
De um modo mais simples, o conjunto-verdade de uma sentença aberta P ( x, y )
em A × B é dado por:
Evidentemente, o conjunto-
verdade de uma sentença aberta Uma sentença aberta
em A × B é sempre
P ( x, y ) P ( x, y ) em A × B torna-
um subconjunto de A × B , ou se uma proposição sempre
que as variáveis x e y
71
seja, VP ⊂ A × B . A seguir,
são substituídas, respectivamente, por
apresentamos alguns exemplos
elementos a ∈ A e b ∈ B .
de sentenças abertas com duas
variáveis e seus correspondentes
conjuntos-verdade.
Exemplo 4
Sejam os conjuntos A = {−2, − 1, 0, 1, 2} e B = {1, 4, 9} . As seguintes
expressões são sentenças abertas com duas variáveis em A × B :
1. P ( x, y ) : x + y ≥ 5
2. Q ( x, y ) : x 2 = y
3. R ( x, y ) : x é divisor de y
4. S ( x, y ) : 3 x + y = 0
Exercício resolvido 2
Determine o conjunto-verdade de cada uma das sentenças abertas do Exemplo 4.
Aula 3 | Tópico 2
Solução
O produto cartesiano A × B é constituído de 5 × 3 = 15 pares ordenados, a saber:
{(−2,1), (−2, 4), (−2,9), (−1,1), (−1, 4), (−1,9), (0,1), (0, 4), (0,9), (1,1), (1, 4), (1,9), (2,1),
(2, 4), (2,9)}.
Matemática Discreta
É fácil perceber que
o conjunto-verdade de uma Uma sentença aberta
sentença aberta P ( x1 , x2 , ..., xn ) P ( x1 , x2 , ..., xn ) em
em A1 × A 2 × ... × A n é A1 × A 2 × ... × A n
torna-se uma proposição
sempre um subconjunto de
sempre que as variáveis x1 , x2 , ...,
A1 × A 2 × ... × A n , ou seja,
e xn são substituídas, respectivamente,
VP ⊂ A1 × A 2 × ... × A n .
por elementos a1 ∈ A1 , a2 ∈ A 2 , ...,
an ∈ A n .
No Exemplo 5, a seguir, 73
apresentamos uma sentença
aberta com três variáveis e determinamos seu conjunto-verdade.
Exemplo 5
Seja = {1, 2, 3, ...} o conjunto dos números naturais. A expressão
P ( x, y, z ) : x + 2 y + 3 z ≤ 10
VP = {( x, y, z ) ∈ × × | x + 2 y + 3 z ≤ 10}
= {(1,1,1), (1,1, 2), (1, 2,1), (1,3,1), (2,1,1), (2,1, 2), (2, 2,1), (3,1,1), (3, 2,1), (4,1,1)}
Finalizamos este tópico com a seguinte observação vista em Alencar Filho (2002,
p. 161)
Neste tópico, tratamos das sentenças abertas com mais de uma variável,
determinando seus conjuntos-verdade. Agora que ampliamos nosso conhecimento
quanto às sentenças abertas, no próximo tópico, veremos como operar com as
mesmas, utilizando os conectivos lógicos que estudamos nas aulas anteriores.
Aula 3 | Tópico 2
Tópico 3
74
OBJETIVOS
Combinar sentenças abertas por meio dos conectivos lógicos
Obter conjuntos-verdade de sentenças abertas diversas
p ( x) : 4 | x (4 divide x ) e q ( x) : x < 20 .
que será satisfeita por todos (e somente por eles) os valores a ∈ que satisfazem
simultaneamente as duas sentenças abertas p(x) e q(x). A exemplo do que foi feito
para proposições, é natural chamar essa nova sentença aberta p ( x) ∧ q ( x ) de
conjunção das sentenças abertas p(x) e q(x).
Matemática Discreta
De modo similar, podemos denir operações com sentenças abertas usando os
conectivos: ¬ (“não”), ∧ (“e”), ∨ (“ou”), → (“se ... então”) e ↔ (“se, e somente
se,”). Assim, dadas as sentenças abertas p(x) e q(x) em A, temos:
1. V p ∧ q = V p ∩ Vq = {a ∈ A | p (a )} ∩ {a ∈ A | q ( a)} .
2. V .
p ∨ q = V p ∪ Vq = {a ∈ A | p ( a )} ∪ {a ∈ A | q ( a )}
3. V¬p = C A V p = C A {a ∈ A | p (a )} .
Aula 3 | Tópico 3
No Exemplo 6, a seguir,
A notação CAB ou apresentamos sentenças abertas
obtidas combinando-se sentenças
C AB , em que A e B são
conjuntos, com A ⊂ B abertas dadas por meio dos
(A é subconjunto de B), conectivos lógicos, bem como
indica o complementar de B em relação a analisamos se um determinado
A, ou seja, é igual ao conjunto A − B . As elemento do domínio da variável
noções de conjuntos e as operações com satisfaz ou não tais sentenças
conjuntos, dentre as quais a diferença e a abertas, ou seja, discutimos se
complementação são objetos de estudo
este elemento pertence ou não
76 da disciplina Matemática básica 1.
aos conjuntos-verdade destas
sentenças. Já no Exercício
resolvido 3, determinamos os conjunto-verdade de algumas sentenças abertas dadas
pela combinação de outras por meio de conectivos lógicos. Vamos lá?
Exemplo 6
Seja = {1, 2, 3, ...} o conjunto dos números naturais. Consideremos as
sentenças abertas em :
p ( x) : x + 1 > 8 , q ( x) : x 2 − 5 x + 6 = 0 e r ( x ) : x é divisor de 3 .
Matemática Discreta
h) não satisfaz a condicional r ( x ) → q ( x ) , isto é, 1 ∉ Vr →q ;
Exercício resolvido 3
Consideremos as sentenças abertas em = {1, 2, 3, ...} :
p ( x) : x + 1 < 7 , q ( x) : x 2 − 14 x + 45 = 0 e r ( x) : x é divisor de 12 .
Solução
5. Vq ↔ r = (C Vq ∪ Vr ) ∩ (C Vr ∪ Vq )
Aula 3 | Tópico 3
6. V¬p∨ ( q ∧ r ) = V¬p ∪ Vq ∧ r = C V p ∪ (Vq ∩ Vr )
Matemática Discreta
Tópico 4
Quantificadores e operações de
quantificação com sentenças abertas
79
OBJETIVOS
Conhecer os quantificadores universal e existencial
Determinar o valor lógico de sentenças abertas quantificadas
Nos tópicos anteriores, vimos uma forma bem simples de transformar uma
sentença aberta em uma proposição – a interpretação ou instanciação da sentença - a
qual consiste na substituição da variável da sentença por um elemento do domínio.
Neste tópico, estudaremos outra forma bem interessante de fazer tal transformação –
através da quanticação. Assim, podemos construir proposições (isto é, sentenças que
podem assumir valor lógico verdade ou falsidade) a partir de uma dada sentença aberta
P, de duas maneiras:
Aula 3 | Tópico 4
1. “Para todo elemento x de A, p(x) é verdadeira (V)”.
2. “Qualquer que seja o elemento x de A, p(x) é verdadeira (V)”.
que é verdadeira (V) quando p(x) é uma condição universal ( V p = A ), e falsa (F)
quando p(x) não é uma condição universal ( V p ≠ A ). Tal proposição é denotada por
(∀x ∈ A)( p ( x)) e lida “para todo x de A, p(x)” ou “qualquer que seja x de A, p(x)”.
Exemplo 7
A proposição (∀ n ∈ )(n + 4 > 3) , em que = {1, 2, 3, ...} é o conjunto dos
números naturais, é verdadeira (V), pois a sentença aberta que a dene p (n) : n + 4 > 3
( V p = {7, 8, 9,} ≠ ).
que V p ≠ ∅ , isto é, p(x) é uma condição possível. Nesse caso, conforme Alencar
Filho(2002), temos
Matemática Discreta
Ou, dito de modo mais simples:
Por questões de simplicidade, desde que não haja dúvidas quanto ao domínio,
podemos omiti-lo e escrever 81
(∃x)( p ( x)) ou ∃x, p ( x) ou ∃x : p ( x) .
Exemplo 8
Exemplo 9
1. ( ∃ | x ∈ ) ( x2 = 4)
2. ( ∃ | x ∈ )( −1 < x < 1)
Aula 3 | Tópico 4
Finalizaremos este tópico
As seguintes implicações observando que a negação
ocorrem: transorma o quanticador
universal em quanticador
existencial e vice-versa, ou seja,
1. ( ∃ | x ∈ A )( p ( x ) ) ⇒ ( ∃ x ∈ A )( p ( x ) )
2. (∀ x ∈ A)( p ( x )) ⇒ (∃ x ∈ A)( p ( x )) transorma o quanticador
existencial em quanticador
As implicações contrárias não ocorrem.
universal. Tais observações, na
verdade, são armações chamadas
82 segundas regras de De Morgan e, simbolicamente, são escritas como:
Desde que não haja dúvidas quanto ao domínio, podemos omiti-lo e escrever
simplesmente
1. ¬[(∀ x)( p ( x ))] ⇔ (∃ x )(¬p ( x )) ;
2. ¬[(∃ x)( p ( x ))] ⇔ (∀ x )(¬p ( x )) .
Matemática Discreta
Exercício resolvido 4
Negar a sentença: ∀ x, x − 1 ≥ 5 .
Solução
¬(∀ x, x − 1 ≥ 5) ⇔ ∃ x, x − 1 < 5 .
Exercício resolvido 5
Negar a sentença: ∃ x, x2 = 1 → x ≠ 0 .
Solução
83
¬(∃ x, x2 = 1 → x ≠ 0) ⇔ ∀ x, ¬( x2 = 1 → x ≠ 0)
⇔ ∀ x, ¬(¬( x2 = 1) ∨ ( x ≠ 0))
⇔ ∀ x, ¬(¬( x2 = 1)) ∧ ¬( x ≠ 0)
⇔ ∀ x, ( x2 = 1) ∧ ( x = 0)
.
Exercício resolvido 6
Negar a sentença: Todos os pescadores são mentirosos.
Solução
Exercício resolvido 7
Negar a sentença: Alguns alunos são estudiosos.
Solução
Aula 3 | Tópico 4
Na Matemática, muitas vezes temos que mostrar que uma proposição do tipo
“Para todo x de A, p(x)”, isto é,
(∀ x ∈ A)( p ( x))
é falsa (F). Da equivalência
(∃ x ∈ A)(¬p ( x))
84 é uma proposição verdadeira (V). Portanto, temos que mostrar que existe pelo
menos um elemento x 0 ∈ A tal que p ( x 0) é uma proposição falsa (F).
Exemplo 10
A proposição (∀ x ∈ )( x2 ≥ x )
Um elemento x0 ∈ A é falsa (F). Um contra-exemplo
tal que p ( x 0) é uma 2
1 1 1
proposição falsa (F) é é o número , pois ≥
2 2 2
chamado contra-exemplo
2
para a proposição (∀ x ∈ A)( p ( x )) . é falsa (F). Os números 0 e
3
também são contra-exemplos.
Verique!
Chegamos ao nal de mais uma aula! Queremos deixar claro que, nessas três
aulas, zemos apenas uma breve introdução ao estudo da Lógica. Entretanto, devemos
ressaltar que os conhecimentos adquiridos aqui serão essenciais para que você possa
ter um bom desempenho em todo o curso. Esperamos que você esteja motivado para
continuar estudando e aprofundar seus conhecimentos.
Matemática Discreta
1. Determine o conjunto-verdade das seguintes sentenças abertas em
A = {1, 3, 4, 7, 9, 11}:
a) x2 < 25 .
b) x2 + 2 ∈ A .
c) | 2 x − 7 | ≥ 5 .
d) x é divisor de 28.
e) x é divisível por 5.
85
2 2
2. Determine o conjunto-verdade da sentença aberta x + y ≤ 4 em
a) × .
b) × .
a) x é par ∨ x | 12 .
b) | x − 2 | < 3 ↔ x 2 − 11x + 30 = 0 .
c) x é primo → ( x − 1) ∈ A .
4. Determine
2
a) o valor lógico (V ou F) da proposição (∃ x ∈ )( x < x ) .
2
b) a negação da proposição (∃ x ∈ )( x < x ) .
a) os conjuntos-verdade de p ( x) e de q ( x) .
b) o conjunto-verdade de p ( x) ∨ q ( x ) .
Pratique
1.
a) V = {1, 3, 4}.
b) V = {1, 3}.
c) V = {1, 7, 9, 11}.
d) V = {1, 4, 7}.
86 e) V = ∅ .
2.
{
a) Considerando = {1, 2,3,...} , V = (1, 1) . }
b) V = {(–2, 0), (–1, –1), (–1, 0), (–1, 1), (0, –2), (0, –1), (0, 0), (0, 1),
(0, 2), (1, –1), (1, 0), (1, 1), (2, 0)}.
3.
a) V = {1, 2, 3, 4, 6}. Condição possível.
b) V = ∅ . Condição impossível.
4.
a) F.
2
b) (∀ x ∈ )( x ≥ x ) .
5.
a) V p = {−6, 0, 3, 6} e Vq = {−6, − 4, − 2, 6} .
b) V p∨ q = {−6, − 4, − 2, 0, 3, 6} .
c) V .
Matemática Discreta
Aula 4
Afirmações e demonstrações
87
Olá, aluno(a)!
Objetivos
Aula 4
Tópico 1
Afirmações na Matemática
88
OBJETIVOS
Perceber a importância da axiomatização na Matemática
Diferenciar afirmações matemáticas demonstráveis e não
demonstráveis
Para iniciarmos esse tópico 1, devemos ter em mente que os princípios básicos
da Matemática (fundamentos da Matemática), ou seja, os modos como ela se
estrutura, suas teorias e os avanços obtidos são objetos de estudo de três correntes
principais de pensamento: logicismo, intuicionismo e formalismo. Todas essas correntes
contribuíram para a evolução da
matemática, sendo marcadas por
O logicismo defendido uma renovação de ideias que são
por Bertrand Russell utilizadas até hoje.
(1872 - 1970) asseverava a
redução da Matemática à Dentre estas contribuições,
lógica. O intuicionismo de Luitzen Brouwer destaca-se a axiomatização da
(1881 - 1966) atribuía primazia à intuição Matemática, apontada pelos
e procurava demonstrar que o saber formalistas como a forma de livrá-
matemático se forma em etapas sucessivas.
la de paradoxos e contradições.
O formalismo representado por David
Hilbert (1862 - 1943) nasceu das conquistas O método axiomático encontra
alcançadas pelo “método axiomático” aplicação praticamente em toda a
e estabelecia que a Matemática poderia Matemática, constituindo-se, hoje,
ser reescrita em sistemas formais, com na técnica básica desta ciência. De
demonstrações rigorosas das verdades
acordo com Almeida (2009),
estabelecidas.
Matemática Discreta
O método axiomático consiste em se escolher certo número
de conceitos básicos não denidos, conhecidos como conceito
primitivos, sucientes para se edicar sobre eles uma teoria
axiomática, e algumas armações sobre estes conceitos, os
axiomas ou proposições primitivas, que também são aceitos sem
demonstração. Em seguida, passa-se a procurar as conseqüências
do sistema assim obtido, sem se preocupar com a natureza ou
o signicado inicial desses termos ou das relações entre eles
existentes. Resultados deduzidos deste sistema de conceitos
primitivos e axiomas são denominados de teoremas.
Aula 4 | Tópico 1
Figura 6 − Esquema da estrutura do método axiomático
90
Fonte: DEaD | IFCE.
Matemática Discreta
Matemática. Em geral, o enunciado de um teorema é composto de duas
partes distintas: hipóteses (conjunto de condições aceitas como verdadeiras)
e tese (verdade lógica que deve ser provada).
Exemplo 1
Se dois ângulos são opostos pelo vértice, então são congruentes.
Aula 4 | Tópico 1
Além da forma de implicação, é também frequente que os teoremas, corolários e
lemassejamequivalênciaslógicas,ouseja,estejamnaforma P ⇔ Q ,oquecorresponde
a dizer que um teorema é uma bicondicional tautológica P ↔ Q , a qual é lida como
“P se, e somente se, Q”. Você, caro(a) aluno(a), a esta altura deve ter percebido que
tal armação corresponde à conjunção das duas condicionais “se P, então Q” e “se Q,
então P”, que simbolicamente é escrito como ( P → Q ) ∧ (Q → P ) . Logo, dizer que
P ⇔ Q , ou seja, que P ↔ Q é uma bicondicional tautológica, corresponde também
a dizer que a conjunção ( P → Q ) ∧ (Q → P ) é também tautológica, ou ainda, que
cada condicional P → Q e Q → P é tautológica. Desse modo, um teorema na forma
92 P ⇔ Q corresponde às duas implicações P ⇒ Q e Q ⇒ P .
Exemplo 2
O produto de dois números inteiros é ímpar se, e somente se, os dois números
são ímpares.
P: a ⋅ b é ímpar
e
Q: a é impar e b é ímpar,
a qual deve ser provada como tautológica. Podemos dizer ainda que esse teorema
corresponde à ocorrência da equivalência lógica P ⇔ Q .
Matemática Discreta
Tópico 2
Tipos de demonstrações
na matemática
93
OBJETIVOS
Compreender a importância das demonstrações na Matemática
Observar as etapas presentes nas demonstrações diretas, por
contraposição, por contradição e por exaustão
Sabemos que um teorema é uma armação declarativa para a qual existe uma
demonstração (prova matemática). Mas anal, o que é uma demonstração? Você já
deve estar curioso(a) para compreender melhor.
Aula 4 | Tópico 2
Há certa piada que ilustra bem essa busca da verdade pelos matemáticos:
Hipóteses
Conjunto das condições ou informações iniciais
que admitimos como verdadeiras.
Demonstração
Deduções tiradas das hipóteses ou de armações verdadeiras
previamente conhecidas usadas para provar a tese.
Tese
Armação que queremos concluir como verdadeira.
Fonte: DEaD | IFCE..
Matemática Discreta
coerente de raciocínios. Mais precisamente, o método dedutivo para demonstrar um
teorema do tipo P ⇒ Q consiste em, assumindo que a proposição P é verdadeira e,
utilizando equivalências lógicas e fatos pré-estabelecidos, deduzir que Q também é
verdadeira. Desse modo, teremos que a condicional P → Q é tautológica e, portanto,
que ocorre a implicação P ⇒ Q . A demonstração direta é o tipo de demonstração
mais comum na Matemática.
Exemplo 3
Se n1 e n2 são números inteiros ímpares, então n1 + n2 é um número inteiro par.
Demonstração
95
É sempre bom iniciar uma demonstração identicando as hipóteses e a tese e
esclarecendo os seus signicados.
Tese: n1 + n2 é um número inteiro par. Assim, queremos provar que existe um inteiro
k tal que n1 + n2 = 2k .
Aula 4 | Tópico 2
2.2 Demonstração por Contraposição
Exemplo 4
Se n é um número inteiro e n 2 é par, então n é par.
Demonstração
Temos:
Hipótese: n é um número inteiro cujo quadrado, n 2 , é par (proposição suposta
verdadeira).
Tese: n é um número inteiro par (proposição que se deseja provar ser verdadeira).
De fato, supondo que n é um número inteiro ímpar, temos que existe um inteiro
k tal que n = 2k + 1 . Dessa forma, n 2 = (2k + 1) 2 = 4k 2 + 4k + 1 que, colocando-se
o fator 2, comum nas duas primeiras parcelas, em evidência, pode ser escrito como
n 2 = 2(2k 2 + 2k ) + 1 = 2k '+ 1 , em que k ' = 2k 2 + 2k é um número inteiro. Assim,
por denição, n 2 é um número inteiro ímpar.
Matemática Discreta
suposição de que ¬Q também é verdadeira, acarreta que ¬P é verdadeira, resultando
que P ∧ ¬P é também verdadeira. Evidentemente, essa é uma contradição, pois,
como já sabemos, não podemos ter uma proposição e sua negação simultaneamente
verdadeiras. A contradição surge do fato de supormos que a negação da tese é
verdadeira, donde segue que a tese é, de fato, verdadeira.
Demonstração
Temos:
Hipótese 1: a é um número racional (proposição suposta verdadeira).
Aula 4 | Tópico 2
Embora, teoricamente, seja necessário analisar todas as possibilidades,
dependendo do problema, podem ser encontrados atalhos que diminuam o número
de casos que se deva testar. Problemas que exigem buscas exaustivas são comuns em
computação e têm impulsionado o desenvolvimento de mecanismos ecientes que
forneçam soluções em tempo razoável.
Exemplo 6
Se n é um número natural par maior que 2 e menor ou igual a 20, então n pode
ser escrito como a soma de dois números naturais primos.
Demonstração
98 Temos:
Hipótese: n é um número natural par tal que 2 < n ≤ 20 (proposição suposta verdadeira).
Essa hipótese corresponde a dizer que n ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20} .
Tese: n pode ser escrito como a soma de dois números naturais primos (proposição
que se deseja provar ser verdadeira). Devemos provar que cada elemento do conjunto
{4, 6, 8, 10, 12, 14, 16, 18, 20} pode ser escrito como p + q , com p e q números
naturais primos (números naturais que têm exatamente dois divisores distintos, o 1 e
o próprio número).
4 = 2+2 10 = 3 + 7 16 = 5 + 11
6 = 3+3 12 = 5 + 7 18 = 5 + 13
8 = 3+5 14 = 7 + 7 20 = 7 + 13
Matemática Discreta
Recentemente, pesquisadores, utilizando supercomputadores, têm mostrado
que a conjectura de Goldbach se verica para números da ordem de 1018 ! Interessante,
não é verdade?
No entanto, devemos tomar muito cuidado ao utilizar essa técnica, pois o famoso
matemático francês Pierre de Fermat (1601-1665), com contribuições importantes na
Teoria dos Números e no Cálculo, andou se aventurando e julgou, por volta de 1640,
ter encontrado uma fórmula que produziria apenas números primos. Sua fórmula era
n
22 + 1 (n número natural), para a qual encontramos:
Aula 4 | Tópico 2
1
22 + 1 = 22 + 1 = 4 + 1 = 5 ,
2
22 + 1 = 24 + 1 = 16 + 1 = 17 ,
3
224 + 1 = 28 + 1 = 256 + 1 = 257 ,
22 + 1 = 216 + 1 = 65 536 + 1 = 65 537 ,
que são todos números primos (verique isto!). Porém, cerca de um século depois,
5
mostrou-se que o quinto número de Fermat, 22 + 1, que resultava em 4 294 967 297,
era um número composto, sendo o resultado do produto de 6 700 417 por 641 . Apesar
do engano, a fórmula de Fermat gerou uma família de números conhecidos como
100 números de Fermat, que aparecem em muitas aplicações da Teoria dos Números.
Matemática Discreta
1. Demonstre, por dedução, esta armação: se n1 e n2 são números inteiros
ímpares, então n1n2 é um número inteiro ímpar.
Pratique
Aula 5
Números naturais
e os axiomas de Peano
102
Olá!
Você certamente deve ter notado que contar consiste, grosso modo, em
associar objetos a números numa determinada ordem. Mas, antes de estabelecer
essa associação, trabalharemos com a sistematização dos números envolvidos nesse
processo.
Você já parou para pensar sobre os números? O objetivo desta nossa aula 5 é
fazer uma discussão sobre os números naturais, estabelecendo regras precisas para a
sua construção. Além disso, juntos desvendaremos como essas regras são usadas para
denir a estrutura ideal para se azer contagem.
Objetivos
Matemática Discreta
Tópico 1
Os axiomas de Peano
103
OBJETIVO
Estudar os axiomas de Peano para os números naturais
Para começar este primeiro tópico de nossa aula 5, vamos pensar: contar signica,
grosso modo, associar objetos a números, não é verdade? Quando dizemos que uma
semana tem sete dias, isso signica que podemos associar os dias de uma semana
aos números de 1 a 7 sem que sobre nem falte nenhum número e de forma que dias
distintos correspondam a números distintos. De maneira mais precisa, estabelecemos
uma bijeção, isto é, uma função que é injetiva e sobrejetiva, entre os dias de uma
semana e os números de 1 a 7. Uma vez que temos bem fundamentada a ideia de
unção e sabemos classicar uma como injetiva ou sobrejetiva, a tarea de contagem
parece ser imediata. Então, o que nos falta para começar, de maneira precisa, a contar?
Veja que interessante, mais uma vez, podemos ilustrar o processo de contagem como
uma associação bijetiva entre conjuntos ao dizer que esta é a quinta aula do nosso
curso, pois é possível associar cada número de 1 a 5 a uma das aulas até a atual. Se
já temos um conjunto para contar
os elementos e já sabemos o que é
uma bijeção, parece não faltar mais Embora, modernamente,
nada, não é? Mas, de fato, falta usemos símbolos
uma noção rigorosa de o que são praticamente unicados
internacionalmente para
os “números de 1 a 7”. Usaremos
representar quantidades, nem sempre
a teoria das funções para elencar
foi assim. Na verdade mesmo, a noção de
algumas regras simples que quantidade e de número foi construída ao
denirão os números naturais. longo de milênios até chegar à formulação
atual, que parece bastante familiar, mas
Você já deve ter observado
apenas porque nos acostumamos a ela.
que os números naturais são
Aula 5 | Tópico 1
os primeiros números com os quais temos contato na infância e, de fato, foram os
primeiros números com os quais a humanidade teve contato.
Uma vez iniciada a contagem com esse número, queremos poder continuar
o processo, de modo que, havendo muitos elementos num conjunto, possamos
atribuir a esses elementos números diferentes de 1 e, além disso, que o processo
de continuar a contagem seja feito de uma única forma. Assim, associaremos a
cada número a ideia de “próximo número”, e essa ideia deve ser tal que todo
número natural tenha um próximo número, sem ambiguidades. Chamaremos
esse “próximo número” de sucessor. Assim, temos o seguinte axioma:
Matemática Discreta
(C) O número 1 não é sucessor de nenhum número natural
Veja que, com esses quatro axiomas, podemos enunciar várias propriedades
sobre os números naturais e começar a contar. Observe que o axioma (A) diz que 1 é 105
um número natural. Usando o axioma (B), podemos garantir que 1 possui um sucessor
e que o sucessor do número 1 também é um número natural. Como o axioma (C) diz
que 1 não é sucessor de qualquer número natural, obtemos que deve haver outro
número natural além do 1. Ao sucessor do número 1 nomeamos usual “dois” e para ele
usamos o símbolo 2. Assim, 1 é um número natural e 2 é um número natural. Usando,
de novo, o axioma (B), temos que 2 possui um sucessor, e o axioma (C) garante que o
sucessor do 2 não é um número 1. Além disso, como 2 é o sucessor do 1, o sucessor do
2 não pode ser o número 2. Vamos resumir essas informações? O sucessor do 2 é um
número natural diferente de 1 e diferente de 2. A esse número natural damos o nome
usual “três” e para ele usamos o símbolo 3. Repetindo o processo para o sucessor do
3, temos que ele deve ser diferente de 1, de 2 e do próprio 3, de modo que deve haver
outro número natural. Ao sucessor do 3 nomeamos usual “quatro” e para ele usamos
o símbolo 4. Podemos continuar o processo e seguir gerando os números (na ordem
usual) 5, 6, 7, 8, 9, e assim por diante. Observe que a expressão “e assim por diante”
está sendo usada aqui para se referir à nomenclatura usual para os números – embora
não haja nomes para todos eles (que nome se dá, por exemplo, ao número 1 seguindo
de quinhentos milhões de zeros?).
De maneira intuitiva, podemos pensar os números naturais como uma la que
tem um ponto de partida (o número 1) e que cada elemento tem um posterior e que
essa la não volta em momento algum.
Os axiomas (A), (B), (C) e (D) já geram uma estrutura bastante interessante e que
pode ser útil nos nossos desejados processos de contagem, porém há uma tecnicalidade
a ser considerada: como garantir que todos os números naturais estão nessa “la”? Bem,
os axiomas listados até agora não garantem que, partindo do número 1 e tomando os
sucessores, podemos chegar a qualquer número natural. Esses números que não são
atingidos por esse processo nunca seriam utilizados numa contagem e, portanto, se
existirem, seriam supérfuos. Com o objetivo de eliminar esses números desnecessários,
Aula 5 | Tópico 1
a m de ter uma estrutura mínima com a qual trabalharemos, instituiremos um novo
axioma, que garante que todo número pode ser alcançado a partir do 1, considerando-
se sucessores. De maneira mais precisa, temos o próximo axioma:
(E) Seja uma coleção de números naturais que possui a seguinte propriedade:
sempre que um número natural está nessa coleção, o sucessor desse
número também está nessa coleção. Se o número 1 estiver nessa coleção,
essa coleção é formada por todos os números naturais.
Embora pareça mais complicado que os axiomas anteriores, esse último nos
permitirá provar propriedades sobre todos os números naturais. Do contrário,
106 provaríamos apenas atos sobre a “la” que começa no 1.
Agora vamos imaginar um campo. Suponha que nesse campo tenha um “pé”
de manga no qual você escreveu seu nome, ok? Suponha, ainda, que, de cada árvore
desse campo, parta um caminho que pode ser percorrido num único sentido e que
termina em outra árvore. Compreendido até aqui? Além disso, suponha que nenhum
caminho tem como ponto nal o pé de manga com seu nome e que não haja dois
caminhos dierentes que chegam a uma mesma árvore. Tudo certo? Por m, imagine
que, partindo do “pé” de manga com seu nome e usando esses caminhos, você
possa chegar a qualquer árvore desse campo. Agora relacione os números naturais
às arvores desse campo e verique que todas as condições de (A) a (E) são satisfeitas.
Interessante, não é?
Matemática Discreta
Tópico 2
107
OBJETIVO
Entender os axiomas de Peano por meio da teoria das funções
Aula 5 | Tópico 2
Dessa forma, denotando por o conjunto dos números naturais, os Axiomas
de Peano podem ser escritos, utilizando a notação matemática, da seguinte maneira
concisa:
(P) 1∈ .
(Q) Existe uma função injetiva s : → \ {1} .
(R) Se um conjunto X ⊂ é tal que valem
(*) 1 ∈ X
(**) se n ∈ X , então s (n) ∈ X ,
108 então X = .
Com essa notação, temos que s (1) = 2 . Além disso, s ( s (1)) = s (2) = 3 , também
s (s( s (1))) = s(3) = 4 , e assim por diante.
Demonstração
Matemática Discreta
(*) e (**) descritas no Princípio da Indução. De maneira bem clara, temos que 1 ∈ X .
Resta mostrar a condição (**). Para tal, suponhamos que um certo número natural n
seja elemento de X e provemos que s (n) também é elemento de X . De fato, se n
é elemento de X , então n é um número natural e, portanto, s (n) é um elemento de
A. Daí, s (n) ∈ X . Assim, o conjunto X é um subconjunto de números naturais que
cumpre as condições (*) e (**) e, portanto, X = , o que termina a demonstração.
Vimos que o sucessor do 2 não podia ser o próprio 2, isto é s (2) ≠ 2 . De maneira
análoga, argumentamos que s (3) ≠ 3 . Se uma certa propriedade é válida para alguns
números naturais, camos tentados a armar que ela vale para todos os números
naturais. Por mais que testemos para vericar que s (4) ≠ 4 e s (5) ≠ 5 , ainda não
é suciente para armar sobre todos os números naturais. Na verdade, podemos
avançar o quanto quisermos nesses testes com números xados e, ainda assim, não
será o suciente para garantir que o teste se mostraria verdadeiro na etapa seguinte.
Aí entra a genialidade e a simplicidade do Princípio da Indução. Se você prova que uma
certa condição é satisfeita pelo 1 e que, sempre que um número satisfaz essa condição,
seu sucessor também a satisfaz, você tem que a condição é satisfeita para o sucessor
do 1, isto é, para o 2. Repetindo o argumento, você tem que a condição é válida para o
sucessor do 2, isto é, para o 3. De forma precisa e genérica, temos um argumento que
garante a validade dessa condição para todos os números naturais, sem que apelemos
para expressões como “e assim por diante” ou “e assim sucessivamente” para validar
nosso argumento.
Aula 5 | Tópico 2
Demonstração
Nesse caso, note que temos uma propriedade a ser demonstrada para todos os
números naturais, de modo que o conjunto a ser construído pode ser simplesmente
o conjunto de todos os números naturais que têm essa propriedade. Façamos, então,
X = {n ∈ ; s (n) ≠ n} . A proposição cará provada se vericarmos que X = .
Para tanto, basta vericar que X tem as propriedades (*) e (**) listadas no Princípio
da Indução. Como 1 não é o sucessor de nenhum número natural, vale que s (1) ≠ 1
e, portanto, 1 ∈ X e, assim, (*) é satisfeita para X . Agora, se n é um elemento de
X , vale s (n) ≠ n . Uma vez que a função sucessor é injetiva e s (n) ≠ n , temos que
110 s ( s (n)) ≠ s (n) , donde concluímos que s (n) é diferente do seu sucessor, ou seja,
s (n) ∈ X . Assim, vericamos que, para todo número natural n, se n ∈ X , então
s (n) ∈ X e, assim, (**) é satisfeita para X . Dessa forma, vale que X = , o que
comprova que nenhum número natural é sucessor de si mesmo.
Matemática Discreta
Tópico 3
111
OBJETIVOS
Estudar a adição entre números naturais
Compreender as principais propriedades da adição
entre números naturais
Você deve lembrar que, nos tópicos anteriores, xamos uma estrutura rígida
chamada de conjunto dos números naturais, denida a partir de uma unção sucessor
com certas propriedades, dentre as quais destacamos que nenhum número é seu
próprio sucessor. Neste tópico 3, estudaremos as operações para essa estrutura. De
maneira geral, uma operação sobre um conjunto V é uma função que associa pares de
elementos de V a um elemento de V. Para começar, deniremos a adição de maneira
bem sucinta e veremos que essa denição dá a essa operação propriedades muito
boas para que o conjunto dos números naturais sirva bem aos propósitos de contagem
a serem explorados na próxima aula. O resultado da adição entre os números m e n,
nesta ordem, será denotado por m + n.
Para que possamos denir, de orma precisa, algo sobre o conjunto dos números
naturais, é suciente dizer o comportamento desse objeto para o número 1 e, supondo
denida a inormação para o número natural m, fornecer uma maneira de obter essa
informação para s(m). Em relação à adição, usaremos essas duas etapas. A primeira coisa
que queremos em relação à adição é que somar o número um signique obter o próximo
número, isto é, o sucessor. Assim, m + 1 será denido simplesmente como s(m).
Aula 5 | Tópico 3
Como colocamos s(n) para ser igual a n + 1, então queremos que m + s(n) seja igual a
m + (n + 1). De modo a essa operação ter propriedades interessantes (associatividade,
por exemplo), gostaríamos que essa última expressão pudesse ser reescrita como
(m + n) + 1, mas isso é exatamente o sucessor de m + n. Nesse sentido, pode surgir a
ideia de que isso não dene bem a adição, pois apenas transere o problema de calcular
m + k para calcular m + n. Mas, repetindo o processo, certamente chegaremos ao
ponto em que teríamos que calcular apenas m + 1, o que já oi denido anteriormente.
Perceba que estamos agora de posse das informações que sugerem, de forma
bastante precisa, uma maneira de realizar a adição de números naturais. Denimos,
112 então, para os números naturais m e n o seguinte:
m + 1 = s(m)
Exemplo 1
Exemplo 2
Matemática Discreta
Dessa forma, poderíamos calcular diretamente 3 + 5 da seguinte forma:
3 + 5 = 3 + (4 + 1) =
= (3 + 4) + 1 =
= (3 + (3 + 1)) + 1 =
= ((3 + 3) + 1) + 1 =
= ((3 + (2 + 1)) + 1) + 1 =
= (((3 + 2) + 1)) + 1) + 1 =
= (((3 + (1 + 1)) + 1) + 1) + 1 =
= ((((3 + 1) + 1) + 1) + 1) + 1 =
= (((4 + 1) + 1) + 1) + 1 =
113
= ((5 + 1) + 1) + 1 =
= (6 + 1) + 1 =
= 7+1=
= 8
Aula 5 | Tópico 3
Assim, vejamos as principais propriedades sobre a adição de números naturais.
Demonstração
Assim como nas demonstrações do tópico anterior, faremos uso do Princípio
da Indução. Para tal, considere o conjunto X formado por todos os números naturais
114 c para os quais vale (a + b) + c = a + (b + c), para quaisquer a e b naturais. Se
mostramos que X = , o teorema ca demonstrado. Observe, inicialmente, que, por
denição, para quaisquer números naturais, vale (a + b) + 1 = a + (b + 1) e, portanto,
é verdade que 1 ∈ X , isto é, a condição (*) é satisfeita. Suponha que n ∈ X , isto é,
suponha válida a igualdade (a + b) + n = a + (b + n), para quaisquer números naturais
a e b. Temos que, para quaisquer números naturais a e b, vale
= (a + (b + n)) + 1 = (pois 1 ∈ X )
= ((a + b) + n) + 1 = (pois n ∈ X )
= (a + b) + (n + 1) (pois 1 ∈ X )
Assim, n + 1 ∈ X ,istoé,acondição(**)ésatisfeita,oqueencerraademonstração.
Demonstração
Começaremos mostrando que a propriedade é válida para b = 1. Para tanto,
devemos mostrar que a + 1 = 1 + a , para todo número natural a. Aqui usaremos indução.
Considere Y o conjunto dos números naturais a para os quais vale a + 1 = 1 + a . É óbvio
que 1 + 1 = 1 + 1, donde obtemos que 1 ∈ Y . Suponha que n seja um elemento de
Y, isto é, que n + 1 = 1 + n. Temos, nesse caso, que
(n + 1) + 1 = (1 + n) + 1 = (pois n ∈ Y )
Matemática Discreta
Assim, n + 1 ∈ Y e, portanto, Y = . Dessa feita, 1 comuta na adição com
todos os números naturais. Se denotarmos por X o conjunto de todos os naturais que
têm essa propriedade, isto é, se colecionarmos em X todos os números b, tais que
a + b = b + a, para todo natural a, vale que 1 ∈ X . Suponha, agora, que n seja um
elemento de X , isto é, que a + n = n + a, para todo natural a. Teremos, para todo
natural a, que
Demonstração
Veja que a propriedade do cancelamento também vale à direita, e isso pode ser
justicado diretamente da comutatividade da adição dos números naturais.
Aula 5 | Tópico 3
Demonstração
Até breve!
Matemática Discreta
Tópico 4
117
OBJETIVOS
Estudar a multiplicação entre números naturais
Compreender as principais propriedades da multiplicação entre
números naturais
Neste tópico, seguiremos a linha do que foi feito no tópico anterior em relação
à adição de números naturais. Assim, aqui deniremos a multiplicação desses em duas
etapas: primeiro, veremos como multiplicar por 1 e, em seguida, como fazer com os
demais números naturais. O resultado da multiplicação entre os números m e n, nessa
ordem, será denotado por m.n ou, quando não houver risco de confusão, simplesmente
por mn.
Aula 5 | Tópico 4
Estamos agora de posse das informações que sugerem, de forma bastante
precisa, uma maneira de realizar a multiplicação de números naturais. Denimos,
então, para os números naturais m e n o seguinte:
m.1 = m
m.(n + 1) = m.n + m.
Exemplo 4
3.5 = 3.(4 + 1) =
= 3.4 + 3 =
= 3.(3 + 1) + 3 =
= 3.3 + 3 + 3 =
= 3.(2 + 1) + 6 =
= 3.2 + 3 + 6 =
= 3.(1 + 1) + 9 =
= 3.1 + 3 + 9 =
= 3 + 12 =
= 15.
Matemática Discreta
Perceba que, assim como no
A multiplicação de
caso da adição, poderíamos pensar
números naturais também
em fazer 5.3 para obter 3.5 (se você
goza das propriedades
calcular 3.5 seguindo a ideia do associativa e comutativa
Exemplo 4, obterá, igualmente, o e também vale o
número 15), mas devemos nos ater cancelamento.
às propriedades demonstradas.
Demonstração
Usaremos aqui livremente a associatividade e a comutatividade tanto da
adição quanto da multiplicação. Seja X o conjunto dos números naturais c tais que
( a + b ) ⋅ c = a ⋅ c + b ⋅ c , para todos os naturais a e b. Mais uma vez, usando o Princípio
Aula 5 | Tópico 4
da Indução, o teorema estará mostrado se vericarmos que 1 ∈ X . Nesse sentido,
observemosque,paraquaisquernúmerosnaturais a e b,vale ( a + b ) ⋅1 = a + b = a ⋅1 + b ⋅1
e, portanto, 1 ∈ X . Suponha que o número natural n é um elemento de X, isto é, que
( a + b ) ⋅ n = a ⋅ n + b ⋅ n , para quaisquer naturais a e b. Temos, assim,
( a + b ) ⋅ ( n + 1) = ( a + b ) ⋅ n + ( a + b ) = (pela denição de multiplicação)
= a⋅n +b⋅n + a +b = (pois n ∈ X )
= a⋅n + a +b⋅n +b = (pelas propriedades da adição)
= a ⋅ ( n + 1) + b ( n + 1) = (pela denição de multiplicação)
2x + 3 = 7 ⇔ 2x + 3 = 4 + 3 ⇔ (pois 7 = 4 + 3)
⇔ 2x = 4 ⇔ (pelo cancelamento na adição)
⇔ 2x = 2.2 ⇔ (pois 4 = 2.2)
⇔ x=2 (pelo cancelamento na multiplicação)
Matemática Discreta
Tópico 5
121
OBJETIVOS
Conhecer a relação de ordem dos números naturais
Compreender as principais propriedades da relação de ordem dos
números naturais
Neste último tópico de nossa aula, devemos compreender que, uma vez denidas
as operações de adição e multiplicação de números naturais, a próxima etapa consiste
em denirmos uma relação de ordem, isto é, um meio para comparar dois números
naturais. A ideia aqui é pedir que, na “la” dos naturais, um número seja menor que
o seu sucessor e isso se propague com o sucessor do seu sucessor. Como tomar o
sucessor de um número pode ser escrito como somar 1 a esse número, podemos
denir que um número é menor que outro quando o segundo puder ser alcançado a
partir do primeiro, usando-se apenas a função sucessor, isto é, apenas a adição.
Caro aluno(a), para tornar a denição acima mais clara, vejam os seguintes
exemplos:
Exemplo 5
Como 4 + 3 = 7, podemos dizer que 4 < 7.
Exemplo 6
Sempre vale n < n + 1, para todo número natural n. Assim, valem 1 < 2, 2 < 3 e
5 < 6. Geralmente, para n e k naturais, sempre vale n < n + k.
Aula 5 | Tópico 5
Exemplo 7
Como todo número natural diferente de 1 é sucessor de algum número natural,
então 1 < n para todo número natural n ≠ 1 .
Você deve estar lembrado, conorme visto no corolário, ao nal do tópico 3, que
não existem naturais n e k, tais que ocorre n = n + k. Assim, nenhum número natural é
menor que ele mesmo, isto é, é sempre falso que n < n.
Demonstração
Se a < b e b < c, vale que b = a + k e c = b + p, para certos naturais k e p. Daí,
temos que c = (a + k) + p = a + (k + p) e, portanto, a < c, como desejado.
Demonstração
A observação feita acima permite concluirmos que duas das relações não ocorrem
simultaneamente. Veriquemos, então, que uma delas ocorre, necessariamente.
Para tal, xado o número a, mostraremos que todo número natural é igual a a,
é menor que a ou é tal que a é menor que ele, isto é, provaremos que o conjunto
X a = {b ∈ ; a < b ou a = b ou b < a} contém todos os números naturais. Como
esperado, usaremos o Princípio da indução. Como 1 < b para todo b natural diferente
Matemática Discreta
de 1, vale X1 = . Suponha que X n = , isto é, que todo número b possa ser
comparado com n. O teorema cará demonstrado se provarmos que X n+1 = . Para
qualquer número natural b, ocorre b < n ou b = n ou n < b. Analisemos cada caso.
Note que, se b < n, e uma vez que n < n + 1, temos que b < n + 1 e, assim,
b pode ser comparado com n + 1. Se b = n, então b < n + 1 e, assim, b pode ser
comparado com n + 1. Dessa forma, nesses dois casos, vale b ∈ X n +1 . Considere,
então, n < b. Isso quer dizer que b = n + k, para certo natural k. Se k = 1, temos
b = n + 1 e, portanto, b ∈ X n +1 . Se k não é 1, vale que k = p + 1, para algum p natural. Daí,
b = n + k = n + (p + 1) = (n + 1) + p e, portanto, n + 1 < b, donde concluímos 123
igualmente que b ∈ X n +1 . Assim, supondo que todos os números naturais podem ser
comparados com n, concluímos que todos os números naturais podem ser comparados
com n + 1 e isso encerra a demonstração.
Demonstração
Sendo a < b, temos que existe um natural k para o qual vale b = a + k. Somando
c aos dois membros dessa igualdade, obtemos b + c = a + k + c, isto é, b + c = a + c + k,
donde concluímos que a + c é menor que b + c. De b = a + k, obtemos também que
bc = (a + k).c = ac + kc e, portanto, vale ac < bc.
Aula 5 | Tópico 5
Demonstração
Se a < b, então a + c < b + c. Se c < d, então b + c < b + d. Daí, pela transitividade
da relação de ordem, temos a + c < b + d. Raciocínio análogo resulta em ac < bd.
Demonstração
124 Se a + c < b + c, então b + c = a + c + k, para certo natural k, isto é, tem-se
b + c = a + k + c e, pela propriedade do cancelamento, b = a + k, donde segue que
a < b. Para a segunda parte, suponha que ac < bc. Se fosse o caso de a = b, teríamos
ac = bc, uma contradição. Se fosse o caso b < a, teríamos bc < ac, uma contradição.
Assim, não vale a = b e nem b < a. Logo, a < b.
Perceba, também, que a relação de ordem pode ser usada para garantir que
certas equações não possuem solução no universo dos números naturais. Por exemplo,
3x + 5 = 2 não tem solução em , pois 3x + 5 é um número necessariamente maior
que 5, isto é 5 < 3x + 5. Como 2 < 5 vale 2 < 3x + 5, para todo número natural x e,
portanto, a igualdade nunca ocorre.
Você deve estar relembrando que, no começo de nossa aula, dissemos que faltava
uma denição rigorosa do que são os números “de 1 a 7”, para que pudéssemos armar
precisamente que os dias da semana formam um conjunto com 7 dias. Podemos, agora,
resolver essa pendência: os números “de 1 a 7” são todos os números naturais que são
menores que 7 ou iguais a 7. Esse tipo de conjunto será a base para os processos de
contagem. Façamos a sua precisa denição, então.
Matemática Discreta
Denição 5.2 Para cada número natural n, denotaremos
por I n o conjunto de todos os números naturais que não
excedem n. Assim, temos
I n = { x ∈ ; x ≤ n}
Demonstração
Seja A é um conjunto que não tem elemento mínimo. Temos que 1 não é um
elemento de A, do contrário, 1 seria o mínimo de A. Assim, 1 é um elemento de \ A .
Assim, {1} ⊂ \ A , isto é, I1 ⊂ \ A . Suponha que, para um número natural xado n,
tenhamos I n ⊂ \ A . Dessa forma, todos os elementos de A são maiores que n, isto
é, n < x, para todo x ∈ A . Assim, vale n + 1≤ x, para todo x ∈ A . Se fosse o caso de
n + 1 ser um elemento de A, teríamos, então, que n + 1 seria o mínimo de A, o que
não ocorre. Assim, n + 1 ∉ A , isto é, n + 1 ∈ \ A . Como I n ⊂ \ A e {n + 1} ⊂ \ A ,
vale I n ∪ {n + 1} ⊂ \ A , ou seja I n+1 ⊂ \ A . Assim, pelo Princípio da Indução, todos
os conjuntos da forma I n estão contidos em \ A , donde concluímos que \ A = ,
o que resulta em A = ∅ . Assim, se um subconjunto de números naturais não possui
elemento mínimo, então ele é o conjunto vazio, e isso é justamente a formulação
contrapositiva do enunciado do teorema.
Aula 5 | Tópico 5
1. Prove que, para todo número natural n, valem as seguintes igualdades:
a) 2.(1 + 2 + … + n) = n.(n + 1)
b) 6.(1.1 + 2.2 + … + n.n) = n.(n + 1).(2n + 1)
a) 10 não é múltiplo de 3.
b) a soma de dois múltiplos de 5 é um múltiplo de 5.
3. Mostre que não existe um natural que é maior que todos os outros
naturais.
Matemática Discreta
Aula 6
127
Olá, aluno(a)!
Vamos contar?
Objetivos
Aula 6
Tópico 1
128
OBJETIVOS
Entender a ideia de contagem
Compreender a relação entre os números naturais e a ideia
intuitiva de contagem
Matemática Discreta
Exemplo 1
Considere N o conjunto dos estados brasileiros da região Norte. Denotando
cada um deles pela sua sigla, temos N = {AC, AM, AP, PA, RR, RO, TO} . Vejamos,
na gura 8, os estados dessa região.
129
Exemplo 2
A cada uma das aulas deste curso de Matemática Discreta foi associado um
número de I8, sem repetir números nem aulas nessa associação. Dessa forma, a maneira
de numerar cada aula (esta, por exemplo, é a aula 6), é uma contagem para as aulas
deste nosso curso e, assim, dizemos que 8 é uma quantidade para as aulas.
Uma primeira observação é que uma contagem para A, como denimos, é uma
bijeção entre In e A, mas, se uma tal bijeção existe, naturalmente sua inversa também
é uma bijeção, de modo que poderíamos ter denido, igualmente, contagem para A
como sendo uma bijeção entre A e In.
Aula 6 | Tópico 1
Uma segunda observação a ser eita sobre a denição anterior trata do uso
do artigo indenido “uma” antecedendo a palavra “quantidade”. Com apenas o que
instituímos não podemos garantir diretamente que um conjunto nito possui apenas
uma quantidade de elementos. Veremos adiante um resultado que atribuímos ao
matemático alemão do século 19, Johann Dirichlet, cuja consequência imediata é que,
se m e n forem ambos quantidades de elementos para o mesmo conjunto, então m = n,
o que justicará o uso do artigo denido e expressões que usaremos a partir de agora,
como “o conjunto B tem k elementos” para dizer que k é a quantidade de elementos
de B, o que responderá a perguntas como esta: “Quantos são?”.
130 Se o conjunto C tem 5 elementos, isso signica que existe uma bijeção
f : I5 → C . Se esse mesmo conjunto tem 8 elementos, isso signica que existe uma
bijeção g : I8 → C . Como g é bijeção, temos que g −1 também é bijeção e, portanto,
g −1 f : I5 → I8 seria uma bijeção, mas veremos, a seguir, que isso não pode ocorrer,
porque 8 > 5.
Demonstração
Seja X o conjunto dos números naturais n para os quais não existe uma função
injetiva f : I m → I n , se m > n. Naturalmente, 1 ∈ X , pois I1 = {1} e não há como
construir uma função injetiva f : I m → I1 , se m > 1 . Suponha, com o objetivo de usar
o Princípio da Indução, que um certo número natural n xado seja um elemento de
X, isto é, que não exista função injetiva f : I m → I n , para nenhum m > n. Analisemos
agora se n + 1 é um elemento de X, isto é, se é possível obter uma função injetiva
f : I m → I n +1 para algum m > n + 1. Suponha que uma tal injeção existe. Nesse
caso, m é diferente de 1 e, portanto, m = k + 1, para certo número natural k e, de
m > n + 1, obtemos que k > n. Assim, teríamos uma função injetiva f : I k +1 → I n +1 .
Se f ( k + 1) = n + 1 , podemos denir uma unção injetiva F : I k → I n colocando
F ( x) = f ( x) , mas aí teríamos uma função injetiva de domínio I k e contradomínio I n ,
com k > n, o que seria uma contradição. Seja, então, b ∈ I n +1 tal que f (k + 1) = b , com
b ≠ n + 1 . Considere a função bijetiva g : I n +1 → I n +1 que troca b por n + 1, isto é, tal
que g (b) = n + 1, g ( n + 1) = b e g ( x ) = x , se x ∉ {b, n + 1} . Nesse caso, se denirmos
h : I k +1 → I n +1 por h( x) = g ( f ( x)) , teremos h injetiva e com a propriedade de que
Matemática Discreta
h(k + 1) = n + 1 , o que já vimos que não pode ocorrer. Dessa forma, não há como
existir uma função injetiva f : I m → I n +1 , com m > n + 1 e, portanto, n + 1 ∈ X , o que
completa a demonstração.
Demonstração
Com isso, temos que os conjuntos nitos possuem uma única quantidade de elementos.
Essa quantidade de elementos para o conjunto A é denotada usualmente por n(a), |A|,
ou card(A). Neste texto, usaremos #A para nos referirmos à quantidade de elementos
do conjunto nito A.
Exemplo 3
É fácil obter uma bijeção entre I7 e o conjunto dos dias da semana. Assim, se S é
o conjunto dos dias da semana, temos #S = 7.
Exemplo 4
Como a função identidade é sempre uma bijeção, temos que #In = n, para todo
n natural.
Se um conjunto A possui um único elemento, isso signica que A é da forma
A = {x}, pois existe uma bijeção entre A e I1 = {1}. Nesse caso, dizemos que o
conjunto A é unitário.
Aula 6 | Tópico 1
Como há uma bijeção
entre o conjunto dos estados Outros exemplos
de contagem são a
da região Norte e o conjunto de
enumeração de páginas
governadores da região Norte,
de um livro ou de seus
podemos dizer que essa região capítulos, a numeração
possui sete governadores, mesmo dos assentos em um ônibus de viagem e a
sem exibir diretamente uma marcação nas raias de uma piscina.
bijeção entre I7 e esse conjunto.
Veja que uma lista de chamada dos alunos de uma turma é uma maneira indireta
132 de fazer a contagem desses alunos, não é? Temos, inicialmente, uma contagem direta
dos nomes completos dos alunos através da associação de um número para cada
nome. Como cada nome completo corresponde a um aluno, então a quantidade de
alunos é igual à quantidade de nomes, já contada pela lista.
Matemática Discreta
do cancelamento, é chamado de diferença entre b e a, nessa ordem, e escrevemos
k = b – a. Assim, denimos uma nova operação entre números naturais, mas que não
é abrangente como a adição e a multiplicação, uma vez que, para calcularmos m – n, é
necessário que n seja menor que m, donde essa operação é claramente não comutativa.
Além disso, ela não é uma operação associativa. Em comum com a adição, a diferença
entre números naturais, quando possível, possui a propriedade do cancelamento,
isto é, vale que, se os números naturais a, b e c, com c < a e c < b, são tais que
a – c = b – c, então a = b. A multiplicação de números naturais também é distributiva
em relação à diferença, isto é, temos a.(b – c) = ab – ac, dado que c < b; e também
vale a compatibilidade da relação de ordem com a diferença, isto é, a < b se, e somente
se, a – c < b – c, dado que c < a e c < b.
133
Usando a diferença entre números naturais, podemos expressar a proposição
anterior nos seguintes termos: se B é um subconjunto de A e valem #B = k e #A = m,
com k < m, então #(A \ B) = m – k.
Assim, chegamos ao nal do tópico inicial de nossa aula. Aqui estudamos a ideia
de contagem e colocamos a estrutura dos números naturais em ação no processo de
contar. Nos próximos tópicos, veremos como operações entre conjuntos (a união, por
exemplo) estão relacionadas com as operações entre números naturais.
Aula 6 | Tópico 1
Tópico 2
134
OBJETIVO
Relacionar a união de conjuntos com a adição de números naturais
por meio do Princípio Aditivo da Contagem
Matemática Discreta
para pensar por que, de fato, usamos a adição, embora o problema não tenha essa
operação em seu enunciado? Veja que, no problema 1, por exemplo, a operação do
enunciado é uma união. Temos o conjunto das laranjas de João e o conjunto das maçãs
que ele possui, e queremos saber uma informação sobre a união desses dois conjuntos.
A mesma operação de união aparece em todos os outros problemas, e não a adição
explicitamente.
Observe que, no problema 5, para dizer que a empresa tem 8 uncionários xos e
7 funcionários temporários, alguém contou os funcionários de cada grupo, certo? Isso
signica, precisamente, que há uma bijeção entre I8 e o conjunto dos uncionários xos
dessa empresa e também uma bijeção I7 e o conjunto dos funcionários temporários. 135
De maneira precisa, para dizer que a quantidade total de funcionários da empresa é
15, alguém deveria unir os dois conjuntos e contar os elementos do novo conjunto
formado, isto é, deveria exibir uma bijeção entre I15 e o conjunto de todos os
funcionários. Observe, caro(a) aluno(a), que, em essência, esse é um procedimento
distinto de simplesmente somar 7 e 8, cujo resultado sabemos ser 15. Sabemos que
não é necessário juntar todo mundo e fazer uma nova contagem.
No problema 6, não é necessário que haja apenas uma catraca para acesso à sala
de exibições do museu para que saibamos o total de visitantes no dia. Para tal, basta
que façamos a conta 94 + 107. Mas, mais uma vez, é preciso saber o que esse número
tem a ver, de fato, com a união dos grupos das pessoas que entraram pelas catracas.
Aula 6 | Tópico 2
Se observarmos bem, notaremos que os números dentro dos parênteses de f
nessa listagem coincidem com os dentro de h, já os de g são 5 a menos, não é? Assim,
se zermos h( x ) = f ( x ) para x ≤ 5 , estamos contando todos os elementos de L e,
se zermos h( x ) = g ( x − 5) para 5 < x ≤ 9 (por exemplo h(8) = g (8 − 5) = g (3) ),
estaremos contando todos os elementos de M. Como f e g são bijeções e L e M não têm
elementos em comum temos que h, dessa forma, é uma bijeção e, portanto, L ∪ M
tem 9 elementos e João tem 9 frutas, como já se sabia desde o começo. Acompanhe
essa construção, no esquema, a seguir.
L∪M f(1) f(2) f(3) f(4) f(5) g(1) g(2) g(3) g(4)
136 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
L∪M h(1) h(2) h(3) h(4) h(5) h(6) h(7) h(8) h(9)
Como última observação nesse problema que retomamos, veja que a diferença
x – 5 sempre faz sentido se x > 5, de modo que usá-la naquela etapa não resulta
em erro. Ademais, esse 5 na diferença é precisamente a quantidade de elementos
de L. Naturalmente, uma vez que a união de conjuntos é uma operação comutativa,
poderíamos ter listados os elementos de L ∪ M colocando primeiro os de M e, em
seguida, os de L. Fica como exercício construir uma bijeção h : I9 → L ∪ M , nesse
caso.
Passemos ao caso geral.
Demonstração
h( z ) = f ( z ) , se 1 ≤ z ≤ m , e
h( z ) = g ( z − m) , se m + 1 ≤ z ≤ m + n
Matemática Discreta
é bem denida, porque, de
fato, para qualquer z ∈ Im+n , O Princípio Aditivo da
Contagem foi enunciado
tem-se que h( z ) é um elemento
até aqui com dois
de A ou de B, mas não de ambos
conjuntos, mas pode ser
simultaneamente, pois A e B são facilmente generalizado
disjuntos (têm interseção vazia). da seguinte forma: a união de conjuntos
Além disso, como f eg são nitos, dois a dois disjuntos, é nita e, além
sobrejetivas, h também o é. Por disso, a sua quantidade de elementos é
m, combinando o ato de A e B igual à soma das quantidades de elementos
serem disjuntos com a injetividade dos conjuntos envolvidos. Para tal, basta
A ∪ B = A ∪ (B \ A) = A ∪ (B \ (A ∩ B))
Aula 6 | Tópico 2
Observe que, nessa última expressão, temos uma união entre conjuntos disjuntos
e, além disso, A ∩ B é um subconjunto de B. Daí, podemos escrever
Se, em vez de dois conjuntos, estivéssemos lidando com três conjuntos nitos
A, B e C, de interseção dois a dois não vazia, teríamos
Uma maneira de memorizar essa fórmula (depois de saber por que ela é
verdadeira, é claro), é pensar que primeiro somamos as quantidades de elementos
de cada um dos três conjuntos, depois subtraímos as quantidades das interseções
duas a duas e, por m, somamos a quantidade de elementos da interseção dos três
conjuntos. Convidamos você, caro(a) aluno(a), a fazer um processo semelhante, mas
naturalmente mais longo, para obter uma expressão para a quantidade de elementos
da união de quatro conjuntos e, em seguida, conjecturar um resultado para n conjuntos.
Com essa fórmula mais geral, encerramos este tópico 2. Nele, vimos, por
meio de problemas e exemplos, como a união e a adição estão relacionadas com
as operações entre números naturais. No próximo tópico, faremos uma pequena
pausa nos processos de contagem para incluir uma tecnicalidade necessária ao bom
desenvolvimento da teoria.
Matemática Discreta
Tópico 3
139
OBJETIVOS
Compreender a ideia de 0 (zero)
Incluir o subconjunto vazio na categoria dos conjuntos finitos
Você deve recordar, caro(a) estudante que todo subconjunto não vazio de
um conjunto nito é nito. Como o vazio é subconjunto de qualquer conjunto, seria
interessante incluí-lo na categoria dos conjuntos nitos a m de evitar car sempre
fazendo essa ressalva, esse é o foco principal deste tópico.
Aula 6 | Tópico 3
também 0 + 0 = 0 . Podemos, através de uma vericação imediata, obter que essa
regra não perturba as propriedades comutativa, associativa e nem de cancelamento da
adição. Assim, a adição denida sobre ∪ {0} é uma operação comutativa, associativa
e com elemento neutro.
Vejamos como estender a multiplicação dos naturais para que ela passe a ser
uma operação sobre ∪ {0} . Como 0 oi incluído inicialmente com ns de manter
propriedades da adição, usemos a ligação entre a adição e a multiplicação, que é a
propriedade distributiva. Para manter essa propriedade, deveríamos ter, para todo
natural n , que n = 1.n = (1 + 0).n = 1.n + 0.n = n + 0.n . Assim, queremos que, para
140 todo natural n , valha n = n + 0.n , mas essa foi exatamente a propriedade que
motivou a adição com parcela 0. Assim, com ns de manutenção de propriedades, para
qualquer número natural n, deniremos 0.n = n.0 = 0 . Denimos, também, 0.0 = 0 .
Uma vericação imediata nos permite concluir que essa regra dene uma operação
sobre ∪ {0} , que é comutativa, e associativa, mas para a qual não vale a lei do
cancelamento no caso de o fator a ser cancelado ser igual a 0, pois essa denição az
m.0 = n.0 , para quaisquer m e n naturais.
Matemática Discreta
Princípio Aditivo da Contagem continuam valendo, mesmo que algumas interseções
sejam vazias, bastando que convencionemos como no começo do tópico: # ∅ = 0 .
Aula 6 | Tópico 3
Tópico 4
142
OBJETIVOS
Relacionar a multiplicação com os processos de contagem
Estudar a quantidade de elementos do produto cartesiano de
conjuntos finitos
1) Fernando tem 3 caixas e em cada uma das caixas há 4 bilas. Quantas bilas
Fernando tem?
2) Numa sala há 5 las com 6 cadeiras cada. Quantas cadeiras há nessa sala?
3) Foram gravadas 8 temporadas de uma série, cada uma das quais com 12
episódios. Quantos foram os episódios dessa série?
4) Cada guia de uma reserva forestal pode conduzir grupos de até 12 pessoas.
Se o parque tem 7 guias, quantas pessoas poderão ser conduzidas ao mesmo
tempo nesse parque?
Matemática Discreta
como a união dos conjuntos das bilas de cada uma das caixas. Assim, sendo
C1 , C2 e C3 as caixas de bilas, temos # C1 = # C2 = #C3 = 4 e, portanto,
#(C1 ∪ C2 ∪ C3 ) = # C1 + # C2 + # C3 = 4 + 4 + 4 = 12 . Alternativamente, para obter
4 + 4 + 4 , poderíamos ter escrito 1.4 + 1.4 + 1.4 = (1 + 1 + 1).4 = 3.4 .
Lembremos que o conjunto dos pares ordenados que pode ser formado com
abscissa sendo um elemento do conjunto A, e com ordenada sendo um elemento do
conjunto B, é denotado por A × B . Assim, o conjunto I8 × I12 possui 96 elementos. Mais
geralmente, temos que se m e n são números naturais, o conjunto I m × I n possui m.n
elementos. Para ver isso, observe que, para cada natural k , com 1 ≤ k ≤ m , o conjunto
J k = {k} × I n , que é formado por todos os pares de I m × I n que possuem abscissa igual
a k, possui n elementos, pois podemos escrever J k = {( k ,1)} ∪ {( k , 2)} ∪ ... ∪ {( k , n)} ,
Aula 6 | Tópico 4
isto é, I k é uma união de n conjuntos unitários e, portanto, possui n elementos. Como
I m × I n = J1 ∪ J 2 ∪ ... ∪ J m , vale que I m × I n é a união de m conjuntos com n elementos
cada e, portanto, possui m.n elementos.
144
Princípio Multiplicativo da Contagem (segunda versão): Se A e B são conjuntos
nitos, então #(A × B) = # A.# B .
Matemática Discreta
fatos sobre potências de expoente natural: se a, m e n são números naturais, então
a m .a n = a m + n e (a m ) n = a mn .
Exemplo 5
Aula 6 | Tópico 4
Exemplo 6
Usando os dígitos 0,1, 2,...,9 , podemos criar 106 senhas distintas de seis dígitos,
pois a escolha de uma tal senha consiste em seis etapas de escolha de um dígito dentre
os nove possíveis. Vejamos essas etapas na Figura 9 .
146
Você sabia que, se digitássemos uma dessas senhas a cada segundo, levaríamos
mais de 11 dias para digitar todas elas? Sabia também que, se quiséssemos imprimir
todas essas senhas, colocando 150 por página, precisaríamos de mais de 6 mil páginas
para ter todas no papel?
Caro(a) estudante, com todos esses exemplos, você deve ter percebido
a relevância do processo de contagem nos estudos de Matemática. Além disso,
teve uma noção das aplicações desse tema para muitos problemas do cotidiano.
Assim, nalizamos este tópico após, por meio dele, compreender a relação entre a
multiplicação e o processo de Contagem. No próximo tópico, daremos continuidade a
esse assunto, determinando a quantidade de contagens para um dado conjunto, bem
como teremos a ideia de fatorial de um número. Até lá!
Matemática Discreta
Tópico 5
A quantidade de contagens
de um conjunto
147
OBJETIVOS
Estudar as permutações para um dado conjunto
Compreender a definição de fatorial de um número
Exemplo 7
Você já parou para pensar sobre quantas são as contagens que podemos fazer
de um determinado conjunto com n elementos?
Para começar a atacar esse problema, observemos que, xada uma bijeção
f : I n → A , para cada outra bijeção g : I n → A , a função g −1 f : I n → I n
, é uma bijeção. Assim, cada contagem de A corresponde a uma bijeção entre I n
e I n e, portanto, podemos contar as contagens de A de forma indireta através da
determinação da quantidade de bijeções entre I n e I n , que pode ser pensada
Aula 6 | Tópico 5
apenas como uma troca na ordem dos números de 1 a n . Por essa razão, chamamos
cada bijeção dessas de uma permutação de I n , ou ainda de uma permutação de n
elementos. O conjunto de todas as permutações de n elementos é denotado por Sn ,
ou seja, Sn = { f : I n → I n ; f é uma bijeção} .
Suponha que seja conhecida uma expressão para #Sn e vejamos como
encontrar uma expressão para #Sn+1 . Uma bijeção h : I n +1 → I n +1 pode ser obtida se
seguirmos duas etapas: primeiro determinamos h(1) e, em seguida, determinamos
as imagens dos demais elementos, mas isso corresponde a fazer uma bijeção entre
I n +1 \{1} e I n +1 \{h(1)} , que são dois conjuntos com n elementos. Assim, podemos
pensar essa segunda etapa simplesmente como uma permutação de n elementos.
Dessa forma, essa segunda etapa pode ser realizada de #Sn maneiras diferentes.
Matemática Discreta
1! = 1
(n + 1)! = (n + 1).n !, para todo n natural.
A segunda parte da denição pode ser acilmente substituída por n ! = n.( n − 1)! ,
para todo natural n > 1 .
Aula 6 | Tópico 5
Neste último tópico de nossa aula 6, ampliamos nossos conhecimentos sobre os
processos de contagem. Deve ter sido interessante para você perceber como a noção
de fatorial de um número natural n está relacionada com a ordenação dos elementos
de um conjunto com n elementos
Matemática Discreta
1. Se A e B são conjuntos com 7 e 3 elementos, respectivamente, determine
a) a quantidade de funções f : A → B.
b) a quantidade de funções f : A → B que são injetivas.
Pratique
1. # ( A ∩ B ) pode assumir os valores 0, 1, 2 e 3
2. # ( E \ D ) = # E − # ( D ∩ E ) = # E − # D = 7 − 1 = 6
152 3.
a) 710
b) 10!/3!
Matemática Discreta
Aula 7
Contagens, arranjos,
combinações, Triângulo de Pascal
e o Binômio de Newton
153
Objetivos
Aula 7
Tópico 1
Arranjos, combinações
e problemas de contagem
154
OBJETIVOS
Aplicar o Princípio Multiplicativo da Contagem a alguns problemas
Estudar arranjos e combinações
Exemplo 1
Exemplo 2
Matemática Discreta
consiste em escolher a primeira letra, depois a segunda e, por m, a terceira. Em cada
uma dessas etapas, temos 26 possibilidades.
Exemplo 3
Aula 7 | Tópico 1
contando os anagramas duas vezes, de modo que o número correto de anagramas da
palavra GEOMETRIA não é 9!, mas sim 9!/2 = 181 440, compreendido? Da mesma
forma, na palavra CAMADA, a ideia inicial levaria a 6! anagramas, mas como as letras
A podem trocar de lugar sem gerar novas palavras, estaríamos contando palavras
repetidas. Mais precisamente, como são 3 letras A, elas podem trocar de posição entre
si de 3! maneiras diferentes, de modo que o total correto é 3! vezes menor que 6! e,
portanto, a palavra CAMADA não tem 6! anagramas, mas sim 6!/3! = 120. Se houver
mais de uma letra repetida, podemos pensar da mesma forma, certo? Em INSTITUTO
temos uma palavra de 9 letras, sendo duas delas I e três delas T. Assim, considerar 9!
o número de seus anagramas é contar acima do número correto. Como são três letras
156 T, e duas letras I, temos que o total correto é 3!.2! vezes menor que 9!, isto é, temos
que INSTITUTO possui 9!/(3!.2!) anagramas.
Exemplo 4
Na aula 6, vimos que, se m > n, não há função injetiva f : I p → I m . Tal fato foi
enunciado como o Teorema de Dirichlet, mas também podemos referenciá-lo como
Princípio da Casa dos Pombos, pois podemos usar o Teorema de Dirichlet para garantir
que, se colocarmos 11 pombos em 10 casas, uma casa terá pelo menos dois pombos,
certo? Agora, se tivermos menos pombos que casas, não só podemos garantir uma
maneira de colocar cada pombo sozinho em uma casa, mas também temos como
saber de quantas maneiras isso pode ser feito. Acompanhe o seguinte raciocínio para
4 pombos em 9 casas. Colocá-los nas casas é um procedimento de quatro etapas:
cada uma das quais consiste em alocar um pombo. Para o primeiro pombo, temos
9 possibilidades. De modo a não colocar dois pombos na mesma casa, ao escolher a
casa do segundo pombo, temos apenas 8 possibilidades (lembre que uma das casas já
está ocupada). Para o terceiro pombo, são 7 casas disponíveis (as 9 iniciais menos as
duas ocupadas pelos primeiros pombos). Por m, o quarto pombo terá 6 casas para
escolher.
Figura 11 − Possibilidades de alocar quatro pombos dentre nove casas disponíveis
Matemática Discreta
Assim, o total de possibilidades de alocar 4 pombos em 9 casas sem colocar
dois na mesma casa é 9.8.7.6. Observe que esse resultado é o começo do cálculo de
9!, faltando 5.4.3.2.1 para completá-lo. Assim, podemos escrever o total de maneiras
segundo as quais 4 pombos podem ocupar algumas dentre 9 casas por 9!/5!.
Caro(a) cursista, com essa ideia e essa fórmula em mente, podemos agilizar
alguns problemas de contagem. Enunciaremos o que acabamos de demonstrar.
Aula 7 | Tópico 1
Antes de ver como aplicar essa fórmula, vale observar que, caso p = n, ela
também é válida, já que denimos 0! = 1.
Exemplo 5
Figura 12 − Número de pódios para premiar oito atletas com medalha de ouro, prata ou bronze
Matemática Discreta
Exemplo 6
Exemplo 7
Uma turma de dez alunos tem aula em uma sala com quinze cadeiras. Se
quisermos saber de quantas formas os dez alunos podem ocupar essas quinze cadeiras,
podemos pensar que há algo errado se usarmos diretamente a fórmula para n = 10
e p = 15, pois 10 – 15 = –5 e não denimos atorial de número negativo. Porém, 159
cada conguração de alunos nessa sala pode ser pensada como uma unção injetiva
do conjunto dos alunos no conjunto das cadeiras, isto é, um arranjo de 15 objetos em
10 posições. Observe que, nesse caso, cada cadeira está sendo pensada como objeto
e cada aluno como uma posição, compreendido? Com essas considerações, usaremos
15! 15!
a fórmula de arranjos simples com n = 15 e p = 10. Assim, há A15,10 = = .
(15 – 10 )! 5!
Naturalmente, podemos calcular esse número, mas podemos expressá-lo assim
mesmo, o que evidencia como a notação de atorial simplica algumas repostas,
principalmente nos problemas de contagem.
Exemplo 8
Aula 7 | Tópico 1
Figura 13 − Exemplo de triângulo inscrito em circunerência com 10 pontos
160
Exemplo 9
Matemática Discreta
de n elementos, podemos formar A n , p sequências de p termos. Se quisermos os
subconjuntos, observamos que cada uma dessas sequências tem os mesmos termos,
mas em outras posições que outras sequências. Um grupo de p elementos pode ser
disposto em p! sequências, isto é, no total de sequências, cada grupo aparece p!
vezes, de modo que o número de subconjuntos de p elementos de um conjunto com n
A n,p
elementos é, portanto, .
p!
Cada um desses subconjuntos é chamado de Combinação simples de n objetos
tomados p a p. Podemos deixar esse número ainda mais explicitamente em função de
n e p da seguinte forma:
161
A n,p n !/ ( n − p ) ! n!
= = . Assim, acabamos de demonstrar o seguinte
p! p! ( n − p )! p !
resultado.
Exemplo 10
Um conjunto com 9 elementos possui exatamente C9,4 = 126 subconjuntos
com exatamente 4 elementos.
Exemplo 11
Aula 7 | Tópico 1
lados, isto é, a quantidade de diagonais de um polígono convexo de n lados pode ser
n ( n − 1) n ( n − 1) − 2n n ( n −1 − 2) n ( n − 3)
encontrada por –n= = = .
2 2 2 2
Exemplo 12
Matemática Discreta
Assim, o total de apostas simples que podem ser feitas na Mega-sena pode ser
calculada por meio das combinações, isto é, C60,6 , que é um número maior que 50
milhões. Já notou que não é tão simples de ganhar, não é?
Exemplo 13
Para encerrar este tópico 1, é importante destacar que tanto arranjos quanto
combinações consistem na escolha de alguns elementos de um conjunto, mas devemos
diferenciá-los no sentido de que arranjos são ordenamentos, geram sequências,
ou seja, a ordem dos elementos a serem escolhidos importa na ormação nal, já as
combinações são agrupamentos, geram subconjuntos, ou seja, a ordem dos elementos
a serem escolhidos não interere no resultado nal. Perceberam a dierença? No póximo
tópico, veremos algumas propriedades importantes sobre o número de combinações,
que são os números binomiais. Até breve!
Aula 7 | Tópico 1
Tópico 2
Números binomiais
e o Triângulo de Pascal
164
OBJETIVOS
Compreender o conceito e as relações importantes entre os
números binomiais
Estudar algumas propriedades do Triângulo de Pascal
Caro(a) aluno(a), nas últimas aulas e no tópico anterior, vimos como determinar
a quantidade de elementos de determinados conjuntos de maneira indireta, bem mais
objetiva do que a contagem elemento a elemento. Vimos, também, que, em casos
especícos, podemos escrever as respostas de orma simplicada usando a notação
de fatorial.
Matemática Discreta
Teorema 7.3 Para qualquer número natural n, vale
n
No número binomial , n é dito ser o numerador e p é dito ser o denominador,
p
mas não se deve confundir um número binomial com uma fração. De fato, o número
binomial é sempre um número natural. Por isso, não se pode simplicar diretamente 165
dividindo os termos pelo mesmo número. Como se pode vericar acilmente, vale que
6 3
≠ .
4 2
Exemplo 14
Exemplo 15
n n
Para qualquer número natural n, verica-se acilmente que = = 1 .
0 n
Se os números naturais p e q são tais que p + q = n, vale q = n – p. Daí, podemos
escrever:
n n! n! n! n
= = = = . Nesse caso, dizemos que
p (n − p)! p ! q !( n − q ) ! ( n − q ) !q ! q
n n
os números binomiais e são complementares. Assim, como calculamos
p q
7 7
= 35 , podemos armar que = 35 . Dessa forma, se quisermos calcular todos
3 4
os números binomiais de um certo numerador, só precisamos fazer as contas para
metade deles, pois a outra metade será repetida. Assim, se listarmos todos os números
binomiais de um numerador xado em ordem crescente de denominador, a lista
Aula 7 | Tópico 2
começará e terminará por 1 e pode ser lida de trás pra frente, tendo o mesmo efeito.
Recomendamos que sejam calculados todos os números binomiais de numerador 7
para treinar as contas e vericar esses atos.
Demonstração
n n n! n!
+ = + =
p p + 1 (n − p)! p ! (n − (p +1 ))!(p +1 )!
n! n!
= + =
(n − p)(n − p − 1 )! p ! (n − p − 1 )!(p +1 ).p !
n !.(n+1 ) (n+1 )!
= = =
((n+1 ) − (p +1 ))!(p +1 )! ((n+1 ) − (p +1 ))!(p +1 )!
n +1
= .
p + 1
Vejamos, por meio dos exemplos a seguir, como usar a Relação de Stifel para
simplicar alguns cálculos.
Exemplo 16
Matemática Discreta
12 11 11
Se quisermos encontrar todos os valores de k para os quais = + ,
k 4 5
podemos simplicar o segundo membro, usando a Relação de Stiel para n = 11 e
12 12
p = 4. Assim, a igualdade se torna = , que sabemos ser verdade para k = 5
k 5
e para k + 5 = 12, isto é, k = 7.
Exemplo 17
5 5 6 7
Para determinar o valor de + + + , podemos usar a Relação de Stifel e 167
2 3 4 5
5 5 6 5 5 6 7
perceber que + = , basta fazer n = 5 e p = 3. Assim + + +
2 3 3 2 3 4 5
6 6 7
= + + . Usando novamente a relação de Stifel para as duas primeiras
3 4 5
7 7
parcelas, com n = 6 e p = 3, temos + . Por m, usando mais uma vez a
4 5
8
relação de Stifel, essa soma se resume ao número binomial , o qual vale
5
8! 8.7.6.5! 5 5 6 7
= = 56 . Assim, obtemos que + + + = 56 .
3!5! 6.5! 2 3 4 5
n
em uma linha em ordem crescente de denominador. Como o número binomial só
p
faz sentido se 0 ≤ p ≤ n, a linha que contém todos os números binomiais de numerador
n terá n + 1 elementos (lembre que aqui estamos contando a partir do 0). Por exemplo,
se listarmos sucessivamente para n = 0, 1, 2, 3, 4, 5 e 6, temos:
Aula 7 | Tópico 2
p=0 p=1 p=2 p=3 p=4 p=5 p=6
0
n=0
0
n=1 1 1
0 1
168 n=2 2
2
2
0 1 2
n=3 3 3 3 3
0 1 2 3
n=4 4 4 4 4 4
0 1 2 3 4
Matemática Discreta
n n
Vimos que, para qualquer n natural, vale = . Assim, cada linha começará
0 n
e terminará com o número 1. Para encontrar os números intermediários da tabela,
podemos usar a Relação de Stifel e os elementos da linha anterior, por meio do
esquema a seguir:
169
se tornam, então:
Aula 7 | Tópico 2
p=0 p=1 p=2 p=3 p=4 p=5 p=6
n=0 1
n=1 1 1
n=2 1 2 1
n=3 1 3 3 1
n=4 1 4 6 4 1
170 n=5 1 5 10 10 5 1
n=6 1 6 15 20 15 6 1
7
temos = 21 .
5
Como a soma de todos os números binomiais de um numerador xado é sempre
uma potência de 2 com expoente igual a esse numerador, podemos armar que a soma
de todos os elementos de uma mesma linha do Triângulo de Pascal vale 2k , onde k é o
numerador dessa linha.
Matemática Discreta
Tópico 3
O Binômio de Newton
171
OBJETIVO
Estudar relações entre os números binomiais e potências de somas
de termos
( x + y)2 = ( x + y ) . ( x + y ) = x 2 + xy + xy + y 2 = x 2 + 2 xy + y 2 .
2
( x + y )3 = ( x + y ) .( x + y ) = (x 2
+ 2 xy + y 2 ) . ( x + y ) =
= x 3 + x 2 y + 2 x 2 y + 2 xy 2 + xy 2 + y 3 =
= x 3 + 3 x 2 y + 3 xy 2 + y 3 .
Usando a denição dada na aula 6 para potências de expoente 0, temos
1
( x + y )0 = 1 . Além disso, vale ( x + y ) = x + y. Se listarmos esses produtos,
explicitando todos os coecientes e expoentes de x e de y, nas expressões obtidas
para ( x + y ) n , para n ≤ 3, teremos:
0
Para n = 0, ( x + y) = 1x0 y 0 .
1
Para n = 1, ( x + y) = 1 x1 y 0 + 1 x 0 y1.
2
Para n = 2, ( x + y) = 1 x 2 y 0 + 2 x1 y1 + 1 x 0 y 2 .
3
Para n = 3, ( x + y) = 1 x 3 y 0 + 3 x 2 y1 + 3 x1 y 2 + 1 x 0 y 3 .
Aula 7 | Tópico 3
Além disso, caro(a)
estudante, se revirmos os termos No desenvolvimento
de expressões do tipo
das primeiras linhas do Triângulo
( x + y)n ,
de Pascal, temos exatamente
os mesmos coecientes dos os expoentes de x
aparecem em ordem decrescente
desenvolvimentos anteriores, para
(começando em n e diminuindo uma
cada n.
unidade a cada termo até atingir 0);
Se usarmos a ideia os expoentes de y aparecem em
apresentada nesse último ícone ordem crescente (começando em 0 e
172 Atenção para construir um aumentando uma unidade a cada termo
desenvolvimento semelhante para até atingir n).
n = 4, consultamos, no tópico
anterior, os termos da linha correspondente do Triângulo de Pascal, os quais são 1,
4, 6, 4, 1, nessa ordem. Se multiplicarmos cada um desses coecientes por x, com
potências decrescendo de 4 a 0; e y, com potências crescendo de 0 a 4, e somando
os resultados, teremos a expressão 1.x 4 y 0 + 4.x 3 y1 + 6.x 2 y 2 + 4.x1 y 3 + 1.x 0 y 4
, ou x 4 + 4 x 3 y + 6 x 2 y 2 + 4 xy 3 + y 4 . Pode-se vericar, acilmente, mas com algum
trabalho, que esse é, de fato, o desenvolvimento de ( x + y ) 4 .
Matemática Discreta
6 6 6 6 6 6 6
( x + 2)6 = x 6 20 + x 5 21 + x 4 22 + x 3 23 + x 2 24 + x1 25 + x 0 26
0 1 2 3 4 5 6
6
( x + 2 ) = x 6 + 12 x5 + 60 x 4 + 160 x3 + 240 x 2 + 192 x + 64 , obtido por um processo
mais simples do que fazer a multiplicação de seis fatores iguais a ( x + 2 ) , não acha?
Demonstração
n
Inicialmente, sabemos que ( x + y) = ( x + y ) . ( x + y ) . ... . ( x + y ) ,com o
produto feito com n fatores. Usando a distributividade da multiplicação em relação
à adição, sabemos que cada termo do resultado poderá usar no produto um x ou
um y de cada fator. Assim, cada termo será uma expressão do tipo x m y p , em que m
representa a quantidade de fatores nos quais o termo x foi escolhido, e p representa
a quantidade de fatores nos quais o termo y foi escolhido, certo? Como o total de
fatores é n, temos necessariamente que m + p = n, isto é, vale m = n – p. Além disso,
esses termos aparecem repetidamente, sendo a sua quantidade igual ao número de
maneiras segundo as quais podemos escolher em qual dos fatores selecionaremos y. A
quantidade de parcelas com termos em que aparece y p é, portanto, C n , p , que é igual
n n
a . Daí, será o coeciente de cada termo do tipo x n − p y p , e teremos termos,
p p
dessa forma, para todos os valores de p, com 0 ≤ p ≤ n, o que demonstra o resultado.
Aula 7 | Tópico 3
17
termo do desenvolvimento de ( x + y ) em potências decrescentes de x, usaremos
n
n = 17 e p = 9. Assim, a expressão x n − p y p é o termo de ordem p + 1, denotado
p
n
por Tp+1 , do desenvolvimento de ( x + y ) em potências decrescentes de x.
Exemplo 18
7
Se quisermos o quinto termo do desenvolvimento de ( 2a + 3) em potências
n
decrescentes de x, basta usar a expressão x n − p y p para n = 7, p = 4 (pois queremos
p
7
o quinto termo), x = 2a e y = 3. Assim, o termo procurado T5 é (2a)3 34 . Usando o
4
7
Triângulo de Pascal ou a fórmula para calcular números binomiais, obtemos = 35 .
4
Como 23 = 8 e 34 = 81 , temos que T5 = 35.8a 3 .81 , isto é, T5 = 22 680a 3 .
Exemplo 19
n
Se zermos x = y = 1 no desenvolvimento de ( x + y) , obtemos que
n n n n
(1+1) n = 1n10 + 1n −111 + 1n − 212 + ... + 101n , mas isso é equivalente a
0 1 2 n
n n n n
2n = + + + ... + , que é uma maneira alternativa de demonstrar essa
0 1 2 n
fórmula que conhecemos nos tópicos anteriores.
Matemática Discreta
Tópico 4
Análise combinatória
175
OBJETIVO
Estudar problemas sobre os métodos de contagem e
desenvolvimento do Binômio de Newton
Exemplo 20
Aula 7 | Tópico 4
Exemplo 21
Exemplo 22
As palavras ORIENTAL, ELEFANTE e CIRCULAR possuem, cada uma,
oito letras. A primeira tem todas as letras distintas e, portanto, é uma palavra que
possui 8! anagramas. A segunda possui 3 ocorrências da letra E, e, assim, possui 8!/3!
anagramas. Já a terceira, que possui duas ocorrências de C e duas ocorrências de R,
possui 8!/(2!.2!) anagramas.
Exemplo 23
⇔ (m – 3).(m – 4) = 30 ⇔
⇔ m 2 – 7 m + 12 = 30 ⇔
Matemática Discreta
Exemplo 24
177
Aula 7 | Tópico 4
Exemplo 25
Os funcionários de uma microempresa, dentre os quais Júlia e Augusto, devem
fazer uma viagem para representá-la, mas só há vagas para quatro pessoas. Dentre todas
as possibilidades de escolha dos que viajarão, Augusto observou que há exatamente
28 maneiras para que ele e Júlia viajem juntos. De posse apenas dessa informação, é
possível determinar a quantidade de funcionários da empresa, pois se essa quantidade
for n, inicialmente há C n ,4 possibilidades de escolha para os quatro funcionários que
viajarão. Entretanto, sabemos que, em um grupo no qual Júlia e Augusto viajam juntos,
só há vagas para mais dois funcionários, que devem ser escolhidos entre os restantes,
que são n – 2. Assim, temos a equação C n -2,2 = 28 . Resolvendo-a, obtemos
178
Cn − 2,2 =
( n − 2 )! = 28 ⇔
( ( n − 2 ) − 2 )!2!
⇔
( n − 2 ) ⋅ ( n − 3) ⋅ ( n − 4 )! = 28 ⇔
( n − 4 )!⋅ 2
⇔ ( n − 2 ) ⋅ ( n − 3) = 56
Exemplo 26
5
No desenvolvimento de ( x + 4) , temos uma soma de termos da forma
5
Tp+1 = x 5− p 4 p . Para obter, por exemplo, o coeciente de x 3 , devemos fazer
p
5
5 – p = 3, ou seja, p = 2. Assim, teremos o terceiro termo: T2+1 = x 5− 2 42 = 10 x 3 .16 ,
2
ou seja, o coeciente de x 3 nesse desenvolvimento é 160.
Exemplo 27
6
1
No desenvolvimento de x+ , o termo geral é dado por
x
p
6 6− p 1 6 1 6
Tp+1 = x = x 6− p . p = x 6− 2p . Assim, o termo desse
p x p x p
desenvolvimento, que independe de x, tem expoente de x igual a 0, isto é, é calculado
6
para p = 3. Esse termo vale, portanto, = 20 .
3
Matemática Discreta
Exemplo 28
n
No desenvolvimento de expressões do tipo ( x – y) , podemos fazer
x – y = x + (–y) e aplicar os procedimentos do que já determinamos anteriormente.
7
Assim, para encontrar o sexto termo do desenvolvimento de ( 3 x – 2 ) , fazemos
7
3x – 2 = 3x + (–2), e o termo geral ca Tp+1 = (3x)7 − p (−2) p . Assim, para obter
p
o sexto termo do desenvolvimento em potências decrescentes de
x, devemos fazer p =
7
5, o qual vale T5+1 = (3x)7 −5 (−2)5 , ou seja, 179
5
T6 = 21.(3x) (−2) = 21.9 x .(−32) = −6048 x .
2 5 2 2
Aula 7 | Tópico 4
1. Mostre que sempre vale C n , p ≤ A n , p , para n e p naturais com p ≤ n.
9
1
4. Encontre o termo independente de x no desenvolvimento de x 2 + .
x
Matemática Discreta
2. São 455 planos.
3. k = 3 e k = 2.
9
4. O termo independente de x é = 84 .
6
181
Pratique
Aula 8
Objetivos
Conhecer o problema que motivou a criação da Teoria dos Grafos: as pontes
de Königsberg
Compreender a denição e os principais elementos de um grao
Entender a classicação de um grao quanto à conexidade e à existência de
ciclos
Estudar alguns problemas em que a teoria dos grafos se aplica
Matemática Discreta
Tópico 1
As pontes de Königsberg
183
OBJETIVO
Conhecer o problema que motivou a criação da Teoria dos Grafos
Vejamos, na Figura 16, essas pontes que são sinalizadas pelos retângulos escuros.
Aula 8 | Tópico 1
Figura 16 − Esboço do mapa da região central de Königsberg e suas pontes
184
Para começar, Euler observou que o percurso realizado dentro de cada ilha
ou na margem é irrelevante, a parte signicativa de cada rota é a sequência com
que as pontes são cruzadas. Com isso, ele reformulou o problema eliminando todas
as partes desimportantes, isto é, mantendo apenas uma lista das margens e ilhas
e as pontes que as ligam. Como o tamanho da ilha ou da margem não desempenha
nenhum papel, podemos representar cada uma dessas porções de terra por um ponto.
Matemática Discreta
Assim, cada ponte pode se trocada por uma linha ligando dois desses pontos. Na Figura
17, temos, essencialmente, todos os caminhos a serem percorridos (representados
pelas linhas brancas).
Figura 17 − Esquema simplicado dos caminhos pelas pontes de Königsberg
185
Uma vez feito isso, o rio, as ilhas, as margens, ou qualquer outra coisa da cidade,
se tornam dispensáveis. Dessa feita, estimado(a) estudante, podemos considerar
apenas a Figura 18 para pensar no problema das pontes de Königsberg.
Assim, camos apenas com o que é signicativo. Perceba que cada ponto
representa uma porção de terra e cada linha ligando esses dois pontos representa uma
Aula 8 | Tópico 1
ponte, certo? A quantidade de conexões entre dois desses pontos é que é relevante,
de modo que poderíamos traçar linhas com outras formas ou posicionar os pontos em
outras partes do plano, bem como colocar uma linha que liga dois pontos em outra
posição (abaixo ou acima da posição real da ponte).
Note que os números, assim como os grafos, são uma maneira abstrata de tratar
um problema com o que efetivamente importa. A mesma abordagem para resolver o
problema das pontes poderia ser empregada se, em vez de margens e ilhas, tivéssemos
quatro cidades e, no lugar das pontes, fossem rodovias ligando-as, ou se, em vez das
ilhas, tivéssemos estações de metrô e linhas ligando essas estações, ou átomos e
ligações entre esses átomos, certo? Em essência, a situação é a mesma.
Neste tópico inicial, você conheceu o problema que originou a Teoria dos Grafos.
No próximo tópico, orneceremos uma introdução a essa teoria com denições precisas
e abordaremos as principais partes de um grafo. Até lá!
Matemática Discreta
Tópico 2
187
OBJETIVO
Compreender a definição de grafo e seus principais elementos
Aula 8 | Tópico 2
Denição 8.1 Um grafo consiste de um conjunto, não vazio
e nito, de vértices V e de um conjunto de arestas A com
vértices em V. Nesse caso, escrevemos G = (V, A).
Exemplo 1
Considerando V = {X, Y, Z, W} e A = {{X, Y}, {X, Z}, {X, W}, {Y, Z},
{Z, W}}, temos que G1= (V, A), primeiro grao que estamos exemplicando, que
possui, nesse caso, quatro vértices e cinco arestas.
188 Exemplo 2
Se considerarmos V como o conjunto dos estados da Região Nordeste do Brasil
e A = {{x, y}; x faz divisa com y}, temos que, no grafo G2 = (V, A), existem, por
exemplo, as arestas {Ceará, Pernambuco} e {Sergipe, Alagoas}, mas {Ceará, Alagoas}
não é uma aresta de A.
Observe que a denição de grao apenas lista alguns elementos para serem
vértices e alguns conjuntos com dois elementos para serem arestas. Quando os vértices
a e b são tais que existe a aresta {a, b} no grafo, dizemos que a e b são adjacentes e,
nesse caso, que a e b são as extremidades dessa aresta, que poderá ser denotada por
ab ou ba. Essa é uma das principais informações sobre um grafo. Assim como podemos
usar diagramas para representar conjuntos, também podemos usar um esquema
gráco para representar as inormações de um grao. Para tal, colocaremos um ponto
para indicar cada vértice e uma curva ligando dois vértices que forem adjacentes. Na
Figura 19, temos possíveis representações para o grafo G1do Exemplo 1.
Matemática Discreta
Figura 20 − Uma representação do grao G 2 (do Exemplo 2)
Exemplo 3
Para V = {P, Q, R} e A = {{P, Q}, {P, R}, {Q, R}}, temos que o grafo
G3 = (V, A) é completo e, portanto, seu complemento é o grafo G 3 = ( V, ∅ ) . Na
Figura 21, temos uma representação do grafo G3 (à esquerda) e de seu complemento
(à direita).
190
Figura 21 − Um esquema para o grao G3 (do Exemplo 3) e seu complemento
Exemplo 4
Para V = {1, 2, 3, 4, 5} e A = {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 4}, {4, 5}},
o grafo G4 = (V, A) não é completo e seu complemento é G'4 = {{1, 3}, {1, 5},
{2, 4}, {3, 5}}. Na Figura 22, temos uma representação do grafo G4 (à esquerda) e de
seu complemento (à direita).
Matemática Discreta
Se sabemos quais vértices são adjacentes, então podemos contar quantos
vértices são adjacentes a um vértice dado. O conjunto de todos os vértices de um
grafo G, que são adjacentes ao vértice x, é chamado de vizinhança de x e denotado por
vizG(x). A quantidade de elementos de vizG(x) será chamada de grau do vértice. Mais
precisamente, temos a seguinte denição:
Exemplo 5
No grafo G4, que apresentamos no exemplo anterior, temos que o grau de
vértice é deg(1) = 2, deg(2) = 3, deg(3) = 2, deg(4) = 3 e deg(5) = 2. Assim, G4 não
é regular.
Exemplo 6
Todo grafo completo é
Se um grafo com n vértices
regular, isto é, os seus
é completo, então cada vértice
vértices têm o mesmo grau.
é ligado a todos os outros n – 1
vértices, de modo que seu grau será
n – 1. Dessa forma, um grafo com n vértices é completo se, e somente se, todos os
seus vértices tiverem grau n – 1.
Exemplo 7
Aula 8 | Tópico 2
Dessa forma, a soma dos graus dos vértices de um grafo é sempre um número par. No
caso do grafo do Exemplo 4, que denominamos de G4, a soma dos graus de todos os
vértices é 2.#A = 2.6=12, pois o número de elementos de A é 6. Você pode conferir
esse resultado somando os graus de cada vértice, como apresentamos no Exemplo 5.
Caro(a) aluno(a), com essa ideia inicial, vimos a denição de graos, estudamos
suas principais partes e aprendemos alguns conceitos sobre essa Teoria. No tópico 3,
trabalharemos a noção de caminho em um grao, uma ideia crucial para classicar os
grafos. Até lá!
Matemática Discreta
Tópico 3
Caminhos e conexidade
193
OBJETIVOS
Estudar os grafos conexos
Compreender as principais propriedades de grafos conexos
Aula 8 | Tópico 3
Exemplo 9
No grafo G 2 , do tópico anterior, cujos vértices são os estados do Nordeste do
Brasil, temos que (MA, PI, PE, AL, SE) é um caminho que liga os vértices MA e SE.
Dois outros caminhos, ligando esses vértices, são (MA, PI, BA, SE) e (MA, PI, MA,
PI, PE, AL, PE, AL, SE, AL, SE).
Exemplo 10
No grafo G 4 , temos este caminho fechado ou circuito (1, 2, 3, 4, 1) e, em seu
complemento G'4 , não há caminho com extremidades em 2 e 5.
194 A noção de caminho pode ser usada para estabelecer uma dierença signicativa
entre G 4 e seu complemento. Para quaisquer vértices de G 4 , existe um caminho
ligando esses vértices enquanto isso não ocorre em G'4 . Os grafos que têm essa
propriedade serão chamados de conexos, de acordo com a seguinte denição:
ligando 1 e 2: (1, 2)
ligando 1 e 3: (1, 2, 3)
ligando 1 e 4: (1, 4)
ligando 1 e 5: (1, 2, 5)
ligando 2 e 3: (2, 3)
ligando 2 e 4: (2, 5, 4)
ligando 2 e 5: (2, 5)
ligando 3 e 4: (3, 4)
ligando 3 e 5: (3, 4, 5)
ligando 4 e 5: (4, 5).
Exemplo 11
Para V = {1, 2, 3, 4} e A = {{1,
2}, {1, 3}, {1, 4}}, temos que
Todo grafo completo é G = (V, A) é conexo e seu
conexo. complemento G 4 também é
conexo.
Matemática Discreta
Quando xamos um vértice x de um grafo G e colecionamos todos os outros
vértices que podem ser ligados a x e incluímos x na lista, temos o que é chamado
de componente de x em G. Uma vez que a justaposição de dois caminhos com
uma extremidade em comum é também um caminho, podemos vericar que duas
componentes distintas de um grafo são sempre disjuntas e que um grafo é conexo
quando ele possui apenas uma componente.
Exemplo 12
Todo grafo G é subgrafo de si próprio e, para qualquer grafo G = (V, A), vale
Exemplo 13
Todo grafo G = (V, A) é um subgrafo de G = V, V ( ( 2)
).
Exemplo: 14
Aula 8 | Tópico 3
Acompanhe o Exemplo 15, no qual observamos as principais propriedades sobre
os graos que denimos até aqui.
Exemplo 15
196
Matemática Discreta
Figura 26 − Outra representação para o grao da Figura 25
Exemplo 16
Exemplo 17
Considere o grao esquematizado na gura a seguir:
Aula 8 | Tópico 3
Temos que esse é um grafo não conexo, no qual podemos destacar os ciclos (1,
4, 7, 1) e (2, 3, 5, 2). Você deve recordar a Denição 8.3, que, nesse caso, esse grao
não possui vértices isolados. O subgrafo H = ({1, 4, 6, 7}, {14, 17, 47, 67} é uma das
componentes desse grafo. As folhas desse grafo são os vértices 6 e 8, uma vez que
esses vértices possuem grau 1.
Exemplo 18
Matemática Discreta
Tópico 4
199
OBJETIVOS
Estudar aplicações da Teoria dos Grafos
Relacionar os conceitos estudados na aula com diversos problemas
Problema 1
Aula 8 | Tópico 4
É possível desenhar uma linha contínua, isto é, sem tirar a caneta do papel, que
atravesse todas as passagens dessa gura uma única vez?
Solução
Problema 2
Mostre que, em um grupo qualquer de n pessoas, existem pelo menos duas que
possuem o mesmo número de conhecidos.
Solução
Supondo que a relação de conhecer outra pessoa seja recíproca, isto é, que, se
A conhece B, então B conhece A, podemos considerar n pontos P1 , P2 , …, Pn no
plano e linhas entre os pontos Pi e P j para indicar que a pessoa Pi conhece a pessoa
Pj . Dessa forma, temos um grafo com n vértices e algumas arestas. A quantidade de
pessoas que Pi conhece é exatamente o grau de P j . Com essa descrição, o problema
Matemática Discreta
se torna o de provar que, em um grafo qualquer, existem pelo menos dois vértices com
o mesmo grau. Como são n vértices, as possibilidades de graus são 0, 1, 2, ... n − 1 .
Se algum vértice tem grau 0, isto é, se há algum vértice isolado, então nenhum vértice
tem grau n – 1, pois isso signicaria que esse vértice está ligado a todos os outros,
o que não ocorre. Assim, nesse caso, teríamos como possibilidades de grau para os
vértices os números 0, 1, 2, …, n – 2, que são n – 1 números. Assim, a função que
associa cada vértice ao seu grau tem domínio com n elementos e contradomínio com
n – 1 elementos e, pelo Princípio de Dirichlet, não pode ser injetiva, isto é, existem dois
vértices com o mesmo grau. Por outro lado, se for o caso de não haver vértices isolados,
as possibilidades de grau passam a ser 1, 2, …, n – 1, que são n – 1 números. Assim,
também, nesse caso, a função que associa cada vértice ao seu grau tem domínio com 201
n elementos e contradomínio com n – 1 elementos e, portanto, não pode ser injetiva,
isto é, existem dois vértices com o mesmo grau. Dessa forma, analisando todas as
possibilidades, vemos que há dois vértices com o mesmo grau. Voltando ao problema
inicial, isso signica que há pelo menos duas pessoas que têm a mesma quantidade de
conhecidos em qualquer grupo.
Problema 3
São marcados 15 pontos no plano. É possível ligar esses pontos de tal forma
que, ao nal do processo, cada ponto esteja ligado a exatamente 5 outros pontos?
Solução
Problema 4
Solução
Aula 8 | Tópico 4
de vezes que a pessoa correspondente participou de um aperto de mãos. Assim,
o problema se torna o de provar que, em qualquer grafo, a quantidade de vértices
que têm grau ímpar é um número par. Se somarmos os graus de todos os vértices de
grau par, obteremos um número par. Como a soma de todos os graus é um número
par, concluímos que a soma dos graus de todos os vértices que têm grau ímpar é um
número par também. A soma de dois números ímpares é um número par. Observe
que, se a quantidade de vértices de grau ímpar fosse ímpar, esses vértices poderiam
ser agrupados de dois em dois, resultando em soma par, e sobraria um vértice de grau
ímpar, resultando em soma total sendo ímpar, o que nunca ocorre em nenhum grafo.
Portanto, em qualquer grafo, a quantidade de vértices que possuem grau ímpar deve
202 ser um número par, o que demonstra o problema.
Problema 5
Solução
Matemática Discreta
até Q, em seguida, tomamos o caminho adicional que vai de Q a Q, e regressamos a P
como tínhamos feito no primeiro caminho. Caso ainda sobrem arestas por percorrer,
repetimos o processo. Como a quantidade de arestas é nita, esses passos conduzirão
a uma solução para o problema.
Problema 6
Solução
Com isso, chegamos ao nal de nossa oitava e última aula. Encerramos aqui nossa
disciplina. Ao longo dessas oito aulas, aprendemos muito sobre tópicos da Matemática
Discreta. Vimos desde os elementos básicos da Lógica e Análise Combinatória a essa
importante introdução à Teoria dos Grafos.
Sucesso!
Aula 8 | Tópico 4
1. Explique por que é impossível reproduzir o desenho abaixo sem tirar a
caneta do papel e sem passar duas vezes pela mesma linha.
204
a) com graus 1, 1, 1, 3, 3, 3, 4, 6, 7, e 9?
Matemática Discreta
Referências
205
ABE, Jair Minoro; SCALZITTI, Alexandre; SILVA FILHO, João Inácio da. Introdução à
Lógica para a Ciência da Computação. São Paulo: Arte & Ciência, 2001.
ALENCAR FILHO, Edgard de. Iniciação à Lógica Matemática. São Paulo: Nobel, 2002.
ALMEIDA, Manoel De Campos. Origens da matemática: a pré-história da matemática.
Curitiba: Progressiva, 2009. (A Matemática Paleolítica) 1 v.
ARISTÓTELES. Organon: I categorias, II. periérmeneias. Tradução de Pinharanda
Gomes. Lisboa: Guimarães Editores, 1985.
_______. Órganon: Categorias, interpretação, analíticos anteriores, analíticos
posteriores, tópicos, refutações sofísticas. Tradução de Edson Bini. Bauru, SP: Edipro,
2005. (Série Clássicos Edipro).
CABRAL, Alexandre Marques et al. Filosoa: um panorama histórico-temático. Volume
único. Rio de Janeiro: MauadX, 2013.
COPI, Irving Marmer. Introdução à Lógica. Tradução de Álvaro Cabral. 2. ed. São Paulo:
Mestre Jou, 1978.
COSTA, Newton Carneiro Afonso da. Introdução aos fundamentos da Matemática.
Texto da Internet, 2008. Disponível em: <http://lomatematica.blogspot.com/2008/05/
introduo-aos-undamentos-da-matemtica.html>. Acesso em: 3 mar. 2009.
DAGHLIAN, Jacob. Lógica e Álgebra de Boole. 4. ed. São Paulo: Atlas, 1995.
DAVIS, Philip; HERSH, Reuben. A experiência matemática. Tradução de João Bosco
Pitombeira. Rio de Janeiro: Francisco Alves, 1985.
DRUCK, Iole de Freitas. A linguagem lógica. Revista do Professor de Matemática. Rio
de Janeiro: Sociedade Brasileira de Matemática, n. 17, p. 10-18, 1990.
GALINARI, Melliandro Mendes. A polissemia do logos e a argumentação. contribuições
sofísticas para a análise do discurso. EID&A - Revista Eletrônica de Estudos Integrados
em Discurso e Argumentação, Ilhéus, n.1, p. 93-103, nov. 2011.
Referências
MUNDIM, Roberto Patrus. A Lógica Formal – princípios elementares. Economia &
gestão, Belo Horizonte, v. 2, n. 3, p. 135-145, jan./jun. 2002. Disponível em: <http://
periodicos.pucminas.br/index.php/economiaegestao/article/view/113/104>. Acesso
em: out. 2014.
PEREIRA, Oswaldo Porchat. Ciência e dialética em Aristóteles. São Paulo: UNESP, 2001.
SALMON, Wesley C. Lógica. Tradução de Leonidas Hegenberg; Octanny Silveira da
Mota. 4. ed. Rio de Janeiro: Zahar, 1978.
SCHEINERMAN, Edward R. Matemática Discreta-uma introdução. Tradução de Alfredo
Alves de Faria. São Paulo: Thomson, 2006.
206
Matemática Discreta
Sobre os autores
207
Francisco Gêvane Muniz Cunha é professor efetivo do Instituto Federal do
Ceará (IFCE) desde 1994. É licenciado (1993) e bacharel (1994) em Matemática pela
Universidade Federal do Ceará (UFC). Possui mestrado em Matemática (1997) e
mestrado em Ciência da Computação (2002), ambos pela UFC. É doutor em Engenharia
de Sistemas e Computação (2007) pela Universidade Federal do Rio de Janeiro. Atua
nas áreas de Ensino de Matemática, Matemática Aplicada e Computação Aplicada.
Atualmente, é professor de cursos presenciais em nível médio, de graduação e de
pós-graduação do IFCE. Na modalidade semipresencial, foi professor formador de
disciplinas do curso Licenciatura em Matemática do IFCE e tem participado na produção
de livros didáticos. Tem interesse no uso de softwares educativos como apoio para o
ensino de Matemática.
Jânio Kléo de Sousa Castro foi aluno da Escola Técnica Federal do Ceará (hoje
IFCE), onde fez seus estudos de nível médio. Possui bacharelado em Matemática, obtido
na Universidade Federal do Ceará (UFC), em 2004. Foi professor da UFC de 2006 a
2008, contribuindo com os cursos de Administração, Matemática e várias engenharias.
No nal de 2008, ingressou como proessor no Centro Federal de Educação Tecnológia
do Ceará (hoje IFCE), onde trabalha até hoje. Atuou no campus de Maracanaú de 2009 a
2012, onde lecionou para os cursos de Engenharia Ambiental e Ciência da Computação.
No campus de Fortaleza, atua desde 2009 ministrando aulas para a Licenciatura em
Matemática, para o ensino médio e para diversas engenharias, sendo responsável pela
condução de disciplinas em diversas áreas da Matemática. Na educação a distância
do IFCE, atuou como tutor, formador e conteudista, tendo produzido materiais de
Matemática Básica, Teoria dos Números, Álgebra Linear e Cálculo Númerico, esses dois
últimos em parceira com o professor Francisco Gêvane Muniz Cunha.
Sobre os autores