Brainscape's Knowledge GenomeTM

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


See full index

Computer science > Logic for Computer science > Flashcards

Logic for Computer science Flashcards

1
Q

Injective function

A

each value in the codomain
B that is actually mapped to by
𝑓 is associated with exactly one unique value in the domain A. if F(x1) = F(x2) then x1 = x2

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

Surjective Function

A

All elements in codomain are mapped by element in domain

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

Bijective function

A

All elements in domain is uniquely mapped to element in codmain. Every element in codomain is mapped by one element in domain.

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

In context of set equality are these sets equal {1,2,3} and {1,2,2,3}

A

Yes

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

S Subset T meaning

A

all element x in s also occur in t

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

S proper subset T meaning

A

S is subset of T and set s and t are not equal.

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

Power set of S meaning P(S)

A

set of all subsets of S
eg. P({1,2}) = {0,{1},{2},{1,2})

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

if S is finite what is P(S)

A

2^(Cardinality of S)

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

Cartesian product S X T

A

all possible combos,
S={1} T= {a,b}
S X T = {1,a} {1,b}

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

Criteria for Partial order

A

reflexive, transitive, anti- symmetric

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

reflexive

A

all x in a set, the element x is in relation with itself, xRx

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

transitive

A

for all elements x,y,z in a set, if xRy and yRz then xRz is mandatory

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

anti-symmetirc

A

for all x,y in a set, if we have xRy and yRx then (x1,y1) = (x2,y2)

In otherwords, if Rxy and x != y then we cannot have yRx

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

Total order

A

Is a partial order that is also connex-

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

connex

A

for every element x,y in a set, we need at least xRy or yRx

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

equivilance relation

A

needs to be reflexive, transitive and also symmetric

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

symmetric

A

for all x,y in a set if xRy then yRx is mandatory

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

When drawing self-complementary isomorphisim how many relations should you use

A

n^2/2

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

How to conduct structural induction

A

ensure it works for base cases first, then work for recursive cases

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

when defining an isomorphism, what to look at first

A

constants

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

Base rules for PL

A

constants 0 and 1
Variables Vi in PL

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

Recursvie rules

A

if ϕ ,Ψ in PL Then:
¬ϕ Ɛ PL (negation)
ϕ V Ψ ( disjunction) (and)
ϕ ^ Ψ ( conjunction) (or)
ϕ -> Ψ ( implication) 1 if phi = 0 or if psi = 1, 0 otherwise.
ϕ <–> Ψ( bi implication) 1 if phi = psi, 0 otherwise

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

satisfiable meaning in PL

A

phi is satosfiable if at least one assignment satisfises phi
(phi) = 1

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

contradiction, unsatisfiable meaning

A

phi = 0 for all assignemnets for phi

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

tautology meaning

A

phi is tautologoy if every assignemnet satisfises phi
phi = 1 for all assignements

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

well structured truth table

A

varaible columns sorted alphabetically in ascending order and indicies in ascending orders
rows from top to bottom are numbers 0 to 2^k-1.

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

semantic implication
how would you prove if two equations are semantical implied

A

phi implies(|=) psi
if phi = 1 then psi = 1

truth table x and y
0 0
0 1
1 0
1 1
then use these inputs on each of the pl formulas

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

Absorption equivilance

A

(Phi ^ (Phi V Psi)) == phi
(Phi V (Phi ^ Psi)) == phi

29
Q

Idempotency equivlance

A

Phi V/^ Phi == Phi

30
Q

Commutativity equivalance

A

(Phi ^ Psi) == (Psi ^ Phi)

31
Q

Implication elimination

A

(Phi –> Psi) = (¬Phi V Psi)

32
Q

Contraposition

A

(Phi –> Psi) = (¬Psi –> ¬Phi)

33
Q

Bi-implication elimination

A

(Phi <–> Psi) = ((Phi –> Psi) ^ (Psi –> Phi))

34
Q

Associativity

A

((Phi ^ Psi) ^X) = (Phi ^(Psi ^ x))

35
Q

Distributivity

A

(Phi ^(Psi V X)) = ((Phi ^ Psi) V (Phi ^ X))

36
Q

What does functionally complete mean

A

only using operators in the set to express negation, conjunction/and/or disjunction.

37
Q

Varaint 1 for PL

A

Base rule: Vi in PL
recursive rule: if phi, psi in PL
¬Phi in Pl, Phi V Psi in pl, Phi ^ psi in pl

38
Q

Variant 2

A

Base rule: 0 in PL, V In pl
Recursive rule: if Phi, Psi in PL
Phi –> Psi in PL

39
Q

Nand in PL

A

–
^ Phi Nand Psi == ¬(Phi ^ Psi)

40
Q

prove nand is functionally complete

A
41
Q

E x : F(x,x) = y:
what is the free variable and what does that mean

A

y is free variable so u describe some property for y

42
Q

Negation normal form

A

phi does not contain —>(implication) or <—>(bi implication) and only negation applied to atoms

43
Q

how to get these into NNF
(phi –> phi)
phi <—> phi2
¬¬phi
¬(phi ^ phi)
¬∃x : phi
¬∀x: phi

A

¬phi V Phi
((Phi ^ Phi2) V (¬Phi ^ ¬Phi2))
phi
(¬phi V ¬phi2)
∀x : ¬phi
∃x : ¬phi

44
Q

satisfiable in Fo

A

Phi is satisfiable if Interpretation |= phi holds for at least one interpretation

45
Q

Contradiction in Fo

A

phi is contradiction if there is no interpretation for it to be true

46
Q

tautology in FO

A

if Interpretaiton |= phi holds for every interpretation

47
Q

Evaluation game rules

A

Trudy wins if (A, α) |= φ,
Noam wins if (A, α) ̸|= φ.
If φ = (φ1 ∨ φ2), Trudy picks i ∈ {1, 2},
and the game continues as Eval(A, α, φi).
If φ = (φ1 ∧ φ2), Noam picks i ∈ {1, 2},
and the game continues as Eval(A, α, φi).
If φ = ∃x: ψ, Trudy picks a ∈ A, and
the game continues as Eval(A, αx7→a, ψ).
If φ = ∀x: ψ, Noam picks a ∈ A, and
the game continues as Eval(A, αx7→a, ψ).

48
Q

Symmetric meaning

A

If F^A represents a friendship relation on a social network, symmetry means “if 𝑥 is friends with 𝑦, then 𝑦 is friends with x.”

49
Q

Automorphism

A

Isomorphism from a structure a to itself

50
Q

All animals say meow for database and relations topic
Which animals say at least 2 different things

A

φ(x) = Says(x,”meow”)
φ(x) =∃y:∃z(Says(x,y) ^ Says(x,z) ^ x!= z)

51
Q

Are there two databases 𝒜vod and ℬvod such that 𝒜vod ≠ ℬvod and 𝒜vod Isomorphic to ℬvod

A

Such structures cannot exist: Recall that σvod contains a constant symbol ’c’ for every possible value c in the database

if h is an isomorphism from 𝒜vod to ℬvod, it needs to have
h(c) = c for every element c of the universe. means that 𝒜vod = ℬvod

52
Q

purely relational meaning

A

contains neither function symbols nor constants

53
Q

what is A|s

A

Restriction of A to s

54
Q

Partial isomorphism

A

a partial function h from a to b is a partial isomorphism if h is an isomorhpsim from A|domain(h) to B|img(h). idek.

55
Q

quantifier Rank rules

A

qr(phi) = 0 if phi is atomic
ar(phi) = qr(phi1) if phi = ¬phi1
qr(phi) = max{qr(phi1),qr(phi2)} if phi = (phi1 o phi2) where o ={V,^,–>,<–>}
qr(phi) = qr(phi1) + 1 if phi =∃x:phi1 or phi =∀x:phi1

56
Q

Elementary equivilance

A

A|=phi if B|=phi then A=B
if Aisomporphic B then A = B

57
Q

EF-game rules

A

Seb represents not having partial isomorphism to win, Paris represents having Partial isomorphism to win.
- Seb picks first
if seb picks from A, than paris picks from b and vice versa and tuple created ( a,b)

58
Q

Countable Set

A

Set is countable if its finite or there is a bijection function from Natural numbers N to Set

59
Q

Bijection from N^3 to N
what does pack(subset3)(x1,x2,x3) become

A

pack(x1,pack(x2,x3))

60
Q

what does unpack(subset3)(n): (y1,y2,y3) simplify to.

A

y1 = π1(unpack(n))
y2 = π1(unpack(π2(unpack(n))))
y3 = π2(unpack(π2(unpack(n))))

61
Q

Uncountable infinity

A

any set where there is no bijection f : S–> P(S) (power set is set of all subsets)

62
Q

trick 1 to show uncountability

A

countable unions
let S = Ui from 1 to k
if Si are countable then S is countable

63
Q

trick 2

A

uncountable union
Set S = Ui 1 to k. If at least one Si is uncountable then S is uncountable

64
Q

trick 3

A

countable cross products
S = s1 x … sk
if all Si are countable, S is countable

65
Q

trick 4

A

Uncountable cross products
if all sets S1 to sk are non-empty and at least one Si is uncountable then S is uncountable

66
Q

(N∩P(N) What does this equal

A

empty set and its countable

67
Q

Reflexive closure (R^Ω)

A

R^Ω := R U {(x,x) | x E S}

68
Q

Transitiv closure

A

R^+ defined recursively
base rule : (x,y) E R^+ for all (x,y) E R
recursive rule : if (x,y) E R+ and (y,z) E R+, Then (x,z) E R+

69
Q

reflexive transitive closure

A

R^*
base case: R^Ω subset R^*
recursive rule : if (x,y) E R* and (y,z) E R* then (x,z) E R*
R* = R^Ω U R^+

Computer science (4 decks)

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