CS 245 - WINTER 2021
ASSIGNMENT 1
SHAI BEN-DAVID
(1) Define the set of all rooted trees inductively as follows:
• The universe set, X, is the set of all rooted finite graphs (a rooted finite graph G =
(V, r, E) consists of a finite set of vertices V and a set E of edges, which are pairs of
elements of V and r is a member of V called the root).
• The core set A is the graph that consists of s single vertex and no edges and this vertex
is also the root.
• The set of operations, P , consists of two operations p1 is ”Connect by a common
root” and p2 is ”Attach to a vertex”. Where p1(G1, G2) takes two rooted graphs
G1 = (V1, rr, E1), G2 = (V2, r2, E2), and construct a graph G = (V, r, E), where, for a
new vertex v0, V = V1 ∪ V2 ∪ {v0}, r = v0 and E = E1 ∪ E2 ∪ {(v0, r1), (v0, r2)}, and
p2(G1, G2) takes two rooted graphs G1 = (V1, r1, E1), G2 = (V2, r2, E2), and construct
a graph G = (V, r, E), where for some vertex v ∈ V1 we ”glue” the root of G2 to that
vertex. Namely, V = V1 ∪V2 \ {r2}, E = E1 ∪E′2, where E′2 is the same as the original
E2 except that in every edge containing r2 (edge of the form (r2, u)) the vertex r2 is
replaced by v (so the edge (r2, U) is replaced by a new edge (v, u)). Finally the root
r = r1.
Prove by structural induction that in every rooted tree in this I(X,A,P ), the number of
vertices |V | equals the number of edges |E| plus 1. (assume that all the unions are disjoint
unions - namely if a vertex appears in both V1 and V2 the union contains two different
copies of that vertex).
(2) We proved in the lectures several properties that hold for all WFF’s: that every WFF is
either an atomic formula or starts with a left bracket. That in every WFF the number of
left brackets equals the number of right brackets, and that every proper initial segment of
a WFF contains more left brackets that right brackets.
Consider the following sequence of symbols ((p ∨ q) ∧ ((¬p)))
(a) Prove that this sequence satisfies all the properties listed above.
(b) Prove that this sequence is not a WFF.
(3) For each of the following claims determine if it is correct or not. If it is, prove it, if it is
not, provide a counter example.
(a) If both α and β are propositional tautologies then so is (α ∨ (¬β)).
(b) If both α and β are satisfiable then so is (α ∨ (¬β)).
(c) If both α and β are satisfiable then so is (α ∧ (¬β)).
(d) If both α and β are satisfiable then so is (α→ (¬β)).
(e) If both α and β are satisfiable then so is ((¬α)→ β).
(f) If each of (α ∧ β), (α ∧ γ), (γ ∧ β) is satisfiable then so is ((α ∧ β) ∧ γ).
(g) if a truth assignment (a1, . . . an) (where each ai is either T or F ) satisfies a propositional
formula α then, the flipped truth assignment (b1, . . . bn) (where for every i, if ai = T
then bi = F and if ai = F then bi = T ) satisfies the formula (¬α).
1

欢迎咨询51作业君