IST/이산수학

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

ssunj 2023. 4. 18. 02:13

오늘 공부할 단원은 챕터 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"(반례)을 보인다!!