Aula 04-10

Prévia do material em texto

Teoria da Computação
Introdução, noções e terminologia
Alysson Oliveira
UERN/FANAT/DI
 
Conteúdos
● Conjuntos – OK
● Sequências e Uplas
● Funções e Relações
 
Sequências e Uplas
● Uma sequência de objetos é uma lista desses 
objetos na mesma ordem. 
– Geralmente designamos uma sequência escrevendo 
a lista entre parênteses:
● Ex.: (7,21,57)
● Em um conjunto a ordem não importa, mas em 
sequência, sim. 
– Daí que:
● (7,21,57) ≠ (7, 57, 21)
 
Sequências e Uplas
● Assim como os conjuntos, sequências podem 
ser finitas ou infinitas.
– Sequências finitas, frequentemente são chamadas 
de uplas. 
– Uma sequência com k elementos é uma k-upla. 
Dessa forma, (7,21,57) é uma 3-upla. Uma 2-upla é 
também chamada de par.
 
Sequências e Uplas
● Conjuntos e sequências podem aparecer como 
elementos de outros conjuntos e sequências.
– O conjunto das partes de A é o conjunto de todos os 
subconjuntos de A.
– Se A for o conjunto {0,1}, o conjunto das partes de A é 
o subconjunto:
● { Ø , {0}, {1}, {0,1}} 
– O Conjunto de todos is pares cujos elementos são 0s e 
1s é:
● { (0,0), (0,1), (1,0), (1,1) }
 
Sequências e Uplas
● Se A e B são dois conjuntos, o produto 
cartesiano, ou produto cruzado de A e B, 
descrito como A x B, é: 
– O conjunto de todos os pares nos quais o primeiro 
elemento é um membro de A e o segundo é um 
membro de B.
– O conjunto N2 é igual a NxN. Ele consiste de todos os 
pares de números naturais. Também podemos 
escrevê-lo como:
● N2 = { (i, j) | i, j ≥ 1}
 
Funções e relações
● Uma função é um objeto que estabelece um 
relacionamento de entrada-saída.
● Em toda função, a mesma entrada produz a 
mesma saída.
● Se f é uma função, b é sua saída e a é sua 
entrada, então podemos escrever:
– f(a) = b
● Uma função é também chamada 
mapeamento, e assim dizemos que f mapeia a 
para b.
 
Funções e relações
● O conjunto de entradas possíveis para uma 
função é chamado domínio.
● As saídas de uma função vêm de um conjunto 
denominado contradomínio da função.
● Podemos escrever uma função e termos dos 
conjuntos de mapeamento:
– f: D → C
● Exemplos de funções
 
Funções e relações
● Funções representadas como tabelas de 
mapeamento
● F: { 0, 1, 2, 3, 4 } → { 0, 1, 2, 3, 4 }
 n f(n)
 0 1
 1 2
 2 3
 3 4
 4 0
 
Funções e relações
● Quando o domínio de uma função f é A1 x ... x 
Ak para alguns conjuntos A1, … Ak, a entrada 
para f é uma k-upla (a1, …, ak) e chamamos os 
ai argumentos para f.
● Uma função com k argumentos é denominada 
função k-ária e k é chamada aridade da 
função.
● Se k=1, a função tem um único argumento é 
chamada função unária
 
Funções e relações
● Algumas funções binárias conhecidas são escritas 
em uma notação infixa, com o símbolo para a 
função colocado entre os seus dois argumentos, 
em vez da notação préfixa.
– A função adição adi geralmente é escrita em notação 
infixa com o símbolo + entre seus dois argumentos, 
como a+b, ao invés de adi(a,b)
● Predicado ou propriedade é uma função cujo 
contradomínio é { VERDADEIRO, FALSO }. 
● Uma propriedade cujo domínio é um conjunto de k-
uplas A x … x A é chamada relação, relação k-ária 
ou relação k-ária sobre A
 
Funções e relações
● Um tipo especial de relação binária, 
chamada relação de equivalência, captura a 
noção de dois objetos serem iguais com 
respeito a alguma característica.
● Uma relação binária R é uma relação se 
satisfizer três condições:
– R é reflexiva, se para todo x, xRx;
– R é simétrica, se para todo x e y, xRy implica yRx
– R é transitiva, se para todo x, y e z, xRy e yRz 
implica xRz.
 
Exercícios
● Faça a tabela de mapeamento do jogo 
Tesoura-Papel-Pedra
 
Exercícios
● Se A tem a elementos e B tem b elementos, 
quantos elementos estão em AxB? Explique 
sua resposta
 
Exercícios
● Se C é um conjunto com c elementos, quantos 
elementos estão no conjunto de partes de C. 
Explique sua resposta
 
● Seja X o conjunto {1,2,3,4,5} e Y o conjunto 
{6,7,8,9,10}. A função unária f:X → Y e a função 
binária g: X x Y → Y são descritas nas tabelas 
seguintes:
, n f(n) g 6 7 8 9 10
 1 6 1 10 10 10 10 10
 2 7 2 7 8 9 10 6
 3 6 3 7 7 8 8 9
 4 9 4 9 8 7 6 10
 5 6 5 6 6 6 6 6
 
 
● Qual é o valor de f(2)?
● Quais são o domínio e o contradomínio de f?
● Qual é o valor de g(2,10)?
● Quais são o domínio e o contradomínio de g?
● Qual é o valor de g( 4, f(4))?