[이산수학] 1. The Foundations: Logic and Proofs

오늘 공부할 단원은 챕터 1입니다😎

 

1. The Foundations: Logic and Proofs>

1. Propositional Logic(1.1-1.2)
2. Propositional Equivalances(1.3)
3. Predicates and Quantifiers(1.4)
4. Nested Quantifiers(1.5)
5. Rules of Inference(1.6)
6. Proofs(1.7-1.8) 

---

1. Propositional Logic 

• Proposition(명제): a declarative sentence, 선언문으로 참이거나 거짓인 문장입니다. 동시에 참과 거짓일 수는 없습니다.
• Propositional variable(statement variable): 명제를 변수로 나타낸 것입니다. 보통 p,q,r,s ... 를 사용합니다
• Truth value(진리값): 명제가 참이면 T (true), 거짓이면 F (false)의 값을 갖습니다

 

Logical operators

• Negation (NOT ~ 또는 ¬)
• Conjunction (AND ∧)
  • p∧q: p, q가 둘 다 참일 때만 참입니다
• Disjunction (OR ∨)
  • p∨q: p, q 중 1개라도 참 값이 있으면 참입니다
• Exclusive or (XOR ⨁)
  • p⨁q: p, q의 값이 서로 다르면 참입니다
• Implication (if - then)
  • p→q: p가 참일 때, q가 거짓이면 거짓입니다. 나머지 경우는 참입니다. (p가 F인 경우에 대해서는 "p면 q인지"에 대해 아무것도 보장하지 않으므로 p가 F면 전부 참이라고 봅니다)
  • 이때 p는 hypotheis / antecedent / premise라고 부르고, q를 conclusion / consequence라고 부릅니다
  • if p then q = q if p = p is sufficient for q = p imlies q = q when(ever) p = p only if q = q is necessary for p = q follows from p = q unless ~p
  • p→q의
    • converse(역): q→p
    • contrapositive(대우): ~q→~p
    • inverse: ~p→~q
• Biconditional (if and only if)
  • p↔q: p→q이고 q→p인 경우 참입니다. 즉 p,q가 둘 다 같은 값일 때 참입니다.
  • ~(p⨁q)와 진리표가 동일합니다

한 개 이상의 명제를 logical operator를 통해 연결하면 compound proposition을 만들 수 있습니다.

operator가 실행되는 우선순위는 아래와 같습니다

operator	precedence(우선순위)
~	1
∧	2
∨	3
→	4
↔	5

 

 

0은 False를 나타내고, 1(사실 0이 아닌 모든 수)는 True를 나타냅니다. 이에 0,1로만 이루어진 bit에서 앞서배운 logical operator를 적용하기도 합니다. bit에서 적용한 연산을 bit operation이라고 합니다

bit operation에는 ∧, ∨, ⨁ 가 있습니다. 각각은 bit 연산일 때 bitwise를 붙여 bitwise AND, bitwise OR, bitwise XOR이라 부릅니다. 

연산 방법은 각 bit 자릿수에 맞추어 AND, OR, XOR 연산을 하면됩니다

   1101

   1010

   -------

   1000  : bitwise AND

   1111  : bitwise OR

   0111  : bitwise XOR

 

 

2. Propositional Equivalances 

• Tautology: 항상 T값을 갖는 compound proposition (예를 들면, p∨~p)
• Contradiction(모순): 항상 F값을 갖는 compound proposition(예를 들면, p∧~p)
• Contingency: tautology도 contradiction도 아닌 proposition (대부분의 proposition이 contingency다)
• logical equivalence: p↔q가 tautology일 때, p와 q는 logically equivalent합니다
  • logically equivalent를 p≡q 또는 p⇔q로 표현합니다

 

logical equivalence를 보장하는 여러 법칙들이 있습니다. 

Equivalences	Name
p∧T≡p p∨F≡p	Identity laws
p∨T≡T p∧F≡F	Domination laws
p∧p≡p p∨p≡p	Idempotent laws
~(~p)≡p	Double negation law
p∨q≡q∨p p∧q≡q∧p	Commutative laws
p∨(q∧r)≡(p∨q)∧(p∨r) p∧(q∨r)≡(p∧q)∨(p∧r)	Distributive laws
~(p∧q)≡~p∨~q ~(p∨q)≡~p∧~q	De Morgan's laws
p∨~p≡T p∧~p≡F	Negation laws

굳이 법칙을 외우지 않더라도 벤다이어그램(venn diagram)을 그려보면 logical equivalence를 찾기 쉽습니다

 

p → q ≡ ¬p ∨ q
p → q ≡ ¬q →¬p  (대우)
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p →¬q)
¬(p → q) ≡ p ∧¬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

 

p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧¬q)  (: ≡ (¬p ∨ q) ∧ (p ∨ ¬q))
¬(p ↔ q) ≡ p ↔¬q

 

3. Predicates and Quantifiers 

 

 

 

4. Nested Quantifiers <

 

5. Rules of Inference

• Argument: a sequence of proposition
• Premises: argument에서 마지막을 제외한 모든 명제
• Conclusion: final proposiiton
• valid: 모든 premise가 참이면 conclusion이 참일 때

 

• Modus ponen(the mode of affirming)
• Modus tollen(the mode of denying)
• Hypothetical syllogism
• Disjuctive syllogism
• Simplification
• Addition
• Conjuction

6. Proofs 

p->q임을 증명하는 방법

1. Direct proof: p면 q인걸 직접 유도
2. Indirect proof (by contraposition)
3. Vacuous proof: p가 거짓임을 보인다 (그럼 q에 상관없이 p->q는 참)
4. Trivial proof: q가 참임을 보인다
5. Proof by contradiction: p가 참일 때, ~q가 참이라고 가정하고 생기는 모순을 보인다

p,q를 나누고, 어디가 참인지 알아보면 어떤 방법을 쓸지 보인다!

or 조건이 들어갔다면 2번을 고려해보자. 그럼 and로 정해지면서 내용이 한정된다.

 

disprove하는 방법: "counterexample"(반례)을 보인다!!