(Predicates and Quantifiers)

Slides:



Advertisements
Similar presentations
수학 7- 가 문자와 식 > 일차방정식의 풀이 > 교과서 p.111 일차방정식의 활용 수업계획수업활동.
Advertisements

3 학년 문제가 남느냐, 내가 남느냐 1. ( 아씨방 일곱 동무 ) 아씨의 방에는 바느질을 위한 친구가 몇 명이 있었나요 ? 정답은 ? 일곱.
폭력. 폭력이란 무엇인가 우상의 눈물 물리적인 폭력 ( 최기표 ) VS 지능적인 폭력 ( 임형우, 담임선생님 )
2012 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics)  중첩된 한정기호 (Nested Quantifiers)
1 박 2 일 !!! 인천마장초등학교 유수아. 1 박 2 일 멤버 인기순 위 1 위 이승기 2 위 엄태웅 3 위 은지원 4 위 김종민, 이수근 ※인터넷에서 본것이기 때문에 사람에따라 서 다를 수 있다. ※
제10주제. 해방정국과 신탁통치문제 8.15는 일제의 식민지에서 해방된 기쁨의 상징으로 일컬어짐.
석관중앙교회 5남전도회 석 관 중 앙 교 회 회원 소식 통권 05-04호 발행일 : 2005년 04월 회 장 : 장진호 집사
지역사회복지론 1조. 요양보호시설에 대해서 황성국 임재형 이동영
6주차:『GPU(CUDA) Programming』
(Mathematical Induction)
Discrete Mathematics Express
I 문학의 개념과 역할 1. 문학의 개념 (1) 언어 예술로서의 문학 (2) 소통 활동으로서의 문학
4. 목적론적 윤리와 의무론적 윤리 01. 경험주의와 이성주의 01. 경험주의와 이성주의 02. 결과론적 윤리와 공리주의
데이터 관리의 모든 것 데이터 최적화하기 데이터 정렬하기 자동 필터와 고급 필터
양태, 증거성, 의외성 통사론 기초
4장. 관계 대수와 SQL SQL 관계 데이터 모델에서 지원되는 두 가지 정형적인 언어
Ruby 프로그래밍 1 문자열 입출력 제어구조 looping 함수 정의
이산수학(Discrete Mathematics)
제2절 법인세의 계산구조와 세무조정 1. 각 사업연도소득에 대한 법인세 계산구조 회계와 사회 결산서상 당기순이익
4.2 SQL 개요 SQL 개요 SQL은 IBM 연구소에서 1974년에 System R이라는 관계 DBMS 시제품을 연구할 때 관계 대수와 관계 해석을 기반으로, 집단 함수, 그룹화, 갱신 연산 등을 추가하여 개발된 언어 1986년에 ANSI(미국 표준 기구)에서 SQL.
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
패턴인식 개론 Ch.5 확률 변수와 확률 분포.
with 신 동 면 교수님 임지영 장영태 조재영 황선희 황예빈
Internet Computing KUT Youn-Hee Han
Chapter 2. Finite Automata Exercises
UML exercise in Class.
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
계수와 응용 (Counting and Its Applications)
5. 관계대수와 관계해석 관계자료 연산(operation)
이산수학(Discrete Mathematics)
이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net.
관계 해석(Relational Calculus)
PCA Lecture 9 주성분 분석 (PCA)
Chapter 3: Introduction to SQL
데이터의 표현과 컴퓨터 연산 Prof. Jae Young Choi (최재영 교수)
1.4 중첩된 한정기호 (Nested Quantifiers) 이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
컴퓨터 개론 및 실습 Dept. Computer Eng. Hankuk University of Foreign Studies
Data Mining Final Project
개항기 조선과 동아시아 박 범 한국역사입문Ⅱ.
Ⅰ운동과 건강 관리 01 건강 관리와 삶의 질 향상 02 건강과 운동의 관계 이해 03 건강 생활과 운동 환경의 책임 의식.
Introduction to Programming Language
관계 해석(Relational Calculus)
이산수학(Discrete Mathematics)
이산수학(Discrete Mathematics)  증명 방법 (Methods of Proof)
6장 데이터 타입(3) 순천향대학교 컴퓨터공학부 하 상 호.
이산수학 (Discrete Mathematics)
이산수학(Discrete Mathematics)
논리와 명제 기본 개념 논리 연산자와 진리표 논리적 동치 한정 기호.
Chapter 4 변수 및 바인딩.
대구의 부도심 대구의 주요축 동대구 부도심 4조 강민석 / 박성균 / 최은지/ 황재현/김예지.
주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현. 주요 내용 명제 조건 명제와 쌍조건 명제 술어와 한정사 논리적 기호로 문장을 표현.
Welcome to Virus World 바이러스의 세계로 초대합니다.
이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle)
이산수학(Discrete Mathematics)
사도행전 13장 22절 말씀 –아멘 다 윗 을 왕 으 로 세 우 시 고 증 언 하 여 이 르 시 되 내 가 이 새 의 아 들
2015년 2학년 1반.
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
이산수학(Discrete Mathematics)
경찰행정과 세미나 결과를 공개해야한다. VS 비공개로 해야한다. 경찰의 근무성적평정 제도.
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
수학 2 학년 1 학기 문자와 식 > 부 등 식 ( 2 / 2 ) 부등식의 성질 이용 풀기.
이산수학(Discrete Mathematics)  술어와 한정기호 (Predicates and Quantifiers)
8단계 3층을 완성한다 Case 1 Case 2 Case 3 Case 4
[CPA340] Algorithms and Practice Youn-Hee Han
Chapter 3. 집합론.
PHP 기초문법 PHP를 공부하는데 있어 가장 기초가 되는 PHP기초문법에 대해서 배워 봅니다.
Presentation transcript:

(Predicates and Quantifiers) 이산수학 (Discrete Mathematics) 1.3 술어와 한정기호 (Predicates and Quantifiers) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

“x is greater than 3.” 술어(Predicate), 명제 함수(Propositional Function) 1.3 Predicates and Quantifiers “x is greater than 3.” 변수(variable) = x 술어(predicate) = P 명제 함수 (propositional function) P(x) = “x is greater than 3.” Q(x, y) = “x = y + 3” R(x, y, z) = “x + y = z” 일반적으로 n개의 변수 x1, x2, x3, …, xn을 포함하는 명제 함수는 P(x1, x2, x3, …, xn) 으로 표기한다.

한정기호(Quantifiers) 명제 함수를 명제로 만드는 방법 변수에 특정 값을 할당하는 방법 1.3 Predicates and Quantifiers 명제 함수를 명제로 만드는 방법 1. 변수에 특정 값을 할당하는 방법 2. 한정(quantification)을 적용하는 방법 변수에 특정 값을 할당하는 방법 P(x) = “x > 3” 만일 x = 4라면 P(x)는 true가 되고, x = 2라면 P(x)는 false가 된다. Quantification을 적용하는 방법 x의 정의역(domain)이 “4 이상인 모든 실수”라면, P(x)는 true가 된다. The collection of values that a variable x can take is called x’s domain or universal of discourse.

Universal Quantifier  (1/3) 1.3 Predicates and Quantifiers 정의 P(x)의 Universal Quantifier란 “정의역(domain)에 속하는 모든 값 x에 대하여 P(x)가 참이다.”라는 명제이다. Universal Quantifier의 표기 및 읽기 표기: xP(x) 읽기: “for all x in P(x)” 혹은 “for every x in P(x)”

Universal Quantifier  (2/3) 1.3 Predicates and Quantifiers Universal Quantifier의 개념적 이해 Domain의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면, xP(x)는 다음과 동일하다. P(x1)  P(x2)  ....  P(xn) Universal Quantifier의 사용 예 예 1: P(x)가 “x < 2”이고 domain이 모든 실수라 할 때, xP(x)의 진리 값은?  거짓 예 2: Q(x)가 “x2  0”이고 domain이 모든 실수라 할 때, xQ(x)의 진리 값은?  참

Universal Quantifier  (3/3) 1.3 Predicates and Quantifiers 반례(counterexample) P(x)가 명제 함수라 할 때, xP(x)가 거짓임을 보이기 위해서는 domain에 속하는 값 중 단지 하나의 값이라도 P(x)를 거짓으로 만드는 예를 보이면 된다. 이와 같이 P(x)를 거짓으로 만드는 예를 반례(counterexample)이라 한다. Counterexample 사용의 예 P(x)가 “x2 > 0”이고 domain이 모든 실수라 할 때, xP(x)의 counterexample은? x = 0이면 x2 = 0이 되어, x2 > 0를 만족하지 않는다. 따라서, xP(x)는 거짓이 되고, 이때 x = 0을 counterexample이라 한다.

Existential Quantifier  (1/2) 1.3 Predicates and Quantifiers 정의 P(x)의 Existential Quantifier란 “Domain에 속하는 적어도 하나의 값 x에 대하여 P(x)가 참이다.”라는 명제이다. Existential Quantifier의 표기 및 읽기 표기: xP(x) 읽기: “for some x in P(x)” 혹은 “there is an x such that P(x)”

Existential Quantifier  (2/2) 1.3 Predicates and Quantifiers Existential Quantifier의 개념적 이해 Domain의 모든 값을 x1, x2, …, xn으로 나열할 수 있다면, xP(x)는 다음과 동일하다. P(x1)  P(x2)  ....  P(xn) Existential Quantifier의 사용 예 예 1: P(x)가 “x > 3”이고 domain이 모든 실수라 할 때, xP(x)의 진리 값은?  참 예 2: Q(x)가 “x = x+1”이고 domain이 모든 실수라 할 때, xQ(x)의 진리 값은?  거짓

Quantifier 개념 요약 Statement When true? When false? xP(x) 1.3 Predicates and Quantifiers Statement When true? When false? xP(x) P(x) is true for every x. There is an x for which P(x) is false. xP(x) There is an x for which P(x) is true. P(x) is false for every x.

x(P(x)Q(x))  xR(x) Binding Variables 1.3 Predicates and Quantifiers Binding Variables vs. Free Variables 변수 x에 quantifier가 적용되거나 특정 값이 할당되면, x를 binding variable이라 한다. 변수 x에 quantifier가 적용되지 않거나 특정 값이 할당되지 않았으면, x를 free variable이라 한다. Quantifier가 적용되는 부분을 quantifier의 범위(scope)라 한다. binding variable xP(x, y) free variable x(P(x)Q(x))  xR(x) scope of x scope of x

Negation with Quantifiers (1/2) 1.3 Predicates and Quantifiers Negation 예제 x = student, P(x) = “x in the class has taken a course in calculus.” xP(x) = “Every student in the class has taken a course in calculus.” ¬xP(x) = “It is not the case that every student in the class has taken a course in calculus.” = “There is a student in the class who has not taken a course in calculus.” = x¬P(x)

Negation with Quantifiers (2/2) 1.3 Predicates and Quantifiers Negation 관련 법칙 Negation 관련 예제 x(x2 > x)의 부정  ¬x(x2 > x)  x¬(x2 > x)  x(x2  x) x(x2 = 2)의 부정  ¬x(x2 = 2)  x¬(x2 = 2)  x(x2  2) ¬xP(x)  x¬P(x) ¬xP(x)  x¬P(x)