수학/이산수학

술어와 한정기호

술어 "x는 3보다 크다."라는 문장을 보자. 이 문장은 두 부분으로 구성된다. 문장의 주어에 해당하는 "x", 그리고 술어(predicate)에 해당하는 "3보다 크다"가 있다. 문장 "x는 3보다 크다"라는 문장은 $P(x)$라고 표시할 수 있다. $P$는 술어를 , $x$는 변수를 나타낸다. $P(x)$는 명제함수(propositional function) $P$에서 $x$의 값이라고도 한다. 명제함수는 정의역(domain)에서 변수에 값이 할당되면 $P(x)$는 명제가 되고 진리값, 즉 참과 거짓을 판단할 수 있게 된다. 예) $P(x)$가 $x>3$일 때, $P(4)$의 진리값은 참이 된다. n개의 변수를 포함하는 명제함수는 $P(x_1, x_2, ..., x_n)$으로 표시하고, $P$를 n-..

명제의 동치(equivalent)

항진명제, 모순, 불확정명제 항진명제(tautology): 항상 참인 명제 모순(contradiction): 항상 거짓인 명제 불확정명제(contingency): 항진명제도 아니고 모순도 아닌 명제 예) $p$ $\neg q$ $p \lor\neg q$ $p \land \neg q$ $T$ $F$ $T$ $F$ $F$ $T$ $T$ $F$ $p \lor\neg q$는 항상 참이므로 항진명제이고, $p \land \neg q$는 항상 거짓이므로 모순이다. 논리적 동치 두 명제 $p$, $q$에 대하여 $p \leftrightarrow q$가 항진명제이면 $p$와 $q$는 논리적 동치이며, $p \equiv q$는 $p$와 $q$가 논리적 동치(logically equvalent)임을 나타낸다. 조건-논리합..

명제 논리(propositional logic)

명제(proposition) 참 또는 거짓 중 하나를 나타내는 선언적 문장이다. 명제인 예: 미국의 수도는 워싱턴 D.C이다. 캐나다의 수도는 토론토이다. 명제가 아닌 예: 몇 시입니까? 이것을 주의 깊게 읽어라. 명제를 표현하는 변수를 p, q, r, s 등 문자로 나타낸다. 명제의 진리값(truth value)이 참일 때는 T, 거짓일 때는 F로 나타낸다. 더 나누어질 수 없는 명제는 단순명제이다. 부정(negation) $p$가 명제라 하면 $p$의 부정은 $\neg p$ or $\bar{p}$로 나타내고, "It is not the case that p."의 문장이 된다. $p$ $\neg p$ $T$ $F$ $F$ $T$ 논리곱(conjunction) $p$와 $q$가 명제라 하면 $p \lan..