2. 명제와 논리 (Sentence and Logic) | 집합론 학습 가이드

DEF 2.1 명제 Sentence

한국어

"명제"란 (주어진 문맥에서) 참인지 거짓인지가 명확하게 하나로 정해지는 서술을 말한다. 예를 들어,

\text{Seoul is the capital of Korea,}

\text{Money grows on trees,}

그리고

\text{Snow is black}

는 모두 명제이다.

English

“Sentence” is a statement which is unambiguously either true or false (in a given context). For example,

\text{Seoul is the capital of Korea,}

\text{Money grows on trees,}

and

\text{Snow is black}

are all sentences.

EX 2.2 명제 여부 판정 Deciding whether a statement is a sentence

한국어

"고려대학교는 한국에서 최고의 대학교이다"가 명제인지 판정하라.

"고려대학교는 한국에서 최고의 대학교이다"는 명제가 아니다. 정의 2.1에 의하면 명제는 참인지 거짓인지가 명확하게 하나로 정해지는 서술이어야 한다. 그러나 "최고"라는 표현에는 모호하지 않은 단일한 판정 기준이 없다 — 예를 들어 연구 실적, 입학 경쟁률, 졸업생의 사회적 성취, 또는 대학 순위 평가기관마다 다른 산정 방식 중 어떤 기준을 적용하느냐에 따라 참·거짓이 달라질 수 있다. 따라서 이 서술은 참·거짓이 명확하게 하나로 정해지지 않으므로 명제가 아니다.

English

Is “Korea university is the top university in Korea” a sentence?

"Korea university is the top university in Korea" is not a sentence. By Definition 2.1, a sentence must be a statement that is unambiguously either true or false. However, the word "top" has no single unambiguous criterion; its truth value can differ depending on which criterion is applied, for example research output, admission competitiveness, graduates' achievements, or the differing methodologies used by various university ranking agencies. Hence this statement does not have a single, unambiguously determined truth value, so it is not a sentence.

NOTE

한국어

명제를 나타내기 위해 $P$, $Q$, $R$, $S$ 등의 문자를 사용할 것이다.

주어진 명제를 이용하여 새로운 명제를 만들어낼 수 있다.

English

We will use letters $P$, $Q$, $R$, $S$ to denote sentences.

By using a given sentence, we can produce a new sentence.

DEF 2.3 부정 Negation

한국어

$P$를 명제라 하자. 그러면 $P$의 부정은 "$P$는 거짓이다"라고 주장하는 것으로 이해한다. 다시 말해 $P$가 참이면 $P$의 부정은 거짓이다. $P$의 부정은 $\neg P$로 표기하고 "$P$가 아니다"로 읽는다. 아래 표에서는 "참"과 "거짓"을 각각 나타내기 위해 "t"와 "f"를 사용한다.

부정의 진리표
$P$	$\neg P$
t	f
f	t

English

Let $P$ be a sentence. Then the negation of $P$ is understood to assert that “$P$ is false”. In other words, if $P$ is true, then the negation of $P$ is false. The negation of $P$ is denoted by $\neg P$ and it is read as “not $P$”. We use “t” and “f” to denote “true” and “false”, respectively in the following table.

Truth table for the negation
$P$	$\neg P$
t	f
f	t

NOTE

한국어

명제들을 결합하여 새로운 명제를 만들 수 있다. 다음은 명제의 결합 목록이다.

English

By combining sentences, we can make a new sentence. Here is a list of combinations of sentences.

DEF 2.4 논리곱 Conjunction

한국어

$P$와 $Q$를 명제라 하자. 그러면 $P$와 $Q$의 논리곱은 "$P$가 참이고 $Q$가 참이면 $P$와 $Q$의 논리곱은 참이다"라고 주장하는 것으로 이해한다. 다시 말해 $P$와 $Q$가 모두 참이면 $P$와 $Q$의 논리곱은 참이고, 그렇지 않으면 거짓이다. $P$와 $Q$의 논리곱은 $P \wedge Q$로 표기하고 "$P$ 그리고 $Q$"로 읽는다.

논리곱의 진리표
$P$	$Q$	$P \wedge Q$
t	t	t
t	f	f
f	t	f
f	f	f

English

Let $P$ and $Q$ be sentences. Then the conjunction of $P$ and $Q$ is understood to assert that “the conjunction of $P$ and $Q$ is true if $P$ is true and $Q$ is true”. In other words, if both $P$ and $Q$ are true, then the conjunction of $P$ and $Q$ is true and otherwise it is false. The conjunction of $P$ and $Q$ is denoted by $P \wedge Q$ and it is read as “$P$ and $Q$”.

Truth table for the conjunction
$P$	$Q$	$P \wedge Q$
t	t	t
t	f	f
f	t	f
f	f	f

DEF 2.5 논리합 Disjunction

한국어

$P$와 $Q$를 명제라 하자. 그러면 $P$와 $Q$의 논리합은 "$P$ 또는 $Q$, 혹은 $P$와 $Q$가 모두 참이면 $P$와 $Q$의 논리합은 참이다"라고 주장하는 것으로 이해한다. 다시 말해 $P$와 $Q$가 모두 거짓일 때만 $P$와 $Q$의 논리합은 거짓이다. $P$와 $Q$의 논리합은 $P \vee Q$로 표기하고 "$P$ 또는 $Q$"로 읽는다.

논리합의 진리표
$P$	$Q$	$P \vee Q$
t	t	t
t	f	t
f	t	t
f	f	f

English

Let $P$ and $Q$ be sentences. Then the disjunction of $P$ and $Q$ is understood to assert that “the disjunction of $P$ and $Q$ is true if $P$, or $Q$, or both $P$ and $Q$ are true”. In other words, the disjunction of $P$ and $Q$ is false only if both $P$ and $Q$ are false. The disjunction of $P$ and $Q$ is denoted by $P \vee Q$ and it is read as “$P$ or $Q$”.

Truth table for the disjunction
$P$	$Q$	$P \vee Q$
t	t	t
t	f	t
f	t	t
f	f	f

DEF 2.6 함의 Implication

한국어

$P$와 $Q$를 명제라 하자. 그러면 "$P$는 $Q$를 함의한다"는 "$P$가 참이면 $Q$도 참이다"라고 주장하는 것으로 이해한다. 수학에서 더 구체적으로 말하면, 이 함의는 $P$가 참이고 $Q$가 거짓인 경우를 제외하고는 항상 참이다. $P$가 $Q$를 함의한다는 것을 나타내기 위해 $P \implies Q$라는 표기를 사용한다.

함의의 진리표
$P$	$Q$	$P \implies Q$
t	t	t
t	f	f
f	t	t
f	f	t

English

Let $P$ and $Q$ be sentences. Then that $P$ implies $Q$ is understood to assert that “if $P$ is true, then $Q$ is true”. More specifically in mathematics, the implication is true except if $P$ is true and $Q$ is false. We use the notation $P \implies Q$ to denote that $P$ implies $Q$.

Truth table for the implication
$P$	$Q$	$P \implies Q$
t	t	t
t	f	f
f	t	t
f	f	t

NOTATION 2.7 함의 읽는 법 Reading the implication

한국어

정의에 의해 $P \implies Q$는 "$P$는 $Q$를 함의한다"로 읽는다.
$P \implies Q$는 "$P$이면 $Q$이다" 또는 "$P$일 때 $Q$이다"로도 읽는다.

English

By the definition, $P \implies Q$ is read as “$P$ implies $Q$”.
$P \implies Q$ is also read as “if $P$, then $Q$” or “$Q$ if $P$”.

EXAM 2.8 함의 진리표의 작동 방식 How the truth table for the implication works

한국어

함의의 진리표는 두 명제 사이에 아무 관계가 없어도 작동한다. 예를 들어 명제 $1+1=2 \quad \implies \quad \pi \text{ is an irrational number}$ 는 "$1 + 1 = 2$"와 "$\pi$는 무리수이다" 두 명제가 모두 참이므로 참이다.
전제 $P$가 참이면 함의 $P \implies Q$의 참·거짓은 $Q$의 참·거짓에 의해 결정되며, 이는 우리의 상식에 매우 자연스러워 보인다. 그러나 전제 $P$가 거짓인 경우에는 함의를 이해하기가 어렵다. 우리의 진리표에 따르면 전제 $P$가 거짓이면 함의 $P \implies Q$는 항상 참임에 유의하라. 다음 예를 생각해보자: $1+1=3 \quad \implies \quad 3 \text{ is an even number.}$ 위의 두 명제는 모두 거짓이지만, 우리의 진리 규칙에 의해 함의는 참이다.
$A$를 공집합이라 하자. 즉 $A$는 원소를 갖지 않는다. 명제 $\text{for all } x \in A, \; x \text{ can have any property.}$ 를 생각하자. 위 명제는 함의 표기를 이용하여 다음과 같이 해석할 수 있다: $x \in A \implies x \text{ can have any property.}$ 따라서 이 명제는 참이다. 다시 말해, 주어진 집합 $A$가 공집합이면 $A$의 모든 원소가 우리가 원하는 어떤 성질이든 가진다고 말할 수 있다. 이러한 상황은 주어진 집합이 공집합인 극단적인 경우를 고려할 때 수학에서 자주 나타난다.
$P$를 명제라 하자. 그러면 $P \implies P$는 항상 참이다.

English

The truth table for the implication is working even though there is no relation between two sentences. For instance, the sentence $1+1=2 \quad \implies \quad \pi \text{ is an irrational number}$ is true since both sentences “$1 + 1 = 2$” and “$\pi$ is an irrational number” are true.
If the premise $P$ is true, then the truth of the implication $P \implies Q$ is determined by truth of $Q$ and it seems very natural to our common sense. However, it is difficult to understand the implication if the premise $P$ is false. Note that if the premise $P$ is false, then the implication $P \implies Q$ is always true due to our truth table. Consider the following example: $1+1=3 \quad \implies \quad 3 \text{ is an even number.}$ Both sentences above are false but the implication is true by our truth rule.
Let $A$ be the empty set, i.e. $A$ has no elements. Consider the sentence $\text{for all } x \in A, \; x \text{ can have any property.}$ We could interpret the above sentence by using the implication notation as follows: $x \in A \implies x \text{ can have any property.}$ Therefore, this sentence is true. In other words, if the given set $A$ is empty, then we may say that all elements of $A$ have any property which we want to give. This kind of situation appears frequently in mathematics when we consider the extreme case that the given set is empty.
Let $P$ be a sentence. Then $P \implies P$ is always true.

EX 2.9 $\mathbb{N}$ 위 두 함의의 진리값 Truth values of two implications over $\mathbb{N}$

한국어

$\mathbb{N}$을 자연수 체계라 하자. 다음 두 명제가 참인지 거짓인지 판정하라:

$A \subset \mathbb{N} \implies \text{all elements of } A \text{ are integers}$
$A \subset \mathbb{N} \implies \text{all elements of } A \text{ are even numbers.}$

이 명제는 참이다. 실제로 $A \subset \mathbb{N}$이라고 가정하고 $x \in A$인 임의의 $x$를 취하자. $A \subset \mathbb{N}$이므로 $x \in \mathbb{N}$이고, 모든 자연수는 정수이므로 $x$는 정수이다. $x \in A$는 임의로 취하였으므로 $A$의 모든 원소는 정수이다. 따라서 함의 "$A \subset \mathbb{N} \implies$ $A$의 모든 원소는 정수이다"는 참이다. 이 논증은 임의의 $A \subset \mathbb{N}$에 대해 성립하며, 특히 $A = \emptyset$인 경우에도 전제와 결론이 모두 공허하게 참이 되어 함의는 여전히 성립한다 (예 2.8(3) 참고).
이 명제는 거짓이다. 반례를 들어 보이자. $A = \{1\}$이라 하자. $1 \in \mathbb{N}$이므로 $A \subset \mathbb{N}$이고, 따라서 전제 "$A \subset \mathbb{N}$"은 참이다. 그러나 $1$은 짝수가 아니므로 $A$의 모든 원소가 짝수라는 결론은 거짓이다. 따라서 이 $A$에 대해 전제는 참이고 결론은 거짓이므로, 함의 "$A \subset \mathbb{N} \implies$ $A$의 모든 원소는 짝수이다"는 거짓이다. (몇몇 특정한 $A$, 예를 들어 $A = \emptyset$이나 $A = \{2\}$에 대해서는 이 함의가 참이 될 수 있음에 유의하라. 그러나 문제는 모든 $A \subset \mathbb{N}$에 대해 이 명제가 참인지를 묻고 있으므로, $A = \{1\}$이라는 하나의 반례만으로도 명제 전체가 거짓임을 보이기에 충분하다.)

□

English

Let $\mathbb{N}$ be the natural number system. Determine if the following two sentence are true or false:

$A \subset \mathbb{N} \implies \text{all elements of } A \text{ are integers}$
$A \subset \mathbb{N} \implies \text{all elements of } A \text{ are even numbers.}$

This statement is true. Indeed, assume $A \subset \mathbb{N}$ and let $x \in A$ be arbitrary. Since $A \subset \mathbb{N}$, we have $x \in \mathbb{N}$, and since every natural number is an integer, $x$ is an integer. As $x \in A$ was arbitrary, every element of $A$ is an integer. Hence the implication "$A \subset \mathbb{N} \implies$ all elements of $A$ are integers" is true. This argument holds for every $A \subset \mathbb{N}$, and in particular for $A = \emptyset$ the premise and the conclusion are both vacuously true, so the implication still holds (cf. Example 2.8(3)).
This statement is false. We exhibit a counterexample. Let $A = \{1\}$. Since $1 \in \mathbb{N}$, we have $A \subset \mathbb{N}$, so the premise "$A \subset \mathbb{N}$" is true. However, $1$ is not an even number, so the conclusion that all elements of $A$ are even numbers is false. Thus for this $A$ the premise is true and the conclusion is false, so the implication "$A \subset \mathbb{N} \implies$ all elements of $A$ are even numbers" is false. (Note that for some particular $A$, e.g. $A = \emptyset$ or $A = \{2\}$, this implication can hold. However, since the question asks whether the statement holds for all $A \subset \mathbb{N}$, the single counterexample $A = \{1\}$ suffices to show that the statement is false in general.)

□

DEF 2.10 역, 이, 대우 The converse, inverse, contrapositive

한국어

$P$와 $Q$를 명제라 하고 $P$가 $Q$를 함의한다는 함의, 즉 $P \implies Q$를 생각하자.

이 함의의 역은 $Q$가 $P$를 함의한다는 것, 즉 $Q \implies P.$
이 함의의 이는 $\neg P$가 $\neg Q$를 함의한다는 것, 즉 $\neg P \implies \neg Q.$
이 함의의 대우는 $\neg Q$가 $\neg P$를 함의한다는 것, 즉 $\neg Q \implies \neg P.$

English

Let $P$ and $Q$ be sentences and consider the implication that $P$ implies $Q$, i.e. $P \implies Q$.

The converse of the implication is that $Q$ implies $P$, i.e. $Q \implies P.$
The inverse of the implication is that $\neg P$ implies $\neg Q$, i.e. $\neg P \implies \neg Q.$
The contrapositive of the implication is that $\neg Q$ implies $\neg P$, i.e. $\neg Q \implies \neg P.$

REM 2.11 역·이·대우의 진리표 Truth tables for the converse, inverse, and contrapositive

한국어

$P$와 $Q$를 명제라 하고 $P$가 $Q$를 함의한다는 함의를 생각하자. 역, 이, 대우의 진리표는 부정과 함의의 진리값으로부터 쉽게 얻을 수 있다. 실제로,

함의의 역의 진리표
$P$	$Q$	$Q \implies P$
t	t	t
t	f	t
f	t	f
f	f	t

함의의 이의 진리표
$P$	$Q$	$\neg P$	$\neg Q$	$\neg P \implies \neg Q$
t	t	f	f	t
t	f	f	t	t
f	t	t	f	f
f	f	t	t	t

함의의 대우의 진리표
$P$	$Q$	$\neg P$	$\neg Q$	$\neg Q \implies \neg P$
t	t	f	f	t
t	f	f	t	f
f	t	t	f	t
f	f	t	t	t

$P \implies Q$와 그 대우의 진리값이 같다는 점을 강조한다.

English

Let $P$ and $Q$ be sentences and consider the implication that $P$ implies $Q$. The truth tables for the converse, inverse, and contrapositive are easily obtained from truth values from the negation and implication. Indeed,

Truth table for the converse of the implication
$P$	$Q$	$Q \implies P$
t	t	t
t	f	t
f	t	f
f	f	t

Truth table for the inverse of the implication
$P$	$Q$	$\neg P$	$\neg Q$	$\neg P \implies \neg Q$
t	t	f	f	t
t	f	f	t	t
f	t	t	f	f
f	f	t	t	t

Truth table for the contrapositive of the implication
$P$	$Q$	$\neg P$	$\neg Q$	$\neg Q \implies \neg P$
t	t	f	f	t
t	f	f	t	f
f	t	t	f	t
f	f	t	t	t

We emphasize that the truth values for $P \implies Q$ and its contrapositive are same.

NOTATION 2.12 충분조건과 필요조건 Sufficient and necessary conditions

한국어

$P \implies Q$는 "$Q$일 때만 $P$이다", "$P$는 $Q$의 충분조건이다", "$Q$는 $P$의 필요조건이다"로도 읽는다.

English

$P \implies Q$ is also read as “$P$ only if $Q$”, “$P$ is a sufficient condition of $Q$”, and “$Q$ is a necessary condition of $P$”.

THM 2.13 논리합·논리곱에 대한 기본 함의 Basic implications for disjunction and conjunction

한국어

$P$와 $Q$를 명제라 하자. 그러면 다음 명제들은 (항상) 참이다:

$P \implies P \vee Q$
$Q \implies P \vee Q$
$P \wedge Q \implies P$
$P \wedge Q \implies Q$

논리곱과 함의의 진리표를 떠올려보자. 증명을 네 가지 경우로 나눈다.

(경우 1: $P$가 참이고 $Q$가 참인 경우). $P$가 참이고 $Q$가 참이면 $P \vee Q$는 참이다. 따라서 $P \implies P \vee Q$는 참이다.
(경우 2: $P$가 참이고 $Q$가 거짓인 경우). $P$가 참이고 $Q$가 거짓이면 $P \vee Q$는 참이다. 따라서 $P \implies P \vee Q$는 참이다.
(경우 3: $P$가 거짓이고 $Q$가 참인 경우). $P$가 거짓이면 $P \implies P \vee Q$는 참이다.
(경우 4: $P$가 거짓이고 $Q$가 거짓인 경우). $P$가 거짓이면 $P \implies P \vee Q$는 참이다.

따라서

P \implies P \vee Q

다음 진리표를 통해서도 결론을 이끌어낼 수 있다:

$P \implies P \vee Q$의 진리표
$P$	$Q$	$P \vee Q$	$P \implies P \vee Q$
t	t	t	t
t	f	t	t
f	t	t	t
f	f	f	t

$Q \implies P \vee Q$에 대한 진리표는 $P \implies P \vee Q$에 대한 것과 유사하다. 세부 사항은 생략한다.

$P \wedge Q \implies P$에 대한 진리표를 유도한다.

$P \wedge Q \implies P$의 진리표
$P$	$Q$	$P \wedge Q$	$P \wedge Q \implies P$
t	t	t	t
t	f	f	t
f	t	f	t
f	f	f	t

$P \wedge Q \implies Q$에 대한 진리표는 $P \wedge Q \implies P$에 대한 것과 매우 유사하므로 세부 사항은 생략한다.

□

English

Let $P$ and $Q$ be sentences. Then the following statements are (always) true:

$P \implies P \vee Q$
$Q \implies P \vee Q$
$P \wedge Q \implies P$
$P \wedge Q \implies Q$

Recall the truth table for the conjunction and implication. We divide the proof into four cases.

(Case 1: $P$ is true and $Q$ is true). If $P$ is true and $Q$ is true, then $P \vee Q$ is true. Thus $P \implies P \vee Q$ is true.
(Case 2: $P$ is true and $Q$ is false). If $P$ is true and $Q$ is false, then $P \vee Q$ is true. Thus $P \implies P \vee Q$ is true.
(Case 3: $P$ is false and $Q$ is true). If $P$ is false, then $P \implies P \vee Q$ is true.
(Case 4: $P$ is false and $Q$ is false). If $P$ is false, then $P \implies P \vee Q$ is true.

Therefore

P \implies P \vee Q

We can also deduce the conclusion through the following truth table:

Truth table for $P \implies P \vee Q$
$P$	$Q$	$P \vee Q$	$P \implies P \vee Q$
t	t	t	t
t	f	t	t
f	t	t	t
f	f	f	t

The truth table for $Q \implies P \vee Q$ is analogous to the one for $P \implies P \vee Q$. We skip the detail.

We derive a truth table for $P \wedge Q \implies P$.

Truth table for $P \wedge Q \implies P$
$P$	$Q$	$P \wedge Q$	$P \wedge Q \implies P$
t	t	t	t
t	f	f	t
f	t	f	t
f	f	f	t

Since the truth table for $P \wedge Q \implies Q$ is very similar to the one for $P \wedge Q \implies P$, we skip the detail.

□

THM 2.14 논리합·논리곱으로 보존되는 함의 Implications preserved by disjunction and conjunction

한국어

$P$, $Q$, $R$을 명제라 하자. $Q \implies R$이 참이라고 가정하자. 그러면 다음 명제들은 참이다:

$P \vee Q \implies P \vee R$
$P \wedge Q \implies P \wedge R.$

먼저 $P \vee Q \implies P \vee R$에 대한 진리표를 살펴보자.

$P \vee Q \implies P \vee R$의 진리표
$P$	$Q$	$R$	$P \vee Q$	$P \vee R$	$P \vee Q \implies P \vee R$
t	t	t	t	t	t
t	t	f	t	t	t
t	f	t	t	t	t
t	f	f	t	t	t
f	t	t	t	t	t
f	t	f	t	f	f
f	f	t	f	t	t
f	f	f	f	f	t

$Q \implies R$이 참이라는 가정을 상기하며 $Q \implies R$에 대한 진리표를 살펴보자.

$Q \implies R$의 진리표
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

가정에 의해 $Q$가 참이고 $R$이 거짓인 경우는 불가능하다. $P \vee Q \implies P \vee R$의 진리표에서 이 경우를 제거하면 다음을 얻는다:

$Q \implies R$라는 가정 아래
$P$	$Q$	$R$	$P \vee Q$	$P \vee R$	$P \vee Q \implies P \vee R$
t	t	t	t	t	t
t	f	t	t	t	t
t	f	f	t	t	t
f	t	t	t	t	t
f	f	t	f	t	t
f	f	f	f	f	t

따라서 $Q \implies R$이라는 가정 아래 $P \vee Q \implies P \vee R$는 항상 참임을 결론지을 수 있다.

(2)의 증명은 (1)의 증명과 유사하다. 이 증명은 연습문제로 남긴다.

□

English

Let $P$, $Q$, and $R$ be sentences. Assume that $Q \implies R$ is true. Then the following statements are true:

$P \vee Q \implies P \vee R$
$P \wedge Q \implies P \wedge R.$

We consider the truth table for $P \vee Q \implies P \vee R$ first.

Truth table for $P \vee Q \implies P \vee R$
$P$	$Q$	$R$	$P \vee Q$	$P \vee R$	$P \vee Q \implies P \vee R$
t	t	t	t	t	t
t	t	f	t	t	t
t	f	t	t	t	t
t	f	f	t	t	t
f	t	t	t	t	t
f	t	f	t	f	f
f	f	t	f	t	t
f	f	f	f	f	t

Recalling the assumption that $Q \implies R$ is true, we consider the truth table for $Q \implies R$.

Truth table for $Q \implies R$
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

Due to the assumption, the case that $Q$ is true and $R$ is false is impossible. Remove this case from the truth table for $P \vee Q \implies P \vee R$. Then we have

Under the assumption that $Q \implies R$
$P$	$Q$	$R$	$P \vee Q$	$P \vee R$	$P \vee Q \implies P \vee R$
t	t	t	t	t	t
t	f	t	t	t	t
t	f	f	t	t	t
f	t	t	t	t	t
f	f	t	f	t	t
f	f	f	f	f	t

Therefore, we conclude that $P \vee Q \implies P \vee R$ is always true under the assumption that $Q \implies R$.

The proof of (2) is analogous to (1). We leave the proof as an exercise.

□

REM 2.15 "참이다" 생략 관행 The convention of omitting “is true”

한국어

정리 2.14에서 우리는 $Q \implies R$이 참이라고 가정하였다. 그러나 관례적으로 "참이다"는 보통 생략한다. 다시 말해 단순히 $Q \implies R$이라고 말하면, 이는 명제 $Q \implies R$이 참이라는 것을 의미한다.

English

In Theorem 2.14, we assumed that $Q \implies R$ is true. However, conventionally, we usually skip “is true”. In other words, if we simply say that $Q \implies R$, then it means that the sentence $Q \implies R$ is true.

EX 2.16 정리 2.14의 (2) 증명 Proving part (2) of Theorem 2.14

한국어

정리 2.14의 (2)를 증명하라.

정리 2.14(1)의 증명과 같은 방식으로 진행한다. $P$, $Q$, $R$을 명제라 하고 $Q \implies R$이 참이라고 가정하자. 먼저 $P \wedge Q \implies P \wedge R$에 대한 진리표를 살펴보자.

$P \wedge Q \implies P \wedge R$의 진리표
$P$	$Q$	$R$	$P \wedge Q$	$P \wedge R$	$P \wedge Q \implies P \wedge R$
t	t	t	t	t	t
t	t	f	t	f	f
t	f	t	f	t	t
t	f	f	f	f	t
f	t	t	f	f	t
f	t	f	f	f	t
f	f	t	f	f	t
f	f	f	f	f	t

$Q \implies R$이 참이라는 가정을 상기하며 $Q \implies R$에 대한 진리표를 살펴보자.

$Q \implies R$의 진리표
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

가정에 의해 $Q$가 참이고 $R$이 거짓인 경우는 불가능하다. $P \wedge Q \implies P \wedge R$의 진리표에서 이 경우를 제거하면 다음을 얻는다:

$Q \implies R$라는 가정 아래
$P$	$Q$	$R$	$P \wedge Q$	$P \wedge R$	$P \wedge Q \implies P \wedge R$
t	t	t	t	t	t
t	f	t	f	t	t
t	f	f	f	f	t
f	t	t	f	f	t
f	f	t	f	f	t
f	f	f	f	f	t

남은 모든 경우에서 $P \wedge Q \implies P \wedge R$의 값이 참임을 확인할 수 있다. 따라서 $Q \implies R$이라는 가정 아래 $P \wedge Q \implies P \wedge R$는 항상 참임을 결론지을 수 있다.

□

English

Prove (2) in Theorem 2.14.

We proceed in the same way as the proof of Theorem 2.14(1). Let $P$, $Q$, $R$ be sentences and assume that $Q \implies R$ is true. We consider the truth table for $P \wedge Q \implies P \wedge R$ first.

Truth table for $P \wedge Q \implies P \wedge R$
$P$	$Q$	$R$	$P \wedge Q$	$P \wedge R$	$P \wedge Q \implies P \wedge R$
t	t	t	t	t	t
t	t	f	t	f	f
t	f	t	f	t	t
t	f	f	f	f	t
f	t	t	f	f	t
f	t	f	f	f	t
f	f	t	f	f	t
f	f	f	f	f	t

Recalling the assumption that $Q \implies R$ is true, we consider the truth table for $Q \implies R$.

Truth table for $Q \implies R$
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

Due to the assumption, the case that $Q$ is true and $R$ is false is impossible. Remove this case from the truth table for $P \wedge Q \implies P \wedge R$. Then we have

Under the assumption that $Q \implies R$
$P$	$Q$	$R$	$P \wedge Q$	$P \wedge R$	$P \wedge Q \implies P \wedge R$
t	t	t	t	t	t
t	f	t	f	t	t
t	f	f	f	f	t
f	t	t	f	f	t
f	f	t	f	f	t
f	f	f	f	f	t

We see that $P \wedge Q \implies P \wedge R$ is true in every remaining case. Therefore, we conclude that $P \wedge Q \implies P \wedge R$ is always true under the assumption that $Q \implies R$.

□

THM 2.17 추이법칙 Transitive law

한국어

$P$, $Q$, $R$을 명제라 하자. 그러면

[(P \implies Q) \wedge (Q \implies R)] \implies (P \implies R).

$(P \implies Q) \wedge (Q \implies R)$가 거짓이면 이 함의는 참이다. 따라서 $(P \implies Q) \wedge (Q \implies R)$가 참인 경우만 고려하면 되고, 논리곱의 진리표에 의해 $P \implies Q$와 $Q \implies R$가 모두 참이라고 가정할 수 있다. $P \implies Q$와 $Q \implies R$가 모두 참인 모든 경우를 분류해보자. $P \implies Q$와 $Q \implies R$에 대한 진리표를 생각하자.

$P \implies Q$의 진리표
$P$	$Q$	$P \implies Q$
t	t	t
t	f	f
f	t	t
f	f	t

그리고

$Q \implies R$의 진리표
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

그러면 가능한 모든 경우는 다음과 같다:

$P \implies Q$와 $Q \implies R$가 모두 참이라는 가정 아래
$P$	$Q$	$R$
t	t	t
f	t	t
f	f	t
f	f	f

그리고 우리는 다음을 얻는다:

$P \implies Q$와 $Q \implies R$가 모두 참이라는 가정 아래
$P$	$R$	$P \implies R$
t	t	t
f	t	t
f	t	t
f	f	t

정리가 증명되었다.

□

English

Let $P$, $Q$, and $R$ be sentences. Then

[(P \implies Q) \wedge (Q \implies R)] \implies (P \implies R).

If $(P \implies Q) \wedge (Q \implies R)$ is false, then the implication is true. Thus we only need to consider the case $(P \implies Q) \wedge (Q \implies R)$ is true and by the truth table for the conjunction, we may assume that both $P \implies Q$ and $Q \implies R$ are true. Let’s classify all cases that both $P \implies Q$ and $Q \implies R$ are true. Consider the truth table for $P \implies Q$ and $Q \implies R$.

Truth table for $P \implies Q$
$P$	$Q$	$P \implies Q$
t	t	t
t	f	f
f	t	t
f	f	t

and

Truth table for $Q \implies R$
$Q$	$R$	$Q \implies R$
t	t	t
t	f	f
f	t	t
f	f	t

Then all possible cases are

Under the assumption that both $P \implies Q$ and $Q \implies R$ are true
$P$	$Q$	$R$
t	t	t
f	t	t
f	f	t
f	f	f

and we have

Under the assumption that both $P \implies Q$ and $Q \implies R$ are true
$P$	$R$	$P \implies R$
t	t	t
f	t	t
f	t	t
f	f	t

The theorem is proved.

□

NOTATION 2.18 동치의 약어 The abbreviation for equivalence

한국어

$(P \implies Q) \wedge (Q \implies P)$에 대한 약어로 $P \iff Q$를 사용한다. $P \iff Q$는 "$Q$일 때 그리고 그럴 때만 $P$이다"로 읽는다. 또한 두 명제 $P$와 $Q$가 "동치"라고 말한다.

English

We use the abbreviation $P \iff Q$ for $(P \implies Q) \wedge (Q \implies P)$. $P \iff Q$ is read as “$P$ if and only if $Q$”. We also say that two sentences $P$ and $Q$ are “equivalent”.

THM 2.19 멱등·교환·결합·분배법칙 Idempotent, commutative, associative, and distributive laws

한국어

$P$, $Q$, $R$을 명제라 하자. 그러면

(멱등법칙) $P \vee P \iff P$
(멱등법칙) $P \wedge P \iff P$
(교환법칙) $P \vee Q \iff Q \vee P$
(교환법칙) $P \wedge Q \iff Q \wedge P$
(결합법칙) $P \vee (Q \vee R) \iff (P \vee Q) \vee R$
(결합법칙) $P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R$
(분배법칙) $P \wedge (Q \vee R) \iff (P \wedge Q) \vee (P \wedge R)$
(분배법칙) $P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee R).$

"만약(if) 부분"은 자명하다. 실제로 $P$가 참이면 $P$는 참이거나 $P$는 참이다. 따라서 $P \vee P$는 참이다. 다음으로 "오직 ~인 경우에만(only if) 부분"을 증명한다. $P \vee P$가 거짓이면 증명할 것이 없다. 따라서 $P \vee P$가 참이면 $P$가 참임을 보이면 충분하다. $P \vee P$가 참이라고 가정하자. 그러면 논리합의 진리표에 의해 $P$는 참이거나 $P$는 참이다. 따라서 $P$는 참이다.

나머지 명제의 증명은 연습문제로 남긴다.

□

English

Let $P$, $Q$, and $R$ be sentences. Then

(Idempotent law) $P \vee P \iff P$
(Idempotent law) $P \wedge P \iff P$
(Commutative law) $P \vee Q \iff Q \vee P$
(Commutative law) $P \wedge Q \iff Q \wedge P$
(Associative law) $P \vee (Q \vee R) \iff (P \vee Q) \vee R$
(Associative law) $P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R$
(Distributive law) $P \wedge (Q \vee R) \iff (P \wedge Q) \vee (P \wedge R)$
(Distributive law) $P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee R).$

The “if part” is obvious. Indeed, if $P$ is true, then $P$ is true or $P$ is true. Therefore $P \vee P$ is true. Next we prove the “only if part”. If $P \vee P$ is false, then there is nothing to prove. Thus it is sufficient to show that if $P \vee P$ is true, then $P$ is true. Assume that $P \vee P$ is true. Then by the truth table for the disjunction, $P$ is true or $P$ is true. Therefore $P$ is true.

We leave the proof of the other statements as exercises.

□

EX 2.20 이중부정 Double negation

한국어

모든 명제 $P$에 대하여 다음이 성립함을 증명하라.

P \iff \neg(\neg P).

진리표를 이용하여 두 명제 $P$와 $\neg(\neg P)$의 진리값이 항상 일치함을 보인다.

$P$와 $\neg(\neg P)$의 진리표
$P$	$\neg P$	$\neg(\neg P)$
t	f	t
f	t	f

표에서 보듯이 $P$와 $\neg(\neg P)$는 모든 경우에 같은 진리값을 갖는다. 즉 $P$가 참이면 $\neg(\neg P)$도 참이고, $P$가 거짓이면 $\neg(\neg P)$도 거짓이다. 따라서 함의의 진리표에 의해 $P \implies \neg(\neg P)$와 $\neg(\neg P) \implies P$가 모두 참이다. 표기 2.18에 의해 이는 곧

P \iff \neg(\neg P)

가 성립함을 의미한다.

□

English

Show that for every sentence $P$,

P \iff \neg(\neg P).

We use a truth table to show that the sentences $P$ and $\neg(\neg P)$ always have the same truth value.

Truth table for $P$ and $\neg(\neg P)$
$P$	$\neg P$	$\neg(\neg P)$
t	f	t
f	t	f

As the table shows, $P$ and $\neg(\neg P)$ have the same truth value in every case. That is, if $P$ is true, then $\neg(\neg P)$ is true, and if $P$ is false, then $\neg(\neg P)$ is false. Therefore, by the truth table for the implication, both $P \implies \neg(\neg P)$ and $\neg(\neg P) \implies P$ are true. By Notation 2.18, this means that

P \iff \neg(\neg P)

holds.

□

EX 2.21 명제에 대한 드모르간 법칙 De Morgan’s laws for sentences

한국어

$P$와 $Q$를 명제라 하자. 다음이 성립함을 증명하라.

\neg(P \vee Q) \iff \neg P \wedge \neg Q

그리고

\neg(P \wedge Q) \iff \neg P \vee \neg Q.

첫 번째 드모르간 법칙 $\neg(P \vee Q) \iff \neg P \wedge \neg Q$의 진리표를 살펴보자.

$\neg(P \vee Q)$와 $\neg P \wedge \neg Q$의 진리표
$P$	$Q$	$\neg P$	$\neg Q$	$P \vee Q$	$\neg(P \vee Q)$	$\neg P \wedge \neg Q$
t	t	f	f	t	f	f
t	f	f	t	t	f	f
f	t	t	f	t	f	f
f	f	t	t	f	t	t

표의 각 행에서 $\neg(P \vee Q)$와 $\neg P \wedge \neg Q$의 값이 일치함을 확인할 수 있다. 따라서 함의의 진리표에 의해 $\neg(P \vee Q) \implies \neg P \wedge \neg Q$와 $\neg P \wedge \neg Q \implies \neg(P \vee Q)$가 모두 참이며, 표기 2.18에 의해

\neg(P \vee Q) \iff \neg P \wedge \neg Q

가 성립한다.

다음으로 두 번째 드모르간 법칙 $\neg(P \wedge Q) \iff \neg P \vee \neg Q$의 진리표를 살펴보자.

$\neg(P \wedge Q)$와 $\neg P \vee \neg Q$의 진리표
$P$	$Q$	$\neg P$	$\neg Q$	$P \wedge Q$	$\neg(P \wedge Q)$	$\neg P \vee \neg Q$
t	t	f	f	t	f	f
t	f	f	t	f	t	t
f	t	t	f	f	t	t
f	f	t	t	f	t	t

표의 각 행에서 $\neg(P \wedge Q)$와 $\neg P \vee \neg Q$의 값이 일치함을 확인할 수 있다. 따라서 마찬가지로 함의의 진리표와 표기 2.18에 의해

\neg(P \wedge Q) \iff \neg P \vee \neg Q

가 성립한다.

□

English

Let $P$ and $Q$ be sentences. Show that

\neg(P \vee Q) \iff \neg P \wedge \neg Q

and

\neg(P \wedge Q) \iff \neg P \vee \neg Q.

We consider the truth table for the first De Morgan's law $\neg(P \vee Q) \iff \neg P \wedge \neg Q$.

Truth table for $\neg(P \vee Q)$ and $\neg P \wedge \neg Q$
$P$	$Q$	$\neg P$	$\neg Q$	$P \vee Q$	$\neg(P \vee Q)$	$\neg P \wedge \neg Q$
t	t	f	f	t	f	f
t	f	f	t	t	f	f
f	t	t	f	t	f	f
f	f	t	t	f	t	t

We see that $\neg(P \vee Q)$ and $\neg P \wedge \neg Q$ agree in every row. Therefore, by the truth table for the implication, both $\neg(P \vee Q) \implies \neg P \wedge \neg Q$ and $\neg P \wedge \neg Q \implies \neg(P \vee Q)$ are true, and by Notation 2.18,

\neg(P \vee Q) \iff \neg P \wedge \neg Q

holds.

Next, we consider the truth table for the second De Morgan's law $\neg(P \wedge Q) \iff \neg P \vee \neg Q$.

Truth table for $\neg(P \wedge Q)$ and $\neg P \vee \neg Q$
$P$	$Q$	$\neg P$	$\neg Q$	$P \wedge Q$	$\neg(P \wedge Q)$	$\neg P \vee \neg Q$
t	t	f	f	t	f	f
t	f	f	t	f	t	t
f	t	t	f	f	t	t
f	f	t	t	f	t	t

We see that $\neg(P \wedge Q)$ and $\neg P \vee \neg Q$ agree in every row. Therefore, similarly, by the truth table for the implication and Notation 2.18,

\neg(P \wedge Q) \iff \neg P \vee \neg Q

holds.

□

NOTE

한국어

마지막으로 이 강의노트와 수학 전반에서 사용될 수학 기호들을 소개하며 이 절을 마친다.

English

Finally we close this section by introducing math symbols which will be used in this lecture note and overall mathematics.

NOTATION 2.22 수학 기호 Math symbols

한국어

"iff"라는 약어를 "필요충분조건(if and only if)"을 나타내기 위해 사용한다. 즉 iff는 $\iff$를 의미한다.
$\wedge$는 "그리고(and)"를 나타내기 위해 사용한다.
$\vee$는 "또는(or)"을 나타내기 위해 사용한다.
모든 명제 $P$, $Q$, $R$, $\ldots$에 대해, $P \implies Q \implies R \implies \cdots$ 는 $P \implies Q$, $Q \implies R$, 등등을 의미하는 것으로 이해해야 한다.
$\exists$는 "존재한다(there exists)"를 나타내기 위해 사용한다
$\forall$은 "모든 ~에 대해(for all)"를 의미한다.
$\ni$는 "~를 만족하는"으로 읽으며 성질을 서술하는 데 사용한다.

English

We use the abbreviation “iff” to denote “if and only if”, i.e. iff means $\iff$ .
$\wedge$ is used for “and”.
$\vee$ is used for “or”.
For all sentences, $P$, $Q$, $R$, $\ldots$, $P \implies Q \implies R \implies \cdots$ should be understood to mean that $P \implies Q$, $Q \implies R$, and so on.
$\exists$ is used to denote “there exists”
$\forall$ means “for all”.
$\ni$ is read as “such that” and it is used to describe properties.

2. 명제와 논리Sentence and Logic

§2 Sentence and Logic · 명제와 논리