TÉCNICAS DE CODIFICAÇÃO DE SINAIS

INTRODUÇÃO À ÁLGEBRA

Evelio M. G. Fernández - 2010

Sistema algébrico com uma operação e seu inverso.

conjunto de elementos e axiomas G1 à G4.

G1) Fechamento, GbaGba , .

G2) Associativa, cbacbaGcba ,, .

G3) Elemento identidade (neutro): 0 ou 1 (depende da operação).

Se operação = “soma”, aaaGa 00

Se operação = “produto”, aaaGa 11 .

G4) Inverso.

Se operação = “soma”,

0/ aaaaGaGa elemento neutro na adição

Se operação = “produto”,

1/ 11 aaaaGaGa elemento neutro na multiplicação

Grupo abeliano (conmutativo)

Para grupo sob adição (soma), abbaGba ,

Para grupo sob multiplicação (produto), abbaGba ,

Grupo (Group), G

Especifique se são grupos os seguintes conjuntos (operação soma e produto).

a) Conj. No reais

b) Conj. No reais exceto zero

c) Conj. No inteiros (positivos e zero)

d) Conj. No inteiros (negativos e zero)

e) Conj. No inteiros (neg., pos. e zero)

Exemplos e Contra-exemplos

Exemplos e Contra-exemplos

Verifique se é “grupo” a álgebra binária (Booleana) sob as seguintes

operações booleanas:

a) Operação “OR”

b) Operação “AND”

c) Operação “OR-EXCLUSIVO ou Módulo 2”

Exemplos e Contra-exemplos

Verifique se constituem grupos os seguintes conjuntos sob operação

soma módulo 2:

a) S1 = {0000, 1111}

b) S2 = {000, 011, 101, 110}

c) S3 = {000, 011, 101, 110, 111}

d) S4 = {000, 001, 100, 101}

Anel (Ring), RSistema algébrico com 2 operações e operação inversa da adição.

Conjunto de elementos e axiomas R1 a R4.

R1) R = Grupo abeliano sob adição ( inverso na adição).

R2) Fechamento, RbaRba ,

R3) Associativa, cabbcaRcba ,,

R4) Distributiva,

cabaacbacabcba

Anel comutativo (abeliano), baabRba ,

Propriedade de anel:

000, aaRba

abbaba

Exemplos e Contra-exemplos

Verifique se são anéis os seguintes conjuntos:

- {No reais}

- {inteiros}

- {Polinômios em uma variável com coeficientes inteiros}

Corpo (Field), F

Sistema algébrico com 2 operações e seus inversos.

Axiomas:

F1) Anel comutativo (A, +, .)

F2) Elemento identidade “1” para operação “.” (produto).

F3) Inverso multiplicativo,

1/;0, 11 aaaaAa

0 = elemento neutro na operação “+”.

1 = elemento neutro na operação “.”

Exemplos e Contra-exemplos

Verifique se são corpos os seguintes conjuntos:

a) {No reais}

b) {No inteiros}

c) S1 = {0, 1} e operações módulo 2

d) S2 = {0, 1, 2} e operações módulo 3

DEF: n-upla sobre F.

conjunto ordenado de elementos de F.

EX: niFaaaa in ,,2,1,,,, 21

DEF: Adição de n-uplas:

nnnn babababbbaaa ,,,,,,,,, 22112121

Adição sobre F

DEF: Multiplicação de uma escalar ( F) por uma n-upla:

nn acacacaaacFc ,,,,,, 2121

Produto sobre F

DEF: Multiplicação de n-uplas:

nnnn babababbbaaa ,,,,,,,,, 22112121

Produto sobre F

Operações com n-uplas

Um conjunto V de elementos é um espaço vetorial sobre um corpo F se satisfazer

axiomas V1-V5 (elemento de V: Vvvvv n ,,, 21 ).

V1) Grupo abeliano sob adição (elemento identidade na adição vetor todo zero 0).

V2) Fechamento:

VvcFcVv e (produto por um escalar).

V3) Distributiva 1:

vcucvucFcVvu escalar e ,

V4) Distributiva 2:

vdvcvdcFdcVv , e

V5) Associativa:

vdcvcdFdcVv , e .

Espaços Vetoriais

Álgebra Linear Associativa

Um conjunto A de elementos é uma álgebra linear associativa sobre um

corpo F se satisfazer axiomas A1 à A4:

A1) Espaço vetorial sobre F.

A2) AvuAvu ,

A3) Associativa,

wvuwvuAwvu ,,

A4) Bilinear,

wudvucwdvcuAwvuFdc ,, e,

OBS: uwduvcuwdvc

Subespaços Vetoriais

DEF: S subespaço de V.

Todo subconjunto de um espaço vetorial que satisfazer os axiomas de

espaço vetorial.

OBS: Para verificação de subespaço vetorial:

Verificar propriedades de fechamento na adição e na multiplicação

por escalar.

Subespaços Vetoriais: Exemplos

EX1: Seja V: conjunto das n-uplas sobre GF(2), n = 3.

S1 = {000, 010, 100} = subespaço de V?

S2 = {000, 010, 100, 110} = subespaço de V?

EX2: Seja V = {conjunto das n-uplas sobre GF(3), n = 2}

S1 = {02, 00} = sub V?

S2 = {02, 00, 01} = sub V?

Combinações Lineares de k Vetores

Sejam FavavavauVvvv ikkk 221121 ,,,

Teorema 2.5 (Peterson & Weldon, Cap. 2)

O conjunto S de todas as combinações lineares de um conjunto

{v1, v2, ..., vk} V é um subespaço de V, i.e., S V.

EXEMPLO: Seja V = {n-uplas, n = 3}

O conjunto de todas as combinações lineares de {010, 110} é

subespaço de V?

Combinações Lineares de k Vetores

Vetores linearmente dependentes (LD).

O conjunto Vvvv k ,,, 21 é LD kccc ,,, 21 nem todos

iguais a zero tal que 02211 kk vcvcvc .

Conjunto de vetores linearmente independentes (LI):

Todo conjunto de vetores que não for LD.

Gerador de um Espaço Vetorial

Um conjunto de vetores gera um espaço vetorial V se qualquer v V

é uma combinação linear dos vetores deste conjunto.

Teorema 2.6 (Peterson & Weldon).

Se um conjunto de m vetores, (v1, v2, ..., vm), gera o espaço vetorial V

e V contém um conjunto de k vetores LI, (u1, u2, ..., uk) então m k.

Teorema 2.7 (Peterson & Weldon).

Se dois conjuntos de vetores LI geram o mesmo espaço vetorial V,

eles possuem o mesmo número de vetores.

Dimensão de um Espaço Vetorial

Dim(V) = número de vetores LI que geram V. DEF: Base de um espaço vetorial V de dimensão k. É um conjunto de k vetores LI que geram V. Teorema 2.8 (Peterson & Weldon). Se Dim(V) = k qualquer conjunto de k vetores LI em V é uma base para V. EXEMPLOS 1) Liste 4 conjuntos de vetores LI que formam uma base para V3. 2) Liste 4 conjuntos de vetores LD que geram V3. 3) Liste todos os conjuntos de vetores que formam uma base para S1 = {000, 110, 010, 100}

Produto EscalarDEF: Produto escalar (ou interno) de dois vetores (n-uplas). Fcbabababbbaaa nnnn 22112121 ,,,,,, . Propriedades de o produto escalar: uvvu vwuwvuw DEF: Vetores ortogonais: vuvu 0 Teorema 2.13 (Peterson & Weldon). O conjunto de todas as n-uplas ortogonais a um subespaço S1 de n-uplas forma um subespaço S2 de n-uplas. S2 é chamado de espaço nulo de S1 (e vice-versa teorema 2.16). S1 ortogonal a S2: S1 S2 ou S2 ortogonal a S1: S2 S1. Teorema 2.14 (Peterson & Weldon). Se um vetor é ortogonal a todo vetor de um conjunto que gera S1, ele pertence ao espaço nulo de S1.

Matrizes

mnmm

n

n

aaa

aaaaaa

M

21

22221

11211

M = [aij], i = 1, 2, ..., m; j = 1, 2, ..., n Linha de M = n-upla ou vetor de n dígitos F, vetor linha. Coluna de M = m-upla ou vetor de m dígitos F, vetor coluna. DEF: Espaço das linhas de M: é o conjunto de todas as combinações lineares dos vetores linhas associados à M. OBS: É um subespaço vetorial do espaço vetorial das n-uplas sobre o corpo F de escalares. RANK (linhas) = Dim[espaço das linhas]. OBS: Idem para espaço das colunas.

Operações sobre as Linhas

Teorema 2.10 (P & W). Operações elementares sobre as linhas de M não alteram seu espaço das linhas. OBS: Operações elementares sobre as linhas:

- Permutação. - Multiplicação por um escalar c F, c 0. - Adição de um múltiplo de uma linha a uma outra.

OBS: Inverso de uma operação elementar é também uma operação linear da mesma espécie.

Forma Canônica Escalonada

DEF: Forma canônica escalonada (echelon canonical form). Características:

1) Líder de linha não zero é o elemento 1. 2) A coluna do líder tem todos os outros elementos iguais a 0. 3) O líder de uma linha está à direita do líder das linhas anteriores. 4) Todas as linhas que têm somente zeros estão abaixo das linhas

não zero. Propriedades das matrizes na forma canônica escalonada

- As linhas não zero são L.I. - Dim(espaço das linhas) = no de linhas não zero da matriz

escalonada. - Um único espaço de linhas uma única matriz escalonada.

Espaço Nulo de uma Matriz

É o espaço nulo do espaço das linhas da matriz. Propriedades do espaço nulo: Um vetor v (n-upla) está no espaço nulo de uma matriz M, se e somente se: ]1[0 m

TMv onde:

MT = matriz mn , transposta de M; nn vvvv ,,, 211 . Teorema 2.15 (P & W): Se V2 V1 e Dim(V1) = k Dim(V2) = n–k onde, n = Dim(V); V = espaço vetorial de n-uplas.