Logic for Computer science Flashcards
Injective function
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
Surjective Function
All elements in codomain are mapped by element in domain
Bijective function
All elements in domain is uniquely mapped to element in codmain. Every element in codomain is mapped by one element in domain.
In context of set equality are these sets equal {1,2,3} and {1,2,2,3}
Yes
S Subset T meaning
all element x in s also occur in t
S proper subset T meaning
S is subset of T and set s and t are not equal.
Power set of S meaning P(S)
set of all subsets of S
eg. P({1,2}) = {0,{1},{2},{1,2})
if S is finite what is P(S)
2^(Cardinality of S)
Cartesian product S X T
all possible combos,
S={1} T= {a,b}
S X T = {1,a} {1,b}
Criteria for Partial order
reflexive, transitive, anti- symmetric
reflexive
all x in a set, the element x is in relation with itself, xRx
transitive
for all elements x,y,z in a set, if xRy and yRz then xRz is mandatory
anti-symmetirc
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
Total order
Is a partial order that is also connex-
connex
for every element x,y in a set, we need at least xRy or yRx
equivilance relation
needs to be reflexive, transitive and also symmetric
symmetric
for all x,y in a set if xRy then yRx is mandatory
When drawing self-complementary isomorphisim how many relations should you use
n^2/2
How to conduct structural induction
ensure it works for base cases first, then work for recursive cases
when defining an isomorphism, what to look at first
constants
Base rules for PL
constants 0 and 1
Variables Vi in PL
Recursvie rules
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
satisfiable meaning in PL
phi is satosfiable if at least one assignment satisfises phi
(phi) = 1
contradiction, unsatisfiable meaning
phi = 0 for all assignemnets for phi
tautology meaning
phi is tautologoy if every assignemnet satisfises phi
phi = 1 for all assignements
well structured truth table
varaible columns sorted alphabetically in ascending order and indicies in ascending orders
rows from top to bottom are numbers 0 to 2^k-1.
semantic implication
how would you prove if two equations are semantical implied
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
Absorption equivilance
(Phi ^ (Phi V Psi)) == phi
(Phi V (Phi ^ Psi)) == phi
Idempotency equivlance
Phi V/^ Phi == Phi
Commutativity equivalance
(Phi ^ Psi) == (Psi ^ Phi)
Implication elimination
(Phi –> Psi) = (¬Phi V Psi)
Contraposition
(Phi –> Psi) = (¬Psi –> ¬Phi)
Bi-implication elimination
(Phi <–> Psi) = ((Phi –> Psi) ^ (Psi –> Phi))
Associativity
((Phi ^ Psi) ^X) = (Phi ^(Psi ^ x))
Distributivity
(Phi ^(Psi V X)) = ((Phi ^ Psi) V (Phi ^ X))
What does functionally complete mean
only using operators in the set to express negation, conjunction/and/or disjunction.
Varaint 1 for PL
Base rule: Vi in PL
recursive rule: if phi, psi in PL
¬Phi in Pl, Phi V Psi in pl, Phi ^ psi in pl
Variant 2
Base rule: 0 in PL, V In pl
Recursive rule: if Phi, Psi in PL
Phi –> Psi in PL
Nand in PL
–
^ Phi Nand Psi == ¬(Phi ^ Psi)
prove nand is functionally complete
E x : F(x,x) = y:
what is the free variable and what does that mean
y is free variable so u describe some property for y
Negation normal form
phi does not contain —>(implication) or <—>(bi implication) and only negation applied to atoms
how to get these into NNF
(phi –> phi)
phi <—> phi2
¬¬phi
¬(phi ^ phi)
¬∃x : phi
¬∀x: phi
¬phi V Phi
((Phi ^ Phi2) V (¬Phi ^ ¬Phi2))
phi
(¬phi V ¬phi2)
∀x : ¬phi
∃x : ¬phi
satisfiable in Fo
Phi is satisfiable if Interpretation |= phi holds for at least one interpretation
Contradiction in Fo
phi is contradiction if there is no interpretation for it to be true
tautology in FO
if Interpretaiton |= phi holds for every interpretation
Evaluation game rules
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, ψ).
Symmetric meaning
If F^A represents a friendship relation on a social network, symmetry means “if 𝑥 is friends with 𝑦, then 𝑦 is friends with x.”
Automorphism
Isomorphism from a structure a to itself
All animals say meow for database and relations topic
Which animals say at least 2 different things
φ(x) = Says(x,”meow”)
φ(x) =∃y:∃z(Says(x,y) ^ Says(x,z) ^ x!= z)
Are there two databases 𝒜vod and ℬvod such that 𝒜vod ≠ ℬvod and 𝒜vod Isomorphic to ℬvod
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
purely relational meaning
contains neither function symbols nor constants
what is A|s
Restriction of A to s
Partial isomorphism
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.
quantifier Rank rules
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
Elementary equivilance
A|=phi if B|=phi then A=B
if Aisomporphic B then A = B
EF-game rules
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)
Countable Set
Set is countable if its finite or there is a bijection function from Natural numbers N to Set
Bijection from N^3 to N
what does pack(subset3)(x1,x2,x3) become
pack(x1,pack(x2,x3))
what does unpack(subset3)(n): (y1,y2,y3) simplify to.
y1 = π1(unpack(n))
y2 = π1(unpack(π2(unpack(n))))
y3 = π2(unpack(π2(unpack(n))))
Uncountable infinity
any set where there is no bijection f : S–> P(S) (power set is set of all subsets)
trick 1 to show uncountability
countable unions
let S = Ui from 1 to k
if Si are countable then S is countable
trick 2
uncountable union
Set S = Ui 1 to k. If at least one Si is uncountable then S is uncountable
trick 3
countable cross products
S = s1 x … sk
if all Si are countable, S is countable
trick 4
Uncountable cross products
if all sets S1 to sk are non-empty and at least one Si is uncountable then S is uncountable
(N∩P(N) What does this equal
empty set and its countable
Reflexive closure (R^Ω)
R^Ω := R U {(x,x) | x E S}
Transitiv closure
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+
reflexive transitive closure
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^+
