|
Tags: 날씨 | logic | the | 오늘은 | not | you | 것이다 | then | for
1장. 논리, 증명, 집합, 함수 (Logic, Proof, Sets and Functions) 1장 1절. 논리 (Logic) 숭실대학교 IT대학 컴퓨터학부
2008년 1학기
김완섭
wskim92@ssu.ac.kr
|
|
|
|
강의 시작에 앞서…
이산수학을 왜 공부하는가?
아래의 많은 컴퓨터 과목의 기초가 된다.
자료구조, 알고리즘, 데이터베이스, 오토마타, 형식 언어론, 프로그래밍 언어
컴파일러, 컴퓨터 보안, 암호학, 운영체제 등
따라서,
이산수학은 컴퓨터 고급전공자 or 컴퓨터 과학자로서의 기본 관문이다.
이산수학의 통해 수학의 기초를 제대로 학습해두지 못한다면 추후에
위의 과목을 배울 때에 상당한 어려움을 겪게 된다.
|
|
|
|
이 강의에서 배울 내용 (2008년 1학기)
논리적 사고력, 효율적인 프로그래밍 or 검증을 위한 기초, 인공지능의 기초 효율적인 알고리즘 작성(빠르고 메모리 적게 사용) : 저장, 탐색 방법 등 알고리즘 분석의 기초 (어떤 알고리즘이 더 좋은가? 비교) 데이터 분석, 예측 재귀적인 프로그래밍 기법, 알고리즘 분석의 기초 1장. 논리, 증명, 집합, 함수
2장. 알고리즘, 정수, 행렬
3장. 수학적 추론, 귀납법, 재귀
4장. 계수
5장. 이산적 확률
|
|
|
|
이 강의에서 배울 내용 (2008년 2학기)
실세계의 복잡한 관계에 대한 관리 방법? 데이터베이스 분야의 수학적 기초 알고리즘 분석을 위한 수학적 기초 최단 경로 찾기 등의 실제적인 문제 해결 방법 등 자료의 효율적인 저장 및 검색에 유용한 트리 구조 컴퓨터의 내부 회로 설계 프로그래밍 언어, 컴파일러 등의 수학적 기초 6장. 고급 계수 방법
7장. 관계
8장. 그래프
9장. 트리
10장. 부울 대수
11장. 계산 모델링
|
|
|
|
1.1 논리 (Logic)
올바른 판단을 위한 지식들(사실,규칙,추론과정) 국어사전 : 말이나 글에서 사고나 추리 따위를 이치에 맞게
이끌어 가는 과정이나 원리 ‘논리’란 무엇인가?
아래 글은 논리적인가?
나는 키가 큰 사람이 좋다.
잘 생긴 사람만 우리 동아리에 가입할 수 있다.
성적이 우수한 학생들에게 장학금을 부여할 것이다.
날씨가 추우면 사람들은 털모자를 뒤집어 쓴다.
창밖에 어떤 사람이 털모자를 뒤집어 쓰고 있으므로 날씨가 추울 것이다.
“비가 오면 우산을 꼭 써야 한다.”는 규칙이 있다.
비가 오지 않는데도 우산을 쓰는 사람은 그는 규칙을 어긴 것이다.
|
|
|
|
1.1 논리 (Logic)
컴퓨터 과학 분야에서 ‘논리’가 왜 필요한가?
수학적 추론의 기초가 된다.
즉, 인공지능 시스템의 기초가 된다.
컴퓨터의 내부 회로는 논리적으로 구성된다.
즉, 컴퓨터의 구조를 이해하는 데 필요하고, 회로를 제작하는데 필요하다.
프로그램을 제대로 작성하려면 논리를 알아야 한다.
프로그램 과정에서 논리 연산을 자주 하게 된다.
논리를 사용하여 프로그램의 정확성을 검증할 수 있다.
|
|
|
|
1.1 논리 (Logic)
(참) (거짓) (거짓) (참) 명제 (Propositions)
명제란 ‘참’ 또는 ‘거짓’으로 판정할 수 있는 선언적 문장을 말한다.
예제 1. 다음의 모든 문장들은 명제인가?
(1) 미국의 수도는 워싱턴 D.C.이다.
(2) 캐나다의 수도는 토론토이다.
(3) 1 + 1 = 2
(4) 2 + 2 = 3
|
|
|
|
1.1 논리 (Logic)
(명제 아님) (명제 아님) (명제 아님) (명제 아님) 예제 2.
아래의 각 문장들은 명제인가? 명제가 아닌가?
(1) 몇 시입니까?
(2) 이것을 신중하게 읽어라.
(3) x + 1 = 2
(4) x + y = z
|
|
|
|
1.1 논리 (Logic)
올바른 추론 올바른 추론 잘못된 추론 주어진 명제들을 사용하여 새로운 명제를 추론할 수 있다.
예를 들어, 아래와 같은 명제들이 참이라고 해보자.
아버지는 금요일마다 아이스크림을 사오신다.
오늘은 금요일이다.
오늘은 비가 온다.
추론한 결과들
오늘은 토요일이 아니다.
오늘은 금요일이므로 아버지가 아이스크림을 사오실 것이다.
오늘은 비가 오므로 아버지가 아이스크림을 사오지 않으실 것이다.
|
|
|
|
1.1 논리 (Logic)
정의 1.
p가 명제라면, “It is not the case that p”라고 하는 것도 역시 명제이다.
이것을 p의 부정(negation)이라고 하며, ￢p (not p)로 표기한다.
p : “Today is Friday”.
￢p : It is not the case that today is Friday”.
Today is not Friday.
It is not Friday today.
|
|
|
|
1.1 논리 (Logic)
main()
{
int gildong = 75;
int soongsil = 100;
if( soongsil >= 80 )
printf(“당신은 Pass 되었습니다. ”);
if( !(gildong >= 80) )
printf(“당신은 Fail 되었습니다. ”);
} Not 을 사용하는 프로그램
성적이 80점 이상이면 Pass 입니다.
성적이 80점 이상이 안되면 Fail 입니다.
|
|
|
|
1.1 논리 (Logic)
P : 오늘은 비가 온다.
Q : 오늘은 토요일이다.
P∧Q : 오늘은 토요일이고 비가 온다.
P : 오늘은 비가 온다.
Q : 오늘은 날씨가 매우 맑다.
P∧Q : 오늘은 비가 오고 매우 맑다. 정의 2
p와 q가 명제라 하면, “p and q”도 명제이며 p∧q라고 표기한다.
이 명제는 p, q가 모두 참일 때만 전체가 참이 되는 명제이다.
p∧q는 p, q의 논리곱(conjunction)이라고도 한다.
|
|
|
|
1.1 논리 (Logic)
main()
{
int visit = 9;
int score = 85;
if( (visit>=8) && (score>=80) )
printf(“당신은 Pass 되었습니다. ”);
} And 를 사용하는 프로그램
출석이 8회 이상이고
성적이 80점 이상이어야지만 Pass 할 수 없습니다.
|
|
|
|
1.1 논리 (Logic)
P : 오늘은 일요일이다.
Q : 오늘은 날씨가 매우 맑다.
P∨Q : 오늘은 일요일이고, 날씨가 매우 맑다.
오늘은 날씨가 매우 맑은 일요일이다. 정의 3 p와 q가 명제이면, “p or q”도 명제이며 p∨q라고 표기한다.
이 명제는 p, q가 모두 거짓일 때만 전체가 거짓이 되는 명제이다.
그 외의 경우는 모두 참이 된다. (즉, 둘 중 하나라도 참이면 참이다!)
p∨q는 p, q의 논리합(disjunction)이라고도 한다.
|
|
|
|
1.1 논리 (Logic)
예제 5
p와 q가 아래와 같을 때, p, q 명제의 논리합 p∨q는 무엇인가?
p : “Today is Friday.”
q : “It is raining today.”
p∨q : “Today is Friday or it is raining today.”
|
|
|
|
1.1 논리 (Logic)
main()
{
int visit = 7;
int score = 85;
if( (visit>=8) || (score>=90) )
printf(“당신은 Pass 되었습니다. ”);
} Or 를 사용하는 프로그램
출석이 8회 이상이거나
성적이 90점 이상이면 Pass 할 수 있습니다.
|
|
|
|
1.1 논리 (Logic)
“Students who have taken calculus or
computer science can take this class” “Students who have taken calculus or
computer science, but not both,
can take this class” 출석 8회 이상, 성적 80점 이상
둘다 만족하면 Pass, 둘다 만족못하면 Fail
둘 중 하나 만족하면 재시험의 기회를 준다. 정의 4 p와 q가 명제라면, “p exclusive-or q”도 명제이며 p q 로 표기
이 명제는 p, q 중 어느 하나만이 참일 때 전체가 참이 되는 명제이다.
즉, 둘 다 거짓이거나, 둘 다 참일 때는 전체 명제가 거짓이 된다.
|
|
|
|
1.1 논리 (Logic)
p q (p∧￢ q) (￢ p∧q) ∨ ⇔ p q 를 ∧ ∨ ￢ 을 사용하는 논리표현으로 변환하라.
p q 는 p가 참이고 q가 거짓이어야 전체가 참이 되거나 또는
p가 거짓이고 q가 참이어야 전체가 참이 된다.
|
|
|
|
1.1 논리 (Logic)
main()
{
int v = ? ;
int s = ? ;
if( ((v>=8) && !(s>=80)) || ( !(v>=8) && (s>=80)) )
printf(“당신은 재시험에 응시할 수 있습니다. ”);
} Exclusive-Or 를 사용하는 프로그램
조건1: 출석이 8회 이상, 조건2: 성적이 80점 이상
두 조건 중 하나만 만족하는 학생에게는 재시험의 기회가 준다.
|
|
|
|
1.1 논리 (Logic)
이때 앞에 위치한 p를
가정(hypothesis) 또는 전제(premise),
전항(antecedent)라고 하며,
뒤에 위치한 q를
결론(Conclusion) 또는
결과(consequence)라고 한다. 비가 오면, 사람들은 우산을 쓴다.
날씨가 추우면, 사람들은 모자를 뒤집어 쓴다. P: 비가 온다. Q : 우산을 쓴다.
비가 오는데 우산을 쓰지 않으면 오류!
비가 오지 않는데 우산을 쓰면 오류! (아님) 정의 5 함축(Implication)
p와 q가 명제라 하면, 함축 “p q”도 명제이다.
이 명제는 p가 참이고, q가 거짓일 경우에 전체 명제가 거짓이 되며,
다른 경우에는 모두 참이 된다.
|
|
|
|
|
Embed a live preview of this presentation on your site.
Copy code to your clipboard, or click here for instructions.
|
