[이산수학] 한정기호(전칭한정기호, 존재한정기호), 한정기호 부정

1. Propositional function P(x) (명제함수)

p(x): 변수 x를 포함하여 진리값을 판별할 수 있는 문장이다. 

한정자인 ∀x ∃x를 이용해 명제를 생성할 수 있다.

predicate: 술어

predicate logic: 술어논리 (주어와 술어에 대해 quantifier(한정자)를 이용해 사용하는 논리)

 

2. Quantifier(한정기호)

전칭한정기호, 존재한정기호로 나뉜다.

 

universal quantifier ∀x (전칭한정기호):

"모든 x에 대해"라는 뜻이다. 

모든 universal 경우가 True여야 는 True, 하나라도 거짓이면 거짓이다.

∀xP(x) = P(x1) ∧ P(x2) ∧ ···∧ P(xn) 

 

 

existential quantifier ∃x (존재한정기호):

"어떤 x에 대해"라는 뜻이다.

하나의 universal 경우가 True라면 는 True, 모두 만족하지 않으면 거짓이다.

∃xP(x) = P(x1) ∨ P(x2) ∨ ···∨ P(xn) 

 

 

※ 한정기호는 어떤 논리연산자보다 우선순위다!

 

3. 한정기호의 부정

드모르간처럼 생각하면 편하다. ∀x와 ∃x 서로 바꾸기, 바깥에 있는 ¬기호를 집어넣기

¬∃xP(x)  ≡  ∀x ¬P(x)

¬∃xP(x)  ≡  ∀x ¬P(x)

 

multiple quantifier 부정하기:

¬(∃x∀yP(x,y))  ≡  ∀x∃yP(x,y)

다양한 변수 x, y, z, ...에 대해 한정기호가 있을 경우, 분배법칙을 사용해주면 된다.