CRN 12107: HW 4 - Revision history

HelmutKnaust at 06:34, 9 October 2013

2013-10-09T06:34:16Z

HelmutKnaust at 06:31, 9 October 2013

2013-10-09T06:31:26Z

HelmutKnaust at 06:29, 9 October 2013

2013-10-09T06:29:28Z

HelmutKnaust: Created page with "'''Problem 16.''' Exercise 2.5 #1a. '''Problem 17.''' # Show that every positive integer can be written as the sum of (one or more) distinct powers of 2. (Examples: $8=2^3$..."

2013-10-09T06:28:02Z

Created page with "'''Problem 16.''' Exercise 2.5 #1a. '''Problem 17.''' # Show that every positive integer can be written as the sum of (one or more) distinct powers of 2. (Examples: $8=2^3$..."

New page

'''Problem 16.''' Exercise 2.5 #1a.

'''Problem 17.'''
# Show that every positive integer can be written as the sum of (one or more) distinct powers of 2. (Examples: $8=2^3$, $25=2^4+2^3+2^0$.)
# Can every positive integer be written as the sum of (one or more) distinct powers of 3?

It is quite obvious that statements and their connectives on the one hand, and sets and set connectives on the other hand behave somewhat analogously. The English mathematician ''George Boole'' (1815--1864) made this idea precise by describing what he called "algebra of logic". Today we use the name "Boolean Algebra" in his honor instead:

A ''Boolean Algebra'' is a set ${\cal B}$ together with two "connectives" $\sqcap$ and $\sqcup$ satisfying the following properties:

#Closure Laws:
## If A and B are two elements in ${\cal B}$, then $A\sqcap B$ is also an element in ${\cal B}$.
## If A and B are two elements in ${\cal B}$, then $A\sqcup B$ is also an element in ${\cal B}$.
#Commutative Laws:
## $A\sqcap B=B\sqcap A$ for all elements $A$ and $B$ in $\cal B$.
##$A\sqcup B=B\sqcup A$ for all elements $A$ and $B$ in $\cal B$.
#Associative Laws:
## $(A\sqcap B)\sqcap C=A\sqcap (B\sqcap C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
## $(A\sqcup B)\sqcup C=A\sqcup (B\sqcup C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
#Absorption Laws:
## $A\sqcap (A\sqcup B)=A$ for all elements $A$ and $B$ in $\cal B$.
## $A\sqcup (A\sqcap B)=A$ for all elements $A$ and $B$ in $\cal B$.
#Distributive Laws:
## $A\sqcap (B\sqcup C)=(A\sqcap B)\sqcup (A\sqcap C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
## $A\sqcup (B\sqcap C)=(A\sqcup B)\sqcap (A\sqcup C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
#There are elements $N\in{\cal B}$ (called the ''null elemen''t) and $O\in{\cal B}$ (the ''one element'') such that
## $A\sqcap N=N$ and $A\sqcap O=A$\quad for all elements $A$ in $\cal B$.
## $A\sqcup O=O$ and $A\sqcup N=A$\quad for all elements $A$ in $\cal B$.
#For every element $A$ in $\cal B$ there is an element $B$ in $\cal B$ such that $A\sqcap B=N$ and $A\sqcup B=O$.

Let $X$ be an arbitrary set. Then ${\cal P}(X)$ with the connectives $\cap$ (in the role of $\sqcap$) and $\cup$ (in the role
of $\sqcup$) forms a Boolean Algebra. Highlights of the proof are the subject of the problem below:

'''Problem 18.'''
Let $X$ be an arbitrary set.
# Show that the Absorption Laws hold for ${\cal P}(X)$.
# Which elements in ${\cal P}(X)$ play the role of the null element, and the one element, respectively?
# For a given element $A$ in ${\cal P}(X)$, how does one choose the element $B$ mentioned in Law 7?

Similarly certain sets of statements with connectives $\wedge$ (in the role of $\sqcap$) and $\vee$ (in the role of $\sqcup$) naturally form Boolean Algebras.

What is meant by "certain" sets of statements? Our task at hand is to identify what sets of statements correspond to power sets.

Let us consider an example and start with one "generic" statement $P$. How many distinct propositional forms can we form involving this statement? A little bit of reflection will lead us on the following path: Every propositional form has a truth table, so the number of distinct propositional forms is limited by the number of distinct truth tables. Since a truth table involving the statement $P$ has two rows, and since we have two choices for each row entry (T or F), there are at most 4 distinct truth tables, and therefore there are at most 4~distinct propositional forms. On the other hand it is easy to see that $P$, $\neg P$, $P\vee \neg P$ and $P\wedge \neg P$ are 4 distinct propositional forms contained in each Boolean Algebra containing $P$.

It is now boring to check that the following 4-element set indeed forms a Boolean Algebra:
\[{\cal S}_1=\{P\wedge\neg P;\ P,\ \neg P;\ P\vee \neg P\}\]
${\cal S}_1$ is called the "Boolean Algebra generated by the free statement $P$".

'''Problem 19.'''
Find the Boolean Algebra ${\cal S}_2$ generated by two free statements $P$ and $Q$.

For a natural number $n$, let ${\cal D}_n$ denote the set of the divisors of $n$. For example, ${\cal D}_{42}=\{1,2,3,6,7,14,21,42\}$ and ${\cal D}_{12}=\{1,2,3,4,6,12\}$. For $m,n\in\mathbb{N}$ let $m\sqcap n$ denote the greatest common divisor of $n$ and $m$, and $m\sqcup n$ their least common multiple. For instance $6\sqcap 4=2$ and $6\sqcup 4=12$. It turns out that ${\cal D}_{42}$ with these two operations $\sqcap$ and $\sqcup$ forms a Boolean Algebra, while ${\cal D}_{12}$ does '''not'''.

'''Problem 20.'''
# Verify Boolean Algebra Laws 5, 6 and 7 for ${\cal D}_{42}$.
# Show that ${\cal D}_{12}$ does not form a Boolean Algebra.
# Conjecture for which values of $n$ the set ${\cal D}_{n}$ forms a Boolean Algebra.

@@ Line 59: / Line 59: @@
 '''Problem 20.'''
-# Verify Boolean Algebra Laws 5, 6 and 7 for ${\cal D}_{42}$.
+# Verify Boolean Algebra Law 7 for ${\cal D}_{42}$.
-# Show that ${\cal D}_{12}$ does not form a Boolean Algebra. (Hint: Law 7.)
+# Show that ${\cal D}_{12}$ does not form a Boolean Algebra.
 # Conjecture for which values of $n$ the set ${\cal D}_{n}$ forms a Boolean Algebra.

@@ Line 26: / Line 26: @@
 ## $A\sqcap (B\sqcup C)=(A\sqcap B)\sqcup (A\sqcap C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
 ## $A\sqcup (B\sqcap C)=(A\sqcup B)\sqcap (A\sqcup C)$ for all elements $A$, $B$ and $C$ in $\cal B$.
-#There are elements $N\in{\cal B}$ (called the ''null elemen''t) and $O\in{\cal B}$ (the ''one element'') such that
+#There are elements $N\in{\cal B}$ (called the ''null element'') and $O\in{\cal B}$ (the ''one element'') such that
 ## $A\sqcap N=N$ and $A\sqcap O=A$\quad for all elements $A$ in $\cal B$.
 ## $A\sqcup O=O$ and $A\sqcup N=A$\quad for all elements $A$ in $\cal B$.
@@ Line 46: / Line 46: @@
 What is meant by "certain" sets of statements? Our task at hand is to identify what sets of statements correspond to power sets.
-Let us consider an example and start with one "generic" statement $P$. How many distinct propositional forms can we form involving this statement? A little bit of reflection will lead us on the following path: Every propositional form has a truth table, so the number of distinct propositional forms is limited by the number of distinct truth tables. Since a truth table involving the statement $P$ has two rows, and since we have two choices for each row entry (T or F), there are at most 4 distinct truth tables, and therefore there are at most 4~distinct propositional forms. On the other hand it is easy to see that $P$, $\neg P$, $P\vee \neg P$ and $P\wedge \neg P$ are 4 distinct propositional forms contained in each Boolean Algebra containing $P$.
+Let us consider an example and start with one "generic" statement $P$. How many distinct propositional forms can we form involving this statement? A little bit of reflection will lead us on the following path: Every propositional form has a truth table, so the number of distinct propositional forms is limited by the number of distinct truth tables. Since a truth table involving the statement $P$ has two rows, and since we have two choices for each row entry (T or F), there are at most 4 distinct truth tables, and therefore there are at most 4 distinct propositional forms. On the other hand it is easy to see that $P$, $\neg P$, $P\vee \neg P$ and $P\wedge \neg P$ are 4 distinct propositional forms contained in each Boolean Algebra containing $P$.
 It is now boring to check that the following 4-element set indeed forms a Boolean Algebra: