\newchapter{Set theory}

\leveldown{}

\myheading{Set theory explanation via boolean operations}

\leveldown{}

We are going to put a set in integer variable, where each bit will represent an element of set.
Groups of bits - a subset.
'Universe' (all possible elements) is a group of all possible bits within variable.

Cardinality of set is number of elements in it.
We can find it just by count all bits or using \verb|popcount()| function (\ref{popcnt}).

\myheading{Collecting TV series}

We're downloading a favorite TV series from torrent tracker.
Obviously, they downloading in random order.
We want to check if we collected all required movies/elements in 0..7 range.

\lstinputlisting[style=customc]{set/1.c}

Important to note that the \verb|add_to_set()| function can be called several times with the same element.

\myheading{Rock band}

\lstinputlisting[style=customc]{set/rock.c}

The obvious limitation: only 32 elements in set are allowed in 32-bit integer type.
But you can switch to 64-bit integer or to bitstring data type.

\myheading{Languages}

\lstinputlisting[style=customc]{set/lang.c}

By the way, an interesting story about applying set/logical operations on paper cards:

\begin{framed}
\begin{quotation}
To allow a visual check that all cards in a deck were oriented the same way, one corner of each card was beveled, much like Hollerith punched cards. Edge-notched cards, however, were not intended to be read by machines such as IBM card sorters. Instead, they were manipulated by passing one or more slim needles through selected holes in a group of cards. As the needles were lifted, the cards that were notched in the hole positions where the needles were inserted would be left behind as rest of the deck was lifted by the needles. Using two or more needles produced a logical and function. Combining the cards from two different selections produced a logical or. Quite complex manipulations, including sorting were possible using these techniques. 
\end{quotation}
\end{framed}
( \url{https://en.wikipedia.org/wiki/Edge-notched_card} )

\myheading{De Morgan's laws}

... is valid for both sets, boolean values and bitstrings of arbitrary size.

You can easily prove this for boolean values.
Construct a truth table for all possible two boolean inputs.
That would consists of only 4 rows.
Q.E.D.

By induction, extend this to bitstrings of arbitrary size.

\myheading{Powerset}

(According to Wiktionary: \url{https://en.wiktionary.org/wiki/power_set}.)
The set whose elements comprise all the subsets of S (including the empty set and S itself).
An alternative notation is $2^S$...

For example, we have 4 elements in set.
Each element for each bit.
How can we enumerate all possible combinations?
Just by listing all numbers between 0b0000 and 0b1111.
That comprises 16 combinations or subsets, including empty set (starting 0b0000).

This is why $2^S$ notation is also used: there are $2^{number of elements}$ subsets.
In our case, $2^4=16$.

\myheading{Inclusion-exclusion principle}

The problem from the "Discrete Structures, Logic and Computability" book by James L. Hein, 4th ed.

\begin{lstlisting}
Suppose a survey revealed that 70% of the population visited
an amusement park and 80% visited a national park.
At least what percentage of the population visited both?
\end{lstlisting}

The problem is supposed to be solved using finite sets counting and \textit{inclusion–exclusion principle}...
But I'm slothful student and would try simple bruteforce.

Each 1 bit in a variable would reflect 10\% of population.
Then I enumerate all possible pairs.
I check only those pairs, where there are 7 bits in p1 variable and 8 bits in p2 variable.

\lstinputlisting[style=custompy]{set/parks.py}

The result:

\begin{lstlisting}
min: 5
max: 7
\end{lstlisting}

You see, the minimum possible value is 5 (50\%), the maximum is 7 (70\%).
Let's add some debug info:

\begin{lstlisting}
...
        if x==5 or x==7:
            print ("-")
            print ("park1 {0:010b}".format(p1), "(%d)" % popcnt(p1))
            print ("park2 {0:010b}".format(p2), "(%d)" % popcnt(p2))
            print ("both  {0:010b}".format(p1 & p2), "(%d)" % popcnt(p1 & p2))
...
\end{lstlisting}

If maximum:

\begin{lstlisting}
park1 0001111111 (7)
park2 0011111111 (8)
both  0001111111 (7)
\end{lstlisting}

If minimum:

\begin{lstlisting}
park1 0001111111 (7)
park2 1111111100 (8)
both  0001111100 (5)
\end{lstlisting}

I've found such a cases, where "ones" are allocated in such a way, so that the AND of "ones" in "both" would be minimal/maximal.

Observing this, we can deduce the general formula: maximal "both" = min(park1, park2)

What about minimal "both"?
We can see that "ones" from park1 must "shift out" or "hide in" to a corresponding empty space of park2.
So, minimal both = park2 - (100\% - park1)

Variations of the problem from the same book:

\begin{lstlisting}
Suppose that 100 senators voted on three separate senate bills as follows:
70 percent of the senators voted for the first bill, 65 percent voted for the second bill,
and 60 percent voted for the third bill. At least what percentage of the senators voted for all three bills?
\end{lstlisting}

\begin{lstlisting}
Suppose that 25 people attended a conference with three sessions, where 15 people attended the first session,
18 the second session, and 12 the third session. At least how many people attended all three sessions?
\end{lstlisting}

Also, The Abstract Algebra book\footnote{\url{https://archive.org/details/Herstein3thEditon/}}
by I.N. Herstein has exercises like:

\begin{lstlisting}
19. In his book A Tangled Tale, Lewis Carroll proposed the following riddle
about a group of disabled veterans: "Say that 70% have lost an eye, 75%
an ear, 80% an arm, 85% a leg. What percentage, at least, must have lost
all four?" Solve Lewis Carroll's problem.
\end{lstlisting}

\levelup{}

\levelup{}