이산수학[명제 ~ 관계]

●명제논리 : 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 True or False 판단

●술어논리 : 주어와 술어로 구분하여 True or False 판단

             ○술어 한정자 : 술어를 나타내는 방법 중에서 변수의 범위를 한정시키는 것

             ○ ∀ = 모든 것에 대하여

             ○ ∃ = 존재한다.

●명제 : True or False를 객관적이고 명확하게 구분할 수 있는 문장 혹은 수식

             ○이진논리 : T,F 두가지 진리 값만을 가지는 논리식

●단순명제 : 하나의 문장or식으로 구성되어 있는 명제

●합성명제 : 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제

●논리연산자

연산자 이름	기호	의미
부정	~	NOT
논리곱	⋀	AND
논리합	⋁	OR
배타적 논리합	⊕	Exclusive OR
조건	→	If ~ then
쌍방조건	↔︎	If and only if (iff)

●논리적 동치관계

                 

논리적 동치관계	법칙 이름
p⋁q⇔q⋁p p⋀q⇔q⋀p p↔︎q⇔q↔︎p	교환법칙
(p⋁q)⋁r⇔p⋁(q⋁r) (p⋀q)⋀r⇔p⋀(q⋀r)	결합법칙
p⋁(q⋀r)⇔(p⋁q)⋀(p⋁r) p⋀(q⋁r)⇔(p⋀q)⋁(p⋀r)	분배법칙
p⋁(p⋀q) ⇔ p p⋀(p⋁q) ⇔ p	흡수법칙
p→q ⇔ ~p⋁q	드 모르간 법칙
p→q ⇔ ~q→~p	대우법칙

 

●항진명제 : 명제들의 진리 값과 관계 없이 항상 진리 값이 T인 명제

●모순명제 : 명제들의 진리 값과 관계 없이 항상 진리 값이 F인 명제

 

●추론 : 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도하는 방법

             ○유효추론 : 주어진 전제가 참이고 결론도 참인 추론

                  ○허위추론 : 추론의 결론이 거짓인 추론

 

●추론법칙

추론 법칙	법칙 이름
p p->q ∴q	긍정법칙
~q p→q ∴q	부정법칙
p→q q→r ∴p→r	조건 삼단 법칙
p⋁q ~p ∴q	선언 삼단 법칙
(p→q)⋀(r→s) ~q⋁~s ∴~p⋁~r	파괴적 법칙
(p→q)⋀(r→s) p⋁r ∴(q⋁s)	양도 법칙
p ∴p⋀q	선접 법칙
p⋀q ∴p	분리 법칙
p q ∴p⋀q	연접 법칙

●집합의 연산법칙

|A∪B|=|A|+|B|-|A∩B|

|A∩B|=|A|+|B|-|A∪B|

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩B|-|B∩C|-|A∩B∩C|

|A-B|=|A∩BC|=|A|-|A∩B|

|A×B|=|A|-|B|

●반사관계↔︎비반사관계 : If a∈A → (a,a)∈R // If a∈A, (a,a)∉R

●대칭관계 // 반대칭관계 : If x,y∈A → (x,y)∈R⇒(y,x)∈R // If x≠y → (x,y)∈R, (y,x)∉R

●추이관계 : A={x,y,z}일 때, If (x,y)∈R, (y,z)∈R, (x,z)∈R

●추이 클로우저(R+)// 반사 및 추이 클로우저(R*) : R+=추이관계가 성립// R*=반사 및 추이관계가 성립

●동치관계 : 관계 R이 반사/대칭/추이 관계가 모두 성립하는 관계

●동치류([x]) : [x]={y|(x,y)∈R} ([x]=R에 대한 x의 동치류, 단, R은 동치관계이다.)

●몫집합(A/R) : 동치류의 모임

●분류 :

●mod합동 : 두 정수가 어떤 수로 나누었을 때 나머지가 같음을 나타내는 관계

                          a≡b(mod n)=“정수 a와 b를 n으로 나눴을 때 나머지가 같다”

                                          =”a와 b의 차이가 n의 배수다”

●부분 순서 관계(A,≲) : 반사/반대칭/추이 관계가 성립하는 관계

                    ○비교가능 : 집합A의 두 원소 x,y가 x≲y or y≲x이면 x와 y는 비교 가능

                    ○선형 순서 집합 : 집합 A의 모든 두 원소가 비교 가능하면 A=선형순서집합

                    ○선형 순서 관계 : 선형 순서 집합인 경우, 관계≲라고 함.
●하세도표 : A={x,y,z}일 때, x≲y, y≲z를 만족하는 y가 존재하지 않을 경우에만 x≲z의 연결을 그림.