{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "-" } }, "source": [ "# MTH5001 Introduction to Computer Programming - Lab 5\n", "Dr. Lennart Dabelow and Prof. Thomas Prellberg\n", "\n", "## Exercises" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1: Translating mathematical statements into Python code" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For any statements A and B, you will recall that the statement \"A implies B\" is equivalent to \"B or not A\". This can be demonstrated by constructing a truth table:\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABA implies BB or not A
TrueTrueTrueTrue
TrueFalseFalseFalse
FalseTrueTrueTrue
FalseFalseTrueTrue
\n", "\n", "Since the Boolean operators `or` and `not` are already defined in Python, we can use them to construct our own `implies` function. This function accepts two Boolean values, `A` and `B`, and returns the truth value of the statement \"A implies B\":" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T19:38:09.247532Z", "start_time": "2024-01-29T19:38:09.239546Z" } }, "outputs": [], "source": [ "def implies(A,B):\n", " \"returns the truth of 'A implies B'\"\n", " return B or not A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.a: \n", "\n", "Test that the `implies` function works by evaluating it for all four possible combinations of Boolean values." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:07.873049Z", "start_time": "2024-01-29T16:49:07.866657Z" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.b: \n", "\n", "Write a function `not_implies` that accepts two Boolean values, `A` and `B`, and returns the negation of \"A implies B\" (i.e. computes the truth value of the statement \"not (A implies B)\" ) and evaluate it for all four possible inputs." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:07.880565Z", "start_time": "2024-01-29T16:49:07.875977Z" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We say that an integer $a$ divides an integer $m$, and write $a|m$, if $m=ka$ for some integer $k$. In Python you can write a function `divides(a,m)` which computes the truth of `a divides m` for integers `a` and `m` as follows:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T19:38:09.255400Z", "start_time": "2024-01-29T19:38:09.250539Z" } }, "outputs": [], "source": [ "def divides(a,m):\n", " \"returns the truth of 'a divides m'\"\n", " return m%a==0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.c: \n", "\n", "Test that this Python function works by evaluating it with an instance for which the statement is true, and an instance for which it is false." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:07.893553Z", "start_time": "2024-01-29T16:49:07.890088Z" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Last year, you will have encountered the following fact about integer division:\n", "\n", "**Theorem:** Let $a,b,m,n\\in\\mathbb Z$. If $a|m$ and $b|n$ then $ab|mn$. \n", "\n", "According to this theorem\n", "\n", " if 7 divides 14 and 2 divides 4 then 14 divides 56 \n", "is a true statement, and\n", "\n", " if 7 divides 14 and 2 divides 3 then 14 divides 42 \n", "is also a true statement (can you see why?)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.d:\n", "\n", "Using the `implies` and `divides` functions defined above, write a function `test_theorem(a,b,m,n)` which tests the truth of this Theorem. Evaluate this function by evaluating it for four well-chosen examples." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:07.904373Z", "start_time": "2024-01-29T16:49:07.896084Z" }, "scrolled": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now consider the following claim, which is different from the theorem above:\n", "\n", "**Claim:** Let $a,b,n\\in\\mathbb Z$. If $a|n$ and $b|n$ then $ab|n$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Exercise 1.e: \n", "\n", "Write a function `test_theorem2(a,b,n)` which tests the truth of the above claim. Find input values that result in the function producing the output `False`, and hence disprove the statement." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:07.911280Z", "start_time": "2024-01-29T16:49:07.906260Z" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2: the Ruler Function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We would like you look at the [Ruler Function](https://en.wikipedia.org/wiki/Ruler_function), which counts the number of times a positive integer $n$ can be evenly divided by two. A cool way of determining this is to consider the binary representation of integers and getting the number of trailing zeros, using the built-in `bin()` function. Binary numbers are shown as strings of zeros and ones with a leading \"0b\", so for example the binary representation of $20=16+4=2^4+2^2$ is given by `0b10100`." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T19:38:09.265756Z", "start_time": "2024-01-29T19:38:09.257408Z" } }, "outputs": [ { "data": { "text/plain": [ "'0b10100'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(20)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that there are two trailing zeros, corresponding to the fact that $20=5\\times 2^2$.\n", "\n", "We can strip the trailing zeros with the `.rstrip()` method." ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T19:38:09.278553Z", "start_time": "2024-01-29T19:38:09.268774Z" } }, "outputs": [ { "data": { "text/plain": [ "'0b101'" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bin(20).rstrip(\"0\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This shortens the string to `0b101` and we can compute the difference in length, using the `len()` function." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T19:38:09.285045Z", "start_time": "2024-01-29T19:38:09.280565Z" } }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(bin(20))-len(bin(20).rstrip(\"0\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In other words, the number of times a positive integer `n` can be evenly divided by two can be computed using\n", "```python\n", " len(bin(n))-len(bin(n).rstrip(\"0\"))\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Produce two plots of the graph of the ruler function for integers $n$ from $0$ to $2^8-1$ and from $0$ to $2^{16}-1$, respectively." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2024-01-29T16:49:09.105320Z", "start_time": "2024-01-29T16:49:07.943434Z" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Submit your Jupyter Notebook to QMPLUS" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once you are done, save the jupyter notebook and submit it to QMPLUS under Lab Report Week 5." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.0" } }, "nbformat": 4, "nbformat_minor": 4 }