MediaWiki API result
This is the HTML representation of the JSON format. HTML is good for debugging, but is unsuitable for application use.
Specify the format parameter to change the output format. To see the non-HTML representation of the JSON format, set format=json.
See the complete documentation, or the API help for more information.
{
"batchcomplete": "",
"continue": {
"gapcontinue": "Sem\u00e2ntica_formal_para_a_L\u00f3gica_Proposicional_Cl\u00e1ssica",
"continue": "gapcontinue||"
},
"warnings": {
"main": {
"*": "Subscribe to the mediawiki-api-announce mailing list at <https://lists.wikimedia.org/mailman/listinfo/mediawiki-api-announce> for notice of API deprecations and breaking changes."
},
"revisions": {
"*": "Because \"rvslots\" was not specified, a legacy format has been used for the output. This format is deprecated, and in the future the new format will always be used."
}
},
"query": {
"pages": {
"236": {
"pageid": 236,
"ns": 0,
"title": "Rela\u00e7\u00e3o de consequ\u00eancia",
"revisions": [
{
"contentformat": "text/x-wiki",
"contentmodel": "wikitext",
"*": "* Defini\u00e7\u00e3o de '''rela\u00e7\u00e3o de consequ\u00eancia''': vers\u00e3o tarskiana, unilateralista<!--\n--><p>{{#ev:youtube|3eEXx4HN3AM}}</p><!--\n--><p>Acima, tamb\u00e9m: '''opera\u00e7\u00e3o de consequ\u00eancia''', '''teoria''', '''finitariedade''', '''invari\u00e2ncia por substitui\u00e7\u00e3o'''</p>\n* No\u00e7\u00e3o de '''equival\u00eancia l\u00f3gica'''<!--\n--><p>{{#ev:youtube|Et_hGh-XLnM}}</p>\n* '''Congruencialidade''': enunciado e significado do Meta-teorema de Substitutividade de Equivalentes (EN: ''replacement theorem'')<!--\n--><p>{{#ev:youtube|fw8t7Kju3gI}}</p>\n* No\u00e7\u00f5es de '''inconsist\u00eancia'''<!--\n--><p>{{#ev:youtube|DaBt0ZFVDtE}}</p>\n\n== Para reflex\u00e3o ==\n\n* Quando podemos dizer que duas ''teorias'' (em uma mesma linguagem) s\u00e3o logicamente equivalentes?\n\n== Veja tamb\u00e9m ==\n\n* [[Formalismos dedutivos]]\n* [[Acarretamento]] (consequ\u00eancia sem\u00e2ntica, ''entailment'')\n* [[Corre\u00e7\u00e3o e completude]]\n* [[Introdu\u00e7\u00e3o Computacional \u00e0 L\u00f3gica Matem\u00e1tica]]\n\n== Links externos ==\n\n* [http://pt.wikipedia.org/wiki/F%C3%B3rmula_%28l%C3%B3gica%29 F\u00f3rmula (l\u00f3gica) (Wikip\u00e9dia)]\n* [http://pt.wikipedia.org/wiki/Rela%C3%A7%C3%A3o_bin%C3%A1ria Rela\u00e7\u00e3o bin\u00e1ria (Wikip\u00e9dia)]\n* [http://pt.wikipedia.org/wiki/Consequ%C3%AAncia_l%C3%B3gica Consequ\u00eancia l\u00f3gica (Wikip\u00e9dia)]"
}
]
},
"190": {
"pageid": 190,
"ns": 0,
"title": "Rela\u00e7\u00f5es",
"revisions": [
{
"contentformat": "text/x-wiki",
"contentmodel": "wikitext",
"*": "Neste artigo, vamos aprender a usar Maple para trabalhar com rela\u00e7\u00f5es bin\u00e1rias e n-\u00e1rias. N\u00f3s explicaremos como usar Maple para representar rela\u00e7\u00f5es bin\u00e1rias usando conjuntos de pares ordenados, usando representa\u00e7\u00f5es utilizando de matrizes zero-um, e usando grafos dirigidos. Mostraremos como usar Maple para determinar se uma rela\u00e7\u00e3o tem v\u00e1rias propriedades que utilizam estas diferentes representa\u00e7\u00f5es.\n\nN\u00f3s descreveremos como calcular o fechamento das rela\u00e7\u00f5es. Em particular, mostraremos como encontrar o fechamento transitivo de uma rela\u00e7\u00e3o utilizando dois algoritmos diferentes, e n\u00f3s iremos comparar o tempo necess\u00e1rio para usar esses algoritmos. Depois de explicar como usar o Maple para trabalhar com rela\u00e7\u00f5es de equival\u00eancia, mostraremos como usar o Maple para trabalhar com ordena\u00e7\u00f5es parciais. Mostraremos como usar Maple para fazer ordena\u00e7\u00e3o topol\u00f3gica e para determinar se uma ordena\u00e7\u00e3o parcial \u00e9 um reticulado. Concluiremos mostrando como usar o Maple para encontrar rela\u00e7\u00f5es de ordena\u00e7\u00f5es parciais.\n\n\n== Uma Introdu\u00e7\u00e3o \u00e0s Rela\u00e7\u00f5es em Maple ==\nO primeiro passo para entender as rela\u00e7\u00f5es e sua manipula\u00e7\u00e3o em Maple \u00e9 determinar como representar as rela\u00e7\u00f5es em Maple. O leitor notar\u00e1 que n\u00e3o h\u00e1 nenhum pacote de rela\u00e7\u00f5es espec\u00edfico presente em Maple, e, portanto, a implementa\u00e7\u00e3o e a representa\u00e7\u00e3o das rela\u00e7\u00f5es em Maple pode assumir a forma mais conveniente para a quest\u00e3o em apre\u00e7o. Poss\u00edveis representa\u00e7\u00f5es de rela\u00e7\u00f5es em Maple incluem conjuntos de pares ordenados, matrizes zero-um ou gr\u00e1ficos dirigidos, entre muitos outros. Para este cap\u00edtulo, vamos examinar representa\u00e7\u00f5es de par ordenado e matrizes zero-um, bem como a representa\u00e7\u00e3o de gr\u00e1fico direcionado.\n\nEm primeiro lugar, devem representar rela\u00e7\u00f5es como pares ordenados. Para este fim, n\u00f3s constru\u00edmos um typerel estruturado para as rela\u00e7\u00f5es. (Note-se que n\u00e3o se pode utilizar a rela\u00e7\u00e3o nome, uma vez que este tipo j\u00e1 \u00e9 usado pela biblioteca do Maple). De acordo com a defini\u00e7\u00e3o, uma rela\u00e7\u00e3o \u00e9 um conjunto de pares ordenados de qualquer tipo e de objeto qualquer. O seguinte tipo Maple reflete essa defini\u00e7\u00e3o.\n\n<pre>\n`type/pair` := [anything, anything];\n`type/rel` := set(pair);\n</pre>\n\nIsso \u00e9 \u00fatil, uma vez que nos permite assegurar que, quando passar argumentos para fun\u00e7\u00f5es, temos utilizado o tipo de dados correto para a entrada. Sendo o nosso tipo rel estruturado, \u00e9 muito mais f\u00e1cil escrever rel do que escrever set(anything, anything) ap\u00f3s cada argumento de que deve ser interpretado como uma rela\u00e7\u00e3o. Isso tamb\u00e9m pode ser feito \u00c0 m\u00e3o dentro de cada fun\u00e7\u00e3o, antes do processamento real come\u00e7ar, mas o Maple fornece este tipo verifica\u00e7\u00e3o autom\u00e1tica para n\u00f3s e resulta em um c\u00f3digo mais r\u00e1pido e, mais importante para n\u00f3s, mais leg\u00edvel.\n\nPara um exemplo espec\u00edfico, suponha que desejamos estabelecer uma rela\u00e7\u00e3o que \u00e9 definida em termos de restri\u00e7\u00f5es num\u00e9ricas, como no Exemplo 4 na p\u00e1gina 3577 do texto. No exemplo texto, precisamos criar uma rela\u00e7\u00e3o R no dom\u00ednio A=(1,2,3,4) de modo que R={(a,b)|a divide b}. Vamos construir esta rela\u00e7\u00e3o ao examinar cada poss\u00edvel par ordenado de elementos, e admitindo pares ordenados em R se, e somente se, o par ordenado satisfaz a condi\u00e7\u00e3o apropriada. Chamaremos R de '''DividesRelation'''.\n\n<pre>\nDividesRelation := proc(A::set(integer))\n local i, j, temp, R;\n R := {};\n for i in A do\n for j in A do\n if (gcd(i,j) = i) then\n R := R union [i, j];\n fi;\n od;\n od;\n RETURN(R);\nend:\nDividesRelation(1,2,3,4);\n</pre>\n\nPor conveni\u00eancia, n\u00f3s tamb\u00e9m definir a seguinte varia\u00e7\u00e3o.\n\n<pre>\nDivRel := proc(n::posint)\n local i;\n DividesRelation(seq(i,i=1..n));\nend:\n</pre>\n\nEste procedimento constr\u00f3i a rela\u00e7\u00e3o divides sobre o conjunto de todos os inteiros no conjunto {1,2,3,...,n}.\n\nSer\u00e1 conveniente ter \u00e0 m\u00e3o o seguinte procedimento para criar o dual ou opposite rela\u00e7\u00e3o de uma determinada rela\u00e7\u00e3o.\n\n<pre>\nDualRelation := proc(R::rel)\n local u;\n map(u -> [ u[2], u[1] ], R);\nend:\n</pre>\n\nIsto simplesmente inverte todos os pares que pertencem \u00e0 rela\u00e7\u00e3o.\n\n\n== Determinar Propriedades de Rela\u00e7\u00f5es usando Maple ==\nMaple pode ser utilizado para determinar se uma rela\u00e7\u00e3o tem uma propriedade espec\u00edfica, tal como a reflexividade, simetria, antissimetria e transitividade. Isto pode ser realizado atrav\u00e9s do procedimento de cria\u00e7\u00e3o do Maple que tomam como entrada a determinada rela\u00e7\u00e3o, examinando os elementos da rela\u00e7\u00e3o, e determinar se a rela\u00e7\u00e3o satisfaz a propriedade dada.\n\nDesde que possamos utilizar isso repetidamente, ser\u00e1 conveniente ter uma rotina que ir\u00e1 extrair para n\u00f3s do dom\u00ednio de qualquer rela\u00e7\u00e3o. N\u00f3s simplesmente coletamos em conjunto todos os pontos que ocorrem tanto como uma primeira ou uma segunda entrada em algum par na rela\u00e7\u00e3o. (N\u00e3o que, estritamente falando, isso n\u00e3o precise ser igual ao dom\u00ednio da rela\u00e7\u00e3o, Uma vez que podem, na verdade, existirem pontos no dom\u00ednio que n\u00e3o s\u00e3o R-relacionados para qualquer outro ponto do dom\u00ednio. Talvez seja melhor chamar a isto o ''effective domain'' (dom\u00ednio efetivo) da rela\u00e7\u00e3o.\n\n<pre>\nDomainRelation := proc(R::rel)\n RETURN(map(u->op(1,u), R)\n union map(u->op(2,u), R));\nend:\n</pre>\n\nEm primeiro lugar, vamos examinar como determinar se uma rela\u00e7\u00e3o \u00e9 reflexiva.\n\n<pre>\nIsReflexive := proc(R::rel)\n local is_reflexive, # return value\n u; # index into Dom(R)\n is_reflexive := true;\n for u in DomainRelation(R) do\n is_reflexive := is_reflexive and member([u,u], R);\n od;\n RETURN(is_reflexive);\nend:\n</pre>\n\n<pre>\nR1 := [1,1], [1,2], [2,1], [2,2], [3,4], [4,1], [4,4]:\nR2 := [1,1], [1,2], [2,1]:\nIsReflexive(R1);\nIsReflexive(R2);\n</pre>\n\nVamos examinar as propriedades sim\u00e9tricas e antissim\u00e9tricas nos pr\u00f3ximos dois procedimentos. Para determinar se uma rela\u00e7\u00e3o \u00e9 sim\u00e9trica vamos simplesmente usar a defini\u00e7\u00e3o; isto \u00e9, verificar se para cada par (a,b) em uma rela\u00e7\u00e3o, o par (b,a) \u00e9 tamb\u00e9m membro da rela\u00e7\u00e3o. Se descobrirmos um par (a,b) na rela\u00e7\u00e3o para o qual o par (b,a) n\u00e3o est\u00e1 na rela\u00e7\u00e3o, ent\u00e3o sabemos que a rela\u00e7\u00e3o n\u00e3o \u00e9 sim\u00e9trica. Caso contr\u00e1rio, deve ser sim\u00e9trica. Esta \u00e9 a l\u00f3gica utilizada pelo procedimento seguinte.\n\n<pre>\nIsSymmetric := proc(R::rel)\n local i, is_symmetric;\n is_symmetric := true;\n for i from 1 to nops(R) do\n if not member( [ R[i][2], R[i][1] ], R) then\n is_symmetric := false;\n fi;\n od;\n RETURN(is_symmetric);\nend:\n</pre>\n\nPara determinar se uma determinada rela\u00e7\u00e3o R \u00e9 anti-sim\u00e9trica, voltamos a usar a defini\u00e7\u00e3o. Lembre-se que para uma rela\u00e7\u00e3o R que ser anti-sim\u00e9trica, ele deve ter a propriedade de que, sempre que um par (a,b) pertencer a R, e o par (b,a) tamb\u00e9m pertence a R, ent\u00e3o devemos ter que a=b. Para verificar isso, n\u00f3s simplesmente vamos varrer todos os membros u=(a,b) de R, e veja se o par oposto (b,a) pertence a R. Se isso acontecer, e se a\u2260b, ent\u00e3o R n\u00e3o pode ser antissim\u00e9trica; caso contr\u00e1rio, ela \u00e9.\n\n<pre>\nIsAntiSymmetric := proc(R::rel)\n local u; # index into R\n for u in R do\n if member([op(2,u), op(1,u)], R) and op(1, u) <> op(2, u) then\n RETURN(false);\n fi;\n od;\n RETURN(true);\nend:\n</pre>\n\nAgora usamos os nossos procedimentos para determinar qual das rela\u00e7\u00f5es definidas anteriormente s\u00e3o sim\u00e9tricas ou antissim\u00e9tricas.\n\n<pre>\nIsSymmetric(R1); IsSymmetric(R2);\nIsAntiSymmetric(R1); IsAntiSymmetric(R2);\nR3 := [1,1], [1,2], [1,4], [2,1], [2,2], [3,3], [4,1], [4,4]:\nR4 := [2,1], [3,1], [3,2], [4,1], [4,2], [4,3]:\nIsAntiSymmetric(R3); IsAntiSymmetric(R4);\n</pre>\n\nPara decidir se uma rela\u00e7\u00e3o R \u00e9 transitiva, devemos verificar se (a,c) pertencer\u00e1 a R quando existirem pares (a,b) e (b,c) que pertencem a R. Fazemos isso examinando todos os pares (a,b) em R, em conjunto com todos os elementos de x do dom\u00ednio D de R, para ver se um par (b,x) existe em R para o qual o par (x,b) n\u00e3o est\u00e1 em R. Se encontrarmos essa combina\u00e7\u00e3o, em sequencia, a rela\u00e7\u00e3o R n\u00e3o pode ser transitiva; de outra forma, R ser\u00e1.\n\n<pre>\nIsTransitive := proc(R::rel)\n local DomR, # domain of R\n u,v,w;# indices into DomR\n for u in DomR do\n for v in DomR do\n for w in DomR do\n if (member([u,v], R) and member([v,w], R) and not member([u,w], R)) then\n RETURN(false);\n fi;\n od;\n od;\n od;\nRETURN(true);\nend:\n\nIsTransitive(R1); IsTransitive(R2);\nIsTransitive(R3); IsTransitive(R4);\n</pre>\n\n\n== Rela\u00e7\u00f5es n-\u00e1rias em Maple ==\nUsando Maple, podemos construir uma rela\u00e7\u00e3o n-\u00e1ria, onde n \u00e9 um n\u00famero inteiro positivo. O formato para a express\u00e3o rela\u00e7\u00e3o n-\u00e1ria em Maple \u00e9 semelhante \u00e0 da rela\u00e7\u00e3o 2-\u00e1ria no Maple. Por exemplo, considere a seguinte rela\u00e7\u00e3o 4-\u00e1ria que representa os registros dos alunos.\n\n<pre>\nM1:=[Adams, 9012345,`Politics`, 2.98],\n [Woo, 9100055, `Film Studies`, 4.99],\n [Warshall, 9354321, `Mathematics`, 3.66]:\n</pre>\n\nO primeiro campo representa o nome do aluno, o segundo campo \u00e9 o n\u00famero de identifica\u00e7\u00e3o do aluno, o terceiro campo \u00e9 o departamento ao qual o estudante pertence e, finalmente, o \u00faltimo registro armazena a m\u00e9dia do estudante.\n\nCom esse exemplo de como usar as rela\u00e7\u00f5es n-\u00e1rias, n\u00f3s iremos construir um procedimento geral para calcular uma determinada proje\u00e7\u00e3o de uma rela\u00e7\u00e3o. O procedimento toma como entrada um conjunto de n-tuplas (enupla) como rela\u00e7\u00e3o com a imagem, que est\u00e1 a ser projetada sobre. A sa\u00edda deste processo \u00e9 um conjunto de m-tuplas.\n\n<pre>\nMakeProjection := proc(R::set, P::list)\n local i, j, S, temp_list;\n S := {};\n for i from 1 to nops(R) do\n temp_list := [];\n for j from 1 to nops(P) do\n temp_list := [ op(temp_list), R[ i ][ P[j] ] ];\n od;\n S := S union temp_list;\n od;\n S;\nend:\n</pre>\n\nAgora vamos examinar este procedimento proje\u00e7\u00e3o sobre a rela\u00e7\u00e3o 4-\u00e1rio que foi constru\u00eddo anteriormente nesta se\u00e7\u00e3o.\n\n<pre>\nMakeProjection(M1, [3,4,1]);\nMakeProjection(M1, [2,4]);\n</pre>\n\nPassamos agora de construir as proje\u00e7\u00f5es para a constru\u00e7\u00e3o de jun\u00e7\u00e3o das rela\u00e7\u00f5es. A opera\u00e7\u00e3o de jun\u00e7\u00e3o tem aplica\u00e7\u00f5es em comandos de banco de dados quando as tabelas de informa\u00e7\u00f5es precisam ser combinadas de forma significativa. A opera\u00e7\u00e3o de jun\u00e7\u00e3o que vamos programar em Maple segue este esquema pseudoc\u00f3digo:\n\n\n1- Entrada: duas rela\u00e7\u00f5es de entrada A e B, e um par\u00e2metro inteiro n\u00e3o negativo p;\n\n2- Analisar cada elemento de A, e determinar os \u00faltimos campos de p de cada elemento;\n\n3- Examinar todos os elementos, y, da rela\u00e7\u00e3o B para determinar se os primeiros campos de p em y coincidem com os \u00faltimos campos p de elemento x;\n\n4- Ao encontrar uma correspond\u00eancia de um elemento em A e um elemento em B, que combinam estes elementos, colocando o resultado em C, que \u00e9 devolvido como sa\u00edda.\n\n\n<pre>\nMakeJoin := proc(p, A, B)\n local i, j, k, C, list_A, list_B, x,\n ret_elem, is_done;\n list_A := [];\n list_B := [];\n C := {};\n for i from 1 to p do\n list_B := [op(list_B), i];\n list_A := [nops(B[1])-i, op(list_A)];\n od;\n for i from 1 to nops(A) do;\n is_done := false;\n x := MakeProjection(A[i], list_A);\n j := 1;\n while j <= nops(B) and is_done = false do\n if MakeProjection(B[j], list_B) = x then\n ret_elem := A[i];\n for k from p+1 to nops(B[j]) do\n ret_elem := [op(ret_elem), B[j][k] ];\n od;\n is_done := true;\n fi;\n j := j+1;\n od;\n C := C union ret_elem;\n od;\n C;\nend:\n</pre>\n\nN\u00f3s examinamos como este procedimento funciona no exemplo definido no livro, nas p\u00e1ginas 371 e 372, envolvendo cursos que os professores est\u00e3o ensinando para determinar onde eles est\u00e3o localizados no campus.\n\n<pre>\nA:=[Cruz, Zoology, 335],\n [Cruz, Zoology, 412],\n [Farber, Psychology, 501],\n [Farber, Psychology, 617],\n [Grammer, Physics, 544],\n [Grammer, Physics, 551],\n [Rosen, Computer, 518],\n [Rosen, Mathematics, 575]:\nB:=[Computer, 518, N521, 14],\n [Mathematics, 575, N502, 15],\n [Mathematics, 611, N521, 16],\n [Physics, 544, B505, 16],\n [Psychology, 501, A100, 15],\n [Psychology, 617, A110, 11],\n [Zoology, 335, A100, 9],\n [Zoology, 412, A100, 8]:\nMakeJoin(2, A, B);\n</pre>\n\n\n== Representar rela\u00e7\u00f5es como d\u00edgrafos e Matrizes Zero-Um ==\nComo foi dito no in\u00edcio deste cap\u00edtulo, o Maple permite representar e manipular as rela\u00e7\u00f5es em uma variedade de formas. Vimos como o pacote '''combinat''' do Maple permite que o produto cartesiano possa ser usado para gerar rela\u00e7\u00f5es e, nesta se\u00e7\u00e3o, vamos utilizar os pacotes '''networks''' (redes) e '''linalg''' para representar e manipular as rela\u00e7\u00f5es. N\u00f3s explicamos como usar Maple para trabalhar com rela\u00e7\u00f5es usando a representa\u00e7\u00e3o das rela\u00e7\u00f5es como conjuntos de pares ordenados. Nesta se\u00e7\u00e3o, vamos mostrar como usar o Maple para trabalhar com as rela\u00e7\u00f5es usando dois m\u00e9todos alternativos para representar essas rela\u00e7\u00f5es. Em primeiro lugar, vamos explicar como representar rela\u00e7\u00f5es como grafos dirigidos; isto requer o uso do pacote ''Maple'' '''networks'''. Em segundo lugar, vamos mostrar como para representar as rela\u00e7\u00f5es utiliza\u00e7\u00e3o de matrizes zero-um; isto requer o uso do pacote ''Maple'' '''linalg'''. Veremos que o uso dessas representa\u00e7\u00f5es alternativas de rela\u00e7\u00f5es nos permite usar uma ampla gama de capacidades do Maple para resolver problemas que envolvem as rela\u00e7\u00f5es.\n\n\n=== Representando Rela\u00e7\u00f5es Usando Grafos Dirigidos ===\nCome\u00e7amos analisando a forma de representar as rela\u00e7\u00f5es usando grafos dirigidos em Maple, com a ajuda do pacote '''networks'''. Para come\u00e7ar, vamos carregar o pacote '''networks'''.\n\n<pre>\nwith(networks):\n</pre>\n\nAgora, podemos converter nossas rela\u00e7\u00f5es que foram representadas no formato de par ordenado em um grafo dirigido usando o seguinte algoritmo simples, chamado '''MakeDigraph'''.\n\n<pre>\nMakeDigraph := proc(A::set,R::set)\n local G;\n new(G);\n addvertex(A, G);\n addedge(R, G);\n RETURN(G);\nend:\nG1 := MakeDigraph(1,2,3,4,R1);\nR1;\n</pre>\n\nO procedimento novo do pacote ''networks'' cria uma ocorr\u00eancia de um gr\u00e1fico, e ''addedge'' faz exatamente o que seu nome sugere: ele adiciona uma borda para o gr\u00e1fico que \u00e9 seu segundo argumento. (Uma discuss\u00e3o mais completa dessas rotinas ser\u00e3o apresentados no Cap\u00edtulo 7.)\n\nPodemos agora usar essa representa\u00e7\u00e3o gr\u00e1fica da rela\u00e7\u00e3o R1 para deduzir se \u00e9 ou n\u00e3o \u00e9 transitiva. Para fazer isso, usamos o algoritmo ''all-pairs shortest path'' (todos os pares de caminho mais curto), denotado como ''allpairs'' em Maple. Especificamente, desejamos determinar que se uma borda (a,b) e uma borda (b,c) ocorrem no gr\u00e1fico, ent\u00e3o a borda (a,c) deve ocorrer tamb\u00e9m. Por isso, usamos o seguinte esbo\u00e7o pseudoc\u00f3digo.\n\n1- Entrada: um gr\u00e1fico G, que representa uma rela\u00e7\u00e3o R;\n\n2- Executar o algoritmo ''all-pairs shortest path'' em G, que retorna o caminho mais curto entre dois pontos quaisquer;\n\n3- Se h\u00e1 um par de elementos que tem comprimento finito que \u00e9 maior do que 1, ent\u00e3o sabe que o grafo n\u00e3o \u00e9 reflexivo;\n\n4- Caso contr\u00e1rio, temos tudo (finitos) comprimentos entre os elementos um, de modo que, se (a,b) \u00e9 um par e (b,c) \u00e9 um par, ent\u00e3o a dist\u00e2ncia de a para c \u00e9 1 (Uma vez que este \u00e9 o \u00fanico comprimento poss\u00edvel, j\u00e1 que foram eliminados os comprimentos finitos que s\u00e3o maiores do que 1, no passo 3), por isso (a,c) tem de ser uma borda, e, portanto (a,c) est\u00e1 na rela\u00e7\u00e3o R.\n\n5- Sa\u00edda: o valor da decis\u00e3o a partir das etapas 3 e 4.\n\n\nA implementa\u00e7\u00e3o deste pseudoc\u00f3digo \u00e9 a seguinte;\n\n<pre>\nIsTransitive_G := proc(G::graph)\n local i, j, S, T, is_trans;\n is_trans := true;\n T := allpairs(G);\n S := vertices(G);\n for i from 1 to nops(S) do;\n for j from 1 to nops(S) do;\n if T[S[i],S[j] ] > 1 and T[S[i],S[j] ] <infinity then\n is_trans := false\n fi;\n od;\n od;\n is_trans;\nend:\nIsTransitive_G(G1);\nR2;\nIsTransitive_G(MakeDigraph(1,2,3,4,R2));\n</pre>\n\nVoc\u00ea deve examinar outras formas de manipular a representa\u00e7\u00e3o gr\u00e1fica das rela\u00e7\u00f5es em Maple. Em particular, depois de ter estudado o Cap\u00edtulo 7, voc\u00ea pode explorar uma variedade de maneiras de manipular gr\u00e1ficos, e ver como as informa\u00e7\u00f5es sobre as rela\u00e7\u00f5es podem ser extra\u00eddos a partir deles.\n\n=== Rela\u00e7\u00f5es representando Usando Matrizes Zero-One ===\nVamos agora considerar a representa\u00e7\u00e3o das rela\u00e7\u00f5es de matrizes zero-um. Para come\u00e7ar, uma vez que estar\u00e1 trabalhando com matrizes, \u00e9 preciso indicar que estaremos usando as fun\u00e7\u00f5es do pacote ''Maple'' '''linalg'''. Especificamente, teremos de usar a fun\u00e7\u00e3o de '''matrix''' (matriz), e as opera\u00e7\u00f5es da matriz relacionados, do pacote '''linalg'''.\n\n<pre>\nwith(linalg):\n</pre>\n\nAgora, n\u00f3s fornecemos um procedimento Maple, que encontra a representa\u00e7\u00e3o de matriz zero-um de uma rela\u00e7\u00e3o, dados os pares ordenados nesta rela\u00e7\u00e3o. O pseudoc\u00f3digo para este algoritmo \u00e9 como se segue;\n\n<pre>\n\\item{Entrada: o conjunto R e dom\u00ednio D.}\n\\item{Para cada par (i,j) em D, que determinar se a (i,j) est\u00e1 em R.}\n\\item{Se o par est\u00e1 em R, colocamos uma entrada 1 na posi\u00e7\u00e3o que representa (i,j) na matriz M. Caso contr\u00e1rio, coloca-se um 0 na posi\u00e7\u00e3o que representa (i,j) na matriz M.}\n\\item{Sa\u00edda: M.}\n</pre>\n\nTraduzindo esse algoritmo para o Maple, o c\u00f3digo resulta no seguinte procedimento.\n\n<pre>\nMakeMatrix := proc (R::set, D::set)\n local i, j, L;\n L := [];\n for i from 1 to nops(D) do\n for j from 1 to nops(D) do\n if member([i,j],R) then\n L := [op(L), 1] else L := [op(L),0];\n fi;\n od;\n od;\n evalm(matrix(nops(D), nops(D), L));\nend:\n</pre>\n\nEm seguida, vamos converter as rela\u00e7\u00f5es definidas no in\u00edcio deste cap\u00edtulo de sua forma conjunto para representa\u00e7\u00e3o de forma zero-um.\n\n<pre>\nm1:=MakeMatrix(R1,1,2,3,4);\nm2:=MakeMatrix(R2,1,2,3,4);\nm3:=MakeMatrix(R3, 1,2,3,4);\nm4:=MakeMatrix(R4,1,2,3,4);\n</pre>\n\nAgora que temos as representa\u00e7\u00f5es de zero-um da matriz dessas rela\u00e7\u00f5es, podemos usar essas matrizes para determinar se as rela\u00e7\u00f5es s\u00e3o reflexivas, sim\u00e9tricas e/ou antissim\u00e9tricas. Nesta forma, \u00e9 um pouco mais f\u00e1cil para determinar se uma a rela\u00e7\u00e3o tem alguma destas propriedades. Aqui, por exemplo, \u00e9 um procedimento em Maple que determina se uma rela\u00e7\u00e3o \u00e9 reflexiva, utilizando a sua representa\u00e7\u00e3o matricial de zero-um.\n\n<pre>\nIsReflexive_M:= proc(M::matrix)\n local i, is_reflex;\n is_reflex := true;\n for i from 1 to coldim(M) do\n if M[i,i] = 0 then\n is_reflex := false;\n fi;\n od;\n is_reflex;\nend:\nIsReflexive_M(m1);\nIsReflexive_M(m3);\n</pre>\n\nAqui tamb\u00e9m est\u00e3o as vers\u00f5es de matriz para '''IsSymmetric''' e '''IsAntiSymmetric'''.\n\n<pre>\nIsSymmetric_M := proc(M::matrix)\n local i,j; # row and column indices\n if rowdim(M) <> coldim(M) then\n RETURN(false);\n fi;\n for i from 1 to rowdim(M) do\n for j from 1 to i-1 do\n if M[i,j] <> M[j,i] then\n RETURN(false);\n fi;\n od;\n od;\n RETURN(true);\nend:\n</pre>\n\nDeve ser quadrada.\nO c\u00f3digo para verificar antissimetria \u00e9 semelhante.\n\n<pre>\nIsAntiSymmetric_M := proc(M::matrix)\n local i,j;\n if rowdim(M) <> coldim(M) then\n RETURN(false);\n fi;\n for i from 1 to rowdim(M) do\n for j from 1 to i - 1 do\n if M[i,j] = 1 and M[i,j] = M[j,i] then\n RETURN(false);\n fi;\n od;\n od;\n RETURN(true);\nend:\n</pre>\n\nMais uma vez, podemos determinar se as rela\u00e7\u00f5es representadas em forma de matriz zero-um s\u00e3o sim\u00e9tricas ou antissim\u00e9tricas.\n\n<pre>\nIsSymmetric_M(m1); IsAntiSymmetric_M(m1);\nIsSymmetric_M(m2); IsAntiSymmetric_M(m2);\nIsSymmetric_M(m4); IsAntiSymmetric_M(m4);\n</pre>\n\n\n== Fecho Computacional de Rela\u00e7\u00f5es ==\nDeterminar o fecho de uma rela\u00e7\u00e3o em Maple pode ser abordado basicamente da mesma forma que abordamos o problema de determinar as propriedades das rela\u00e7\u00f5es. Especificamente, deve implementar algoritmos que utilizam t\u00e9cnicas semelhantes para determina\u00e7\u00e3o das propriedades reflexivas e sim\u00e9tricas, a fim de determinar o fecho dessas propriedades relacionais. O fecho transitivo da rela\u00e7\u00e3o vai exigir mais conhecimento, mas vamos analisar v\u00e1rios m\u00e9todos para determinar o fecho transitivo de uma determinada rela\u00e7\u00e3o.\n\n=== Fecho reflexivo ===\nO algoritmo para calcular o fecho reflexivo de uma rela\u00e7\u00e3o \u00e9 realmente muito simples. N\u00f3s simplesmente definimos cada entrada diagonal em sua representa\u00e7\u00e3o matricial igual a 1. A matriz resultante representa o fecho reflexivo da rela\u00e7\u00e3o.\n\n<pre>\nRefClose := proc(M::matrix)\n local i;\n for i from 1 to coldim(M) do\n M[i,i] := 1;\n od;\n evalm(M);\nend:\n</pre>\n\nAgora usamos '''RefClose''' para encontrar o fecho reflexivo de algumas das rela\u00e7\u00f5es que introduzimos como exemplos no in\u00edcio do cap\u00edtulo.\n\n<pre>\nRefClose(m1); RefClose(m4);\n</pre>\n\n=== Fecho sim\u00e9trico ===\nEm seguida, vamos construir um processo de determina\u00e7\u00e3o do fecho sim\u00e9trico de uma rela\u00e7\u00e3o R. Novamente, usamos a observa\u00e7\u00e3o, a partir da p\u00e1gina 3822, que observa que, se (a,b) \u00e9 um elemento de R, ent\u00e3o (b,a) \u00e9 um elemento do fecho sim\u00e9trico de R. O c\u00f3digo em Maple, o qual \u00e9 semelhante ao fecho reflexivo implementado acima, \u00e9:\n\n<pre>\nSymmClose := proc(M::matrix)\n local i, j;\n for i from 1 to coldim(M) do\n for j from 1 to rowdim(M) do\n if M[i,j] = 1 then\n M[j,i] := 1;\n fi;\n od;\n od;\n evalm(M);\nend:\n</pre>\n\nEste procedimento pode ser usado para localizar o fecho sim\u00e9trico da alguns dos nossos exemplos anteriores, como se segue.\n\n<pre>\nSymmClose(m1); SymmClose(m4);\n</pre>\n\n=== Fecho transitivo ===\nTendo criado os fechos mais simples, das propriedades reflexivas e sim\u00e9tricos, n\u00f3s agora nos concentraremos na implementa\u00e7\u00e3o do fecho transitivo em Maple, que \u00e9 um problema mais dif\u00edcil do que os casos anteriores em termos de complexidade computacional. No texto, h\u00e1 dois algoritmos descritos, ou seja, um fecho transitivo gen\u00e9rico e um algoritmo de Warshall, e ambos ser\u00e3o abordados nesta se\u00e7\u00e3o.\n\nPara implementar o fecho transitivo, precisamos implementar tanto o juntar booleano quanto as opera\u00e7\u00f5es de produto booleanas, previamente introduzido no Cap\u00edtulo 2. Para come\u00e7ar, vamos criar as fun\u00e7\u00f5es auxiliares booleana que nos permitem converter entre zero e um e valores verdadeiro-falso.\n\n<pre>\nwith(linalg):\nint_to_bool(0) := false:\nint_to_bool(1) := true:\nbool_to_int(true) := 1:\nbool_to_int(false) := 0:\n</pre>\n\nEm seguida, vamos construir o booleano se juntar a fun\u00e7\u00e3o, novamente com base no trabalho anterior do cap\u00edtulo 3.\n\n<pre>\nBoolJoin := proc(A::matrix, B::matrix)\n local i, j, C;\n C := matrix(rowdim(A), coldim(A), zeroes);\n for i from 1 to rowdim(A) do\n for j from 1 to coldim(A) do\n C[i,j] := int_to_bool(A[i,j]) or int_to_bool(B[i,j]);\n od;\n od;\n map(bool_to_int,C);\nend:\n</pre>\n\nAp\u00f3s isso, n\u00f3s constru\u00edmos o produto booleano.\n\n<pre>\nBoolProd := proc(A::matrix, B::matrix)\n local i, j, k, C;\n C := matrix(rowdim(A), coldim(B), zeroes);\n for i from 1 to rowdim(A) do\n for j from 1 to coldim(B) do\n C[i,j] := false;\n for k from 1 to coldim(A) do\n C[i,j] := C[i,j]\n or (int_to_bool(A[i,k])\n and int_to_bool(B[k,j]));\n od;\n od;\n od;\n map(bool_to_int, C);\nend:\n</pre>\n\nAgora estamos prontos para come\u00e7ar a aplicar o procedimento para o c\u00e1lculo do fecho transitivo, tal como definido na p\u00e1gina 3877 do texto.\n\n<pre>\nTransClosure := proc(M::matrix)\n local i, A, B;\n A := M;\n B := A;\n for i from 2 to coldim(M) do\n A := BoolProd(A, M);\n B := BoolJoin(B, A);\n evalm(A);\n evalm(B);\n od;\n evalm(B);\nend:\n</pre>\n\nN\u00f3s testamos nosso procedimento de fecho transitivo em um exemplo.\n\n<pre>\nT1 := matrix(3,3,[1,0,1,0,1,0,1,1,0]):\nTransClosure(T1);\n</pre>\n\nEm seguida, vamos examinar como o algoritmo de Warshall compara (em termos de tempo de execu\u00e7\u00e3o de um exemplo simples) para este algoritmo geral que acabamos de implementar. Em primeiro lugar, temos de implementar o algoritmo de Warshall em Maple.\n\n<pre>\nWarshall := proc(M::matrix)\n local i, j, k, W, n;\n W := map(int_to_bool,M);\n n := coldim(M);\n for k from 1 to n do\n for i from 1 to n do\n for j from 1 to n do\n W[i,j] := W[i,j] or (W[i,k] and W[k,j]);\n od;\n od;\n od;\n evalm(map(bool_to_int, W));\nend:\nWarshall(T1);\n</pre>\n\nPodemos comparar estes dois procedimentos em termos de tempo de execu\u00e7\u00e3o usando o comando do tempo no Maple. Mas, devemos notar que esta compara\u00e7\u00e3o em um \u00fanico exemplo n\u00e3o prova nada; ao contr\u00e1rio, ela \u00e9 \u00fatil para ilustrar geralmente os tempos de execu\u00e7\u00e3o para os dois algoritmos que foram implementados. Para fazer essa ilustra\u00e7\u00e3o, vamos criar uma matriz zero-um que opera sobre o conjunto A = {1,2,3,4}.\n\n<pre>\nT2:=matrix(4, 4, [0,0,0,1,1,0,1,0,1,0,0,1,0,0,1,0]);\nst:=time():Warshall(T2):time()-st;\nst:=time():TransClosure(T2):time()-st;\n</pre>\n\nA partir deste exemplo, podemos ver que no algoritmo do Warshall pode ser uma melhoria substancial sobre o m\u00e9todo que utiliza jun\u00e7\u00e3o e produtos booleanos, neste exemplo espec\u00edfico. O leitor \u00e9 encorajado a explorar mais que este.\n\n\n== Rela\u00e7\u00f5es de equival\u00eancia ==\nExaminaremos, nesta se\u00e7\u00e3o, como podemos usar o Maple para calcular com rela\u00e7\u00f5es de equival\u00eancia. H\u00e1 tr\u00eas problemas espec\u00edficos que vamos abordar aqui: como calcular a classe de equival\u00eancia de um elemento, dada uma rela\u00e7\u00e3o de equival\u00eancia em um conjunto; como determinar o n\u00famero de rela\u00e7\u00f5es de equival\u00eancia em um conjunto finito; e, como calcular a rela\u00e7\u00e3o de equival\u00eancia menor que cont\u00e9m uma dada rela\u00e7\u00e3o em algum conjunto finito.\n\nPara come\u00e7ar, vamos primeiro fornecer um teste para uma rela\u00e7\u00e3o estar em uma rela\u00e7\u00e3o de equival\u00eancia. Usando o trabalho que j\u00e1 fizemos, e recordando que uma rela\u00e7\u00e3o de equival\u00eancia \u00e9 simplesmente aquele que \u00e9 reflexiva, sim\u00e9trica e transitiva, o nosso trabalho \u00e9 simples.\n\n<pre>\nIsEqRel := IsTransitive @ IsSymmetric @ IsReflexive;\n</pre>\n\nRecorde-se que, tendo uma rela\u00e7\u00e3o de equival\u00eancia de R, e um membro a do dom\u00ednio de R, a classe de equival\u00eancia de um \u00e9 o conjunto de todos os membros b do dom\u00ednio de R para o qual o par (a,b) pertence a R. Em outras palavras, \u00e9 o conjunto de todos os elementos no dom\u00ednio de R que s\u00e3o R-equivalentes para a. Assim, o algoritmo usado para construir a classe de equival\u00eancia de um \u00e9 muito simples: n\u00f3s apenas iremos pesquisar R procurando todos os pares da forma (a,b), acrescentando cada um desses segundo elemento b para a classe. N\u00e3o precisamos procurar por pares da forma (b,a), porque as rela\u00e7\u00f5es de equival\u00eancia s\u00e3o sim\u00e9tricas. Dada uma rela\u00e7\u00e3o de equival\u00eancia, e um ponto no seu dom\u00ednio, esse procedimento retorna a classe de equival\u00eancia do ponto.\n\n<pre>\nEqClass := proc(R::set, a::anything)\n local i, S;\n S := {};\n for i from 1 to nops(R) do\n if R[i][1] = a then\n S := S union R[i][2];\n fi;\n od;\n RETURN(S);\nend:\nEqClass([0,0],[0,2],[1,0],[1,1], [2,1],[1,2],[0,1], 0);\n</pre>\n\nAgora apresentamos um procedimento que constr\u00f3i todas as rela\u00e7\u00f5es de equival\u00eancia em um determinado conjunto.\n\n<pre>\nDetermineEqClass := proc(A::set)\n local P, Q, S, E, i, j, p;\n S := {};\n E := {};\n for i from 1 to nops(A) do\n for j from 1 to nops(A) do\n S := S union [A[i], A[j] ] ;\n od;\n od;\n P := combinat[powerset](S);\n for p in P do\n if IsSymmetric(p) and IsReflexive(p) and IsTransitive(p) then\n E := E union p;\n fi;\n od;\n RETURN(E);\nend:\nDetermineEqClass(1,2);\nDetermineEqClass(1,2,3);\n</pre>\n\nComo \u00faltima quest\u00e3o a ser analisada nesta se\u00e7\u00e3o, vamos determinar a rela\u00e7\u00e3o de equival\u00eancia menor que cont\u00e9m uma determinada rela\u00e7\u00e3o. O elemento motivador no algoritmo \u00e9 o fato de que precisamos para gerar uma rela\u00e7\u00e3o P contendo a rela\u00e7\u00e3o determinada R tal que P \u00e9 sim\u00e9trica, reflexiva e transitiva. Recordando a se\u00e7\u00e3o sobre fechos, deduzimos a seguinte algoritmo em pseudoc\u00f3digo para determinar a rela\u00e7\u00e3o de equival\u00eancia P contendo a rela\u00e7\u00e3o R:\n\n\n1- Criar o fecho reflexivo da rela\u00e7\u00e3o R; chamam isso de P.\n\n2- Criar o fecho sim\u00e9trico da rela\u00e7\u00e3o P e chamar este Q. Observe que Q ainda \u00e9 reflexiva j\u00e1 que n\u00e3o h\u00e1 elementos foram removidos, assim que todos os pares diagonais (a,a) ainda pertencem ao Q.\n\n3- Criar o fecho transitivo da rela\u00e7\u00e3o Q e devolver o presente como sa\u00edda. Este \u00e9 reflexivo, pela mesma raz\u00e3o, conforme descrito na etapa anterior. Esta rela\u00e7\u00e3o tamb\u00e9m \u00e9 sim\u00e9trica, j\u00e1 que, se (a,b) e (b,c) implica a inclus\u00e3o de um elemento (a,c), em seguida, uma vez que executou o fecho sim\u00e9trico, sabemos que existem elementos (c,b) e (b,a) de modo a que tamb\u00e9m temos o elemento (c,a). Da\u00ed a rela\u00e7\u00e3o final ser\u00e1 transitiva, reflexiva e sim\u00e9trica.\n\n\nN\u00f3s implementamos isso em Maple como a composi\u00e7\u00e3o dos quatro fun\u00e7\u00f5es: '''Warshall''', '''SymmClose''', '''RefClose''', e '''MakeMatrix'''.\n\n<pre>\nEqContainment := Warshall @ SymmClose @ RefClose @ MakeMatrix;\nR2;\nEqContainment(R2, 1,2,3,4);\n</pre>\n\n== Ordenamento parcial e elementos m\u00ednimos ==\nNesta se\u00e7\u00e3o, analisamos ''posets'', ''m\u00e1ximos'' e ''m\u00ednimos'', assim como as ideias de supremo, \u00ednfimo e ordena\u00e7\u00e3o topol\u00f3gica. Vamos explorar esses t\u00f3picos em Maple, e vamos deixar a explora\u00e7\u00e3o dos outros t\u00f3picos desta sec\u00e7\u00e3o para o leitor.\n\nPrimeiro, vamos definir um novo tipo em ''Maple'' para ordens parciais. Para esta parte, vamos considerar uma ordem parcial a ser um conjunto de pares ordenados (um objeto do tipo '''rel''') que satisfaz as tr\u00eas condi\u00e7\u00f5es necess\u00e1rias para uma rela\u00e7\u00e3o a ser uma ordem parcial: reflexividade (''reflexivity''), antissimetria (''antisymmetry'') e transitividade (''transitivity'').\n\n<pre>\n`type/po` := proc(obj)\n type(obj, rel) and IsReflexive(obj)\n and IsAntiSymmetric(obj)\n and IsTransitive(obj);\nend:\n</pre>\n\nIsto ilustra uma outra maneira em que voc\u00ea pode definir novos tipos em Maple, dever\u00e1 a \u00e1lgebra de tipos estruturados revelar-se insuficiente.\n\nEm seguida, vamos construir um procedimento que determina o conjunto de elementos m\u00ednimos de um conjunto parcialmente ordenado. O procedimento a seguir usa dois argumentos: uma ordem de '''R''' parcial, e um subconjunto '''S''' do dom\u00ednio de '''R'''. Ele retorna o conjunto de elementos m\u00ednimos de '''S''' com respeito \u00e0 ordenamento '''R'''.\n\n<pre>\nMinimalElements := proc(R::po, S::set)\n local M, # set of minimal elements of S; returned\n s,t; # indices into S\n if S minus DomainRelation(R) <> {} then\n ERROR(`set must be contained in the domain of the relation`);\n fi;\n M := S;\n for s in S do\n for t in S minus s do\n if member([t,s], R) then\n M := M minus s;\n fi;\n od;\n od;\n RETURN(M);\nend:\nR := DividesRelation(1,2,3,6);\nMinimalElements(R, 1,2,3,6);\nMinimalElements(R, 2,3,6);\n</pre>\n\nNote-se que, pela dualidade, obtemos - quase de gra\u00e7a - uma forma muito simples implementa\u00e7\u00e3o de elementos m\u00e1ximos (''MaximalElements'').\n\n<pre>\nMaximalElements := proc(R::po, S::set)\n MinimalElements(DualRelation(R), S);\nend:\nMaximalElements(R, 1,2,3,6);\nMaximalElements(R, 1,2,3);\n</pre>\n\nEm seguida, vamos construir um procedimento para calcular os elementos m\u00ednimos de um conjunto no que diz respeito a uma determinada ordem parcial, se ele existir. Nosso procedimento ir\u00e1 retornar o valor NULL no caso de o conjunto que tenha nenhum limite m\u00ednimo superior. Vamos realizar em v\u00e1rias etapas. Para fazer isso, primeiro escrevemos um procedimento que ir\u00e1 calcular o conjunto de todos os limites superiores de um subconjunto de um conjunto parcialmente ordenado. Este procedimento, por sua vez, se baseia na sequ\u00eancia de utilidade para determinar se um determinado elemento \u00e9 um limite superior para um conjunto.\n\n<pre>\nIsUpperBound := proc(R::po, S::set, u::anything)\n local s; # index into S\n</pre>\nverifica\u00e7\u00e3o de sanidade:\n<pre>\n if not member(u, DomainRelation(R)) then\n ERROR(`bad arguments`);\n fi;\n for s in S do\n if not member([s, u], R) then\n RETURN(false);\n fi;\n od;\n RETURN(true);\nend:\nUpperBounds := proc(R::po, S::set)\n local U, # set of upper bounds of S; returned\n DomR, # domain of R\n d; # index into DomR\n DomR := DomainRelation(R);\n</pre>\nverifica\u00e7\u00e3o de erros:\n<pre>\n if S minus DomR <> {} then\n ERROR(`set must be contained in the domain of the relation`);\n fi;\n U := {};\n for d in DomR do\n if IsUpperBound(R, S, d) then\n U := U union d;\n fi;\n od;\n RETURN(U);\nend:\n</pre>\n\nEm seguida, \u00e9 conveniente introduzir um procedimento chamado '''mub''' que calcula o conjunto de limites m\u00ednimos da cota superior de um subconjunto de um conjunto parcialmente ordenado.\n\n<pre>\nmub := proc(R::po, S::set)\n MinimalElements(R, UpperBounds(R, S));\nend:\n</pre>\n\nAgora, para completar a tarefa em m\u00e3os, precisamos apenas verificar se mub retorna uma \u00fanica coisa. Se assim for, ent\u00e3o o supremo (por defini\u00e7\u00e3o); caso contr\u00e1rio, n\u00e3o faz, e n\u00f3s devolver o valor NULL.\n\n<pre>\nlub := proc(R::po, S::set)\n local M; # set of minimal upper bounds of S\n M := mub(R, S);\n if nops(M) <> 1 then\n RETURN(NULL);\n fi;\n RETURN(op(M));\nend:\n</pre>\n\nA ordena\u00e7\u00e3o topol\u00f3gica \u00e9 usada para produzir, a partir de uma dada ordem parcial, uma ordem linear no seu dom\u00ednio que \u00e9 compat\u00edvel com o mesmo. Por exemplo, a ordem natural no conjunto {1,2,3,6} \u00e9 uma ordem linear que \u00e9 compat\u00edvel com a ordem parcial de divisibilidade. (de fato, isso \u00e9 verdade para a rede de divisores de qualquer inteiro positivo uma vez que, se ''m'' e ''n'' s\u00e3o inteiros positivos, em seguida, ''m'' divide ''n'' somente se ''m'' \u00e9 menor ou igual ''n''). Tendo implementado supremo e elementos m\u00ednimos, podemos agora criar um procedimento ordena\u00e7\u00e3o topol\u00f3gica que usa o algoritmo ''MinimalElements'' acima.\n\n<pre>\nTopSort := proc(R::po, T::set)\n local i, k, S, A;\n k := 1;\n S := T;\n A := [];\n while S <> {} do\n A := [op(A), MinimalElements(R, S)[1] ];\n S := S minus A[k];\n k := k+1;\n od;\n A;\nend:\nR := DivisorLattice(12);\nTopSort(R, DomainRelation(R));\nR := DivisorLattice(2*3*5);\nTopSort(DualRelation(R), DomainRelation(R));\nR := DivisorLattice(2*3*5*7);\nTopSort(R, numtheory[divisors](2*3*7));\n</pre>\n\n== Grades ==\nNesta se\u00e7\u00e3o, vamos olhar para o problema de determinar se uma ordem parcial \u00e9 reticulada. A abordagem que devemos tomar \u00e9 um bom exemplo de ''top down programming'' (programa\u00e7\u00e3o de cima para baixo).\n\nPara que possamos construir alguma exemplo interessante, vamos introduzir uma nova fun\u00e7\u00e3o para produzir exemplos de uma boa classe de reticulados.\n\n<pre>\nDivisorLattice := proc(n::posint)\n DividesRelation(numtheory[divisors](n));\nend:\n</pre>\n\nO procedimento '''divisors''', do pacote '''numtheory''', retorna o conjunto de divisores positivos de seu argumento inteiro. Usamos o procedimento '''DividesRelation''', constru\u00eddo no in\u00edcio deste cap\u00edtulo, para criar a rela\u00e7\u00e3o de divis\u00e3o neste conjunto.\n\n<pre>\ntype(DivRel(6), po);\n</pre>\n\nQueremos escrever um programa em ''Maple'' que ir\u00e1 determinar se uma ordem parcial (finita) \u00e9 um reticulado. Agora, uma ordem de ''R'' parcial \u00e9 um reticulado, se, e somente se, \u00e9 tanto um ''meet semilattice'' quanto um ''join semilattice''. A primeira \u00e9 uma ordem parcial em que cada par de elementos tem um encontro - um limite m\u00ednimo superior ou supremo; Segundo, \u00e9 aquele em que a dupla condi\u00e7\u00e3o for satisfeita: cada par de elementos tem um supremo, ou um \u00ednfimo. Ent\u00e3o, o nosso teste para uma ordem parcial deve ser um reticulado, apenas precisa de verificar se estas duas condi\u00e7\u00f5es s\u00e3o satisfeitas.\n\n<pre>\nIsLattice := proc(R::po)\n IsMeetSemiLattice(R) and IsJoinSemiLattice(R);\nend:\n</pre>\n\nEm seguida, usamos o fato de que uma ordem parcial \u00e9 um ''meet semilattice'', se, e somente se, a sua rela\u00e7\u00e3o dual \u00e9 um ''join semilattice''.\n\n<pre>\nIsJoinSemiLattice := IsMeetSemiLattice @ DualRelation;\n</pre>\n\nAgora o verdadeiro trabalho come\u00e7a; devemos codificar a fun\u00e7\u00e3o '''IsMeetSemiLattice'''. Para isso, \u00e9 preciso testar se, dada a rela\u00e7\u00e3o ''R'', cada par ''a'', ''b'' no dom\u00ednio da ''R'' tem um supremo com rela\u00e7\u00e3o a ''R''. Uma observa\u00e7\u00e3o que simplifica a nossa tarefa consideravelmente \u00e9 que, uma vez que estamos a lidar apenas com rela\u00e7\u00f5es finitas, basta verificar que cada par tem um limite superior comum.\n\n<pre>\nIsMeetSemiLattice := proc(R::po)\n local DomR, # the domain of R\n r,s; # indices into R\n DomR := DomainRelation(R);\n for r in DomR do\n for s in DomR do\n if lub(R, r, s) = NULL then\n RETURN(false);\n fi;\n od;\n od;\nRETURN(true);\nend:\n</pre>\n\nFinalmente, todas as sub-rotinas que est\u00e3o fazendo o nosso programa '''IsLattice''' est\u00e3o completas, e podemos test\u00e1-lo em alguns exemplos. O seguinte resultado n\u00e3o deve vir com qualquer surpresa.\n\n<pre>\nIsLattice(DivisorLattice(24));\n</pre>\n\nMas, observe o que acontece quando n\u00f3s constru\u00edmos a rela\u00e7\u00e3o ''divides'' em todos os inteiros no conjunto {1,2,3, ..., 24}.\n\n<pre>\nIsLattice(DividesRelation(seq(i, i=1..24)));\n</pre>\n\n== Rela\u00e7\u00f5es de abrang\u00eancia ==\n\u00c9 muito ineficiente, em geral, armazenar todos os pares em uma rela\u00e7\u00e3o de ordem parcial. H\u00e1 uma representa\u00e7\u00e3o m\u00ednima de uma ordem parcial, a partir do qual toda a rela\u00e7\u00e3o pode ser reconstru\u00edda, denominado sua rela\u00e7\u00e3o de abrang\u00eancia. (Isto n\u00e3o \u00e9 abordado no texto, mas ser\u00e1 \u00fatil para n\u00f3s na se\u00e7\u00e3o seguinte, al\u00e9m de ser um tema importante por si s\u00f3). A rela\u00e7\u00e3o de abrang\u00eancia de uma ordem parcial n\u00e3o \u00e9 em si uma ordem parcial. \u00c9 um subconjunto m\u00ednimo da ordem parcial a partir do qual todos os outros pares de rela\u00e7\u00e3o podem ser deduzidos. Seja ''R'' uma ordem parcial em um conjunto ''S''. Dizemos que um elemento ''b'' em ''S'' abrange um elemento ''a'' em ''S'' se (''a'', ''b'') pertence a ''R'', e ''a''\u2260''b'', mas n\u00e3o h\u00e1 elemento ''s'' em ''S'' para o qual ambos (''a'', ''s'') e (''s'', ''b'') pertencem a ''R''. Em outras palavras, ''b'' abrange ''a'' se ''b'' \u00e9 maior do que ''a'', e se n\u00e3o h\u00e1 nada entre eles. A rela\u00e7\u00e3o de abrang\u00eancia de uma ordem ''R'' parcial \u00e9 a rela\u00e7\u00e3o ''C'' de ''S'' que consiste naqueles pares (''a'', ''b'') em ''R'' para o qual ''b'' abrange ''a''. Como um exemplo simples, considere o conjunto {1,2,3,4} ordenado pela magnitude. Sua rela\u00e7\u00e3o de abrang\u00eancia \u00e9 o conjunto {(1,2), (2,3), (3,4)}. Todos os outros pares, tais como (1,3), pode ser deduzida a partir da rela\u00e7\u00e3o de abrang\u00eancia, usando transitividade: 1 \u2264 2 \u2264 3, e, portanto, uma 1 \u2264 3 (isto \u00e9, o par (1,3) est\u00e1 na rela\u00e7\u00e3o). Rela\u00e7\u00f5es de abrang\u00eancia tamb\u00e9m s\u00e3o importantes porque \u00e9 a rela\u00e7\u00e3o de abrang\u00eancia de uma ordem parcial que \u00e9 desenhada num diagrama de Hasse, em vez de toda a rela\u00e7\u00e3o.\n\nNesta se\u00e7\u00e3o, n\u00f3s fornecemos um procedimento em Maple para calcular a rela\u00e7\u00e3o cobrindo de uma ordem parcial. Em primeiro lugar, precisamos de um teste para saber se um determinado elemento cobre outro.\n\n<pre>\nCovers := proc(R::po, a, b)\n local u; # index into Dom(R)\n if a = b then\n RETURN(false);\n fi;\n if not member([a,b], R) then\n RETURN(false);\n fi;\n for u in DomainRelation(R) minus a, b do\n if member([a,u], R) and member([u,b], R) then\n RETURN(false);\n fi;\n od;\n RETURN(true);\nend:\n</pre>\n\nAgora podemos construir a rela\u00e7\u00e3o cobrindo de uma ordem parcial usando o seguinte procedimento em Maple:\n\n<pre>\nCoveringRelation := proc(R::po)\n local C, # covering relation; returned\n DomR, # the domain of R\n r,s; # indices into DomR\n DomR := DomainRelation(R);\n C := {};\n for r in DomR do\n for s in DomR do\n if Covers(R, r, s) then\n C := C union [r,s];\n fi;\n od;\n od;\n RETURN(C);\nend:\n</pre>\n\nVejamos alguns pequenos exemplos.\n\n<pre>\nCoveringRelation(DivisorLattice(6));\nCoveringRelation(DividesRelation(1,3,5,7,11,13,17));\n</pre>\n\n== Diagramas de Hasse ==\nA rela\u00e7\u00e3o de abrang\u00eancia de uma ordem parcial \u00e9 muitas vezes usada para representar uma ordem parcial. N\u00f3s j\u00e1 mencionamos que \u00e9 mais eficiente (o que exige menos mem\u00f3ria), mas tamb\u00e9m \u00e9 usada para representar uma ordem parcial graficamente, no sentido de que o diagrama de Hasse \u00e9 apenas uma representa\u00e7\u00e3o visual da rela\u00e7\u00e3o de abrang\u00eancia da ordem parcial. N\u00f3s j\u00e1 temos a maioria das ferramentas de que precisamos para fazer uma primeira tentativa de uma representa\u00e7\u00e3o visual de uma ordem parcial. As ferramentas de visualiza\u00e7\u00e3o no pacote '''networks''' tornam relativamente f\u00e1cil de desenhar uma imagem gr\u00e1fica de uma ordem parcial. N\u00f3s simplesmente calculamos sua rela\u00e7\u00e3o de abrang\u00eancia, e depois a convertemos para um gr\u00e1fico e a exibimos como no seguinte procedimento.\n\n<pre>\nHasseDiagramFirstTry := proc(R::po)\n local C;\n C := CoveringRelation(R);\n networks[draw](MakeDigraph(DomainRelation(C),C));\nend:\n</pre>\n\nPor exemplo, aqui est\u00e1 uma imagem do divisor reticulado de 2100.\n\n<pre>\nHasseDiagramFirstTry(DivisorLattice(2*3*5*7));\n</pre>\n\nInfelizmente, esta sofre da desvantagem de n\u00e3o desenhar diagramas Hasse na forma tradicional, com o fim de os elementos representados pelo fluxo do diagrama. Para corrigir isso, precisamos fazer um pouco de codifica\u00e7\u00e3o. A ideia \u00e9 organizar os elementos de um ordenado parcialmente definida em n\u00edveis, e ent\u00e3o usar a op\u00e7\u00e3o '''Linear''' para rotina '''draw''' para formar o diagrama mais apropriadamente. V\u00e1rias rotinas de servi\u00e7os p\u00fablicos s\u00e3o necess\u00e1rias. Esta fun\u00e7\u00e3o \u00e9 usada para verificar se um elemento \u00e9 um \u00e1tomo; isto \u00e9, que n\u00e3o tem precedentes. Destina-se a ser utilizado apenas com rela\u00e7\u00f5es de abrang\u00eancia '''CR'''. O argumento extra '''D''' \u00e9 necess\u00e1rio para que possamos localiz\u00e1-lo mais tarde.\n\n<pre>\nIsAtom := proc(CR::rel, D::set, a::anything)\n local d;\n for d in D do\n if member([d,a], CR) then\n</pre>\nencontrou um predecessor:\n<pre>\n RETURN(false);\n fi;\n od;\n</pre>\ndeve ser um \u00e1tomo:\n<pre>\n RETURN(true);\nend:\n</pre>\n\nN\u00f3s usamos isso no pr\u00f3ximo procedimento, que determina todos os \u00e1tomos em um determinado subconjunto de uma rela\u00e7\u00e3o de cobertura.\n\n<pre>\nAtoms := proc(CR::rel, D::set)\n local A, # set of atoms; returned\n d; # index into D\n A := {};\n for d in D do\n if IsAtom(CR, D, d) then\n A := A union d;\n fi;\n od;\n RETURN([op(A)]);\nend:\n</pre>\n\nAqui \u00e9 a nossa nova implementa\u00e7\u00e3o do Diagrama de Hasse. A maior parte do novo trabalho envolve a disposi\u00e7\u00e3o dos elementos do conjunto parcialmente ordenado em uma sequ\u00eancia de n\u00edveis para passar para '''Linear''' na rotina '''draw'''.\n\n<pre>\nHasseDiagram := proc(R::po)\n local L, C, G, A, D;\n C := CoveringRelation(R);\n D := DomainRelation(C); # = DomainRelation(R)\n G := MakeDigraph(D, R);\n L := NULL;\n while D <> {} do\n A := Atoms(C, D);\n L := L, sort(A);\n D := D minus op(A);\n od;\n networks[draw](Linear(L), G);\nend:\n</pre>\n\nEla produz imagens muito melhores, com o fluxo, da esquerda para a direita, seguindo aproximadamente os elementos crescentes do conjunto parcialmente ordenado.\n\n<pre>\nHasseDiagram(DivisorLattice(4));\nHasseDiagram(DivisorLattice(6));\nHasseDiagram(DivisorLattice(81));\n</pre>\n\nOs dois seguintes s\u00e3o especialmente bonitos!\n\n<pre>\nHasseDiagram(DivisorLattice(2*3*5*7));\nHasseDiagram(DivisorLattice(2*3*5*2));\n</pre>\n\n== C\u00e1lculos e explora\u00e7\u00f5es ==\nNesta se\u00e7\u00e3o, vamos explorar como o ''Maple'' pode ser usado para resolver as quest\u00f5es 1, 4 e 5 da sec\u00e7\u00e3o c\u00e1lculos e explora\u00e7\u00f5es.\n\n1- Exibir todas as diferentes rela\u00e7\u00f5es em um conjunto com 4 elementos.\n\n'''Solu\u00e7\u00e3o:'''\n\nComo de costume, Maple \u00e9 demasiado poderoso para resolver somente uma \u00fanica inst\u00e2ncia do problema geral sugerido por esta quest\u00e3o. N\u00f3s fornecemos aqui um procedimento muito simples que ir\u00e1 calcular todas as rela\u00e7\u00f5es em qualquer conjunto finito.\n \n<pre>\nAllRelations := proc(S::set)\n local s, t, # indices into S\n C; # Cartesian product SxS\n C := {};\n for s in S do\n for t in S do\n C := C union [s,t];\n od;\n od;\n combinat[powerset](C);\nend:\n</pre>\n\nN\u00f3s agora testar o nosso procedimento em um conjunto menor, de modo a manter a sa\u00edda de um comprimento razo\u00e1vel. O leitor \u00e9 convidado para determinar o tempo de execu\u00e7\u00e3o e o comprimento de sa\u00edda para o processo, quando o conjunto de entrada tem cardinalidade 4 ou 5. Tenha em mente que existem <math>2^{n^{2}}</math> rela\u00e7\u00f5es em um conjunto com n membros.\n\n<pre>\nAllRelations(1,2);\n</pre>\n\n2- Determine quantas rela\u00e7\u00f5es transitivo existem em um conjunto com ''n'' elementos para todos os inteiros positivos ''n'' com ''n'' \u2264 7.\n\n'''Solu\u00e7\u00e3o:'''\n\nVamos construir cada poss\u00edveis <math>N x N</math> da matriz zero-um, usando um algoritmo semelhante ao de contagem bin\u00e1ria. O pseudoc\u00f3digo \u00e9:\n \n1- Para cada valor de 1 at\u00e9 <math>2^{(n ^{2})}</math>, criamos uma lista que \u00e9 a representa\u00e7\u00e3o de base 2 desse inteiro.\n \n2- N\u00f3s criamos uma matriz M com elementos sendo a lista de valores. Estes s\u00e3o todos os poss\u00edveis <math>n^{2}</math> de matriz zero-um (o leitor pode provar esta afirma\u00e7\u00e3o).\n \n3- Avaliar o fechamento transitivo de cada uma das matrizes que criamos, e retornar o conjunto de fechos transitivos dessas matrizes.\n \nA implementa\u00e7\u00e3o \u00e9 como se segue:\n\n<pre>\nFindTransitive := proc(S::set)\n local i, j, T, P;\n P := {};\n for i from 0 to 2^(nops(S)^2)-1 do\n T := convert(i, base, 2);\n while nops(T) < nops(S)^2 do\n T := [op(T), 0];\n od;\n P := P union matrix(nops(S), nops(S), T);\n od;\n P;\nend:\n</pre>\n\nMais uma vez, utilizamos o nosso processo em valores relativamente pequenos (devido ao comprimento da sa\u00edda), e deixamos a explora\u00e7\u00e3o adicional para o leitor.\n\n<pre>\nP := FindTransitive(1,2):\nQ := {}:\nfor i from 1 to nops(P) do\n Q := Q union Warshall(P[i]):\nod:\nQ;\n</pre>\n\n3- Encontre o fecho transitivo de uma rela\u00e7\u00e3o em um conjunto com pelo menos 200 elementos.\n\n'''Solu\u00e7\u00e3o:'''\n\nVamos gerar aleatoriamente uma matriz zero-um com dimens\u00e3o 10x10, e em seguida, aplicar o algoritmo de \\textbf{Warshall} para deduzir o fecho transitivo matriz.\n \nPara gerar uma matriz zero-um aleat\u00f3ria, usamos a fun\u00e7\u00e3o '''randmatrix''' do pacote '''linalg''', e fornecer seu terceiro argumento, opcional com um procedimento que gera uma sequ\u00eancia aleat\u00f3ria 0's (zero) e 1's (uns). Em seguida, aplicamos o algoritmo de '''Warshall''' a esta matriz aleat\u00f3ria, obtendo o resultado. Aqui, para economizar espa\u00e7o, podemos aplicar este procedimento para uma matriz de 10x10 como um exemplo.\n\n<pre>\nQ := randmatrix(10, 10, entries=rand(2));\nWarshall(Q);\n</pre>\n\n== Refer\u00eancias ==\n[http://www.mhhe.com/math/advmath/rosen/r5/student/ch07/maple.html Maple: Chapter 7. Relations]"
}
]
}
}
}
}