[예습] Propositional Logic

Logic (Logic System)

• Syntax(구조): symbolic structure of the statements
• Semantics(의미): a mapping from symbolic structures to things that the logic system concerns

---

Propositional Logic

Proposition(명제): declarative sentence (Only True or False)

• 1+1=2 (T)
• Toronto is the capital of Canada (F)
• 1 + 2 + 3
• x + 1 = 2

Positional Variable: a symbol that represents a propositional statement

• p, q, r, s⋅⋅⋅

Atomic Proposition: one that cannot be expressed in term of simpler terms

• T: True
• F: False

Compound Proposition: one or more propositions + logical operators

• Logical Operator
  • Negation(NOT)
    • ¬p

    • p	¬p
      T	F
      F	T

  • Conjunction(AND)
    • p ∧ q

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

  • Disjunction(OR)
    • p ∨ q

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

  • Exclusive-Or(XOR)
    • p ⊕ q

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

    • T가 하나만
  • Implication(IMPLIES)
    • (Conditional Statement)
    • p → q

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

    • p(약속, hypothesis), q(약속을 지키는 거, conclusion)
    • “if p, then q”, “p implies q”, “p only if q” “q when p”, “q if p”
    • q는 p의 필요조건
    • p는 q의 충분조건
    • Converse(역): q → p
    • Inverse(이): ¬p → ¬q
    • Contrapositive(대우): ¬q → ¬p
  • Biconditional(IFF)
    • p ↔ q

    • p	q	p ↔ q
      T	T	T
      T	F	F
      F	T	F
      F	F	T

    • 필요 충분 조건

---

Equivalent Propositions

• If two propositions always the same truth value -> Equivalent
• ≡
• p → q ≡ ¬q → ¬p(contrapositive)
• p → q ≡ ¬p ∨ q (truth table)

---

Precedence of Logical Operators

1. ¬ (Negation)
2. ∧ (Conjunction)
3. ∨ (Disjunction)
4. → (Implication)
5. ↔ (Biconditional)

---

Propositional Equivalences

• Tautology(동어반복)
  • always True
  • Ex) p ∨ ¬p
• Contradiction(모순)
  • always False
  • Ex) p ∧ ¬p
• Contingency(우연)
  • not tautology ∧ not contradiction
• 
  
• De Morgan’s law: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Negation Laws: p ∨ ¬q ≡ T, p ∧ ¬p ≡ F
• Absorption Laws: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p

---

Propositional Satisfiability

• Satisfiable Proposition: 적어도 하나의 case가 True
• Unsatisfiable Proposition: All case is False -> Contradiction(모순)
• Valid Proposition: 모든 결과가 True -> Tautology

---

Notation

p1 ∨ p2 ∨ … pn

p1 ∧ p2 ∧ … pn

---

N-Queen Problem

• Place N Queens on a NxN grid
• Don’t place two Queens on the same vertical, horizontal or diagonal line
• Proposition p𝑖,𝑗: i행, j열에 있는 퀸
  • Queen이 있으면 True, 없으면 False
• Algorithm
  𝑄 = 𝑄1 ∧ 𝑄2 ∧ 𝑄3 ∧ 𝑄4 ∧ 𝑄5
  1. 모든 행은 최소 한개의 퀸을 포함
     
     • OR operator: 한 row에 어디든 하나만 존재(위치 상관x)
       나머지 퀸이 없어도(F) 퀸이 하나라도 있으면(T) = True
     • AND operator: 모든 row에 한개씩 존재
       한줄이라도 퀸이 없다면(F) 모든 줄에 퀸이 있다면(T)
  2. 각 행에 최대 한개의 퀸만 존재
     
     • pi1 ∧ pi2 = F
       T F = F
       F T = F
       F F = F
       T T (X) 한줄에 최대 퀸 한개
     • Why negation?
  3. 각 열에 최대 하나의 퀸만 존재
     
  4. top-right 방향 대각선에 2개 이상의 퀸이 존재X
     
  5. bottom- right 방향 대각선에 2개 이상의 퀸이 존재X