이산수학 요점정리 (2/5)

Predicate logic (술어 논리)

1. Basics / 기초

• Predicates (술어) : 속성과 관계를 나타낸다.
• 명제와는 달리, 주어와 술어를 구분하여 참 또는 거짓을 판단한다.

• 술어는 한정된 수의 변수를 포함하는 문장이며 변수에 대해 특정 값이 대체 될 때 명령문이 된다.
• 술어에는 하나 이상의 변수가있을 수 있다. 예 : student (x), mother (x, y)

• 술어 계산 (Predicate Calculus) : 명제 함수(Propositional Function)를 이용한다.

• 예) She is a student.
• 주어 : She -> x
• 술어 : is a student. -> P(x)
• P(x) : x is a student.
• P 자체는 명제가 아니고, 변수 x가 적절한 값으로 치환되면 결과적으로 명제가 된다.

• 술어 변수의 도메인(domain)은 해당 변수로 대체 될 수있는 모든 값의 세트다.
• 술어의 진리 집합(Truth Set)은 술어가 참인 변수 도메인의 모든 값의 집합이다.

• P (x) → Q (x) 는 P (x)의 진리 집합의 모든 요소가 Q (x) 의 진리 집합에 있는 요소이기도하다는 것을 의미한다.
• P (x) ↔ Q (x) 는 P (x)의 진리 집합이 Q (x)의 진리 집합과 동일하다는 것을 의미한다.

2. Quantifiers / 한정사

• 한정사 : 변수 x가 가질 수 있는 값들의 양을 제한하는 기호

• Universally quantified statements (전체 한정 서술)
• Universally quantifier (전체 수량자) 기호 : ∀
• 술어 P(x)가 x의 전체 집합 U에 대하여 성립하여야 한다.
• ∀xP(x)이 참이 되기 위한 필요충분 조건은
• ∀xP(x) : “모든 x에 대하여 P(x)는 참이다”

 

• Existentially quantified statements (존재 한정 서술)
• Existentially quantifier (존재 수량자) 기호 : ∃
• ∃xP(x) : “어떤 x에 대하여 P(x)가 참인 x가 존재한다.”
• ∃xP(x) 이 참이 되기 위한 필요 충분 조건은 전체 집합 U안에 P(x)를 만족시키는 x가 적어도 한 개 존재하여야 한다.

 

요약

• 전체 한정사 : 모든 것에 대하여 x는 참이다..
• 존재 한정사 : x가 적어도 하나는 존재한다.

• ∀x ∈ H, Q(x) 모든 인간은 동물이다.
• ∃x ∈ H, P(x) 생각하는 인간이 존재한다.
• ∀x ∈ H, ( P(x)∧Q(x)) 모든 인간은 생각하는 동물이다.
• ∃x ∈ H, ~P(x) 생각하지 않은 인간도 있다.

3. Negation of quantifiers / 한정사의 부정

• 전체수량자(한정자)의 부정
• ~(∀x∈ D, P(x) ) ≡ ∃x∈ D, ~P(x).
• p(x)가 성립하지 않는 x가 존재한다.

• 존재수량자(한정자)의 부정
• ~( ∃x∈ D, P(x) ) ≡ ∀x∈ D, ~P(x).
• 모든 x는 p(x)가 성립하지 않는다.

 

나머지는 (3/5)에서... ㅠ.ㅠ

Problems on Logic (논리 문제)

1. Propositional logic / 명제 논리

2. Predicate logic / 술어 논리

3. Additional problems / 추가 문제

Sequences (시퀸스)

1. Sequences / 시퀸스

2. Definitions / 정의

3. Recurrence relation / 복귀 관계

4. Arithmetic and geometric sequences / 산술 및 기하학적 시퀸스

5. Problems / 문제

6. Inductive proof / 귀납 증명

Sets and Relations (집합과 관계)

1. Sets, Venn diagrams / 집합, 벤 다이어그램

2. Basic set identities / 기초 집합 아이덴티티

3. Set partitions, Cartesian product of sets, Power sets / 집합의 분할, 집합의 데카르트 곱, 멱집합

4. Relations // 관계

5. Properties of binary relations on a set A / 집합 A의 이항 관계 속성

 

 

참고자료

• http://www.aistudy.co.kr/ai/logic_dean.htm
• http://www.kocw.net/home/search/kemView.do?kemId=1165096