Uma Apresentação do Sistema
GAP – Laboratório II
Professores: Osnel Broche Cristo e Anliy Sargeant
Monitor: Junior Assis Barreto Bernardes
Listas: Revisão
gap> L : [6,8,9];; # Elementos entre colchetes e separados por vírgula.
gap> Append(L, [2]);; # Concatena a segunda lista passada no final da
primeira.
gap> Add(L, true); # Adiciona o elemento no final da lista.
gap> L[3]; # Acesso a determinada posição da lista.
9
Listas: Revisão
gap> List([1,2,3], x -> x^3);
[1,8,27]
gap> Length(L); # Retorna a quantidade de elementos da lista.
5
gap> Position(L, 8); # Retorna a posição que o elemento passado ocupa
na lista.
2
Conjuntos
• Os conjuntos são definidos no GAP como listas
densas (sem buracos) e sem repetições, cujos
elementos obedecem uma certa ordem que,
no caso dos números inteiros, deve ser
crescente.
gap> IsSet([1,2,3,4]);
true
gap> IsSet([1,,2,,3,4]);
false
Conjuntos
gap> IsSet([3,2,1]);
false
gap> IsSet([1,2,2,3]);
false
gap> AsSet([1,,3,2,,]);
[1,2,3]
gap> IsSet([“a”, “b”, “c”]);
true
gap> IsSet([“c”, “b”, “a”]);
false
Conjuntos
• Conjuntos Heterogêneos:
gap> IsSet(["a",4,true,3,0,false,8/9,"b",-6]);
false
gap> AsSet(["a",4,true,3,0,false,8/9,"b",-6]);
[ -6, 0, 8/9, 3, 4, true, false, "a", "b" ]
Conjuntos
• Existem funções para adicionar e remover
elementos obedecendo as restrições dos
conjuntos:
gap> S := [2,3,7,11];;
gap> AddSet( S, 5 );
gap> S;
[ 2, 3, 5, 7, 11 ]
gap> RemoveSet(S,7);
gap> S;
[ 2, 3, 5, 11 ]
Álgebra dos Conjuntos
• As operações União, Interseção e Diferença já
estão definidas no sistema.
gap> B := [1,2,3];;
gap> A := [1,5,6];;
gap> Union (A,B);
[1, 2, 3, 5, 6]
gap> Intersection (A,B);
[1]
gap> Difference(A,B);
[5, 6]
gap> Difference(B,A);
[2, 3]
Álgebra dos Conjuntos
• Quando as listas passadas não estão nas condições
necessárias para representarem conjuntos, o
próprio sistema faz uma conversão interna para
executar as operações:
gap> C := [1,2,,,3,3,,2];;
gap> D := [,1,,1,,,5,6,5,6];;
gap> Union(D,C);
[1, 2, 3, 5, 6]
gap> Intersection(D,C);
[1]
gap> Difference(D,C);
[5, 6]
gap> Difference(C,D);
[2, 3]
Álgebra dos Conjuntos
gap> P := [-7, 1, true, "b", "o"];
[ -7, 1, true, "b", "o" ]
gap> Q := [0, false, true, "o"];
[ 0, false, true, "o" ]
gap> Union(P,Q);
[ -7, 0, 1, true, false, "b", "o" ]
gap> Intersection(P,Q);
[ true, "o" ]
gap> Difference(P,Q);
[ -7, 1, "b" ]
gap> Difference(Q,P);
[ 0, false ]
Relações entre Conjuntos
• Igualdade
gap> [1,2,3] = [3,2,1];
false
gap> IsEqualSet([1,2,3],[3,2,1]);
true
gap> IsEqualSet([1,2,3],[1,2,2,3]);
true
gap> IsEqualSet([1,2,3],[1,2,3,4]);
false
gap> IsEqualSet(["a",true,8],[8,true,"a"]);
true
Gap> IsEqualSet([1,2,,3],[1,2,3]);
true
Relações entre Conjuntos
• Subconjunto
gap> IsSubset(Rationals,Integers);
#Obs: A ordem é se o segundo é subconjunto do primeiro.
true
gap> IsSubset([1,2,3,4], [2,3,5]);
false
gap> IsSubset([1,2,3],[2,1]);
true
gap> IsSubset([1,2,,2,3,4,,,5,],[2,1]);
true
gap> IsSubset([1,2,,2,3,4,,,5,],[2,1,2,,5]);
true
Relação Especial
• Pertinência (Entre elemento e conjunto)
gap> 3 in Integers;
true
gap> 2/8 in Integers;
false
gap> 1 in [1,2,3];
true
gap> [1] in [1,2,3];
false
gap> [1] in [[1],[2],[3]];
true
gap> 1 in [[1],[2],[3]];
false
Relações
• Uma relação binária em A é definida como um
subconjunto do produto cartesiano de A com A:
gap> A := [1,2,3];
gap> Cartesian(A,A);
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ], [ 3, 1 ],
[ 3, 2 ], [ 3, 3 ] ]
gap> IsBinaryRelation([[1,1],[2,2],[3,3]]);
Error, no method found! For debugging hints type ?Recovery from
NoMethodFound
Error, no 1st choice method found for `IsEndoGeneralMapping' on 1
arguments called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
Relações
• A função IdentityBinaryRelation(n) gera a
relação dada pelo diagonal do conjunto dos
inteiros de 1 até n:
gap> R1 := IdentityBinaryRelation(3);
<equivalence relation on <object>
gap> Source(R); #Conjunto
gap> <object>
gap> List(Source(R));
[1 ,2 ,3]
gap> List(UnderlyingRelation(R)); #Elementos
[ Tuple( [ 1, 1 ] ), Tuple( [ 2, 2 ] ), Tuple( [ 3, 3 ] ) ]
Relações
• A função IdentityBinaryRelation também pode ser
aplicada a outros conjuntos:
gap> R2 := IdentityBinaryRelation(Integers);
IdentityMapping( Integers )
gap> Source(R2);
Integers
gap> List(Source(R2));
Error, resulting list would be too large (length
infinity) called from …
Relações
• A função EmptyBinaryRelation(n) gera a relação
vazia no conjunto dos inteiros de 1 até n:
gap> R3 := EmptyBinaryRelation(4);
Binary Relation on 4 points
gap> List(Source(R3));
[ 1, 2, 3, 4 ]
gap> List(UnderlyingRelation(R3));
[ ]
Relações
• A função EmptyBinaryRelation também pode
ser aplicada a outros conjuntos:
gap> R4 := EmptyBinaryRelation(Rationals);
<general mapping: Rationals -> Rationals >
gap> Source(R4);
Rationals
gap> List(Source(R4));
Error, resulting list would be too large (length
infinity) called from
gap> List(UnderlyingRelation(R4));
[ ]
Relações
• A função BinaryRelationByElements(A, R) gera a relação
R do conjunto A:
gap> A := [1,2,3];;
gap>BinaryRelationByElements(A,[[1,1],[2,2],[3,3]]);
Error, <S> and <R> must be domains called from
GeneralMappingByElements( d, d, elms ) called from
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
Relações
•
Como definir relações no sistema usando a
função BinaryRelationByElements(A, R) ?
1) Primeiramente deve-se definir o conjunto A ,
para o sistema o domínio A usando a função
Domain:
gap> A := Domain([1,2,3]);;
Relações
2) Depois define-se os elementos da relação R,
isto é os pares de elementos relacionados
por R, para o sistema as tuplas usando a
função Tuple:
gap>R := [Tuple([1,1]),Tuple([2,2]),Tuple([3,3])];
3) Por fim, define-se a relação em si:
gap> RR := BinaryRelationByElements (A, R);
Relações: Propriedades
gap> IsReflexiveBinaryRelation(R1);
true
gap> IsReflexiveBinaryRelation(R2);
true
gap> IsReflexiveBinaryRelation(R3);
false
gap> IsReflexiveBinaryRelation(R4);
false
gap> IsReflexiveBinaryRelation(RR);
true
Relações: Propriedades
gap> A := Domain(["a","b"]);
<object>
gap> R :=[Tuple(["a","b"])];
[ Tuple( [ a, b ] ) ]
gap> R5 := BinaryRelationByElements(A,R);
<general mapping: <object> -> <object> >
gap> IsBinaryRelation(R5);
true
gap> IsReflexiveBinaryRelation(R5);
false
Relações: Propriedades
gap> IsTransitiveBinaryRelation(R1)
true
gap> IsTransitiveBinaryRelation(R1)
true
gap> IsTransitiveBinaryRelation(R3)
true
gap> IsTransitiveBinaryRelation(R4)
true
gap> IsTransitiveBinaryRelation(RR)
true
gap> IsTransitiveBinaryRelation(R5);
true
Relações: Propriedades
gap> IsSymmetricBinaryRelation(R1);
true
gap> IsSymmetricBinaryRelation(R2);
true
gap> IsSymmetricBinaryRelation(R3);
true
gap> IsSymmetricBinaryRelation(R4);
true
gap> IsSymmetricBinaryRelation(RR);
true
gap> IsSymmetricBinaryRelation(R5);
false
Relações: Propriedades
gap> B := Domain(["a","b"]);
<object>
gap> R :=[Tuple(["a","b"]), Tuple(["b","a"])];
[ Tuple( [ a, b ] ), Tuple( [ b, a ] ) ]
gap> R6 := BinaryRelationByElements(B,R);
<general mapping: <object> -> <object> >
gap> IsBinaryRelation(R6);
true
gap> IsSymmetricBinaryRelation(R6);
true
Relações: Propriedades
gap> IsAntisymmetricBinaryRelation(R1);
true
gap> IsAntisymmetricBinaryRelation(R2);
true
gap> IsAntisymmetricBinaryRelation(R3);
true
gap> IsAntisymmetricBinaryRelation(R4);
true
gap> IsAntisymmetricBinaryRelation(RR);
true
gap> IsAntisymmetricBinaryRelation(R6);
false
Funções (Mappings)
• Função é um caso particular de relação. Assim, está
definida analogamente no sistema:
gap> S := Domain([1,2,3]);
<object>
gap> R := Domain([1,2,3,4,5]);
<object>
gap> elms := [Tuple([1,5]),Tuple([3,4])];
[ Tuple( [ 1, 5 ] ), Tuple( [ 3, 4 ] ) ]
gap> F := GeneralMappingByElements(S,R,elms);
<general mapping: <object> -> <object> >
Funções (Mappings)
• Outra maneira de definir:
gap> B := Domain([1,2,3]);
gap> G := MappingByFunction(B,Integers,x->x^2);
MappingByFunction( <object>, <object>, function( x ) ... end )
gap> UnderlyingRelation(G);
<object>
gap> List(last);
[ Tuple( [ 1, 1 ] ), Tuple( [ 2, 4 ] ), Tuple( [ 3, 9 ] ) ]
Funções: Propriedades
gap> IsSurjective(F);
false
gap> IsSurjective(G);
false
gap> IsInjective(G);
true
gap> IsInjective(F);
true
gap> IsBijective(F);
false
gap> IsBijective(G);
false
Funções: Propriedades
gap> F := Domain([-1,-2,-3]);
<object>
gap> H := MappingByFunction(Integers,F,x -> x^2);
MappingByFunction( <object>, <object>, function( x ) ... end )
gap> IsInjective(last);
false
gap> IsBijective(H);
false
Funções: Propriedade
gap> A := Domain(["a","b","c"]);
<object>
gap> B := Domain(["a","b","c"]);
<object>
gap> R :=[Tuple(["a","b"]), Tuple(["b","a"]),
Tuple(["c","c"])];
[ Tuple( [ a, b ] ), Tuple( [ b, a ] ), Tuple( [ c, c ] ) ]
gap> F2 := GeneralMappingByElements(A,B,R);
<general mapping: <object> -> <object> >
Funções: Propriedades
gap> List(UnderlyingRelation(F2));
[ Tuple( [ a, b ] ), Tuple( [ b, a ] ), Tuple( [ c, c ] ) ]
gap> IsInjective(F2);
true
gap> IsSurjective(F2);
true
gap> IsBijective(F2);
true
Funções (Programação)
• gap> cubo := x -> x^3;
function( x ) ... end
gap> cubo(5);
125
• function ([argumentos f, argumentos g])
local identicador local f, identicador local g;
instruções;
end;
Funções (Programação)
• gap> fat := function(n)
> local f,i; # Variaveis locais
> f := 1;
> for i in [1 .. n] do
> f := f*i;
> od;
> return f; # Retorno da função.
> end;
Funções (Programação)
• gap> fatorial := function(n)
> if n = 0 then
> return 1;
> else
> return n*fatorial(n-1); #Chamada recursiva, também
presente no GAP.
> fi ;
> end;