명제와 연결사, 양화사

명제란 참 또는 거짓 둘 중 하나임이 분명한 문장을 말하며, 어떤 문장에 가치판단이 개입된 경우 그것은 명제라고 할 수 없다. 명제는 참 또는 거짓 둘 중 하나의 진리값을 가진다. 두 명제 $p$와 $q$의 진리값이 같으면 두 명제 $p$와 $q$는 동치라고 하고, $p \equiv q$와 같이 나타낸다.

 

물론 위에서의 정의만으로는 명제인지 아닌지 분명하지 않은 문장이 발생한다. 따라서 명제를 더욱 엄밀하게 정의하기 위해서는 추가적인 서술이 필요하지만 거의 대부분의 경우는 위의 설명만으로도 충분하다.
보통 참은 $T$로 나타내며 거짓은 $F$로 나타낸다. 그런데 단순히 명제가 무엇인지 정의하는 것만으로는 논리적인 서술이 불가능하다. 따라서 기존의 명제들을 이용하여 새로운 명제를 만들어내고, 그들의 관계를 정립할 필요가 있으며, 그것을 위해 우리는 결합자와 양화사를 도입한다.

 

다음과 같은 것들을 연결사라고 한다. 1. 부정 : $\neg$ 2. 논리곱 : $\land$ 3. 논리합 : $\lor$ 4. 조건부 : $\to$ 5. 쌍조건부 : $\leftrightarrow$

 

명제에 연결사를 취해서 나타낸 명제의 진리값은 다음과 같이 진리표를 만들면 편하게 파악할 수 있다.

 

1. 부정 : $p$가 참이면 $\neg p$는 거짓이고, $p$가 거짓이면 $\neg p$는 참이다.

 

2. 논리곱 : $p$와 $q$가 모두 참이면 $p\land q$는 참이고, $p$와 $q$ 둘 중 하나라도 거짓이면 $p\land q$는 거짓이다.

 

3. 논리합 : $p$와 $q$가 모두 거짓이면 $p\lor q$는 거짓이고, $p$와 $q$ 둘 중 하나라도 참이면 $p\lor q$는 참이다.

 

4. 조건부 : $p$가 참일 때 $q$가 참이면 $p\to q$도 참이다. 자연어와 달리 $p$가 거짓이면 $q$의 진리값에 관계 없이 $p\to q$는 참이다. 이때, $p\to q\equiv p\lor\neg q$임에 주목하자. 이는 진리표로 쉽게 증명할 수 있다.

 

5. 쌍조건부 : $p\to q$와 $q\to p$ 모두 참이면 $p\leftrightarrow q$도 참이다. 즉, $p\leftrightarrow q\equiv (p\to q)\land(q\to p)$이다. 이때, $p$와 $q$의 진리값이 같을 때 $p\leftrightarrow q$가 참이고, $p$와 $q$의 진리값이 다를 때 $p\leftrightarrow q$가 거짓임에 주목하자. 이 역시 진리표로 쉽게 증명할 수 있다.

 

연결사 여러개가 혼용되어 사용됐을 경우에는 부정이 제일 우선순위가 높으며, 논리곱, 논리합, 조건부, 쌍조건부 순서의 우선순위를 가진다. 예를 들면 $p\lor q\land\neg r\to s$는 $(p\lor(q\land(\neg r)))\to s$와 같은 의미이다.

 

다음 두 가지를 양화사라고 한다. 1. 존재양화사 : $\exists$ 2. 보편양화사 : $\forall$

 

1. 존재양화사 : $\exists$는 어떤 대상의 존재를 나타낸다. 예를 들어 $\exists x\;s.t.\;x\to q$는 $x\to q$가 참인 $x$가 존재함을 나타낸다. 이때, $s.t.$는 such that의 약자이다.

 

2. 보편양화사 : $\forall$은 모든 대상이 지닌 성질을 말할 때 사용한다. 예를 들면 $\forall x\;with\;x\to q,\;x\to r$은 $x\to q$인 모든 $x$에 대해 $x\to r$임을 나타낸다.

 

존재양화사와 보편양화사는 둘 중 하나의 양화사와 위의 연결사를 사용해서 나머지 하나의 양화사를 만들어낼 수 있다. 그 관계는 다음과 같다.
$\forall x\phi\leftrightarrow\neg\exists x\neg\phi$, $\exists x\phi\leftrightarrow\neg\forall x\neg\phi$

 

존재양화사 뒤에 !를 붙인 형태인 $\exists!$는 유일하게 존재함을 나타낸다.