EECS 2001C 2020F – Test 1
电气工程作业代写 I will give you two setting of the free variables. For each, you must decide whether this setting makes the sentence true or false.
| Marks | I | II | III |
| a) TM | 15 | 7 | 15 |
| b) Set | 7 电气工程作业代写 | 7 | 7 |
| c) f | 7 | 7 | 7 |
| d) Sat | 7 | 7 | 7 |
| 2) Art | 2 电气工程作业代写 | ||
| Total | 102 |
Keep your answers short and clear.
Do not repeat the question.
20% is given to any subquestion left blank (eg 3b).
1.LogicSentences: 电气工程作业代写
Hint: The good thing for you is that everything I want people to know about logic is outlined in
https://www.eecs.yorku.ca/~jeff/courses/1090/syllabus/
For each of these examples, you will must do each of the following. 电气工程作业代写
I You will either be producing a logic sentence from an English sentence or the other way around.
Give me a deep understanding of what the sentence means.
Hint: Here are some things that might help. (You don’t have to do all of these things.)
- Explain it from the inside out as done in
- Explain the game used to prove whether or not it is true. Specify who provides what and in which order and the sentence’s meaning. 电气工程作业代写
Explain how these effect both the dynamics of the game and the sentence’s meaning.
- Explain which settings of the free variables make it true and which make it false.
II&III I will give you two setting of the free variables. For each, you must decide whether this setting makes the sentence true or false. Either way, give a proof. i.e. Explain the strategy of the winning player and why he wins. 电气工程作业代写
Example: ∀x ∈ {0, 1, . . .}, ∃y ∈ {0, 1, . . .}, cy > cx
The two setting of the free variables are c = 1 and c = −1.
Prove True: The following is a proof that the sentence is made true by setting c = 1.
Let x be arbitrary (given by adversary) Let y = x + 1 (given by the prover).
cy = y = x + 1 > x = cx hence prover wins.
Prove False: The following is a proof that the sentence is made false by setting c = −1. 电气工程作业代写
Let x = 0 (given by adversary)
Let y be arbitrary (given by prover).
We are talking about positive integers so no y is smaller than zero. Hence, y ≥ x.
Hence, cy = −y ≤ −x = cx.
Hence adversary wins. 电气工程作业代写
(a)Suppose you have a Turing Machine whose input consists of an array of some n values each in the range {1, . . . , d}. Each TM cell can contain one such We have not studied TMs yet. All you need to know is that each time step a TM reads from a cell, makes a decision, writes a value,and moves the head. A TM’s tape alphabet (i.e. what can be stored in a tape cell) can be anything the machine designer wants as longs she fixes it.
Hint:
- Inyour logical sentence include I[i] ∈ {1, . . . , d} to indicate that the ith value in the input I is in the correct range and i ∈ {1, . . . , n} to indicate that I has the n values.
- IncludeM (I) = P (I) to indicate that TM M has solved the sorting problem on input I.
- Include T ime(M, I) to indicate the number of time steps taken by TM M on inputI.
- Include1000dc, or 1000nc, or 1000dc1×nc2 to indicate an upper bound on the Here 1000 is stuck in so that we do not have to worry about the big-Oh constant.
- Connect the above ideas with and, or, →, and≤.
- Our parameters are M , I, d, n, i, c1, and c2. For each, use either a ∀ or a ∃ quantifier and list them in the correct order.
I Give logic sentence that expresses that P is computable in this
I** Give me a deep understanding of what the sentence means. 电气工程作业代写
II In your explanation, use and explain the expressions “compile time,” “run time” and “con- stant”.
Hint: Though I am likely too verbose with a 42 line essay.
II Let P be sorting.
III Let P be some problem that is computable but whose fastest algorithm requires at least 1000 2ntime.
Hint: The exact math can be a pain so fudge it the best you can.
(b)Let S be a set and c be an integer. Answer the above list of questions about the
∃list L, [∀objects x ∈ S, ∃integer i ∈ {1, . . . , c}, L(i) = x] and [∀integer i ∈ {1, . . . , c}, ∃objects x ∈ S, L(i) = x]
II: Let S = {p, q, r} and c = 3. III: Let S = {p, q, r} and c = 2. 电气工程作业代写
(c)Let f and gbe functions from the reals to the reals.
∀infinitesimals ǫ > 0, ∃real x0, ∀reals x ≥ x0, f (x) ∈ [g(x) − ǫ, g(x) + ǫ]
II: Let f (x) = 1 and g(x) = 0 III: Let f (x) = 1 and g(x) = 0
(d)ClauseSat(I):
The input I is a propositional formula which is the and of clauses; Each clause the or of literals;
Each literal a variable or its negation. 电气工程作业代写
Eg (a or ¬b or d) and (¬a or ¬c or d or e) and (b or ¬c or ¬e) and (¬a or ¬c or e) An assignment/solution S assigns true/false to each variable:
Eg S = (a = T, b = T, c = F, d = F, e = T ).
ClauseSat(I) ≡, ∃assignment/solution S, ∀clauses C, ∃literal x, “Assignment S satisfies literal x in clause C in input I”
II: The I given in the example. 电气工程作业代写
III: I = (a or b or c) and (a or b or ¬c) and (a or ¬b or c) and (a or ¬b or ¬c) and (¬a or b or c) and (¬a or b or ¬c) and (¬a or ¬b or c) and (¬a or ¬b or ¬c)
2.(2 marks) Art therapy question: When half done the exam, draw a picture of how you are feeling.
其他代写：代写CS C++代写 java代写 matlab代写 web代写 app代写 作业代写 物理代写 数学代写 考试助攻 paper代写 cs作业代写 金融经济统计代写 python代写
