CS2333/Assignment 2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Question 6\n",
    "Let $S = \\{0,1\\}^*$ be the set of all strings of zero and ones, which includes the empty string $\\epsilon$.\n",
    "Let $h : S \\rightarrow \\mathbb{Z}^*$ be the function defined by $h(x)$ equal the number of zeros in $x$ multiplied by the number of ones in $x$\n",
    "For example, $h(00100011) = 5 \\times 3 = 15, and h(111) = 0 \\times 3 = 0$\n",
    "\n",
    "(a) Is $h$ one-to-one? No, because both strings $001$ and $110$ map to the same value, $2$\n",
    "$2 \\times 1 = 2$ and $1 \\times 2 = 2$\n",
    "\n",
    "(b) Is $h$ onto? Yes, because you can find every non-negative integer by multiplying any number of ones by one zero $(1 \\times 1), (1 \\times 2), ...$\n",
    "Let the number of zeros be exactly 1, and n be the number of ones, and m be any non-negative integer\n",
    "$h(n) = m, 1n = m, n = m$ "
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "b67364155fcb1072"
  },
  {
   "cell_type": "markdown",
   "source": [
    "<div style=\"page-break-after: always;\"></div>"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ec5269e5b4749d08"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 8\n",
    "(a)\n",
    "This function is not one-to-one (111110, 1111100 are both 5)\n",
    "This function is onto (10, 110, 1110, 11...0 is all non-negative integers)\n",
    "\n",
    "(b)\n",
    "This function is not one-to-one (11111, 01111 are both 1)\n",
    "This function is onto (All strings are mapped to, as you can simply pad any character with any 4 characters first)\n",
    "\n",
    "(c)\n",
    "This function is not one-to-one (Quebec, Yukon both are 0)\n",
    "This function is not onto (None of the provinces contain 3 or 5 a's"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ead9052998c5edf6"
  },
  {
   "cell_type": "markdown",
   "source": [
    "<div style=\"page-break-after: always;\"></div>"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "f27520443479cce9"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 9\n",
    "Consider the relation $R$ defined on the set $\\mathbb{Z}$ as follows:\n",
    "$$R = \\{(m,n) | m,n \\in \\mathbb{Z}, mn < 0\\}$$\n",
    "\n",
    "(a) Is the relation reflexive? No\n",
    "For every integer $x$, $x \\times x = x^2$, and by the definition of squares, can never be less than zero\n",
    "\n",
    "(b) Is the relation symmetric? Yes\n",
    "Let $x, y$ be a pair of integers in the relation and $z$ be the product of $x and y$, so $x \\times y = -z$\n",
    "Since multiplication is commutative, the position of $x$ and $y$ do not matter, so $(x,y)$ and $(y,x)$ are in the relation\n",
    "(Both $x \\times y$ and $y \\times x$ equal $-z$)\n",
    "\n",
    "(c) Is the relation transitive? No\n",
    "Let $a = 1, b = -2, c = 3$\n",
    "$1 \\times -2 = -2$ and $-2 \\times 3 = -6$, however $1 \\times 3 = 3$, which is $> 0$\n",
    "$\\therefore$ this relation is not transitive\n",
    "\n",
    "(d) Is this an equivalence relation? No, because these three conditions are not met"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "874c8dbcc345edad"
  },
  {
   "cell_type": "markdown",
   "source": [
    "<div style=\"page-break-after: always;\"></div>"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "ca477f12a96f397a"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 11\n",
    "Consider the relation $R$ defined on the set $\\mathbb{Z}$ as follows:\n",
    "$$\\forall m,n \\in \\mathbb{Z}, (m,n) \\in R \\text{ if and only if } m + n = 2k \\text{ for some integer } k$$\n",
    "\n",
    "(a) Is this relation reflexive? Yes\n",
    "For every integer $x$, $x + x = 2x$, therefore it is reflexive\n",
    "\n",
    "(b) Is this relation symmetric? Yes\n",
    "Let $x, y$ be a pair of integers in the relation and $z$ be the sum of these integers, so $x + y = 2z$\n",
    "Since addition is commutative, the position of $x$ and $y$ do not matter, so $(x,y) and $(y,x) are in the relation\n",
    "(Both $x + y$ and $y + x$ equal $2z$)\n",
    "\n",
    "(c) Is this relation transitive? Yes\n",
    "Let $(a,b)$ and $(b,c)$ be valid pairs of integers of the relation $R$\n",
    "$a + b = 2n$, and $b + c = 2p$, then $b = 2n - a$ and $b = 2p - c$\n",
    "$-2n + a = 2p - c$\n",
    "$a + c = 2p + 2n$\n",
    "Since the sum of a and c is the sum of two even numbers (numbers multiplied by 2 must be even), then the result must be even, so the result is divisible by 2\n",
    "$\\therefore$ The relationship is transitive"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "5fe823d05dd08b12"
  },
  {
   "cell_type": "markdown",
   "source": [
    "<div style=\"page-break-after: always;\"></div>"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "889a2a7359618ee7"
  },
  {
   "cell_type": "markdown",
   "source": [
    "# Question 14\n",
    "There are 7 equivalence classes as the results are grouped by the integer returned by $n_0(x) - n_1(x)$/$n_0(y) - n_1(y)$ for any relation pair, the results are that being set of differences $\\{-3, -2, -1, 0, 1, 2, 3\\}$"
   ],
   "metadata": {
    "collapsed": false
   },
   "id": "fd69c73a15e8e6a0"
  },
  {
   "cell_type": "code",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{-3: [('111', '111')],\n",
      " -2: [('11', '11')],\n",
      " -1: [('1', '1'),\n",
      "      ('1', '011'),\n",
      "      ('1', '101'),\n",
      "      ('1', '110'),\n",
      "      ('011', '1'),\n",
      "      ('011', '011'),\n",
      "      ('011', '101'),\n",
      "      ('011', '110'),\n",
      "      ('101', '1'),\n",
      "      ('101', '011'),\n",
      "      ('101', '101'),\n",
      "      ('101', '110'),\n",
      "      ('110', '1'),\n",
      "      ('110', '011'),\n",
      "      ('110', '101'),\n",
      "      ('110', '110')],\n",
      " 0: [('', ''),\n",
      "     ('', '01'),\n",
      "     ('', '10'),\n",
      "     ('01', ''),\n",
      "     ('01', '01'),\n",
      "     ('01', '10'),\n",
      "     ('10', ''),\n",
      "     ('10', '01'),\n",
      "     ('10', '10')],\n",
      " 1: [('0', '0'),\n",
      "     ('0', '001'),\n",
      "     ('0', '010'),\n",
      "     ('0', '100'),\n",
      "     ('001', '0'),\n",
      "     ('001', '001'),\n",
      "     ('001', '010'),\n",
      "     ('001', '100'),\n",
      "     ('010', '0'),\n",
      "     ('010', '001'),\n",
      "     ('010', '010'),\n",
      "     ('010', '100'),\n",
      "     ('100', '0'),\n",
      "     ('100', '001'),\n",
      "     ('100', '010'),\n",
      "     ('100', '100')],\n",
      " 2: [('00', '00')],\n",
      " 3: [('000', '000')]}\n"
     ]
    }
   ],
   "source": [
    "# Set of all strings containing 0 and 1 up to length 3\n",
    "def get_all_strings_with_a_given_alphabet_and_length(_alphabet, _length):\n",
    "\t_strings = ['']\n",
    "\tfor i in range(_length):\n",
    "\t\ts = [s + c for s in _strings for c in _alphabet]\n",
    "\t\t_strings += s\n",
    "\n",
    "\t# Remove duplicates (set() isn't as nice as it doesn't preserve order, at least for verification purposes)\n",
    "\t_strings = list(dict.fromkeys(_strings))\n",
    "\treturn _strings\n",
    "\n",
    "alphabet = ['0', '1']\n",
    "strings = get_all_strings_with_a_given_alphabet_and_length(alphabet, 3)\n",
    "\n",
    "# The relation is valid if the number of zeros from string x minus the number of ones from string x is equal to the number of zeros from string y minus the number of ones from string y\n",
    "def is_valid_relation(_x, _y):\n",
    "\t# Count the number of zeros and ones in each string\n",
    "\tx_zeros = _x.count('0')\n",
    "\tx_ones = _x.count('1')\n",
    "\ty_zeros = _y.count('0')\n",
    "\ty_ones = _y.count('1')\n",
    "\n",
    "\t# Return true if the difference between the number of zeros and ones is equal\n",
    "\treturn (x_zeros - x_ones) == (y_zeros - y_ones)\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "# Print all valid relations\n",
    "equivalence_classes = defaultdict(list)\n",
    "for x in strings:\n",
    "\tfor y in strings:\n",
    "\t\tif is_valid_relation(x, y):\n",
    "\t\t\t# create a tuple of the two strings\n",
    "\t\t\tt = (x, y)\n",
    "\t\t\t# calculate the difference between the number of zeros and ones\n",
    "\t\t\td = x.count('0') - x.count('1')\n",
    "\t\t\t# add the tuple a list under the key of the difference\n",
    "\t\t\tequivalence_classes[d].append(t)\n",
    "\t\t\t\t\n",
    "# Print the dict\n",
    "equivalence_classes = dict(equivalence_classes)\n",
    "from pprint import pprint\n",
    "pprint(equivalence_classes)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2024-01-26T22:03:01.411977200Z",
     "start_time": "2024-01-26T22:03:01.364977700Z"
    }
   },
   "id": "94712ae197e8639c",
   "execution_count": 5
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}