학교 공부/인공지능
인공지능 chpater_03~04
wqdsdsf
2024. 10. 8. 23:04
*명제 논리 (Propositional Calculus)
명제 논리의 의미론 정의
명제 집합의 해석은 각 명제 기호에 대해 참(T) 또는 거짓(F)의 진리값을 할당하는 것입니다.
기호 "true"는 항상 T로 할당되고, "false"는 F로 할당됩니다.
Satisfy (만족):
표현 S가 해석 I와 특정 변수 할당 하에서 참(T)의 값을 가지면, S는 만족된다고 합니다.
Model (모델):
해석 I가 모든 변수 할당에 대해 S를 만족시키면, I는 S의 모델이라고 합니다.
문장의 해석 또는 진리값 결정
부정 (Negation): ¬P는 P가 참이면 거짓이고, P가 거짓이면 참입니다.
합집합 (Conjunction): ∧는 두 항이 모두 참일 때만 참입니다.
교집합 (Disjunction): ∨는 두 항이 모두 거짓일 때만 거짓입니다.
함축 (Implication): →는 전제가 참이고 결론이 거짓일 때만 거짓입니다.
동치 (Equivalence): ≡는 두 표현이 모든 해석에서 동일할 때만 참입니다.
명제 논리 기호
명제 기호: P, Q, R 등
진리 기호: true, false
연결자: ∧ (그리고), ∨ (또는), ¬ (부정), → (함축), ≡ (동치)
명제 논리 문장
모든 명제 기호와 진리 기호는 문장입니다.
문장의 부정(¬)도 문장입니다.
두 문장의 합집합(∧) 또는 교집합(∨)도 문장입니다.
한 문장이 다른 문장을 함축(→)하는 것도 문장입니다.
두 문장이 동치(≡)인 것도 문장입니다.
명제 논리 문장의 정의
모든 명제 기호와 진리 기호는 문장입니다.
예: true, P, Q, R은 문장입니다.
부정 예: ¬P와 ¬false는 문장입니다.
합집합 예: P ∧ ¬P는 문장입니다.
교집합 예: P ∨ ¬P는 문장입니다.
함축 예: P → Q는 문장입니다.
동치 예: P ∨ Q ≡ R은 문장입니다.
WFFs (Well-Formed Formulas)
합법적인 문장
예시: ((P ∧ Q) → R) ≡ ¬P ∨ ¬Q ∨ R
이유: P, Q, R은 명제이고 각각 문장으로 인정됩니다. 결합, 부정, 함축, 동치 등의 연산을 통해 복잡한 문장을 형성합니다.
명제 문장의 의미 (Semantics)
정확한 의미 처리가 논리적 오류를 피하는 데 필수적입니다.
명제 기호는 세계에 대한 진술을 나타냅니다.
예시: P는 "비가 온다"를 나타낼 수 있습니다.
명제는 세계의 상태에 따라 참 또는 거짓일 수 있습니다.
진리값 할당은 "해석"이라고 불립니다.
중요한 명제 관계
이중 부정 법칙: ¬(¬P) ≡ P
드 모르간의 법칙: ¬(P ∨ Q) ≡ (¬P ∧ ¬Q) 및 ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
교환 법칙: (P ∧ Q) ≡ (Q ∧ P) 및 (P ∨ Q) ≡ (Q ∨ P)
연관 법칙: ((P ∧ Q) ∧ R) ≡ (P ∧ (Q ∧ R)) 및 ((P ∨ Q) ∨ R) ≡ (P ∨ (Q ∨ R))
분배 법칙: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
연산자 ∧의 진리표
P와 Q가 모두 참일 때만 P ∧ Q가 참입니다.
그 외의 경우에는 거짓입니다.
*명제 논리의 한계
개별 명제의 구성 요소에 접근할 방법이 없습니다.
각 원자 기호(P, Q 등)는 어느 정도 복잡성을 지닌 명제를 나타냅니다.
예: "화요일에 비가 왔다"는 명제
변수를 허용하지 않습니다.
*술어 논리 (Predicate Calculus)(명제 논리 + 술어 + 양화 + 추론 규칙)
구성 요소에 접근할 수 있는 방법을 제공합니다.
예: weather(tuesday, rain)
추론 규칙을 통해 술어 논리 표현을 조작하고 새로운 문장을 유도할 수 있습니다.
표현식에 변수를 포함할 수 있습니다.
예: weather(X, rain)
술어 논리 기호 (Predicate Calculus Symbols)
알파벳 구성: 대문자와 소문자, 숫자(0-9), 밑줄("_")
기호는 문자로 시작하고 합법적인 문자로 이어집니다.
예시: a, R, 6, 9, p, _, z
불법 문자: #, %, @, /, &, " "
합법적인 술어 논리 기호 예시: George, fire3, tom_and_jerry, bill, XXXX
불법 문자열 예시: 3jack, "no blanks allowed", ab%ocd
기호와 용어 (Symbols and Terms)
진리 기호 (Truth Symbols): true와 false (예약된 기호)
상수 기호 (Constant Symbols): 첫 글자가 소문자인 기호 표현 (예: george, tree)
변수 기호 (Variable Symbols): 대문자로 시작하는 기호 표현 (예: George, BILL)
함수 기호 (Function Symbols): 첫 글자가 소문자인 기호 표현
양화사 (Quantifiers)
변수와 문장이 뒤따릅니다.
전칭 양화사 (Universal Quantifier): 변수의 모든 값에 대해 문장이 참임을 나타냅니다.
예: ∀X likes(X, ice_cream)
존재 양화사 (Existential Quantifier): 도메인 내 일부 값에 대해 문장이 참임을 나타냅니다.
예: ∃Y friends(Y, peter)
Predicate Calculus Sentences
모든 원자 문장은 문장입니다.
그림 1-1
Well-formed Predicate Calculus Sentences
함수 기호: times와 plus는 아리티 2의 함수 기호입니다.
술어 기호: equal은 아리티 2, foo는 아리티 3의 술어 기호입니다.
예시:
plus(two, three)는 함수이며 원자 문장이 아닙니다.
equal(plus(two, three), five)는 원자 문장입니다.
∃X foo(X, two, plus(two, three)) ∧ equal(plus(two, three), five)는 두 결합이 모두 문장이므로 전체가 문장입니다.
(foo(two, two, plus(two, three)) → (equal(plus(three, two), five) ≡ true))는 모든 구성 요소가 논리 연산자로 적절히 연결되어 있어 전체가 문장입니다.
* Predicate Calculus의 의미론
WFF의 의미: 담론 영역의 어떤 주장
영역 (Domain): 비어 있지 않은 집합 (무한일 수 있음)
예: 정수의 집합, 가능한 8-퀸 문제의 모든 구성 집합
함수: 영역 간의 매핑
*일차 술어 논리
특징:
양화된 변수는 담론의 객체를 참조할 수 있으며, 술어나 함수는 참조할 수 없습니다.
술어는 술어로만 나타날 수 있으며, 그 자체에 대해 아무것도 주장할 수 없습니다.
예시로 제시된 표현은 일차 술어 논리에서 잘못된 형식입니다:
∀(likes)likes(george,kate).
해결 방법:
해결은 일차 논리에서만 정의됩니다.
*predicate Calculus 사용 예제
성경의 가계도를 통해 가족 관계를 설명
mother(eve, abel), mother(eve, cain)
father(adam, abel), father(adam, cain)
모든 X, Y에 대해 father(X, Y) ∨ mother(X, Y) → parent(X, Y)
모든 X, Y, Z에 대해 parent(X, Y) ∧ parent(X, Z) → sibling(Y, Z)
sibling(cain, abel)을 확인하는 예제
파일 이름: "family1.pl"
가족 관계를 정의하는 Prolog 코드
부모 관계 정의: parent(X, Y) :- father(X, Y); mother(X, Y).
다름을 확인하는 규칙: different(X, Y) :- X = Y, !, fail ; true.
형제 관계 정의: sibling(Y, Z) :- parent(X, Y), parent(X, Z), different(Y,Z).
If it doesn’t rain tomorrow, Tom will go to the mountain.
논리식: ¬weather(rain, tomorrow) → go(tom, mountain)
해석: 내일 비가 오지 않으면, 톰은 산에 갈 것이다.
Emma is a Doberman and a good dog.
논리식: gooddog(emma) ∧ isa(emma, doberman)
해석: 엠마는 도베르만이며 좋은 개이다.
All basketball players are tall.
논리식: ∀X (basketball_player(X) → tall(X))
해석: 모든 농구 선수는 키가 크다.
Some people like anchovies.
논리식: ∃X (person(X) ∧ likes(X, anchovies))
해석: 어떤 사람들은 멸치를 좋아한다.
Nobody likes taxes.
논리식: ¬∃X likes(X, taxes)
해석: 아무도 세금을 좋아하지 않는다.*Logical Inference
표기법 "X F S": X가 S로부터 논리적으로 따라온다는 의미
X는 S를 만족하는 모든 해석에 대해 참이다.
이는 X가 S로부터 유도되거나, S로부터 유도 가능하다는 것을 의미하지 않는다.
모든 해석을 시도하는 것은 비실용적:
Inference rules는 한 표현이 다른 표현으로부터 논리적으로 따라오는지를 결정하는 계산적으로 실용적인 방법을 제공한다.
"논리적으로 따른다"는 개념:
추론 규칙의 타당성과 정확성을 증명하기 위한 형식적 기초를 제공한다.
새로운 올바른 표현을 추론: 명제나 공리 집합에서 새로운 올바른 표현을 도출하는 과정
추론 규칙: 주어진 문장에서 새로운 술어 논리 문장을 기계적으로 생성하는 방법
구문적 주장에 기반
추론 규칙의 예시:
Modus Ponens (긍정 논법): "P → Q"와 "P"가 주어졌을 때 "Q"를 얻음
Resolution
Modus Tollens (부정 논법): "P → Q"와 "¬Q"가 주어졌을 때 "¬P"를 얻음
*Inference Rule(추론 규칙): Sound, Complete
술어 논리의 의미론:
논리적 추론의 형식 이론을 위한 기초를 제공합니다.
참된 명제 집합으로부터 새로운 올바른 명제를 추론하는 능력을 강조합니다.
올바른 명제는 원래 표현 집합의 모든 이전 해석과 일치해야 합니다.
비공식 정의:
문장을 참으로 만드는 해석은 그 문장을 만족한다고 합니다.
표현 X가 술어 논리 표현 집합 S로부터 논리적으로 따라온다고 할 때, S를 만족하는 모든 해석이 X도 만족해야 합니다.
Sound (타당성):
어떤 추론 규칙이 논리 표현의 집합 S에서 작동하여 생성된 모든 문장 X가 S로부터 논리적으로 따라올 때, 그 추론 규칙은 타당하다고 합니다.
타당한 추론 규칙의 예시로 Modus Ponens와 Resolution이 있습니다.
예시로 "토끼는 눈이 좋다, 토끼는 당근을 먹는다"에서 "당근을 먹으면 눈이 좋아진다"는 귀납적 추론으로, 타당하지 않을 수 있습니다.
Complete (완전성):
추론 규칙이 S로부터 논리적으로 따라오는 모든 표현을 생성할 수 있다면, 그것은 완전하다고 합니다.
완전성은 덜 중요하지만 종종 바람직한 특성입니다.
*Useful Inference Rules(그림)
*Modus Ponens("P"와 "P→Q"가 주어졌을 때 "Q"를 추론할 수 있다는 논리 규칙)
간단한 예시:
"비가 오면 땅이 젖는다"라는 조건과 "비가 온다"는 사실이 있을 때, 우리는 "땅이 젖는다"는 결론을 도출할 수 있습니다.
여기서:
P: "비가 온다"
Q: "땅이 젖는다"
공리 집합: {P→Q, P}
*Undecidability
전제 논리의 완전성 증명은 결정 불가능합니다.
이는 변수의 무한 가능성 때문입니다.
유효성을 증명하는 절차는 존재하지만 무효성을 보일 수는 없습니다.
이는 반결정적(semi-decidable)입니다.
이러한 과정은 해결 반박 과정이라고 불립니다.
*Finding Proof(사진)
*Clause Form(논리적 일치 및 추론 과정에서 편리한 형식-함축, 전칭 및 존재 한정자가 없고 괄호가 없는 형태로, 일련의 논리합으로 구성)
변환 과정 (WFFs를 절 형태로 변환):
함축 기호 제거(Eliminate implication sign)
부정 기호의 범위 축소(Reduce scope of negation sign)
변수 표준화(Standardize variables)
존재 한정자 제거(Eliminate existential quantifier)
전항형(prenex form)으로 변환(Convert to prenex form)
행렬을 합동적 정상형(conjunctive normal form)으로 변환(Put matrix in conjunctive normal form)
전칭 한정자 제거(eliminate universal quantifier)
논리곱 제거(eliminate conjunctives)
*Requirements of Unification :
변수의 제한:
변수를 해당 변수를 포함하는 항(term)과 통합할 수 없습니다.
예를 들어, X는 f(X)로 대체될 수 없습니다
*Proof Procedure : 추론 규칙과 그 규칙을 논리적 표현 집합에 적용하여 새로운 문장을 생성하는 알고리즘의 조합입니다.
Truth Table Method:
변수를 포함하지 않는 표현의 타당성을 테스트하는 데 사용될 수 있습니다.
변수를 포함하는 표현의 타당성을 결정하는 것은 항상 가능하지 않습니다.
Complete Proof Procedure:
표현 집합에서 논리적으로 따라오는 모든 표현을 생성할 수 있습니다.
*Control of Resolution
-Derivation Graph:
어떤 해를 선택했는지를 추적하기 위한 그래프
초기 노드: 주어진 S의 절
새로운 노드: 해
링크: 부모 절에서 해로 연결
-Refutation Tree:
파생 그래프의 부분 그래프로, NIL로 레이블된 루트 노드를 가짐
집합 S가 만족 불가능함을 보여주는 해의 순서를 나타냄
*Control Strategy(Refutation Tree의 탐색 제어: 파생 그래프 내에서 반박 트리를 제어하는 방법)
완전성과 효율성:
너비 우선 검색 (Breadth-First Search):
낮은 레벨을 먼저 탐색
완전하지만 효율적이지 않음
Set-of-Support 전략:
적어도 하나는 부정된 목표 절이거나 부정된 목표로부터 생성된 절이어야 함
큰 절 공간에서 우수한 전략
Unit-Preference 전략:
Set-of-support와 단일 리터럴 우선
Linear-Input Form 전략:
부정된 목표와 원래 공리를 직접 사용
완전한 전략은 아님**Logical Inference 예제
명제: "모든 X에 대해, 만약 X가 인간이라면, X는 필멸자이다."
해석: 소크라테스가 인간임을 나타냄.
논리적 추론: 주어진 명제와 해석에 따라, 소크라테스가 필멸자라는 결론이 도출됨.
*Mean of 'Logically Follows':S를 만족시키는 모든 해석과 변수 할당이 X도 만족시킬 때, X는 S로부터 논리적으로 따라온다고 합니다
명제 S: 모든 X에 대해, 만약 X가 인간이라면 X는 필멸자이다.
해석 I: 소크라테스가 인간임을 나타냄.
추론 X: 소크라테스가 필멸자라는 결론을 도출.
