conjuntos e logica

Prévia do material em texto

Conjuntos e Lógica
Matemática Discreta – Reinaldo Madarazo - 2014
Noção Intuitiva de Conjuntos
• É uma coleção não-ordenada de objetos.
• Normalmente todos os objetos possuem a 
mesma propriedade.
• Qualquer objeto que contenha a 
propriedade é um elemento do conjunto.
• Qualquer objeto que não contenha a 
propriedade não é elemento do
conjunto.
Notação de Conjuntos
• Letras maiúsculas denotam CONJUNTOS.
• O símbolo ϵ denota que um elemento pertence ao conjunto.
• Letras minúsculas representam um elemento ou membro de 
um conjunto.
• Assim:
• indica que a é elemento do conjunto A.
• indica que a não é elemento do conjunto A.
– Ex.: Se A={violeta,mostarda,vermelho}
então 
e 
Aa
Aa
Amostarda
Apúrpura
Observações
• Como um conjunto é uma coleção não-
ordenada de objetos, a ordem na qual os 
elementos são escritos não importa:
– {violeta, mostarda, vermelho} é o mesmo
conjunto que {mostarda, vermelho, violeta}.
• Cada elemento é listado apenas uma vez; 
a repetição de elementos seria re-
dundante.
Igualdade de conjuntos
• Dois conjuntos são iguais se possuem os 
mesmos elementos.
• Em notação matemática:
A=B significa
• Ex.: Se A={1,2,3} e B={x,y,z} e A=B
então x=1, y=2, z=3.
)]())[(( AxBxeBxAxx 
Propriedades da Igualdade
• Sejam A, B e C três conjuntos:
– 1. A=A (reflexiva)
– 2. Se A=B então B=A (simétrica)
– 3. Se A=B e B=C então A=C (transitiva)
Descrição de conjuntos
• Um conjunto pode ser descrito das 
seguintes formas:
– Listando (ou listando parcialmente) os 
elementos.
– Usando recursão para descrever e gerar o 
conjunto de elementos.
– Descrevendo uma propriedade P que 
caracterize o conjunto de elementos.
Descrição de conjuntos
• Listas:
– Para conjuntos finitos podemos representá-
lo apenas descrevendo seus elementos:
A={2, 4, 6}
– Para conjuntos infinitos, embora seja 
impossível listar todos os elementos, para 
alguns deles é possível indicar um padrão:
A={2, 4, 6,...}
Forma recursiva
• Em um conjunto infinito, pode ocorrer de não ser muito 
fácil identificar o padrão na forma de listagem.
• Assim, um conjunto pode ser definido definindo 
explicitamente um de seus elementos e depois definindo 
os demais elementos em termos dos elementos já 
conhecidos.
• Por exemplo:
1. 2 ϵ A
2. Se n ϵ A, então (n + 2) ϵ A
Propriedade Característica
• É a forma mais clara de representar um 
conjunto, seja finito ou infinito.
• Assim, A pode ser definido como:
A = {x | x é inteiro positivo par}
• A forma geral é:
A = {x | P(x)}
ou: A={x|P(x)} significa:
])(())()[( AxxPxPAxx 
Exercícios
• Descreva cada um dos seguintes conjuntos, listando 
seus elementos:
– a. {x|x é um inteiro e 3<x≤7}
– b. {x|x é um mês com exatamente 30 dias}
– c. {x|x é a capital do Brasil}
• Descreva cada um dos seguintes conjuntos, fornecendo-
lhes uma propriedade característica:
– a. {1,4,9,16}
– b. {Huguinho, Zezinho, Luisinho}
– c. {2, 3, 5, 7, 11, 13, 17, ... }
Conjuntos-Padrão
• São alguns conjuntos que aparecem com 
grande frequência:
• N: conjunto de todos números inteiros não 
negativos (note que 0 ϵ N). 
• Z: conjunto de todos os inteiros.
• Q: conjunto de todos os números racionais.
• R: conjunto de todos os números reais
• C: conjunto de todos os números 
complexos.
Conjuntos Universo e Vazio
• Conjunto Universo: Conjunto maior que 
engloba todos os elementos dos conjuntos 
considerados.
– Ex.: Conjunto de todos os pontos de um plano; 
conjunto de todas as pessoas do mundo.
– Símbolo: U
• Conjunto Vazio: não possui elementos.
– Ex.:
– Símbolo: ?
}3|{ 2  x e positivo inteiro um é xxS
Exercícios
• Descreva cada um dos conjuntos definidos 
abaixo:
– a.
– b. 
– c.
– d.
– e. 
)} e }2,1,0{)((|{ 3yxyyxA 
)} e )(( e |{ yxNyyNxxB 
)})(( e |{ yxNyyNxxC 
}}5,4,3,2{)(( e |{ yxyyNxxD 
} e }3,2{ e }2,1{)()((|{ zyxzyzyxE 
Subconjuntos
• Dizemos que A é subconjunto de B
quando todo elemento de A é também 
elemento de B.
• Matematicamente: 
• Notação: Se A é subconjunto de B 
representamos por: 
)__________)((  Axx
BA
Subconjuntos
• Se A é subconjunto de B, escrevemos:
• Se A é subconjunto de B, mas A≠B (existe 
pelo menos um elemento de B que não é 
elemento da A), então A é dito um 
subconjunto próprio e é denotado por:
BA
BA
Exemplos
• Sejam:
A={1,7,9,15}
B={7,9}
C={7,9,15,20}
• Então as seguintes sentenças são verdadeiras:
C 
A{7} 
B{7,9} 
C15 




CA
AB
AB
CB
Exercícios
• Sejam:
• Quais das seguintes sentenças são verdadeiras? 
)}2 e )((|{
}20,16,12,10{
}5 e |{
yxNyyxC
B
xNxxA



AB
ABxNxx
BB
CA
CCA
ABCB






 l) }{ k)
5 j) }20 e |{ i)
}12{ h) }12{ g)
}13,12,11{ f) }13,12,11{ e)
26 d) c)
 b) a)
Propriedades
• 1. Simétrica
• 2. Simétrica
• 3. Reflexiva 
• 4. Transitiva
• 5. Transitiva
ABBABA  e 
AAAA 
ABBABA  e 
CACBBA  e Se
CACBBA  e Se
Conjuntos de Conjuntos
• Dado um conjunto S, podemos criar um 
novo conjunto cujos elementos sejam 
todos os subconjuntos de S.
• Este novo conjunto é chamado de 
Conjunto das Partes de S, representado 
por P (S).
• P (S) conterá pelo menos, e S, pois 
são sempre verdadeiras.

SSS  e 
Partes de um Conjunto
• O número de elementos de P (S) pode ser 
obtido por: n(P (S))=2n(S), onde n(S) é o 
número de elementos de S (cardinalidade).
Exemplos
• Seja S={1,2,3}. Então n(S)=3 e n(P (S))=23=8.
Assim:
P (S)={ ,{1},{2},{3},{1,2},{1,3},{2,3},S}
• Seja S={1,2,3,4}. Seja A o conjunto de conjuntos 
de S que contém exatamente 3 elementos de S:
A={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
O conjunto A é chamado de Classe de A e 
temos que:
A P (S)
• Construa a Classe B de S que contém o 
número 2 e outros dois elementos de S.


Operações em Conjuntos
• É possível realizar operações envolvendo 
conjuntos. Dado um conjunto arbitrário S, 
podemos definir algumas operações no 
conjunto P (S) . Nesse caso o conjunto S 
é denominado Conjunto Universo ou 
Universo de Discurso. Esse conjunto 
define o contexto das operações.
• Se S=Z, então todos seus subconjuntos 
conterão apenas números inteiros. 
União entre Conjuntos
• Seja A, B P (S). A união de A e B, 
representada por , é definida por:
• Ex.:
A={1,2,3}
B={2,4,6}
BA
} |{ BxouAxxBA 
}6,4,3,2,1{BA

União entre Conjuntos
• Representação por diagrama de Euler-
Venn:
Intersecção entre Conjuntos
• Seja A, B P (S). A intersecção de A e B, 
representada por , é definida por:
• Ex.:
A={1,2,3}
B={2,4,6}
BA
} |{ BxeAxxBA 
}2{BA

Intersecção entre Conjuntos
• Representação por diagrama de Euler-
Venn:
U 
Complemento de um Conjunto
• Para um conjunto A P (S), o 
complemento de A, denotado A’ é definido 
por:
• Ex.: Considere o seguinte conjunto 
universo S={1,2,3,4,5,6,7,8,9,10} e o 
conjunto A={1,3,5,7,9}. 
• Então: A’={2,4,6,8,10}

} e |{' AxSxxA 
Complemento de um Conjunto
• Representação pordiagrama de Euler-
Venn:
A’ não engloba A
S
A
Diferença entre Conjuntos
• Sejam os conjuntos A e B. A diferença 
entre A e B, denotada por A-B pode ser 
definida como:
• Ex.: 
A={1,2,3,4,5}
B={1,2,3}
A-B={4,5}
'
ou }' e |{
ou } e |{
BABA
BxAxxBA
BxAxxBA



Diferença entre Conjuntos
• Representação por diagrama de Euler-
Venn:
S
Conjuntos disjuntos
• Dois conjuntos A e B tais que são 
ditos disjuntos.
BA
S
A B
Propriedades
• Dados 3 conjuntos A, B e C, valem as 
seguintes propriedades:
)()( 
)()( .5
 .4
)()()( 
)()()( .3
)()( 
)()( .2
 
 .1
CBCABA
CBCABA
ABABBABA
CABACBA
CABACBA
CBACBA
CBACBA
ABBA
ABBA









Leis de De Morgan
• Dados A e B partes de um conjunto 
universo U:
'')'(
'')'(
BABA
BABA


Exercícios
1. Sejam A={1,3,5,7,9} e B={3,5,6,10,11}.
Obtenha 
2. Sejam
A={1,2,3,5,10}
B={2,4,7,8,9}
C={5,8,10}
subconjuntos de S={1,2,3,4,5,6,7,8,9,10}
Encontre:
BABA  e 
)(' .
 .
 .
CABc
CAb
BAa



Relação de Inclusão e 
Implicação Lógica
• A relação é chamada de Relação de 
Inclusão e admite dois casos particulares: 
• O segundo caso pode ser demonstrado por 
absurdo: Se admitíssemos que , 
teríamos um elemento x tal que e 
. Mas é impossível, logo:
BA
AAA  e 
A
x
Ax x
A
Inclusão e Lógica
• A inclusão admite as seguintes propriedades:
• A propriedade transitiva é fundamental nas 
deduções lógicas. Ela é conhecida pelo nome 
de Silogismo.
a)(transitiv então , e Se 3.
simétrica)-(anti então , e Se 2.
)(reflexiva .1
CACBBA
BAABBA
AA



Exemplo de Silogismo
• Seja P: conjunto de paulistas
• Seja B: conjunto de brasileiros
• Seja S: conjunto de sul-americanos
Todo paulista é brasileiro.
Todo brasileiro é sul-americano.
Então, todo paulista é sul-americano.
S
B P
SPSBBP  então , e Se
Implicação Lógica
• Considere um conjunto A como parte de U
cujos elementos possuam uma propriedade 
p (classe), e B outro conjunto como parte de 
U e que seus elementos possuam outra 
propriedade q (outra classe).
• Quando dizemos (p implica q ou p 
acarreta q) estamos dizendo: 
• Que também pode ser lida como:
• Se p, então q
• p é condição suficiente para q
• q é condição necessária para p
qp
BA
Exemplos de Implicação
• No universo dos números naturais, vamos 
considerar as seguintes propriedades:
• p: n é um número natural que termina em 3.
• q: n é um número natural ímpar.
– Então A={3,13,23,33,...},
B={1,3,5,7,...}
e ou .
(terminar em 3 é condição suficiente para
ser ímpar e ser ímpar é condição neces-
sária para terminar em 3.)
qp BA
Exemplos de Implicação
• Consideremos, no universo dos quadriláteros, as 
propriedades:
• p: ser quadrilátero com quatro lados de mesma 
medida.
• q: ser quadrilátero com lados opostos paralelos.
• Neste caso, A é o conjunto dos losangos e B é o conjunto 
dos paralelogramos (duas classes) e, portanto . 
Logo, , ou seja, ser losango implica ser 
paralelogramo, ou ser losango é condição suficiente para 
ser paralelogramo ou ser paralelogramo é condição
necessária para ser losango ou se um quadrilátero
é um losango, ele também é um paralelogramo.
BA
qp
Exemplos de Implicação
Recíproca de Uma Implicação
• Dada uma implicação , chamamos de sua Recíproca
a implicação . Observe que nem sempre a recíproca 
de uma implicação é verdadeira.
• No exemplo anterior, vimos que todo losango é um 
paralelogramo ( é verdadeira), mas sua recíproca
é falsa, pois nem todo paralelogramo é um losango.
• Assim:
• Lemos: p é equivalente a q ou p se e somente se q
ou p é condição necessária e suficiente para q.
qp
pq
qp
pq
. 
, 
 
qpescrevemos
verdadeirafortambémpqe
verdadeiraforqpSe



Exemplo:
• p: a propriedade de um número natural x ser igual a 2 
(x=2).
• q: a propriedade de o dobro de um número natural x ser 
igual a 4 (2x=4).
• , pois se x=2, multiplicamos os dois membros da 
igualdade por 2 e obtemos q (2x=4).
• , pois se 2x=4, dividimos ambos os membros da 
igualdade por 2 e obtemos p (x=2).
• Assim, são verdadeiras,
logo e podemos escrever:
qp
pq
pqqp  e 
qp
422  xx
Operadores Lógicos
• Consideremos apenas os conjuntos Universo (U) e vazio .
• Em computação, esses conjuntos passam a representar os dois 
estados possíveis de um circuito elétrico: Ligado e Desligado.
• O estado ligado (U) pode ser representado por VERDADEIRO, V
ou simplesmente pelo algarismo 1.
• O estado desligado ( ) pode ser representado por FALSO,
F ou pelo algarismo 0.


Operador OU
• Vamos agora calcular os possíveis resultados de uniões entre os 
conjuntos Universo e Vazio:
• O Conjunto Solução S é igual ao Universo U quando o Conjunto
A ou o Conjunto B forem iguais ao Universo.
• Podemos então associar à operação de conjuntos UNIÃO,
o conectivo lógico OU.
UUU
UU
UU








Tabela
A B S
? ? ?
? U U
U ? U
U U U
Tabela-Verdade
• É uma tabela que exibe os resultados de um operador, usando F
para o conjunto Vazio e V para o conjunto Universo.
• Para o operador OU podemos escrever:
• Outra forma é usando os dígitos 0 para Falso e 1 para Verdadeiro:
A B S
F F F
F V V
V F V
V V V
A B S
0 0 0
0 1 1
1 0 1
1 1 1
Operador E
• Vamos agora calcular os possíveis resultados de intersecções entre 
os conjuntos Universo e Vazio:
• O Conjunto Solução S é igual ao Universo apenas quando o
Conjunto A e o Conjunto B forem iguais ao Universo
• Podemos então associar à operação de conjuntos 
INTERSECÇÃO o conectivo E.
Tabela
A B S
? ? ?
? U ?
U ? ?
U U U
UUU
U
U








Tabela-Verdade
• Para o operador E podemos escrever:
• Outra forma é usando os dígitos 0 para Falso e 1 para Verdadeiro:
A B S
F F F
F V F
V F F
V V V
A B S
0 0 0
0 1 0
1 0 0
1 1 1
Significado
Lógica
• Pode-se também representar o operador OU por e é chamada 
de DISJUNÇÃO. O operador E pode ser representado por e é 
chamado de CONJUNÇÃO. 
• Monte as tabelas-verdade:
DISJUNÇÃO CONJUÇÃO


A B S
F F
F V
V F
V V
A B S
F F
F V
V F
V V
SE... ENTÃO
• Um conjunto A será denominado SENTENÇA e pode assumir os 
valores F (Vazio) e V (Universo). Ex.:
– Dez é menor que sete (sentença FALSA)
– Existem formas de vida em outros planetas do universo (sentença FALSA ou 
VERDADEIRA, embora não saibamos responder...)
• Não são SENTENÇAS:
– Como vai você? (não pode ser considerada nem VERDADEIRA, nem FALSA).
– Ela é muito talentosa. (como ela não foi especificada, a frase não pode ser 
considerada nem VERDADEIRA nem FALSA).
• As sentenças podem ser combinadas na forma “se sentença 1, 
então sentença 2” ou “se A então B” ou “A implica B” ou
simplesmente A→B (implicação já vista).
• Na expressão A→B, A é a sentença antecedente e B a sem-
tença consequente.
SE... ENTÃO
• A sentença “Fogo é uma condição necessária para fumaça” pode 
ser reescrita como “Se há fumaça então há fogo”. O antecedente é 
“há fumaça” eo consequente é “há fogo”.
• Exercício: Indique o antecedente e o consequente em cada uma 
das seguintes sentenças. (Dica: reescreva as frases na forma “se... 
então”.)
– a) Se a chuva continuar, o rio vai transbordar.
– b) Uma condição suficiente para a falha de uma rede é que a chave geral pare 
de funcionar.
– c) Os abacates só estão maduros quando estão escuros e macios.
– d) Uma boa dieta é uma condição necessária para um gato saudável.
Respostas: a) A: A chuva continua – C: O rio vai transbordar.
b) A: A chave geral parar de funcionar – C: A falha de uma rede
c) A: Os abacates estarem maduros – C: Eles estarem escuros e macios
d) A: Um gato saudável – C: Uma boa dieta
Tabela-Verdade da Implicação
• “Se eu me formar nesta primavera, vou tirar férias na Flórida.”
• Ou: “Se A então B” onde A=“Se eu me formar nesta primavera” e B=“vou 
tirar férias na Florida”.
• Se A e B forem verdadeiras, então A→B também é verdadeira.
• Se A for verdadeira (significado?) e B for falsa (significado?) então A→B é 
falsa.
• Se A for falsa (significado?), A→B não pode ser considerada falsa
independente de B ser falsa ou verdadeira (por quê?) e nesse caso, por 
convenção, aceita-se A→B como VERDADEIRA. 
A B A→B B→A (A→B) (B→A)
F F
F V
V F
V V

Tabela-Verdade (Resposta)
• “Se A então B” onde A=“Se eu me formar nesta primavera” e B=“vou 
tirar férias na Florida”.
• Se A→B for V, B pode ser V ou F. Assim, o fato de A ser V implicar 
que B também seja V, B sendo V não implica que A seja V.
• A expressão (A→B) (B→A) significa EQUIVALÊNCIA e é
denotada pelo símbolo ↔ e é lida como “se e somente se”.
A B A→B B→A (A→B) (B→A)
F F V V V
F V V F F
V F F V F
V V V V V

B (tirar férias) não precisa ter ligação com A (se formar)

Negação
• Se A=“Vai chover amanhã”, a sentença A’=“Não é verdade que vai 
chover amanhã” ou simplesmente “Não vai chover amanhã” é 
denominada NEGATIVA ou NEGAÇÃO de uma sentença e 
costuma ser representada por A’.
• A negação de uma sentença composta é mais complicada, mas os 
Teoremas de De Morgan podem auxiliar.
• Exercício: Qual das frases a seguir representa A’ se A=“Julie adora 
manteiga mas detesta nata”?
– a) Julie detesta manteiga e nata.
– b) Julie não gosta de manteiga ou nata.
– c) Julie não gosta de manteiga mas adora nata.
– d) Julie detesta manteiga ou adora nata.
Resposta: d
Exercícios
• Construa as tabelas-verdade para as 
seguintes expressões:
– a) (A→B)↔(B→A)
– b) (A A’)→(B B’)
– c) [(A B’)→C’]’
– d) (A→B)↔(B’→A’)
 

Respostas
A B A→B B→A (A→B)↔(B→A)
V V V V V
V F F V F
F V V F F
F F V V V
A B A’ B’ A A’ B B’ (A A’)→(B B’)
V V F F V F F
V F F V V F F
F V V F V F F
F F V V V F F
a)
b)
 
Respostas
A B C B’ A B’ C’ [(A B’)→C’] [(A B’)→C’]’
V V V F F F V F
V V F F F V V F
V F V V V F F V
V F F V V V V F
F V V F F F V F
F V F F F V V F
F F V V F F V F
F F F V F V V F
c)
  
Respostas
A B A’ B’ A→B B’→A’ (A→B)↔(B’→A’)
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
c)
Dica para montagem da implicação:
•Se 1º termo for F, a implicação é sempre V
•Se 1º termo for V, a implicação depende do 2º termo
Dica para montagem da equivalência:
•Se os dois termos forem iguais, a equivalência vale V
•Se os dois termos forem diferentes, a equivalência vale F
Tautologia e Contradição
• TAUTOLOGIA são expressões cujo resultado é sempre 
VERDADEIRO.
• CONTRADIÇÃO são expressões cujo resultado é sempre FALSO.
• Algumas equivalências Tautológicas:
tativas)(complemen 0' 5b. 1' 5a.
e)(identidat 1 4b. 0 4a.
iva)(distribut )()()( 3b. )()()( 3a.
va)(associati )()( 2b. )()( a.2
a)(comutativ 1b. .a1





AAAA
AAAA
CABACBACABACBA
CBACBACBACBA
ABBAABBA
Exercícios
• Construa a tabela-verdade para as 
seguintes expressões, identificando as 
Tautologias:
– a)(A→B)↔A’ B
– b) (A B) C→A (B C)
– c) A A’
– d) A B→B




  
Respostas
A B A→B A’ A’ B (A→B)↔A’ B
V V V F V V
V F F F F V
F V V V V V
F F V V V V
a)


 
A B C A B (A B) C B C A (B C) (A B) C→A (B C)
V V V V V V V V
V V F V V V V V
V F V F V V V V
V F F F F F F V
F V V F V V F F
F V F F F V F V
F F V F V V F F
F F F F F F F V

 
 

 


b)
Respostas
A A’ A A ‘
V F V
F V V

c)
A B A B A B→B
V V V V
V F F V
F V F V
F F F V
 
d)
Bibliografia
• Gersting, Judith L.. Fundamentos 
Matemáticos para a Ciência da 
Computação. 3ª Ed. Ed. LTC.
• Dante, Luiz Roberto. Matemática Volume 
Único. Ed. Ática