# How do I interpret \bigwedge notation in discrete math?

I started reading Discrete Mathematics and Its Applications (Eighth Edition) by Kenneth H. Rosen and came across a problem that assumes knowledge not discussed in the book. The question reads as follows:

If $$p_1, p_2,…, p_n$$ are n propositions, explain why

$$\bigwedge_{i=1}^{n-1} \bigwedge_{j=i+1}^n (\neg p_i \vee \neg p_j)$$

is true if and only if at most one of $$p_1, p_2, ...p_n$$ is true.

From my research, it seems $$\bigwedge$$ denotes that I should AND each term together (what does this really mean?). I do not see why at least one of the propositions above need to be True. If someone could break down how to go about solving this I would be very appreciative. The fuller the explanation the more I would benefit as I think I am interpreting the problem incorrectly.

• The interpretation here seems wrong, it seems that when $n=2$ the expression reduces to $\neg p_1 \vee \neg p_2$ i.e. at least one of the two propositions is false. Are you sure that both symbols are $\bigwedge$, rather than one of them being $\bigvee$ (written \bigvee in LaTeX)?
– Ian
Feb 10, 2021 at 19:44
• This is definitely incorrect: the conjunction is true if and only if each term $\neg p_i\lor\neg p_j$ is true, which is the case if and only if at most one of the propositions $p_i$ is true. Feb 10, 2021 at 19:54
• @Ian I apologize. There was a mistake in what I have written, it should read "if at most one of..." rather than "if at least..." I have edited my question. Everything else is the same as the text. Feb 10, 2021 at 19:56

Yes, it’s a conjunction: $$\bigwedge$$ bears the same relationship to $$\land$$ as $$\sum$$ bears to $$+$$. Thus, for example, $$\bigwedge_{i=1}^3p_i$$ means exactly the same thing as $$p_1\land p_2\land p_3$$.

In the double conjunction $$\bigwedge_{i=1}^{n-1}\bigwedge_{j=i+1}^n$$ each value of $$i$$ from $$1$$ through $$n-1$$ is paired with each value of $$j$$ from $$i+1$$ through $$n$$; this has the effect of running through all pairs $$\langle i,j\rangle$$ of indices with $$1\le i, so

$$\bigwedge_{i=1}^{n-1}\bigwedge_{j=i+1}^n(\neg p_i\lor\neg p_j)$$

is precisely equivalent to

$$\bigwedge_{1\le i

If $$n=4$$, for instance, this is

\begin{align*} &(\neg p_1\lor\neg p_2)\land(\neg p_1\lor\neg p_3)\land(\neg p_1\lor\neg p_4)\\ &\land(\neg p_2\lor\neg p_3)\land(\neg p_2\lor\neg p_4)\land(\neg p_3\lor\neg p_4)\,. \end{align*}

The net effect is to take the conjunction of all pairs $$\neg p_i\lor\neg p_j$$ for distinct $$p_i$$ and $$p_j$$.

The conjunction $$(1)$$ is true precisely when all of the disjunctions $$\neg p_i\lor\neg p_j$$ with $$1\le i are true; if even one of them is false, $$(1)$$ is also false.

Suppose that $$1\le i, and $$p_i$$ and $$p_j$$ are both true. Then $$\neg p_i$$ and $$\neg p_j$$ are both false, so $$\neg p_i\lor\neg p_j$$ is false, and therefore $$(1)$$ is also false. In other words, if two or more of the propositions $$p_1,\ldots,p_n$$ are true, then $$(1)$$ is false. Now suppose that at most one of these propositions is true. If $$1\le i, then at least one of $$p_i$$ and $$p_j$$ is false, so at least one of $$\neg p_i$$ and $$\neg p_j$$ is true, and therefore $$\neg p_i\lor\neg p_j$$ is true. Thus, each of the disjunctions $$\neg p_i\lor\neg p_j$$ is true, and therefore their conjunction $$(1)$$ is true. Thus, we have shown that $$(1)$$ is true if and only if at most one of the propositions $$p_1,\ldots,p_n$$ is true.

• Dang, beat me to it. Feb 10, 2021 at 20:05