본문 바로가기

Computer Science/이산수학8

이산수학 2.2 Set Operations 집합 연산 chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.2 Set Operations Union 합집합 표기: A ∪ B Example: What is {1,2,3} ∪ {3, 4, 5}? Solution: {1,2,3,4,5} Intersection 교집합 표기: A ∪ B 만약 교집합이 존재하지 않는다면, A와 B는 disjoint되었다고 말한다. Example: What is {1,2,3} ∩ {3,4,5} ? Solution: {3} Example: What is {1,2,3} ∩ {4,5,6} ? Solution: ∅ Complement 여집합 U - A (전체집합에서 A를 제외한 나머지) Ā(or Ac) = {.. 2021. 9. 25.
이산수학 2.1 Sets 집합 chapter 2. Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1 Sets 집합 Sets 집합은 순서가 없는(unordered) object들의 모임이다. ex. 반의 학생들 / 방의 의자들 집합의 object들을 elements(원소), 또는 집합의 members(멤버)라 칭한다. 집합은 이러한 element들을 포함(contain)하고 있다. a ∈ A : a는 집합 A의 element이다. a ∉ A : a는 집합 A의 element가 아니다. Describing a Set: 원소나열법 S = {a,b,c,d} 순서는 중요하지 않다. ☞ S = {a,b,c,d} = {b,c,a,d} 중복 멤버는 허용하지 않는다. ☞ S =.. 2021. 9. 24.
이산수학 1.4 Predicates and Quantifiers 술어와 한정 기호(3) chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Equivalences in Predicate Logic predicates(술어)와 quantifiers(한정자)가 포함된 문장은 동일한 진리 값을 갖는 경우에만 논리적으로 동일하다. - 이 statements(진술)로 대체되는 모든 predicate에 대하여 - 표현식의 변수에 사용되는 담론의 모든 domain에 대해 표기법 S ≡ T: S와 T가 논리적으로 동일하다. Example: ∀x¬¬S(x) ≡ ∀xS(x) Thinking about Quantifiers as Conjunctions and Disjunctions Conjunctions: ∧ Disjuncti.. 2021. 9. 24.
이산수학 1.4 Predicates and Quantifiers 술어와 한정 기호(2) chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Quantifiers quantifiers(한정자): all과 some를 포함한 영어 단어의 의미를 표현하기 위해 필요하다. - “All men are Mortal.” - “Some cats do not have fur.” 가장 중요한 두 가지 한정자는 다음과 같다. - 전체 한정자(Universal Quantifier), “For all,” symbol: ∀ - 존재 한정자(Existential Quantifier), “There exists,” symbol: ∃ ∀xP(x) (☞모든 x에 대해 P(x)) 와 ∃xP(x) (☞P(x)인 x가 존재) 와 같이 사용한다. .. 2021. 9. 24.
이산수학 1.4 Predicates and Quantifiers 술어와 한정 기호(1) chapter 1. The Foundations: Logic and Proofs 1.4 Predicates and Quantifiers Propositional Logic Not Enough "모든 사람은 죽는다." "소크라테스는 남자다." ☞ "소크라테스는 죽는다" 명제 논리(Propositional Logic)로는 이러한 추론을 나타낼 수 없다. 따라서 사물, 그 속성, 그리고 그 관계에 대해 말하는 언어가 따로 필요하다. Introducing Predicate Logic 술어논리 도입 술어 논리는 다음과 같은 새로운 기능을 사용한다. 변수(Variables): x, y, z 술어(Predicates): P(x), M(x) ☞술어논리에서는 변수가 들어간 형태를 허용. 명제 논리의 논리식은 변수를 포함.. 2021. 9. 24.
이산수학 1.3 Propositional Equivalences 명제 동치 chapter 1. The Foundations: Logic and Proofs 1.3 Propositional Equivalences 명제 동치(section 1.3) Tautologies, Contradictions, and Contingencies tautology : 언제나 true 값을 갖는 명제(항진 명제) ex. p ∨¬p contradiction : 언제나 false 값을 갖는 명제(모순 명제) ex. p ∧¬p contingency : p와 같이 true가 되기도 하고 false가 되기도 하는 명제 Logically Equivalent 만약 *p ↔ q가 항진명제라면, 두 개의 결합 명제 p와 q는 논리적으로 동치이다. 이를 p ⇔ q 또는 p ≡ q 로 나타낸다. 진리표에서 각 열의 값.. 2021. 9. 9.
이산수학 1.2 Aplication of Propositional Logic 명제이론의 응용 chapter 1. The Foundations: Logic and Proofs 1.1 Propositional Logic 명제이론(section 1.2) Translating English Sentence 영문장 → 명제 1. atomic proposition 확인 → 명제변수로 나타내기 2. 적절한 logical connectives 결정 ex 1) "If I go to Harry’s or to the country, I will not go shopping." p : I go to Harry’s q : I go to the country. r : I will go shopping. If p or q then not r. ex 2) “You can access the Internet from camp.. 2021. 9. 8.
이산수학 1.1 Propositional Logic 명제이론(+implication함축을 쉽게 이해하기) chapter 1. The Foundations: Logic and Proofs 1.1 Propositional Logic 명제이론(section 1.1) Propositions(명제) 명제: True / False로 정의할 수 있는 서술문. 명제의 예 1. 지구는 둥글다 2. 1 + 0 = 0 3. 7 + 7 = 14 명제가 아닌 경우 1. 자리에 앉아라. 2. 오늘 몇 일이지? 3. x + 3 = 5 // x값에 따라 결과가 달라짐 propositional Logic 명제 변수 propositional variable p, q, r, s, .... 복합 명제 Compound Propositions 하나 이상의 명제와 논리 연산, 괄호로 이루어진 명제 논리연산 Negation 부정 ¬ Conjuncti.. 2021. 9. 8.
반응형