Módulo 05c - Complementos de Estruturas Algébricas

Prévia do material em texto

1
1
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 1
Módulo 05c – Complementos de Estruturas 
Algébricas
Marco Túlio Carvalho de Andrade
Professor Responsável
Versão: 2.0 (Setembro de 2.013)
PCS 2215
Sistemas Digitais I
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 2
Conteúdo
Complementos de Estruturas Algébricas
Álgebra
Estrutura Algébrica – Sistema Algébrico
Estruturas Algébricas – Exemplos:
Semigrupo
Monóide
Grupo
Anel
Corpo
Reticulado
2
2
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 3
Álgebra
Álgebra = derivado de “al-jabr”.
Parte do Título do Livro: “Hisab al-jabr w‘al-
muqabala”; escrito em 820 DC pelo 
matemático e astrônomo “al-khowârizmi”.
Uma tradução para o inglês [Hein-2010] do 
Título do Livro é:
“Calculations by Restoration and Reduction”.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 4
Álgebra
De onde se deduz que:
“al-jabr”  “Restoration” & “Reduction”
“Restoration” refere-se a uma técnica de 
adição e subtração de um número, de ambos 
os lados de uma equação.
“Reduction” refere-se à técnica de 
simplificação. 
Álgebra
Equações
Manipulações
Simplificações
3
3
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 5
Álgebra
Algorítmo – Provém do nome do Autor do 
Livro citado – “al-khowârizmi” – mal pronun-
ciado, que se refere a um método de calcular
que faz uso de numerais Hindús.
Simplificação – O ato de simplificar é vago e 
as perguntas que ficam são: Simplificar O 
QUE? O que é SIMPLIFICAR?
Usa-se Álgebra para descrever e/ou modelar
problemas reais e os métodos de simplifica-
ção para extrair soluções. 
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 6
Álgebra
Uma parte importante da solução de proble-
mas é o processo de transformar problemas 
descritos com palavras informais – texto 
informal em linguagem natural – em elemen-
tos formais tais como equações, expressões, 
algorítmos, etc.
Outra parte importante é transformar a des-
crição e/ou representação formal em solu-
ções. 
4
4
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 7
Álgebra
A transformação da descrição formal em 
soluções é obtida pela resolução de equa-
ções, simplificação de expressões, e imple-
mentação de algorítmos.
Uma Álgebra deve proporcionar ferramen-
tas e técnicas para auxiliar que problemas 
descritos de maneira informal sejam trans-
formados em uma descrição formal e que 
isto seja de auxílio à obtenção de soluções
para estes.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 8
Álgebra
O mecanismo de descrição deve ser tal que 
que permita uma descrição correta por 
construção, precisa, clara e consistente.
Álgebra [Hein-2010] – Estrutura que con-
siste de um ou mais conjuntos e com uma 
ou mais operações definidas sobre elemen-
tos destes.
Sistema Algébrico – Notação:
<S , f1 , f2 , . . . >
Conjunto (S); Operações f1, f2, etc.
5
5
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 9
Estrutura Algébrica – Sistema Algébrico
Estrutura Algébrica – Sistema Algébrico.
Quando usar um Sistema Algébrico ou um 
Diagrama Lógico?
Sistema Algébrico – Quando o uso de Expressões 
Algébricas for necessário por permitir manipula-
ções com maior facilidade.
Diagrama Lógico – Permite encontrar simplifica-
ções com maior facilidade, pois sua visualização é 
mais direta.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 10
Estrutura Algébrica – Sistema Algébrico
Sistema Algébrico – Estrutura Algébrica – Sis-
tema que consiste de um conjunto de uma ou mais 
operações n-árias, fechadas, sobre elementos 
pertencentes ao conjunto.
Operação Fechada – O resultado da operação é 
um elemento pertencente ao mesmo conjunto do 
qual foram tirados os operandos.
Operação Unária – Aplicação f de {0,1} em {0,1}:
f : {0,1}  {0,1}
f : Z2  Z2
6
6
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 11
Estrutura Algébrica – Sistema Algébrico
Operação Binária – Aplicação f, do Produto 
Cartesiano de {0,1} por {0,1}, em {0,1}:
f : {0,1} X {0,1}  {0,1}
f : {0,1}2  {0,1}
f : Z2
2  Z2
Z2
2 = Z2 X Z2 = {0,1} X {0,1} 
Z2
2 = {(0,0),(0,1),(1,0),(1,1)}
f : {(0,0),(0,1),(1,0),(1,1)}  {0,1}
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 12
Estrutura Algébrica – Sistema Algébrico
Operação n-ária – Aplicação f, do Produto 
Cartesiano de {0,1} por {0,1} por {0,1} por … … 
por {0,1}, em {0,1}:
f : {0,1} X {0,1} X … X {0,1}  {0,1}
f : {0,1}n  {0,1}
f : Z2
n  Z2
Z2
n = Z2 X … X Z2 = {0,1} X … X {0,1} 
Z2
n = {(0,…,0),(0,…,1),(1,…,0),(1,…,1)}
f : {(0,…,0),(0,…,1),(1,…,0),(1,…,1)}  {0,1}
7
7
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 13
Estrutura Algébrica – Sistema Algébrico
Sistema Algébrico – Estrutura Algébrica:
Elementos (objetos); Operadores; Propriedades.
A aplicação de operadores a elementos permite 
verificar algumas propriedades que dependem da 
forma como se definiu o operador.
Os Sistemas Algébricos guardam propriedades
em comum.
Motivam o estudo dos Sistemas Algébricos Abs-
tratos (SAA`s), para os quais estas propriedades 
são tomadas como axiomas.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 14
Estrutura Algébrica – Sistema Algébrico
Qualquer resultado válido para um Sistema 
Algébrico Abstrato (SAA), mantém sua validade 
para todos os SAA`s para os quais os axiomas do 
SAA original também são válidos.
8
8
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 15
Estruturas Algébricas – Exemplos:
Estruturas Algébricas – Exemplos:
Semigrupo
Monóide
Grupo
Anel
Corpo
Reticulado
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 16
Estruturas Algébricas – Exemplos: Semigrupo
Estruturas Algébricas – Exemplos: Semigrupo
Semigrupo < S , o >.
É a mais simples das Estruturas Algébricas.
O operador satisfaz as propriedades do 
Fechamento e da Associatividade.
Aplicações: Linguagens formais, máquinas 
sequenciais.
9
9
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 17
Estruturas Algébricas – Exemplos: Monóide
Estruturas Algébricas – Exemplos: Monóide
Monóide < S , ° >.
Além das propriedades do Semigrupo satisfaz a 
propriedade da identidade:
Existe elemento I tal que
a ° I = I ° a = a
Aplicações: Linguagens formais e análise 
sintática.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 18
Estruturas Algébricas – Exemplos: Grupo
Estruturas Algébricas– Exemplos: Grupo
Grupo < S , ° >. Grupos são monóides que pos-
suem a propriedade da inversão – Cada elemento 
x possui um único correspondente elemento 
inver-so x-1. Existe o elemento inverso x-1 tal que:
x-1 ° x = x ° x-1 = I
Aplicações: Projetos de somadores e códigos de 
correção de erros.
Grupo Abeliano – É um grupo no qual a operação 
“°” é comutativa.
10
10
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 19
Estruturas Algébricas – Exemplos: Anel
Estruturas Algébricas – Exemplos: Anel
Anel < S , + ,  > – Sistema Algébrico cujas 
operações + e  satisfazem as três propriedades 
seguintes:
1-) < S , + > – É um Grupo Abeliano;
2-) < S , + ,  > – É um Semigrupo;
3-) A operação  é distributiva com relação à 
operação +:
a  (b + c) = a  b + a  c
(b + c)  a = b  a + c  a
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 20
Estruturas Algébricas – Exemplos: Corpo
Estruturas Algébricas – Exemplos: Corpo
Corpo (Field) – Um Anel comutativo < S , + ,  > 
que tem mais do que um elemento, de maneira 
que, cada elemento não-zero de S tenha um 
inverso multiplicativo em S é chamado de Corpo.
11
11
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 21
Estruturas Algébricas – Exemplos: Reticulado
Estruturas Algébricas – Exemplos: Reticulado.
Reticulado – Sistema Algébrico < L , + ,  > com 
duas operações binárias, onde L é um conjunto 
parcialmente ordenado L = (L, ≤).
Reticulado – < L , + ,  > – < (L, ≤) , + ,  >.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 22
Estruturas Algébricas – Exemplos:
Estruturas Algébricas – Exemplos:
.
12
12
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 23
Bibliografia
Fernández, Gregório; Saez Vacas, Fernando; 
“Fundamentos de Informática”, Alianza 
Editorial, Colección Alianza Informática, 1.987.
Gersting, Judith L.; “Fundamentos Matemáticos 
Para a Ciência da Computação”, LTC - Livros 
Técnicos e Científicos Editora S. A., 1.995.
Hein, James L.; “Discrete Structures, Logic and 
Computability”, Jones and Bertlett Publishers, 
Sudbury, MA, USA, 2010.
© Andrade, Corrêa, Gomi e Margi 2.013 < Complementos de EstruturasÁlgebricas > PCS 2215 Sistemas Digitais I 24
Bibliografia
Johnsonbaugh, Richard; “Discrete Mathema-
tics”, 3ª Edição, Macmillan Publishing Com-
pany, 1.993.
Mendelson, Elliott; “Álgebra Booleana e Cir-
cuitos de Chaveamento”, Coleção Schaum, 
Editora McGraw-Hill, 1.977.
Tremblay, J. P. and Monohar, R.; “Discrete 
Mathematical Structures With Applications 
to Computer Science”, McGraw-Hill, 1.975.