4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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)? $\endgroup$
    – Ian
    Feb 10, 2021 at 19:44
  • $\begingroup$ 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. $\endgroup$ Feb 10, 2021 at 19:54
  • $\begingroup$ @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. $\endgroup$
    – ssstier
    Feb 10, 2021 at 19:56

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Dang, beat me to it. $\endgroup$ Feb 10, 2021 at 20:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .