Core logic homework 1 Mon Sep 14 20:06:35 CEST 2009 Andreas van Cranenburgh 0440949. Exercise 1 Smith gives a different interpretation for vague predicates than standard fuzzy semantics does. His conceptual model consists of the following elements: world: vagueness, eg., of the term 'bald' in actual usage model: definition of logic of vague predicates, eg., 'bald' in the blurry semantics of Smith's paper experiment: thought experiments, comparison with other models These are linked by: world -> model: intuitions about how conditionals with eg., baldness work. in this case eg., that consequents from shaky antecedents will get shakier, if the degree of truth is taken as an approximation. model -> experiment: predictions the model makes, namely that the model works better in everyday reasoning with vague terms experiment - world: results, example cases where model does or does not work well compared to standard fuzzy semantics. Exercise 2 It is not really possible to give truth conditions for these sentence fragments, because they only quantify, but if we suppose that there is some ellipsis [...] it might run as follows: (X, E, i) |= "everyone except for John [...]" if and only if for all y in X where y \= John [...] (X, E, i) |= "twice [...]" if and only if there exists an x in E, [...] holds for x there exists a z in E where x \= z, and [...] holds for z These truth conditions can be combined in two different ways to account for the readings. Example situation 1: X = {John, Sue, Mary} (abbreviated as J, S, M) E = {0, 1, 2} i = {0 -> , 1 -> , 2 -> } In this situation the first reading works when we use the truth conditions as given: (X, E, i) |= "everyone except for John sees Sue twice" if and only if for all y in X there exists an x in E such that i(x) = and if x \= John then there exists a z in E where z \= x, such that i(z) = Example situation 2: X = {John, Sue, Mary} (abbreviated as J, S, M) E = {0, 1} i = {0 -> , 1 -> } Here the sentence only holds on the second reading where John doesn't see Sue at all, and when we re-arrange the existential quantifiers and the seeing-event to be next to each other,: (X, E, i) |= "everyone except for John sees Sue twice" if and only if for all y in X where y \= John there exists an x and a z in E, where x \= z, and i(x) = and i(z) = The two readings of the example sentence occur because of scope ambiguity of the word "except", the part x \= John can restrict both existential quantifiers (second reading), or only the second existential quantifier (first reading). Exercise 3 We consider the set P of people, B of black sheep, and W of white sheep. They have no elements in common. The union of B & W is the set S of sheep. There is an owner relation O which is a subset of the cartesian product of P & S, such that for a given , there is no where o \= o'. Birth cycles extend the model by adding new sheep and new owner relations. S0 is the set of potential parents, S1 their children, such that: | S0 | = 2 * | S1 | if | S0 | is even | S0 | = 2 * | S1 | + 1 otherwise The parents and children are related by a subset of the cartesian product of S0 and S1, such that for any given in this subset: there is no where x \= x' there is no where y \= y' if x is in B then y is in B if x is in W then y is in W if is in O then is in O Now the statement: there is no sheperd who only owns white sheep, a.k.a.: statement A: there is no in O such that for all z in S where in O it holds that z is in W We want to prove that if statement A holds before a birth cycle, it also holds after a birth cycle. Suppose statement A holds. A birth cycle occurs and new elements are added to B, W and, O. Because only new elements are added and none are ever removed (no sheep die), the model is monotonic. Thus, B, W, and O from before the cycle are all proper subsets of B, W, and O from after the cycle. Hence property A must still hold after the transition. Exercise 4 The dictionary server maintains two sets E and D, with the requests for english-to-dutch and dutch-to-english respectively, in the form of pairs where n is the time of arrival in seconds, and m is the request number which is set to 1 at the beginning of every second. There are three modes, e, d, and w, where w is the waiting mode to switch between e and d. Every second t, the following happens: in mode e: repeat 15 times while E is non-empty: take min(E) out of E in mode d: repeat 15 times while D is non-empty: take min(D) out of D otherwise: do nothing The protocol to switch modes can be defined like this: mode(t) = e if t mod 12 <= 3 d if 7 <= s mod 12 <= 9 w otherwise We assume the worst case scenario of 5 requests per second being added to E, and 8 requests per second being added to D. With this protocol a counterexample of the statement can be found. At 72 seconds, there is a request made in the 41st second that is still waiting, as shown by a simulation I programmed. We can estimate the number of requests waiting using a continuous formula: e(t) = 8t - 15 * 3/12 * t d(t) = 5t - 15 * 3/12 * t At the end of each cycle (t mod 12 equals 0), this estimate will be correct; however, at other points it is an estimate because it spreads the handling of requests evenly over the rest of the interval, instead of being discontinuous like the mode(t) function. For our purposes this can be ignored. Here 8t is the number of requests pouring in, minus the number that can be handled: 15 per second, however only 3/12 of the time it's in the right mode. And 15 times 3/12 equals 3+3/4, which is the average number of requests handled per second. Thus it is easy to see that this protocol will receive requests faster than they are being handled, and must fail eventually. State differently, the number of requests coming in per cycle is: E: 5 * 12 = 60 D: 8 * 12 = 96 If each mode handles requests for 3 seconds as in our protocol then: 3 * 15 = 45 requests per seconds will be handled. Again, the incoming requests clearly outstrip the capacity of the server.