I am reading Discrete Mathematics 8th Edition by Rosen. On page 30, the author writes
We will sometimes use the notation $\bigvee_{j=1}^{n} p_{j}$ for $p_{1} \vee p_{2} \vee \cdots \vee p_{n}$ and $\bigwedge_{j=1}^{n} p_{j}$ for $p_{1} \wedge p_{2} \wedge \cdots \wedge p_{n}$.
This notation is used in an example a couple of pages later discussing the $n$-queens problem. Modeling $n$-queens problem as a satisfiability problem, we introduce $n^2$ variables $p(i,j)$ for $i=1,2, \ldots, n$ and $j=1,2, \ldots, n$ where $i$ is the row and $j$ is the column, and the proposition is true if there is a queen on that square.
$\bigvee_{j=1}^{n} p(i, j)$ asserts that row $i$ contains at least one queen. I think this is how that would be expanded out for $n=4$..
$p(i, 1) \vee p(i, 2) \vee p(i, 3) \vee p(i, 4)$
so that I can make sense of.
But then the following is given as the assertion that every row contains at least one queen
$$
Q_{1}=\bigwedge_{i=1}^{n} \bigvee_{j=1}^{n} p(i, j)
$$
How is this supposed to be written out, for $n=4$ for example?
Best Answer
If you are already familiar with summation ($\sum$) and product ($\prod$) notation, then $\,\bigwedge_{i=1}^{n} \bigvee_{j=1}^{n} p(i, j)\,$ is analogous to $\,\prod_{i=1}^{n}\sum_{j=1}^{n} p(i, j).\,$ This is not surprising given the origin of Boolean algebra where the value $0$ is the analog of false and $1$ is the analog of true. Further, addition is the analog of logical $\vee$ and multiplication is the analog of logical $\wedge$. It may help that a more explicit notation with parentheses is $\,\bigwedge_{i=1}^{n} \big(\bigvee_{j=1}^{n} p(i, j)\big).\,$ Thus, you expand the inner $\,\bigvee\,$ first and then apply the $\,\bigwedge\,$ next. For example, if $\,n=2\,$ then the expression is $\, (p(1,1)\vee p(1,2))\wedge(p(2,1)\vee p(2,2)).$