0
$\begingroup$

I'm working through Discrete Mathematics and its Applications, which early on delves into the following as part of a Sudoku solver:

$$\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9} p(i,j,n)$$

Now I understand $\bigvee_{j=1}^{9} p(i,j,n)$ to be a disjunction of a series expanding into $p(i,1,n) \vee p(i,2,n) \vee \ldots \vee p(i,9,n)$. (Please forgive/correct me if I'm using the wrong terminology).

My problem, now, is that I'm not sure how something like the following would expand:

$$\bigwedge_{i=1}^{2} \bigvee_{j=1}^{2} p(i,j)$$

I know that conjunction distributes over disjunction and vice versa, so I feel perhaps it could expand into the following:

$$[p(1,j) \wedge p(i,1)] \vee [p(2,j) \wedge p(i,2)]$$

I'm thoroughly certain I'm getting this wrong, but I can't seem to find an online resource that discusses this index notation. If somebody could point me in the right direction I'd be hugely grateful.

(If it helps, I'm a programmer, so loop-based analogies and the like are right at home.)

Note: I've read the answers to this question as well as this question, which were suggested as similar questions, but they don't appear to duplicate this.

$\endgroup$
  • $\begingroup$ Obviously on textbooks... See e.g. SG Simpson, Math Log. $\endgroup$ – Mauro ALLEGRANZA Jan 24 '19 at 9:05
  • 1
    $\begingroup$ Expand first the inner connective (e.g. disjunction) and then the outer ones (e.g. conjunctions). $\endgroup$ – Mauro ALLEGRANZA Jan 24 '19 at 9:06
  • 2
    $\begingroup$ Regarding $\bigwedge_{i=1}^{2} \bigvee_{j=1}^{2} p(i,j)$ (working inner first) it is $\bigwedge_{i=1}^{2} [p(i,1) \lor p(i,2)]$. $\endgroup$ – Mauro ALLEGRANZA Jan 24 '19 at 9:16
  • 1
    $\begingroup$ There is nothing specific in this notation; it is like $\sum_{i=1}^{2} \sum_{j=1}^{2} a_{ij}$. $\endgroup$ – Mauro ALLEGRANZA Jan 24 '19 at 9:18
  • 1
    $\begingroup$ If it helps, the expansion is done the same way that double, triple, etc. summations are carried out. See the google search "double summation" + examples, which incidentally led me to this. Also, try the google search "triple summation" + examples. Of course, once you have the expansion, you may want to apply various distributivity laws to rewrite it, and this can wind up getting messy. $\endgroup$ – Dave L. Renfro Jan 24 '19 at 9:20
1
$\begingroup$

As @MauroALLEGRANZA rightly points out, reading a textbook dedicated to the subject (rather than one that necessarily glosses over it) is the answer my silly question deserves.

Be that as it may, it is perhaps not the worst idea to clarify my understanding of the matter.

Edit: The notation under discussion (alongside summation and the like) is an example of an iterated binary operation, described here.

Based on the (very helpful) comments by @MauroALLEGRANZA and @DaveL.Renfro, this notation harks to sigma and pi notation for summation and product operations, respectively. So, working from the inside out:

$$\bigwedge_{i=1}^{2} \bigwedge_{n=1}^{2} \bigvee_{j=1}^{2} p(i,j,n) \equiv \bigwedge_{i=1}^{2} \bigg(\bigwedge_{n=1}^{2} \bigg(\bigvee_{j=1}^{2} p(i,j,n) \bigg) \bigg)$$

With that in mind, the following:

\begin{align} \bigwedge_{i=1}^2 \bigwedge_{n=1}^2 \bigvee_{j=1}^2 p(i,j,n) & \equiv \bigwedge_{i=1}^2 \bigwedge_{n=1}^2 p(i,1,n) \vee p(i,2,n) \\ & \equiv \bigwedge_{i=1}^2 [p(i,1,1) \vee p(i,2,1)] \wedge [p(i,1,2) \vee p(i,2,2)] \\ & \equiv [p(1,1,1) \vee p(1,2,1)] \wedge [p(1,1,2) \vee p(1,2,2)] \\ & \wedge [p(2,1,1) \vee p(2,2,1)] \wedge [p(2,1,2) \vee p(2,2,2)] \end{align}

This final equivalence I understand to be in conjunctive normal form, which is to say a sequence of disjunctive clauses connected by conjunction.

Clearly I have a long, long way to go with all of this. Many thanks in any event to those who took the time to help me understand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.