Unit 1: Logic Flashcards
1
Q
Define
Proposition
A
A proposition is:
a declarative sentence
(a sentence that declares a fact),
that is either true or false, but not both.
2
Q
Define
Negation
A
The negation of p, denoted by ¬p, is the statement:
it is not the case that p
3
Q
Define
Conjunction
A
The conjunction of p and q, denoted by ** p ∧ q**, is the proposition:
p and q
The conjuction p ∧ q is true when both p and q are true, and false otherwise.
4
Q
Define
Disjunction
A
The disjunction of p and q, denoted by p ∨ q, is the proposition:
p or q
The disjunction p ∨ q is false when both p and q are false and true otherwise.
5
Q
Define
Implication
A
The implication p → q, is the proposition:
if p then q
p → q is false when p is true and q is false, and true otherwise.
The implication, p is callsed the hypothesis.
And q is called the conclusion
6
Q
Define
Converse
A
The proposition q → p is called the converse of p → q
7
Q
Define
Contrapositive
A
The contrapositive of p → q is:
¬q → ¬p
8
Q
Define
Biconditional statement
A
The biconditional statement p ↔ q, is the proposition:
p if and only if q
The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise.
9
Q
Precedence of logical operators
A
¬-
∧and∨ -
→and↔
10
Q
Define
(propositional) formula
A
A proposition or a compound proposition.
11
Q
Define
Truth assignment
A
A truth assignment to a propositional formula is an assignment of truth values to each of the propositions that occur in the formula.
12
Q
Define
Tautology
A
A formula that is true under every truth assignment.
13
Q
Define
Logical equivalence
A
Formulats that have the same truth values under all possible truth assignments are called logically equivalent.
Defined:
Formulas p and q are logically equivalent, if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
The symbol ⇐⇒ is sometimes used instead of ≡ to denote logical equivalence.
14
Q
Idempotent laws
A
(p ∧ p) ≡ p
(p ∨ p) ≡ p
15
Q
Commutative laws
A
(p ∧ q) ≡ (q ∧ p)
(p ∨ q) ≡ (q ∨ p)
16
Q
Associative laws
(logic)
A
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
17
Q
Absorption laws
(logic)
A
p ∧ (p ∨ q) ≡ p
p ∨ (p ∧ q) ≡ p
18
Q
Distributive laws
A
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
19
Q
Double negation
A
¬¬p ≡ p
20
Q
De Morgan’s laws
A
¬(p ∧ q) ≡ (¬p ∨ ¬q)
¬(p ∨ q) ≡ (¬p ∧ ¬q)
21
Q
Tertium non datur
A
(p ∧ ¬p) ≡ F
(p ∨ ¬p) ≡ T
22
Q
Identity laws
A
(p ∧ T) ≡ p
(p ∨ F) ≡ p
23
Q
Domination laws
A
(p ∨ T) ≡ T
(p ∧ F) ≡ F
24
Q
Subject & Predicate
A
“x is greater than 3” has 2 parts:
- The first part, x, is the subject of the statement.
- The second part, the predicate, is greater than 3 refers to a property that the subject of the statement may or may not have.
25
# Define
Universal Quantification
The **universal quantification** of `P(x)` is the statement:
`P(x)` **for all** values of `x` in the domain of `x`
- The notation `∀x P(x)` denotes the universal quantification of `P(x)`.
- The symbol `∀` is called the universal quantifier.
26
# Define
Existential Quantification
The existential quantification of `P(x)` is the statement:
There exists an element `x` in the domain such that `P(x)`
- The notation `∃x P(x)` denotes the existential quantification of `P(x)`.
- The symbol `∃` is called the existential quantifier.
27
# Define
Set
A set is an unordered collection of objects, called elements or members of the set.
A set is said to **contain** its elements.
`x ∈ A` denotes that `x` is an element of the set `A`.
`x ∈/ A` denotes that `x` is not an element of the set `A`.
28
3 Fundamental Set Properties
- All elements in a set are distinct. (i.e. a value is either an element of a set, or it is not. It cannot occur multiple times in the set.)
- The elements of a set do not come with a fixed ordering.
- The same set can be described in different ways {1, 2, 3} = {1, 2, 2, 3} = {3, 1, 2} = {i | i integer, 0 < i ≤ 3}
29
6 Standard sets of numbers
N := {0,1,2,3,···} set of natural numbers
Z := {0,1,−1,2,−2,3,−3,···} set of integers
Z>0 := {1, 2, 3, · · · } set of positive natural numbers
Q := {ab | a,b ∈ Z,b ̸= 0} set of rational numbers
R := the set of real numbers
R>0 := the set of positive real numbers
30
# Definition
Set equality
Two sets *A* and *B* are **equal** (**A=B**), if they contain the same elements, i.e.
* every x ∈ A satisfies x ∈ B and
* every x ∈ B satisfies x ∈ A.
31
# Definition
Empty set
The **empty set** is the (uniquely determined) set that contains no element(s).
We denote it by ∅, or by {}.
32
# Definition
Singleton set
A set with exactly one element.
33
# Definition
Finite set
A set is called finite, if it contains only finitely many elements, i.e. if there is a number `n ∈ N`, such that the set contains exactly `n` elements.
34
# Define
Cardinality
The cardinality of a set *M* is:
|M|: {
The number if elements in M, if M is finite,
∞, otherwise
35
# Define
Subset
A is a subset of B
(short: A⊆B),
if every element of A is also an element of B.
36
# Define
Proper Subset
A is a proper subset of B (short: A ⊊ B), if:
`A ⊆ B` and `A ≠ B`.
37
Superset
A is a superset of B (short: `A ⊇ B`), if `B ⊆ A`
38
Proper Superset
A is a proper superset of B
(short: `A ⊋ B`), if
`A ⊇ B` and `A ≠ B`.
39
# Define
Power set
The **power set** of a set `S` is the set of all subsets of `S`:
`P(S)` := `{ X |X ⊆ S}`
E.g. `P({a, b})` = `{ ∅, {a}, {b}, {a,b} }`
40
# Set operations
Intersection
`A ∩ B` := { `x : x ∈ A` and `x ∈ B` }
41
# Set operations
Union
`A ∪ B` := { `x : x ∈ A` or `x ∈ B` }
42
# Set operations
Difference
`A − B` := { `x ∈ A` : `x ∉ B` }
43
# Set operations
Symmetric difference
`A ⊕ B` := `(A−B) ∪ (B−A)`
44
Complement of a set
We would like the **complement** of a set `A`, short `A^`, to be the set of all elements, that do not belong to `A`.
`A^` := { `x` : `x ∉ A`},
45
# Sets
Idempotent laws
`A ∩ A` = `A` and `A ∪ A` = `A`
46
# Sets
Commutative laws
`A ∩ B` = `B ∩ A` and `A ∪ B` = `B ∪ A`
47
# Sets
Associative laws
`A ∩ (B ∩ C)` = `(A ∩ B) ∩ C`
and
`A ∪ (B ∪ C)` = `(A ∪ B) ∪ C`
48
# Sets
Absorption laws
`A ∩ (A ∪ B)` = `A`
and
`A ∪ (A ∩ B)` = `A`
49
# Sets
Distributive laws
`A ∩ (B ∪ C)` = `(A ∩ B) ∪ (A ∩ C)`
and
`A ∪ (B ∩ C)` = `(A ∪ B) ∩ (A ∪ C)`
50
# Sets
Double Complement
(`A^`)`^` = `A`
51
De Morgan's laws
(sets)
`(A ∩ B)^` = `A^ ∪ B^`
and
`(A ∪ B)^` =`A^ ∩ B^`
52
Inverse laws
`A ∩ A^` = `∅` and `A ∪ A^` = `U`
53
Identity laws
`A ∩ U` = `A` and `A ∪ ∅` = `A`
54
Cartesian product of two sets
`A x B` is the set of ordered pairs `(a, b)`, where `a` belongs to `A` and `b` belongs to `B`.
`A×B` := { (a,b) | `a ∈ A` and `b ∈ B` }
55
Symmetric relation
A relation *R* on set `A` is called **symmetric**, if `(a, b) ∈ R` implies `(b, a) ∈ R` for all `a, b ∈ A`
56
Antisymmetric relation
A relation *R* on a set `A` such that for all `a, b ∈ A`, if `(a, b) ∈ R` and `(b, a) ∈ R`, then `a=b` is called **antisymmetric**.
57
# Properties of relations
transitive
A relation *R* on a set `A` is called **transitive** if whenever `(a, b) ∈ R` and `(b,c) ∈ R`, then `(a,c) ∈ R`, for all `a,b,c ∈ A`.
58
# Properties of relations
total
A relation *R* on a set `A` is called total if all `a,b ∈ A` satisfy: `(a,b) ∈ R` or `(b, a) ∈ R`.
59
# Definition
Function
Let `A` and `B` be nonempty sets.
A **function `f` from `A` to `B`** is an assignment of **exactly** one element of `B` to each element of `A`.
`f : A → B`
60
Domain & Codomain
Let `f : A → B` be a function.
The set `A` is called the **domain** of the function `f`.
`B` is called the **codomain** of the function `f`.
61
Image & Preimage
If `f(a) = b`, we say that:
`b` is the **image** of `a`,
and `a` is the **preimage** of `b`.
62
# Definition
Injective function
A function `f : A → B` is said to be injective (or one-to-one), if and only if `f(a) = f(b)` implies that `a = b` **for all `a` and `b`** in the domain `A` of `f`.
63
# Definition
Surjective function
A function `f : A → B` is said to be **surjective** (or onto), if and only if for every element `b ∈ B` there is an element `a ∈ A` with `f(a) = b`.
64
# Definition
Bijective function
A function `f` is said to be **bijective** (or a one-to-one correspondence), if it is both injective and surjective.
We also say that the function is a **bijection**.
65
# Definition
Inverse function
Let `A, B` be sets and `f ⊆ A × B` be a function.
If the relation
`{(b, a) | (a, b) ∈ f } ⊆ B × A` is a function from `B` to `A`, then it is called the **inverse function** of `f`.
In this case, `f` is called **invertible**.
66
# Definition
theorem
A theorem is a statement that can be shown to be true.
A theorem consists of assumptions (premises) and a conclusion.
Assumptions and a
conclusion are statements such that the following is true:
**If all assumptions are satisfied, then the conclusion must be true.**
67
# Definition
proof
The **proof** of a theorem has to establish that the statement of the theorem is true.
The proof can use:
* the assumptions of the theorem
* definitions, known facts and known theorems
* statements, that are proved within the proof or have already been proved elsewhere
* logical rules of inference.
68
# Definition
lemma
A less important theorem that is helpful in the proof of other results is often called a lemma.
69
# Definition
corollary
A corollary is a theorem that follows immediately from a theorem or proposition that has been proved.
70
# Definition
conjecture
A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, but a proof is still missing.
71
Proof by contraposition
In a **proof by contraposition**, a statement of the form `p → q` is proved by showing `¬q → ¬p`.
This is correct, because the statements are logically equivalent.
72
Propose-and-reject algorithm
## Footnote
Gale-Shapley 1962
Initialize each person to be free;
**while** some man is free and has not proposed to every woman **do**
* choose such a man `m`;
* `w` ← 1st woman on `m`’s list to whom `m` has not yet proposed;
* if `w` is free then
* assign `m` to `w`;
* else if `w` prefers `m` to her fiance `m′` **then**
* assign `m` to `w`, and `m′` to be free;
* else
* `w` rejects `m`;
73
Equivalence relation
A binary relation that is:
- Reflexive
- Transitive
- Symmetric
74
Equivalence class
Let `E` be an equivalence relation over a set `V`.
For every `v ∈ V` we let:
`[v]E` := {`v' ∈ V` | `(v, v') ∈ E` }
denote the **equivalence class of** `v` with respect to `E`.
A set `W ⊆ V` is an **equivalence class** (of `E`) if there exists an element `v ∈ V` with `W = [v]E`.
The element `v` is then called a **representative** of its equivalence class `W`.
75
Preorder
Let `E` be a binary relation over a set `V`.
`E` is a **preorder**, if e is:
- Reflexive, and
- Transitive
76
Partial order
Let `E` be a binary relation over a set `V`.
`E` is a **partial order**, if `E` is:
- **reflexive**,
- **transitive**, and
- **antisymmetric**
77
Linear order
or
Total order
Let `E` be a binary relation over a set `V`.
`E` is a **linear order** or **total order**, if `E` is:
- **reflexive**,
- **transitive**,
- **antisymmetric**, and
- **total**.
78
Example of a **linear order**
≤ is a **linear order** on `N` (and `Z`, `Q` and `R`).
≥ is a **linear order** on `N` (and `Z`, `Q` and `R`).
79
Example of a **partial order**
For every set `M`, the relations `⊆` and `⊇` are **partial orders** on the power set `P(M)`.
80
Real-valued / integer-valued function
A function is called **real-valued** if its codomain is the set of real numbers.
It is called **integer-valued** if its codomain is the set of integers.
81
Identity function
The **identity function** on `A` is the function `A→A`, given by `ιA(x)` := `x` for all `x∈A`
## Footnote
ι is a greek letter, pronounced 'iota'
82
Direct proof
In a **direct proof**, the statement is proven 'directly', i.e. without any detours.
This is often by a chain of implications, leading us from the assumptions of the theorem to its conclusion;
or by a chain of equalities,
or a chain of equivalences.
83
**Proof by contradiction**
Suppose we want to show a statement of the form `p` is true.
Suppose we find a contradiction `q` such that `~p→q`.
Because `q` is false, but `~p→q` is true, we can conclude that `~p` is false, which means `p` is true.
84
Proof by mathematical induction
**By `N` we denote the set of all natural numbers.
Let `P(n)` be a statement about a natural number `n`.
The aim is to prove that statement `P(n)` is true **for every** `n ∈ N`.
1. In the first step, we prove that the statement `P(n)` is true for `n=0`. We call this step **basis of the induction**.
2. In a second step, we prove for every natural number `n∈N`: **If** statement `P(n)` is true, then statement `P(n+1)` is true as well. This step is called the **inductive step**.
