[이산 수학] 논리 연산자

논리 연산자

• 일반적으로 명제 하나를 단순 명제(Simple Proposition)라고 한다.
• 하나 이상의 단순 명제를 부정, 논리곱, 논리합, 베타적 논리합과 같은 논리 연산자로 결합하면 새로운 하나의 명제가 되기도 하는데, 이를 합성 명제(Compound Proposition)라고 한다.

 

합성 명제(Compound Proposition)

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

• 합성 명제를 구성하는 단순 명제의 진릿값과 논리 연산자에 따라 합성 명제의 진릿값은 달라진다.
• 그러므로 합성 명제의 진릿값을 판별하기 위해 진리표(Truth Table)를 사용한다.

 

진리표(Truth Table)

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

 

① 부정(NOT : $\neg p$ 또는 $\sim p$)

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

• 부정 $\neg$ 은 명제 하나에 대해 사용하는 단항 연산자이다.
• 명제 $\neg p$ 는 명제 `p` 와 반대의 의미를 가지므로, '`p` 가 아니다', 'not `p`' 혹은 '`p` 의 부정' 이라고 읽으며, 명제 `p` 와 반대의 진릿값을 갖는다.

 

부정 연산자의 진리표

$p$	$\neg p$
T	F
F	T

 

부정 연산의 예

명제	의미	진릿값
$p$	지구는 태양 주변을 도는 행성이다.	참(T)
$\neg p$	지구는 태양 주변을 도는 행성이 아니다.	거짓(F)

 

② 논리곱(AND : $p \land q$)

명제  `p, q` 에 대하여, '`p` 그리고 `q`' 를 의미
명제  `p, q` 의 진릿값이 모두 참(T)일 때만 결과가 참(T)인 연산

• 두 명제를 결합하는 데 사용하는 이항 연산자로, '그리고' 의 의미를 갖는다.
• 명제 $p \land q$ 는 '`p` 그리고 `q`', '`p` 이고 `q`' 혹은 '`p` and `q`'  라고 읽는다.
• 명제 $p \land q$ 의 진릿값은 두 단순 명제 `p, q` 의 진릿값이 모두 참(T)일 때만 참(T)이고, 두 단순 명제 중 하나라도 거짓(F)이면 거짓(F)이다.

 

논리곱 연산자의 진리표

$p$	$q$	$p \land q$
T	T	T
T	F	F
F	T	F
F	F	F

 

논리곱 연산의 예

명제	의미	진릿값
$p$	지구는 태양의 행성이다.	참(T)
$q$	달의 실제 크기는 지구보다 작다.	참(T)
$p \land q$	지구는 태양의 행성이다. 그리고 달의 실제 크기는 지구보다 작다. (지구는 태양의 행성이고, 달의 실제 크기는 지구보다 작다.)	참(T)

 

명제	의미	진릿값
$p$	지구는 태양의 행성이다.	참(T)
$q$	달의 실제 크기는 지구보다 크다.	거짓(F)
$p \land q$	지구는 태양의 행성이다. 그리고 달의 실제 크기는 지구보다 크다. (지구는 태양의 행성이고, 달의 실제 크기는 지구보다 크다.)	거짓(F)

 

명제	의미	진릿값
$p$	태양은 지구의 행성이다.	거짓(F)
$q$	달의 실제 크기는 지구보다 크다.	거짓(F)
$p \land q$	태양은 지구의 행성이다. 그리고 달의 실제 크기는 지구보다 크다. (태양은 지구의 행성이고, 달의 실제 크기는 지구보다 크다.)	거짓(F)

 

③ 논리합(OR : $p \lor q$)

명제  `p, q` 에 대하여, '`p` 또는 `q`' 를 의미
명제  `p, q` 의 진릿값 중 하나라도 참(T)이면 결과가 참(T)인 연산

• 두 명제를 결합하는 데 사용하는 이항 연산자로, '또는' 의 의미를 갖는다.
• 명제 $p \lor q$ 는 '`p` 또는 `q`', '`p` 이거나 `q`' 혹은 '`p` or `q`'  라고 읽는다.
• 명제 $p \lor q$ 의 진릿값은 두 단순 명제 `p, q` 의 진릿값 중 하나라도 참(T)이면 참(T)이고, 두 단순 명제의 진릿값이 모두 거짓(F)인 경우에만 거짓(F)이다.

 

논리합 연산자의 진리표

$p$	$q$	$p \lor q$
T	T	T
T	F	T
F	T	T
F	F	F

 

논리합 연산의 예

명제	의미	진릿값
$p$	지구는 태양의 행성이다.	참(T)
$q$	달의 실제 크기는 지구보다 크다.	거짓(F)
$p \lor q$	지구는 태양의 행성이다. 또는 달의 실제 크기는 지구보다 크다. (지구는 태양의 행성이거나  달의 실제 크기는 지구보다 크다.)	참(T)

 

④ 베타적 논리합(Exclusive OR, XOR : $p \oplus q$)

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

• 두 명제를 결합하는 데 사용하는 이항 연산자이다.
• '`p` xor `q`'  라고 읽는다.
• 명제 $p \oplus q$ 의 진릿값은 두 단순 명제 `p, q` 의 진릿값 중 하나만 참(T)일 때만 참(T)이고, 그 외의 경우에는 모두 결과가 거짓(F)이다.

 

베타적 논리합 연산자의 진리표

$p$	$q$	$p \oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

 

$p \oplus q ≡ (\neg p \land q) \lor (p \land \neg q)$

• 베타적 논리합은 다음과 같이 부정, 논리곱, 논리합 연산으로 표현할 수 있다.

$$p \oplus q ≡ (\neg p \land q) \lor (p \land \neg q)$$

 

• 포함하는 연산의 의미를 한 문장으로 표현하기에 복잡하기에 베타적 논리합 연산의 문장 표현은 다루지 않는다.

 

동치(Equivalence, $≡$)

• 진릿값이 같아서 두 식이 동일함을 의미하는 기호
• 예) $p \oplus q ≡ (\neg p \land q) \lor (p \land \neg q)$
  • $p \oplus q$ 와 $(\neg p \land q) \lor (p \land \neg q)$ 는 진릿값이 같으므로 서로 대체하여 사용할 수 있다.

 

증명 진리표

`p`	`q`	$p \oplus q$	$\neg p$	$\neg q$	$\neg p \land q$	$p \land \neg q$	$(\neg p \land q) \lor (p \land \neg q)$
T	T	F	F	F	F	F	F
T	F	T	F	T	F	T	T
F	T	T	T	F	T	F	T
F	F	F	T	T	F	F	F