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

chapter 1. The Foundations: Logic and Proofs

1.4 Predicates and Quantifiers

 

Propositional Logic Not Enough

• "모든 사람은 죽는다."
• "소크라테스는 남자다."

☞ "소크라테스는 죽는다"

 

명제 논리(Propositional Logic)로는 이러한 추론을 나타낼 수 없다.

따라서 사물, 그 속성, 그리고 그 관계에 대해 말하는 언어가 따로 필요하다. 

 

 

Introducing Predicate Logic 술어논리 도입

술어 논리는 다음과 같은 새로운 기능을 사용한다.

• 변수(Variables): x, y, z
• 술어(Predicates): P(x), M(x)  ☞술어논리에서는 변수가 들어간 형태를 허용. 명제 논리의 논리식은 변수를 포함하지 않는다.
• 한정자(Quantifiers): 변수 x, y, z의 범위를 표현 ex. 일부 x, 모든 y...

명제 함수(Propositional functions)는 명제의 일반화이다. 

• 변수와 술어를 포함한다. ex. *P(x)
• 변수는 해당 *domain의 elements로 대체 가능하다.

*domain: 변수의 범위

*P(x): 변수 x가 고정되어 있을 시 P(x)는 하나의 명제가 되고, x가 변수일 시 P(x)는 명제함수가 됨.

  ex. P(3) = 명제

       P(x) = 명제함수

 

Propositional Functions

• 하나의 전체집합 U의 원소 x를 포함하는 명제 P(x)로서 x가 지정될 때마다 그것이 참인지 거짓인지가 판정되는 것을 집합 U에 관한 명제함수(Propositional functions)라고 한다.
• U는 domain(변수의 범위)을 의미한다. 
• P(x)는 x에 대한 명제 함수 P의 값이다.
• 예를 들어, P(x)가 "x > 0"이고 domain이 정수라고 하자. 이때,

- P(-3): 거짓

- P(0): 거짓

- P(3): 참

• 위 예시에서 U는 정수이다.

 

Examples of Propositional Functions

Let “x + y = z” be denoted by  R(x, y, z) and U (for all three variables) be the integers. Find these truth values:

   R(2,-1,5)

     Solution:  F

   R(3,4,7)

     Solution: T

   R(x, 3, z)

     Solution: Not a Proposition (명제가 아님, 변수가 들어감 → 명제함수O 명제X)

 

Now let  “x - y = z” be denoted by Q(x, y, z), with U as the integers. Find these truth values:

   Q(2,-1,3)

     Solution:  T

   Q(3,4,7)

     Solution: F

   Q(x, 3, z)

     Solution: Not a Proposition (명제가 아님, 변수가 들어감 → 명제함수O 명제X)

 

 

Compound Expressions 복합 명제

• 더 이상 간단한 명제로 분해할 수 없는 긍정형의 명제인 단순명제(primary statement또는 원자명제)가 두 개 이상 합쳐져서 만들어진 명제를 합성명제(compound statement또는 분자명제)라고 한다.
• 논리 연산 및 괄호를 포함한다.
• 예를 들어 “조지 워싱턴은 미국인이고 베를린은 독일의 수도이다.” 등이 합성명제가 된다. 
• 복합명제, 겹명제라고도 한다.
• P(x)가 "x > 0"을 나타내면, 진리값은

      P(3) ∨ P(-1)      Solution: T

      P(3) ∧ P(-1)      Solution: F

      P(3) → P(-1)     Solution: F

• 변수가 있는 식은 명제가 아니므로 진리값이 존재하지 않는다. 예를 들어,

      P(3) ∧ P(y)     

      P(x) → P(y)    

*명제 함수 형태 → T/F 판단 불가

• quantifiers(한정자)와 함께 사용될 때, 이러한 표현(propositional functions)은 명제가 된다.

 

 

 

---

출처:

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

위키백과 <명제>