THREE POSSIBLE FINAL PROJECTS: You can either choose one of the following three projects or create your own. All final projects are due the last day of finals. PROJECT ONE: Mathematical Logic is important not just in the foundations of mathematics, but also in computer science, circuit design, artificial intelligence, programming languages, etc. Many problems in logic can be encoded using polynomial too!! A proof system in logic consists of axioms and inference rules. By applying those rules repeatedly we obtain theorems. Here we deal with propositional logic. We only have variables that are true or false and we use the logic connectives: NOT, OR, AND, IMPLIES. There are no quantifiers! An example of an axiom is x OR (NOT x) because this is always true. In a typical proof system aims one proves that a certain set of formulas S is unsatisfiable= impossible to make all formulas in S true by giving appropiate values to its variables. Example: x AND (NOT x) is an unsatisfiable system. If the system is unsatisfiable we wish to find a refutation, a proof that it is unsatisfiable by deriving the simplest contradiction=false. There are many proof systems around: Tableaux, Horn clause resolution, Davis-Putnam procedure, Frege-Hilbert proofs, etc. The key question is: How long is a shortest refutation of a given unsatisfiable set of logic formulas? How hard is it to find a short refutation if one exists? Example: The pigeonhole principle says that it is impossible to fit n+1 pigeons into n pigeonholes without a collision. Haken proved that any resolution or proof of this impossibility requires exponential length at least 2^{cn} for some constant c. Here we represent propositional logic as polynomial relations: We associate to the value true=0 and false=1, similarly we associate to a formula a polynomial as follows: NOT f <----> 1-f f OR g <----> f*g f AND g <----> 1-(1-f)*(1-g) f IMPLIES g <----> (1-f)*g Lemma: Every propositional formula corresponds to a polynomial. The rules of inferences are precisely the rules of membership in the ideal: Namely if f, g are valid then af+bg and (x_i) *f are valid as well. Thus the valid formulas are precisely the members of the ideal. Example: { x OR y, z OR w, u OR v, (NOT x) OR (NOT z), (NOT x) OR (NOT u), (NOT y) OR (NOT u), (NOT y) OR (NOT w), (NOT y) OR (NOT v), (NOT w) OR (NOT v)} can be transfered to a system of equations (see below) Lemma: The associated system of equations together with the conditions that each variable must be either zero or one will have a solution if and only if the logical formula is satisfied. restart; with(Groebner); N0NJJkJhc2lzRzYiSSVGR0xNR0YkSTFIaWxiZXJ0RGltZW5zaW9uR0YkSTJIaWxiZXJ0UG9seW5vbWlhbEdGJEkuSGlsYmVydFNlcmllc0dGJEkrSG9tb2dlbml6ZUdGJEksSW5pdGlhbEZvcm1HRiRJLEludGVyUmVkdWNlR0YkSSlJc1Byb3BlckdGJEkySXNaZXJvRGltZW5zaW9uYWxHRiRJM0xlYWRpbmdDb2VmZmljaWVudEdGJEkwTGVhZGluZ01vbm9taWFsR0YkSSxMZWFkaW5nVGVybUdGJEksTWF0cml4T3JkZXJHRiRJNk1heGltYWxJbmRlcGVuZGVudFNldEdGJEkuTW9ub21pYWxPcmRlckdGJEk1TXVsdGlwbGljYXRpb25NYXRyaXhHRiRJOU11bHRpdmFyaWF0ZUN5Y2xpY1ZlY3RvckdGJEkrTm9ybWFsRm9ybUdGJEkqTm9ybWFsU2V0R0YkSUFSYXRpb25hbFVuaXZhcmlhdGVSZXByZXNlbnRhdGlvbkdGJEknUmVkdWNlR0YkSS5SZW1lbWJlckJhc2lzR0YkSSxTUG9seW5vbWlhbEdGJEkmU29sdmVHRiRJNVN1Z2dlc3RWYXJpYWJsZU9yZGVyR0YkSShTdXBwb3J0R0YkSSpUZXN0T3JkZXJHRiRJMFRvcmljSWRlYWxCYXNpc0dGJEktVHJhaWxpbmdUZXJtR0YkSTVVbml2YXJpYXRlUG9seW5vbWlhbEdGJEklV2Fsa0dGJEkvV2VpZ2h0ZWREZWdyZWVHRiQ= F:=[x^2-x,y^2-y,z^2-z,w^2-w, u^2-u, v^2-v, x*y, z*w, u*v, (1-x)*(1-z), (1-x)*(1-u), (1-y)*(1-u), (1-y)*(1-w), (1-y)*(1-v), (1-w)*(1-v)]; NzEsJiokKUkieEc2IiIiIyIiIkYpRiYhIiIsJiokKUkieUdGJ0YoRilGKUYuRiosJiokKUkiekdGJ0YoRilGKUYyRiosJiokKUkid0dGJ0YoRilGKUY2RiosJiokKUkidUdGJ0YoRilGKUY6RiosJiokKUkidkdGJ0YoRilGKUY+RioqJkYmRilGLkYpKiZGMkYpRjZGKSomRjpGKUY+RikqJiwmRilGKUYmRipGKSwmRilGKUYyRipGKSomRkNGKSwmRilGKUY6RipGKSomLCZGKUYpRi5GKkYpRkZGKSomRkhGKSwmRilGKUY2RipGKSomRkhGKSwmRilGKUY+RipGKSomRkpGKUZMRik= Basis(F,plex(x,y,z,w,u,v),characteristic=2); NyMiIiI= A system of polynomials can be refuted if we can prove that 1 is in the ideal they generate! This can be done by using Groebner bases. These systems were introduced by Clegg, Edmonds, and Impagliazzo in 1996. Similarly, remember the Hilbert Nullstellensatz guarantees that the system has no solution (unsatisfiable) if and only if 1 is in the ideal! The Nullstellesatz gives another way to prove that logical systems are infeasible. PROJECT: Write a MAPLE program that implements the Groebner bases proof system of logical given logical formulas formulas. Investigate more about the Logic Satisfiability problem (have you heard of NP?), what is the Davis-Putnam algorithm. Implement in MAPLE either the Davis-Putnam or the Hilbert Nullstellensatz method and compare your method of choice to the Groebner bases method. Which one is faster? To test your code make sure to formulate the pigeonhole principle for n pigeons, n<=7 and see which method is faster in 2 more examples. TWO: INTEGER PROGRAMMING: In many applications in engineering and management one is interested to solve the optimization problem Maximize c_1 x_1+c_2 x_2+ .... + c_n x_n subject to the conditions a_{11} x_1 + a_{12} x_2 + .... + a_{1n} x_n = b_1 a_{21} x_1 + a_{22} x_2+..... + a_{2n} x_n = b_2 ..... a_{m1} x_1+ a_{m2} x_2+.... + a_{mn} x_n= b_m x_i >= 0 and integer. This problem receives the name of the INTEGER PROGRAMMING problem and it is abbreviated, using matrix notation as max{cx | Ax=b, x>=0, integer}. Here we will study one simple procedure, using Groebner bases, that computes the solution. It will depend on the matrix A given by the system. But first, the version where we do not ask for integer solutions is called the LINEAR PROGRAMMING problem.Linear programming is easier than integer programming and there is a very good algorithm, the simplex method, that works really well in practice. MAPLE has an implementation already: with(simplex); NzFJJmJhc2lzRzYiSStjb252ZXhodWxsR0YkSSZjdGVybUdGJEksZGVmaW5lX3plcm9HRiRJKGRpc3BsYXlHRiRJJWR1YWxHRiRJKWZlYXNpYmxlR0YkSSltYXhpbWl6ZUdJKF9zeXNsaWJHRiRJKW1pbmltaXplR0YsSSZwaXZvdEdGJEkpcGl2b3RlcW5HRiRJKXBpdm90dmFyR0YkSSZyYXRpb0dGJEkmc2V0dXBHRiRJLHN0YW5kYXJkaXplR0Yk constraints:={3*a+2*b+c=11,4*a+b+c+d=55}; PCQvLChJImFHNiIiIiRJImJHRiYiIiNJImNHRiYiIiIiIzYvLCpGJSIiJUYoRitGKkYrSSJkR0YmRisiI2I= objectivefct:=a+b+c+1000000*d; LCpJImFHNiIiIiJJImJHRiRGJUkiY0dGJEYlSSJkR0YkIigrKysi minimize(objectivefct,constraints,NONNEGATIVE); PCYvSSJhRzYiIyIjNiIiJC9JImJHRiUiIiEvSSJjR0YlRisvSSJkR0YlIyIkQCJGKA== But suppose we wish to find the integral optimal solutions?? We will use Groebner bases in an innovative way. The first issue is there may NOT be any integer solution at all. How can one find that kind of solution? with(Groebner); N0NJJkJhc2lzRzYiSSVGR0xNR0YkSTFIaWxiZXJ0RGltZW5zaW9uR0YkSTJIaWxiZXJ0UG9seW5vbWlhbEdGJEkuSGlsYmVydFNlcmllc0dGJEkrSG9tb2dlbml6ZUdGJEksSW5pdGlhbEZvcm1HRiRJLEludGVyUmVkdWNlR0YkSSlJc1Byb3BlckdGJEkySXNaZXJvRGltZW5zaW9uYWxHRiRJM0xlYWRpbmdDb2VmZmljaWVudEdGJEkwTGVhZGluZ01vbm9taWFsR0YkSSxMZWFkaW5nVGVybUdGJEksTWF0cml4T3JkZXJHRiRJNk1heGltYWxJbmRlcGVuZGVudFNldEdGJEkuTW9ub21pYWxPcmRlckdGJEk1TXVsdGlwbGljYXRpb25NYXRyaXhHRiRJOU11bHRpdmFyaWF0ZUN5Y2xpY1ZlY3RvckdGJEkrTm9ybWFsRm9ybUdGJEkqTm9ybWFsU2V0R0YkSUFSYXRpb25hbFVuaXZhcmlhdGVSZXByZXNlbnRhdGlvbkdGJEknUmVkdWNlR0YkSS5SZW1lbWJlckJhc2lzR0YkSSxTUG9seW5vbWlhbEdGJEkmU29sdmVHRiRJNVN1Z2dlc3RWYXJpYWJsZU9yZGVyR0YkSShTdXBwb3J0R0YkSSpUZXN0T3JkZXJHRiRJMFRvcmljSWRlYWxCYXNpc0dGJEktVHJhaWxpbmdUZXJtR0YkSTVVbml2YXJpYXRlUG9seW5vbWlhbEdGJEklV2Fsa0dGJEkvV2VpZ2h0ZWREZWdyZWVHRiQ= B:=Matrix([[3,2,1,0],[4,1,1,1]]); LUknTWF0cml4RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiMvSSQlaWRHRiciK0c4aklW zs:=[seq(z[i],i=1..4)]; xs:=[seq(x[i],i=1..2)]; NyYmSSJ6RzYiNiMiIiImRiQ2IyIiIyZGJDYjIiIkJkYkNiMiIiU= NyQmSSJ4RzYiNiMiIiImRiQ2IyIiIw== sys:=[seq(zs[i]-mul(x[j]^(B[j,i]),j=1..2),i=1..4)]; NyYsJiZJInpHNiI2IyIiIkYoKiYmSSJ4R0YmRiciIiQmRis2IyIiIyIiJSEiIiwmJkYlRi5GKComRipGL0YtRihGMSwmJkYlNiNGLEYoKiZGKkYoRi1GKEYxLCYmRiU2I0YwRihGLUYx G:=Basis(sys,plex(op(xs),op(zs))); NycsJiomJkkiekc2IjYjIiIjIiIiJkYmNiMiIiVGKkYqKiQmRiY2IyIiJEYpISIiLCYqJkYvRjFGK0YqRjImRiY2I0YqRiosJkYrRjImSSJ4R0YnRihGKiwmKiZGK0YqJkY5RjZGKkYqRi9GMiwmKiZGL0YqRjxGKkYqRiVGMg== NormalForm(x^11*x^55,G,plex(op(xs),op(zs))); KiYmSSJ6RzYiNiMiIiQiIzYmRiQ2IyIiJSIjVw== This shows that one solution of the integer program is taking [0,0,11,44] as a solution. But now let us find the OPTIMAL integer solution with respect to the cost vector. That is accomplished with just the H:=remove(has, G, xs); NyQsJiomJkkiekc2IjYjIiIjIiIiJkYmNiMiIiVGKkYqKiQmRiY2IyIiJEYpISIiLCYqJkYvRjFGK0YqRjImRiY2I0YqRio= J:=Basis(H,'matrix'([[1,1,1,1000000]],zs)); NyUsJiokJkkiekc2IjYjIiIkIiImIiIiKiYmRiY2I0YrRismRiY2IyIiI0YrISIiLCYqJkYvRismRiY2IyIiJUYrRisqJEYlRjFGMiwmKiZGJUYpRjVGK0YrRi1GMg== NormalForm(z^44*z^11,J,'matrix'([[1,1,1,1000000]],zs)); KigmSSJ6RzYiNiMiIiIiIiQmRiQ2IyIiJSIjVCZGJDYjRigiIiM= PROJECT: Implement in MAPLE the Groebner bases method to solve integer programming problems given by an integer matrix A, vectors b and c, assuming the entries are all non-negative integers. Test your code with at least 3 examples, the first one of them should be the integer programming problem. Minimize \$(2x+3y+z+5w)\$ subject to the conditions that \$3x+2y+z+w=10\$, \$4x+y+z=5\$ and all variables are non-negative integers. Using MAPLE's simplex package, compare the optimal value of the INTEGER optimal solution to the LINEAR programming optimal solution in one hundred randomly generated problems given by 3 x 8 matrices. How far apart are the two optima? THIRD OPTION: CHOOSE YOU OWN PROJECT: RULES: You can pick from any area of mathematics, but it has to include some MAPLE code and some experimentation (either by comparing it to other algorithms or by showing interesting phenomena through random examples, graphics, etc). When in doubt talk to me about what is legal or not. TTdSMApJN1JUQUJMRV9TQVZFLzQzMzA2MzEzMjhYLCUpYW55dGhpbmdHNiJGJVtnbCEiJSEhISMpIiMiJSIiJCIiJSIiIyIiIkYpRikiIiFGKUYl