relation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Relation (이항관계)\n",
    "\n",
    "여기서는 이항관계만을 다루므로 아래에서 이항관계 대신 짧게 \"관계\"(relation)라고 줄여 쓰기도 하겠다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 관계의 정의\n",
    "$R$이 집합 $V$에 대한 이항관계임을 수학에서 쓰는 표기로는 다음과 같이 나타낼 수 있다.\n",
    "  * $R$이 $V\\times V$의 부분집합이라는 뜻에서\n",
    "    $$R \\subset V\\times V$$\n",
    "  * $R$이 $V\\times V$의 멱집합(모든 부분집합의 집합)의 원소라는 뜻에서\n",
    "    $$R \\in \\wp(V) \\quad \\text{또는} \\quad R \\in 2^V$$    \n",
    "\n",
    "$(x,y)\\in R$라는 집합 원소 표기 대신 $x\\,R\\,y$라로 중위(infix) 표기법을 자주 쓴다.\n",
    "\n",
    "이항관계를 진리값(`False` 또는 `True`)을 돌려주는 함수 즉 $V\\times V \\to 2$ 또는 $V\\times V \\to \\textsf{Bool}$ 타입의 함수로 생각할 수도 있다.\n",
    "이항관계를 정의하는 집합에 들어 있는 원소에 대해서는 `True`를 돌려주고 들어있지 않은 함수에 대해서는 `False`를 돌려주는 함수를 생각해 보라."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  관계의 합성\n",
    "이항관계의 합성은 함수의 합성과 비슷하다.\n",
    "두 이항관계 $R_1$과 $R_2$의 합성은 함수 합성과 마찬가지 기호를 써서 $R_1 \\circ R_2$와 같이 표현하며 그 정의는 다음과 같다.\n",
    "\n",
    "  $$ R_1 \\circ R_2 = \\{(x,z) \\mid (x,y) \\in R_1, (y,z) \\in R_2\\} $$\n",
    "\n",
    "또는 중위 표기법을 써서 나타낸다면\n",
    "\n",
    "  $$ R_1 \\circ R_2 = \\{(x,z) \\mid x\\mathop{R_1}y,~ y\\mathop{R_2}z\\} $$\n",
    "\n",
    "\n",
    "이렇게 기존의 두 이항관계를 합성해 만든 이항관계를 합성관계(compsite relation)라고 부르기도 한다.\n",
    "\n",
    "예를 들어\n",
    "$R_1 = \\{(a,b),(c,d)\\}$\n",
    "이고\n",
    "$R_2 = \\{(b,c),(d,b)\\}$\n",
    "이면\n",
    "$R_1 \\circ R_2 = \\{(a,c),(c,b)\\}$가 된다."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 같은 관계끼리 합성\n",
    "합성관계 중에서도 특히 같은 관계끼리 합성한 $R \\circ R$을 $R^2$와 같이 표기한다.\n",
    "예컨대 $R=\\{(a,b),(b,c)\\}$이면 $R \\circ R=\\{(a,c)\\}$가 된다.\n",
    "\n",
    "일반적으로 같은 관계를 여러 번 반복해 합성한 관계들을 다음과 같이 표기한다. \n",
    "$$\n",
    "\\begin{array}{l}\n",
    "R^1 = R \\\\\n",
    "R^2 = R \\circ R \\\\\n",
    "R^3 = R \\circ R \\circ R \\\\\n",
    "R^4 = R \\circ R \\circ R \\circ R \\\\\n",
    "R^5 = R \\circ R \\circ R \\circ R \\circ R \\\\\n",
    "\\vdots \\\\\n",
    "~\n",
    "\\end{array}\n",
    "$$\n",
    "위를 수학적귀납법스럽게 혹은 점화식처럼 공식으로 정리하면 다음과 같다.\n",
    "$$\n",
    "\\begin{array}{l}\n",
    "R^1 = R \\\\\n",
    "R^{n} = R \\circ R^{n-1} \\qquad (n>1)\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "\n",
    "$R^0$라는 표기법을 쓰기도 한다. $R^0$는 실제로는 $R$에 관계없이 $V$만으로 정의되는 집합이다.\n",
    "$$\n",
    "R^0 = \\{ (x,x) \\mid x\\in V \\}\n",
    "$$\n",
    "\n",
    "$R^{-1}$이라는 표기법도 쓰는데 이는 $R$의 역관계이다.\n",
    "$$\n",
    "R^{-1} = \\{ (y,x) | (x,y)\\in R \\}\n",
    "$$\n",
    "\n",
    "참고로 유한집합 $V$에 대해 정의된 이항관계는 방향그래프에 해당한다. 방향그래프에서 점으로 나타나는 vertex의 집합이 $V$에 해당하며 화살표로 나타나는 edge의 집합이 $R$에 해당한다. 즉 $xRy$ 는 $x$ 에서 $y$ 로 가는 화살표가 있다는 뜻. 이런 관계를 보고 방향그래프를 그림으로 그릴 수 있고 방향그래프 그림을 보고 집합으로 옮겨 쓸 수도 있다. 방향그래프와 연관지어 생각하면 $R^k$를 직관적으로 이해할 수 있다. $R^k$는 화살표를 따라 $k$ 걸음만큼 갈 수 있는 모든 시작점과 도착점의 관계인 것이다. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 관계의 성질\n",
    "  * reflexive (반사): 모든 $x\\in V$에 대해, $xRx$\n",
    "  * symmetric (대칭): 모든 $x,y\\in V$에 대해, $xRy$ 이면 $yRx$\n",
    "      * 대표적인 대칭관계의 예로는 \"배우자\" 관계를 들 수 있다. 남편이 아내의 배우자라면 아내도 남편의 배우자가 된다.\n",
    "  * transitive (전이, 추이): 모든 $x,y,z\\in V$에 대해, $xRy$이고 $yRz$이면 $xRz$ \n",
    "      * 대표적인 전이관계의 예로는 \"자손\" 관계를 들 수 있다. 내가 할아버지의 자손이고 할아버지가 고조할아버지의 자손이므로 나도 고조할아버지의 자손이다.\n",
    "\n",
    "위 세 성질을 한꺼번에 만족하면 equlvalence (동치) 관계이다.\n",
    "즉 $R$이 동치관계라는 뜻은, $R$이 반사관계이면서 전이관계이면서 대칭관계이기도 하다는 말이다.\n",
    "\n",
    "\n",
    "## 관계의 Closure (닫힘, 폐포, 폐쇄)\n",
    "어떤 관계로부터 관심있는 *무슨무슨* 성질을 만족하도록 최소한으로 확장된 관계를 $R$의 *무슨무슨* closure라고 한다.\n",
    "\n",
    "$R$의 *무슨무슨* closure를 $R'$이라고 이름붙이자.\n",
    "이 때 $R'$의 정의는 다음과 같다.\n",
    "  1. $R \\subset R' \\quad$ (즉, R을 포함해야 한다) \n",
    "  1. $R$은 *무슨무슨* 관계 (즉, R이 *무슨무슨* 성질을 만족) \n",
    "  1. 위 두 조건을 동시에 만족하는 가장 작은 집합\n",
    "\n",
    "예컨대,\n",
    "$$V = \\{a,b,c,d\\}$$\n",
    "$$R=\\{(a,b),(b,c)\\}$$\n",
    "이라고 하고 $R$ 의 여러가지 closure 들을 생각해 보자. \n",
    "\n",
    "### reflexive closure\n",
    "$R=\\{(a,b),(b,c)\\}$의 reflexive closure는 다음과 같다.\n",
    "$$\\{(a,b),(b,c),(a,a),(b,b),(c,c),(d,d)\\}$$\n",
    "여기에다 $(c,d)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자.\n",
    "$$\\{(a,b),(b,c),(a,a),(b,b),(c,c),(d,d),(c,d)\\}$$\n",
    "이 관계도 $R$을 포함하는 reflexive relation이기는 하나 $R$의 reflexive closure는 될 수 없다.\n",
    "왜냐하면 $R$을 포함하면서도 refexive인 그보다 더 작은 집합이 따로 있기 때문이다.\n",
    "\n",
    "일반적으로 reflexive closure를 계산하는 방법은 원래의 관계에 $R^0$를 추가한 합집합을 구하면 된다.\n",
    "즉, $R$의 reflexive closure는 $R\\cup R^0$이다.\n",
    "\n",
    "### symmetric closure\n",
    "$R=\\{(a,b),(b,c)\\}$의 symmetric closure는 다음과 같다. $$\\{(a,b),(b,c),(b,a),(c,b)\\}$$\n",
    "여기에다 $(a,a)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자.\n",
    "$$\\{(a,b),(b,c),(b,a),(c,b),(a,a)\\}$$\n",
    "이 관계도 $R$ 을 포함하는 symmetric relation이기는 하나 $R$의 symmetric closure는 될 수 없다.\n",
    "왜냐하면 $R$ 을 포함하면서도 symmetric인 그보다 더 작은 집합이 따로 있기 때문이다.\n",
    "\n",
    "일반적으로 symmetric closure를 계산하는 방법은 원래의 관계에 $R^{-1}$를 추가한 합집합을 구하면 된다.\n",
    "즉, $R$의 reflexive closure는 $R\\cup R^{-1}$이다.\n",
    "\n",
    "### transitive closure\n",
    "$R=\\{(a,b),(b,c)\\}$의 transitive closure는 다음과 같다. $$\\{(a,b),(b,c),(a,c)\\}$$\n",
    "여기에다 $(a,a)$를 하나 더 원소로 추가한 또다른 관계를 생각해 보자.\n",
    "$$\\{(a,b),(b,c),(a,c),(a,a)\\}$$\n",
    "이 관계도 $R$ 을 포함하는 transtive relation이기는 하나 $R$의 transitive closure는 될 수 없다.\n",
    "왜냐하면 $R$ 을 포함하면서도 transitive인 그보다 더 작은 집합이 따로 있기 때문이다.\n",
    "\n",
    "일반적으로 transitive closure를 구하는 방법은 다음과 같이 정의되는 $R^+$를 계산하면 된다.\n",
    "$$R^+ = R^1\\cup R^2\\cup R^3 \\cdots = \\bigcup_{k \\in \\mathbb{Z}^{+}}R^k$$\n",
    "$V$가 유한집합인 경우에는 계산할 수 있다. 계산방법에 대해서는 Haskell 프로그램으로 작성한 예시가 뒷부분에 나온다.\n",
    "\n",
    "### reflexive transitive closure\n",
    "reflexive와 transitive 두 성질을 동시에 만족하는 closure이다.\n",
    "$R$ 의 reflexive transitive closure는 일단 transitive closure를 구한 뒤 그것의 reflexive closure를 구해주면 된다.\n",
    "즉, $R^0 \\cup R^+$를 구하면 되는데 이것을 $R^{*}$ 라고 표기하기도 한다. 즉,\n",
    "$$R^* = R^0 \\cup R^1 \\cup R^2 \\cup R^3 \\cdots = \\bigcup_{k\\in\\mathbb{N}}R^k = R^0 \\cup R^+$$\n",
    "\n",
    "이것 말고도 다른 두 성질의 조합에 대한 closure를 생각할 수 있다.\n",
    "예를 들면 reflexive symmetric closure라던가 symmetric transtive closure라던가.\n",
    "\n",
    "### equivalence closure\n",
    "reflexive symmetric transitive closure에 해당한다. $R^*$를 구한 다음 그것의 symmetric closure를 구하면 된다.\n",
    "즉, $R$ 의 equivalence closure는 $R^* \\cup (R^*)^{-1}$ 이다.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "아래에서는 유한한 $V$ 에 대한 이항관계 $R$ 의 transitive closure 즉 $R^+$ 를 구하는 예시를 보여준다.\n",
    "계산하는 방법은 아래 $R^+$의 부분집합 공식에서 n을 1부터 하나씩 늘려가보면서 더 이상 집합의 크기가 늘어나지 않고 변화가 없을 때까지 반복하면 된다.\n",
    "$$\\bigcup_{k=1..n} R^n$$ "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "v = ['a','b','c','d']\n",
    "\n",
    "reflexive  r = and [elem (x,x) r | x<-v]\n",
    "symmetric  r = and [elem (y,x) r | (x,y)<-r]\n",
    "transitive r = and [elem (x,z) r | (x,y1)<-r, (y2,z)<-r, y1==y2]\n",
    "\n",
    "equivalence r = and [reflexive r, transitive r, symmetric r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r1 = [('a','b'),('b','c'),('c','d')]\n",
    "r2 = [('a','b'),('b','c'),('c','d'),('d','b')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><div class=\"suggestion-name\" style=\"clear:both;\">Redundant list comprehension</div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Found:</div><div class=\"highlight-code\" id=\"haskell\">[x | x <- v]</div></div><div class=\"suggestion-row\" style=\"float: left;\"><div class=\"suggestion-warning\">Why Not:</div><div class=\"highlight-code\" id=\"haskell\">v</div></div>"
      ],
      "text/plain": [
       "Line 1: Redundant list comprehension\n",
       "Found:\n",
       "[x | x <- v]\n",
       "Why not:\n",
       "v"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\"abcd\""
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','a'),('b','b'),('c','c'),('d','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "[x | x <- v]\n",
    "[(x,x) | x <- v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "-- (.@.)은 관계 합성 연산자를 정의한 것이다\n",
    "r1 .@. r2 = [(x,z) | (x,y1)<-r1, (y2,z)<-r2, y1==y2]\n",
    "\n",
    "-- r .^ k 는 $R^k$에 해당 \n",
    "r .^ 1 = r\n",
    "r .^ n = r .@. (r .^ (n-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('a','c'),('b','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('a','c'),('b','d'),('a','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('a','c'),('b','d'),('a','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('a','c'),('b','d'),('a','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rel1 = r1 .^ 1\n",
    "rel2 = r1 .^ 2\n",
    "rel3 = r1 .^ 3\n",
    "rel4 = r1 .^ 4\n",
    "rel5 = r1 .^ 5\n",
    "\n",
    "import Data.List\n",
    "\n",
    "rel1\n",
    "rel1 `union` rel2\n",
    "rel1 `union` rel2 `union` rel3\n",
    "rel1 `union` rel2 `union` rel3 `union` rel4\n",
    "rel1 `union` rel2 `union` rel3 `union` rel4 `union` rel5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('d','b')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('d','b'),('a','c'),('b','d'),('c','b'),('d','c')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('d','b'),('a','c'),('b','d'),('c','b'),('d','c'),('a','d'),('b','b'),('c','c'),('d','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('d','b'),('a','c'),('b','d'),('c','b'),('d','c'),('a','d'),('b','b'),('c','c'),('d','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a','b'),('b','c'),('c','d'),('d','b'),('a','c'),('b','d'),('c','b'),('d','c'),('a','d'),('b','b'),('c','c'),('d','d')]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rr1 = r2 .^ 1\n",
    "rr2 = r2 .^ 2\n",
    "rr3 = r2 .^ 3\n",
    "rr4 = r2 .^ 4\n",
    "rr5 = r2 .^ 5\n",
    "\n",
    "rr1\n",
    "rr1 `union` rr2\n",
    "rr1 `union` rr2 `union` rr3\n",
    "rr1 `union` rr2 `union` rr3 `union` rr4\n",
    "rr1 `union` rr2 `union` rr3 `union` rr4 `union` rr5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "7.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}