명동 스터디_이산수학_2(명제와 논리)

명동 스터디 : 기초를 숙련한지 너무 오래되어 컴퓨터공학부 커리큘럼의 필수 과목과 관련된 공부를 통해 기초를 숙련하고 숙련된 기초를 통해 프로젝트 진행을 하기 위한 4명의 스터디 모임

 

기원 : ki-w0n.tistory.com

백범 : https://long-shift-6b9.notion.site/dbf9ea3ec9fd49379e43c127e470123a

찬형 : https://memo.chanhyung.kim/407d7b36c9204fb3813a42eac8674897

병묵 : https://manso98.notion.site/23723aa1c0bb44828b52fc57efa6639e

 

명동 스터디 첫번째 커리큘럼 일정(2024.07.29 ~2024.11.16)

- 컴퓨터 과학 기초(07.09 ~ 07.21)
- 이산수학(07.29 ~ 08.17)

- 자료 구조(08.19 ~ 09.07)

- 컴퓨터 구조(09.09 ~ 10.12)

- DB(10.07 ~ 10.26)
- 네트워크(10.28 ~ 11.16)

 

 

목차

---

---

명제

진릿값(truth value)

참(true   : T)이나 거짓(False : F)을 가르키는 값

 

명제

객관적인 기준으로 진리값을 구분할 수 있는 문장이나 수식

일반적으로 명제는 영문 소문자 p, q, r... 로 표현

---

 

논리 연산자

일반적으로 명제 하나를 단순명제(Simple proposition)이라고 합니다.

 

합성명제(Compound proposition)

하나 이상의 명제들이 논리 연산자에 의해 결합된 명제

 

진리표(truth table)

합성명제를 구성하는  단순명제의 진릿값에 따른 논리 연산 결ㄹ과를 나타낸 표

 

부정(NOT : ¬p)

명제 p에대하여 'p가 아니다'를 의미 명제 p와 반대의 진릿값을 갖는 연산

 

논리곱(AND : p∧q, p&q)

명제 p, q에 대하여 'p 그리고 q'를 의미

명제 p, q의 진릿값이 모두 참(T)일ㄷ 때만 결과가 참(T)인 연산

p	q	p∧q
T	T	T
T	F	F
F	T	F
F	F	F

 

논리합(OR : p∨q, pǀǀq)

명제 p, q에 대하여 'p 또는 q'를 의미

명제 p, q의 진릿값 중 하나라도 참(T)이면 결과가 참(T)인 연산

p	q	p∧q
T	T	T
T	F	T
F	T	T
F	F	F

 

배타적 논리합(Exclusive OR, XOR : p⊕q)

두 명제 p, q의 진릿값 중 하나만 참(T)일 때 결과가 참(T)이고, 그 외의 경우에는 모두 결과가 거짓(F)인 연산

p	q	p⊕q
T	T	F
T	F	T
F	T	T
F	F	F

 

 

---

 

조건명제

조건명제(conditional proposition : p->q)

명제 p, q에 대하여, 명제 p가 전제(premise) 또는 가정(hypothesis)이고 명제 q가 결론(conclusion) 또는
결과(consequence)인 명제

p	q	p->q
T	T	T
T	F	F
F	T	T
F	F	T

 

역(converse)

조건명제 p->q에 대하여, q->p 형태의 명제

 

이(inverse)

조건명제 p->q에 대하여, ¬p->¬q 형태의 명제

 

대우(contraposition)

조건명제 p->q ¬q->¬p 형태의 명제

 

쌍방조건명제(biconditional proposition : p<->q)

명제 p, q가 모두 전제이면서 동시에 결론인 명제

p	q	p<->q
T	T	T
T	F	F
F	T	F
F	F	T

---

 

합성명제

논리 연산자의 우선순위

우선순위	논리연산자
1	¬
2	∧
3	∨
4	->
5	<->

합성 명제의 종류

- 항진명제(tautology : t) : 합성명제를 구성하는 단순명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 참(T)인 명제

- 모순명제(contradiction : f) : 합성명제를 구성하는 단순명제의 진릿값과 상관없이 합성명제의 진릿값이 항상 거짓(F)인 명제

- 사건명제(contingency) : 항진명제도 모순명제도 아닌 합성명제

 

논리적 동치

두 합성명제 P와 Q의 진릿값이 서로 같은 경우

---

 

명제함수와 한정자

명제함수(propositional funcation : P(x))

논의영역이 주어진 변수 x를 포함하여 진릿값을 판별할 수 있는 문장이나 수식

 

논의영역(domain of discource : D)

명제함수에 포함된 변수 x의 범위나 값

명제함수는 일반적으로 P, Q, R ... 과 같은 대문자와 명제함수에 포함된 변수를 함게 표시합니다.

 

명제함수의 예시

P(x) : 정수 x에 대하여 |x|=<0을 만족하는 정수가 적어도 한개는 있다.

Q(x,y) : 실수 x, y에 대하여 x=2y를 만족하는 x, y는 하나도 없다.

 

한정자(Quantifier) 

논의영역이 범위 형태로 주어지는 경우 주어진 범위에 포함되는 값들이 모두 명제함수를 참(T)으로 만드는지, 아니면 일부 값만이 명제함수를 참(T)으로 만드는지, 혹은 범위 내의 어느 값도 명제함수를 참(T)으로 만들지 않는지에 따라 명제 함수의 진릿값이 달라집니다.

그러므로 범위 형태로 논의 영역이 주어지는 경우 명제함수가 논의영역에 전체 값(원소)에 대한 것인지, 혹은 일부에 대한 것인지를 표시해야하는데, 이를 한정자라고 합니다.

-> 논의 영역 안에서 정의된 범위

 

전체 한정자

논의 영역에 속하는 모든 값
∀xP(x): '논의영역 U에 속하는 모든 x에 대해 P(x)는 참'이라는 명제
논의영역의 모든 원소에 대해 만족할 경우에만 참

 

존재 한정자

논의 영역에 속하는 어떤 값
∃xP(x) : '논의 영역 U에 속하는 어떤 x에 대해 P(x)의 참'이라는 명제
논의영역의 원소 중 하나라도 만족할 경우에는 참이 된다.

 

---

 

추론

추론과 논증

참(T)인 명제를 근거로 하여 다른 명제가 참(T)임을 유도하는 과정 또는 방식

 

전제와 결론

전제 : 결론의 근거가 되는 참(T)인 명제

결론 : 주어진 전제에 의해 유도된 최종적인 참(T)인 명제

 

유효추론과 허위 추론

진릿값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 모두 참(T)인 추론

 

허위추론/부당한 추론

진릿값이 참(T)인 주어진 전제를 이용하여 유도한 결론이 거짓(F)인 추론

---

참고 문헌

1. 박주미.2021.한빛아카데미 <컴퓨팅 사고를 키우는 이산수학>