Unit 1: Logic

Question 1

Define

Proposition

Answer 1

A proposition is:

a declarative sentence
(a sentence that declares a fact),

that is either true or false, but not both.

Question 2

Define

Negation

Answer 2

The negation of p, denoted by ¬p, is the statement:

it is not the case that p

Question 3

Define

Conjunction

Answer 3

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.

Question 4

Define

Disjunction

Answer 4

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.

Question 5

Define

Implication

Answer 5

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

Question 6

Define

Converse

Answer 6

The proposition q → p is called the converse of p → q

Question 7

Define

Contrapositive

Answer 7

The contrapositive of p → q is:

¬q → ¬p

Question 8

Define

Biconditional statement

Answer 8

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.

Question 9

Precedence of logical operators

Answer 9

1. ¬
2. ∧ and ∨
3. → and ↔

Question 10

Define

(propositional) formula

Answer 10

A proposition or a compound proposition.

Question 11

Define

Truth assignment

Answer 11

A truth assignment to a propositional formula is an assignment of truth values to each of the propositions that occur in the formula.

Question 12

Define

Tautology

Answer 12

A formula that is true under every truth assignment.

Question 13

Define

Logical equivalence

Answer 13

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.

Question 14

Idempotent laws

Answer 14

(p ∧ p) ≡ p

(p ∨ p) ≡ p

Question 15

Commutative laws

Answer 15

(p ∧ q) ≡ (q ∧ p)

(p ∨ q) ≡ (q ∨ p)

Question 16

Associative laws
(logic)

Answer 16

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

Question 17

Absorption laws
(logic)

Answer 17

p ∧ (p ∨ q) ≡ p

p ∨ (p ∧ q) ≡ p

Question 18

Distributive laws

Answer 18

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Question 19

Double negation

Answer 19

¬¬p ≡ p

Question 20

De Morgan’s laws

Answer 20

¬(p ∧ q) ≡ (¬p ∨ ¬q)

¬(p ∨ q) ≡ (¬p ∧ ¬q)

Question 21

Tertium non datur

Answer 21

(p ∧ ¬p) ≡ F

(p ∨ ¬p) ≡ T

Question 22

Identity laws

Answer 22

(p ∧ T) ≡ p

(p ∨ F) ≡ p

Question 23

Domination laws

Answer 23

(p ∨ T) ≡ T

(p ∧ F) ≡ F

Question 24

Subject & Predicate

Answer 24

“x is greater than 3” has 2 parts:

1. The first part, x, is the subject of the statement.
2. The second part, the predicate, is greater than 3 refers to a property that the subject of the statement may or may not have.

Question 25

Define

Universal Quantification

Answer 25

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.

Question 26

Define

Existential Quantification

Answer 26

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.

Question 27

Define

Set

Answer 27

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.

Question 28

3 Fundamental Set Properties

Answer 28

• 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}

Question 29

6 Standard sets of numbers

Answer 29

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

Question 30

Definition

Set equality

Answer 30

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.

Question 31

Definition

Empty set

Answer 31

The empty set is the (uniquely determined) set that contains no element(s).

We denote it by ∅, or by {}.

Question 32

Definition

Singleton set

Answer 32

A set with exactly one element.

Question 33

Definition

Finite set

Answer 33

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.

Question 34

Define

Cardinality

Answer 34

The cardinality of a set M is:

|M|: {
The number if elements in M, if M is finite,
∞, otherwise

Question 35

Define

Subset

Answer 35

A is a subset of B
(short: A⊆B),
if every element of A is also an element of B.

Question 36

Define

Proper Subset

Answer 36

A is a proper subset of B (short: A ⊊ B), if:
A ⊆ B and A ≠ B.

Question 37

Superset

Answer 37

A is a superset of B (short: A ⊇ B), if B ⊆ A

Question 38

Proper Superset

Answer 38

A is a proper superset of B
(short: A ⊋ B), if

A ⊇ B and A ≠ B.

Question 39

Define

Power set

Answer 39

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} }

Question 40

Set operations

Intersection

Answer 40

A ∩ B := { x : x ∈ A and x ∈ B }

Question 41

Set operations

Union

Answer 41

A ∪ B := { x : x ∈ A or x ∈ B }

Question 42

Set operations

Difference

Answer 42

A − B := { x ∈ A : x ∉ B }

Question 43

Set operations

Symmetric difference

Answer 43

A ⊕ B := (A−B) ∪ (B−A)

Question 44

Complement of a set

Answer 44

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},

Question 45

Sets

Idempotent laws

Answer 45

A ∩ A = A and A ∪ A = A

Question 46

Sets

Commutative laws

Answer 46

A ∩ B = B ∩ A and A ∪ B = B ∪ A

Question 47

Sets

Associative laws

Answer 47

A ∩ (B ∩ C) = (A ∩ B) ∩ C
and
A ∪ (B ∪ C) = (A ∪ B) ∪ C

Question 48

Sets

Absorption laws

Answer 48

A ∩ (A ∪ B) = A
and
A ∪ (A ∩ B) = A

Question 49

Sets

Distributive laws

Answer 49

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
and
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

Question 50

Sets

Double Complement

Answer 50

(A^)^ = A

Question 51

De Morgan’s laws
(sets)

Answer 51

(A ∩ B)^ = A^ ∪ B^
and
(A ∪ B)^ =A^ ∩ B^

Question 52

Inverse laws

Answer 52

A ∩ A^ = ∅ and A ∪ A^ = U

Question 53

Identity laws

Answer 53

A ∩ U = A and A ∪ ∅ = A

Question 54

Cartesian product of two sets

Answer 54

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 }

Question 55

Symmetric relation

Answer 55

A relation R on set A is called symmetric, if (a, b) ∈ R implies (b, a) ∈ R for all a, b ∈ A

Question 56

Antisymmetric relation

Answer 56

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.

Question 57

Properties of relations

transitive

Answer 57

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.

Question 58

Properties of relations

total

Answer 58

A relation R on a set A is called total if all a,b ∈ A satisfy: (a,b) ∈ R or (b, a) ∈ R.

Question 59

Definition

Function

Answer 59

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

Question 60

Domain & Codomain

Answer 60

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.

Question 61

Image & Preimage

Answer 61

If f(a) = b, we say that:

b is the image of a,

and a is the preimage of b.

Question 62

Definition

Injective function

Answer 62

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.

Question 63

Definition

Surjective function

Answer 63

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.

Question 64

Definition

Bijective function

Answer 64

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.

Question 65

Definition

Inverse function

Answer 65

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.

Question 66

Definition

theorem

Answer 66

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.

Question 67

Definition

proof

Answer 67

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.

Question 68

Definition

lemma

Answer 68

A less important theorem that is helpful in the proof of other results is often called a lemma.

Question 69

Definition

corollary

Answer 69

A corollary is a theorem that follows immediately from a theorem or proposition that has been proved.

Question 70

Definition

conjecture

Answer 70

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.

Question 71

Proof by contraposition

Answer 71

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.

Question 72

Propose-and-reject algorithm

Gale-Shapley 1962

Answer 72

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;

Question 73

Equivalence relation

Answer 73

A binary relation that is:
- Reflexive
- Transitive
- Symmetric

Question 74

Equivalence class

Answer 74

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.

Question 75

Preorder

Answer 75

Let E be a binary relation over a set V.

E is a preorder, if e is:
- Reflexive, and
- Transitive

Question 76

Partial order

Answer 76

Let E be a binary relation over a set V.

E is a partial order, if E is:
- reflexive,
- transitive, and
- antisymmetric

Question 77

Linear order
or
Total order

Answer 77

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.

Question 78

Example of a linear order

Answer 78

≤ is a linear order on N (and Z, Q and R).

≥ is a linear order on N (and Z, Q and R).

Question 79

Example of a partial order

Answer 79

For every set M, the relations ⊆ and ⊇ are partial orders on the power set P(M).

Question 80

Real-valued / integer-valued function

Answer 80

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.

Question 81

Identity function

Answer 81

The identity function on A is the function A→A, given by ιA(x) := x for all x∈A

ι is a greek letter, pronounced ‘iota’

Question 82

Direct proof

Answer 82

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.

Question 83

Proof by contradiction

Answer 83

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.

Question 84

Proof by mathematical induction

Answer 84

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