Upload
truonghanh
View
221
Download
1
Embed Size (px)
Citation preview
Programa Combinatória Aritmética Racional
MATEMÁTICA DISCRETA
Patrícia Ribeiro
Departamento de Matemática, ESTSetúbal
2018/2019
1 / 52
Programa Combinatória Aritmética Racional
Programa
1 Combinatória2 Aritmética Racional3 Grafos
2 / 52
Programa Combinatória Aritmética Racional
Capítulo 1
Combinatória
3 / 52
Programa Combinatória Aritmética Racional
Princípio da Adição
TeoremaSe A e B são conjuntos finitos e disjuntos, então o número de maneirasdistintas de escolher um elemento de A ou um elemento de B é igual a
|A∪B|= |A|+ |B|.
TeoremaSe A1,A2, ...,An são conjuntos finitos e disjuntos dois a dois, então onúmero de maneiras distintas de escolher um elemento de A1 ou umelemento de A2 ... ou de An é igual a
|A1∪A2∪ ...∪An|= |A1|+ |A2|+ ...+ |An|.
4 / 52
Programa Combinatória Aritmética Racional
Princípio da Adição
TeoremaSe A e B são conjuntos finitos e disjuntos, então o número de maneirasdistintas de escolher um elemento de A ou um elemento de B é igual a
|A∪B|= |A|+ |B|.
TeoremaSe A1,A2, ...,An são conjuntos finitos e disjuntos dois a dois, então onúmero de maneiras distintas de escolher um elemento de A1 ou umelemento de A2 ... ou de An é igual a
|A1∪A2∪ ...∪An|= |A1|+ |A2|+ ...+ |An|.
4 / 52
Programa Combinatória Aritmética Racional
Princípio do Produto
TeoremaSejam A e B conjuntos finitos. Suponhamos que se pretende realizaruma escolha múltipla de dois elementos que consiste na escolha deexatamente um elemento em cada um dos conjuntos. Admitindo queestas escolhas se combinam livremente (isto é, cada escolha múltiplacorresponde a um elemento de A×B e vice-versa), então o númerototal de diferentes escolhas múltiplas possíveis é igual a
|A×B|= |A|× |B|.
5 / 52
Programa Combinatória Aritmética Racional
Princípio do Produto
TeoremaSejam A1,A2, ...,An conjuntos finitos. Suponhamos que se pretenderealizar uma escolha múltipla de n elementos que consiste na escolhade exatamente um elemento em cada um dos conjuntos. Admitindoque estas escolhas se combinam livremente (isto é, cada escolhamúltipla corresponde a um elemento de A1× ...×An e vice-versa),então o número total de diferentes escolhas múltiplas possíveis éigual a
|A1× ...×An|= |A1|× ...×|An|.
6 / 52
Programa Combinatória Aritmética Racional
Arranjos completos
DefiniçãoSeja A um conjunto com n elementos. Chamamos arranjo completo(ou com repetição) dos n elementos de A tomados k a k, a todo oelemento (a1,a2, ...,ak) do produto cartesiano Ak.
O número total de arranjos completos de n elementos tomados k a krepresenta-se por An
k .
TeoremaO número total de arranjos completos de n elementos tomados k a k édado por
Ank = nk.
7 / 52
Programa Combinatória Aritmética Racional
Arranjos completos
DefiniçãoSeja A um conjunto com n elementos. Chamamos arranjo completo(ou com repetição) dos n elementos de A tomados k a k, a todo oelemento (a1,a2, ...,ak) do produto cartesiano Ak.
O número total de arranjos completos de n elementos tomados k a krepresenta-se por An
k .
TeoremaO número total de arranjos completos de n elementos tomados k a k édado por
Ank = nk.
7 / 52
Programa Combinatória Aritmética Racional
Arranjos simples
DefiniçãoChamamos arranjo simples (ou sem repetição ou simplesmentearranjo) dos n elementos de A tomados k a k, a todo o elemento(a1,a2, ...,ak) do produto cartesiano Ak, em que a1,a2, ...,ak sãotodos distintos entre si.
O número total de arranjos de n elementos tomados k a krepresenta-se por An
k .
TeoremaO número total de arranjos simples de n elementos tomados k a k édado por
Ank = n(n−1)(n−2)...(n− k+1).
8 / 52
Programa Combinatória Aritmética Racional
Arranjos simples
DefiniçãoChamamos arranjo simples (ou sem repetição ou simplesmentearranjo) dos n elementos de A tomados k a k, a todo o elemento(a1,a2, ...,ak) do produto cartesiano Ak, em que a1,a2, ...,ak sãotodos distintos entre si.
O número total de arranjos de n elementos tomados k a krepresenta-se por An
k .
TeoremaO número total de arranjos simples de n elementos tomados k a k édado por
Ank = n(n−1)(n−2)...(n− k+1).
8 / 52
Programa Combinatória Aritmética Racional
Permutações
DefiniçãoChamamos permutação dos n elementos de um conjunto A, a todo oarranjo simples dos n elementos de A tomados n a n.O número total de permutações de n elementos designa-se por Pn e éigual a
Pn = Ann = n× (n−1)× ...×2×1 = n!.
9 / 52
Programa Combinatória Aritmética Racional
Permutações
ProposiçãoDado 0 < k ≤ n, o número de arranjos simples de n elementostomados k a k é dado por
Ank =
n!(n− k)!
.
10 / 52
Programa Combinatória Aritmética Racional
Permutações com repetição
DefiniçãoSeja A um conjunto com k elementos, A = {a1,a2, ...,ak}. Chama-sepermutação-n com repetição dos k elementos de A, em que a1 serepete n1 vezes, a2 se repete n2 vezes,..., ak se repete nk vezes e em quen1 +n2 + ...+nk = n, a todo o n-uplo do produto cartesiano An comn1 componentes iguais a a1, n2 componentes iguais a a2,..., nk
componentes iguais a ak.
O número total de permutações-n representa-se por P(n1,n2, ...,nk).
11 / 52
Programa Combinatória Aritmética Racional
Permutações com repetição
TeoremaO número total de permutações-n com repetição dos k elementos deA, em que a1 se repete n1 vezes, a2 se repete n2 vezes,..., ak se repetenk vezes e em que n1 +n2 + ...+nk = n, é igual a
P(n1,n2, ...,nk) =n!
n1!×n2!× ...×nk!.
12 / 52
Programa Combinatória Aritmética Racional
Combinações
DefiniçãoSeja A um conjunto com n elementos e k um inteiro, tal que 0≤ k ≤ n.Chama-se combinação sem repetição (ou simplesmente combinação)dos n elementos tomados k a k, a qualquer subconjunto de A com kelementos.
O número total de combinações dos n elementos tomados k a krepresenta-se por
(nk
)ou por Cn
k .
13 / 52
Programa Combinatória Aritmética Racional
Combinações
ProposiçãoPara todo o n ∈ N tem-se que(
n0
)=
(nn
)= 1,
(n1
)=
(n
n−1
)= n e
(nk
)= 0,k > n.
14 / 52
Programa Combinatória Aritmética Racional
Combinações
ProposiçãoPara n,k ∈ N0, tal que 0≤ k ≤ n, tem-se que(
nk
)=
(n
n− k
).
15 / 52
Programa Combinatória Aritmética Racional
Combinações
TeoremaPara n ∈ N e 0≤ k ≤ n temos que
(nk
)=
1 se k = 0 ou k = n(n−1
k−1
)+(n−1
k
)se 0 < k < n
16 / 52
Programa Combinatória Aritmética Racional
Combinações
TeoremaPara n ∈ N e 0≤ k ≤ n temos que(
nk
)=
n!k!(n− k)!
.
17 / 52
Programa Combinatória Aritmética Racional
Combinações com repetição
DefiniçãoSeja A um conjunto com n elementos e k > 0 um inteiro qualquer.Chama-se combinação com repetição dos n elementos tomados k a ka toda a amostra não ordenada de k elementos de A distintos ou não.
Representa-se por C nk o número total de combinações com repetição
dos n elementos tomados k a k.
TeoremaPara n ∈ N e k > 0 qualquer, temos que
C nk = P(k,n−1) =
(k+n−1
k
),
18 / 52
Programa Combinatória Aritmética Racional
Combinações com repetição
DefiniçãoSeja A um conjunto com n elementos e k > 0 um inteiro qualquer.Chama-se combinação com repetição dos n elementos tomados k a ka toda a amostra não ordenada de k elementos de A distintos ou não.
Representa-se por C nk o número total de combinações com repetição
dos n elementos tomados k a k.
TeoremaPara n ∈ N e k > 0 qualquer, temos que
C nk = P(k,n−1) =
(k+n−1
k
),
18 / 52
Programa Combinatória Aritmética Racional
Teorema binomial
TeoremaDados a,b ∈ R e n ∈ N qualquer, temos que
(a+b)n =n
∑k=0
(nk
)akbn−k.
19 / 52
Programa Combinatória Aritmética Racional
Princípio da inclusão-exclusão
Sejam A e B conjuntos finitos. Então,
|A∪B|= |A|+ |B|− |A∩B|.
20 / 52
Programa Combinatória Aritmética Racional
Princípio da inclusão-exclusão
TeoremaSeja X um conjunto e A1,A2, ...,An ⊆ X não necessariamentedistintos. Então,
|A1∪ ...∪An|=n
∑i=1|Ai|−
n
∑1≤i<j≤n
|Ai∩Aj|+
n
∑1≤i<j<k≤n
|Ai∩Aj∩Ak|+ ...+(−1)n+1|A1∩ ...∩An|.
21 / 52
Programa Combinatória Aritmética Racional
Princípio da inclusão-exclusão
CorolárioSeja X um conjunto e A1, ...,An ⊆ X não necessariamente distintos.Então,
|X \ (A1∪ ...∪An) |= |X|− |A1∪ ...∪An|.
22 / 52
Programa Combinatória Aritmética Racional
Princípio da distribuição
Forma fraca:Sejam m,n ∈ N. Se m≥ n+1 objetos são distribuídos por n caixas,então uma das caixas terá, pelo menos, dois objetos.
Forma forte:Sejam m,n,k ∈ N. Se m≥ nk+1 objetos são distribuídos por ncaixas, então uma das caixas terá, pelo menos, k+1 objetos.
23 / 52
Programa Combinatória Aritmética Racional
Capítulo 2
Aritmética Racional
24 / 52
Programa Combinatória Aritmética Racional
Axiomática dos Inteiros
Sejam a e b inteiros. Designaremos por a+b a sua soma e a×b (ouab) a sua multiplicação. Admitem-se válidos os seguintes axiomas:
I1. a+b e ab pertencem a Z;
I2. a+b = b+a e ab = ba;
I3. (a+b)+ c = a+(b+ c) e (ab)c = a(bc);
I4. a+0 = a e a×1 = a;
I5. a(b+ c) = ab+ac;
I6. Para cada a ∈ Z existe um único inteiro representado por −a, talque a+(−a) = 0;
I7. Se a 6= 0 e ab = ac, então b = c.
25 / 52
Programa Combinatória Aritmética Racional
Axiomática dos Inteiros
ProposiçãoSão válidas as seguintes propriedades:
1 O elemento neutro da adição em Z é único;2 Sendo a,b,c ∈ Z é válida a lei do corte para a adição, ou seja se
a+b = a+ c, então b = c;3 Se a ∈ Z,a×0 = 0;4 Sendo a,b ∈ Z é válida a lei do anumlamento do produto, ou
seja ab = 0 sse a = 0 ou b = 0.
26 / 52
Programa Combinatória Aritmética Racional
Axiomática dos Inteiros
DefiniçãoA subtração de inteiros representa-se por a−b e define-se como sesegue:
a−b = a+(−b).
27 / 52
Programa Combinatória Aritmética Racional
Axiomática dos Inteiros
Suponha-se que existe uma relação de ordem nos inteirosrepresentado pelo símbolo ≤. Sejam a,b e c inteiros. Admitem-seválidos os seguintes axiomas:
I8. a≤ a;
I9. Se a≤ b e b≤ a, então a = b;
I10. a≤ b e b≤ c, então a≤ c;
I11. a≤ b⇒ a+ c≤ b+ c;
I12. a≤ b e 0≤ c, então ac≤ bc.
ObservaçãoDe referir que se pode definir as relações ≥,< e >: a≥ b sse b≤ a;a < b sse a≤ b e a 6= b; a > b sse b≤ a e a 6= b.
28 / 52
Programa Combinatória Aritmética Racional
Axiomática dos Inteiros
DefiniçãoSeja X um subconjunto de Z. Diz-se que l é um minorante de X se
l≤ x,∀x ∈ X.
Se l ∈ X diz-se que l é mínimo de X.
I13. (Princípio da boa ordenação de Z) Se X é um subconjunto nãovazio de Z com um minorante, então X tem mínimo.
Princípio da boa ordenação de N: Se X é um subconjunto não vaziode N ou N0, então X tem mínimo.
29 / 52
Programa Combinatória Aritmética Racional
Princípio de Indução
TeoremaSeja P(n) uma afirmação na variável n ∈ N que satisfaz as seguintescondições:
i) Base de indução: P(1) é verdadeira;
ii) Passo de indução: para qualquer k ∈ N se P(k) é verdadeira,então P(k+1) é verdadeira.
Então P(n) é verdadeira para todo o n ∈ N.
30 / 52
Programa Combinatória Aritmética Racional
Princípio de Indução (1a variante)
TeoremaSeja a ∈ N e P(n) uma afirmação na variável n ∈ N com n≥ a quesatisfaz as seguintes condições:
i) Base de indução: P(a) é verdadeira;
ii) Passo de indução: para qualquer k ≥ a se P(k) é verdadeira,então P(k+1) é verdadeira.
Então P(n) é verdadeira para todo o n≥ a.
31 / 52
Programa Combinatória Aritmética Racional
Princípio de Indução completa
TeoremaSejam a,r ∈ N e P(n) uma afirmação na variável n ∈ N com n≥ aque satisfaz as seguintes condições:
i) Base de indução: P(a),P(a+1), ...,P(a+ r) são verdadeiras;
ii) Passo de indução: para qualquer k ≥ a+ r seP(a),P(a+1), ...,P(a+ r), ...,P(k) são verdadeiras, entãoP(k+1) é verdadeira.
Então P(n) é verdadeira para todo o n≥ a.
32 / 52
Programa Combinatória Aritmética Racional
Divisão Inteira
TeoremaDados a,b ∈ Z, existem inteiros q e r, tais que
a = bq+ r, 0≤ r < |b|,
onde q e r têm respetivamente o nome de quociente e resto da divisãode a por b. Além disso, q e r são únicos.
33 / 52
Programa Combinatória Aritmética Racional
Representação de números em diferentes basesSeja b≥ 2 um inteiro. Dado a ∈ N, se utilizarmos repetidamente oteorema anterior concluímos que
a = bq0 + r0
q0 = bq1 + r1
...
qn−2 = bqn−1 + rn−1
qn−1 = bqn + rn.
Se eliminarmos por retrosubstituição os quocientes qi conseguimosrepresentar a da seguinte maneira:
a = rnbn + rn−1bn−1 + ...+ r1b+ r0,
que usualmente se representa por
a = (rnrn−1...r1r0)b.
34 / 52
Programa Combinatória Aritmética Racional
Divisibilidade
DefiniçãoDados inteiros a e b, diz-se que a é divisor de b se b = aq para algumq ∈ Z.Denota-se por a|b. Quando a não divide b utiliza-se a notação a - b.
35 / 52
Programa Combinatória Aritmética Racional
DivisibilidadeProposiçãoSejam a,b,c,d ∈ Z. Então:
1 ±a|a, e 1|a;2 a|b sse (−a)|b sse a|(−b);3 se c 6= 0, então a|b sse ac|bc;4 se a|b, então a|bc;5 se ab|c, então a|c e b|c;6 se a|b e b|c, então a|c;7 se a|b e c|d, então ac|bd;8 se a|b e a|c, então a|(bx+ cy), para quaisquer x,y ∈ Z;9 se a|b e b|a, então a =±b;
10 se a|1, então a =±1;11 se a,b ∈ N e a|b, então a≤ b;12 o número de divisores de um inteiro não nulo é finito. 36 / 52
Programa Combinatória Aritmética Racional
Máximo divisor comum
Um inteiro d é um divisor comum dos inteiros a e b se d|a e d|b.
DefiniçãoSejam a,b inteiros não ambos nulos. Ao maior dos divisores comunsde a e b dá-se o nome de máximo divisor comum de a e b.Representa-se por mdc(a,b).
37 / 52
Programa Combinatória Aritmética Racional
Máximo divisor comum
Lema (Algoritmo de Euclides)Se a = bq+ r, então mdc(a,b) = mdc(b,r).
38 / 52
Programa Combinatória Aritmética Racional
Máximo divisor comum
TeoremaSejam a e b inteiros não ambos nulos e d = mdc(a,b). Então, existeminteiros x e y, tais que
d = ax+by.
39 / 52
Programa Combinatória Aritmética Racional
Máximo divisor comum
TeoremaSejam a e b inteiros não ambos nulos. Então d = mdc(a,b) sse
i) d > 0;
ii) d|a e d|b;
iii) se c|a e c|b, então c|b.
40 / 52
Programa Combinatória Aritmética Racional
Números primos entre si
DefiniçãoSejam a,b ∈ Z. Diz-se que a e b são primos entre si (ou primosrelativos) se mdc(a,b) = 1.
ProposiçãoDois inteiros a e b são primos entre si sse existem inteiros x e y, taisque
1 = ax+by.
41 / 52
Programa Combinatória Aritmética Racional
Números primos entre si
ProposiçãoSejam a,b,c ∈ Z. Se mdc(a,b) = 1, a|c e b|c, então ab|c.
Proposição (Lema de Euclides)Sejam a,b,c ∈ Z. Se a|bc e mdc(a,b) = 1, então a|c.
42 / 52
Programa Combinatória Aritmética Racional
Menor múltiplo comum
DefiniçãoSejam a e b inteiros não nulos. Ao menor dos múltiplos comuns de a eb dá-se o nome de menor múltiplo comum de a e b. Representa-se pormmc(a,b).
43 / 52
Programa Combinatória Aritmética Racional
Menor múltiplo comum
TeoremaSejam a e b inteiros não ambos nulos. Então m = mmc(a,b) sse:
1 m > 0;2 a|m e b|m;3 sendo c 6= 0, se a|c e b|c, então m|c.
44 / 52
Programa Combinatória Aritmética Racional
Relação entre mdc e mmc
TeoremaSe a e b são inteiros não nulos, então
mmc(a,b) =|ab|
mdc(a,b).
45 / 52
Programa Combinatória Aritmética Racional
Equação linear diofantina a 2 incógnitas
TeoremaSejam a,b,c ∈ Z,a,b 6= 0 e d = mdc(a,b).
1 a equação ax+by = c tem soluções inteiras sse d|c;2 suponhamos que d|c. Então, se (x0,y0) é uma solução inteira da
equação ax+by = c, qualquer outro par (x,y) é solução sse forda forma
x = x0 +bd t
y = y0− ad t, t ∈ Z.
46 / 52
Programa Combinatória Aritmética Racional
Números primos
DefiniçãoUm número natural maior do que 1 diz-se primo se não tem outrosdivisores positivos além dele próprio e do 1.Um número que não é primo diz-se composto.
47 / 52
Programa Combinatória Aritmética Racional
Números primos
TeoremaQualquer número natural maior do que 1 é produto de númerosprimos, isto é pode ser decomposto em fatores primos.
48 / 52
Programa Combinatória Aritmética Racional
Trial division
CorolárioSeja n > 1 um número natural. Se n não é primo, então existe umprimo p, tal que p|n e p≤
√n.
49 / 52
Programa Combinatória Aritmética Racional
Números primos
TeoremaExiste um número infinito de primos.
50 / 52
Programa Combinatória Aritmética Racional
Decomposição em fatores primos
TeoremaSejam a e b números inteiros e p um número primo. Se p divide ab,então p divide a ou p divide b.
CorolárioSe p é um número primo e x1,x2, ...,xn são inteiros, tais que
p|x1× x2× ...× xn,
então p|xi, para algum i = 1,2, ...,n.
51 / 52
Programa Combinatória Aritmética Racional
Decomposição em fatores primos
Teorema (Teorema fundamental da aritmética)A decomposição em fatores primos de um número maior do que 1 éúnica, a menos da ordem dos fatores.
52 / 52