제 4 장 관 계.

Slides:



Advertisements
Similar presentations
Add Your Text 5. 지수함수와 로그함수 1. 지수함수 2. 로그함수 · 지수함수와 그 그래프 · 지수방정식과 지수부등식 · 로그 함수와 그 그래프 · 로그방정식과 로그부등식.
Advertisements

출석수업 과제 – 총 5문제, 10월 25일 제출 정보통계학과 장영재 교수.
주요 내용 행렬 스칼라, 벡터, 행렬 행렬의 합과 곱 여러가지 행렬들 전치 행렬 정방 행렬 역가능 행렬 역 행렬 행렬식.
이진 나무 구조 강윤섭 2008년 5월 23일.
적분방법의 연속방정식으로부터 Q=AV 방정식을 도출하라.
Entity Relationship Diagram
RLC 회로 R L C 이 때 전류 i 는 R, L, C 에 공통이다.
유한 오토마타 Finite Automata
제 12 장 직교배열표에 의한 실험계획(1).
수치해석 6장 예제문제 환경공학과 천대길.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
부록 1: 행렬대수의 기본개념 1. 기본정의 2. 행렬 연산 전치(transpose) 행렬의 동등(equal)
CHAP 10:그래프 (1) 순천향대학교 하상호.
6 장. ER-관계 사상에 의한 관계 데이터베이스 설계
Chapter 04 C 연산자의 이해.
공개키 암호화 프로그래밍 전자상거래보안.
P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt)
Modulo 연산.
Simulating Boolean Circuits on a DNA Computer
1. 관계 데이터 언어 관계 대수 1) 관계대수 정의 ① 원하는 정보와 그 정보를 어떻게 유도하는가를 기술하는 절차적 인 방법 ② 주어진 관계로 부터 원하는 관계를 얻기 위해 연산자와 연산 규칙을 제공하는 언어 ③ 릴레이션 조작을 위한 연산의 집합으로 피연산자와 결과가.
Tail-recursive Function, High-order Function
A Moments of Areas.
CH 4. 확률변수와 확률분포 4.1 확률 확률실험 (Random Experiment, 시행, Trial) : 결과를 확률적으로 예측 가능, 똑 같은 조건에서 반복 근원사상 (Elementary Event, e) : 시행 때 마다 나타날 수 있는 결과 표본공간.
행렬 기본 개념 행렬의 연산 여러가지 행렬 행렬식 역행렬 연립 일차 방정식 부울행렬.
Ⅲ. 이 차 방 정 식 1. 이차방정식과 그 풀이 2. 근 의 공 식.
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
(Relations and Its Properties)
Lesson 4. 수식과 연산자.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
문제 2명의 사형수가 있다. 둘에게는 검정색 모자와 흰색 모자를 임의로 씌우는데, 자기가 쓴 모자의 색은 절대로 알 수가 없다. 서로 상대의 모자색만을 볼 수 있고, 이들이 살기 위해선 자신의 쓴 색의 모자를 맞춰야 한다. 단, 둘 중 한명만이라도 자신이 쓴 모자의 색을.
주요 내용 왜 그래프인가? 기본 용어 그래프의 표현 오일러(Euler) 그래프와 해밀턴(Hamilton) 그래프
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
관계 기본 개념 관계의 표현 관계의 성질 관계의 연산 관계의 폐포 동치 관계 부분순서 관계.
4장 기하학적 객체와 변환 - 기하 1장 – 그래픽스 시스템과 모델 2장 – 그래픽스 프로그래밍 3장 – 입력과 상호작용
05. Relational DBMS 명지대학교 ICT 융합대학 김정호.
합집합과 교집합이란 무엇인가? 01 합집합 두 집합 A, B에 대하여 A에 속하거나 B에 속하는 모든 원소로 이루어진 집합을 A와 B의 합집합이라고 하며, 기호 A∪B로 나타낸다. A∪B ={x | x∈A 또는 x∈B}
제 3장 행 렬.
1. 2진 시스템.
2. Boole 대수와 논리 게이트.
표지 수학8-나 2학년 2학기  Ⅲ.도형의 닮음 (4) 삼각형의 중점연결정리 (13/21) 삼각형의 중점연결정리.
미분방정식.
수학10-나 1학년 2학기 Ⅳ.삼각함수 3. 삼각함수의 그래프(7/12) 삼각함수 수업계획 수업활동.
01 로그의 정의 ⑴ 일 때, 양수 에 대하여 을 만족시키는 실수 는 오직 하나 존재한다. 이때 를
2nd day Indexing and Slicing
1. 선분 등분하기 (1) 주어진 선분 수직 2등분 하기 ① 주어진 선분 AB를 그린다. ② 점 A를 중심으로 선분AB보다
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
작도 작도 작도: 눈금 없는 자와 컴퍼스만을 사용하여 도형을 그리는 것
2장 PHP 기초 PHP의 시작과 끝을 이해한다. 주석문에 대하여 이해한다. echo 문을 이용하여 화면에 출력하
Chapter 1 단위, 물리량, 벡터.
원의 방정식 원의 방정식 x축, y축에 접하는 원의 방정식 두 원의 위치 관계 공통접선 원과 직선의 위치 관계
SPL3D Printer If 조건문.
Chapter 1 단위, 물리량, 벡터.
Part 2 개념적 데이터 모델 Copyright © 2006 by Ehan Publishing Co. All rights reserved.
Ⅵ. 확 률 1. 확 률 2. 확률의 계산.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
ER-관계 사상에 의한 관계데이터베이스 설계 충북대학교 구조시스템공학과 시스템공학연구실
The theory of m-sequences
문장제 쉽게 풀기 -최소공배수 응용 문제.
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다.
수치해석 ch3 환경공학과 김지숙.
07. DB 설계 명지대학교 ICT 융합대학 김정호.
이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net.
Chapter 2: Intro to Relational Model
수학 2 학년 1 학기 문자와 식 > 부 등 식 ( 1 / 2 ) 일차부등식의 풀이.
                              데이터베이스 설계 및 실습 #6 - SQL 실습 한국외국어대학교 DaPS 연구실                              
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
Report #2 (기한: 3/16) 데이터 구조 과목의 수강생이 50명이라고 가정한다. 이 학생(학번은 2016????으로 표현됨)들의 중간 시험(0~100), 기말 시험(0~100) 성적을 성적 파일에 작성하라(프로그램을 통해서 또는 수작업으로). 성적 파일을 읽어들여서.
Countable & Uncountable
Presentation transcript:

제 4 장 관 계

목차 4.1 관 계 4.2 관계의 표현 4.3 관계의 합성 4.4 동치 관계 4.5 관계의 폐쇄 성질 4.6 부분 순서와 속

4.1 관 계 정의 4-1 n-항 관계(n-ary relation) 순서쌍의 집합 곱 집합 A1×A2× …×An의 부분집합 R 4.1 관 계 순서쌍의 집합 관계를 표현하는 가장 기본적인 표기법 RØ = 이면 R : 영 관계(empty relation), R=A1×A2×…×An이면 R : 전체 관계(universal relation) 정의 4-1 n-항 관계(n-ary relation) 곱 집합 A1×A2× …×An의 부분집합 R : 집합 A1, A2, …, An 에서의 n-항 관계 R={(a1, a2, …, an) | ai∈Ai} (n - 투플의 집합)

4.1 관 계 정의 4-2 2-항 관계(binary relation) 4.1 관 계 정의 4-2 2-항 관계(binary relation) n = 2, R⊆A1×A2일 때, R : A1에서 A2로의 이항 관계(a, b) ∈ R이면 aRb , (a, b) ∈ R이면 aRb 정의역(domain): 순서쌍에서 모든 첫 번째 원소의 집합 치역(range): 순서쌍에서 모든 두 번째 원소의 집합 집합 A에 대한(on a set A) 관계 : A1=A2=A일 때 A에서 A로 가는 이항 관계

4.1 관 계 【예제 4.1】 두 집합 A={1, 2}, B={3, 4}일 때, A 에서 B 로의 모든 관계를 나타내어라. 4.1 관 계 【예제 4.1】 두 집합 A={1, 2}, B={3, 4}일 때, A 에서 B 로의 모든 관계를 나타내어라. [풀이] A×B={(1, 3), (1, 4), (2, 3), (2, 4)} ∴ 모든 관계의 개수 ː 24=16 Ф {(1,3)} {(1,4)} {(2,3)} {(2,4)} {(1,3), (1,4)} {(2,3), (2,4)} {(1,3), (2,3)} {(1,4), (2,4)} {(1,3), (2,4)} {(1,4), (2,3)} {(1,3), (1,4), (2,3)} {(1,3), (1,4), (2,4)} {(1,3), (2,3), (2,4)} {(1,4), (2,3), (2,4)} {(1,3), (1,4), (2,3), (2,4)}

4.1 관 계 【예제 4.2】 집합 A={1, 2, 3, 4}에 대한 관계 R을 R={(a, b) ∈ A×A | b가 a로 나누어진다}라고 할 때, R의 모든 순서쌍을 나열하라. [풀이] R={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

4.1 관 계 【예제 4.3】 정수 집합에 대한 관계들이 다음과 같을 때, 4.1 관 계 【예제 4.3】 정수 집합에 대한 관계들이 다음과 같을 때, R1={(a, b) | a < b} R2={(a, b) | a>b } R3={(a, b) | a=b 또는 a=-b} R4={(a, b) | a=b} R5={(a, b) | a=b+1} R6={(a, b) | a+b < 3} 각각의 순서쌍 (1, 1), (1, 2), (2, 1), (1, -1), (2, 2)를 포함하는 관계들을 모두 구하라. [풀이] (1, 1) : R1, R3, R4, R6 (1, 2) : R1, R6 (2, 1) : R2, R5, R6 (1, -1) : R2, R3, R6 (2, 2) : R1, R3, R4

4.1 관 계 정의 4-3 역관계(inverse relation) R-1={(b, a)|(a, b)∈R} 4.1 관 계 정의 4-3 역관계(inverse relation) R이 관계일 때 R의 역관계 : R-1 R-1={(b, a)|(a, b)∈R}

4.1 관 계 【예제 4.4】R={(1, 1), (1, 6), (5, 1), (5, 8), (7, 2)} 일 때, R-1를 구하라. [풀이] R-1={(1, 1), (6, 1), (1, 5), (8, 5), (2, 7)}

4.2 관계의 표현 (1) 화살표(arrow diagram) 4.2 관계의 표현 (1) 화살표(arrow diagram) 집합 A, B가 있을 때 a∈A와 b∈B가 aRb이면 이 관계를 a 에서 b로 가는 화살표로 표현

4.2 관계의 표현 【예제 4.5】 A={1, 2, 3, 4,} B={a, b, c, d}이고 관계 R={(1, c), (1, d), (2, b), (3, a), (3, c), (4, a)}일 때, R을 화살표를 사용해서 나타내어라.

4.2 관계의 표현 [풀이]

4.2 관계의 표현 (2) 관계 행렬(relation matrix) 4.2 관계의 표현 (2) 관계 행렬(relation matrix) R : A={a1, a2, …, am} 에서 B={b1, b2, …, bn} 로의 관계. 관계 R은 행렬 MR=(mij) (단, 1≤i≤m, 1≤j≤n) 로 표현

4.2 관계의 표현 【예제 4.6】 집합 A={1, 2, 3}, B={1, 2}에 대하여, A에서 B로의 관계 R이 "a∈A, b∈B일 때 a>b이다"로 주어진 경우 R을 관계 행렬(relation matrix)로 표현하라. [풀이] R={(2, 1), (3, 1), (3, 2)}이므로, R의 관계 행렬은

4.2 관계의 표현 【예제 4.7】 A={a1, a2, a3}, B={b1, b2, b3, b4}이고, 관계 R에 대한 관계 행렬이 다음과 같이 표현될 때, R에 대한 순서쌍을 구하라

4.2 관계의 표현 [풀이] 관계 R은 mij=1인 순서쌍(ai, bj)의 집합이므로 4.2 관계의 표현 [풀이] 관계 R은 mij=1인 순서쌍(ai, bj)의 집합이므로 R={(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)}

4.2 관계의 표현 【예제 4.8】 집합 A={1, 2, 3}일 때, 관계 R={(1, 1), (1, 3), (2, 3), (3, 2)}이고, S={(1, 1), (1, 3), (2, 1), (2, 2), (3, 3)}이다. 이 때 MRS와 MRS 를 각각 구하라.

4.2 관계의 표현 [풀이]

4.2 관계의 표현 (3) 방향 그래프(directed graph) 정의 4-4 방향 그래프 4.2 관계의 표현 (3) 방향 그래프(directed graph) 정의 4-4 방향 그래프 정점(vertex)들의 집합 V와, V의 각 원소들로 구성된 순서쌍인 간선(edge)의 집합 E로 구성

4.2 관계의 표현 【예제 4.9】 정점: a, b, c, d와 연결선: (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)로 구성된 방향 그래프는 ? [풀이]

4.2 관계의 표현 【예제 4.10】방향 그래프로 표시된 관계 R의 순서쌍 ? ◀ 책 그림 참조 ▶ [풀이] 4.2 관계의 표현 【예제 4.10】방향 그래프로 표시된 관계 R의 순서쌍 ? ◀ 책 그림 참조 ▶ [풀이] R={(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) }

4.2 관계의 표현 【예제 4.11】 집합 A={1, 2, 3, 4, 5, 6, } 관계 {R=(m, n)∈A×A|mod(m, n)=0, m≠ n, 단, mod 연산은 n/m의 나머지를 구하는 연산자} 관계 R에 대한 방향 그래프 ? [풀이]

4.3 관계의 합성 정의 4-5 합성 관계(composite relation) 집합 A, B, C, 4.3 관계의 합성 정의 4-5 합성 관계(composite relation) 집합 A, B, C, Rː A→B관계, S : B→C관계 합성 관계 R ◦ S 의 정의 R ◦ S={(a, c)∈A×C | (a, b)∈R이고 (b, c)∈S인, b∈B 가 존재한다}

4.3 관계의 합성 【예제 4.12】 A={2, 3, 8, 9}, B={4, 6, 18}, C={1, 4, 7, 9}이다. Rː A→B관계, S : B→C관계, R ◦ S를 구하라. R={(a, b) | a∈A, b∈B, mod(b, a)=0} S={(b, c) | b∈B, c∈C, b≤c}

4.3 관계의 합성 [풀이] R={(2, 4), (2, 6), (2, 18), (3, 6), (3, 18), (9, 18)}, 4.3 관계의 합성 [풀이] R={(2, 4), (2, 6), (2, 18), (3, 6), (3, 18), (9, 18)}, S={(4, 4), (4, 7), (4, 9), (6, 7), (6, 9)} ∴ R ◦ S={(2, 4), (2, 7), (2, 9), (3, 7), (3, 9)}

4.3 관계의 합성 【예제 4.13】 A={1, 2}, B={3, 4}, C={5, 6}이고, 관계 R={(1, 3), (1, 4)}, S={(3, 5), (4, 5)}이다. 이 때 R ◦ S을 구하라. [풀이] R ◦ S={(1, 5)}

4.3 관계의 합성 【예제 4.14】 합성 관계 R ◦ S를 구하여 관계 행렬로 표현하라.

4.3 관계의 합성 [풀이]

4.3 관계의 합성 ☞ 정리 4-1 집합 A, B, C, D, R⊆A×B, S⊆B×C, T⊆C×D 일때, R ◦ (S ◦ T)=(R ◦ S) ◦ T 이다.

4.3 관계의 합성 [증명] R ◦ (S ◦ T)⊆(R ◦ S) ◦ T와 (R ◦ S) ◦ T⊆R ◦ (S ◦ T)를 동시에 만족함을 보인다. (1) R ◦ (S ◦ T)⊆(R ◦ S) ◦ T 증명 (x, y) ∈ R ◦ (S ◦ T)라 가정. (x, z) ∈ R, (z, y) ∈ S ◦ T, z ∈ B가 존재. (z, y)∈S ◦ T이므로, (z, w)∈S, (w, y)∈T, w∈C가 존재 (x, z)∈R, (z, w)∈S이므로 (x, w)∈R ◦ S (x, w)∈R ◦ S이고 (w, y)∈T이므로, (x, y)∈(R ◦ S) ◦ T ∴ R ◦ (S ◦ T)⊆(R ◦ S) ◦ T (2) (R ◦ S) ◦ T⊆R ◦ (S ◦ T)도 같은 방법으로 증명.

4.3 관계의 합성 ☞ 정리 4-2 A, B, C가 집합이고, R⊆A×B와 S⊆B×C일 때, (R ◦ S) -1=S-1 ◦ R-1이다.

4.3 관계의 합성 [증명] (R ◦ S) -1⊆S-1 R-1와 S-1 R-1⊆(R ◦ S) -1를 동시에 만족함을 보인다. 4.3 관계의 합성 [증명] (R ◦ S) -1⊆S-1 R-1와 S-1 R-1⊆(R ◦ S) -1를 동시에 만족함을 보인다. (1) (R ◦ S)-1 ⊆S-1 R-1 증명 : (y, x)∈(R ◦ S) -1 가정, (x, y)∈R ◦ S이므로 (x, z)∈R, (z, y)∈S인 z∈B가 존재 (x, z)∈R이므로 (z, x)∈R-1, (z, y)∈S이므로 (y, z)∈S-1 (y, z)∈S-1, (z, x)∈R-1이므로, (y, x)∈S-1 R-1 ∴ (R ◦ S) -1⊆S-1 R-1 (2) S-1 R-1⊆(R ◦ S) -1 : 같은 방법으로 증명

4.3 관계의 합성 【예제 4.15】 집합 {1, 2, 3}에 대한 관계 R이 다음과 같을 때 R2을 관계 행렬과 방향 그래프로 표시하여라.

4.3 관계의 합성 [풀이] R2={(1, 1), (2, 2), (3, 1), (3, 2), (3, 3)}

4.3 관계의 합성 【예제 4.16】 R={(1, 1), (3, 1), (2, 3), (4, 2)}일 때, R2, R3, R4을 구하라. [풀이] R2=R ◦ R={(1, 1), (2, 1), (4, 3), (3, 1)} R3=R2 ◦ R={(1, 1), (3, 1), (2, 1), (4, 1)} R4=R3 ◦ R={(1, 1), (3, 1), (2, 1), (4, 1)}

4.3 관계의 합성

4.3 관계의 합성 ☞ 정리 4-3 R이 A에 대한 관계이고, m, n이 자연수일 때 다음 식이 성립한다. 4.3 관계의 합성 ☞ 정리 4-3 R이 A에 대한 관계이고, m, n이 자연수일 때 다음 식이 성립한다. (1) Rm ◦ Rn=R m+n (2) Rm ◦ Rn=Rn ◦ Rm (3) (Rm)n=Rmn

4.4 동치 관계 4.4.1 관계의 성질 (1) 반사 관계(reflexive relation) 정의 4-6 반사 관계 4.4 동치 관계 4.4.1 관계의 성질 (1) 반사 관계(reflexive relation) 정의 4-6 반사 관계 A의 모든 원소 a가, (a, a)∈R이면, R은 반사적 또는 반사 관계 (R 은 집합 A에 대한 관계)

4.4 동치 관계 【예제 4.17】 집합 {1, 2, 3, 4}에 대한 다음의 방향 그래프로 표시된 관계들은 반사적인가? 4.4 동치 관계 【예제 4.17】 집합 {1, 2, 3, 4}에 대한 다음의 방향 그래프로 표시된 관계들은 반사적인가? [풀이] (1) 반사적, (2) 반사적이 아니다.

4.4 동치 관계 【예제 4.18】 다음의 관계들은 집합 {1, 2, 3, 4}에 대해 반사적인가? 4.4 동치 관계 【예제 4.18】 다음의 관계들은 집합 {1, 2, 3, 4}에 대해 반사적인가? R1={(1, 1), (1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 1), (4, 4)} R2={(1, 1), (1, 4), (2, 2), (2, 4), (3, 3), (3, 4), (4, 4)} R3={(1, 2), (2, 1), (3, 4), (4, 3), (1, 1), (2, 2), (3, 3)} R4= ø R5={(1, 1), (2, 2), (3, 3), (4, 4)} R6={(3, 2), (4, 4), (2, 1), (1, 1), (4, 2), (3, 3), (3, 1), (2, 2)} [풀이] R2, R5, R6 : 반사적, R1, R3, R4 : 반사적이 아니다

4.4 동치 관계 【예제 4.19】 양의 정수들의 집합에서 관계 "나누기"는 반사적인가? [풀이] 반사적

4.4 동치 관계 (2) 대칭관계 정의 4-7 대칭 관계 R은 집합 A에 대한 관계, 4.4 동치 관계 (2) 대칭관계 정의 4-7 대칭 관계 R은 집합 A에 대한 관계, 모든 a, b∈A에 대해 (a, b)∈R일 때 반드시 (b, a)∈R인 관계가 존재하면, R은 대칭적 또는 대칭 관계

4.4 동치 관계 【예제 4.20】 [예제 4.18]의 관계는 집합 {1, 2, 3, 4} 에 대해 대칭적인가? [풀이] 4.4 동치 관계 【예제 4.20】 [예제 4.18]의 관계는 집합 {1, 2, 3, 4} 에 대해 대칭적인가? [풀이] R3, R4, R5 : 대칭적, R1, R2, R6 : 대칭이 아니다

4.4 동치 관계 【예제 4.21】 대칭 관계는 관계 행렬로 표현하면 쉽게 파악할 수 있다. 다음과 같이 관계 행렬로 표현된 관계는 대칭적인가? [풀이] (1), (2), (3) : 대칭적

4.4 동치 관계 【예제 4.22】 다음의 관계들은 대칭적인가? 단, Z는 정수의 집합이다. 4.4 동치 관계 【예제 4.22】 다음의 관계들은 대칭적인가? 단, Z는 정수의 집합이다. (1) R1={(m, n)∈Z×Z : m=n} (2) R2={(m, n)∈Z×Z : m ≥ n} (3) R3={(m, n)∈Z×Z : m=n 또는 m=-n} (4) R4={(m, n)∈Z×Z : n=m+1} (5) R5={(m, n)∈Z×Z : m < n} (6) R6={(m, n)∈Z×Z : m+n ≤ 0} [풀이] R1, R3, R6 : 대칭적 R2, R4, R5 : 대칭이 아니다.

4.4 동치 관계 (3) 반대칭 관계 (antisymmetruc relation) 정의 4-8 반대칭 관계 4.4 동치 관계 (3) 반대칭 관계 (antisymmetruc relation) 정의 4-8 반대칭 관계 R은 집합 A에 대한 관계, 모든 a, b∈A에 대해, 다음의 조건을 만족하면 반대칭적 또는 반대칭 관계 (a, b)∈R (b, a)∈R ⇒ a=b

4.4 동치 관계 【예제 4.23】 다음 관계들은 반대칭적인가?

4.4 동치 관계 [풀이] (1) 반대칭적, (2) 대칭적, 반대칭적이 아니다. 4.4 동치 관계 [풀이] (1) 반대칭적, (2) 대칭적, 반대칭적이 아니다. (3) 영관계이므로 반대칭적, 대칭적이다. 반사적은 아니다

4.4 동치 관계 【예제 4.24】 다음의 관계들은 집합 1, 2, 3, 4에 대해 반대칭적인가? 4.4 동치 관계 【예제 4.24】 다음의 관계들은 집합 1, 2, 3, 4에 대해 반대칭적인가? R1={(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (4, 4)} R2={(1, 1), (2, 2), (3, 3), (4, 4)} R3={(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} R4={(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} R5={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4),(3, 3), (3, 4), (4, 4)} R6={(3, 4)}

4.4 동치 관계 [풀이] R4, R5, R6 : 반대칭적 R2 : 반대칭적, 동시에 대칭적 4.4 동치 관계 [풀이] R4, R5, R6 : 반대칭적 R2 : 반대칭적, 동시에 대칭적 ( 대칭적과 반대칭적은 서로 반대가 아님) R1, R3 : 반대칭적이 아니다

4.4 동치 관계 (4) 이행 관계(transitive relation) 정의 4-9 이행 관계 R은 집합 A에 대한 관계, 4.4 동치 관계 (4) 이행 관계(transitive relation) 정의 4-9 이행 관계 R은 집합 A에 대한 관계, 모든 a, b, c∈A, (a, b)∈R이고, (b, c)∈R이면 (a, c)∈R일 때, R을 이행적 또는 이행 관계

4.4 동치 관계 【예제 4.25】 다음의 방향 그래프로 표시된 관계들은 이행적인가? 4.4 동치 관계 【예제 4.25】 다음의 방향 그래프로 표시된 관계들은 이행적인가? [풀이] (1) 이행적 (2) 이행적이 아니다

4.4 동치 관계 【예제 4.26】 다음의 관계들은 이행적인가? [풀이] R1, R5, R7 : 이행적 4.4 동치 관계 【예제 4.26】 다음의 관계들은 이행적인가? R1={(1, 2), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} R2={(1, 1), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (4, 1), (4, 4)} R3={(1, 1), (1, 3), (2, 2), (3, 1), (3, 4), (4, 1), (4, 4)} R4={(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 4)} R5={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4)} R6={(1, 1), (1, 3), (3, 1), (3, 4)} R7={(1, 2)} [풀이] R1, R5, R7 : 이행적 R2, R3, R4, R6 : 이행적이지 않다

4.4 동치 관계 【예제 4.27】 다음의 방향 그래프(directed graph)로 주어진 관계가 반사적, 대칭적, 반대칭적, 이행적인지를 판별하고, 관계 행렬(relation matrix)로 나타내어라.

4.4 동치 관계

4.4 동치 관계 [풀이] (1) 반사적, 대칭적, 이행적이다. (2) 반사, 반대칭적, 이행적이다. 4.4 동치 관계 [풀이] (1) 반사적, 대칭적, 이행적이다. (2) 반사, 반대칭적, 이행적이다. (3) 대칭적, 반대칭적, 이행적이다. (4) 반사적, 대칭적이다.

4.4 동치 관계 ☞정리 4-4 R을 집합 A에 대한 관계라 할 때 (1) R은 반사 관계 ⇔ IA⊆R 4.4 동치 관계 ☞정리 4-4 R을 집합 A에 대한 관계라 할 때 (1) R은 반사 관계 ⇔ IA⊆R (2) R은 이행 관계 ⇔ R ◦ R⊆R (3) R은 반사 관계이고, 이행 관계 IA⊆R=R ◦ R (4) R이 이행 관계라면 자연수 n에 대해 Rn⊆R이 된다. 단, IA는 항등 관계로서 {(a, a) | a∈A} 이다.

4.4 동치 관계 정의 4-10 동치 관계(equivalence relation) 4.4 동치 관계 정의 4-10 동치 관계(equivalence relation) 집합 A에 대한 관계가 반사적, 대칭적, 이행적 이면 이를 동치 관계라 한다.

4.4 동치 관계 【예제 4.28】 Z가 정수의 집합이고 R={(m, n)∈Z×Z | m=n 또는 m=-n}일 때, 4.4 동치 관계 【예제 4.28】 Z가 정수의 집합이고 R={(m, n)∈Z×Z | m=n 또는 m=-n}일 때, R이 Z에 대한 동치 관계임을 보여라. [풀이] (1) n∈Z라면, (m, n)∈R인 m=n이 존재:반사적 (2) (m, n)∈R라면, m=n일 때 n=m이고, m=-n일 때, n=-m이므로 (n, m)∈R : 대칭적

4.4 동치 관계 (3) (m, n)∈R이고 (n, p)∈R이면, 네 가지 경우 m=n, n=p인 경우 m=p 4.4 동치 관계 (3) (m, n)∈R이고 (n, p)∈R이면, 네 가지 경우 m=n, n=p인 경우 m=p m=n, n=-p인 경우 m=-p m=-n, n=p인 경우 m=-p m=-n, n=-p인 경우 m=p 모든 경우에서, (m, p)∈R이므로 : 이행적 ∴ 관계 R은 동치 관계

4.4 동치 관계 【예제 4.29】 R이 실수 집합이고 R={(a,b)∈R×R | a-b는 정수}일 때, R은 동치 관계인가? 4.4 동치 관계 【예제 4.29】 R이 실수 집합이고 R={(a,b)∈R×R | a-b는 정수}일 때, R은 동치 관계인가? [풀이] (1) 모든 실수 a에 대해 a-a = 0은 정수, aRa를 만족 : 반사적

4.4 동치 관계 (2) aRb가 존재할 때 a-b가 정수이면 b-a 또한 정수 bRa가 존재 : 대칭적 4.4 동치 관계 (2) aRb가 존재할 때 a-b가 정수이면 b-a 또한 정수 bRa가 존재 : 대칭적 (3) aRb, bRc가 존재할 때 a-b와 b-c는 정수, a-c=(a-b)+(b-c)는 정수로 aRc 만족 : 이행적 ∴ R은 동치 관계

4.4 동치 관계 정의 4-11 동치류(equivalence class) R은 집합 A에 대한 동치 관계 4.4 동치 관계 정의 4-11 동치류(equivalence class) R은 집합 A에 대한 동치 관계 R에 대한 a의 동치류 : [a]로 표기 [a]={x (a, x)∈R}

4.4 동치 관계 【예제 4.30】 집합 A={1, 2, 3, 4}에 대한 관계 R이 다음과 같이 주어졌을 때 동치류를 구하라. R={(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)} [풀이] [1]=[2]={1, 2}, [3]=[4]={3, 4}

4.4 동치 관계 【예제 4.31】 [예제 4.28]에서 정의한 R에 대한 동치류를 구하라. [풀이] 4.4 동치 관계 【예제 4.31】 [예제 4.28]에서 정의한 R에 대한 동치류를 구하라. [풀이] [a]={-a, a}, 각각 두 개의 원소 (a=0 제외)

4.4 동치 관계 ☞ 정리 4-5 R을 집합 A에 대한 동치 관계라 할 때, 다음 문장들은 동치이다. (1) aRb 4.4 동치 관계 ☞ 정리 4-5 R을 집합 A에 대한 동치 관계라 할 때, 다음 문장들은 동치이다. (1) aRb (2) [a]=[b] (3) [a]∩[b] ≠ ø

4.4 동치 관계 [증명] <1> (1) ⇒ (2) 4.4 동치 관계 [증명] <1> (1) ⇒ (2) aRb라 가정, [a]=[b] : [a]⊆[b]와 [b]⊆[a]임을 보임 c∈[a] → aRc R : 대칭적, aRb → bRa R : 이행적, bRa , aRc → bRc ∴ c∈[b] → [a]⊆[b] * [b]⊆[a]도 같은 방법으로 증명

4.4 동치 관계 <2> (2) ⇒ (3) [a]=[b]가정, R : 반사적 → a∈[a], [a] ≠ ø 4.4 동치 관계 <2> (2) ⇒ (3) [a]=[b]가정, R : 반사적 → a∈[a], [a] ≠ ø ∴ [a]∩[b]=[a]∩[a]=[a] ≠ ø <3> (3) ⇒ (1) [a]∩[b] ≠ ø 가정, c∈[a], c∈[b]가 존재 → aRc , bRc R은 대칭적 → cRb ∴ 이행적 성질에 의해 aRc, cRb → aRb

4.4 동치 관계 정의 4-12 분할(partition) 4.4 동치 관계 정의 4-12 분할(partition) 집합 A의 분할은 다음의 조건을 만족하는 A의 부분 집합 A1, A2, …, An의 모임이다. 이 때, Ai를 A의 분할 원소라 한다.

4.4 동치 관계 【예제 4.32】 A={1, 2, 3, 4, 5, 6}이라 할 때 A1={1, 2}, A2={3, 4, 6}, A3={5}는 A의 분할인가? [풀이] 분할이다

4.4 동치 관계 ☞ 정리 4-6 R이 A에 대한 동치 관계일 때 동치류의 모임은 A의 분할이다. [증명] 4.4 동치 관계 ☞ 정리 4-6 R이 A에 대한 동치 관계일 때 동치류의 모임은 A의 분할이다. [증명] A의 모든 원소 a에 대해 a∈[a] 즉, ∪[a]=A a∈A [a] ≠ [b] 이면 [a]∩[b]= ø (정리 4-5) ∴{[a] | a∈A} : A의 분할

4.4 동치 관계 ☞ 정리 4-7 집합 A의 분할이 {A1, A2, …, Ak}일 때 A에 대한 동치 관계 R이 존재하고, R에 대한 각 동치류는 A의 분할 원소 Ai이다. [증명] A에 대한 관계 R 정의 : aRb ( a, b∈Ai ) R이 동치 관계임을 보인다. (1) aRa는 명백, R : 반사적

4.4 동치 관계 (2) aRb → bRa (∵a, b가 같은 분할 원소 Ai에 속함) R : 대칭적 4.4 동치 관계 (2) aRb → bRa (∵a, b가 같은 분할 원소 Ai에 속함) R : 대칭적 (3) aRb, bRc → a, b∈Ai 이고, b, c∈Aj b∈Ai∩Aj, 분할의 정의에 의해 Ai=Aj 즉, a와 c는 같은 분할 원소에 속해 있고 aRc 이다 R : 이행적 ∴ 반사적, 대칭적, 이행적이므로 R은 동치 관계이다.

4.5 관계의 폐쇄 성질 P : 관계가 갖는 성질(반사적·대칭적·이행적 성질) 4.5 관계의 폐쇄 성질 P : 관계가 갖는 성질(반사적·대칭적·이행적 성질) R : 집합 A에 대한 관계(R은 P를 만족 또는 만족하지 않음) S : P에 관한 R의 폐쇄(closure) : R을 포함하면서 성질 P를 갖는 최소 관계

4.5 관계의 폐쇄 성질 【예제 4.33】 집합 A={1, 2, 3, 4}이고 R={(1, 2), (2, 1), (2, 2), (3, 2)}일 때, R의 반사 폐쇄를 구하라. [풀이] S={(1, 1), (1, 2), (2, 1), (2, 2), (3, 2), (3, 3), (4, 4)}

4.5 관계의 폐쇄 성질 ☞ 정리 4-8 R이 집합 A에 대한 관계이면 R의 반사 폐쇄는 R∪{(a, a) | a∈A}이다.

4.5 관계의 폐쇄 성질 【예제 4.34】 집합 A={1, 2, 3}이고 R={(1, 2), (2, 1), (2, 2), (3, 2)}일 때, R의 대칭 폐쇄를 구하라. [풀이] S={(1, 2), (2, 1), (2, 2), (2, 3), (3, 2)}

4.5 관계의 폐쇄 성질 【예제 4.35】 양의 정수의 집합에 대한 관계 4.5 관계의 폐쇄 성질 【예제 4.35】 양의 정수의 집합에 대한 관계 R={(a, b) a>b}의 대칭 폐쇄를 구하라. [풀이] R∪R-1 ={(a, b) | a>b} ∪{ (b, a) | a>b} ={(a, b) | a ≠ b}

4.5 관계의 폐쇄 성질 ☞ 정리 4-9 R이 집합 A에 대한 관계이면 R의 대칭 폐쇄는 R∪{(b, a)∈A×A | (a, b)∈R}=R∪R-1이다.

4.5 관계의 폐쇄 성질 정의 4-13 경로(path) 방향 그래프 G의 a에서 b로의 경로는 G에서 4.5 관계의 폐쇄 성질 정의 4-13 경로(path) 방향 그래프 G의 a에서 b로의 경로는 G에서 한 개 이상 간선 (x0, x1), (x1, x2), …, (x n-1, xn) 으로 구성(단, x0=a, xn=b)된 순서를 갖는다. 길이가 n인 경로에서 시작점과 끝점이 같은 경우를 사이클(순환; cycle)이라 한다.

4.5 관계의 폐쇄 성질 【예제 4.36】 다음의 방향 그래프에서 <a, b, e, d>, <a, e, c, d, b>, <b, a, c, b, a, a, b>, <d, c>는 경로가 존재하는가? 또한 경로의 길이와 경로의 순회 여부를 결정하라. ◀ 책 그림 참조 ▶

4.5 관계의 폐쇄 성질 [풀이] <a, b, e, d> : 길이 3인 경로 존재 4.5 관계의 폐쇄 성질 [풀이] <a, b, e, d> : 길이 3인 경로 존재 <a, e, c, d, b> : 경로가 존재하지 않는다. <b, a, c, b, a, a, b> : 길이는 6인 경로, 순환 <d, c> : 길이가 1인 경로 존재

4.5 관계의 폐쇄 성질 ☞ 정리 4-10 집합 A에 대한 관계 R은 a에서 b로의 길이가 n인 경로가 존재하면 (a, b)∈Rn이다.

4.5 관계의 폐쇄 성질 정의 4-14 접속 관계(connectivity relation) 4.5 관계의 폐쇄 성질 정의 4-14 접속 관계(connectivity relation) 집합 A에 대한 관계 R의 접속 관계 R* R*={(a, b) | a에서 b로의 경로가 존재}

4.5 관계의 폐쇄 성질 【예제 4.37】 집합 A={1, 2, 3, 4, 5}, 관계 R={(1, 1), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5)}라 할 때 다음을 구하라. (1) R2 (2) R* (1) R2 ={(1,1),(1,2),(1,3),(2,4),(2,5),(3,5)} (2) R* ={(1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4), (2,5),(3,4),(3,5),(4,5)}

4.5 관계의 폐쇄 성질 정의 4-15 이행 폐쇄(transitive closure) R을 집합 A에 대한 관계라면, R*는 4.5 관계의 폐쇄 성질 정의 4-15 이행 폐쇄(transitive closure) R을 집합 A에 대한 관계라면, R*는 R의 이행 폐쇄이다.

4.5 관계의 폐쇄 성질 【예제 4.38】 집합 A={1, 2, 3, 4}이고, 관계 R이 다음의 방향 그래프로 구성될 때 R의 이행 폐쇄 R*를 구하라.

4.5 관계의 폐쇄 성질 [풀이] R*={(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4) }

4.5 관계의 폐쇄 성질 【예제 4.39】 집합 {1, 2, 3, 4}에서 관계 R이 다음과 같은 관계 행렬로 주어졌을 때 방향 그래프, 반사 폐쇄, 대칭 폐쇄, 이행 폐쇄를 구하라.

4.5 관계의 폐쇄 성질 [풀이] (1) 방향 그래프는 다음과 같이 구성된다.

4.5 관계의 폐쇄 성질 (2) 반사 폐쇄 : 순서쌍 (1, 1), (4, 4) 추가 4.5 관계의 폐쇄 성질 (2) 반사 폐쇄 : 순서쌍 (1, 1), (4, 4) 추가 (3) 대칭 폐쇄 : 순서쌍 (3, 1) 추가 (4) 이행 폐쇄 (R*) : 경로에 존재하는 모든 순서쌍을 구한다 R*={(1, 1), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1), (4, 3), (4, 4)}

4.6 부분 순서와 속 정의 4-16 부분 순서 관계 집합 A에 대한 관계 R이 반사적, 반대칭적, 4.6 부분 순서와 속 정의 4-16 부분 순서 관계 집합 A에 대한 관계 R이 반사적, 반대칭적, 이행적이면 이를 부분 순서 관계라 하며, (A, R) 을 부분 순서 집합(partially ordered set ; poset) 이라 한다.

4.6 부분 순서와 속 【예제 4.40】 정수(Z)의 집합에 대한 관계 ≥ 가 부분 순서 관계임을 보여라. [풀이] 4.6 부분 순서와 속 【예제 4.40】 정수(Z)의 집합에 대한 관계 ≥ 가 부분 순서 관계임을 보여라. [풀이] 모든 정수 a에 대해, a ≥ a만족 : 반사 관계 a ≥ b, b ≥ a이면 a=b : 반대칭 관계 a ≥ b, b ≥ c 이면 a ≥ c : 이행 관계 ∴ 정수(Z)의 집합에서 관계 ≥ 가 부분 순서 관계임

4.6 부분 순서와 속 【예제 4.41】 다음의 방향 그래프(directed graph)가 부분 순서 관계인지를 판별하라. 4.6 부분 순서와 속 【예제 4.41】 다음의 방향 그래프(directed graph)가 부분 순서 관계인지를 판별하라. [풀이] (1), (2), (3) ː 부분 순서 관계

4.6 부분 순서와 속 정의 4-17 선형 순서 관계(linear order relation) 4.6 부분 순서와 속 정의 4-17 선형 순서 관계(linear order relation) 부분 순서 집합 (A, )에서 A의 원소 a, b가 a b 또는 b a이면 a와 b를 비교 가능 (comparable)하다고 하고, A의 모든 두 원소들이 비교 가능하면 A를 선형 순서 집합이라 하며, 관계 를 선형 순서 관계라고 한다.

4.6 부분 순서와 속 【예제 4.42】 부분 순서 집합 (Z, |)에서 정수 3과 4.6 부분 순서와 속 【예제 4.42】 부분 순서 집합 (Z, |)에서 정수 3과 9가 비교 가능한가? 또한 5와 7은 비교 가능한가? 단, 관계 | 는 mod(a, b)=0을 의미한다. [풀이] 9 | 3 : 9와 3은 비교 가능, 5 | 7, 7 | 5 : 비교 가능하지 않다. ∴ | 는 선형 순서 관계가 아니다.

4.6 부분 순서와 속 【예제 4.43】 부분 순서 집합 (Z, ≤ )는 비교 가능한가? [풀이] 4.6 부분 순서와 속 【예제 4.43】 부분 순서 집합 (Z, ≤ )는 비교 가능한가? [풀이] a, b가 정수, a ≤ b 또는 b ≤ a 만족, 선형 순서 관계

4.6 부분 순서와 속 ■ 유사 순서(quasi-order) :반사적이 아니고 이행적인 관계 “a b이고 b c이면 a c” 4.6 부분 순서와 속 ■ 유사 순서(quasi-order) :반사적이 아니고 이행적인 관계 “a b이고 b c이면 a c” ( 는 반대칭이고 이행적이다: a b이고 a ≠ b이면, a b)

4.6 부분 순서와 속 : 부분 순서 집합 (A, )의 방향 그래프 4.6 부분 순서와 속 : 부분 순서 집합 (A, )의 방향 그래프 : A의 원소인 정점과 b가 a를 커버할 때 a에서 b로의 간선으로 구성됨 원소 b는 원소 a를 커버(cover) : a b이고 A 내에 a c b인 c가 존재하지 않을 때

4.6 부분 순서와 속 【예제 4.44】 A = { 1, 2, 3, 4, 5, 6}이고, n | m은 mod(m, n) = 0 이라 하자. 부분 순서 집합 (A, |)를 하세 도표를 작성하라. 단, mod(m, n) = 0 은 m이 n으로 나누어 나머지가 0임을 뜻한다.

4.6 부분 순서와 속 [풀이] 하세 도표를 작성하면 다음과 같다.

4.6 부분 순서와 속 【예제 4.45】 P({a, b, c})를 멱집합이라고 할 때, 부분 순서 집합 (P, ⊆)를 하세 도표로 작성하라. [풀이] 하세 도표로 작성하면 다음 그림과 같다.

4.6 부분 순서와 속 【예제 4.46】 다음 도표가 하세 도표인지를 판별하라.

4.6 부분 순서와 속 [풀이] (1) : 하세 도표가 아니다. (2) : 하세 도표 (3) : 하세 도표가 아니다.

4.6 부분 순서와 속 ☞ 정리 4-11 모든 유한 부분 순서 집합은 하나의 하세 도표로 표시할 수 있다.

4.6 부분 순서와 속 정의 4-18 극대 원소(maximal) 와 극소 원소(minimal) 4.6 부분 순서와 속 정의 4-18 극대 원소(maximal) 와 극소 원소(minimal) (P, )를 부분 순서 집합이라 하자. P 내의 원소 x에 대하여 x y인 y가 존재하지 않을 때 원소 x를 P의 극대 원소라 하고, y x인 y가 존재하지 않을 때 원소 x를 P의 극소 원소라고 한다.

4.6 부분 순서와 속 ■ 부부분 순서 집합(subposet) 4.6 부분 순서와 속 ■ 부부분 순서 집합(subposet) 부분 순서 집합 P의 부분 집합 S는 P의 부분 순서를 계승받고, 그 자체가 부분 순서 집합이 된다. 왜냐하면 반사적 · 반대칭적 · 이행적 특성은 P의 모든 원소에 적용되기 때문이다.

4.6 부분 순서와 속 【예제 4.47】 [예제 4.44]의 부분 순서 집합 {1, 2, 3, 4, 5, 6}의 부부분 순서 집합인 (1) {2, 3, 4, 5, 6}과 (2) {1, 2, 3, 6}을 하세 도표로 작성하라. [풀이]

4.6 부분 순서와 속 【예제 4.48】 집합 {a, b, c}의 공집합을 제외한 모든 진부분 집합은 부분 순서 ⊆ 를 갖는 멱집합 P({a, b, c})의 부부분 순서 집합이다. 이를 하세 도표로 작성하라.

4.6 부분 순서와 속 [풀이]

4.6 부분 순서와 속 정의 4-19 최대 원소(largest element;maximum) 4.6 부분 순서와 속 정의 4-19 최대 원소(largest element;maximum) 와 최소 원소(smallest element;minimum) S : 부분 순서 집합 (P, )의 부부분 순서 집합, 최대 원소 : ∀s∈S, s M인 원소 M이 S 내에 존재 M = max(S) 최소 원소 : ∀s∈S, m s인 원소 m이 S 내에 존재 m = min(S)

4.6 부분 순서와 속 [예제 4.44] 최대 원소 : 존재하지 않는다 (극대 원소간의 의 관계가 없기 때문) 4.6 부분 순서와 속 [예제 4.44] 최대 원소 : 존재하지 않는다 (극대 원소간의 의 관계가 없기 때문) 최소 원소 : 1 [예제 4.45] 최대 원소 : {a, b, c}, 최소 원소 : { }

4.6 부분 순서와 속 정의4-20 상한(upper bound)과 최소 상한 4.6 부분 순서와 속 정의4-20 상한(upper bound)과 최소 상한 (least upper bound), 하한(lower bound)과 최대 하한(greatest lower bound) S : 부분 순서 집합 (P, )의 부부분 순서 집합 (1) ∀s∈S, s x인 ∃x∈P, x : P 내에서 S에 대한 상한

4.6 부분 순서와 속 (2) x : P 내에서 S에 대한 상한 y : P 내에 있는 S에 대한 모든 상한에 대하여, 4.6 부분 순서와 속 (2) x : P 내에서 S에 대한 상한 y : P 내에 있는 S에 대한 모든 상한에 대하여, x y일 때 x를 P 내에 있는 S의 최소 상한 x = lub(S) (3) ∀s∈S, z s인 ∃z∈P, z : P 내에서 S에 대한 하한 (4) z : P 내에서 S에 대한 하한 w : P 내에 있는 S에 대한 모든 하한에 대하여, w z일 때 z를 P 내에 있는 S의 최대 하한 z = glb(S)

4.6 부분 순서와 속 【예제 4.49】 [예제 4.44]와 같이 부분 순서 집합({1, 2, 3, 4, 5, 6}, |)이 있을 때, 다음과 같은 부부분 순서 집합에 대하여 상한, 최소 상한, 하한, 최대 하한을 각각 구하라. (1) {2, 3} (2) {4, 6} (3) {3, 6}

4.6 부분 순서와 속 [풀이] (1) 상한: 6, 최소 상한: 6, 하한: 1, 최대 하한: 1 4.6 부분 순서와 속 [풀이] (1) 상한: 6, 최소 상한: 6, 하한: 1, 최대 하한: 1 (2) 상한: 없음, 하한 : 2, 1, glb({4, 6}) = 2 (3) 상한: 6, lub({3, 6}) = 6 하한 : 3, 1, glb({3, 6 }) = 3

4.6 부분 순서와 속 【예제 4.50】 다음 하세 도표에 해당하는 부분 순서 집합 P에 대하여, 다음과 같은 부부분 순서 집합이 있을 때, 상한, 최소 상한, 하한, 최대 하한을 각각 구하라. (1) {b, c} (2) {d, f} (3) {d, e, f} (4) {b, d, e, f}

4.6 부분 순서와 속

4.6 부분 순서와 속 [풀이] (1) 상한: d, e, g, h. 최소 상한 : 없음. 하한 : 없음 4.6 부분 순서와 속 [풀이] (1) 상한: d, e, g, h. 최소 상한 : 없음. 하한 : 없음 (2) 상한: h. lub({d, f})=h. 하한: a, c, 최대 하한: 없음 (3) 상한, 최소 상한: h, 하한: a, c, 최대 하한 : 없음 (4) 상한, 최소 상한: h, 하한, 최대 하한 : a

4.6 부분 순서와 속 정의 4-21 속(lattice) 부분 순서 집합 (P, )에서 P의 임의의 원소 4.6 부분 순서와 속 정의 4-21 속(lattice) 부분 순서 집합 (P, )에서 P의 임의의 원소 x, y에 대하여 {x, y}의 glb와 lub가 각각 하나씩 존재한다고 하면, (P, )을 속이라고 한다. 이 때, lub({x, y}) x∨y, glb({x, y})=x∧y로 나타내며, (∨또는 : 합 연산자, ∧ 또는 *: 곱 연산자)

4.6 부분 순서와 속 【예제 4.51】 P({a, b, c})를 멱집합이라 할 때, 부분 순서 집합 (P, ⊆)이 속인지 판별하라. [풀이] [예제 4.45]의 하세 도표를 참고하면, lub({{a}, {c}})={a}∨{c}={a, c} lub({{a, b}, {a, c}})={a, b}∨{a, c}={a, b, c} glb({{a, b}, {c}})={a, b}∧{c}= ø glb({{a, b}, {b, c}})={a, b}∧{b, c}={b} 결국, 부분 순서 집합 (P, ⊆)은 속이다.

4.6 부분 순서와 속 ■ 일반적으로 임의의 집합 S에 대하여 (P(S), ⊆): 속 4.6 부분 순서와 속 ■ 일반적으로 임의의 집합 S에 대하여 (P(S), ⊆): 속 lub({A, B, …, Z})=A∪B…∪Z glb({A, B, …, Z})=A∩B…∩Z

4.6 부분 순서와 속 【예제 4.52】 A={1, 2, 3, 4, 5, 6}이고, n | m은 mod(m, n)=0이라 하자. 부분 순서 집합 (A, |)이 속인지 판별하라. 단, mod(m, n)=0은 m이 n으로 나누어짐을 말한다. [풀이] {3, 4}는 상한이 존재하지 않으므로 속이 아니다.

4.6 부분 순서와 속 【예제 4.53】 P를 양의 정수라 하고 n | m은 mod(m, n)=0이라 할 때, 부분 순서 집합 (P, |)이 속인지 판별하라. [풀이] lub({m, n}) : m, n의 최소 공배수 glb({m, n}) : m, n의 최대 공약수 (예), lub({12, 10})=60, glb({12, 10})=2 ∴ ( P, | ) : 속

4.7 n-항 관계의 응용 정의 4-25 도메인, 카티션 프로덕트, 릴레이션 도메인(domain) : D1, D2, … , Dn 으로 표기하며 값들의 집합 카티션 프로덕트(Cartesian product) : D1 x D2 x … x Dn 으로 표기하며 n-튜플의 집합 릴레이션(relation) : R로 표기, R ⊆ D1xD2x … xDn P171 – p177 참조

4.7 n-항 관계의 응용 [예] 학번, 성명, 전공, 평균점수 : 도메인 * 카티션 프로덕트(4-튜플)

4.7 n-항 관계의 응용 [예] 학생 릴레이션

4.7 n-항 관계의 응용 [예] 학생 릴레이션 : 학생 테이블 릴레이션 스킴(내포) : 학번, 성명, 전공, 평균평점(애트리뷰트) * 테이블의 논리적 구조를 기술한 것으로 정적 릴레이션 인스턴스(외포) : 1, 이영호, CS, 3.83 (n-튜플들의 집합) * 현실세계의 어느 한 시점에서의 릴레이션의 내용 기술, 동적