👋

Discrete Mathematics I

2021/02/12に公開

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.

https://artofproblemsolving.com/news/articles/discrete-math

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".

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

https://ja.wikipedia.org/wiki/論理記号の一覧

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.

https://web.stanford.edu/class/cs103/tools/truth-table-tool/

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.

https://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html

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