[수학 리부트] 논리의 기초

논리의 기초

명제

• 정의 : 참인지 거짓인지 판별할 수 있는 문장이나 수식
  • p,q,r같은 영문자로 표시
• 진리값 : 명제의 참 거짓
• 명제에도 기본적인 연산이 존재 (논리연산)
• 진리표 : 논리연산의 결과를 표 형태로 알아보기 위해 나타낸 것.

• 항진명제 : 항상 참인 명제
• 모순명제 : 항상 거짓이 되는 명제
• 부정 연산한 결과를 다시 부정 연산하면 원래 명제의 진리값으로 돌아감

드 모르간의 법칙(De Morgan's law)

• not (A or B)=(not A) and (not B)
• not (A and B)=(not A) or (not B)

항등원 : 논리합에는 F, 논리곱에는 T라는 항등원이 존재, 그러나 숫자와 다르게 자기 자신에 대한 논리합과 논리곱 연산은 다시 자신으로 돌라옴

논리 연산의 법칙 : 교환법칙, 결합법칙, 분배법칙에 모두 적용

 

XOR 연산 (배탁적 논리합)

• 두 명제 중 어느 한쪽만 참일때 결과가 참
• 두 명제중 어느 한쪽만 참이면 결과가 참이기에 교환법칙 성립이며 결합법칙도 성립
• T와의 XOR연산은 부정 연산자처럼 동작하지만, F와의 연산은 원래 명제의 진리값을 그대로 보존함.
• 자기 자신과 XOR연산은 F
• 명제 p에 q를 XOR연산하고 다시 q를 XOR연산하면 원래의 결과로 돌아감

 

집합의 종류와 연산

• 집합 :  개별적인 개체들의 모임
• 원소 : 집합을 이루는 개체
• 원소나열법 : 집합에 속한 원소들을 나열. 순서는 상관없지만 같은 원소를 중복하지 않음조건제시법 : 집합의 원소들에 공통되는 조건 기술
• 크기 : 집합 A에 속한 원소의 개수 (기호 : |A|)
• 유한집합 : 원소의 개수가 유한 
• 무한 집합 : 원소의 개수가 무한 (EX. 자연수 중 3의 배수의 집합)
• 공집합(∅) : 집합에 아무 원소도 없는 경우. 공집합 기호 주위에 중괄호를 두르지 않음. 중괄호를 두르는 경우 공집합을 원소로 갖는 집합을 의미
• 상동 : A⊂B와 B⊂A가 동시에 성립. A = B로 나타냄
• 진부분 집합 : B에 A의 원소가 아닌 것도 포함되어 있을 경우
• 합집합 : 여러 집합의 원소를 모두 모은 집합

  

• 교집합 : 집합 A, B의 공통된 원소들만 골라낸 집합

  

• 서로소 : 두 집합 간에 공통된 원소가 하나도 없는 경우
• 전체집합(U) : 기본 전제가 되는 집밥
• 여집합 : 전체집합(U)에서 A를 제외한 것을 A의 여집합이라고 칭함
• 차집합 : 집합 A로 부터 B와 공통인 부분을 제외한 것.

  

집합의 드 모르간 법칙

집합의 연산

1. 교환 법칙 : 합집합과 교집합의 경우 성립

2. 결합법칙 : 합집합과 교집합의 경우 성립

3. 분배법칙 : 합집합과 교집합의 경우 성립