How to interpret \bigwedge notation in discrete math

logicnotationpropositional-calculus

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.

Best Answer

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<j\le n$, 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<j\le n}(\neg p_i\lor\neg p_j)\,.\tag{1}$$

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<j\le n$ are true; if even one of them is false, $(1)$ is also false.

Suppose that $1\le i<j\le n$, 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<j\le n$, 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.

Related Question