from __future__ import print_function
from sys import stdin
import sys

def printf(str, *args):
    print(str % args, end='')

domain = 2                       # 집합의 크기를 위한 상수
map_power_set = list()           # 멱집합 원소들을 저장하기 위한 map 구조 
mat_size = 9                     # 멱집합에서 부분집합을 만족하는 관계의 크기를 위한 변수

# setout 함수가 주어진 집합을 출력
def setout(A):
    count = 0
    if 1 not in A:
        print("\u2205")
        return
    printf("{")
    for i in range(0, domain):
        if A[i] == 1:
            if count != 0:
                printf(",")
            printf("%2d"%(i+1))
            count = 1
    
    printf(" }\n")

# printPowerSet 함수가 멱집합을 계산하면서 출력
def printPowerSet(set,set_size):
  
  pow_set_size =  1 << set_size        # 2^{set_size}로 멱집합 크기 정의 및 초기화
  counter = 0
  j = 0 
  element = ""                         # 멱집합 원소를 문자열로 저장하는 변수
  print("P(A) = { \u2205", end = "")

  map_power_set.append("\u2205")       # 공집합을 map에 추가

  for counter in range(1, pow_set_size):
    print(" , { ", end = "")
    for j in range(0, set_size):
      # counter의 (오른쪽부터) j번째 비트가 1이면 set[j]를 출력
      if (counter & (1 << j)) > 0:
        element = element + str(j+1)
        print(j+1, end = ", ")            
        
    print("\b\b }", end = "")
    map_power_set.append(element)      # 멱집합의 다음 원소를 map에 추가
    element = ""                       # 새로운 다른 원소를 받기 위해 재초기화
  print("}")

# 순서쌍을 출력하는 함수
def print_pair(i, j):
    if map_power_set[i] == "\u2205" and map_power_set[j] == "\u2205" :
        print("(", map_power_set[i], " ,", map_power_set[j], " ),", end = "", sep = '')
    elif map_power_set[i] == "\u2205" and map_power_set[j] != "\u2205" :
        print("(", map_power_set[i], " , {", end = "", sep = '')
        for c in map_power_set[j]:
            print(c, end = ", ")
        print("\b\b}),", end = "")
    else:
        print("({", end = "")
        for c in map_power_set[i]:
            print(c, end = ", ")
        print("\b\b}, {", end = "")
        for c in map_power_set[j]:
            print(c, end = ", ")
        print("\b\b}),", end = "")

# init_matrix P(A)에 대한 관계행렬을 adjacency에 대입
def init_matrix(adjacency):
    adjacencymx = [[0 for j in range(len(adjacency[0]))] for i in range(len(adjacency))]
    
    # P(A)에 대한 관계를 저장하는 관계행렬 adjacencymx의 초기화 및 관계 출력
    print("R = (P(A), \u2286 ) = { ", end = "")
    for i in range(0,len(map_power_set)):
        for j in range(0,len(map_power_set)):
            if i <= j:                     # 부분집합 관계를 표현하기 위한 조건
                # {1}이 {2}의 부분집합이 아니므로 반복을 건너뜀
                if i == 1 and j == 2:
                    continue
                adjacencymx[i][j] = 1
                print_pair(i, j)           # 순서쌍 출력
        
    print("\b\b }")
    return adjacencymx
setA = [1 for _ in range(0,domain)]        # 집합 A를 위한 0으로 초기화된 배열

# 관계(부울)행렬을 위한 2차원 배열 정의 및 초기화
adjacencymx = [[0 for j in range(mat_size)] for i in range(mat_size)]

print("\nA =", end = " ")
setout(setA)                             # 집합 A를 출력
printPowerSet(setA, domain)              # 집합 A의 멱집합을 출력
adjacencymx = init_matrix(adjacencymx)   # A의 멱집합에서 부분집합을 만족하는 관계행렬을 대입                       
reflexivity = 1
# 관계행렬에서 반사관계 여부를 확인 
for i in range(0, len(map_power_set)):
    # iRi가 없으면 바로 반복문을 멈춤
    if adjacencymx[i][i] == 0:
        reflexivity = 0
        break

if reflexivity == 1:
    print("\n{ ", end = "")
    for i in range(0, len(map_power_set)):
        print_pair(i, i)            # 순서쌍 출력

    print("\b\b } \u2286 R이므로 R은 반사관계이다.\n")
else:
    print("R은 반사관계가 아니므로 부분순서관계도 아니다.\n")
    sys.exit()      # R은 부분순서관계가 아니므로 프로그램을 멈춤


print("반사관계를 만족하는 R의 부분집합은 a, b \u2208 A, (a, b) \u2208 R이고 (b, a) \u2208 R일  때 a = b를 만족한다.", end = "\n")
for i in range(0, len(map_power_set)):
    for j in range(0, len(map_power_set)):
        if i < j :              # 반대칭관계를 만족하는 원소 출력 및 이유 해석
            print_pair(i, j)            # 순서쌍 출력
            print("에 대해", end = " ")
            print_pair(i, j)            # 순서쌍 출력
            print("\u2208 R이지만", end = " ")
            print_pair(i, j)            # 순서쌍 출력
            print("\u2209 R이므로 만족한다.", end = "\n")
   

print("\b\b그러므로 반대칭관계이다.\n")

transitivity = 1
test = 1
# 관계행렬에서 추이관계 여부를 확인 
for i in range(0, len(map_power_set)):
    for j in range(0, len(map_power_set)):
        if adjacencymx[i][j] == 1:
            for k in range(0, len(map_power_set)):
                # iRj와 jRk가 있을 때 iRk가 있으면
                if adjacencymx[j][k] == 1:
                    if adjacencymx[i][k] == 1:
                        print_pair(i, j)            # 순서쌍 출력
                        print("\b\u2208 R이고", end = " ")
                        print_pair(j, k)            # 순서쌍 출력
                        print("\b\u2208 R이면", end = " ")
                        print_pair(i, k)            # 순서쌍 출력
                        print("\b\u2208 R이 성립한다.", end = "\n")
                    else:
                        transitivity = 0
                        test = 0
                        break
            if test == 0:
                print("R은 추이관계가 아니므로 부분순서관계도 아니다.\n")
                sys.exit()      # R은 부분순서관계가 아니므로 프로그램을 멈춤

    if test == 0:
        break
print("\b\b따라서 추이관계를 만족한다.\n")

# 부분순서관계를 하세 도형으로 출력
print("그러므로 A의 멱집합 P(A)에서 \u2286을 만족하는 관계 R은 부분순서관계이다. 이 관계를 하세 도형으로 변환하면 다음과 같다.\n")

print("                       {1, 2}        ")
print("                        /  \     ")
print("                       /    \     ")
print("                     {1}    {2}   ")
print("                       \    /     ")
print("                        \  /     ")
print("                         \u2205  ")

