Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Logic and Set Theory > Memorise! > Flashcards

Memorise! Flashcards

1
Q

Truth table Implication

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Truth table bi-implication

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Simplification of Implication

A

a => b = not(a)Vb

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Simplification of Bi-Implication

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Tautology

A

Proposition that is always true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Contradiction

A

Proposition that is always false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Contingency

A

Proposition that is not a tautology or contradiction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Definition of Consequence

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Definition of Comparable

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Definition of Strongness & Weakness

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

De Morgan’s law for Quantifiers

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

write it!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Introduction and Elimination Rules for Universal and Existentisal Quantification

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Property and Definition Rules

A

Property = Intro, Definition = Elim

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

write it!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Ordered Pair

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Property of Ordered Pair

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Cartesian Product

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Property of Cartesian Product

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Definition of a Relation

A

A set of ordered pairs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Cartesian Graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Arrow Graph

A

Draw it!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Reflexive Property Definition

A

Ax[x in A: xRx]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Symmetry Property Definition

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Transitivity Property Definition

A

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

26
Q

Equivalence Relation

A

A relation that is reflexive, symmetric and transitive

27
Q

Equivalence Class

A

Partition of the set into classes that are related

28
Q

Mapping

A

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

29
Q

Property of Mapping

A

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

30
Q

Composite Mapping

A

research cases of injection,surjection and bijection in this context

31
Q

Image

A

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

32
Q

Property of Image

A
  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]
33
Q

Source

A

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

34
Q

Property of Source

A

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

35
Q

Surjection

A

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

36
Q

Injection

A

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

37
Q

Property of Surjection

A

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

38
Q

Property of Injection

A

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

39
Q

Bijection

A

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

40
Q

Property of Bijection

A

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

41
Q

Inverse

A

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

42
Q

Property of Inverse

A

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

43
Q

Property of Induction

44
Q

Property of strong induction

45
Q

Proving Reflexivity, Symmetry and Transitivity

46
Q

Ordering

A

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

47
Q

Reflexive Partial Ordering

A
  1. Reflexive
  2. Anti-Symmetric
  3. Transitive
48
Q

Irreflexive Partial Ordering

A
  1. Irreflexive
  2. Strictly Anti-Symmetric
  3. Transitive
49
Q

Irreflexive Property

A

Ax[x in A: not(xRx)]

50
Q

Quasi-Ordering

A

A structure <A,R> such that R is reflexive and transitive

51
Q

Structure

A

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

52
Q

Anti Symmetry Property

A

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

53
Q

Strictly Anti Symmetric Property

A

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

54
Q

Hasse Diagram

A

Shows successors/predecessors and max/min of a structure

55
Q

Maximum

A

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)]

56
Q

Minimum

A

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)]

57
Q

Maximal Element

A

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

58
Q

Minimal Element

A

There is nothing below it

59
Q

Direct Successors

A

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]

60
Q

Lexicographic Orderings

A

Given two ordered sets, <A,S1> and <B,S2>, 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

61
Q

Linear (Total) Orderings

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

Logic and Set Theory (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions