[수학리부트] 논리 (명제, 진리집합, 논리연산자, 논리연산식, 집합연산식, 곱집합, 동치관계)

명제

• 조건명제 : 말 그대로 어떤 조건이 충족되는지 여부
  • p(가정) -> q(결론) 로 표현 (p이면 q이다)
• 명제의 역 : 원래의 명제에서 가정과 결론을 바꾼 것 (q -> p)
• 명제의 이 : 명제의 부정 (~p -> ~q)
• 명제의 대우 : 명제에서 가정과 결론도 바꾸고 부정한 것 (~q -> ~p)

• 명제함수 : x에 대해 참,거짓이 대응되는 일종의 함수. 미지의 값을 인자로 두어 p(x), q(x) 같은 함수의 형태로 쓰기도 함.
  • p(x) : 2ˣ < 10 (x ∈ N)
• 진리집합 : 전체집합의 원소 중 명제함수를 참으로 만드는 원소들의 집합
  • 정의 : P = {x | x  ∈ U, p(x)}
  • 위의 경우 진리집합은 {1,2,3} (4이상은 거짓이 됨)
• 한정자 : 명제함수의 인자 범위 규정
  • ∀(for all) : 인자가 속하는 전체집합의 '모든'원소에 대해 그 명제가 성립함을 주장하는 기호
    • ∀x ∈ N, 2ˣ < 10   -> x가 4이상이면 성집하지 않으므로 전체적으로 거짓
  • ∃(there exists) : 인자가 속하는 전체집합 중에 그 명제함수를 참으로 만드는 원소가 '하나라도 존재'
    • ∃x ∈ N, 2ˣ < 10  -> 해당 명제함수를 참이 되게 하는 자연수 x가 하나 이상 존재하므로 참 (x=1,2,3)
• 반례 : 명제함수를 거짓이 되게 하는 사례

조건 명제의 진리집합

• p(x) : x는 사람이다
• q(x) : x는 포유류이다
• r(x) : x는 동물이다.

=> p(x) -> q(x) : x가 사람이면, x는 포유류이다.

• 진리집합(p(x) -> q(x)) : {x|x ∈ U, ㄱp(x) V q(x)} = Pᶜ ∪ Q
  • 이는 P이면 항상 Q이어야 한다는 것으로 곧 P ⊂ Q로 나타낼 수 있다.
  • 위에서 p(x) -> q(x) -> r(x)도 성립하는데 이는 p(x) -> r(x)로 나타낼 수 있다. 이를 삼단논법이라고 한다.
• 필요조건 : p(x) -> q(x) 일때 p(x)가 참이면 반드시 q(x)여야하며, 이때 q(x)를 p(x)가 되기 위한 필요조건이라고 함
• 충분조건 : p(x) -> q(x) 일때 p(x)가 충족되었으면 q(x)는 자동으로 참이 되며, 이때 p(x)를 q(x)가 되기위한 충분조건이라고 한다.
• 필요충분 조건 : 두 명제함수가 서로에게 필요조건이자 충분조건인 경우
  • p(x) ⇔ q(x)로 표현 (겹화살표)
• 쌍방조건 : q (p이면 q이고, q이면 p이다) : p와 q가 같은 값일때 참, 서로 다른 값이면 거짓.
  • p ↔ q (일반화살표)로 표현
• 배타적 합(exclusive or) :  p와 q 중 어느 하나만 참일 때 참, 그 외에는 거짓, p⊕q로 표기(p 배타적 합 q):

CF) 논리 연산자

이름	기호	설명
Negation(부정)	~ 혹은 ㄱ	Not
Conjunction(논리곱)	∧	AND
Disjunction(논리합)	∨	OR
Exclusive OR (배타적논리합)	⊕	Exclusive OR
Condition(조건)	->	If … then
Bicondition(쌍방조건)	↔	If and only if( iff )

 

진리집합의 연산

• 항진명제 : 합성명제의 진리값이 항상 참인 명제 ( T로 표현 )
• 모순 명제 : 합성명제의 진리값이 항상 거짓인 명제 ( F로 표현 )

논리연산식과 집합의 연산식 정리

	논리연산식	집합의 연산식
항진명제	p v ¬p ≡ T	A ∪ Aᶜ = U
모순명제	p ∧ ¬p ≡ F	A ∩ Aᶜ = Ø
이중 부정	¬¬p ≡ p	(Aᶜ)ᶜ = A
드 모르간 법칙	¬ (p v q) ≡ ¬p ∧ ¬q ¬ (p ∧q) ≡ ¬p v ¬q	(A ∪ B)ᶜ = Aᶜ ∩ Bᶜ  (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
항등원	p v F ≡ p p ∧ T ≡ p	A ∪ Ø = A A ∩ U = A
자기 자신과 연산	p v p ≡ p p ∧ p ≡ p	A ∪ A = A A ∩ A = A
교환법칙	p v q ≡ q v  p p ∧ q ≡ q ∧ p	A ∪ B = B∪ A  A ∩ B = B ∩ A
결합법칙	(p v q) v r ≡ p v (q v r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)	(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C)
분배법칙	p v (q ∧ r) ≡ (p v q)  ∧ (p v r) p ∧ (q v r) ≡ (p ∧ q)  v (p ∧ r)	A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

• 쌍대 : 대응되는 한 쌍의 등식 (EX. A ∪ Ø = A, A ∩ U = A)
• 쌍대성 원리 : 어떤 등식이 참이면 그 등식의 쌍대도 역시 참
  • ∪ 는 ∩으로, ∩은 ∪로 모두 바꾼다
  • 전체집합은 공집합으로, 공집합은 전체집합으로 모두 바꾼다.

부분집합의 성질

• 멱집합(P(A)) : 어떤 집합 A의 모든 부분집합을 원소로 가지는 집합
  • A={a,b,c} 일때, A의 멱집합은 아래와 같다.
    P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
  • 임의의 유한집합에 대해서 그 크기가 ∣A∣=n 이라고 할때, 부분집합의 개수는 2ˣ 개가 된다. 임의의 정수 n(n≥0)에 대해서 2ˣ>n이 항상 성립하므로, 임의의 유한집합에 대해서 멱집합의 크기는 원래의 집합의 크기보다 항상 더 커진다.
• 분할 (원래 집합 A의 분할) 
  • P의 모든 원소는 서로 서로소
  • P의 모든 원소를 U한 결과가 A와 같을 것
  • 다만 P의 원소중에 ∅은 없을것
  • 따라서P ={{a,b},{c}}는 집합 A= {a,b,c}의 한 분할이다.

곱집합과 관계

• A = {1,2}, B = {1,2,3} 이 있을 때
• A X B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}

• 순서쌍 : 위와 같이 순서가 있는 쌍으로 원소를 묶은 것
• 곱집합(데카르트곱)(A X B) : 두 집합으로 부터 순서쌍을 만들어 내는 것
  • 이것은 실수의 집합 R끼리 연산시킨 곱집합 R x R 이기도 하므로 아래처럼 표현가능하다.
  • 또한 셋이상의 집합에서도 곱집합을 만드는 것도 가능하다.

• 관계 : 순서상 (a, b)가 곱집합의 부분집합에 속한다면 '곱집합의 부분집합'을 일컽은다.
  • 순서상 (a,b)가 곱집합의 부분집합 R에 속한다면 aRb 로 속하지 않는다면 aRb로 나타낸다.

관계의 속성과 동치류

• 어떤 집합 A가 있는데 관계 R이 곱집합 AxA의 부분집합으로 정의된 경우 
  • 집합 A위의 관계 R 로 표현
• 특정조건에 따라 속성을 부여할 수 있다.
  • R은 반사적(reflexive) : 모든 a ∈ A에 대해 aRa가 성립
  • R은 대칭적(symmetric) : 모든 a,b ∈ A에 대해 aRb -> bRa가 성립
  • R은 반대칭적(antisymmetric) : 모든 a,b ∈ A에 대해 (aRb ∧ bRa) -> (a - b)
  • R은 추이적(transitive) : 모든 a,b,c ∈ A에 대해  (aRb ∧ bRc) -> (aRc)
• 동치관계 : 반사성, 대칭성, 추이성을 모두 만족하는 경우
  • 일상에서 '같다'고 표현하는 개념을 수학적으로 일반화한것
  • a ~ b로 표현
• 동치류 : 동치관계로 이어진 원소들이 모인 집합