이산수학 1. 개요 - swkim0128/PARA GitHub Wiki
영상: https://www.youtube.com/playlist?list=PLRx0vPvlEmdDgOIBt9MKQl-uMVrxtac4n
- 불연속적인 숫자를 다루는 수학
- 컴퓨터를 위한 수학, 참과 거짓으로 살펴보는 컴퓨터 수학, 전산, 정보 수학, 1학년이나 처음 컴퓨터를 배우는 입장에서 배우게됨, 자료구조 또는 알고리즘의 베이스, 논리적 사고, 컴퓨팅 사고력 향상
- 보편적인 컴퓨터 수학
진실 혹은 거짓으로 진리를 구분할 수 있는 문장
연산자는 명제를 연산하기 위한 도구
기본 연산자의 종류
-
부정, Not(￢ )
명제의 진리값을 뒤집어줌
p ⇒ 참
￢p ⇒ 거짓
-
논리곱, And( ^ )
그리고
p ^ q 일때 p,q모두 참일 경우에만 p ^ q⇒ 참 이다 나머지는 거짓
-
논리합, Or( v )
또는
p v q 일때 p,q모두 거짓일 경우에만 p v q⇒ 거짓 이다 나머지는 참
-
배타적논리합, Exclusive or( ⊕ )
p, q가 다르면 참
p, q가 같으면 거짓
-
함축, 조건명제, Implication (→)
p → q : p일때 q이다
조건 → 결과 (ex) 비가 올때 우산을 쓴다)
참 → 거짓 ⇒ 거짓 나머지 경우는 참
-
쌍방 조건명제, Biconditional (↔)
p, q가 같으면 참
p, q가 다르면 거짓
⊕와 반대
잘 안쓰임
각 명제 사이의 관계식의 진리값을 보여주는 표
조건명제에서 사용함
하나의 명제를 변형해 표현함
- 본 명제 p → q
- 역 q → p
- 이 ￢p → ￢q
- 대우 ￢q → ￢p 대우가 참이면 본 명제도 참 ( 대우와 본 명제는 반드시 같은 명제를 가짐)
왜 ?
증명을 돕기 위함
증명하기 어려운 본 명제를 대우를 이용해 증명 가능
ex)
명제 "30이 10보다 크다면, 30은 50보다 작다"
p: 30>10
q: 30<50
p → q : 30이 10보다 크다면, 30은 50보다 작다 ⇒ 참 → 참 ⇒
**참
역:
**q → p : 30이 50보다 작다면, 30은 10보다 크다 ⇒ **참
이:
**￢p → ￢q : 30이 10보다 작거나 같다면, 30은 50보다 크거나 같다 ⇒ **참
대우:
**￢q → ￢p : 30이 50보다 크거나 같으면, 30은 10보다 작거나 같다 ⇒ **참**역, 이는 본 명제와 다른 명제가 나올 수 있지만 대우는 반드시 같은 명제를 가짐
논리적으로 일치한다
같은 의미를 가진 더 쉬운 명제를 발견하는데 사용
ex) 2+2+2+2+2+2+2+2+2+2 와 2*10 은 동치이다
동치법칙 + 함축 법칙 : p → q === ~p v q
ex)
(p→q)^(p→~q)를 동치법칙을 이용한 간소화하라
- (p→q)^(p→~q)
⇒ (~p v q)^(~p v ~q) : 함축법칙
⇒ ~p v (q ^ ~q) : 분배법칙
⇒ ~p v F : 부정법칙
⇒ ~p : 항등법칙