matematica discreta fasciculo 1v7

Prévia do material em texto

Universidade Federal Rural de Pernambuco
Reitor: Prof. Valmar Corrêa de Andrade
Vice-Reitor: Prof. Reginaldo Barros
Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho
Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski
Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire
Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira
Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena
Coordenação de Ensino a Distância: Profª Marizete Silva Santos
Produção Gráfica e Editorial
Capa e Editoração: Allyson Vila Nova, Rafael Lira, Aline Luciana Fidelis e Alesanco Andrade
Revisão Ortográfica: Ivanda Martins
Ilustrações: Allyson Vila Nova e Diego Almeida
Coordenação de Produção: Marizete Silva Santos
Sumário
Plano da Disciplina ......................................................................................6
Ementa .................................................................................................. 6
Objetivo Geral........................................................................................ 6
Objetivos Específicos ............................................................................6
Conteúdo Programático.........................................................................6
Referências ........................................................................................... 7
Apresentação ...............................................................................................8
Capítulo 1 - Conjuntos: uma breve revisão. .............................................. 9
1.1 Definições. ....................................................................................... 9
Capítulo 2 - Álgebra de Conjuntos: como operar com conjuntos? ...... 18
2.1 Operações entre conjuntos. ...............................................................18
2.2 Partição de um conjunto ....................................................................28
2.3. Cardinal da união e da interseção. .................................................29
2.4. Produto Cartesiano. ..........................................................................35
2.5 Produto Cartesiano de k conjuntos ....................................................37
2.6. Identidades de conjuntos. .................................................................38
Capítulo 3 - Introdução à Lógica Matemática .......................................... 43
3.1 Proposições compostas. ....................................................................44
3.2 Tautologias e Contradições ...............................................................51
3.3 Negação de conjunção e de disjunção .............................................53
3.4 Álgebra das proposições. ..................................................................54
3.5 Funções proposicionais. Quantificadores. .........................................59
3.5.1 Quantificadores. .........................................................................59
3.5.2 Negação de sentenças quantificadas ........................................ 60
Capítulo 4 - Portas Lógicas .......................................................................65
4.1 Porta Not (Não) ..................................................................................65
4.2 Porta Or (Ou) ....................................................................................66
4.3 Porta And (E) .....................................................................................67
4.4. Porta Nand e Porta Nor. ...................................................................68
4.5. Portas XOR e XNOR ........................................................................68
4.6 Portas Lógicas Equivalentes .............................................................69
4.7 Propriedades das Portas Lógicas. .....................................................69
Plano da Disciplina
Ementa
Conjuntos. Introdução à Lógica Matemática. Portas Lógicas. Somatório. Princípios 
de Contagem. Matrizes. Relações. Funções. Recursão. Técnicas de provas. Indução 
Matemática. 
Objetivo Geral
 O objetivo geral é abordar conteúdos selecionados da Matemática Discreta que 
realizam interface com o curso de Sistema de Informação, visando dar a base para 
a compreensão de conceitos de estruturas de dados, bem como, para dar suporte na 
construção de algoritmos em seus diferentes níveis de complexidade.
Objetivos Específicos
• Aprender a encontrar modelos matemáticos que representem certos problemas 
concretos (noções de modelagem matemática), em especial quando estes se 
referem a situações práticas 
• Familiarizar-se com a escrita matemática formal e a linguagem computacional 
• Representar fenômenos na forma algébrica e na forma gráfica 
• Conhecer técnicas de resolução de problemas 
• Desenvolver a capacidade de raciocínio abstrato (lógico-matemático).
Conteúdo Programático
Módulo 1 – Fascículo 1
Carga horária do Módulo 1: 20 h
• Conjuntos. 
• Introdução à Lógica Matemática. 
• Portas Lógicas.
Módulo 2 – Fascículo 2
Carga horária do Módulo 2: 20 h
Somatório. Princípios de Contagem. Matrizes. Relações
Módulo 3 – Fascículo 3
Carga horária do Módulo 3:
• Funções. 
• Recursão. Técnicas de provas. 
• Indução Matemática. 
Referências
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. 
Tradução Valéria de Magalhães Lorio. Rio de Janeiro: LTC, 2004.
Scheinerman, Edward R. Matemática Discreta: uma introdução. Tradução de 
Alfredo Alves de Farias. São Paulo: Pioneira Thomson Learning, 2003.
Livros de referência:
ABE, Jair Minoro; PAPAVERO, Nelson. Teoria intuitiva dos conjuntos. São Paulo 
McGraw Hill:, 1997
ALENCAR Filho, Edgard de. Iniciação à Lógica Matemática. São Paulo: Nobel, 
1995.
ROSS, Kenneth A; WRIGHT, Charles R. B. Discrete Mathematics. Prentice Hall, 
1999.
TRUSS, J. K. Discrete mathematics for computer scientist. Addison Wesley. 
1999.
LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas de Matemática 
Discreta. Porto Alegre: Bookman, 2004
Apresentação
Caro (a) cursista,
A importância da Matemática Discreta nos Cursos de Computação e Informática é 
destacada nas Diretrizes Curriculares do MEC ao se afirmar que “A Matemática, para 
a área de computação, deve ser vista como uma ferramenta a ser usada na definição 
formal de conceitos computacionais (linguagens, autômatos, métodos, etc)”. E ainda: 
“Considerando que a maioria dos conceitos computacionais pertence ao domínio 
discreto, a Matemática Discreta é fortemente empregada”.
A Matemática Discreta dá ênfase aos temas, matemáticos tomando por base os 
conjuntos contáveis, finitos ou infinitos. A Matemática do Continuum, ao contrário da 
Matemática Discreta, enfatiza os temas matemáticos baseados em conjuntos não- 
contáveis, como o conjunto dos números reais, em disciplinas como o Cálculo Diferencial 
e Integral.
Iremos abordar conteúdos selecionados da Matemática Discreta que realizam 
interface com os cursos das áreas relacionadas à informática. Para tanto, o material será 
apresentado em fascículos que tratarão de maneira sistemática os seguintes assuntos: 
Conjuntos, Operações com conjuntos, Introdução à Lógica Matemática, Portas lógicas, 
Somas, Matrizes, Princípios de Contagem, Relações, Funções, Recursão, Técnicas de 
Provas e Princípio de Indução Finita.
9
Matemática Discreta
Capítulo 1 - Conjuntos: uma 
breve revisão.
A idéia de conjuntos é largamente utilizada em Computação e 
Informática, tendo em vista que, praticamente todos os conceitos 
dessas áreas, bem como os resultados correspondentes, são 
baseados em conjuntos ou as construções sobre conjuntos. Por isso, 
que tal fazermos uma revisão dos principais elementos da teoria dos 
conjuntos? 
1.1Definições.
 Conjuntos são geralmente designados por letras maiúsculas e 
reservam-se as letras minúsculas para representar os seus elementos. 
A expressão x∈A significa que x é elemento do conjunto A. Se x não 
é elemento do conjunto A, escrevemos x∉A.
Várias maneiras podem ser usadas para descrever um conjunto. 
Entre elas, destacamos as seguintes:
• Listando seus elementos, isto é, nomeando explicitamente 
todos os seus elementos, colocando-os entre chaves e 
separados por vírgula. 
 Exemplo: A = { a, e, i, o, u }, B = { a, b, c, d }.
• Definindo uma propriedade de seus elementos. Em geral 
escrevemos {x : P(x) }, isto é, o conjunto dos x tal que x tem a 
propriedade P. 
 Exemplo A = { x : x é uma letra vogal do alfabeto português}, 
B = { x : x é uma das quatro primeiras letras minúsculas do 
alfabeto português }.
• Por meio de um Diagrama de Venn1 (1834 -1923): O conjunto 
constituído por todos os elementos sob consideração numa 
Acesse
1. http://paginas.
terra.com.br/
educacao/calculu/
Historia/venn.htm
10
Matemática Discreta
determinada situação é denominado conjunto universo U 
e será, em geral, representado por um retângulo. Dentro do 
retângulo, círculos (ou outras figuras geométricas) representam 
conjuntos. Dentro dos círculos são colocados os elementos 
desses conjuntos.
Por exemplo: Considere o conjunto universo U = {1, 2, 3, 4, 5, 6, 
7, 8, 9, 10, 11, 12} e os conjuntos A = { 1, 2, 3, 4, 5, 9} e B = {2, 4, 6, 
7, 8 }
A idéia de conjunto universo U estará sempre presente mesmo 
quando não seja explicitamente mencionado num determinado 
problema ou situação. Em Matemática, há conjuntos que constituem 
muito freqüentemente os universos do discurso, sendo conveniente 
indicar nomes para eles. Entre os mais importantes, destacaremos:
• N = { 0, 1, 2, 3, 4, 5, ... } é o conjunto dos números naturais. 
(Perceba que 0 ∈ N)
• N*= { 1, 2, 3, 4, 5, ... }é o conjunto dos números naturais 
positivos.
• Z = { x : x é um número inteiro } = { ..., -3, -2, -1, 0 , 1 , 2, 3, ...}
• Q = { x : x é um número racional } é o conjunto de todos os 
números que podem ser escritos sob a forma de fração.
• R = { x : x é um número real }
• I = { x : x é um número irracional) é o conjunto dos números 
reais não racionais, isto é, não podem ser escritos sob a forma 
de fração. 
 Conjunto vazio é o conjunto sem elementos, pode ser 
representado pelos símbolos ∅ ou { } 
Exemplo: A = { x ∈ N : 1 < x < 2 } é uma conjunto vazio, pois não 
existe número natural entre 1 e 2.
11
Matemática Discreta
Exemplo: B = { x ∈ Z : x2 = 3 } também é um conjunto vazio. Você 
sabe por quê? Existe número inteiro cujo quadrado seja igual a 3?
 Conjuntos iguais. Dois conjuntos são iguais se e somente se 
contém os mesmos elementos. Por exemplo: Os conjuntos A = {x∈ Z 
: x2 = 4 } e B = { -2, 2} são iguais.
 Subconjunto. Um conjunto A é subconjunto do conjunto B se 
todo elemento do conjunto A é também elemento de B. Usamos a 
notação A ⊆ B para denotar que A é subconjunto de B e lemos “A está 
contido em B”.
Por exemplo, A = {1,2} é subconjunto de B = {1, 2,3} mas não é 
subconjunto de C = {1,3,4}.
Agora, vamos lembrar algumas conclusões relacionas a 
subconjunto.
 Observação 1. De acordo com a definição de subconjunto, 
o conjunto vazio é subconjunto de qualquer conjunto A, isto é, ∅ 
⊆ A. Isso parece estranho a você? Mas, existe algum elemento no 
conjunto ∅ que não esteja no conjunto A? A sua resposta foi não! 
Logo, o conjunto vazio é subconjunto do conjunto A.
 Também dizemos que A ⊆ A, qualquer que seja o 
conjunto A. Isso é verdade, pois todo elemento de A, é elemento de 
A.
 Observação 2. Se A ≠ B e A é subconjunto de B, escrevemos 
A ⊂ B para dizer que A é subconjunto próprio de B. Por exemplo, 
{1,2,3} é subconjunto próprio de {1,2,3,4,5}. 
Temos também que N ⊂ Z, Z ⊂ Q, Q ⊂ R. Veja a figura a seguir.
 Observação 3. Se A ⊆ B e B ⊆ C então A ⊆ C. 
12
Matemática Discreta
Exemplo: {1, b} ⊂ { 1, 2, b, c } ⊂ { 1, 2, 3, a, b, c }.
Exemplo: A figura da observação 2 mostra que N ⊂ Z e Z ⊂ R 
então N ⊂ R.
 Observação 4. Para provarmos que A ⊆ B teremos que 
provar que, dado x ∈ A então x ∈ B. 
 Cardinal. Se A um conjunto com exatamente n elementos, 
tal que n é um inteiro não negativo, dizemos que A é um conjunto 
finito e que o cardinal de A é n. Assim, o cardinal de um conjunto 
A, denotado por #A é o número de elementos do conjunto A. Desse 
modo, se A = { x ∈ Z : 3 ≤ x ≤ 7 } então #A = 5. É claro que #∅ = 0.
 Observe que um conjunto A é finito se podemos estabelecer 
uma correspondência entre seus elementos e os elementos de um 
conjunto da forma {1, 2, 3, ..., n} onde n é o cardinal de A. Por exemplo, 
A = { a, b, c, d, e } é finito pois, podemos estabelecer a seguinte 
correspondência entre seus elementos e os elementos do conjunto { 
1, 2, 3, 4, 5 }: 
a 1, b 2, c 3, d 4, e 5. Você então conclui que o 
cardinal do conjunto A é 5.
 Conjunto infinito. Um conjunto A é infinito se não é finito. 
Por exemplo, os conjuntos N, Z, Q e R são conjuntos infinitos. Você 
concorda com a afirmação de que o conjunto A = {x∈R : 0 < x < 1}é 
infinito?
 Conjunto das partes de um conjunto A é o conjunto constituído 
por todos os subconjuntos de A e será denotado por P(A). Exemplo, 
se A = {a, b} então P(A) = { ∅, {a}, {b}, {a,b} }. O cardinal de P(A) é o 
número de subconjuntos de A. Assim #P(A) = 4.
Agora, escreva o conjunto das partes do conjunto A = {x, y, z}. 
Quantos são os subconjuntos de A? O lembrete ao lado dá uma dica. 
13
Matemática Discreta
Nesse caso #A = 3, #P(a)=2³=8.
Aprenda Praticando - Exercício Proposto 1.1
Demonstre que você entendeu bem os assuntos dessa seção, 
resolvendo os exercícios propostos. As respostas dos exercícios são 
apresentadas logo a seguir. Se tiver dúvidas, procure saná-las com 
professores e tutores da disciplina.
1) Considere N = {0, 1, 2, 3, 4, ...}. Liste os elementos de cada um 
dos seguintes conjuntos:
 a) {n ∈ N : n é divisível por 3} 
 b) {x : x = 2n-1 , n ∈ N*}
 c) {x : x = 2y +1 : y∈N e y < 8 }
 d) {x = 2n : n ∈ N }
 e) {x : x =1/n : n ∈ N* e n < 6}
 f) {n ∈ N* : n + 1 é primo}
2. Liste os elementos dos seguintes conjuntos e informe que 
conjuntos são vazios.
 a) { n ∈ N : n2 = 9 }
 b) { n ∈ Z : n2 = 9 }
 c) { x ∈ R : x2 = 9 }
 d) { n ∈ N : 3 < n < 7 }
 e) { n ∈ Z : | n | < 7 }
 f) { x ∈ R : x2 ≤ 0 }
 g) { n ∈ N : n2 = 3 }
 h) { x ∈ Q : x2 = 3 }
Atenção
De um modo geral 
se #A= n então 
#P(A) = 2n.
Atenção
Um número natural 
n ∈ N, n >1 é primo 
se os seus únicos 
divisores são 1 e n.
14
Matemática Discreta
 i ) {x ∈ R: x2 = -4 }
 j) { n ∈ N : n é primo e n ≤ 15 }
3. Determine o cardinal dos seguintes conjuntos:
 a) A = { x : x = 2n + 1, 3 ≤ n ≤ 6, n ∈ N }
 b) B = { y = -x +1, -2 ≤ x ≤ 2, x ∈ Z }
 c) C = { y = x2 +1, -2 ≤ x ≤ 2, x ∈ Z }
4. Se A = { x∈Z : 4 divide x } e B = { x∈Z : 2 divide x } . A é 
subconjunto próprio de B ?
5. Relacione todos os subconjuntos X do conjunto A = { 1, 2, 3, 4 } 
tais que #X = 2.
6. Represente os conjuntos abaixo indicados por uma propriedade 
características de seus elementos:
A = { -6, -4, -2, 0, 2, 4, 6 } B = { 13, 11, 9, 7, 5 }
C = { 2, 6, 10, 14, ..., 42 }.
7. Sejam X = { 1, 2, 3 }, Y = { 2, 3, 4 } e Z = { 2 } . Encontre o maior 
conjunto W satisfazendo as seguintes condições W ⊂ X , W 
⊂ Y e Z ⊂ W . Faça diagramas de Venn.
8. Dados os conjuntos A = { um , dois }, B = { dois, tres, quatro } e 
C = { um , quatro } identifique o menor conjunto D tal que A 
⊂ D , B ⊂ D e C ⊂ D. Faça diagramas de Venn.
9. Suponha que A ⊂ B , B ⊂ C , 1∉A , 2∉B , 3∉C . Quais das 
afirmações abaixo sempresão verdadeiras?
 a) 1 ∈ B. b) 2∉ A c) 3 ∉ A
10. Seja A = { 1, 2, 3, 4, 5, 6, 7, 8, 9}. Nomear os elementos dos 
seguintes conjuntos:
 a) B = { x ∈ A : x é par }
 b) C = { x∈A : x é múltiplo de 3 }
 c) D = { x ∈ A : x + 1 < 6 }
15
Matemática Discreta
 d) E = { x ∈ A : x < 10 }
 e) F = { x ∈ A : x + 3 ∉ A }.
11. Dizer quais dos seguintes conjuntos são infinitos:
 a) O conjunto das retas do plano que são paralelas ao eixo 
dos x.
 b) O conjunto das palavras com duas letras do alfabeto 
português.
 c) O conjunto dos múltiplos de cinco.
 d) O conjunto dos animais existentes na Terra.
 e) O conjunto das frações 
q
p onde p, q ∈ { 1, 2, 3, 4, ..., 10 }
12. Represente os seguintes conjuntos por meio de uma 
propriedade comum aos seus elementos:
 a) A = { 4, 8, 12, 16, 20, ....}
 b) B = { 4, 8, 12, .... 204}
 c) C = { 7, 17, 27, 37, .....}
 d) D = { 7, 17, 27, 37, .....207} 
 e) E = {300, 301, 302, ....., 399, 400}
 f) F = { 1, 4, 9 , 16, 25, .....}
 g) G = { 1, ½, ¼, 1/8, 1/16,..., 1/1024} 
13. Partindo das premissas: 
 (1) Todo repórter é esperto.
 (2) Todo repórter é formado em Jornalismo.
 (3) Jamil é esperto.
 (4) Adelaide é jornalista. 
Pode-se concluir que 
 a) Adelaide é esperta?
 b) Jamil é repórter?
 c) Há jornalistas espertos?
16
Matemática Discreta
Respostas dos exercícios 1.1
Aqui você poderá conferir as suas respostas. Caso elas não 
correspondam às apresentadas abaixo, converse com seus colegas 
sobre os exercícios, releia os conteúdos da seção e descubra o motivo 
da divergência. Lembre-se que os tutores podem ajudá-lo. Consulte-
os!
1. a) {0, 3, 6, 9, 12, 15, ...} b) {1, 3, 5, 7, 9, ...} 
c) { 1, 3, 5, 7, 9, ..., 15} d) {0, 2, 4, 8, 16, 32,..}
e) {1, ½, 1/3, ¼, 1/5 } f) { 1, 2, 4, 6, 10, 12, ... }
2. a) { 3 } b) { -3, 3 } c) { -3, 3 } d) (4, 5, 6 } 
e) { -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6 } f) { 0 }
g) ∅ h) ∅ i) ∅ 
3. a) #A = 4 b) #B = 5 c) #C = 3 
4. sim 
5. {1, 2} , { 1, 3 } , { 1, 4} , { 2, 3 }, {2, 4} , { 3, 4 }
6. A = {x : x = 2y, y ∈ Z, -3 ≤ y ≤ 3 }
B = { x: x = 2y + 1, y ∈ N, 2 ≤ y ≤ 6 }
C = { x : x = 2 + 4n , n ∈ N n ≤ 10 }
7. W = {2,3}
8. D = { um, dois, três, quatro }
9. b) e c) 
10. B = {2, 4, 6, 8 } C = { 3, 6, 9} D = { 1, 2, 3, 4 }
E = A F = { 7, 8, 9 }
11. a) e c)
12. A = {x : x = 4n, n∈N* }, B = { x : x = 4n, n∈N*, n ≤ 51 },
C = { x : x = 7 +10n, n∈N } D = { x : x = 7 +10n, n∈N, n ≤ 20}
17
Matemática Discreta
E = {x : 300 ≤ x ≤ 400, x∈ Z} F = {x : x = n2, n∈ N}
G = {x ; x = 
2
1
n
, n∈ N, n ≤10.
13. c.
Saiba Mais
 
Caro (a) cursista. Aprofunde os conhecimentos sobre conjuntos, 
consultando os seguintes livros:
ABE, Jair Minoro; PAPAVERO, Nelson. Teoria intuitiva dos 
conjuntos. São Paulo McGraw Hill:, 1997.
ALENCAR Filho, Edgard de. Iniciação à Lógica Matemática. São 
Paulo: Nobel, 1995.
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência 
da Computação. Tradução Valéria de Magalhães Iorio. Rio de 
Janeiro: LTC, 2004.
LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas 
de Matemática Discreta. Porto Alegre: Bookman, 2004
Scheinerman, Edward R. Matemática Discreta: uma introdução. 
Tradução de Alfredo Alves de Farias. São Paulo: Pioneira 
Thomson Learning, 2003.
Atenção
A Matemática é 
uma disciplina 
de natureza 
cumulativa. 
É importante 
dominar bem 
seus fundamentos 
antes de passar 
para tópicos mais 
avançados.
18
Matemática Discreta
Capítulo 2 - Álgebra de 
Conjuntos: como operar com 
conjuntos?
Nesta parte do fascículo, estudaremos a Álgebra de Conjuntos, 
conteúdo da Matemática que trata das operações definidas sobre 
todos os conjuntos. Voltaremos a fazer uso dos diagramas de Venn, 
na ilustração das operações entre conjuntos envolvendo a união, 
interseção, diferença entre outras. Vamos começar?
2.1 Operações entre conjuntos.
 União de Conjuntos: Se A e B são dois conjuntos então A∪B é 
o conjunto constituído pelos elementos que pertencem a pelo menos 
um dos dois conjuntos. 
A ∪ B = { x : x ∈ A ou x ∈ B }
 Interseção de Conjuntos: Se A e B são 2 conjuntos, então 
o conjunto A ∩ B denota a interseção de A e B, constituído pelos 
elementos que pertencem a A e a B.
A∩B = { x : x∈A e x∈B } 
 Complementar. Seja U o conjunto universo e A um subconjunto 
de U. Chama-se complementar de A em relação ao conjunto U ao 
conjunto A dos elementos de U que não pertencem a A.
A = { x∈U : x∉A }
19
Matemática Discreta
 Diferença: Se A e B são conjuntos então A – B denota o 
conjunto dos elementos de A que não estão em B.
A – B = { x: x∈A e x∉B }
 Diferença Simétrica: Se A e B são conjuntos então A⊕B ou 
A∆B denota o conjunto dos elementos que estão em A ou em B, mas 
não em ambos. O símbolo ⊕ representa o ou exclusivo.
A⊕B = { x: x∈(A-B) ou x∈(B-A) } A⊕B = (A∩B ) ∪ ( A∩B)
Exemplo 2.1.1 Aqui, apresentamos exemplos de todas as 
operações definidas acima. Confira os resultados.
A ∪ B = { 1, 2, 3, 4, 5, 6,7, 8, 9}
A ∩ B = { 6, 8 }
Atenção
 A se escreve 
também A’
Atenção
A – B pode ser 
escrito assim: 
A ∩ B
Atenção
A ⊕ B pode ser 
escrito assim: 
A ∆ B
20
Matemática Discreta
A – B = { 1, 2, 3, 4 }
B – A = { 5, 7, 9 }
A = { 5, 7, 9 10, 11, 12}
B = { 1,2,3, 4, 10, 11, 12}
A ⊕ B = { 1, 2, 3, 4, 5, 7, 9}
 Tabela de pertinência das operações entre conjuntos: Para 
construirmos a tabela de pertinência de um conjunto, procedemos 
como segue. Se x∈X, indicamos o fato pondo 1 (verdadeiro) na coluna 
do conjunto X. Se x∉X, indicamos o fato pondo 0 (falso) na coluna do 
conjunto X. 
 Por exemplo, em relação à união de dois conjuntos A∪B, 
existem quatro situações distintas indicadas nas quatro linhas da 
tabela de pertinência da união abaixo:
 Elementos que não pertencem a nenhum dos dois conjuntos 
(linha 1), não pertencem a A∪B
 Elementos que não pertencem a A e pertencem a B ( linha 2), 
pertencem a A∪B.
 Elementos que pertencem a A e não pertencem a B (linha 3), 
pertencem a A∪B.
 Elementos que pertencem a A e a B ( linha 4), pertencem a 
A∪B. 
Tabela de pertinência da união
Tabela de pertinência da interseção
21
Matemática Discreta
 Em relação à interseção de dois conjuntos A ∩ B, existem 
quatro situações distintas indicadas na tabela de pertinência da 
interseção abaixo:
 Elementos que não pertencem a nenhum dos dois conjuntos 
(linha 1), não pertencem a A∩B
 Elementos que não pertencem a A e pertencem a B (linha 2), 
não pertencem a A∩B.
 Elementos que pertencem a A e não pertencem a B (linha 3), 
não pertencem a A∩B.
 Elementos que pertencem a A e a B (linha 4), pertencem a 
A∩B.
 As tabelas de pertinência dos conjuntos A – B, B- A e A⊕B 
são apresentadas abaixo, de acordo com as respectivas definições.
 Tabela de pertinência do complementar: A tabela de 
pertinência do complementar apresenta apenas duas linhas, visto 
que o complementar é uma operação que envolve apenas um 
conjunto.
 
Exemplo 2.1.2. Considere o conjunto universo U = {1, 2, ..., 9} e 
os seus subconjuntos:
22
Matemática Discreta
A = {1, 2, 3, 4, 5, 6, 7} B = { 4, 5, 6, 7, 8} C = { 5, 6, 7, 8, 9 }
D = { 1, 3, 5, 7, 9 } E = { 2, 4, 6, 8 } F = { 1, 5, 9 }.
A ∪ B = {1,2, 3, 4, 5, 6,7, 8} A ∩ B = {4, 5, 6, 7}
B ∪ D = {1, 3, 4, 5, 6, 7, 8, 9 }, B ∩ D = {5,7}
A ∪ C = {1,2, 3, 4, 5, 6, 7, 8, 9} A ∩ C = {5, 6,7}
D ∪ E = {1,3,5,7,9,2,4,6,8}, D ∩ E = ∅
D ∪ F = { 1, 3, 5, 7, 9 } D ∩ F = { 1, 5, 9 }
E∪E = { 2, 4, 6, 8 } E ∩E = ∅
A = {8,9} B = { 1, 2, 3, 9 } C = {1, 2,3, 4 } D ={ 2, 4, 6, 8}
A – B = {1,2, 3} B – A = { 8 } D – E = { 1, 3, 5, 7, 9 }
E – E = ∅
A⊕B = {1,2, 3, 8} A⊕C= {1, 2, 3, 4, 8, 9} A⊕D = { 2, 4, 6, 9 }
A⊕E= {1, 3, 5, 7
(A - B) - C = {1, 2, 3} - { 5, 6, 7, 8, 9 } = {1, 2, 3}
A - (B – C) = {1, 2, 3, 4, 5, 6, 7} – { 4 } = {1, 2, 3, 5, 6,7}
(A-B) – (B-A)= {1, 2, 3} - { 8 } = {1, 2, 3} 
BA = }{ 8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 = { 9 }
A∩B = {8,9} ∩ { 1, 2, 3, 9 } = { 9 }
BA = }{ 7 6, 5, 4, = {1, 2, 3, 8, 9}
BA = {8,9} ∪ { 1, 2, 3, 9 } = {1, 2, 3, 8, 9}
Exemplo 2. 1. 3. Para construir a tabela de pertinência do conjunto 
(A∩B ) ∪ ( A∩B), devemos construir colunas para os conjuntos A, B, 
Atenção
Você observou no 
exercício 2.1. 2 que,
BA = A ∩ B 
e que 
BA
 = 
BA ? 
Isso não é mera 
coincidência. 
Trata-se de 
igualdades válidas 
para quaisquer 
conjuntos A e B!
23
Matemática Discreta
A e B . Em seguida, as colunas relativas aos conjuntos A∩B , 
A∩B e por último, a coluna do conjunto (A∩B ) ∪ ( A∩B).
Você deve observar que, logo após o preenchimento com 0 (zero) 
e 1 (um) nas colunas relativas aos conjuntos A e B, preenchemos as 
colunas do complementar de A, denotado por A , e do complementar 
de B, denotado por B , simplesmente trocando 0 (zero) por 1 (um). 
As colunas relativas aos conjuntos A ∩ B e A ∩ B são preenchidas 
por 0 (zero) e 1 (um) de acordo com a tabela de pertinência da 
interseção. Por fim, a última coluna é feita de acordo com a tabela de 
pertinência da união de conjuntos. A tabela de pertinência do conjunto 
(A ∩ B ) ∪ ( A ∩ B) é a igual à tabela de pertinência do conjunto A ⊕B. 
Observe isso. Mostraremos na seção 2.6 como provar a igualdade 
entre conjuntos, observando a igualdade das respectivas tabelas-
verdade.
Exemplo 2.1.4. Na determinação dos tipos sangüíneos, cada 
pessoa é duplamente classificada: se o sangue tem o antígeno Rh, 
ele é Rh positivo, caso contrário é Rh negativo. Se o sangue contém 
o antígeno A, mas não contém o antígeno B, é tipo A. Se o sangue 
tem o antígeno B, mas não tem o antígeno A, é tipo B. Se tem ambos, 
é tipo AB. Se nenhum dos dois antígenos está presente, é tipo O. 
Considere os conjuntos: 
P = {x : x é pessoa cujo sangue contém o antígeno Rh}
A = {x : x é pessoa cujo sangue contém o antígeno A}
B = {x : x é pessoa cujo sangue contém o antígeno B}
Um elemento x qualquer pode pertencer ou não a cada um 
dos três conjuntos P, A e B. Ao todo são 8 possibilidades.Elas são 
representadas na tabela ao lado e no diagrama de Venn.
24
Matemática Discreta
Determine os respectivos tipos sangüíneos das pessoas 
pertencentes a cada conjunto:
1) BAP ∩∩ = { g }
2) BAP ∩∩ = { d }
3) BAP ∩∩ = { f }
4) ABP ∩∩ { e }
5) BAP ∩∩ = { a }
6) BAP ∩∩ = { h } 
7) ABP ∩∩ = { d }
8) BAP ∩∩ = { c } 
Resp. 1) Tipo AB Rh+ 2) Tipo AB Rh-
 3) Tipo A Rh+ 4) Tipo B Rh+ 5) Tipo A Rh- 
 6) Tipo O Rh- 7) Tipo B Rh- 8) Tipo O Rh+ 
Aprenda Praticando - Exercícios Proposto 2.1
Apresentamos agora uma lista de exercícios para que você mostre 
que entendeu as operações entre conjuntos. Discuta com seus 
colegas as respostas que são apresentadas logo em seguida.
25
Matemática Discreta
1. Considere o conjunto universo igual ao conjunto U de todos os 
alunos da UFRPE e os seguintes subconjuntos:
 A = { x : U: x é aluno do Curso de Agronomia }
 B = { x : U: x é aluno do Curso de Biologia }
 C = { x : U: x é aluno do Curso de Ciência Domésticas }
 Defina os seguintes conjuntos por meio de operações com 
conjuntos:
a) O conjunto dos alunos da UFRPE que cursam Biologia ou 
Ciências Domésticas (Eles podem fazer apenas um desses 
cursos ou ambos ).
b) O conjunto dos alunos da UFRPE que fazem Agronomia 
e Biologia ao mesmo tempo, mas não fazem Ciências 
Domésticas.
c) O conjunto dos alunos da UFRPE que cursam Agronomia e não 
cursam Biologia.
d) O conjunto dos alunos da UFRPE que fazem apenas um dos 
cursos A, B e C.
e) O conjunto dos alunos da UFRPE que não fazem qualquer um 
dos cursos A, B e C .
f) O conjunto dos alunos da UFRPE que fazem Biologia, mas não 
Ciências Domésticas ou fazem Ciências Domésticas mas não 
Biologia.
2. Considere o conjunto A = { 1, 2, 3, 4, 5, 6, 7, 10,12,13 }. Listar os 
elementos dos seguintes conjuntos:
 A1 = { x ∈ A : x2 ≥ 9 }
 A2 = { x ∈ A : (x+2) ∉ A } 
 A3 = { x ∈ A : x-1 é impar }
 A4 = {x∈A : x é divisível por 2 ou por 3}
 A5 = {x∈A : x2 – 4 = 0 ou x2 –9x +20 = 0 }
 Calcule: a) ( A1∩A2) – (A1∩A3) b) (A3∪A4) ⊕ (A1-A4)
3. Considere U como o conjunto de todas as pessoas e os 
subconjuntos
26
Matemática Discreta
 S = { x∈U : x reside no Brasil }
 M= { x∈U : x é mulher }
 J = { x∈U : x tem menos de 25 anos } 
 A = { x∈U : x tem mais de 1,70 m de altura }
 Descreva os conjuntos abaixo através de uma propriedade 
característica dos seus elementos:
a) S∩A∩J b) S∩(J –A ) c) S∩(M∪J) 
d) S∪(M∩J).
4. Encontre os conjuntos A e B, sabendo–se que 
 A – B = { 1, 5, 7, 8 }, B – A = { 2, 10 } e A∩B = {3, 6, 9 }. 
Respostas dos exercícios 2.1 
1. a) B∪C b) (A∩B) – C 
 c) A – B d) )()()( CBACBACBA ∩∩∪∩∩∪∩∩ 
 e) CBA ∩∩ f) B⊕C
2. A1= { 3, 4, 5, 6, 7, 10,12, 13} A2 = {6,7,12,13}
 A3= {2, 4, 6, 10, 12} A4 = {2, 3, 4, 6, 10, 12}
 A5 = { 2, 4, 5}
 a) ( A1∩A2) – (A1∩A3) = {6, 7, 12, 13} – { 4, 6, 10,12}= {7, 13} 
 b) (A3∪A4) ⊕ (A1-A4) = { 2, 3, 4, 6, 10, 12} ⊕ {3, 5, 7, 13} = {2, 4, 
5, 6, 7, 10,12, 13}.
3. a) S∩A∩J = { x∈U : x reside no Brasil, tem menos de 25 anos e 
mais 1,70 m de altura}
 b) S∩(J –A ) = { x∈U : x reside no Brasil, tem menos de 25 
anos e 1,70 m de altura e no máximo 1,70 m de altura}.
 c) S∩(M∪J) = { x∈U : x reside no Brasil e é mulher ou tem 
menos de 25 anos}. 
 d) S∪(M∩J) = { x∈U : x reside no Brasil ou é mulher com menos 
de 25 anos}.
27
Matemática Discreta
4. A = { 1, 3, 5, 6, 7, 8, 9} e B = {2, 3, 6, 9, 10}
28
Matemática Discreta
2.2 Partição de um conjunto
 Dois conjuntos A e B são chamados disjuntos se A ∩ B = ∅, 
isto é, não têm elementos comuns. Os conjuntos A = {2, 5, 7, 9}, B = 
{4, 6, 8, 10} e C = {1, 3, 11,12} são dois a dois, disjuntos. 
De fato, A ∩ B = ∅, A ∩ C = ∅ e B ∩ C = ∅
 Uma partição de um conjunto S é uma coleção de subconjuntos 
não vazios de S, disjuntos dois a dois, cuja união resulte S. Ou 
seja, é uma coleção de subconjuntos A1, A2, ... , An de S tal que 
S =A1 ∪ A2 ∪ A3 ∪......∪ An e Ai ∩ Aj = ∅, para i ≠ j .
Exemplo 2.2. S = {1, 2, 3, 4, 5, 6}. A coleção de conjuntos 
A1= {1, 2, 3}, A2= {4, 5} e A3= {6 } forma uma partição de S . Observe 
que A1∩ A2 = φ, A1∩ A3 = φ, A2∩ A3 = φ e além disso, a união dos três 
conjuntos A1∪A2∪A3 = {1, 2, 3, 4, 5, 6}.
Aprenda Praticando - Exercícios Proposto 2.2 
Agora, você é solicitado a apresentar partições de conjuntos. 
Algumas partições são constituídas por conjuntos finitos outras não. 
Mãos à obra!
1. Dê partições dos seguintes dos conjuntos: 
 a) N b) Z c) S = {0, 1, 2 ,3, 4, 5, 6 , 7, 8, 9 }.
2. Se S = {0, 3, 6, 9, 12,15, 18, ...}, escrever uma partição de S 
que:
 a) contenha dois subconjuntos infinitos
29
Matemática Discreta
 b) contenha três subconjuntos infinitos.
3. Se S = {1, 5, 9, 13, 17, 21, 25, ...}, os conjuntos A1 = {1 +12n, 
n∈ N }, A2 = {5 +12n, n∈ N } e A3 = { 9 + 12n, n∈ N } constituem 
uma partição de S .
Respostas - Exercícios Proposto 2.2 
As suas respostas possivelmente não batem com as apresentadas 
logo abaixo. Isso pode ocorrer, pois um conjunto pode ter várias 
partições.
1. a) A1= {0, 2, 4, ,6, 8, 10, ...} A2 = { 1, 3, 5, 7, 9, 11, ...}
 b) A1= {0, 2, 4, ,6, 8, 10, ...}A2 = { 1, 3, 5, 7, 9, 11, ...} 
 A3= { -2, -4, ,-6, -8, -10, ...} A4 = { -1, -3, -5, -7,-9, -11, ...} 
2. a) A1= {0, 6, 12, ,18, 24, 30, ...} A2 = {3, 9, 15, 21, 27, ...}
 b) A1= {0, 9, 18, 27, 36, ...} A2 = {3, 12, 21, 30, ...},
 A3= { 6, 15, 24, 33, 42, ...}
3. Sim. A1 = {1 +12n, n∈ N }= { 1, 13, 25, 37, 49, ..., } 
 A2 = {5 +12n, n∈ N } = {5, 17, 29, 41, 53, ... } e 
 A3 = { 9 + 12n, n∈ N }= {9, 21, 33, 45, 56, ...} constituem uma 
partição de S, pois os conjuntos são dois a dois disjuntos e sua 
união resulta S.
2.3. Cardinal da união e da interseção. 
Se você dispõe de dois ou mais conjuntos e quer saber quantos 
elementos tem o conjunto união desses conjuntos, como proceder? 
Faremos uso do princípio da inclusão – exclusão.
 Princípio da Inclusão – Exclusão. 
#(A∪B) = # (A) + #(B) – #(A∩B)
• Vejamos como descobrir a quantidade de elementos da união 
de dois conjuntos sendo conhecidos n(A), n(B) e )( BAn ∩ 
30
Matemática Discreta
Note que a quantidade de elementos de BA∪ é obtida pela 
quantidade de elementos que pertence:
só ao conjunto A: )BA(n)A(n)BA(n ∩−=∩ ,
só ao conjunto B: )()()( BAnBnBAn ∩−=∩ e
só a A e B: )( BAn ∩ .
Assim, podemos concluir que:
)()()()()()()()()( BAnBnAnBAnBAnBnBAnAnBAn ∩−+=∩+∩−+∩−=∪
Isso significa que, para calcular o número de elementos da união 
A ∪ B, incluímos os elementos de A, incluímos os elementos de B e 
excluímos os elementos de A ∩ B. 
Exemplo 2.3.1: Considere os conjuntos A = {1, 2, 3, 4, 5, 6, 7} 
B = { 4, 5, 6, 8}
Observe que # ( A ) = 7, # ( B ) = 4, # ( A ∩ B ) = 3, então 
# ( A ∪ B) = # (A) + # (B) – # ( A ∩ B ) = 7 + 4 – 3 = 8
# ( A ∪ B ∪ C) = # (A) + # (B) + # (C) – # (A ∩ B) – # (A ∩ C) – # (B ∩ C) + #(A ∩ B ∩ C).
• Podemos escrever A ∪ B ∪ C = (A ∪ B) ∪ C, de modo que:
#(A ∪ B ∪ C) = #((A ∪ B) ∪ C) = #(A ∪ B) + #C - #((A ∪ B) ∩ C) 
= #A + #B + #C - #(A ∩ B) - #[(A ∩ C) ∪ (B ∩ C)] 
= #A + #B + #C - #(A ∩ B) - #(A ∩ C) - #(B ∩ C) + #(A ∩ B ∩ C).
31
Matemática Discreta
Exemplo 2. 3. 2. Considere os conjuntos A = {1, 2, 3, 4, 5, 6, 7, 
10}, B = { 4, 5, 6, 7, 8, 11} C = { 5, 6, 7, 8, 9, 10 }.
Sabendo que A ∩ B = {4, 5, 6, 7}, A ∩ C = {5, 6, 7, 10}, 
B ∩ C = { 5, 6, 7, 8} e que A ∩ B ∩ C = {5, 6, 7}, podemos escrever 
que: 
#(A∪B∪C) = #(A) + #(B) + # (C) – #(A∩B) – #(A∩C) – #(B∩C) + 
#(A∩B∩C)
 = 8 + 6 + 6 – 4 – 4 – 4 + 3 = 11
A∪B∪C = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
• Se A e B são conjuntos disjuntos (A ∩ B = ∅), então 
#(A ∪ B) = #(A) + #(B).
Exemplo 2. 3. 3. Os conjuntos A = {2, 5, 7, 9 } e B = {4, 6, 8, 10 } 
são disjuntos, pois A ∩ B = ∅ , de modo que, o cardinal da união de A 
e B é #(A∪B) = #(A) + #(B) = 4 + 4 = 8
# I = 35, # F = 18, # (I∪F) = 42. # (I∪F) = # I + # F - # (I∩F) 
42 = 35 +18 - # (I∩F), de modo que # (I∩F) = 11.
Outra solução poderá ser dada usando os diagramas de Venn. 
Para isso, você define dois conjuntos I e F. Coloque inicialmente os 
elementos que pertencem à interseção I∩F. Como não sabemos, 
colocaremos o número x.
imagem
32
Matemática Discreta
O cardinal do conjunto dos que falam inglês e não falam francês é 
35 – x. Analogamente, o número de turistas que falam francês e não 
falam inglês é 18 – x. A soma desses elementos deve ser 42. Logo, 
devemos ter 35 – x + x + 18 – x = 42. A equação se reduz a 53 – x = 
42. Portanto, x = 11.
Exemplo 2. 3. 4. Todos os convidados de uma festa bebem café 
(A) ou chá (B); 13 bebem café, 10 bebem chá e 4 bebem café e chá. 
Quantas pessoas há neste grupo?
#(A∪B) = #(A) + #(A) - #(A∩B) #(A∪B) = 13 + 10 – 4 = 19
Exemplo 2. 3. 5. O controle de qualidade de uma fábrica introduziu 
na linha de montagem 42 peças com defeitos de pintura (A), 
embalagem (B) ou na parte eletrônica (C). Dessas peças, 28 tinham 
defeito na pintura, 17 tinham defeito na embalagem, 11 com defeito na 
parte eletrônica, 7 tinham defeito na embalagem e na parte eletrônica, 
3 tinham defeitos na pintura e na parte eletrônica e 6 com defeito na 
pintura e na embalagem. Quantas peças tinham os três defeitos?
#A = 28, #B = 17, #C = 11, #(A∩B) = 6, #(A∩C) = 3,
#(B∩C) = 7, #(A∩B∩C) = x
#(A∪B∪C) = #(A) + #(B) + # (C) – #(A∩B) – #(A∩C) – #(B∩C) + #(A∩B∩C)
42 = 28 + 17 + 11 – 6 – 3 - 7 + x
42 = 40 + x
x = 2
Você poderá usar diagramas de Venn para resolver esse problema. 
Vamos lá? Use as figuras seguintes:
Exemplo 2.3.6. Entre os americanos que tiraram férias no ano 
passado, 90% tiraram férias no verão, 65% no inverno, 10% na 
33
Matemática Discreta
primavera, 7% no outono, 55% no inverno e no verão, 8% na primavera 
e no verão, 6% no outono e no verão, 4% no inverno e na primavera, 
4% no inverno e no outono, 3% na primavera e no outono, 3% no 
verão, no inverno e outono, 3% no verão, no inverno e primavera, 2% 
no verão, no outono e primavera e 2% nono inverno, na primavera e 
outono. Que percentagem tirou férias nas quatro estações?
Para resolver este problema que envolve quatro conjuntos, 
podemos usar uma extensão do princípio da Inclusão – Exclusão 
para quatro conjuntos. O diagrama de Venn com quatro conjuntos 
deve apresentar 16 regiões. Na figura abaixo, apresentamos uma 
alternativa usando retângulos. Você acha que pode fazer um diagrama 
de Venn para quatro conjuntos usando quatro círculos e apresentando 
16 regiões? Tente fazer!
#(A∪B∪C∪D) = #(A) + #(B) + # (C) + # (D)
 – #(A∩B) – #(A∩C) – #(A∩D) – #(B ∩C) – #(B∩D) – #(C∩D)
 + #(A∩B∩C) + #(A∩B∩D) + #(A∩C∩D) + #(B∩C∩D)
 – #(A∩B∩C∩D)
100 = 90 + 65 + 10 + 7 – 55 – 8 – 6 – 4 – 4 – 3 + 3 + 3 + 2 + 2 - x
100 = 102 – x
x = 2%
Aprenda Praticando - Exercícios 2.3
Mostre que você entendeu bem as técnicas de cálculos do número 
34
Matemática Discreta
de elementos de um conjunto, usando o Princípio da Inclusão – 
Exclusão ou os diagramas de Venn. Caso tenha dificuldade, oriente-
se com seus tutores.
1. Em um congresso de informática, há 43 participantes do 
Curso de Java, 57 de Pascal Avançado e 29 de C++. Há 10 
participantes dos cursos de Java e Pascal Avançado, 5 em 
Pascal Avançado e C++, 5 em Java e C++, e dois matriculados 
nos três cursos. Quantos alunos estão inscritos ao menos em 
um curso do congresso?
2. Há quatro grandes grupos de pessoas, cada um com 1.000 
membros. Dois quaisquer desses grupos têm 100 membros 
em comum. Três quaisquer desses grupos têm 10 pessoas 
em comum. E há 1 pessoa em todos os quatro grupos. 
Conjuntamente, quantas pessoas há nesses grupos?
3. Num universo de 200 estudantes, 50 estudam Matemática, 140 
estudam Economia e 24 estudam ambos os cursos. Dos 200 
estudantes 60 são mulheres, das quais 20 estudam Matemática, 
45 estudam Economia e 16 delas estudam ambos os cursos. 
Determine, para o universo de estudantes, quantos são os 
homens que não estudam nem Matemática nem Economia.
4. Uma companhia, 240 dos seus empregados obtiveram aumento 
salarial, 115 obtiveram ascensão funcional e 60 obtiveram 
ambas as coisas. Quantos são os empregados sabendo que 
nenhum empregado deixou de ser promovido ou ter ascensão 
funcional ?
5. Em um grupo de 110 estudantes, 63 estudam Inglês, 30 estudam 
Francês e 50 estudam Alemão. Há 25 alunos que estudam 
apenas dois idiomas, 13 estudam Inglês e Francês, 30 estudam 
Inglês e Alemão e 12 estudam Francês e Alemão.
 a) Quantos estudam Inglês e Francês, mas não estudam 
Alemão? 
 b) Quantos alunos não estudam nenhum dos idiomas?
6. De 100 pessoas que foram pesquisadas, 52 são mulheres, 40 
almoçam, 40 jantam, 25 são mulheres que almoçam, 15 são 
mulheres que jantam, 20 são pessoas que almoçam e jantam, e 
12 são mulheres que almoçame jantam. Quantas pessoas são 
homens que não almoçam nem jantam? Quantas são mulheres 
35
Matemática Discreta
que não almoçam nem jantam?
7. No auditório de uma faculdade há um grupo de alunos, dos 
quais 12 cursam a disciplina A, 20 cursam a B, 20 cursam a C, 
10 cursam a D, 5 cursam A e B, 7 cursam A e C, 4 cursam A e 
D, 16 cursam B e C, 4 cursam B e D e 5 cursam as disciplinas 
C e D. Três alunos cursam as disciplinas A, B e C, 2 cursam 
A, B e D, 4 cursam B, C e D, e 3 cursam A, C e D. Apenas 2 
alunos cursam as quatro disciplinas e 71 alunos não cursam 
nenhumas das disciplinas citadas. Quantos são os alunos no 
auditório? 
Respostas dos Exercícios 2.3
 
Verifique aqui quantos exercícios acertou. Caso tenha errado ou 
não tenha conseguido fazer, mude o método de resolução (Princípio 
de Inclusão – Exclusão ou Diagrama de Venn). Discuta com seus 
colegas
1. 111 2. 3.439 3. 23 4. 295
5. a) 3 b) 12 6. a) 16 b) 24 7. 102
2.4. Produto Cartesiano.
 Se A e B são dois conjuntos, o produto cartesiano de A por 
B é o conjunto A x B = { (x,y) : x ∈ A e y ∈ B}. 
EXEMPLO 2.4.1 Sejam A = {a, b, c } e B = { a, b, d }. 
a) Liste todos os pares ordenados de A x B
 A x B = { (a, a), (a, b), (a, d), (b, a), (b, b), (b, d), (c, a), (c, b), (c, 
d) }
b) Liste todos os pares ordenados de B x A. 
 B x A = { (a, a), (b, a), (d, a), (a, b), (b, b), (d, b), (a, c), (b, c), (d, 
c) }
c) Liste todos os elementos do conjunto { (x,y)  A x B : x = y } { 
(a, a), (b, b) }
36
Matemática Discreta
Aprenda praticando - Exercícios 2.4
 
Você deverá listar os elementos dos seguintes conjuntos, pondo 
em prática os conceitos de produto cartesiano.
1. Sejam S ={ 0, 1, 2 ,3, 4 } e T = { 0 , 2, 4 } . Liste todos os 
elementos dos seguintes conjuntos:
 A = { (m,n) ∈ S x T : m < n }
 B = { (m, n) ∈ T x S ; m < n }
 C = { (m, n) ∈ S x T : m + n ≥ 3 }
 D = { (m,n) ∈ T x S ; m.n ≥ 4 }
 E ={ (m, n) ∈ S x S : m + n = 10 }.
 Obs.: S x S = S2
2. Liste pelo menos 6 elementos dos seguintes conjuntos:
 a) { (m,n) ∈ N2 : m = n }
 b) { (m,n) ∈ N2 : m + n é primo }
 c) { (m,n) ∈ N2 : m = 6 }
 d) { (m,n) ∈ N2 : min {m ,n } = 3}
 e) { (m,n) ∈ N2 : máx {m , n} = 3 }
 f) { (m,n) ∈ N2 : m2 = n }
Resposta
Logo em seguida, apresentamos respostas. Confira as suas. 
A = { (0, 2), (0, 4), (1, 2), (1, 4), (3, 4)} B ={(0,1), (0, 2), (0, 3), 
(0,4), (2, 3), (2, 4)}
C = { (0, 4), (1, 2), (1, 4), (2, 2), (2, 4), (3, 0), (3, 2), (3, 4), (4,0), 
(4,2), (4,4) }
D = { (1, 4), (2, 2), (2, 4), (3, 2), (3, 4), (4, 2), (4, 4).
2. a) { 0,0) , (1,1), (2,2), (3, 3), (4, 4), (5, 5), (6, 6) ...}
 b) {(0,2), (0,3), (0, 5), (0, 7), (1,2), (2,3), ...}
37
Matemática Discreta
 c) { (6,0), (6,1), (6,2), (6, 3), (6, 4), (6, 5), ...}
 d) { (3,3), (3,4), (3,5), (6,3), (7, 3), (8, 3), ...}
 e) (0,3), (1,3), (2,3), (3,0), (3,1), (3,2) (3,3)}
 f) { (1,1), (2,4), (3,9), (4,16), (5, 25), (6, 36), ...}
2.5 Produto Cartesiano de k conjuntos
Dados os conjuntos A1, A2, ..., Ak, o produto cartesiano A1 x A2 x ...x 
Ak é o conjunto de todas as n-uplas (a1, a2, ... , ak) tais que ai ∈ Ai.
Se #(A1)= n1, #(A2) = n2, ..., #(Ak)= nk então #(A1 x A2 x ... x Ak) = 
n1. n2. ... . nk.
Exemplo 2. 5. 1. Considere os conjuntos X = {1, 2}, Y = {a, b} e Z = 
{ m, n, p}. Liste os elementos dos seguintes produtos cartesianos.
a) X x Y x Z b) X x Y x Y c) X x X x X d) Y x X x Y x Z
 X x Y x Z = {(1, a, m), (1, a, n), (1, a, p), (1, b, m), (1, b, n), 
 (1, b, p) , (2, a, m), (2, a, n), (2, a, p), (2, b, m), (2, b, n), (2, b, p)} 
b) X x Y x Y = {(1, a, a), (1, a, b), (1, b, a), (1, b, b), {(2, a, a), 
 (2, a, b), (2, b, a), (2, b, b)}.
Exemplo 2. 5. 1. Se A é o conjunto das letras maiúsculas do 
alfabeto português (26 letras) e B é o conjunto dos naturais de 0 a 
9,represente sob a forma de conjunto, todas as placas de automóveis 
possíveis no Brasil. Quantas são essas placas?
Uma placa consiste em três letras seguidas por quatro algarismos. 
O número total de placas possíveis é dado pelo cardinal do produto 
cartesiano A x A x A x B x B x B x B.
# (A x A x A x B x B x B x B) = 26 x 26x 26 x 10 x 10 x 10 x 10 = 263 
x 104 = 175.760.000 placas.
Aprenda Praticando - Exercícios 2.5
Nesses exercícios, você terá oportunidade de explorar o conceito 
38
Matemática Discreta
de produto cartesiano envolvendo mais do que dois conjuntos.
1. Considere os conjuntos X = {1, 2}, Y = {a, b} e Z = { m, n, p}. 
Liste os elementos dos seguintes produtos cartesianos. 
 a) X x X x X b) Y x X x Y x Z
2. Calcular o cardinal dos conjuntos produto cartesiano da primeira 
questão.
3. Dados os conjuntos A = {x ∈ Z : -1 ≤ x ≤ 2} e B = {y ∈ Z : -1 ≤ y ≤ 
1}, pede-se:
a) Enumerar os elementos do conjunto A x B
b) Enumerar os elementos do conjunto B x A
c) Obter (A x B ) ∩ ( B x A )
d) Obter o cardinal de (A x B ) ∪ ( B x A )
2.6. Identidades de conjuntos.
As operações entre conjuntos, tais como: união, interseção, 
diferença, diferença simétrica e complemento satisfazem diversas 
propriedades. Essas propriedades são apresentadas na forma 
de igualdade entre conjuntos e são chamadas de identidades de 
conjuntos.
Identidades de Conjuntos
Exemplo 2. 6. 1: Prove que A ∩ (B - A) = ∅ usando as identidades 
de conjuntos.
Prova: A ∩ (B-A) = A ∩ (B ∩ A ) pela definição de diferença
 = A ∩ ( A ∩ B) pela propriedade comutativa
 = (A ∩ A ) ∩ B pela propriedade associativa
39
Matemática Discreta
 = ∅ ∩ B pela propriedade de complemento
 = ∅ por definição de interseção
Exemplo 2. 6. 2: Prove que A ∪ (B - A) = A ∪ B usando as 
identidades de conjuntos A ∪ (B-A) = A ∪ (B ∩ A ) = (A ∪ B) ∩ (A ∪ A ) 
= (A ∪ B) ∩ U = A ∪ B.
Exemplo 2.6.3: Provar a igualdade de De Morgan B A ∩=∪ BA 
Teremos que provar que: BA∪ ⊆ B A ∩ e que B A ∩ ⊆ BA∪ , 
usando as definições das operações entre conjuntos.
1.Suponha que x ∈ BA∪ . 2.De 1 temos que x ∉ A ∪ B. 3.De 2 
temos que x ∉ A e x ∉ B. 4.De 3 temos que x ∈ A e x∈B . 5. De 4, 
temos que x∈ A∩B . Provamos que BA∪ ⊆ B A ∩ 
1.Suponha que x ∈ B A ∩ . 2.De 1 temos que x ∈ A e x∈B 3.De 2 
temos que x ∉ A e x ∉ B. 4.De 3 temos que x ∉ A ∪ B. 5.De 4, temos 
que x ∈ BA∪ . Provamos que BA∪ ⊆ B A ∩
Logo B A ∩=∪ BA .
Exemplo 2. 6. 4: Provar que B A ∪=∩ BA (Igualdade de De 
Morgan), usando as definições das operações entre conjuntos.
1.Seja x ∈ BA∩ . 2.De 1 temos que x ∉ A ∩ B. 3.De 2 escrevemos 
x ∉ A ou x ∉ B. 4.De 3 temos que x ∈ A ou x ∈ B . 5.De 4, temos que 
x ∈ BA∪ e, assim B A ∪⊆∩ BA .
1.Seja x ∈ BA∪ . 2.De 1 temos que x ∈ A ou x ∈ B . 3.De 2, temos 
que x ∉ A ou x ∉ B. 4.De 3 escrevemos x ∉ A ∩ B. 5.De 4, temos que 
x ∈ BA∩ e, assim, BA∪ ⊆ BA∩ .
Logo B A ∪=∩ BA .
Exemplo 2. 6. 5: Provar que A =A , usando as definições das 
operações entre conjuntos.
Seja x ∈ A . Então x ∉ A . Logo x ∈ A. Assim provamos que A ⊆ 
A.
Seja x ∈ A. Então x ∉ A . Logo x ∈ A . Provamos que A ⊆ A . Logo 
A =A .
40
Matemática Discreta
Exemplo 2. 6. 6: Mostre por meio da tabela de pertinência que, 
dados os conjuntos A, B e C então (A – B) – C = A – (B ∪ C).
Devemos construir as tabelas de pertinência do conjunto do 
primeiro membro e do segundo membro. Os conjuntos iguais 
apresentam tabelas de pertinência iguais.
Exemplo 2.6.7: Mostre, por meio da tabela de 
pertinência que dados os conjuntos A, B e C tem-se que 
C - B)(A )C(B )C (A ⊕=∩⊕∩
Exemplos 2. 6.7: Simplifique ( )( ) BAABA ∩∪∩∪
. ( )( ) BAABA ∩∪∩∪ = ( )( ) BAABBAABAA  ))(( )( f=∩∪
= (B ∩ =)() BAA  ((B∩ A ) ∪ A ) ∪ B = =BA BA .
41
Matemática Discreta
Aprenda praticando - Exercícios 2.6Nos exercícios seguintes, pede-se que você apresente, por meio 
da tabela de pertinência de conjuntos, uma prova da igualdade de 
conjuntos. Compartilhe com seus colegas as tabelas de pertinência 
feitas por você.
1. Considere os conjuntos A, B e C. Prove, por meio da tabela de 
pertinência que:
 a) A ∩ (B - A) = ∅
 b) CBCBA ∪∪=∩∩ A 
 c) A∪(B-A) = A∪B
 d) (A ∪ B) ∩ (A ∪ B ) = A
 e) A – B = A ∩ B
 f) (A – B) – C = (A - C) – B
 g) (A – B) – C = (A - C) – (B – C).
2. Prove por meio da tabela de pertinência que, dados os conjuntos 
A, B e C, as igualdades abaixo são verdadeiras.
 
3. Use a tabela de pertinência para mostrar que (A ∪ B) - (A ∩B) 
= (A ∪ B) ∩ ( BA∪ ) para os conjuntos A e B.
4. Use a tabela de pertinência para verificar se ( )BA∩ ∩ BA∩ 
= (A∪B) ∩ ( A ∪ B ) para os conjuntos A e B.
42
Matemática Discreta
Saiba Mais
 
As operações com conjuntos estudadas nesse capítulo apresentam 
propriedades importantes que tem relação com outras estruturas que 
serão vistas nos capítulos seguintes.
Sugerimos consultar os seguintes livros para aprofundar os 
seus conhecimentos em relação às operações entre conjuntos, 
suas propriedades, as diversas formas de provar a igualdade entre 
conjuntos:
- ABE, Jair Minoro; PAPAVERO, Nelson. Teoria intuitiva dos 
conjuntos. São Paulo McGraw Hill:, 1997.
- ALENCAR Filho, Edgard de. Iniciação à Lógica Matemática. 
São Paulo: Nobel, 1995.
- GERSTING, Judith L. Fundamentos Matemáticos para a 
Ciência da Computação. Tradução Valéria de Magalhães Iorio. Rio 
de Janeiro: LTC, 2004.
- LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas 
de Matemática Discreta. Porto Alegre: Bookman, 2004
- Scheinerman, Edward R. Matemática Discreta: uma introdução. 
Tradução de Alfredo Alves de Farias. São Paulo: Pioneira Thomson 
Learning, 2003.
43
Matemática Discreta
Capítulo 3 - Introdução à Lógica 
Matemática
A Lógica Matemática é base para qualquer estudo nas áreas de 
Computação e Informática. Muitas demonstrações em Matemática 
e muitos algoritmos em Ciência da Computação usam expressões 
lógicas, tais como,“se P então Q” ou “se P e Q então P ou Q”. De 
modo que, para desenvolver qualquer algoritmo, em conseqüência, 
qualquer software, é necessário ter o conhecimento dos fundamentos 
da Lógica. Existem linguagens de programação, tais como Prolog e 
Haskel, que são desenvolvidas de acordo com o paradigma lógico.
Nesse capítulo, seguiremos os fundamentos da Lógica Booleana 
(George Boole2, 1815 – 1864), conjunto de princípios e métodos 
usados para distinguir sentenças verdadeiras de falsas. 
 Uma proposição é uma construção (sentença, frase, 
pensamento) à qual se pode atribuir juízo. Em lógica matemática, o 
tipo de juízo é o verdadeiro (V) ou falso (F), não ambos.
Para uma dada proposição p, denota-se por V(p) o seu valor 
verdade, de modo que V(p) = V se p é verdadeira e V(p) = F, se p é 
falsa.
São proposições:
 p: 6 é um número primo
 q: (72)3 = 76
 r: =1, 4142
 s: Linux é um software livre.
Para cada uma delas, o valor-verdade é como segue: V(p) = F, 
V(q)= V, V(r) = F, V(s) = V.
Não são proposições:
 p: Como vai você?
 q: Não chegue atrasado!
 r: x + 2 = 5 
 t: “O que estou dizendo agora é mentira”.
Acesse
2. http://www.
santarita.g12.br/
matematicos/gm1/
george_boole.htm
44
Matemática Discreta
3.1 Proposições compostas.
As proposições estudadas até aqui são ditas proposições simples, 
no sentido de que não podem ser decompostas em proposições 
mais simples. É possível, a partir de proposições simples, construir 
proposições mais complexas, chamadas de proposições compostas, 
usando os conectivos lógicos ∨ (OU), ∧ (E), ¬ (NÃ0).
 Negação ¬p. A negação de uma proposição é construída 
introduzindo a palavra não de forma apropriada ou prefixando-
se a expressão “não é fato que”, como nos exemplos a seguir:. 
Considerando uma proposição p, sua negação é denotada por ¬p. 
Alguns autores usam a notação ~p, outros usam p’.
p: Linux é um software livre ¬p : Linux não é um software livre.
q: Paris não fica na França. ¬q : Paris fica na França.
r : 1,5 2 ≥ ¬ r : 1,5 2 <
 A tabela-verdade descreve todas as possibilidades dos 
valores lógicos de uma proposição. A tabela lista todas as possíveis 
combinações de valores-verdade V ou F para as componentes simples 
envolvidas na composição da proposição composta. 
Quando a proposição é composta de duas proposições simples, 
sua tabela-verdade contém quatro linhas. Em geral, se uma proposição 
é composta de n proposições simples, sua tabela-verdade contém 2n 
linhas.
Vamos iniciar a construção das tabelas-verdade? Iniciaremos com 
a tabela da negação.
 Negação. A tabela – verdade da negação apresenta apenas 
duas linhas, pois envolve uma só proposição.
Isto é, se p é verdadeira, então ¬p é falsa. Se p é falsa, então ¬p 
é verdadeira.
 Conjunção. A conjunção de duas proposições p e q, denota-se 
por p ∧ q ( lê-se p e q ), tem valor lógico verdadeiro quando p e q são 
Atenção
Você percebeu 
semelhança da 
tabela ao lado 
com alguma 
tabela envolvendo 
conjuntos? 
Recorde a tabela 
de pertinência do 
complementar de 
um conjunto!
45
Matemática Discreta
ambas verdadeiras e, tem valor lógico falso, em qualquer outro caso. 
Abaixo segue a tabela da conjunção exemplos.
p: Windows é um sistema operacional
q: Java é uma linguagem de programação.
p∧q : Windows é um sistema operacional e q: Java é uma linguagem 
de programação 
V(p∧q)=V
p: Windows é um sistema operacional.
q: Java é uma planilha eletrônica
p∧q : Windows é um sistema operacional e Java é uma planilha 
eletrônica 
V(p∧q)=F
p: Windows é um editor de textos.
q: Java é uma linguagem de programação
p∧q : Windows é um editor de textos e Java é uma linguagem de 
programação 
V(p∧q)=F
p: Windows é um editor de textos. 
q: Java é uma planilha eletrônica.
p∧q : Windows é um editor de textos e Java é uma planilha 
eletrônica
V(p∧q)=F
 Disjunção. A disjunção de duas proposições p e q, denota-se 
por p ∨ q ( lê-se p ou q ) reflete a noção de que pelo menos uma 
das proposições deve ser verdadeira para que a resultante seja 
verdadeira. De modo que, a proposição p ∨ q é verdadeira, se pelo 
menos uma das proposições é verdadeira; falsa, se as proposições 
Atenção
E agora, você 
percebeu 
semelhança da 
tabela ao lado 
com a tabela 
de pertinência 
da interseção 
conjuntos?
46
Matemática Discreta
são todas falsas. A tabela-verdade da disjunção é :
Exemplos:
p: Windows é um sistema operacional.
q: C++ é uma linguagem de programação.
p∨q : Windows é um sistema operacional ou C++ é uma linguagem 
de programação 
V(p∨q)=V
p: Windows é um sistema operacional.
q: C++ é uma planilha eletrônica
p ∨ q : Windows é um sistema operacional ou C++ é uma planilha 
eletrônica
V(p ∨ q)=V
p: Windows é um editor de textos. 
Atenção
Nesta tabela, 
você percebeu 
semelhança 
com a tabela de 
pertinência da 
união conjuntos?
47
Matemática Discreta
q: C++ é uma linguagem de programação
p ∨ q : Windows é um editor de textos ou C++ é uma linguagem 
de programação 
V(p ∨ q)=V
p: Windows é um editor de textos.
q: C++ é uma planilha eletrônica.
p ∨ q : Windows é um editor de textos ou C++ é uma planilha
V(p ∨ q)=F
 Condicional. (Implicação). A condicional envolvendo duas 
proposições p e q, denota-se por p → q que é lida: “Se p então q”. A 
proposição p é chamada premissa (antecedente) e a proposição q é 
dita conclusão (conseqüente).
A condicional reflete a noção de que, partindo-se de uma premissa 
verdadeira (p verdadeira) obrigatoriamente chega-se a uma conclusão 
verdadeira (q verdadeira), para que a condicional p → q sejaverdadeira. Partindo-se de uma premissa falsa, qualquer conclusão 
pode ser considerada, e a condicional é verdadeira. A condicional 
é falsa apenas quando a premissa é verdadeira e a conclusão é 
falsa.
Resumo: a condicional p → q é:
Falsa, quando p é verdadeira e q falsa.
Verdadeira, nos outros casos.
A tabela-verdade da condicional é: 
48
Matemática Discreta
Exemplo:
Analisaremos a seguinte situação condicional: Pedro diz: “Se 
chover domingo então ficarei estudando”.
Vamos considerar as seguintes hipóteses e vejamos se Pedro 
cumpriu sua palavra (V):
a) Domingo choveu (V) e Pedro ficou estudando (V).
 Pedro cumpriu com a sua palavra (V)
b) Domingo choveu (V) e Pedro não ficou estudando (F).
 Pedro não cumpriu sua palavra (F)
c) Domingo não choveu (F) e Pedro ficou estudando (V).
 Pedro cumpriu sua palavra (V), pois não disse o que faria se 
não chovesse. Nesse caso, poderia ou não ficar estudando. 
d) Domingo não choveu (F) e Pedro não ficou estudando (F).
 Pedro cumpriu sua palavra (V), pelos motivos explicados na 
letra (c).
Exemplos: Considere as proposições seguintes:
p: Recife fica no Brasil q: 2 + 3 = 4
49
Matemática Discreta
r: 2 + 2 = 4 t: Recife fica na Índia
p → r : Se Recife fica no Brasil então 2 + 2 = 4 V(p→ r) = V
p → q : Se Recife fica no Brasil então 2 + 3 = 4 V(p→ q) = F
t → q : Se Recife fica na Índia então 2 + 3 = 4 V(t→ q) = V 
q → r : Se 2 + 3 = 4 então 2 + 2 = 4 V(q→ r) = V
 Bicondicional. A bicondicional envolve duas proposições p e 
q, é denotada por p↔q e é lida: “p se somente se q”, traduz a noção 
de uma dupla condicional, uma no sentido “ida” p→q e outra no 
sentido “volta” q→p.A tabela-verdade da bicondicional é dada abaixo:
Isto é, a bicondicional é verdadeira quando as proposições são 
ambas verdadeiras ou ambas falsas. A bicondicional é falsa, quando 
as proposições p e q têm valores-verdade distintos. Observe que a 
bicondicional p↔q tem o mesmo significado que (p→q) ∧(q→p). Faça 
a tabela-verdade.
 Duas proposições p e q são logicamente equivalentes se têm 
tabelas-verdade idênticas e escrevemos p ≡ q
Observe que a tabela-verdade da condicional p→q é a mesma da 
proposição composta ¬ p∨q
Dizemos que a condicional p → q é equivalente a ¬p∨q, isto é, p 
→ q ≡ ¬p∨q
50
Matemática Discreta
Aprenda Praticando - Exercícios 3.1
Você vai agora praticar a construção de tabela-verdade de 
proposições compostas e verificar as que são equivalentes, 
comparando a última coluna de cada uma delas. 
1. Mostre que as proposições abaixo são equivalentes, em cada 
caso:
 a) ¬(p∧q) ≡ (¬p)∨(¬q)
 b) (¬p)∧(¬q) ≡ ¬(p∨q)
 c) p→q ≡ ¬(p∧¬q) 
 d) p ∧(q∨r) ≡ (p∧q) ∨(p∧r)
 e) ¬(p→q) ≡ p∧¬q
 f) p ↔ q ≡ (p ∧ q) ∨ (¬p ∧¬q)
 g) p ↔ q ≡ (¬p ∨ q) ∧ (p ∨¬q) 
Respostas dos Exercícios 3.1
Apresentamos as respostas de alguns exercícios. Em relação aos 
outros exercícios, comente com seus colegas. Dificuldade? Peça 
ajuda ao seu tutor.
51
Matemática Discreta
a) ¬(p∧q) ≡ (¬p)∨(¬q)
b) (¬p)∧(¬q) ≡ ¬(p∨q) 
c) p→q ≡ ¬(p ∧¬ q) 
3.2 Tautologias e Contradições
 Tautologia (V) é uma proposição que toma o valor V para todas 
as possíveis atribuições de valor V e/ou F para as suas componentes 
simples nela presentes. Por exemplo, p ∨ ¬ p. 
 Contradição (F) é uma proposição que toma o valor F para todas 
as possíveis atribuições de valor V e/ou F para suas componentes 
simples nela presentes. Por exemplo, p ∧ ¬ p
 Contingência é uma proposição cuja tabela-verdade consta V 
e F. Por exemplo, a conjunção p ∧ q e a disjunção são exemplos de 
contingências.
52
Matemática Discreta
Exemplo 3.2.1 A proposição p →(p∨q) é uma tautologia. Confira a 
sua tabela-verdade.
Exemplo 3.2.2 A proposição (p→q) ∧(p∧ ¬ q) é uma contradição. 
Confira a sua tabela-verdade.
Aprenda Praticando - Exercícios 3.2
Decida quais as proposições abaixo são tautologias, contradições 
ou contingências. Faça a tabela.
1. Quais proposições abaixo são tautologias, contradições ou 
contingências?
 a) (p∨¬q) ∨(p∨q)
 b) (p∧q) → (p∨q)
 c) ¬p → (q→p)
 d) (x ∧ (x → y)) → y
 e) ((x→y) ∧ (y→z)) → (x→z) 
53
Matemática Discreta
 f) (p∨ ¬q) → (p→¬q)
 g) (¬p ∨ q) → (p→q)
 h) (p∧q) → (p↔q)
 i) (¬p) ∧(p∧¬q)
 j) ¬(p∨q) → (p↔q)
 j) (p→q) ↔(¬q→¬p)
2. Qual o valor-verdade das seguintes proposições?
 a) 8 é par ou 6 é ímpar
 b) 8 é par e 6 é ímpar
 c) 8 é impar ou 6 é ímpar
 d) Se 8 é ímpar, então 6 é par.
 e) Se 8 é ímpar, então 6 é ímpar
 f) Se 8 é impar ou 6 é par, então 8 < 6.
 g) Se 8 é par, e 6 é ímpar então 6 > 8.
Respostas dos Exercícios 3.2
1. a) Tautologia b) Tautologia. c) Contingência. d) Tautologia. 
e) Tautologia. f) Tautologia g) Tautologia. h) Tautologia.
i) Contingência. j) Tautologia. k) Tautologia.
2. a) V. b) V. c) F. d) V. e) V. f) F g) V.
3.3 Negação de conjunção e de disjunção 
 DE MORGAN
Considere a conjunção p ∧ q e a disjunção p ∨ q. 
A negação da conjunção é denotada por ¬(p ∧ q) e é equivalente 
a ¬p ∨ ¬q.
54
Matemática Discreta
A negação da disjunção é expressa por ¬(p ∨ q) e é equivalente a 
¬p ∧ ¬q. 
Confira fazendo a tabela-verdade: 
¬(p ∧ q) ≡ ¬p ∨ ¬q e de ¬(p ∨ q) ≡ ¬p ∧ ¬q.
3.4 Álgebra das proposições.
Você observou, nesse capítulo, que as proposições, a exemplo 
dos conjuntos, satisfazem várias propriedades que estão listadas na 
tabela abaixo. Cabe ao leitor, identificar aquelas propriedades que 
correspondem às dos conjuntos:
Exemplo 3.3.1
a) A negação de “Hoje é segunda-feira e amanhã não choverá” é 
“Hoje não é segunda-feira ou amanhã choverá”.
b) A negação de 2 < 7 ou 3 é par é : 2 ≥ 7 e 3 é ímpar.
Exemplo 3.3.2. Considere as seguintes proposições:
 p: Rosas são vermelhas. q:Violetas são azuis. 
 r: Cravos são brancos. s: Cravos são vermelhos.
A forma simbólica usando os conectivos ∧, ∨ , ¬ , → e ↔, das 
seguintes proposições compostas:
a) Rosas são vermelhas e violetas são azuis.
a) p∧q
55
Matemática Discreta
b)Rosas não são vermelhas ou violetas não são azuis.
b) ¬p ∨¬q
c) Cravos são brancos ou vermelhos.
c) r∨s
d) Cravos não vermelhos ou violetas não são azuis.
d) ¬s∨¬q
e) Não é verdade que violetas são azuis e rosas são vermelhas.
e) ¬(q∨p)
f) É falso que cravos são vermelhos ou brancos.
f) ¬(s∨r)
g) Se cravos são brancos, então cravos são vermelhos e violetas 
são azuis.
g) r → s ∧ q
h) Se rosas não são vermelhas, então violetas não são azuis ou 
cravos não são brancos.
h) ¬p →¬ q ∨ ¬r
i) Se violetas são azuis e cravos brancos, então é falso que cravos 
são brancos ou vermelhos. 
i) (q∧r)→¬(r∨s)
j) Rosas são vermelhas se e somente se cravos são brancos.
j) p ↔r
Exemplo 3.3.3. Os conectivos lógicos E (AND) , OU (OR) e Não 
(NOT), correspondentes, respectivamente a, ∧, ∨ e ¬, são usados em 
algumas linguagens de programação conjuntamente com expressões 
verdadeiras ou falsas para produzir um valor lógico final.
Suponha as seguintes variáveis
“Fluxo_de_saída”, “Fluxo _de_entrada” e “Pressão” e o seguinte 
programa de computador:
If [ (Fluxo_de_saída > Fluxo _de_entrada ) and not ((Fluxo_de_saída > Fluxo 
_de_entrada) and Pressão <1000 )] 
 do Ponha água;
56
Matemática Discreta
Else
 do Desligue a máquina;
Pondo P = Fluxo_de_saída > Fluxo _de_entrada e Q = Pressão 
<1000, a expressão usada no programa se escreve P ∧¬ (P ∧Q).
Essa expressão pode ser simplificada assim:
P ∧¬ (P ∧Q) = P ∧ ( ¬P ∨ ¬Q) = (P ∧¬P) ∨ (P ∧¬Q) = 0 ∨ (P 
∧¬Q) = P ∧¬Q.
Assim o programa poderia ser reescrito na forma:
If ((Fluxo_de_saída > Fluxo _de_entrada ) and not ( Pressão < 1000))
 do Ponha água;
else
 do Desligue a máquina;
Exemplo 3. 3. 4 Suponhaque P, Q e R representam condições 
que serão verdadeiras ou falsas quando certo programa é executado. 
O programa manda realizar uma tarefa somente quando P ou Q for 
verdadeira ( mas não ambas) e R for falsa. Escreva uma proposição 
usando os conectivos and , or e not que seja verdadeira apenas 
dessas condições.
Resp. ( (P and not Q) or (not P and Q) and not R ) ) ou seja ( (P 
∧¬Q) ∨ ( ¬P ∧Q) ) ∧ ¬R.
Exemplo 3. 3. 5 Reescreva o programa abaixo com uma 
expressão condicional mais simples. A função impar(número) tem 
valor verdadeiro se n é ímpar.
Se não ( (valor 1 < valor 2) ou ímpar (número) ) ou ( não (valor 
1 < valor 2) e ímpar(número)) então
faça Alguma Coisa;
Caso contrário
faça Outra Coisa;
Resp. Sugestão: Ponha A = valor 1 < valor 2 e B = 
impar(número) 
A expressão condicional é : ¬(A ∨ B) ∨ (¬A ∧B)
Assim, ¬(A ∨ B) ∨ (¬A ∧B) = ( ¬A ∧ ¬B) ∨( ¬A ∧B) = ¬A ∧( ¬B ∨ 
B) = ¬A∧(T) = ¬A
57
Matemática Discreta
Aprenda Praticando - Exercícios 3.3
Novamente, solicitamos que revise o conteúdo dessa seção e 
resolva os exercícios seguintes.
1. Determinar as proposições compostas por conjunção ∧ com as 
proposições simples p e q, antecedidas ou não por negação 
¬, que satisfazem a cada um das tabelas-verdade abaixo 
indicadas.
2. Repetir o exercício com disjunção ∨.
3. Repetir o exercício com condicional →.
4. Mostre por meio da tabela-verdade que as proposições p→q e 
¬q → ¬ p são equivalentes.
 Use a equivalência para resolver as questões seguintes.
58
Matemática Discreta
5. (ESAF / AFTN) Considere as seguintes afirmações:
 - Se Carlos é mais velho do que Pedro, então Maria e Júlia têm 
a mesma idade.
 - Se Maria e Júlia têm a mesma idade, então João é mais moço 
do que Pedro.
 - Se João é mais moço do que Pedro, então Carlos é mais velho 
do que Maria.
 Ora, Carlos não é mais velho do que Maria. Então:
 a) Carlos não é mais velho do que Júlia e João é mais moço do 
que Pedro.
 b) Carlos é mais velho do que Pedro, e Maria e Júlia têm a 
mesma idade.
 c) Carlos e João são mais moços do que Pedro.
 d) Carlos é mais velho do que Pedro e João é mais moço do 
que Pedro.
 e) Carlos não é mais velho do que Pedro, e Maria e Júlia não 
têm a mesma idade.
6. Se Rodrigo mentiu, então ele é culpado. Logo:
 a) Se Rodrigo não mentiu, então ele não é culpado.
 b) Rodrigo é culpado.
 c) Se Rodrigo não é culpado, então ele não mentiu.
 d) Rodrigo mentiu.
 e) Se Rodrigo é culpado, então ele mentiu 
59
Matemática Discreta
Respostas dos Exercícios 3.3 e 3.4
1. 
5. e
6. c.
3.5 Funções proposicionais. Quantificadores.
 Considere as seguintes sentenças p: 3 + 6 = 9 q: x + 4 < 9.
A sentença p, como sabemos, é verdadeira, ao passo que, nada 
podemos afirmar sobre o valor lógico da sentença q enquanto x 
não for identificado. Dependendo do valor de x, esta sentença pode 
assumir o valor verdadeiro ou falso. Nesse caso, a sentença q é dita 
uma sentença aberta ou função proposicional.
De um modo geral, p(x) significa que x tem a propriedade p. Nas 
sentenças abertas p(x), p(y), os símbolos x, y são chamados de 
variáveis. O conjunto de valores que a variável pode assumir constitui 
o seu conjunto universo U. O subconjunto de U para os quais o valor 
lógico da sentença aberta é verdadeiro é o conjunto V, dito conjunto-
verdade da sentença aberta. Exemplos.
a) Considere a proposição p(x) “x + 2 > 9 “ com x ∈ N. O conjunto-
verdade V = {8, 9, 10 ,l 1, ....}
b) A proposição p(x) “x + 7 < 4“ com x ∈ N tem conjunto verdade 
V = φ.
c) A proposição p(x) “ x + 7 > 4 “ com x ∈ N tem V = N.
Os exemplos acima mostram que, se uma proposição p(x) é 
definida para x do universo U, então p(x) pode ser verdade para todo 
x ∈ U, para algum x ∈ U, ou para nenhum x ∈ U.
3.5.1 Quantificadores.
Usaremos o símbolo ∀, chamado quantificador universal, para 
exprimir o fato de que “ para todo x em um conjunto, a proposição 
Atenção
Atenção
A sentença ∀ x, 
p(x) é verdadeira se 
o conjunto-verdade 
de p(x) e o seu 
conjunto universo 
são iguais, isto é, 
U=V e, falsa , se 
U ≠ V.
A sentença ∃x, p(x) 
é verdadeira se o 
conjunto-verdade 
de p(x) é não vazio, 
V ≠ φ e, falso se V 
= φ
60
Matemática Discreta
p(x) é verdadeira”. Uma proposição do tipo “ Para todo x, p(x) “ é 
simbolicamente denotada por “∀x, p(x)”. 
Exemplos: 
∀x∈N, x  = x é verdadeira pois V(p(x)) = N ∀x∈Z, x  = x 
é falsa, pois V(p(x)) = N ≠ Z
∀x∈N*, x2 + 1 ≥ 2 é verdadeira, pois V(p(x)) = N
* ∀x∈Z, x2 ≥ 0 é 
verdadeira, pois V(p(x)) = Z
Analogamente, no caso de proposições que envolvem expressões 
do tipo “existe”, “há pelo menos um”, “algum”, usaremos o símbolo ∃, 
chamado quantificador existencial, para exprimir o fato de que para 
um ou mais elementos de um dado conjunto U a proposição p(x) é 
verdadeira. Uma proposição do tipo “existe um x tal que p(x) ” pode 
ser escrita simbolicamente: “∃x, p(x)”.
Exemplo: A proposição “ ∃x, x∈N” tem os seguintes significados: 
“ existe um x tal que x∈N”, “algum número é natural”, “existe pelo 
menos um número natural”.
Exemplos: ∃n, n ∈ N : n + 2 = 5 é verdadeira, pois V(p(n)) = { 3 } 
≠ ∅ 
∃x, x ∈ N: x + 2 = 0 é falsa, pois V(p(x)) = ∅
∃x∈{1, 2, -3, -4}, x2 + x - 6 = 0 é verdadeira, pois V(p(x)) = {2, -3}
∃n, n ∈ N, n! < 10 é verdadeira, pois V(p(n)) = {0, 1, 2, 3}
3.5.2 Negação de sentenças quantificadas
Exemplos: Seja A = {1, 2, 3, 4, 5 }
a) A negação da sentença ∃x ∈ A, x + 3 = 10 é ∀x∈A, x + 3 ≠ 
10
b) A negação da sentença ∃x ∈ A, x + 3 < 5 é ∀x∈A, x + 3 ≥ 5 
c) A negação de ∀x∈A, x + 3 < 10 é ∃x ∈ A, x + 3 ≥ 10 
d) A negação de ∀x∈A, x + 3 ≤ 7 é ∃x ∈ A, x + 3 > 7 
Atenção
Atenção
A negação da 
sentença ∀x, p(x) 
é ∃x, ¬ p(x).
Logo, ¬ (∀x, p(x)) 
é equivalente a ∃x, 
¬ p(x).
A negação da 
sentença ∃x, 
p(x) é ∀x, ¬ p(x).
Logo, ¬ ∃ (x, p(x)) 
é equivalente a∀x, 
¬ p(x).
61
Matemática Discreta
Aprenda Praticando - Exercícios 3.4
1.Escreva as proposições seguintes utilizando a notação de 
quantificador (isto é, use os símbolos ∀ e/ou ∃ ).
 a) Todo inteiro é primo.
 b) Há um inteiro que não é primo.
 c) Existe um inteiro cujo quadrado é 4.
 d) Todos os inteiros são divisíveis por 5.
 e) Algum inteiro é divisível por 7.
 f) O quadrado de qualquer inteiro é não negativo.
 g) Para todo número inteiro x, existe um inteiro y tal que x.y =1. 
 h) Existem dois inteiros x e y tais que x/y =10.
2. Escreva a negação de cada uma das proposições do problema 
anterior. Dê sua resposta por extenso e simbolicamente.
3. Assinale como verdadeiras ou falsas as proposições abaixo 
relativas aos números inteiros:
 a) ∀x, ∀y, x + y = 0 b) ∀x, ∃y, x + y = 0
 c) ∃x, ∀y, x + y = 0 d) ∃x, ∃y, x + y = 0 
 e) ∀x, ∀y, x.y = 0 f) ∀x, ∃y, x.y = 0
 g) ∃x, ∀y, x.y = 0 h) ∃x, ∃y, x.y = 0.
4. Para cada uma das proposições seguintes, escreva a 
negação.
 a) ∀x ∈ Z, x < 0.
 b) ∃ x ∈ Z, x = x + 1
 c) ∃ x ∈ N, x > 10
 d) ∀ x ∈ N, x + x = 2x
 e) ∃ x ∈ Z, ∀y ∈ Z, x > y. 
 f) ∀ x ∈ Z, ∀y ∈ Z, x = y. 
62
Matemática Discreta
 g) ∀ x ∈ Z, ∃y ∈ Z, x + y = 0.
5. Mostre por meio da tabela-verdade se as proposições abaixo 
são equivalentes:
 a) p ∧ p ⇔ p b) p ∨ p ⇔ p
 c) p ∨ q ⇔ q ∨ p d) p ∧ q ⇔ q ∧ p
 e) p∧(q ∨ r) ⇔ (p∧ q) ∨ (p∧ r)
 f) p∨(q ∧ r) ⇔ (p∨ q) ∧ (p∨ r)
 g) p∧(q ∨ r) ⇔ (p∧ q) ∨ (p∧ r)
 h) ( p → q) ⇔ ( q’ → p’)
6. Considere as seguintes sentenças abertas cujo domínio 
consiste nos números inteiros Z:
 O(x) : x é impar L(x) : x < 10 G(x) : x > 9
 Qual o valor-verdade de cada uma das seguintes sentenças 
abertas?:
 a) ∃x : O(x) 
 b) ∀x [ L(x) → O(x) ] 
 c) ∃x [ L(x) ∧ G(x) ]d) ∀x [L(x) ∨ G(x)] 
7. Sabendo que as proposições “x = 0” e “x = y” são verdadeiras 
e que as proposições “y = z” e “y = t” são falsas, determinar o 
valor lógico de cada uma das seguintes proposições:
 a) (x = 0 ) ∧(x = y) → (y ≠ z)
 b) (x ≠ 0 ) ∨ (y = t) → (y = z) 
 c) (x = 0 ) → (x ≠ y) ∨( y ≠ t)
 d) (x ≠ 0 ) ∨(x ≠ y) → (y ≠ z) 
8. Determine o valor lógico de cada uma das sentenças a seguir, 
considerando o conjunto universo de todos os números 
inteiros Z.
 a) ∀n, n2 ≥ 0 b) ∃n, n2 = 2 c) ∀n, n2 ≥ n 
 d) ∀n ∃m, n2 < m. e) ∃n ∀m, n < m2 f) ∃n ∀m, n + m = 0, 
63
Matemática Discreta
 g) ∃n ∀m, n.m = m h) ∃n ∃m, n2 + m2 = 5,
 i) ∃n ∃m, n2 + m2 = 6. 
 j) ∃n ∃m, (n + m = 4) ∧ (n – m = 1) 
 k) ∃n ∃m, (n + m = 4) ∧ (n – m = 2) 
 l) ∀n ∀m ∃p, p = 
2
nm + .
 m) ∃n, ∀m , n + m = m n) ∀m, ∃n, n2 + 1 = m 
9. Determine o valor lógico de cada uma das sentenças a seguir, 
considerando o conjunto universo de todos os números reais 
R.
 a) ∃x, x2 = 2 b) ∃x, x2 = - 4 c) ∀x ∃y, x2 = y 
 d) ∀x ∃y, x = y2 e) ∃x ∀y, x.y = 0 f) ∀x ∃y, x + y ≠ y + x
 g) ∀x, x ≠0, ∃y, x.y = 1 h) ∃x ∀y, y ≠0, x.y =1
 i) ∀x ∃y, x + y = 1 j) ∃x ∃y, ( x + 2y = 2) ∧(2x + 4y = 5)
 k) ∀x ∀y ∃z, z = 
2
yx +
10. Considere as seguintes proposições: p(x): “ x é par” , q(x) : “x 
é divisível por 3” e r(x): “x é divisível por 4”. Determinar o seu 
valor lógico cada uma das proposições abaixo:
 a) *Nx∈∀ , p(x+2) ∧ q(x) b) *Nx∈∀ , p(x) → r(x) 
 c) x∃ ∈N*, q(x) → q(x+5) d) x∃ ∈N*, r(x) ∧ r(x -2) 
Respostas dos Exercicios 3.4
8. a) V b) F c) V d) V e) V f) F g) V h) V i) F
 j) F k) V l) F m) V n) F
9. a) V b) F c) V d) F e) V f) F g) V h) F i) V
 j) F k)V.
Atenção
Procure ensinar 
aos seus colegas 
tudo aquilo que 
você aprender, 
pois lecionar é uma 
ótima maneira de 
aprender.
64
Matemática Discreta
Saiba Mais
 
Neste capítulo, você teve oportunidade de conhecer os 
fundamentos da lógica matemática, fortemente empregada, nas 
áreas de informática e computação. Percebeu que existe uma estreita 
relação entre as propriedades das operações entre com juntos e as 
proposições lógicas. Você poderá aprender mais sobre proposições, 
consultando os seguintes livros sobre Lógica Matemática:
ALENCAR Filho, Edgard de. Iniciação à Lógica Matemática. São 
Paulo: Nobel, 1995.
LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas 
de Matemática Discreta. Porto Alegre: Bookman, 2004
65
Matemática Discreta
Capítulo 4 - Portas Lógicas
Os circuitos lógicos (redes lógicas) são estruturas concebidas 
com base em certos circuitos elementares designados portas lógicas. 
São vistos como uma máquina L que contém um ou mais dispositivos 
de entrada e apenas uma saída S. Os dispositivos de entrada em L 
enviam um sinal, ou seja, um bit, 0 ou 1, ao circuito L que o processa 
e manda um sinal, um bit de saída S.
A descrição de circuitos construídos pela combinação de portas 
lógicas, exige um novo tipo de álgebra, denominada Álgebra de 
Boole em que as variáveis e funções tem apenas valores 0 e 1. Na 
Álgebra de Boole são usados três operadores E, OU e NÃO (AND, OR 
e NOT) para efetuar comparações e as quatro operações aritméticas 
básicas.
Os computadores atuais utilizam a Álgebra de Boole em microchips 
que contém centenas de pequenos interruptores combinados em 
portas lógicas que produzem os resultados das operações em 
linguagem binária.
Entre os circuitos elementares destacamos as portas lógicas 
seguintes: porta OR, porta AND e porta NOT.
4.1 Porta Not (Não)
A porta NOT inverte o sinal de entrada (executa a negação do sinal 
de entrada), ou seja, se o sinal de entrada for 0 ela produz uma saída 
1, se a entrada for 1 ela produz uma saída 0. Também é chamada de 
porta inversora.
Se A é uma variável binária então a porta NOT transforma A em 
NOT(A), ou simplesmente A , de modo que se A = 0 então NOT(A) = 
A = 1, se A = 1 então NOT(A) = A = 0. Usaremos também a notação 
A’ para a negação. O símbolo e a tabela-verdade da porta NOT são as 
seguintes:
66
Matemática Discreta
4.2 Porta Or (Ou)
A porta OR combina dois ou mais sinais de entrada de forma 
equivalente a um circuito em paralelo, para produzir um único sinal 
de saída, ou seja, ela produz uma saída 1, se qualquer um dos sinais 
de entrada for igual a 1; a porta OR produz um sinal da saída igual a 
0 apenas se todos os sinais de entrada forem 0. Usaremos o sinal + 
para indicar a operação OR (OU). A tabela-verdade e o símbolo da 
porta OR com duas entradas são: 
 
Exemplo: Considere um detector de incêndio com dois sensores 
(entradas A e B) e uma campainha para alarme (saída S). Se qualquer 
um dos sensores for acionado (1) detectando sinal de incêndio, a 
campainha toca (1). O circuito lógico, a função booleana e a tabela – 
verdade correspondem às de uma porta OR.
Porta OR com três entradas A tabela verdade apresenta 23 = 8 linha
 
67
Matemática Discreta
4.3 Porta And (E)
A porta AND combina dois ou mais sinais de entrada de forma 
equivalente a um circuito em série, para produzir um único sinal de 
saída, ou seja, ela produz u ma saída 1, se todos os sinais de entrada 
forem 1; caso qualquer um dos sinais de entrada for 0, a porta AND 
produz um sinal de saída igual a 0. Usaremos o símbolo . para a 
operação AND (E).
A tabela-verdade e o símbolo da porta AND com duas entradas 
são:
Exemplo: Uma campainha que toca (saída S) se o motorista 
der partida no motor do carro (entrada A) sem estar com o cinto de 
segurança afivelado (entrada B). Esboce o circuito lógico, a função 
booleana e a tabela-verdade correspondente. Convenção: ignição 
for acionada (1) e o cinto estiver desafivelado (1), a campainha toca 
(1). Caso contrário, a campainha não toca. O circuito lógico, a função 
booleana e a tabela–verdade correspondem às de uma porta AND.
Atenção
 
Observe que a tabela-verdade da porta NOT é idêntica à tabela de 
pertinência do complementar. A tabela da porta OR tem semelhança 
dom a tabela de pertinência da união e a da porta AND com a tabela 
de pertinência da interseção. Há semelhança também com as tabelas-
verdade para as proposições ¬p ( Negação), p∨q ( disjunção) e 
p∧q ( conjunção). A diferença é que, nas tabelas das portas e nos 
conjuntos usamos 0 e 1, e nas proposições usamos F e V.
68
Matemática Discreta
Porta AND com três entradas A tabela verdade apresenta 23 = 8 linha
4.4. Porta Nand e Porta Nor.
Em muitos casos é necessário fazer combinações de portas 
básicas, formando portas mais complexas, de modo a reduzir espaços 
nos diagramas dos circuitos.
Por exemplo, a porta NAND nada mais é do que a negação da 
porta AND, com saída S = BA. . A tabela-verdade e sua representação 
são dadas abaixo:
A porta NOR é obtida pela negação da porta OR e sua saída é 
representada por S = BA + . A sua tabela-verdade e representação 
simbólica são:
4.5. Portas XOR e XNOR
Destacamos ainda as portas XOR e XNOR representadas 
respectivamente pelos símbolos e tabelas a seguir:
69
Matemática Discreta
PORTA XOR A ⊕ B = (A + B) . (A.B)’ = A.B’ + A’.B
PORTA XNOR BA⊕ = ((A + B). (A.B)’ )’ = (A’+B).(A+B’) 
4.6 Portas Lógicas Equivalentes
Dizemos que 2 portas lógicas são equivalentes se têm a mesma 
tabela-verdade.
Exemplo: S1 = (A+B) . (A + C) S 2 = A+ B.C
4.7 Propriedades das Portas Lógicas.
Apresentamos abaixo, uma tabela contendo identidades em 
Álgebra de Boole.
70
Matemática Discreta
Observe que podemos provar que os circuitos S1 = (A+B) . (A + C) 
e S 2 = A + B.C são equivalentes aplicando as identidades acima:
S1 = (A+B) . (A + C) = A. (A+C) + B(A+C) = A.A + A.C + B.A + B.C = 
A + A.C + B.A + B.C= A( 1+ C) + B.A + B.C = A.1 + A.B + BC = A(1 + 
B) + B. C = A.1