Memorise!

Question 1

Truth table Implication

Answer 1

A | B | Output
0 0 1
0 1 1
1 0 0
1 1 1

Question 2

Truth table bi-implication

Answer 2

A | B | Output
0 0 1
0 1 0
1 0 0
1 1 1

Question 3

Simplification of Implication

Answer 3

a => b = not(a)Vb

Question 4

Simplification of Bi-Implication

Answer 4

a <=> b = (a=>b) n (b=>a)

Question 5

Tautology

Answer 5

Proposition that is always true

Question 6

Contradiction

Answer 6

Proposition that is always false

Question 7

Contingency

Answer 7

Proposition that is not a tautology or contradiction

Question 8

Definition of Consequence

Answer 8

Q is a logical consequence of D if for every “output value”, if D evaluates to True, then Q evaluates to True
D|= Q

Question 9

Definition of Comparable

Answer 9

If Q is a logical consequence of P, or P is a logical consequence of Q, then they are comparable

Question 10

Definition of Strongness & Weakness

Answer 10

False is strongest, True is weakest
P is a logical consequence of Q = P is stronger then Q, Q is weaker then P

Question 11

De Morgan’s law for Quantifiers

Answer 11

not Ax[P:Q] = Ex[P: not q]
not Ex[P:Q] = Ax[P:not q]

Question 12

Introduction and Elimination Rules for Conjunction, Disjunction, Implication, Bi-implication, Negation, Contradiction, Double Negation, Contraposition, Case Distinction

Answer 12

write it!

Question 13

Introduction and Elimination Rules for Universal and Existentisal Quantification

Answer 13

5 in total!
(universal intro &elim)
(existensial intro &elim)
(normal existensial intro)

Question 14

Property and Definition Rules

Answer 14

Property = Intro, Definition = Elim

Question 15

Property and Definition Rules for =, n, u, complement, difference, empty set, subset, Powerset,

Answer 15

write it!

Question 16

Ordered Pair

Answer 16

Two elements with fixed ordering (a,b), a is the first and b is the second

Question 17

Property of Ordered Pair

Answer 17

(a,b) = (a’,b’)
logically equivalent to
(a=a’) n (b=b’)

Question 18

Cartesian Product

Answer 18

The set of all ordered pairs (a,b) with a exists in A and b exists in B

Question 19

Property of Cartesian Product

Answer 19

(a,b) exists in AxB
logically equivalent to
a exists in A n b exists in B

Question 20

Definition of a Relation

Answer 20

A set of ordered pairs

Question 21

Cartesian Graph

Answer 21

A graph that corresponds to an ordered pair that shows which are related

Question 22

Arrow Graph

Answer 22

Draw it!

Question 23

Reflexive Property Definition

Answer 23

Ax[x in A: xRx]

Question 24

Symmetry Property Definition

Answer 24

Ax,y[x,y in A: xRy => yRx]

Question 25

Transitivity Property Definition

Answer 25

Ax,y,z[x,y,z in A: xRy n yRz => xRz]

Question 26

Equivalence Relation

Answer 26

A relation that is reflexive, symmetric and transitive

Question 27

Equivalence Class

Answer 27

Partition of the set into classes that are related

Question 28

Mapping

Answer 28

A relation from Set A to Set B that relates every element x in A to a element y in B

Question 29

Property of Mapping

Answer 29

Ax[x in A: Ey^1[y in B: F(x) = y]]

Question 30

Composite Mapping

Answer 30

research cases of injection,surjection and bijection in this context

Question 31

Image

Answer 31

A subset of set A, A', that is mapped to set B

Question 32

Property of Image

Answer 32

1. F(x) in F(A') is a logical consequence of x in A' 2. y in F(A') is logically equivalent to Ex[x in A':F(x) = y]

Question 33

Source

Answer 33

A subset of Set B, B', that is related to a subset of A, A' A' is the source of B' with respect to F

Question 34

Property of Source

Answer 34

x in F<-(B') = F(x) in B'

Question 35

Surjection

Answer 35

For every element in the codomain, there is AT LEAST one element in the domain that maps to it

Question 36

Injection

Answer 36

For every element in the codomain, there is AT MOST one element in the domain that maps to it

Question 37

Property of Surjection

Answer 37

Ay[y in B: Ex[x in A: F(x) = y]]

Question 38

Property of Injection

Answer 38

Ax1,x2[x1,x2 in A: F(x1) = F(x2) => x1=x2]

Question 39

Bijection

Answer 39

For every element in the codomain, there is EXACTLY one element in the domain that maps to it

Question 40

Property of Bijection

Answer 40

Ay[y in B: Ex^1[x in a, F(x) = y]]

Question 41

Inverse

Answer 41

The opposite of a mapping from F: A->B its F^-1: B -> A such that for all x in A and y in B, F^-1(y) = x, if F(x) = y

Question 42

Property of Inverse

Answer 42

F^-1(y) = x is logically equivalent to F(x) = y

Question 43

Property of Induction

Answer 43

write it

Question 44

Property of strong induction

Answer 44

write it

Question 45

Proving Reflexivity, Symmetry and Transitivity

Question 46

Ordering

Answer 46

A relation on a set that organises elements of a set according to rules

Question 47

Reflexive Partial Ordering

Answer 47

1. Reflexive 2. Anti-Symmetric 3. Transitive

Question 48

Irreflexive Partial Ordering

Answer 48

1. Irreflexive 2. Strictly Anti-Symmetric 3. Transitive

Question 49

Irreflexive Property

Answer 49

Ax[x in A: not(xRx)]

Question 50

Quasi-Ordering

Answer 50

A structure such that R is reflexive and transitive

Question 51

Structure

Answer 51

A set with an ordering, such as A = set R = ordering

Question 52

Anti Symmetry Property

Answer 52

Ax,y[x,y in A: (xRy n yRx) => x=y]

Question 53

Strictly Anti Symmetric Property

Answer 53

Ax,y[x,y in A: not(xRy n yRx)]

Question 54

Hasse Diagram

Answer 54

Shows successors/predecessors and max/min of a structure

Question 55

Maximum

Answer 55

There is an element for which everything is below it Reflexive Ax[x in A': mRx => m=x] Irreflexive: Ax[x in A': not(mRx)]

Question 56

Minimum

Answer 56

There is an element for which everything is above it Reflexive Ax[x in A': xRm => x=m] Irreflexive Ax[x in A': not (xRm)]

Question 57

Maximal Element

Answer 57

There is nothing above it Reflexive Ax[x in A': xRm] Irreflexive Ax[x in A' n x != m : xRm]

Question 58

Minimal Element

Answer 58

There is nothing below it

Question 59

Direct Successors

Answer 59

Y is a direct successor of X IF: Reflexive: xRy n zRy n notEz(z in A n z!=x n z!=y: xRz n zRy] Irreflexive: xRy n notEz[z in A: xRz n zRy]

Question 60

Lexicographic Orderings

Answer 60

Given two ordered sets, and , the lexicographic ordering is determined by: (a1,b1) S3 (a2,b2) if a1 S1 a2 V (a1=a2 n b1 S2 b2) can be reflexive or irreflexive ALL lexicographic orderings are transitive

Question 61

Linear (Total) Orderings

Answer 61

1. Reflexive 2. Anti-Symmetric 3. Transitive 4. Comparability (for every pair of elements a,b in a set, either aRb or bRa)