DiscreteMathematics
Updated:
Proposition
A sentence or formula that can clearly distinguish true or false.
- Simple proposition
A proposition of units that can no longer be divided. - Synthetic proposition
A proposition of simple propositions.
Logic
Proposition logic: Can’t deduce new facts using the elements that make up the proposition because they are only interested in the true and false of the proposition unit
Predicate logic: It describes the behavior, condition, and nature of the subject
Proposition function: A formula or sentence that is decided function’s truth by variable
Quantifier: limit variavle value. ex) some, all
Inference: The process of drawing true facts from facts known to be true through logical processes.
- Premise
Proposition that already known - Conclusion
New proposition
Hypothetical syllogism
- p -> q
- q -> r
- p -> r
Proof
Inference rule: A rule that draw another proposition and logic from some proposition basically use logical equvaluation.
Axiom
Basically assumption that is used to proof another proposition.
Proof
Assume specific axiom and then prove the proposition proposed under the assumption.
Proof in computer science
It is necessary to check program run well.
Theorem
It is proved conclusion by logic based on axiom
Lemma: Proposition that is used to prove theorem
Corollary: It is proposition that is easilly drew from theorem
Method of proof
Set
Set: Set is a group of elements that have same specific
Tabular form: A = {1, 2, 3, 4}
Set-builder form: A = {x | 0 < x <=4, x is integer}
Finite set: It has finite elements
Infinite set: It has infinite elements
Empty set: A = {}
Cardinality: |A| = 5, the number of elements
Venn diagram: It is a picture that shows relations of sets
Matrix
Binary relation
Function
Boolean algebra
Graph
Adjacency matrix Adjacency list
Types of graphs
Shortest path problem