1. The Foundation: Logic and Proofs

1.1. Propositional Logic

Introduction

Propositional logic(명제 논리) = 문장 구조를 모델링 할 때 사용한다.
Proposition = True, Flase의 값 중 하나만 갖는 Statement이다.
Proposition이기 위해 Declarative sentence여야 한다.

팁

Example

• $2+2=3$ (Proposition이나 False)
• $x+1=2$ (Not proposition)

Logical Operators

Name	Sign	Example	Mean
Negation	$\neg$	$\neg p$	not p
Conjunction	$∧$	$p∧q$	p and q
Disjunction	$∨$	$p∨q$	p or q
Exclusivr-or	$⊕$	$p⊕q$	p excusive or q
Implication	$→$	$p→q$	if p, then q
Biconditional	$\leftrightarrow$	$p\leftrightarrow q$	p if and only if q

Negation Truth Table

p	\neg p	\neg (\neg p)
T	F	T
F	T	F

Conjunction Truth Table

p	q	p∧q
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction Truth Table

p	q	p∨q
T	T	T
T	F	T
F	T	T
F	F	F

Exclusivr-or Truth Table

p	q	p⊕q
T	T	F
T	F	T
F	T	T
F	F	F

Conditional Truth Table

p	q	p→q
T	T	T
T	F	F
F	T	T
F	F	T

Antecedent(전건)가 False인 경우 그 Conditional은 Consequent(후건)에 관계 없이 True이다.
이를 Vacuous Truth(공허한 참)이라고 한다.

Biconditional Truth Table

p	q	p\leftrightarrow q
T	T	T
T	F	F
F	T	F
F	F	T

Antecedent와 Consequent가 모두 False일 때 Vacuous Truth에 의거해 True이다.

Precedence of Logical Operators

Priority	Logical operator
1	$\neg$
2	$∧$
3	$∨$
4	$→$
5	$\leftrightarrow$

Compound Proposition

Compound proposition(복합 명제)은 괄호와 Operator의 순서에 따라 Truth value를 도출한다.

팁

Example

$(p∨\neg q)→(p∧q)$

단계 별로 나눠 해결한다.

$p = T$, $q = T$

1. $p∨\neg q = T$
2. $p∧q = T$
3. $(p∨\neg q)→(p∧q)$

Translating Natural Language Sentences

Natural language를 Compound proposition으로 나타내어 문장의 모호성을 제거할 수 있다.

Boolean Search

Boolean search는 Propositional logical technique를 이용해 방대한 정보를 검색할 때 사용한다.

Boolean operator	Decription
AND	Intersection
OR	Union
NOT	Subtraction

Boolean search로 정확도 향상, 유연한 검색, 검색 시간 절약 등 이점을 가질 수 있다.

Logic and Bit Operations

Bit operation	Sign	Description	Example(A = 1101, B = 1011)
AND	&	Retruns 1 when all corresponding bits are 1.	A&B=1001
OR	|	If any of the corresponding bits are 1, then 1 is returned.	A|B=1111
NOT	~	Inverse bits.	~B=0100
XOR	^	If the corresponding bits are different, then 1 is returned.	A^B=0110
Left Shift	<<	Move a specified number of bits to the left.	A<<2=11 0100
Right Shift	>>	Move bits to the right by a specified number while maintaining the sign.	B>>2=10

1.2. Propositional Equivalences

Tautology and Contingency

Tautology(항진 명제) = 항상 Value가 True인 Compound proposition
Contigency(모순 명제) = 항상 Value가 False인 Compound proposition

Logical Equivalences

Logical equivalences(논리적 동치)는 항상 같은 Truth value를 갖는 Compound proposition의 관계를 말한다.
Compound proposition p, q가 Logical equivalence라면 Notation으로 p≡q이다.

Propositional Laws

De Morgan's laws(드 모르간 법칙)

• $\neg (p∨q)≡(\neg p∧\neg q)$
• $\neg (p∧q)≡(\neg p∨\neg q)$

Identity laws(항등 법칙)

• $p∧T≡p$
• $p∨F≡p$

Domination laws(지배 법칙)

• $p∨T≡T$
• $p∧F≡F$

Idenpotent laws(등멱 법칙)

• $p∨p≡p$
• $p∧p≡p$

Double negation laws(이중 부정 법칙)

• $p∨\neg p≡T$
• $p∧\neg p≡F$

Commutative laws(교환 법칙)

• $p∨q≡q∨p$
• $p∧q≡q∧p$

Associative laws(결합 법칙)

• $(p∨q)∨r≡p∨(q∨r)$
• $(p∧q)∧r≡p∧(q∧r)$

Distributive laws(분배 법칙)

• $p∨(q∧r)≡(p∨q)∧(p∨r)$
• $p∧(q∨r)≡(p∧q)∨(p∧r)$

Absorption laws(흡수 법칙)

• $p∨(p∧q)≡p$
• $p∧(p∨q)≡p$

Logical Equivalences Involving Conditional Statements

• $p→q≡\neg p∨q$
• $p→q≡\neg q→\neg p$
• $p∨q≡\neg p→q$
• $p∧q≡\neg (p→\neg q)$
• $\neg (p→q)≡p∧\neg q$
• $(p→q)∧(p→r)≡p→(q∧r)$
• $(p→r)∧(q→r)≡(p∨q)→r$
• $(p→q)∨(p→r)≡p→(q∨r)$
• $(p→r)∨(q→r)≡(p∧q)→r$

Logical Equivalences Involving Biconditionals

• $p\leftrightarrow q≡(p→q)∧(q→p)$
• $p\leftrightarrow q≡\neg p\leftrightarrow \neg q$
• $p\leftrightarrow q≡(p∧q)∨(\neg p∧\neg q)$
• $\neg (p\leftrightarrow q)≡p\leftrightarrow \neg q$

Constructing New Logical Equivalences

식 풀이 편이를 위해 Logical equivalence를 이용할 수 있다.

팁

Example

$\neg (p∨(\neg p∧q))≡\neg p∧\neg q$

$\neg (p∨(\neg p∧q))$

$≡ \neg p∧\neg (\neg p∧q)$ ∵ De Morgan's laws

$≡ \neg p∧(\neg (\neg p)∨\neg q)$ ∵ De Morgan's laws

$≡ \neg p∧(p∨\neg q)$ ∵ Double negation laws

$≡ (\neg p∧p)∨(\neg p∧\neg q)$ ∵ Distributive laws

$≡ F∨(\neg p∧\neg q)$ ∵ \neg p∧p=Contingency

$≡ \neg p∧\neg q$ ∵ Commutative laws and Identity laws

1.3. Predicates and Quantifiers

Predicates

Proposion 'A is B'에서 A를 Subject(주어), B를 Predicate(술어)라고 한다.

Propositional function(=Condition)은 Variable value에 따라 Truth value가 달라지는 Proposition이다.

Propositional function $P(x_1, x_2, x_3, ..., x_n)$을 n-place predicate(n항 술어)라 한다.

Propositional function는 Variable이 지정되지 않은 경우 Truth value를 가질 수 없다.

• Precondition(사전 조건): 유효한 Input을 기술하는 Statement를 의미
• Postcondition(사후 조건): 유효한 Output을 기술하는 Statement를 의미

팁

Example

temp := x
x := y
y := temp

Precondition: x=a, y=b
Postcondition: x=b, y=a

Quantifiers

Quantifier(한정자, 양화사)는Propositional function의 Truth value를 판별하기 위해 Domain(=Universe of discourse)의 범위를 지정하기 위해 사용하는 것이다.

• Universal quantifier
  • 한국어로 전체한정자, 전체양화사, 전칭기호라고도 하며 Domain의 모든 Value를 의미한다.
  • Domain의 모든 Element에 대해 만족할 경우에만 True이다.
  • Domain U에 속하는 모든 x에 대해 Propositional function $P(x)$를 Notation으로 $∀xP(x)$로 표기한다.
• Existential Quantifier
  • 한국어로 존재한정자, 존재양화사, 존재기호라고도 하며 Domain에 속하는 어떠한 Value를 의미한다.
  • Domain의 Element 중 하나라도 만족할 경우 True이다.
  • Domain U에 속하는 어떤 x에 대해 Propositional funtion $P(x)$를 Notation으로 $∃xP(x)$로 표기한다.
  • $∃_1$로 표기한 것은 Uniqueness quantifier로 Domain의 Element 중 단 하나만 만족할 경우에만 True이다.

Quantifiers with Restricted Domains

Abbreviated notation은 종종 Domain을 제한하는 데 사용한다.
Abbreviated에서 Variable이 충족해야 하는 Condition이 Quantifier 이후 포함된다.

팁

Example

Domain이 Real number인 Poposition P가 "Negative number의 제곱은 Positive number이다." 일 때

$∀x<0(x^2>0)$의 경우 $∀x(x<0→x^2>0)$

Precedence of Quantifiers

Quantifier는 모든 Logical Operation보다 우선순위가 높다.

Binding Variables

Variable x에 Quantifier를 사용할 경우 Variable x는 Bound(범위에 든다)라고 표현한다.
Variable x가 Bound하지 않거나 특정 Value로 지정되지 않은 경우 Free(범위에서 벗어났다)라고 표현한다.

Bound variable을 한국어로 기속 변수라 하고 Free variable을 한국어로 자유 변수라고 한다.

Variable이 Quantifier가 적용된 Scope를 벗어나면 Free variable이 된다.

Logical Equivalences Involving Quantifiers

Predicate와 Quantifier를 포함하는 Statement는 어떤 Predicate거나 Quantifier이던 상관 없이 동일한 Truth value를 갖는 경우에만 Logical equivalence(논리적 동치)하다고 한다.

Predicateㅇ와 Quantifier를 포함하는 두 Statement S, T에 대해 S와 T가 Logical equivalence할 경우 Notation으로 $S≡T$라 한다.

Negating Quantified Expressions

$\neg ∀xP(x)≡∃x\neg P(x)$이고 $\neg ∃xP(x)≡∀x\neg P(x)$임을 De Morgan's laws for quantifiers라고 부른다.

Negation	Equivalent statement	When is negation true?	When False
\neg ∃xP(x)	∀x\neg P(x)	For every $x$, $P(x)$ is false.	There is an $x$ for which $P(x)$ is true.
\neg ∀xP(x)	∃x\neg P(x)	There is an $x$ for which $P(x)$ is false.	$P(x)$ is true for every x.

Translating from Natural Language into Logical Expressions

Statement of natural language를 Logical expression으로 변환하는 것은 수학, Logical programming, AI, Software Engineering 등에 중요한 작업이다.

Quantifier를 사용할 때 Natural language를 Logical expression으로 변환하는 것이 더 복잡하므로 주의하여 변환하여야 한다.

Examples from Lewis Carroll

팁

Example

"All lions are fierce." = $∀x(P(x)→Q(x))$
"Some lions do not drink coffee." = $∃x(P(x)∧\neg R(x))$
"Some fierce creatures do not drink coffee." = $∃x(Q(x)∧\neg R(x))$

$P(x)$ is "x is lion.".
$Q(x)$ is "x is fierce.".
$R(x)$ is "x drinks coffee."

Logical Programming

Programming language의 중요한 유형은 Rule of preicate logic을 사용하여 추론하도록 설계된 것이다.
아래는 1970년대 AI 분야 Computer Science들이 개발한 Prolog(PROgramming in LOGic)라는 Language를 예시로 들어 설명한다.

팁

Example

각 수업 교수와 학생이 등록한 수업을 알려주는 Prolog program을
Predicate instructor(p, c)와 enrolled(s, c)를 사용해 교수 p가 수업 c의 강사이고 학생 s가 수업 c를 신청했다는 것을 표현 가능하다.

instructor(chan, math273)

...

enrolled(kevin, math273)

...

새로운 Predicate 교수 p가 학생 s를 가르치는 것을 만들 때 Prolog rules를 사용하여 정의할 수 있다.

teaches(p, s) :- instructor(p, c), enrolled(s, c)

즉 teaches(p, s)는 교수 p가 c 수업의 강사이며 학생 s가 c 수업을 신청한 경우에만 참이다.

Prolog는 주어진 facts와 rules를 사용하여 Query에 답변한다.

?enrolled(kevin, math273) //yes

?enrolled(X, math273) // kevin

1.4. Nested Quantifiers

Nested Quantifiers

Nested quantifier(중첩 한정자, 중첩 양화사)는 두 Quantifier 중 하나가 다른 범위 내에 있는 경우를 의미한다.

팁

Example

$\forall x \exists y(x+y=0)$

Quantifier scope 내에 있는 모든 Value는 Propositional function으로 판단 가능하다.
$\forall xQ(x)$일 때 $Q(x)$는 $\exists yP(x, y)$이고, $P(x, y)$는 $x+y=0$으로 표현 가능하다.

Nested loop 상황으로 Nested quantifier를 이해하는 것이 유용할 수 있다.

The Order of Quantifiers

모든 Quantifier가 Universal quantifier거나 Existential quantifier인 경우 순서의 영향을 받지 않는다.
그렇지 않은 경우 순서에 따라 영향을 받는다.

팁

Example

$P(x, y) = "x+y=0" , Dom(f)=R$일 때
$\forall x\exists yP(x, y)$와 $\exists y \forall xP(x, y)$의 Truth value

• $\forall x\exists yP(x, y)$의 경우 "모든 Real number $x$에 대해 $P(x, y)$를 만족하는 Real number y가 존재" 즉 Truth value = True이다.
• $\exists y \forall xP(x, y)$의 경우 "Real number $y$가 존재하고, 모든 Real number $x$에 대해 $P(x, y)$가 존재" 즉 Truth value = False이다.

Translating Mathematical Statements into Statements Involving Nested Quantifiers

팁

Example

"두 Positive integer의 Sum은 항상 Positive integer이다."를 Nested quantifier를 포함한 Logical statement로 변환

1. Quantifier와 Domain이 표시되도록 변경한다.

   "모든 Integer에 대해, 두 Integer가 Positive일 때, 이 Positive integer의 Sum은 Positive integer이다."

2. Variable로 대치한다.
   "모든 Integer $x$, $y$에 대해, $x$가 0보다 크고 $y$가 0보다 크다면 $x+y$는 0보다 크다."

3. Quantifier를 사용하여 대치한다.
   $\forall x\forall y((x>0)\land(y>0)\rightarrow(x+y>0))$

Translating from Nested Quantifiers into Natural Language

Nested quantifier를 포함한 Statement를 Natural language로 변환하는 것은 복잡할 수 있다.
Statement를 변환하는 첫 단계는 Statement의 Quantifier와 Predicate가 무엇을 의미하는 지 작성하는 것이 좋다.
다음 단계에서는 의미를 단순한 문장으로 표현하는 것이 좋다.

팁

Example

$C(x)$는 "$x$는 컴퓨터를 가지고 있다.", $F(x, y)$는 "$x$와 $y$는 친구이다.", $x$와 $y$의 Domain이 같은 학교를 다니는 학생일 때 $\forall x(C(x)\lor\exists y(C(y)\land F(x, y)))$를 Natural language로 변환

1. "같은 학교를 다니는 모든 학생 $x$, $y$에 대해 $x$가 컴퓨터를 가지고 있거나 $y$가 컴퓨터를 가지고 있고 $x$와 $y$가 친구인 학생 $y$가 있다."
2. "학교의 모든 학생이 컴퓨터를 가지고 있거나 컴퓨터를 가지고 있는 친구가 있다."

Negating Nested Quantifiers

Nested quantifier를 포함한 Statement의 부정은 단일 Quantifier가 포함된 문장을 부정하는 규칙을 연속으로 적용하여 부정 가능하다.

팁

Example

$\forall x \exists y (xy=1)$의 부정을 Quantifier 앞에 Negation이 나오지 않게 표현

• \lnot \forall x \exists y(xy=1) \equiv \forall x \lnot \exists y(xy=0) \equiv \exists x \forall y \lnot(xy=1) \equiv \exists x \forall y (xy\not = 1)$$$$\becauseDe Morgan's law for quantifiers

1.5. Rules of Inference

Proof and Rules of Inference

Arguments(논증) = Conclusion(결론)으로 끝나는 일련의 Statement이다.
Valid argument(유효한 논증) = Conclusion이 Argument의 이전 Statement나 Premise의 True에서 나와야 함을 의미한다. 즉 Argument는 모든 Premise가 True일때 Conclusion이 True일 수 밖에 없는 경우 Valid argument이다.
Proof(증명) = Mathematic에서 Mathematical statement의 Truth를 확립하는 Valid argument이다.
Rules of inference(추론 규칙) = 이미 존재하는 Statement에서 새 Statement를 Inference하기 위해 Valid argument를 구성하기 위한 틀과 같은 역할을 한다.

Valid Arguments in Propositional Logic

팁

Example

"현재 비밀번호가 있다면 네트워크에 로그인 가능하다.", "현재 비밀번호가 있다.", 따라서 "네트워크에 로그인 가능하다."가 Valid argument인 지 확인

Valid argument인 지 확인하기 위해 $p$를 "현재 비밀번호가 있다.", $q$를 "네트워크에 로그인 가능하다."로 표현한다.

$p\rightarrow q\\ p \\-\\ \therefore q$

$p$, $q$가 Proposition일 때 $((p\rightarrow q) \land p)\rightarrow q$는 Tautology이기에 $p\rightarrow q$, $p$(Premise)가 모두 True일 때 $q$또한 역시 True가 된다.

Rules of Inference for Propositional Logic

Rules of inference의 경우 더 복잡한 Valid argument의 형태를 구성하는 Basic element로 사용 가능하다.
Tautology $(p \land (p\rightarrow q)\rightarrow q)$를 Modus ponens(긍정식)이나 Distributive law라고 말하며 Rules of inference의 Basic이 된다.
Notation은 Premise를 한 열에 나열한 후 Conclusion을 수평선 아래에 작성한다.

Rules of inference	Tautology	Name
$p\\ p\rightarrow q \\-\\ \therefore q$	$[p\land(p\rightarrow q)]\rightarrow q$	Modus ponens(긍정식)
$\lnot q\\ p\rightarrow q \\-\\ \therefore \lnot p$	$[\lnot q \land(p\rightarrow q)]\rightarrow \lnot p$	Modus tollens(부정식)
$p\rightarrow q\\ q\rightarrow r \\-\\ \therefore p\rightarrow r$	$[(p\rightarrow q)\land(q\rightarrow r)]\rightarrow(p\rightarrow r)$	Hypothetical syllogism(가언적 삼단논법)
$p\lor q\\ \lnot p\\-\\ \therefore q$	$[(p\lor q)\land \lnot p]\rightarrow q$	Disjunctive syllogism(선언적 삼단논법)
$p\\-\\ \therefore p\lor q$	$p\rightarrow(p\lor q)$	Addition(가산 논법)
$p\land q\\-\\ \therefore q$	$(p\land q)\rightarrow p$	Simplification(단순화 논법)
$p\\ q\\-\\ \therefore p\land q$	$[(p)\land(q)]\rightarrow(p\land q)$	Conjunction(논리곱 논법)
$p\lor q\\ \lnot p\lor r \\-\\ \therefore q\lor r$	$[(p\lor q)\land(\lnot p\lor r)]\rightarrow(q\lor r)$	Resolution(분해 증명)

Using Rules of Inference to Build Arguments)

Premise가 많은 경우 Arguments가 타당함을 보여주기 위해 여러 개의 Rules of Inference가 필요한 경우가 있을 수 있다.

팁

Example

Premise "오늘 오후는 맑지 않고 어제보다 더 춥다.", "맑을 때만 수영을 할 것이다.", "수영을 하지 않는다면 카누를 탈 것이다.", "카누를 타면 일몰까지 집에 도착할 것이다."와 Conclusion "일몰까지 집에 도착할 것이다."로 구성되어 있는 Argument가 Valid argument인 지 확인

Proposition $p$ "오늘 오후는 맑다.", $q$ "오늘 오후는 어제보다 더 춥다.", $r$ "수영을 할 것이다.", $s$ "카누를 탈 것이다.", $t$ "일몰까지 집에 도착할 것이다."로 설정하고 위 Promise들을 $\lnot p\land q$, $r\rightarrow p$, $\lnot r\rightarrow s$, $s\rightarrow t$일 때 Conclusion $t$인 Argument가 된다.

Promise들이 모두 True일 때 t가 True인 지 확인하여 Valid argument인 지 판단할 수 있다.
즉, $[(\lnot p\land q )\land (r\rightarrow p) \land (\lnot r\rightarrow s) \land (s\rightarrow t)] \rightarrow t$임을 간단히 보여주기 위해 $\lnot p\land q$를 Simplication으로 $\lnot p$, $\lnot p \land (r\rightarrow p)$를 Modus tollens로 $\lnot r$, $\lnot r \land (\lnot r\rightarrow s)$를 Modus ponens로 $s$, $s \land (s\rightarrow t)$를 Modus ponens로 $t$를 도출하기에 Promise들이 참일 경우 Conclusion $t$는 항상 True(Tautology $t\rightarrow t$)이다.

Resolution

Resolution은 Tautology $((p\lor q)\land (\lnot p\lor r))\rightarrow(q\lor r)$을 기반으로 한다.
Resolution의 가장 뒤에 있는 Disjunction $q \lor r$을 Resolvent(분해식)라고 한다.
위 Tautology에서 $q=r$일 때 $((p\lor q)\land(\lnot p\lor q))\rightarrow(q\lor q)$, 즉 $((p\lor q)\land(\lnot p\lor q))\rightarrow q$를 도출할 수 있다.
만약 $r=F$라면 $((p\lor q)\land(\lnot p\lor F))\rightarrow(q\lor F)$, 즉 $(p\lor q)\land \lnot p\rightarrow q$를 도출할 수 있다.

Fallacies

Fallacy는 잘못된 Argument에서 발생한다.
Rules of inference와 유사하나 Tautology가 아닐 때 주로 발생한다.

• Fallacy of affirming the conclusion(결론 단언의 오류)
  • $(p\rightarrow q)\land q)\rightarrow p$
  • Ex) "사람은 동물이니, 동물은 사람이다."
• Fallacy of denying the hypothesis(가정 부정의 오류)
  • $((p\rightarrow q)\land \lnot p)\rightarrow \lnot q$
  • Ex) "사람은 동물이니, 사람이 아니면 동물이 아니다."

Rules of Inference for Quantified Statements

Quantifier를 포함하는 Statement에 대한 Rules of inference는 크게 네 종류가 있다.

1. Universal instantiation(전칭 예시화)
   1. 모든 $x$에 대해 $P(x)$가 True라면 $P(c)$는 True이다.
2. Universal generalization(전칭 일반화)
   1. 임의의 $c$에 대해 Domain에 속하는 모든 Element들을 대입할 지라도 $P(c)$가 True라면 모든 $x$에 대해 $P(x)$는 True이다.
3. Existential instantiation(존재 예시화)
   1. $\exists xP(x)$가 True라면 Domain에 $P(c)$를 True로 만드는 어떤 Element c가 존재한다.
4. Existential generalization(존재 일반화)
   1. 임의의 $c$에 대해 $P(c)$가 True라면 $\exists xP(x)$가 True이다.

Combining Rules of Inference for Propositions and Quantified Statements

Universal instantiation은 Modus ponens와 함께 사용되는 경우가 많아 Universal modus ponens(전칭긍정논법)이라고도 한다.
$\forall x(P(x)\rightarrow Q(x))$가 True이고 Universal quantifier의 Domain에서 특정 Element $a$에 대해 $P(a)$가 True라면 $Q(a)$역시 True여야 한다는 의미이다.

Universal instation은 Modus tollens와도 함께 사용되는 경우가 많아 Universal modus tollens(전칭부정논법)이라고도 한다.
$\forall x(P(x)\rightarrow Q(x))$가 True이고 Universal quantifier의 Domain에서 특정 Element $a$에 대해 $\lnot Q(a)$가 True라면 $\lnot P(a)$역시 True여야 한다는 의미이다.

1.6. Introduction to Proofs

Proofs

Proof(증명) = Mathematical statement의 Truth를 확립하는 Valid argument이다.
Proof는 Hypotheses of theorem(정리의 가설), 사실로 가정된Axiom(공리), 이전에 증명된 Theorem들을 사용 하여 Proof의 마지막 단계에서 Statement의 Truth를 확립한다.
Methods of proof(증명 방법)은 Mathematical theorem을 증명하는 데 사용될 뿐만 아니라 Computer science에서도 다양하게 응용되므로 중요하다.

Terminology

• Theorem
  • True로 증명될 수 있는 Proposition이다.
  • 중요하다고 여겨지는 Statement에만 사용된다.
  • 중요하지 않은 Theorem을 Proposition이라고 한다.
  • 하나 이상의 Premise와 Conclusion을 갖는 Conditional statement의 보편적인 Quantifier일 수 있다.
• Proof
  • Theorem이 True임을 나타낼 때 증명명한다고 한다.
  • Proof는 Theorem의 Truth를 확립하는 Valid argument이다.
  • Axiom이나 Postulate, Premise가 포함될 수 있다.
• Axiom
  • 정의가 필요하지 않은 기본 용어를 사용하여 표현할 수 있다.
  • 가장 기초적인 근거가 되는 Proposition이다.
  • 증명할 필요 없이 자명한 진리이거나 다른 Proposition을 증명하는 Premise가 되는 원리이다.
• Rules of inference
  • Terminology의 Definition과 함께 다른 Argument로부터 Conclusion을 도출하는 데 사용되며 Proof step을 연결하는 역할을 한다.
• Lemma( Plural: Lemmas, Lemmata)
  • 다른 Conclusion의 Proof에 도움이 되는 덜 중요한 Theorem이다.
  • 복잡한 Proof의 경우 일반적으로 일련의 Lemma들을 사용하여 Proof할 때 더 쉽게 이해할 수 있다.
• Corollary
  • Proved theorem에서 직접 확립할 수 있는 Theorem을 뜻한다.
• Conjecture
  • 일반적으로 부분적인 증거, 경험적 주장, 전문가의 직감에 근거해 True로 제안되는 Statement이다.
  • Conjecture는 Prove될 시 Theorem이 된다.
  • Conjecture는 False인 경우도 많아 Theorem과 다르다.

Understanding How Theorems are Stated

많은 Theorem은 Integer나 Real number와 같은 Domain의 모든 Element에 대해 Property가 성립한다고 주장한다.
Theorem을 정확하게 표현하기 위해 Universal quantifier를 포함하여야 하지만 Mathematic에서는 생략하는 것이 관례이다.

Proof의 첫 단계는 일반적으로 Domain의 Element를 선택하는 것이다.

Methods of Proving Theorems

$\forall x(P(x)\rightarrow Q(x))$의 형태의 Theorem을 증명하기 위해 $P(c)\rightarrow Q(c)$가 True임을 보여주는 것이 목표이다.
$c$는 Domain의 임의의 Element이고 Universal generalization을 적용하여 이 Proof에서 Conditional statement가 True임을 보여야 한다.

Vacuous truth을 고려하여 $p\rightarrow q$일 때 $p$가 True, $q$가 True임을 증명하면 된다.

증명법은 크게 Direct proofs와 Indirect proofs로 나뉜다.

• Direct proof
  • Condition statement $p\rightarrow q$의 증명은 $p$가 True일 때 $q$가 True인 Combination을 보여주는 것이다.
  • $p$가 True라고 가정한 후 Axiom, Theorem등을 사용하여 $q$가 True임을 증명
• Indirect proof
  • Direct proof로 증명하기 힘들 때 Indirect proof를 사용하여 증명
  • Proof by contraposition(대우 증명법)
    • $p\rightarrow q \equiv \lnot q\rightarrow \lnot p$임을 이용하여 $\lnot q\rightarrow \lnot p$가 True임을 증명하는 방법이다.
  • Proof by contradiction(모순 증명법)
    • 증명할 Proposition의 Negation이 True라고 가정한 후 Logical contradiction을 찾아 증명하는 방법이다.
  • Proof by counterexample(반례 증명법)
    • Logical contradiction이되는Counterexample을 찾아 증명하는 방법이다.

Mistakes in Proof

증명을 구성할 때 흔히 저지르는 오류들의 이유로는 논리적이지 않은 단계를 도입하거나 산수, 기본 대수에서 실수하는 경우 발생한다.

1.7. Proof Methods and Strategy

Exhaustive Proof and Proof by Cases

Exhaustive proof(진수 증명)의 경우 비교적 적은 수의 예시를 조사해 증명할 수 있을 때 모든 가능성을 소진하여 증명하는 방법이다.

Proof by cases(사례별 증명)의 경우 Conditional statement $(p_1\lor p_2\lor \cdots \lor p_n)\rightarrow q$임을 증명할 때 Tautology $((p_1\lor p_2\lor \cdots \lor p_n)\rightarrow q)\leftrightarrow ((p_1\rightarrow q)\land(p_2\rightarrow q)\land \cdots \land(p_n\rightarrow q))$를 Rule of inference로 사용한다.
원 Conditional statement를 n개의 Conditional statement로 개별적으로 증명해 증명할 수 있다.

Existence Proofs

Existence proof는 특정 Proposition이 성립할 수 있는 지 증명하기 위해 Proposition을 만족하는 하나의 경우를 보이는 Proof method이다.
이 유형의 형태는 $\exists xP(x)$이다.

$P(a)$가 True인 Element $a$를 찾는 방법을 Constructive proof(구성적 증명)이라고 하고
다른 방법으로 $\exists xP(x)$가 True임을 찾는 방법을 Nonconstructive proof라고 한다.

Nonconstructive proof의 경우 Proof by contradiction을 사용하고 Exist quantifier의 Negation이 Contradiction을 함축한다는 것을 보여준다.

Uniqueness Proofs

Uniqueness proof는 Property를 갖고 있는 Element가 정확히 하나 있다고 주장하는 Theorem에서 사용되는 방법이다.
위 같은 상황에서 Statement를 증명하기 위해 이 Property를 가진 Element가 존재하나 다른 Element는 이 Property를 가지고 있지 않음을 증명해야 한다.
Notation으로 $\exists x(P(x)\land \forall y(y\not =x\to \lnot P(y)))$로 표현할 수 있다.

Proof Strategies

Forward reasoning(전방 추론)의 경우 Premise부터 Axiom, Theorem순으로 증명을 구성하는 방법이고 목표부터 반대로 Premise를 찾아가는 방식을 Backward reasoning(후방 추론)이라고 한다.

Looking for Counterexamples

Conjecture를 증명하려고 시도하다가 실패할 경우 Counterexample을 찾을 수 있다.
Counterexample을 찾을 수 없는 경우 다시 Proposition을 증명해 볼 수 있다.