Propositional formula to represent set of binary strings

Question

I'm "getting acquainted" with mathematical logic and found an exercise online whose solution I don't understand. It asks for the most compact representation of a set of binary strings

{000000),(100000),(110000),(111000),(111100),(111110),

(111111),(011111),(001111),(000111),(000011),(000001)}

as a propositional formula. A possible solution is given: $$ \bigvee_{k=0}^5 \left( \biggl( \bigwedge_{i=0}^k \neg b_i \land \bigwedge_{i=k+1}^5 b_i \biggr) \lor \biggl( \bigwedge_{i=0}^k b_i \land \bigwedge_{i=k+1}^5 \neg b_i \biggr) \right) $$

First I thought it was something about arbitary set unions (because of the reminiscent notation), researched it, but found nothing with regards to some "nestedness". I guess, this displays how rudimentary my understanding of the whole topic still is. I thought the key lied in how the whole expression would evaluate, because it had that nested aspect to its structure, but then again, I don't understand how the connectives are acting in this.

Can someone explain me what is going on? Also how can I figure what I should have been searching for, how should I generally approach such a problem? I guess, having a good resource that provides one with a firm foundation is the first step. Do you have any recommendations that cover mathematical logic and set theory, or even better illuminate their interconnections?

Answer 1

The key thing to understand here is that, what you have quoted is not actually a propositional formula. Things like "$\bigwedge\limits_{i=0}^k$" are not themselves part of the syntax of propositional formulas.

Instead what you have is a shorthand recipe for how to construct a formula. The actual formula that the notation is asking you to imagine is quite long; it starts with

$$ \big( (\neg b_0 \land (b_1 \land b_2 \land b_3 \land b_4 \land b_5)) \lor (b_0 \land (\neg b_1 \land \neg b_2 \land \neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \lor \big( ((\neg b_0 \land \neg b_1) \land (b_2 \land b_3 \land b_4 \land b_5)) \lor ((b_0 \land b_1) \land (\neg b_2 \land \neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \lor \big( ((\neg b_0 \land \neg b_1 \land \neg b_2) \land (b_3 \land b_4 \land b_5)) \lor ((b_0 \land b_1 \land b_2) \land (\neg b_3 \land \neg b_4 \land \neg b_5) ) \big ) \\ \vdots$$

Note that this "unfolded" formula only contains ordinary binary conjunctions and disjunctions, and doesn't contain the dummy variables $k$ and $i$, which were just used as a way to describe the huge formula in a way that would fit on a single line.

You will also note that the huge formula is not particularly clever -- it just contains a disjunct for each of the strings that are to be accepted, and in effect says "accept this string, and accept this string, and accept this string ...".

The exercise must be about finding something better than that (which requires some cleverness). Finding the best representation seems to be quite hard and is probably not expected.

Answer 2

The strings of interest as those that are either increasing or decreasing. Writing $x \Rightarrow y$ as a shorthand for $\lnot x \lor y$, you can characterise them in the follow compact way: $$ \begin{align*} &[(b_1 \Rightarrow b_2) \land (b_2 \Rightarrow b_3) \land (b_3 \Rightarrow b_4) \land (b_4 \Rightarrow b_5)]\\ \lor \quad&[(b_5 \Rightarrow b_4) \land (b_4 \Rightarrow b_3) \land (b_3 \Rightarrow b_2) \land (b_2 \Rightarrow b_1)] \end{align*} $$

If you are being asked to prove that this is the most compact representation, then that will need some more work.