Discrete Mathematics I
Why this is important?
The mathematics of modern computer science is built almost entirely on discrete math, in particular combinatorics and graph theory. This means that in order to learn the fundamental algorithms used by computer programmers, students will need a solid background in these subjects. Indeed, at most universities, a undergraduate-level course in discrete mathematics is a required part of pursuing a computer science degree.
Subfields of Discrete Mathematics
The subfields of Discrete mathematics include:
- Logic
- Set theory
- Combinatorics
- Graph theory
- Number theory
Or
- Algebra
- Algorithm theory
- Cryptography
- Discrete geometry
- Game theory
- Information theory
- Probability theory
- Operations research
- Theory of computation
Logical Operations
Statements (Propositions) in logic can be connected by logical operations.
A proposition is a collection of declarative statements that has either a truth value "True" or a truth value "False".
There are 5 logical operations:
- Negation : ¬ A
- And (Conjunction) : A ∧ B
- Or (Inclusive Or . Disjunction) : A ∨ B
- If ... , then ... (Implication) : A ⇒ B
- ... if and only if ... (Equivalence) : A ⇔ B
Truth tables
The difitnion can be refered in Wiki.
| A | B | ¬A | A ∧ B | A ∨ B | A ⇒ B | A ⇔ B |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
The logical operations can be defined by their truth tables.
And there is a tool for show the truth tables made by Stanford University.
Or
There are different types of "or"
-
Inclusive or : A ∨ B is true if and only if at least either of A and B is
true. -
Exclusive or : A ⊕ B is true if and only if exactly one of A and B is
true. -
Conflicting or : A || B is true if and only if at most one of A and B is
true.
A | B | A ∨ B | A ⊕ B | A || B |
---|---|---|---|---
T |T | T | F | F
T |F |T |T |T
F |T |T |T |T
F |F |F |F |T
implication
| A | B | A ⇒ B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
examples:
- Compound statement: "1+1=2 ⇒ 1+1=2" True
- Compound statement: "1+1=2 ⇒ 1+1=3" False
- Compound statement: "1+1=3 ⇒ Human beings are mammals." True
To understand why this table is the way it is, consider the following example:
"If you get an A, then I'll give you a dollar."
The statement will be true if I keep my promise and false if I don't.
Suppose it's true that you get an A and it's true that I give you a dollar. Since I kept my promise, the implication is true. This corresponds to the first line in the table.
Suppose it's true that you get an A but it's false that I give you a dollar. Since I didn't keep my promise, the implication is false. This corresponds to the second line in the table.
What if it's false that you get an A? Whether or not I give you a dollar, I haven't broken my promise. Thus, the implication can't be false, so (since this is a two-valued logic) it must be true. This explains the last two lines of the table.
Properties of logical operations
idempotence
- A ∨ A ⇔ A
- A ∧ A ⇔ A
associativity
it doesn't matter how we group the statements.
- A ∨ (B ∨ C) ⇔ (A ∨ B) ∨ C
- A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C
commutativity
we can swap statements over and still get the same truth value.
- (A ∨ B) ⇔ (B ∨ A)
- (A ^ B) ⇔ (B ^ A)
distributivity
- A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
- A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)
absorption laws
- (A ∨ B) ∧ A ⇔ A
- (A ∧ B) ∨ A ⇔ A
De Morgan’s laws
- ¬(A ∨ B) ⇔ ¬A ∧ ¬B
- ¬(A ∧ B) ⇔ ¬A ∨ ¬B
law of contrapositive
- (A ⇒ B) ⇔ (¬B ⇒ ¬A)
modus ponens
- ((A ⇒ B) ∧ A) ⇒ B
syllogism
- ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
?
- ((A ⇒ B) ∧ (B ⇒ A)) ⇔ (A ⇔ B)
How to prove the properties of logical operations
For example, law of contrapositive
(A ⇒ B) ⇔ (¬B ⇒ ¬A)
| A | B | ¬B | ¬A | A ⇒ B | ¬B ⇒ ¬A | (A ⇒ B) ⇔ (¬B ⇒ ¬A) |
|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T |
| T | F | T | F | F | F | T |
| F | T | F | T | T | T | T |
| F | F | T | T | T | T | T |
tautologies and logical equivalences
(A ⇒ B) ⇔ (¬A ∨ B)
| A | B | A ⇒ B | ¬A | ¬A ∨ B |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Since the columns for A ⇒ B and ¬A ∨ B are identical, the two statements are logically equivalent. This tautology is called Conditional Disjunction. You can use this equivalence to replace a conditional by a disjunction.
Discussion