Logic for Computer science

Question 1

Injective function

Answer 1

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

Question 2

Surjective Function

Answer 2

All elements in codomain are mapped by element in domain

Question 3

Bijective function

Answer 3

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

Question 4

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

Answer 4

Yes

Question 5

S Subset T meaning

Answer 5

all element x in s also occur in t

Question 6

S proper subset T meaning

Answer 6

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

Question 7

Power set of S meaning P(S)

Answer 7

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

Question 8

if S is finite what is P(S)

Answer 8

2^(Cardinality of S)

Question 9

Cartesian product S X T

Answer 9

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

Question 10

Criteria for Partial order

Answer 10

reflexive, transitive, anti- symmetric

Question 11

reflexive

Answer 11

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

Question 12

transitive

Answer 12

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

Question 13

anti-symmetirc

Answer 13

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

Question 14

Total order

Answer 14

Is a partial order that is also connex-

Question 15

connex

Answer 15

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

Question 16

equivilance relation

Answer 16

needs to be reflexive, transitive and also symmetric

Question 17

symmetric

Answer 17

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

Question 18

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

Answer 18

n^2/2

Question 19

How to conduct structural induction

Answer 19

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

Question 20

when defining an isomorphism, what to look at first

Answer 20

constants

Question 21

Base rules for PL

Answer 21

constants 0 and 1
Variables Vi in PL

Question 22

Recursvie rules

Answer 22

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

Question 23

satisfiable meaning in PL

Answer 23

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

Question 24

contradiction, unsatisfiable meaning

Answer 24

phi = 0 for all assignemnets for phi

Question 25

tautology meaning

Answer 25

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

Question 26

well structured truth table

Answer 26

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

Question 27

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

Answer 27

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

Question 28

Absorption equivilance

Answer 28

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

Question 29

Idempotency equivlance

Answer 29

Phi V/^ Phi == Phi

Question 30

Commutativity equivalance

Answer 30

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

Question 31

Implication elimination

Answer 31

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

Question 32

Contraposition

Answer 32

(Phi --> Psi) = (¬Psi --> ¬Phi)

Question 33

Bi-implication elimination

Answer 33

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

Question 34

Associativity

Answer 34

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

Question 35

Distributivity

Answer 35

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

Question 36

What does functionally complete mean

Answer 36

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

Question 37

Varaint 1 for PL

Answer 37

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

Question 38

Variant 2

Answer 38

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

Question 39

Nand in PL

Answer 39

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

Question 40

prove nand is functionally complete

Question 41

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

Answer 41

y is free variable so u describe some property for y

Question 42

Negation normal form

Answer 42

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

Question 43

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

Answer 43

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

Question 44

satisfiable in Fo

Answer 44

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

Question 45

Contradiction in Fo

Answer 45

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

Question 46

tautology in FO

Answer 46

if Interpretaiton |= phi holds for every interpretation

Question 47

Evaluation game rules

Answer 47

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, ψ).

Question 48

Symmetric meaning

Answer 48

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

Question 49

Automorphism

Answer 49

Isomorphism from a structure a to itself

Question 50

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

Answer 50

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

Question 51

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

Answer 51

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

Question 52

purely relational meaning

Answer 52

contains neither function symbols nor constants

Question 53

what is A|s

Answer 53

Restriction of A to s

Question 54

Partial isomorphism

Answer 54

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.

Question 55

quantifier Rank rules

Answer 55

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

Question 56

Elementary equivilance

Answer 56

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

Question 57

EF-game rules

Answer 57

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)

Question 58

Countable Set

Answer 58

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

Question 59

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

Answer 59

pack(x1,pack(x2,x3))

Question 60

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

Answer 60

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

Question 61

Uncountable infinity

Answer 61

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

Question 62

trick 1 to show uncountability

Answer 62

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

Question 63

trick 2

Answer 63

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

Question 64

trick 3

Answer 64

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

Question 65

trick 4

Answer 65

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

Question 66

(N∩P(N) What does this equal

Answer 66

empty set and its countable

Question 67

Reflexive closure (R^Ω)

Answer 67

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

Question 68

Transitiv closure

Answer 68

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+

Question 69

reflexive transitive closure

Answer 69

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^+