Predicate Logic
술어논리
Predicate symbol
=> 대문자로 표현되고, 문장을 return한다. 대상 간의 관계 혹은 대상의 특성을 알림. assign(=).
Function symbol
=> 한 대상과 다른 대상에 대입시킴. boolean 값을 return. boolean(==).
term : Constant symbols, variable 그 자체나 functional symbol과의 결합으로 주어짐. => 그렇다면 predicate symbol은?
variable과 propositional function(ex. "x > 3")의 결합 p(x) 자체는 proposition이 아니다. 왜냐면 참과 거짓을 모르기 때문.
하지만 x에 특정 값이 배정된다면, 이는 proposition이 된다.
Quantifiers = Universal quantifier와 Existential quantifier로 나뉜다.
x의 전체 범위를 u.d of x(universe of discourse) 또는 domain of x라고 한다.
Predicate("x is full")에 u.d. of x("parking spaces at SNU") Quantifer를 결합하면 proposition이 된다. => 참과 거짓을 판별할 수 있기 때문.
quantifier로 묶이지 않은 변수 x를 free variable x, quantifier로 묶인 변수 x를 bound variable이라고 한다.
<wff>
모든 predicate formula는 wff이다
P가 wff이면, ~P도 wff이다.
두개의 wff가 부모자식 관계이거나, boolean operator로 연결되어 있다면 wff이다.
quantifier로 묶여 있어도 wff이다.
//기호 적기 귀찮아서 앞으로 Universal quantifier는 U, Existential quntifier는 E로 작성하겠다.
만약에 Likes(x, y)["x likes y"]라는 Predicate이 있다면 UxEyLikes(x,y)와 EyUxLikes(x,y)는 다르다!!!
UxEyLikes(x,y) = For everybody, there is somebody he likes. (모든 사람은 그 사람이 사랑하는 특정 사람이 있다.)
EyUxLikes(x,y) = Everybody has somebody they like.(모든 사람이 사랑하는 특정 사람이 있다. (ex. 유재석))
UxExP(x) = x는 이미 E로 묶였기 때문에 U로는 묶이지 않음. not valid question
(UxP(x)) AND Q(x) = Q의 변수 x는 묶이지 않은 free variable이기 때문에 명제가 아님
(UxP(x)) AND (ExQ(x)) = 이건 가능. 왜냐면 다른 변수 x가 존재하고 각각 묶이기 때문.
=> 모든 변수가 묶이거나 특정 값으로 배정되면 명제가 된다.
만약 u.d. = {a, b, c, d, ...}라면
UxP(x) = P(a) AND P(b) AND P(c) AND P(d) AND ......
ExP(x) = P(a) OR P(b) OR P(c) OR P(d) OR ....
UxUyP(x,y) <-> UyUxP(x,y)
ExEyP(x,y) <-> EyExP(x,y) => 같은 종류 Quantifier끼리는 교환해도 문제 없음
Ux(P(x) AND Q(x)) <-> (UxP(x)) AND (UxQ(x))
Ex(P(x) OR Q(x)) <-> (ExP(x)) OR (ExQ(x))
UxEy(x + y = 0) = true
EyUx(x + y = 0) = false
monotonic => 새로 추가된 sentence가 포한된 knowledge base가 기존의 knowledge base를 모두 포함하는 경우.
Problems of predicate logic => 반복적으로 풀어볼 것!
Proofs and Inference Rules
Terminology
Theorem : A statement that has been proven to be true
Axioms, postulates, hypotheses, premises : Assumptions defining the structures about which we are reasonning.
Lemma : A minor theorem used as a stepping-stone to proving major theorem.
Corollary : A minor theorem proved as an easy consequence of a major theorem
Theory : The set of all theorems tha can be proven from a given set of axioms
Rules of inference : Patterns of deriving conclusions from hypotheses : Correct and Complete
An argument is a sequence of statements that end with a conclusion.
An argument is valid if and only if it is impossible for all the premises to be true and for the conclusion to be false.
(p -> q && p ) <=> q
Each rule of inference corresponds to an implication that is a tautology.
((p -> q) AND p) -> q
Implication Tautologies
Biconditional Tautologies
check할 것!