명제(proposition) = 문장인데 참과 거짓을 구분 할 수 있는 문장
EX)
앉아 - 명제가 아님
의자는 앉는 용도야 - 명제임
자동차는 살아있어 - 명제임(거짓이기 때문)
지금 몇시노? - 명제 아님명제를 변수로 표현 : p, q, r, s 등등등
명제가 참이면 T 거짓이면 F
명칭(?):
- 복합명제: 하나 또는 여러 개의 명제를 조합하여 만듦.
- Nagation(부정): ㄱ
- Conjuction(논리곱, 명제끼리 곱함을 뜻함, or): ^
- Disjuntion(논리합, 명제끼리 더함, and): ∨
- Implication(함축, if): ->
- Biconditional(상호충족, and이나 T,F 구분 없이 같은 결과일 때): <->
부정
명제 p의 부정은 ㄱp
p = 지구는 둥글다
ㄱp(지구는 둥글지 않다) = F
논리곱
p와 q의 논리곱은 p ^ q
And문 - p q 둘 다 T여야 T
T -> 1 F -> 0으로 생각하면 좋음
| p | q | p^q |
|---|---|---|
| T | F | F -> 1 * 0 = 0 |
| T | T | T -> 1 * 1 = 1 |
| F | F | F -> 0 * 0 = 0 |
| F | T | F -> 0 * 1 = 0 |
논리합
p ∨ q로 표기
or 문 - 둘 중 하나라도 T면 T
- 포괄적 논리합(or, ∨) 둘 중 하나라도 T면 T
- 베타적 논리합(xor, ⊕) 둘 중 하나라도 F면 F
함축, 조건문
p(가정 or 추측) -> q(결론 or 결과)
if p then q : (p가 T라면 q이다)
EX)
p = i am home / q = it's raining
p -> q = if i am home then it's raining
만약 내가 집에 있다? = p
만약 비가 온다? = q
p -> q == T
p = T, q = F
p -> q == F
p = F, q = T
p -> q == Tp와 q는 관계가 없을 수 있음.
p와 q의 진리값(T or F)만 따름
p가 F면 무조건 T - 이 상황은 공허한 참이라고 함
q -> p: 역(q, p 위치 전환)
ㄱq -> ㄱp: 대우(q, p 위치 전환 + ㄱ 포함)
ㄱp -> ㄱq: 이(ㄱ 포함)
- 상호조건문
p <-> q는 p if and only q라 함
진리표
변수가 3개면 2**3
EX)
p ∨ q -> ㄱr
p,q,r이 변수로 2 ** 3 == 88개의 진리표 변수가 나옴
p, q, r, ㄱr, p∨q, p∨q->ㄱr 순서로 만듦
(*서식 컬럼은 순서 상관 없는 듯)
동치(두 명제가 항상 같은 진리 값을 가지는 것)
p -> q == F, ㄱq -> ㄱp == F (동치)
p -> q == T, ㄱq -> ㄱp == T (동치)
p -> q == F, ㄱq -> ㄱp == T (동치 아님)
p -> q == T, ㄱq -> ㄱp == F (동치 아님)논리 연상자 우선 순위
ㄱ 1
^ 2
∨ 3
-> 4
<-> 5
후순위 연산자를 실행하려면 선순위 연산자의 값이 필요함
p ∨ q -> ㄱr와 (p∨q) ->ㄱr는 동치
명제 논리의 응용
영어 문장을 논리로 변환
영어 문장에서 명제를 분활하고 논리로 변환하는 작업
if i go to Harray's or to the country, I will not go shopping
-> 명제 분활
p: i go to Harray's
q: to the country
r: go shopping
논리 변환 : p ^ q -> ㄱr
시스템 명세
자연어로 요구사항을 접수 받아 시스템 개발에 사용되는 정확하고 모호하지 않은 명세
요구사항을 받고 그걸 정확하고 모호하게 정리한 것.
프로젝트 아이디어 구상 -> 시스템 명세 작성
아이디어는 정한 당시엔 어떤 기능을 만들어야 하고 이런 것들이 모호하기에 시스템 명세를 작성함으로써 모호하지 않고 정확한 값을 얻으려 함
시스템 명세의 일관성
여러 명제는 각 명제가 참이 되도록 명제 변수에 진리 값을 할당할 수 있는 경우 "일관성" 이라고 한다.
진리표 중 모든 명제가 "참"인 경우가 있다면 일관성이 있다고 한다.
사용 예시:
-
부울 탐색 - 검색시 And, Or, Not을 사용하여 검색 함으로써 내가 원하는 값을 더 쉽게 하도록 함
-
논리 퍼즐 - 퍼즐을 논리를 사용하여 풀어나감
-
논리 회로 - 회로 설계시 명제들을 쌓아가며 결론적으로 복합명제가 되는 것과 같음
명제의 동치
항진명제 - 항상 참인 명제
ex) p∨ㄱp
모순 - 항상 거짓인 명제
ex) p^ㄱp
불확정명제 - 경우에 따라 참과 거짓이 갈리는 명제
- 논리적 동치
p <-> q 가 항진명제일 경우, 즉 둘 다 참일 경우 p, q는 논리적 동치
p <=> q or p ≡ q
드모르간의 법칙(외우면 편함)
1. ㄱ(p ^ q) ≡ ㄱp ∨ ㄱq
2. ㄱ(p ∨ q) ≡ p ^ q
논리적 동치를 증명할 때는 진리표 쓰삼 ㅇㅇ
- 명제의 만족 가능성
복합명제의 진리값이 참인 경우가 존재하는지 확인하는 것
솔루션 쓸 땐 만족가능함. q에 F를 넣고 p에 T를 넣으면 됨
이라는 식으로 작성해야하는 듯
