이산수학: 논리 ①

이산수학

코드라니(CODERANY) 2026. 5. 17. 14:22

목차

1. 논리와 명제

2. 단순명제와 합성명제

3. 논리연산자와 진리표

4. 역, 이, 대우

5. 항진명제와 모순명제

6. 동치

7. 추론

8. 술어논리

9. 변수의 명세와 한정화

1. 논리와 명제

1-1. 논리

논리는 말이나 글에서 사고나 추리 따위를 이치에 맞게 이끌어 가는 과정이나 원리이다.

이 논리는 두가지로 나뉘는데,

그래서 그게 진짠지 가짠지 궁금한 명제논리(propositional logic)와

문장을 객체와 그 객체의 성질을 나타내는 술어로 나눈 술어논리(Predicate logic)가 있다.

1-2. 명제(Proposition)

참(T)인지 거짓(F)인지를 객관적이고 분명하게 판별할 수 있는 문장이나 식이다.

1-3. 진리값(truth value)

그래서 일단 명제가 생겼으면 그게 찐인지 짜인지 구분한 걸 진리값이라고 부른다.

좀 더 교과서적으로 이야기하면 명제가 참 또는 거짓의 값을 가질 때의 값이다.

참은 T(true), 거짓은 F(false)로 표기한다.

2. 단순명제와 합성명제

단순명제(simple proposition)	명제가 하나	예: 사과는 빨갛다.
합성명제(composition proposition)	여러 개의 단순 명제의 합	예: 사과는 빨갛고, 포도는 달다.

3. 논리연산자와 진리표

부제. 이제 수학적으로 명제를 사용해보자.

논리연산자(logical operator)	∨(or), ∧(and), ~(not)과 같은 연산자
진리표(truth table)	입력값의 모든 가능한 조합에 대해 그 결과값이 어떻게 나오는지를 한눈에 보기 좋게 표로 정리한 것으로 복잡한 진리값을 구하기 위해 사용한다.

3-1. 논리 연산자

연산자의 이름	기호	연산자의 의미	예
부정 (NOT)	~p	p가 아니다	~오늘은 비가 온다 : 오늘은 비가 오지 않는다
논리곱 (AND)	p∧q	p와 q가 모두 참일 때 참	사과는 빨갛다∧포도는 달다 : 사과는 빨갛고 포도는 달다.
논리합 (OR)	p∨q	p와 q 중 하나만 참일 때 참	오늘 영화를 본다∨오늘 잠을 잔다 : 오늘 영화를 보거나 잠을 잔다.
배타적 논리합 (XOR)	p⊕q	서로를 배재함. p와 q중 하나만 참일 때 참	밥을 먹는다 ⊕ 빵을 먹는다 : 밥을 먹거나, 빵을 먹는다.
조건 (IF...THEN)	p→q	만약 p이면 q이다	공부를 하다 → 성적이 오르다 : 공부를 하면 성적이 오른다.
쌍방조건 (IF AND ONLY IF)	p↔q	서로가 서로에 대해 조건이 성립	x+2 = 5 ↔ x = 3

3-2. 진리표

3-2-1. 부정 (~, NOT)

p	~p	~(~p)	설명
T	F	T	p가 참이면 p의 부정은 거짓이고 p의 부정의 부정은 참이다
F	T	F	p가 거짓이면 p의 부정은 참이고 p의 부정의 부정은 거짓이다

3-2-2. 논리곱 (∧, AND)

3-2-3. 논리합 (∨, OR)

3-2-4. 배타적 논리합(⊕, XOR)

p	q	p⊕q	설명
T	T	F	p와 q가 참이면 p와 q의 배타적 논리합은 거짓이다.
T	F	T	p가 참이고 q가 거짓이면 p와 q의 배타적 논리합은 참이다.
F	T	T	p가 거짓이고 q가 참이면 p와 q의 배타적 논리합은 참이다.
F	F	F	p와 q가 거짓이면 p와 q의 배타적 논리합은 거짓이다.

3-2-5. 조건(→, Conditional)

p	q	p∧q	설명
T	T	T	p와 q가 참이면 조건 명제는 참이다.
T	F	F	p가 참이고 q가 거짓이면 조건 명제는 거짓이다.
F	T	T	p가 거짓이고 q가 참이면 조건 명제는 참이다. ※비가 오지 않아(~p)도 땅은 젖을 수 있기(q) 때문에 q를 어긴게 아님.
F	F	T	p와 q가 거짓이면 조건 명제는 참이다.

3-2-6. 쌍방조건(↔, Biconditional)