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作业君
