\documentclass[12pt]{article}
\title{{\sc Comp} 280\\Assignment 5}
\author{Kiran Nair}
\date{February 15, 2007}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{array}
\begin{document}
\begin{titlepage}
\maketitle
\thispagestyle{empty}
\begin{center}
{\sc Note:} One slip day was used on this assignment.
\end{center}
\end{titlepage}
\pagestyle{myheadings}
\markright{COMP 280 Assignment 5}
\paragraph{Problem 1.}
\begin{proof}
Since $m$ and $n$ are odd, they can be expressed as $m=2k+1$ and $n=2l+1$. Thus,
\begin{equation*}
\begin{split}
m \cdot n&=(2k+1)(2l+1)\\
&=4kl+2k+2l+1\\
&=2(kl+k+l)+1\\
\end{split}
\end{equation*}
This is an odd number.
\end{proof}
\paragraph{Problem 2.}
\begin{proof}[Disproof by counterexample]
Let $a=3$ and $b=1/2$. $a$ is rational $(3\equiv3/1)$ and $b$ is rational. However, $a^b=\sqrt{3}$, which is known to be irrational.
\end{proof}
\paragraph{Problem 3.}$ $\\
Yes, we can conclude that $A = B$ if $A$ and $B$ are two sets with the same power set.
\begin{proof}[Proof by contradiction.]
Assume that $A$ and $B$ are two sets with the same power set but are not equal: $A\neq B$ and $P(A)=P(B)$. Because $A\neq B$, one of the following two cases must be true:
\begin{enumerate}
\item[(a)] There is an element $a$ in $A$ that is not in $B$.
\item[(b)] There is an element $b$ in $B$ that is not in $A$.
\end{enumerate}
If we assume (a) is true, we have the definitions $P(A)=P(B)$, $a\in A$, and $a\not \in B$. Using the definition of the power set, we can see that $\{a\}\in P(A)$. However, $\{a\}\not \in P(B)$ because $a\not \in B$. Thus, $P(A)\neq P(B)$, contradicting our original assumption.
\end{proof}
\paragraph{Problem 4.}
\begin{proof}
Let $A$ and $B$ be non-empty sets, and assume that $A\neq B$. Just as in \textit{Problem 3}, either there is an element $a$ in $A$ that is not in $B$, or there is an element $b$ in $B$ that is not in $A$. Let $x$ be an element in $B$. If we take the Cartesian product $A\times B$, we find that $\{a, x\}$ is an element. However, it cannot be in $B\times A$ since $A\not \in B$. Thus, $A\times B\neq B\times A$.
\end{proof}
\paragraph{Problem 5.}
\begin{enumerate}
\item[(a)] $A\cap B$
\item[(b)] $A-B$
\item[(c)] $A\cup B$
\item[(d)] $\bar{A}\cup \bar{B}$
\end{enumerate}
\paragraph{Problem 6.}
\begin{proof}
Let $A$ and $B$ be sets. Assume $x\in A$. $x\in A\cup (A\cap B)$ by the definition of union. From this definition,
\end{proof}
\paragraph{Problem 7.}
\begin{proof}
Let $A, B,$ and $C$ be sets:
\begin{flalign}
(A-B)-(B-C) &\equiv (A\cap \overline{C})\cap \overline{(B\cap\overline{C})}\\
&\equiv(A\cap\overline{C})\cap(\overline{B}\cup C)\\
&\equiv((A\cap \overline{C})\cap \overline{B})\cup ((A\cap \overline{C})\cap C)\\
&\equiv((A\cap \overline{B})\cap \overline{C})\cup ((A\cap \overline{C})\cap C)\\
&\equiv((A\cap \overline{B})\cap \overline{C})\cup (A\cap (\overline{C}\cap C))\\
&\equiv((A\cap \overline{B})\cap \overline{C})\cup (A\cap \emptyset)\\
&\equiv((A\cap \overline{B})\cap \overline{C})\cup \emptyset\\
&\equiv((A\cap \overline{B})\cap \overline{C})\\
&\equiv(A-B)-C
\end{flalign}
\begin{enumerate}
\item Definition of set subtraction
\item De Morgan's Law
\item Law of Distribution
\item Commutativity
\item Associativity
\item Law of Complements
\item Law of Domination
\item Law of Identities
\item Definition of set subtraction
\end{enumerate}
\end{proof}
\paragraph{Problem 8.}
See attached.
\paragraph{Problem 9.}
\begin{enumerate}
\item[(a)]\begin{equation*}
\bigcup_{i=1}^nA_i=A_n
\end{equation*}
\item[(b)]$$\bigcap_{i=1}^nA_i=A_1$$
\end{enumerate}
\paragraph{Problem 10.}
\{1, 3, 6, 10\} = 10 1001 0001.
\paragraph{Problem 11.}
\begin{enumerate}
\item[(a)] $A\cup B$
\item[(b)] $A\cap B$
\item[(c)] $B-A$
\item[(d)] $A\cup B$
\end{enumerate}
\paragraph{Problem 12.}
\begin{verbatim}
import java.util.*;
public class Problem12 {
public Problem12() {
}
public Set setDifference(Object[] a, Object[] b) {
Set s = new TreeSet();
outer:
for(Object o : a){
for(Object p : b)
if(o.equals(p))
continue outer;
s.add(o);
}
return s;
}
public Set crossProduct(Object[] a, Object[] b) {
Set s = new HashSet();
for(Object o : a) {
for(Object p : b)
s.add(new Pair(o,p));
}
return s;
}
public class Pair{
private Object p1, p2;
public Pair(Object p1, Object p2) {
this.p1 = p1;
this.p2 = p2;
}
public String toString() {
return "" + p1 + " " + p2;
}
}
public static void main(String[] args) {
Problem12 prob = new Problem12();
//Set-Difference
Set set1 = prob.setDifference(
new Object[] {"a", "b", "c", "d", "e"},
new Object[] {"b", "d"});
System.out.println(set1);
Set set2 = prob.setDifference(
new Object[] {5,3,6,7,2},
new Object[] {});
System.out.println(set2);
Set set3 = prob.setDifference(
new Object[] {},
new Object[] {1,7,2,7,8});
System.out.println(set3);
Set set4 = prob.setDifference(
new Object[] {6,4,1,7,8},
new Object[] {1,7,4,8,6});
System.out.println(set4);
//Cartesian-product
Set set5 = prob.crossProduct(
new Object[] {},
new Object[] {});
System.out.println(set5);
Set set6 = prob.crossProduct(
new Object[] {2,8},
new Object[] {});
System.out.println(set6);
Set set7 = prob.crossProduct(
new Object[] {"1"},
new Object[] {"2","4"});
System.out.println(set7);
Set set8 = prob.crossProduct(
new Object[] {"56", "53"},
new Object[] {"24", "32"});
System.out.println(set8);
}
}
\end{verbatim}
\paragraph{Problem 13.} $ $\newline
{\bf{\sc Note:}} The fifth edition points to Section 7.3, \#6. This happens to be different than the problem the homework set points to in the sixth edition: below is the solution to the fifth edition problem.\newline
A relation $R$ on a set $A$ is asymmetric if, for all points $x$ and $y$ on the set $A$, $x$ points to $y$ on the relation $R$, but $y$ does not point to $x$ on the same relation.
\paragraph{Problem 14.}
For an irreflexive relation $R$, the relation $R^2$ is not necessarily irreflexive. Assume the matrix $M_R$ below (the $X$'s signify that we don't care about their values for this problem):\newline
\begin{flalign*}
\mathbf{M}_R=\left [ \begin{array}{c,c,c,c}
0 & 1 & 1 & 1 \\
1 & 0 & X & X \\
1 & X & 0 & X \\
1 & X & X & 0 \\
\end{array} \right ]
\end{flalign*}
Then,
\begin{flalign*}
\mathbf{M}_R^2=\left [ \begin{array}{c,c,c,c}
3 & X & X & X \\
X & 1 & X & X \\
X & X & 1 & X \\
X & X & X & 1 \\
\end{array} \right ]
\end{flalign*}
Since the diagonal values are nonzero in $M_R^2$, the relation is not irreflexive.
\paragraph{Problem 15.}
\begin{flalign*}
\mathbf{M}_R=\left [ \begin{array}{c,c,c,c,c}
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 \\
\end{array} \right ]
\end{flalign*}
\begin{flalign*}
\mathbf{M}_R^2=\left [ \begin{array}{c,c,c,c,c}
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 \\
\end{array} \right ]
\end{flalign*}
\begin{flalign*}
\mathbf{M}_R^3=\left [ \begin{array}{c,c,c,c,c}
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{array} \right ]
\end{flalign*}
\begin{flalign*}
\mathbf{M}_R^4=\left [ \begin{array}{c,c,c,c,c}
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{array} \right ]
\end{flalign*}
${M}_R^5$=${M}_R^4$, and so on. Thus,
\mathbf{M}_R^{[*]}&=\mathbf{M}_R \vee \mathbf{M}_R^{[2]} \vee \ldots \vee \mathbf{M}_R^{[5]}\\ \newline
&=\left [ \begin{array}{ccccc}
0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 \\
\end{array} \right ] $ $\newline
$ $\newline
R^*&=\{(b,b),(b,c),(b,e),(c,b),(c,c),(c,e),(d,a),(e,b),(e,c),(e,e)\}.
\end{flalign*}
\paragraph{Problem 16.}
Items \(a\) and \(b\) are equivalence relations, while \(c\), \(d\), and \(e\) are not equivalence relations by the transitive property.
\paragraph{Problem 17.}
$R$ is reflexive because any bit string is equal to itself. $R$ is symmetric because there is at least one pair $(a,b)$ in $R$ where $a$ and $b$ have the same bits after the first three, and thus $(b,a)$ is in $R$. In addition, $R$ is transitive: if $(a,b)\in R$ and $(b,c)\in R$, then $a$, $b$, and $c$ must be the same in all bits other than the first three. Thus, $R$ is an equivalence relation on the set of all bit strings.
\paragraph{Problem 18.}
The adjacency matrices:
\begin{flalign*}
\mathbf{A}_G=\left [ \begin{array}{cccccccc}
0 & 1 & 0 & 1 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 0 & 1 & 1 & 1 & 0\\
0 & 1 & 0 & 1 & 0 & 1 & 1 & 1\\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 1\\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 1\\
1 & 1 & 1 & 0 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 1 & 0 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 1 & 0 & 1 & 0\\
\end{array} \right ]\\\\
\mathbf{A}_H=\left [ \begin{array}{cccccccc}
0 & 1 & 1 & 0 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 1 & 0 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\
0 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\
1 & 0 & 1 & 0 & 1 & 1 & 0 & 1\\
1 & 1 & 0 & 1 & 0 & 1 & 1 & 0\\
\end{array} \right ].
\end{flalign*}
\end{document}