이산수학 1.4 Predicates and Quantifiers 술어와 한정 기호(2)

chapter 1. The Foundations: Logic and Proofs

1.4 Predicates and Quantifiers

 

Quantifiers

• quantifiers(한정자): all과 some를 포함한 영어 단어의 의미를 표현하기 위해 필요하다.

      - “All men are Mortal.”

      - “Some cats do not have fur.”

• 가장 중요한 두 가지 한정자는 다음과 같다.

       - 전체 한정자(Universal Quantifier), “For all,”   symbol: ∀

       - 존재 한정자(Existential Quantifier), “There exists,”  symbol: ∃

• ∀xP(x) (☞모든 x에 대해 P(x)) 와 ∃xP(x) (☞P(x)인 x가 존재) 와 같이 사용한다.
• ∀xP(x): domain 안의 every(모든) x에 대해 P(x)가 참이다. (모두 존재해야 True)
• ∃xP(x): domain 안의 some(일부) x에 대해 P(x)가 참이다. (하나라도 존재할 시 True)
• quantifier는 이러한 표현식에서 변수 x를 bind한다.

 

Universal Quantifier

∀xP(x) is read as “For all x, P(x)” or “For every x, P(x)”

 

Examples:

1) If P(x) denotes “x > 0” and U is the integers, then ∀xP(x) is false.

2) If P(x) denotes “x > 0” and U is the positive integers, then ∀xP(x) is true.

3) If P(x) denotes “x is even” and U is the integers, then ∀xP(x) is false.

 

 

Existential Quantifier

∃xP(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).”

 

Examples:

1. If P(x) denotes “x > 0” and U is the integers, then ∃xP(x) is true. It is also true if U is the positive integers.

2. If P(x) denotes “x < 0” and U is the positive integers, then ∃xP(x) is false.

3. If P(x) denotes “x is even” and U is the integers, then ∃xP(x) is true.

 

 

Properties of Quantifiers 한정자의 특성

∃xP(x) 와 ∀xP(x) 의 진리값은 propositional function P(x)와 domain U에 따라 달라진다.

 

Examples:

1. If U is the positive integers and P(x) is the statement “x < 2”, then ∃xP(x) is true, but ∀xP(x) is false.

2. If U is the negative integers and P(x) is the statement “x < 2”, then both ∃xP(x) and ∀xP(x) are true.

3. If U consists of 3, 4, and 5, and P(x) is the statement “x > 2”, then both ∃xP(x) and ∀xP(x) are true. But if P(x) is the statement “x < 2”, then both ∃xP(x) and ∀xP(x) are false.

 

 

Precedence of Quantifiers 한정자의 우선순위

• ∀와 ∃는 모든 논리 연산자보다 우선 순위가 높다.
• 예를 들어, ∀xP(x) ∨ Q(x) 는 (∀xP(x)) ∨ Q(x) 를 의미한다.
• ∀x (P(x) ∨ Q(x))는 위의 식과 의미가 다르다.
• ∀xP(x) ∨ Q(x) 와 ∀x (P(x) ∨ Q(x)) 구분하기

 

Translating from English to Logic

Example 1:

다음 문장을 술어 논리로 번역하라: “Every student in this class has taken a course in Java.”

 

Solution:

가장 먼저 domain U를 정한다.

   Solution 1: If U is all students in this class, define a propositional function J(x) denoting “x has taken a course in Java” and translate as ∀xJ(x).

  ▷ 만약 U가 이 반에 있는 모든 학생이라면, 명제함수 J(x)를 "x는 자바 수업을 들었다"로 정하고 이를 ∀xJ(x)로 번역할 수 있다. 

  Solution 2: But if U is all people, also define a propositional  function S(x) denoting “x is a student in this class” and translate as ∀x (S(x)→ J(x)).

  ▷ 만약 U가 이 모든 사람이라면, 명제함수 S(x)를 "x는 이 반에 있는 학생이다"로 정하고(추가적인 정의) 이를 ∀x (S(x)→ J(x))로 번역할 수 있다.

  ▷∀x (S(x)→ J(x)): 모든 사람들 x에 대해, 만약 x가 이 반에 있는 학생이라면 x는 자바수업을 들었다.

 

* ∀x (S(x) ∧ J(x)) is not correct. What does it mean?

원문: 이 반에 있는 모든 학생은 자바 수업을 들었다. 

∀x (S(x) ∧ J(x)): x는 이 반에 있는 학생이면서 자바 수업을 들은 모든 사람. 반에 있는 학생 중 자바 수업을 안 들은 학생이 있을 수 있으므로 원문과 동치가 아니다. 

 

 

Example 2:

다음 문장을 술어 논리로 번역하라: “Some student in this class has taken a course in Java.”

 

Solution:

가장 먼저 domain U를 정한다.

   Solution 1: If U is all students in this class, translate as ∃xJ(x)

  ▷ 만약 U가 이 반에 있는 모든 학생이라면, ∃xJ(x)로 번역할 수 있다. 

  Solution 2: But if U is all people, then translate as ∃x (S(x) ∧ J(x))

  ▷ 만약 U가 모든 사람이라면, ∃x (S(x) ∧ J(x))로 번역 가능하다. 즉, "이 반에 있는 학생"이고 "자바 수업을 들은" 학생이 존재한다.

 

* ∃x(S(x)→ J(x)) is not correct. What does it mean?

원문: 이 반에 있는 몇몇 학생은 자바 수업을 들었다. 

∃x(S(x)→ J(x)): 몇몇 사람들 x에 대해, 만약 x가 이 반에 있는 학생이라면 x는 자바수업을 들었다.

▷ 반에 있는 학생들 중 자바 수업을 안 들은 학생이 있을 수 있으므로, x가 이 반에 있는 학생이라고 해서 자바수업을 들었다는 보장을 할 수는 없다. 

 

 

 

---

출처: Discrete Mathematics and Its Applications (K. H. Rosen 저, McGraw Hill, 2007)