1.4 술어와 한정기호
명제 논리?
모든 사람은 죽는다. + 소크라테스는 사람이다.
라는 두 명제가 주어질 때 소크라테스는 죽는다 라는 것을 증명하기엔 아직 부족함
객체 특진 관계 등이 필요함. "추론"
술어논리:
- 변수: X,Y,Z
- 명제 함수: P(x), M(x),
- 한정기호:
명제 함수는 명제의 일반화.
- X 는 3보다 크다 -> P(x)
p = ~ 3보다 크다.-개발자 적인 시각에서 보자면 P는 함수 x는 변수이자 P의 인자 값
명제 함수
변수 X에 할당되는 값에 다라 P(x)의 명제 진리값이 달라짐.
예를 들어 P(x)를 X > 0 이라고 하고, 정의역(domain)을 정수라 하면
- P(-3) == false
- P(3) == true
- P(0) == false
정의역 ==> U
그냥 진짜 함수의 개념과 똑같음.
인자를 넣어 Boolean 타입을 반환하는 함수
*만약 인자에 변수가 들어왔으면 해당 명제 함수는 명제라 할 수 없음.
진리값을 구할 수 없기 때문.
N-튜플
P(x1, x2, x3.....xn) 형태의 문장을 n-튜플이라고 함.
n-변수 술어나 n-항 술어 라고도 함.
복합 표현식
- 명제 논리의 접속사를 술어 논리에서도 사용.
P(x): x > 0 :
한정 기호(제한자, 수량사)
한정에 사용되는 단어는 all some many none과 같이 직접적인 수량, 특징이 아닌 포괄적인 것을 지칭하는 것
- 전칭한정기호: All의 의미인 A거꿀로
- 존재한정기호: 를 의미하는 ∃
∀x P(x): "정의역에 속하는 x의 모든 값에 대하여 P(x) 이다"
∃x P(x): 정의역에 속하는 적어도 하나의 값 x에 대하여 P(x) 이다.
전치한정기호
∀x p(x): 모든 x는 P(x) 이다.
- if P(x) denotes "x > 0" and U is the integers, then ∀x P(x) is false
P(x)가 x > 0 일 때 U가 자연수라면 모든 x는 0 이하이다.
- if P(x) denotes "x > 0" and U is the positive integers, then ∀x P(x) is true
- if P(x) denotes "x is even" and U is the integers, then ∀x P(x) is false
존재 한정 기호
유일 한정 기호(기호 뒤에 ! 붙임.) 잘 안쓰임.
∃!x P(x)는 오직 딱 하나의 X라는 의미.
유한 정의역을 가진 한정기호
한정 기호의 정의역이 유한하면, 모든 원소들을 나열할 수 있어서, 한정된 문장을 명제 논리로 표현할 수 있다.
∀x P(x) 를 정의역의 x를 가지고 반복하여 구할 수 있다.
- 매 단계마다 P(x)가 참이면, ∀x P(x)는 참이다.
- 만약 한 단계에서 P(x)가 거짓이면, ∀x P(x)는 거짓이 되고 반복을 종료.
∃x P(x) 를 정의역의 x를 가지고 반복.
- 만약 어느 단계에서 P(x)가 참이면, ∃x P(x)는 참이 되고 반복을 종료.
- 반복이 종료되어도 P(x)가 참인 X가 없으면, ∃x P(x)는 거짓.
정의역이 무한이더라도 이러한 방식으로 한정되지 않은 값을 통해 무한한 정의역이 존재할 수 있다.
한정 기호의 우선순위
한정기호 ∀와 ∃는 명제 논리의 모든 논리 연산자보다 상위의 우선순위를 갖는다.
EX) ∀x P(x) v Q(x) = (∀x P(x)) v Q(x) != ∀x ((Px) v Q(x))
아쉽게도 이런 우선순위를 고려하지 않고 그냥 ∀x P(x) v Q(x)로 쓰는 사람도 많으나 틀린 것임.
영어 문장을 논리 표현으로 변환 - 1
이 수업의 모든 학생들은 자바 수업을 듣는다.
정의역 U?
S1
U: 이 수업의 모든 학생
J(x): 자바 수업을 듣는다.
∀x J(x)
S2
U: 모든 사람
S(x): x는 이 수업 안의 모든 학생
∀x (S(x) -> J(x))
∀x (S(x) ^ J(x)) ?
and 연산자와 if 연산자라 진리값은 같게 나오나 문장을 영어로 풀어내면 다르게 나옴.
한정 기호를 포함한 논리적 동치
두 개의 서로 다른 논리식이 같은 진리값을 가진다면 동치임.
∀x ㄱㄱS(x) === ∀x S(x)
한정 기호를 논리곱과 논리합으로
정의역이 유한한 경우
- 전칭 한정기호로 된 명제는 한정 기호가 없는 명제의 논리곱과 동일
- 존재 한정 기호로 된 명제는 한정기호가 없는 명제의 논리합과 동일
한정 표현의 부정(시험 문제로 가끔 냄)
∀x J(x): 이산수학을 듣는 모든 학생은 자바 수업을 듣는다.
J(x): x는 자바 수업을 듣는다
U: 이 수업의 모든 학생
모든 학생이 듣지는 않는다와 일부 학생은 듣지 않는다 는 동치임
ㄱ∀x J(x) === ∃x ㄱJ(x)
수학은 명제들의 집합이다. 말과 같이 모호한 부분이 없다.
영어 문장을 논리 표현으로 변환
Q: Some student in this class has visited Mexico
A: ∃x(S(x)^M(x))
시스템 명세에 한정 기호 사용하기
술어 논리는 시스템이 충족해야하는 속성을 지정하는데 사용.
다음의 시스템 명세를 술어와 한정기호로 표현:
some example
논리 프로그래밍 언어(optional) - 넘어가도 ㄱㅊ
Prolog(from Programming in Logic)는 1970년대 인공지능(AI) 연구자들이 개발한 프로그래밍 언어.
논리 프로그래밍을 할 수 있는 언어: Prolog facts(명제, 사실) 과 Prolog rules(규칙)을 주는 방식으로 개발
초창기 개발은 논리 그 자체들을 가지고 개발하려 했음.
1.5 중첩된 한정기호 - 연습문제 안해도 됨
그냥 한정기호가 연속되는 것
∃x ∀y~~
1.6 추론 규칙 - 연습문제 안해도 됨
추론을 하는 방법 등을 다루는 부문.
재미는 있으나 어렵고 철학적 내용도 많이 다루기에 넘어감.
1.7 증명의 소개
수학적 문장의 증명
증명은 어떤 문장의 참을 입증하는 유효 논증이다.
수학, CS 및 기타 분야에서는, 일반적으로 더 짧은, 비형식적 증명이 사용된다. (책이나 이런 곳에선 상당히 구체적이고 까다로운 증명이 사용됨)
-
증명의 단계에서 하나 이상의 추론 규칙이 사용된다.
- 단계들은 생략할 수 있다.
- 추론의 규칙들은 명시적으로 표현되지 않는다.
- 사람들에게 이해와 설명이 더 쉽다.
- 그러나, 오류가 더 쉽게 발생할 수 있다.
-
증명의 응용
- 컴퓨터 프로그램이 올바른지 검증
- 운영체제가 안전한지 확인
- 인공지능에서 프로그램이 추론을 가능하게 함
- 시스템 명세가 일관성이 있는지 확인
몇가지 용어들
정리(theorem)란 다음을 이용하여 참임을 보일 수 있는 문장:
- 정의(definitions)
- 다른 정리
- 공리(axioms) (참임을 "가정"한 문장)
- 추론의 규칙
보조 정리(lemma)는 "helping throrem" 혹은 다른 정리를 증명하기 위해 필요한 결과(한 정리가 너무 길면 가독성이 떨어지니까 따로 뺀 정리)
따름 정리(corollary)는 어떤 정리로 부터 직접적으로 귀결될 수 있는 정리.(정리를 하다보니 나오는 정리?)
propositions는 덜 중요한 정리(정리,...는 아니지만 어느정도 참인 그런거)
가설(conjecture)은 참이라고 제안된 문장. 증명이 발견되면 정리가 됨. 거짓으로 판명될 수도 있음. (증명은 되지 않았으나 참으로 추정되는 것)
정리의 형태
정의역의 모든 원소들에 대하여 어떤 성질이 성립함을 확고히 한다.
수학에서는 이를 생략함.
예를 들면 x > y 이면 x**2 > y**2 는 생략함
정리 증명 방법
명제 ∀x(P(x) -> Q(x))를 증명하기 위해서는,
c가 정의역에 속한 임의의 원소일 때,
P(c) -> Q(c)가 성립함을 보이고,
전칭 일반화를 적용한다.
그러므로, 다음 형태의 문장을 증명해야함: p -> q
쉽게 말하자면 ∀x(P(x) -> q(x)) 를 분해하며 기초부분인 p -> q 부터 단계별로 참임을 증명해야함.
p -> q 증명
자명한 증명
만약 q가 참이라면 p -> q 도 참이다.
q가 참이면 뭐가 됐든 진리값은 참으로 나오기에 q가 참인 것만 보여주자!
공허한 증명
만약 p 가 거짓이면, p -> q 는 참이다.
[이러한 예가 어리석은 것 처럼 보이지만 사소하고 공허한 증명이 수학적 귀납법(5장)에서 자주 사용된다.]
직접 증명: p -> q
p나 q가 참이거나 거짓이라는 것을 보여주기가 쉽지 않을 떄 쓰는 것.
p가 참이라고 가정.
추론, 공리, 논리적 동치 등을 사용하여 q가 참임을 보임.
Q: 만약 n이 홀수인 정수라면 n 2은 홀수인 정수이다.
A: n이 홀수라고 가정. 홀수의 정의에 의하여 n = 2k + 1 인 정수 K가 존재한다. n = 2k + 1의 양변을 제곱하면:
n 2 = (2k + 1) 2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1 = 2r + 1,
단 r = 2k 2 + 2k인 정수
그러므로, n ** 2은 홀수인 정수이다.
직접 증명: p -> q - 2
정의: 만약 q != 0 인 정수 p 와 q가 존재하면, 실수 r = p/q 은 유리수이다.
유리수란? 두 정수의 비율로 나타낼 수 있는 수
무리수란? 이해할 수 없는 수
정수 / 정수 가 가능하면 유리수임.(단 분모는 0일 수 없음.)
r + s = p / q + t / u = pu + qt / qu
대우에 의한 증명: p -> q - 3
ㄱq가 참이라고 가정했을 때, ㄱp이 참임을 증명.
간접 증명이라고도 함.
ㄱp -> ㄱq === p -> q
예제: N이 정수이고 3n + 2 이 홀수라면, n은 홀수
풀이: N이 짝수라고 가정. 그러면, 임의의 정수 K에 대해 n = 2k
따라서 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k+1) = 2j for j = 3k + 1
그러므로 3n + 2는 짝수. ㄱq -> ㄱp가 참임을 보였으므로, p -> q 역시 참이다.
모순에 의한 증명: p -> q - 4
p가 참임을 증명하기 위해, ㄱp가 참이라고 가정하고 p ^ ㄱp 와 같은 모순을 유도(간접 증명).
상호 조건문 정리
상호조건문인 p <-> q의 정리를 증명하기 위해서는, p -> q와 q -> p를 둘 다 증명하게 된다.
1.8 증명 방법과 전략
경우에 의한 증명 - 1
모든 경우를 구하여 증명하기
(P1 v p2 v p3 ... v pn) -> q 를 증명하라.
항진명제 사용
만약 a >= b 이면, a @ b = max{a, b} = a 이고
글치 않으면 a @ b = max{a, b} = b 이다.
(즉, 연산자 @는 결합법칙이 성립)
Withour Loss Of Generality(WLOG)
EX: x와 y가 정수이고 x,y와 x + y가 모두 짝수이면 x와 y가 모두 짝수임을 보여라.
증명: 대우를 이용한 증명. x와 y가 모두 짝수가 아니라고 가정하면 하나 혹은 둘 다 홀수. 일반성을 잃지 않고 x가 홀수라고 가정. 그러면, x = 2m + 1.
하나의 예재만 보여줘도 상관이 없을 떄 사용
존재 증명 ∃x P(x)
생산적 존재 증명:
- P(c)가 참인 값 c(증인)를 찾는다
- 그러면, ∃x P(x)는 존재 일반화에 의해 참이다.
비생산적 존재 증명
P(c)를 참으로 하는 c가 존재하지 않는다고 가정하고, 모순을 유도한다.
반례
∃xㄱP(x) === ㄱ∀xP(x)
ㄱ∀xP(x)가 참(혹은, ∀xP(x)이 거짓) 인 것을 보이기 위해서는 ㄱP(c)가 참 혹은 P(c)가 거짓인 c를 찾는다.
증명 전략: p -> q
방법 선택
1. 직접 증명 방법 시도.
2. 직접 증명으로 부족하면, 간접 증명법으로 시도(ex: 대우 증명법)
오똔 방법이든, 전략을 선택.
1. 전향 추론을 시도.
미해결 문제들의 역할
미해결 문제는 수학에 많은 동기를 부여했다. 그 중 하나가 페르마가 300년 전에 제시한 가설이다.
페르마의 마지막 정리:
x^n + y^n = z^n 은 n > 2인 정수 x, y, z(xyz != 0)에 대해서 해를 갖지 않는다.
증명은 1990년대에 Andrew Wiles에 의해 발견되었다.
그 외 증명 방법
앞으로 다른 많은 증명 방법을 소개한다
- 수학적 귀납법: 이것은 정의역이 양의 정수인 경우 ∀n P(n) 형태의 증명에 유용하다.
- 구조적 귀납법: 재귀적으로 정의되는 집합들에 대한 결과를 증명하는 데 사용한다.
- 칸도르의 대각선 방법: 무한집합의 크기에 대한 결과를 증명하는데 유용하다.
- 조합 증명: 계수 논증에 의해 결과를 증명하는 데 사용된다.
- 정지문제: 풀 수 없는 문제의 존재에 대한 증명.
나중에 빈 부분 있으면 말해줘. 검색해서 채워 넣을거임
