Logic(3)

Predicates : 술어

• x 는 3보다 크다
  • x : 값
  • 3보다 크다 : P = 술어
  • P(x)
• Q(x,y) = x는 y + 3과 같다.
  • Q(1,2) false ⇒ 1 ≠ 2 + 3
  • Q(3,0) true ⇒ 3 = 0 + 3
• n-place predicate
  • P(x₁, x₂, … x_n)

propositional function : 명제 함수

• 변수의 값에 의해 참과 거짓을 구변할 수 있는 문장이나 수식
  • 명제함수에 값을 지정하는 방법
    • 각 변수에 특정한 값을 부여
    • Quantifiers를 이용해 변수의 값을 제한.
      • 전체 한정자(∀, universal quantifier), 존재한정자(∃, existential quantifier)

Quantifiers

• Quantifiers : 한정자(공식을 만족하는 개인의 수를 지정하는 연산자)
  • Universal quantification : 전체 한정자
    • ∀xP(x)
    • “주어진 어떠한 ~에 대해서도”, “모든 ~에 대해서”
  • Existential quantification : 존재 한정자
    • ∃xP(x)
    • 주어진 술어를 만족시키는 객체가 논의 영역에 적어도 하나 존재함.
  • Precedence of Quantifiers : 한정자의 우선 순위
    • 모든 논리 연산자에 대해 우선 순위를 가지고 있다.
    • ∀xP(x) ∨ Q(x) ≡ (∀xP(x)) ∨ Q(x)
  • 하나의 명제 함수에 여러 한정자가 사용될 경우 해석에 주의, 서로 다른 한정자가 사용된다면 순서를 지켜야 한다.
  • 여러 한정자가 사용된 명제 한수가 부정될 경우 다양한 해석이 존재

    • ￢∀x ∃y ∀z P(x,y,z) ≡ ∃x ￢∃y ∀z P(x,y,z) ≡ ∃x ∀y ￢∀z P(x,y,z) ≡ ∃x ∀y ∃z￢ P(x,y,z)
      

Logical Equivalences Involving Quantifiers

• 한정자 관련된 논리적 동등성

statement	equivalent statement
∀x(P(x) ∧ Q(x))	(∀xP(x)) ∧ (∀xQ(x))
￢∃xP(x)	∀x￢P(x)
￢∀xP(x)	∃x￢P(x)

Nested Quantifiers

• ∀x∃y(x + y = 0)
  • 모든 x에 대하여 x + y = 0 을 만족시키는 y가 존재한다.
  • ∀xQ(x)에서 Q(x)는 ∃y(x + y = 0)
  • true
• ∃y∀x(x + y = 0)
  • 어떤 y는 모든 x에 대하여 x + y = 0를 만족시키는 y가 존재한다.
  • ∃yQ(y) 에서 Q(y)는 ∀x(x + y = 0)
  • false
• Negation nested quantifiers
  • ￢∀x∃y(xy=1) ≡ ∃x￢∃y(xy=1) ≡ ∃x∀y￢(xy=1) ≡ ∃x∀y(xy≠1)

Valid Arguments : 전제가 true 일때 결론이 반드시 true 이다.

• Argument
  • 제안 순서 (P₁, P₂, … P_n)
  • P_n 이 되기 위해서는 이전의 제안들이 모두 ∧ 되어야한다.
  • P₁ ∧ P₂ ∧ … ∧ P_n-1 ⇒ P_n

Rules of Inference : 추론의 규칙

• 기존에 검증된 true 를 가지고 새로운 사실을 밝혀내는것.

rule of inference	name
p ^ (p ⇒ q) ⇒ ∴q	Modus ponens
￢q ∧ (p ⇒ q) ⇒ ∴￢q	Modus tollens
(p ⇒ q) ∧ (q ⇒ r) ⇒ ∴p ⇒ r	Hypothetical syllogism
(p ∨ q) ∧ ￢p ⇒ ∴q	Disjunctive syllogism
p ⇒ ∴p ∨ q	Addition
p ∧ q ⇒ ∴ p	Simplification
p ∧ q ⇒ ∴p ∧ q	Conjunction
(p ∨ q) ∧ (￢p ∨ r) ⇒ ∴q ∧ r	Resolution

• 추론 판별 방법

  • p ⇒ q
    q
    ∴ p
    

    | p ⇒ q | q | ∴ p | result | |——-|—|—–|——–| | T | T | T | pass | | F | F | T | pass | | T | T | F | fail | | T | F | F | pass |

• 기존에 밝혀진 p ⇒ q, q 둘다 T 일 경우 p 도 무조건 T 가 되어야 하는데 F인 케이스이 발생함으로 유효하지 않은 추론이다.

Normal Forms

• true or false 를 가지고 얻고 싶은 모든 케이스는 and, or, not 으로 만들 수 있다.

• Disjunctive Normal Form (DNF)
  • (p ⇒ q) ∧ ￢q ≡ (￢p ∧ ￢q) ∨ (q ∧ ￢q)
  • ∧ 의 ∨ 다.
• Conjunctive Normal Form (CNF)
  • (p ⇒ q) ∧ ￢q ≡ (￢p ∨ q) ∧ ￢q

p	q	c(carry)	s
1	1	1	0
1	0	0	1
0	1	0	1
0	0	0	0

• c ≡ p ∧ q
• s ≡ p ⊕ q
  • 하지만 normal form 에서는 ⊕ 사용 불가.
    • 해결책 : ￢(p ⇒ q) ∨ ￢(q ⇒ p)
      • ￢(￢p ∨ q) ≡ p ∧ ￢q
      • ￢(￢q ∨ p) ≡ q ∧ ￢p
      • (p ∧ ￢q) ∨ (q ∧ ￢p)

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

Principal Disjunctive Normal Form

• minterm 들의 or

p	q	r	result
T	T	T	p ∧ q ∧ r
T	T	F	p ∧ q ∧ ￢r
T	F	T	p ∧ ￢q ∧ r
T	F	F	p ∧ ￢q ∧ ￢r
F	T	T	￢p ∧ q ∧ r
F	T	F	￢p ∧ q ∧ ￢r
F	F	T	￢p ∧ ￢q ∧ r
F	F	F	￢p ∧ ￢q ∧ ￢r

• minterm 의 or 연산과 똑같은 결과를 내는 다른 개념
  • ex) p ⊕ q

p	q	p ⊕ q	x	y	x ∧ y
1	1	0	0	1	0
1	0	1	1	1	1
0	1	1	1	1	1
0	0	0	1	0	0