predicate logic
서술논리
quantification
정량화
quantifiers
양화사
universal quantifier
전칭양화사(for all)
for all every object x
for all x
∀x
∀x Home(x)
뭐든지 집에 있다.
∀x (P(x)→Q(x))
모든 x에 대해 P이면 Q이다.
existential quantifier
존재양화사(at least one)
for some object x
for some x
∃x
∃x Home(x)
뭔가 집에 있다.
∃x (Professor(x)∧Smart(x))
교수이면서 똑똑한 사람이 있다.
atomic well-formed formulas(atomic wffs)
문법규칙에 맞는 핵논리식
핵문장 + 변수
ex)Home(x), Taller(suni, y)
well-fromed formulas(wffs)
문법규칙에 맞는 논리식
핵논리식들
ex)∀x ((Cube(x)∧Small(x)) → ∃y LeftOf(x,y))
sentence
풀려있는 변수가 없고 변수가 묶여있는 wff를 문장(sentence)라고 한다.
이때 변수는 bound(묶여있다)여야 한다.
satisfaction
quantified sentence의 true/false는 satisfaction(만족성)을 이용하여 정의하여야 한다. S(x)의 의미만으로는 true/false를 알수 없다.
∀x S(x)
모든 물건이 S(x)를 만족한다.
∃x S(x)
S(x)를 만족하는 물건이 최소한 하나 존재한다.
domain of discourse
논의 영역
논의 대상 영역이 있다고 가정한다.
명확한 경우는 명시하지 않음
aristotle's logic
All P's are Q's P인것은 모두 Q이다.
∀x (P(x) → Q(x))
Some P's are Q's P이고 Q인것이 있다.
∃x (P(x) ∧ Q(x))
No P's are Q's P인것은 절대로 Q가 아니다.
∀x (P(x) → Q(x))
￢∃x (P(x)∧Q(x))
Some P's are not Q's P지만 Q가 아닌것이 있다.
∃x (P(x) → ￢Q(x))
noun phases
명사구 - 영어로 표현되는 명사구(꾸밈)은 ∧(and)로 연결한다.
작고행복한 강아지가 집에 있다.
∃x [(Small(x)∧Happy(x)∧Dog(x))∧Home(x)]
집에 있는 작은 강아지는 모두 행복하다.
∀x [(Small(x)∧Home(x)∧Dog(x))→Happy(x)]
conversational implicature
대화의 함의
"P는 모두 Q이다." 라고 해서 P가 존재한다는 보장을 하는건 아니다.
"어떤 P는 Q이다"P가 모두 Q가 되지 말라는건 아니다.
vacuously true generalization
따져볼것없이 참이 되는 일반화
∀x (P(x) → Q(x))
에서 P(x)를 만족하는 x가 존재하지 않을경우에 따져볼것없이 참이 된다.
inherently vacusous generalization
선천적으로 따져볼 필요 없는 일반화
∀x ￢P(x) 인 세상에서만 ∀x (P(x) → Q(x))가 참이 되면 이 문장은 선천적으로 따져볼 필요없다.
truth-funtonal form
진리함수형
양화사 기호와 핵문장을 A,B등의 단순한진리함수로 바꾼것
replacement method
양화사가 포함된 문장이 FO타당한지 알기 위해서 술어를 모두 의미없는 단어로 바꾼다.
이렇게 해서 반례를 찾아서 반례를 못찾으면 FO타당.
mixed sentence
전칭,존재기호가 섞여있는 경우
양화사 위치에 따른 의미변화
∀x ∃y Likes(x,y) 모두는 좋아하는 것이 있다.
∀x ∃y Likes(y,x) 모두를 좋아하는 것이 있다.
∃y ∀x Likes(x,y) 모두가 좋아하는 무언가가 있다.
∃y ∀x Likes(y,x) 모두를 좋아하는 무언가가 있다.
context sensitivity
문맥민감성
만약 "뉴욕시에서는 매분마다 한 사람이 강도에게 습격당합니다"
라는 문장이 있다면 이는 때에 따라 2가지 의미로 해석될수 있다.
1.뉴욕에서는 각각 다른 한사람이 매분마다 습격을 당한다.
2.뉴욕에서는 매분마다 강도에게 습격당하는 어떤 사람이 있다.
글로는 2가지의미가 해석가능하지만 양화사로 만든 논리문장에서의 의미는 단 하나만 가능하다.
prenex form
문장의 가장앞쪽에 모든 양화사기호가 모여있는 문장
universal instantiation = universal elimination
전칭 사례화
전칭기호 없애기(전칭일반화)
∀x S(x)
라면 S(c)이다.
existential generalization = existential introduction
존재일반화,
존재기호(만들기)
S(c)라면 ∃x S(x)이다.
existential instantiation
존재사례화
존재기호 없애기
∃x S(x)인데 임의의 c에 대해 S(c)를가정하고 Q(d)라는 결론을 낸다면 존재사례화에 의해서 Q(d)도 참이다.
general conditional proof
일반화 조건 증명
∀x (P(x)→Q(x))
를 증명하는 것으로 임의의 이름 c를 하나 선택한후 P(c)를 가정하고 Q(c)를 증명한다.
!!이때 P(c)를 가정하후 새로 생긴 이름이 Q에 포함되어 있지 않아야 한다.
universal generalization
전칭일반화
임의의 하나 c를 뽑아 S(c)임을 증명하면 ∀x S(x)라고 결론낼수 잇다.
수학적귀납법
mathematical induction
inductive definition
귀납적 정의
무한대의 집합을 간결하게 정리할수 있다.
1. 토대(basis) 기본베이스
2. 귀납(induction) 복잡한 요소를 정의하는 방법
3. '그게 전부'라는 범위의 지정(불순물제거)
ex)0은 자연수이다.
n이 자연수이면,n+1도 자연수이다.
그외의 방법으로 자연수를 만들수 없다.
induction
귀납법
x가 귀납적으로 정의되는 경우 P(x)는 귀납적으로 증명이 가능하다.
대상이 되는 사례가 무한이 많다 하더라도 유한한 증명단계를 통해 일반적인 결론을 내릴수 있다.
ex)1~n개까지의 자연수의 합,
inductive definition in set theory
집합론으로 귀납정의하기
ex)집합론으로 자연수를 정의하기.
자연수의 집합N은 다음을 만족하는 '최소' 집합이다.
1)0 ∈ N
2)n ∈ N이면 n+1 ∈ N이다.
서술논리
quantification
정량화
quantifiers
양화사
universal quantifier
전칭양화사(for all)
for all every object x
for all x
∀x
∀x Home(x)
뭐든지 집에 있다.
∀x (P(x)→Q(x))
모든 x에 대해 P이면 Q이다.
existential quantifier
존재양화사(at least one)
for some object x
for some x
∃x
∃x Home(x)
뭔가 집에 있다.
∃x (Professor(x)∧Smart(x))
교수이면서 똑똑한 사람이 있다.
atomic well-formed formulas(atomic wffs)
문법규칙에 맞는 핵논리식
핵문장 + 변수
ex)Home(x), Taller(suni, y)
well-fromed formulas(wffs)
문법규칙에 맞는 논리식
핵논리식들
ex)∀x ((Cube(x)∧Small(x)) → ∃y LeftOf(x,y))
sentence
풀려있는 변수가 없고 변수가 묶여있는 wff를 문장(sentence)라고 한다.
이때 변수는 bound(묶여있다)여야 한다.
satisfaction
quantified sentence의 true/false는 satisfaction(만족성)을 이용하여 정의하여야 한다. S(x)의 의미만으로는 true/false를 알수 없다.
∀x S(x)
모든 물건이 S(x)를 만족한다.
∃x S(x)
S(x)를 만족하는 물건이 최소한 하나 존재한다.
domain of discourse
논의 영역
논의 대상 영역이 있다고 가정한다.
명확한 경우는 명시하지 않음
aristotle's logic
All P's are Q's P인것은 모두 Q이다.
∀x (P(x) → Q(x))
Some P's are Q's P이고 Q인것이 있다.
∃x (P(x) ∧ Q(x))
No P's are Q's P인것은 절대로 Q가 아니다.
∀x (P(x) → Q(x))
￢∃x (P(x)∧Q(x))
Some P's are not Q's P지만 Q가 아닌것이 있다.
∃x (P(x) → ￢Q(x))
noun phases
명사구 - 영어로 표현되는 명사구(꾸밈)은 ∧(and)로 연결한다.
작고행복한 강아지가 집에 있다.
∃x [(Small(x)∧Happy(x)∧Dog(x))∧Home(x)]
집에 있는 작은 강아지는 모두 행복하다.
∀x [(Small(x)∧Home(x)∧Dog(x))→Happy(x)]
conversational implicature
대화의 함의
"P는 모두 Q이다." 라고 해서 P가 존재한다는 보장을 하는건 아니다.
"어떤 P는 Q이다"P가 모두 Q가 되지 말라는건 아니다.
vacuously true generalization
따져볼것없이 참이 되는 일반화
∀x (P(x) → Q(x))
에서 P(x)를 만족하는 x가 존재하지 않을경우에 따져볼것없이 참이 된다.
inherently vacusous generalization
선천적으로 따져볼 필요 없는 일반화
∀x ￢P(x) 인 세상에서만 ∀x (P(x) → Q(x))가 참이 되면 이 문장은 선천적으로 따져볼 필요없다.
truth-funtonal form
진리함수형
양화사 기호와 핵문장을 A,B등의 단순한진리함수로 바꾼것
replacement method
양화사가 포함된 문장이 FO타당한지 알기 위해서 술어를 모두 의미없는 단어로 바꾼다.
이렇게 해서 반례를 찾아서 반례를 못찾으면 FO타당.
mixed sentence
전칭,존재기호가 섞여있는 경우
양화사 위치에 따른 의미변화
∀x ∃y Likes(x,y) 모두는 좋아하는 것이 있다.
∀x ∃y Likes(y,x) 모두를 좋아하는 것이 있다.
∃y ∀x Likes(x,y) 모두가 좋아하는 무언가가 있다.
∃y ∀x Likes(y,x) 모두를 좋아하는 무언가가 있다.
context sensitivity
문맥민감성
만약 "뉴욕시에서는 매분마다 한 사람이 강도에게 습격당합니다"
라는 문장이 있다면 이는 때에 따라 2가지 의미로 해석될수 있다.
1.뉴욕에서는 각각 다른 한사람이 매분마다 습격을 당한다.
2.뉴욕에서는 매분마다 강도에게 습격당하는 어떤 사람이 있다.
글로는 2가지의미가 해석가능하지만 양화사로 만든 논리문장에서의 의미는 단 하나만 가능하다.
prenex form
문장의 가장앞쪽에 모든 양화사기호가 모여있는 문장
universal instantiation = universal elimination
전칭 사례화
전칭기호 없애기(전칭일반화)
∀x S(x)
라면 S(c)이다.
existential generalization = existential introduction
존재일반화,
존재기호(만들기)
S(c)라면 ∃x S(x)이다.
existential instantiation
존재사례화
존재기호 없애기
∃x S(x)인데 임의의 c에 대해 S(c)를가정하고 Q(d)라는 결론을 낸다면 존재사례화에 의해서 Q(d)도 참이다.
general conditional proof
일반화 조건 증명
∀x (P(x)→Q(x))
를 증명하는 것으로 임의의 이름 c를 하나 선택한후 P(c)를 가정하고 Q(c)를 증명한다.
!!이때 P(c)를 가정하후 새로 생긴 이름이 Q에 포함되어 있지 않아야 한다.
universal generalization
전칭일반화
임의의 하나 c를 뽑아 S(c)임을 증명하면 ∀x S(x)라고 결론낼수 잇다.
수학적귀납법
mathematical induction
inductive definition
귀납적 정의
무한대의 집합을 간결하게 정리할수 있다.
1. 토대(basis) 기본베이스
2. 귀납(induction) 복잡한 요소를 정의하는 방법
3. '그게 전부'라는 범위의 지정(불순물제거)
ex)0은 자연수이다.
n이 자연수이면,n+1도 자연수이다.
그외의 방법으로 자연수를 만들수 없다.
induction
귀납법
x가 귀납적으로 정의되는 경우 P(x)는 귀납적으로 증명이 가능하다.
대상이 되는 사례가 무한이 많다 하더라도 유한한 증명단계를 통해 일반적인 결론을 내릴수 있다.
ex)1~n개까지의 자연수의 합,
inductive definition in set theory
집합론으로 귀납정의하기
ex)집합론으로 자연수를 정의하기.
자연수의 집합N은 다음을 만족하는 '최소' 집합이다.
1)0 ∈ N
2)n ∈ N이면 n+1 ∈ N이다.
