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.
The subfields of Discrete mathematics include:
- Set theory
- Graph theory
- Number theory
- Algorithm theory
- Discrete geometry
- Game theory
- Information theory
- Probability theory
- Operations research
- Theory of computation
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".https://www.tutorialspoint.com/discrete_mathematics/discrete_mathematics_propositional_logic.htm
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
The difitnion can be refered in Wiki.
|A||B||¬A||A ∧ B||A ∨ B||A ⇒ B||A ⇔ B|
The logical operations can be defined by their truth tables.
And there is a tool for show the truth tables made by Stanford University.https://web.stanford.edu/class/cs103/tools/truth-table-tool/
There are different types of "or"
Inclusive or : A ∨ B is true if and only if at least either of A and B is
Exclusive or : A ⊕ B is true if and only if exactly one of A and B is
Conflicting or : A || B is true if and only if at most one of A and B is
|A||B||A ⇒ B|
- 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.
- A ∨ A ⇔ A
- A ∧ A ⇔ A
it doesn't matter how we group the statements.
- A ∨ (B ∨ C) ⇔ (A ∨ B) ∨ C
- A ∧ (B ∧ C) ⇔ (A ∧ B) ∧ C
we can swap statements over and still get the same truth value.
- (A ∨ B) ⇔ (B ∨ A)
- (A ^ B) ⇔ (B ^ A)
- A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
- A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)
- (A ∨ B) ∧ A ⇔ A
- (A ∧ B) ∨ A ⇔ A
- ¬(A ∨ B) ⇔ ¬A ∧ ¬B
- ¬(A ∧ B) ⇔ ¬A ∨ ¬B
- (A ⇒ B) ⇔ (¬B ⇒ ¬A)
- ((A ⇒ B) ∧ A) ⇒ B
- ((A ⇒ B) ∧ (B ⇒ C)) ⇒ (A ⇒ C)
- ((A ⇒ B) ∧ (B ⇒ A)) ⇔ (A ⇔ B)
For example, law of contrapositive
(A ⇒ B) ⇔ (¬B ⇒ ¬A)
|A||B||¬B||¬A||A ⇒ B||¬B ⇒ ¬A||(A ⇒ B) ⇔ (¬B ⇒ ¬A)|
(A ⇒ B) ⇔ (¬A ∨ B)
|A||B||A ⇒ B||¬A||¬A ∨ B|
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.