Chapter 1.4 중첩된 한정기호

소개

---

• Chapter 1.3에서는 $∀x∃y(x + y = 0)$와 같은 하나의 한정기호 범위안에 다른 한정기호가 나타나는 중첩된 한정기호는 피했었다.
• But 이번 Chapter 1.4에서는 위와 같은 것을 알아볼 것이다.
  • 어떤 한정기호 범위 안의 모든 것은 명제함수로 볼 수 있음
  • ex) $∀x∃y(x + y = 0)$
    • 위의 표현은 $Q(x)$ is $∃yP(x, y)$이고 $P(x, y)$ is $x + y = 0$ 인 $∀xQ(x)$와 같은 표현이다.

쫄지말자. 그냥 하나하나 대입한거다.

중첩된 한정기호 → 선언문

---

• 예제 1) 변수(variable) $x,y$의 정의역(domain)이 모든 실수(all real numbers)라고 하면,

  • $∀x∀y(x + y = y + x)$
    • "모든 실수 $x$와 $y$에 대하여, $x + y = y + x$"라는 표현이고, 실수의 덧셈에 대한 교환법칙을 의미한다.
  • $∀x∃y(x + y = 0)$
    • "모든 실수 $x$에 대하여, $x + y = 0$을 만족하는 실수 y가 존재한다."라는 표현이고, 역원(additive inverse)이 있음을 나타낸다.
  • $∀x∀y∀z(x+(y+z) = (x+y)+z)$
    • "모든 실수 $x$, $y$, $z$에 대하여, $x + (y + z) = (x + y) + z$"라는 표현이고, 이는 실수의 덧셈에 대한 결합법칙을 나타낸다.

• 예제 2) 다음 중첩된 한정기호를 선언문으로 번역하시오:

  • $x,y$의 정의역이 모든 실수인
    $∀x∀y((x > 0) ∧ (y < 0) → (xy < 0))$

    • sol) "모든 실수 $x$와 $y$에 대하여, if $x > 0$ and $y < 0$,
      then $xy < 0$ 이다."

• 예제 3) 다음 중첩된 한정기호를 선언문으로 번역하시오:

  • 단, 술어 $S(x, y)$: "$x$는 $y$에서 쇼핑한다."를 사용해라. (변수 $x$는 사람들, 변수 $y$는 가게)

    • $∀yS(Margaret, y)$

  • 술어는 "If $y$가 하나의 가게라면, then $Margaret$은 거기서 쇼핑한다"를 의미하므로,
    답은 : "$Margaret$은 모든 가게에서 쇼핑한다."

선언문 → 중첩된 한정기호

---

• 예제 1)

  • "만약 한명의 사람이 여성이고 한명의 부모라면, 이 사람은 누군가의 어머니이다. "를 술어(predicate), 정의역(domain)="모든 사람들"에 대해 한정사, 논리연산자로 표현하라.

  • The answer) 다음과 같이 표현 가능:

  • "모든 사람 $x$에 대하여, If 사람 $x$가 여성이고 사람 $x$가 한명의 부모라면, then 사람 $x$가 사람 $y$의 어머니임을 만족하는 한명의 사람 $y$가 존재한다."

    • 명제 함수:
      • $F(x)$ = "$x$는 여성이다"
      • $P(x)$ = "$x$는 한명의 부모이다"
      • $M(x, y)$ = "$x$는 $y$의 어머니이다."
    • 명제 함수 With 한정사, 논리연산자:
      • $∀x( (F(x) ∧ P(x)) → ∃yM(x, y) )$

• 예제 2)

  • "모든사람은 반드시 한명의 베프만을 가진다. "를 술어(predicate), 정의역(domain)="모든 사람들"에 대해 한정사, 논리연산자로 표현하라.

  • The answer) 다음과 같이 표현 가능:

  • "모든 사람 $x$에 대하여, 사람 $x$는 반드시 한명의 베프만을 가진다."

    • "$∀x$(사람 $x$는 반드시 한명의 베프만을 가진다)"
    • 명제 함수:
      • $B(x, y) = "y는$ $x의 베프이다."$
    • 명제 함수 With 한정사, 논리연산자:
      • $∀x∃y( (B(x, y) ∧ ∀z((z≠y)→¬B(x, z)) )$

한정사의 순서

• 예제 1) 술어 $P(x, y) = "x+y = y+x"$이고 $x$와 $y$의 정의역이 실수일 때, $∀x∀yP(x, y)$의 진리 값은? 그리고, $∀y∀xP(x, y)$의 진리 값은?

  • Sol)

    • 모든 실수에 대하여 덧셈의 교환법칙이 성립하므로,

      $∀x∀yP(x, y)$의 진리 값은 True

      $∀y∀xP(x, y)$의 진리 값 역시 True

$∀x∀y$와 $∀y∀x$에 있어서, $∀x$와 $∀y$의 순서는 진리 값에 영향을 주지 않음

• 예제 2) 술어 $Q(x, y) = "x+y =0"$이고 $x$와 $y$의 정의역이 실수일 때,
  $∃y∀xQ(x, y)$와 $∀x∃yQ(x, y)$의 진리 값은?

  • Sol)

    • $∃y∀xQ(x, y)$ : 어떤 $y$에 대해 모든 $x$가 "$x + y = 0$"을 만족하는 $y$가 존재함

      → false

    • $∀x∃yQ(x, y)$ : 모든 $x$에 대해 "$x + y = 0$"을 만족하는 $y$가 존재함

      → true

아래의 것은 왜 true인가?? 모든 $x$를 나열했을 때 ${x_1,x_2,⋯,x_∞}$라면 그러한 $x$에 대해서 $x+y=0$을 만족하는 $y$값을 하나라도 찾는다면 참이 된다. 하지만, $∃y∀x$의 경우 어떠한 $y$의 값이 고정되어 있고 그러한 $y$에 대해 모든 $x$가 $x+y=0$을 만족한다는 표현이므로 false가 된다.

즉, ∃y∀x와 ∀x∃y에 있어서, ∀x와 ∃y의 순서는 진리 값에 영향을 줌

• 변수가 두 개인 경우의 한정사 순서의 영향
  

유용한 동치법칙

• $∀xP(x) ⇔ ¬∃x¬P(x)$
• $∃xP(x) ⇔ ¬∀x¬P(x)$
  • 위의 두 표현 식은 앞서 소개한 한정사 정의를 이용하면 증명이 가능 (try it !)
  • 한정사의 정의:
    • $∀xP(x) ⇔ P(x_1)∧P(x_2)∧⋯∧P(x_n)$
    • $∃xP(x) ⇔ P(x_1)∨P(x_2)∨⋯∨P(x_n)$
• $∀x( P(x)∧Q(x) ) ⇔ (∀xP(x))∧(∀xQ(x))$
• $∃x( P(x)∨Q(x) ) ⇔ (∃xP(x))∨(∃xQ(x))$
  • 위의 표현 식 역시 한정사 정의를 이용해 증명이 가능 (try it !)