Md9 Estruturas-algébricas

•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE •CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA •DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO •Professor Ulrich Schiel

Estruturas Matemáticas • Modelos matemáticos de fenômenos da natureza podem ser divididos em três grandes categorias: • Estruturas de Ordem



• Estruturas Algébricas



• Estruturas Topológicas (Geometria, Análise)

Estruturas Algébricas •

Estruturas Algébricas:

 - conjunto abstrato de objetos juntamente com operações e relações entre esses objetos e que obedecem certas regras.  A =  Em que Op é um conjunto de operações e  R é um conjunto de relações  Se R é vazio temos uma Álgebra,  se Op é vazio temos um Modelo ou um Sistema Relacional

Estruturas Algébricas •

Estruturas Algébricas - Operações:

 Uma operação (interna) * sobre um conjunto C, é uma função *:C×.. × C → C  Exemplos: A = ;  C = < Z, ≤ >;

B = ;

D = < N, succ, *, 0, 1, max, min >

 Uma operação externa * de um domínio K sobre um conjunto C, é uma função *:K×C→C Exemplo:  E = < R2, N, *>, com *: N → R2, dado por *(k,(x,y)) = (kx,ky)

Estruturas Algébricas

• DEFINIÇÃO: • Uma Álgebra é um par com:  - C é um conjunto  - Op é um conjunto de operações sobre C

Estruturas Algébricas Propriedades das operações: - Dado uma álgebra as seguintes propriedades podem ser válidas, para quaisquer x, y, z de C: x*y=y*x

(comutativa)

(x * y) * z = x * (y * z)

(associativa)

∃ 1∈C (x * 1 = x)

(identidade)

∀x ∈C ∃ x-1 ∈C (x * x-1 = 1)

(inverso)

Se houver outra operação + em C, ou seja, temos , pode valer a propriedade: x + (y * z) = (x + y) * (x+ z) e x * (y + z) = (x * y) + (x * z)

(distributiva)

Estruturas Algébricas • Estruturas Algébricas – Álgebras de Boole

• Um exemplo notável de estrutura algébrica é a álgebra booleana ou Álgebra de Boole (George Boole, 1850), formulada inicialmente para modelar a lógica proposicional e utilizada posteriormente por Shannon (1938) para modelar circuitos eletrônicos (ou digitais).

Álgebra Booleana → Uma Álgebra de Boole B é uma estrutura algébrica B = formada por →um conjunto não-vazio (domínio) B, →duas operações binárias + : B2→B e · : B2→B, →uma operação unária ‘ : B→B e →dois elementos distinguíveis de B, a e b, obedecendo às seguintes propriedades, para todo x, y e z pertencentes à B: • • • • •

1a. x+y = y+x 2a. (x+y)+z = x+(y+z) 3a. x+(y · z) = (x+y)·(x+z) 4a. x+a = x 5a. x+x’ = b

1b. x · y = y · x 2b. (x · y) ·.z = x · (y · z) 3b. x · (y+z) = (x · y)+(x · z) 4b. x · b = x 5b. x · x’ = a

Álgebra Booleana • Exemplo 1: B1 = <{0,1}, +, ·, ‘, 0, 1>, onde: • x+y = max(x,y), x · y = min(x,y), 0’=1 e 1’=0. • Exemplo 2: B2 = <{∅, {1}, {2}, {1,2}}, ∪, ∩, ‘, ∅, {1,2}> • Exemplo 3: B3 = , para qualquer S • Exemplo 4: B4 = <{F,V}, OR, AND, NOT, F, V>.

Exercícios •

Demonstre as seguintes propriedades para uma álgebra de Boole B = :

2. x+x = x, para todo x ∈ B (Idempotência) 3. x+b = b, para todo x ∈ B 4. (x ’) ’ = x, para todo x ∈ B 5. x+(x · y) = x, para todo x, y ∈ B 6. (x+y)’ = x ’ · y ’ (Lei de De Morgan) 7. O elemento neutro é único.

Homomorfismos e Isomorfismos • •

Entre conjuntos temos funções f:C → D Entre estruturas matemáticas ou álgebras ou categorias temos morfismos h: →

•

Dados duas Álgebras A= e B=, um morfismo h: A → B é um homomorfismo se conserva as operações, ou seja, para todo a,b ∈ A temos

•

h(a *A b) = h(a) *B h(b)

Homomorfismos e Isomorfismos •

•

•

Duas estruturas matemáticas A e B são ditas serem isomorfas se e somente se existir uma bijeção (isomorfismo) que leva elementos de uma em elementos da outra de modo que as propriedades (funções e relações) sejam preservadas. Se duas estruturas são isomorfas então cada uma é a imagem semelhante da outra, a menos do rotulamento de seus elementos. Ex.: considere os seguintes POSET’s:

• •

P1: ({1,2,3,6}, x divide y)

•

P2: (P({1,2}), x⊆y)

Isomorfismo • •

Seja f:: {1,2,3,6} → P({1,2}) definida por:

•

f(1) = ∅;

f(2) = {1};

f(3) = {2};

6

f(6) = {1,2} {1,2}

f 2

3

{1}

1

f é um isomorfismo de P1 em P2

{2}

∅

Isomorfismo de álgebras booleanas • Sejam A = e B = duas álgebras booleanas. Um morfismo f: A → B é dita ser um isomorfismo de A em B, se para todo x e y ∈A: – – –

f é uma bijeção f(x+y) = f(x) & f(y) f(x.y) = f(X) * f(y)

–

f(x’) = f(x)”

Isomorfismo

x,y ∈B

operação (+, ., ‘)

f

u,w∈A

z ∈B

f-1

operação (&, *, “)

v ∈A

Exercício Sejam C = <{0, 1, a, b}, +, ·, “, 0, 1>, onde as operações são dadas pelas tabelas ao lado, e B = duas álgebras booleanas.

Mostre que a função f:{0,1,a,b} → P({1,2}) dada por: f(0) = ∅ f(1) = {1,2} f(a) = {1} f(b) = {2} é um isomorfismo de C em B .

+ 0 1 a b

0 0 1 a b

1 1 1 1 1

a a 1 a 1

b b 1 1 b

.

0

1

a

b

0

0

0

0

0

1

0

1

a

b

a

0

a

a

0

b

0

b

0

b

“ 01 10 ab ba

Teorema de álgebras booleanas finitas Seja B qualquer álgebra booleana com |B|=n elementos. Então, n = 2m, para algum m, e B é isomorfa a P({1,2,...,m}). Obs.: o número de elementos do domínio de qualquer álgebra booleana é uma potência de 2.

Outras estruturas algébricas Seja S um conjunto e * uma operação binária : * : S x S → S. • A operação * é associativa se: x * (y * z) = (x * y) * z, para quaisquer x, y e z ∈ S. • A operação . é comutativa se: x * y = y * x, para todo x e y ∈ S. • S tem um elemento neutro em relação à operação * se: existe i ∈ S tal que para todo x ∈ S, x * i = x = i * x . • Todo elemento tem um inverso em relação à operação * se: para todo x ∈ S existe x-1 ∈ S tal que x * x-1 = i = x-1 * x . Ex.: As estruturas < Z, + >, < Z, . >.

Grupo → Uma estrutura G = < S, * > é um grupo se S é um conjunto não vazio e * é uma operação binária sobre S (operação de grupo) tal que: •

a operação * é associativa;

• •

S tem um elemento neutro em relação à operação * ; todo elemento de S tem um elemento inverso em relação à operação *

→ Se valer só a associatividade temos um semi-grupo. → Obs. Um grupo no qual a operação de grupo chamado de grupo comutativo ou abeliano. → A estrutura < Z, + > é um grupo comutativo.

* é comutativa é

Exemplo Seja R+ o conjunto dos reais positivos e seja . a operação de multiplicação de reais. Então, : • < R+, . > é um grupo comutativo. • O elemento neutro é o 1. • Para qualquer real positivo x, 1/x é o seu inverso com relação à operação de multiplicação.

Exercícios •

< R, . > é um grupo ? É semi-grupo?

•

< Z, - > é um grupo ? É semi-grupo?

•

Seja M2(Z) o conjunto das matrizes 2x2 de elementos inteiros e seja + a operação de adição de matrizes. Mostre que < M2(Z), + > é um grupo comutativo. Mostre que < M2(Z), . > não é um grupo.

•

Temos e . Como será ??

Anel → Uma álgebra G = < S, +, * > é um anel se valem as seguintes propriedades: • < S, + > é um grupo abeliano; • < S, * > é um semi-grupo; • Vale a distributividade a esquerda e a direita entre as operações, ou seja, a.(b+c)= a.b + a.c e (a+b).c = a.c + a.c Um anel é comutativo se * é comutativa. Exemplos: Z, Q, R, C com + e . são anéis. Uma álgebra de Boole é um anel comutativo idempotente (i.e. a.a = a)

Corpo → Uma álgebra G = < S, +, * > é um corpo se valem as seguintes propriedades: • < S, + , * > é um anel; • < S-{0}, * > é um grupo comutativo; • Vale a distributividade a esquerda e a direita entre as operações, ou seja, a*(b+c)= a*b + a*c e (a+b)*c = a*c + a*c Exemplos: Q, R, C com + e . são corpos. → Dado um corpo < S, +, * >, podemos definir a diferença e a divisão como → a - b = a + (-b) e a / b = a * b-1

Operadores externos → Dado um conjunto S uma operação externa * de um domínio K sobre S é uma função: • * : K x S → S, ou seja k*a = b ; • Operações externas de um anel podem ser combinadas com operações internas em um grupo <S, + >: → k * (a + b) = k*a + k*b → (k + s)* a = k * a + s * a → (k . s) * a = k*(s*a) →1*a=a Que da origem a estrutura de Módulo

Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z • comutativo C – comutativa x * y = y * x • <M2(Z), +> comutativo N – neutro ou identidade x * i = i * x = x • comutativo I – inverso x * x-1 = x-1 * x = i • monóide • comutativo A → semi-grupo • comutativo AN → monóide • comutativo ANI → grupo • comutativo ACNI → grupo comutativo • <M2(Z), . > não-comutativo • semi-grupo • comutativo

Exercícios Propriedades: <S,*> Exemplos: * é fechada se x * y está em S • grupo A – associativa x * (y * z) = (x * y) * z • comutativo C – comutativa x * y = y * x • monóide N – neutro ou identidade x * i = i * x = x • comutativo I – inverso x * x-1 = x-1 * x = i • < Σ*, ||> não-comutativo A → semi-grupo AN → monóide ANI → grupo ACNI → grupo comutativo

• • semi-grupo •

Exercícios Propriedades: * é fechada se x * y está em S A – associativa x * (y * z) = (x * y) * z C – comutativa x * y = y * x N – neutro ou identidade x * i = i * x = x I – inverso x * x-1 = x-1 * x = i D-distributivo a.(b+c)= a.b + a.c (a+b)*c = a*c + b*c Dado <S,+,*> é um: Anel se <S, +> grupo comutativo (ACNI) <S, *> semi-grupo (A) vale D Corpo se é um anel e < S-{0}, * > é um grupo Corpo comutativo se é um corpo e * é comutativa

Exemplos: • anel • comutativo • corpo • comutativo • <M2(Z), +, . > não-comut. • •

comutativo

• Em uma Álgebra de Boole e são monóides comutativos