Propositions

[Albi]

Guys, can someone help me with this question, I don't know where to start

 

[Dr.Peterson]

View attachment 28438
Guys, can someone help me with this question, I don't know where to start

First, this is not Beginning Algebra; it's logic. I'd put it under Advanced Math.

What I would do to get started, if I were you, is to try a simple case with small numbers, perhaps n=3 or 4, and write out what the expression means. I might call the propositions p, q, r, and s rather than use subscripts, initially, to make it a little less intimidating.

By playing with such a specific case, you will probably get a better feel for what it is about.

 

[Albi]

First, this is not Beginning Algebra; it's logic. I'd put it under Advanced Math.

What I would do to get started, if I were you, is to try a simple case with small numbers, perhaps n=3 or 4, and write out what the expression means. I might call the propositions p, q, r, and s rather than use subscripts, initially, to make it a little less intimidating.

By playing with such a specific case, you will probably get a better feel for what it is about.

I know that its logic but I put it here since there isn't any section about logic.

 

[Albi]

First, this is not Beginning Algebra; it's logic. I'd put it under Advanced Math.

What I would do to get started, if I were you, is to try a simple case with small numbers, perhaps n=3 or 4, and write out what the expression means. I might call the propositions p, q, r, and s rather than use subscripts, initially, to make it a little less intimidating.

By playing with such a specific case, you will probably get a better feel for what it is about.

Can I say, "Based on the definition of the disjunction we know that for the proposition to be true, it is sufficient that only one of the values is true, and since in our case one of p1, p2, ..., pn is at most true then we can conclude the expression is going to be true.

 

[Dr.Peterson]

Can I say, "Based on the definition of the disjunction we know that for the proposition to be true, it is sufficient that only one of the values is true, and since in our case one of p1, p2, ..., pn is at most true then we can conclude the expression is going to be true.

No, that's not what you're being asked! You aren't assuming that one of the p's is true and concluding that the given expression is true; you are to show that the given expression is true IF AND ONLY IF AT MOST ONE of the p's is true. That is entirely different. And the expression is not just one big disjunction.

Please try what I suggested. What does the expression look like if n=3?

 

[Albi]

No, that's not what you're being asked! You aren't assuming that one of the p's is true and concluding that the given expression is true; you are to show that the given expression is true IF AND ONLY IF AT MOST ONE of the p's is true. That is entirely different. And the expression is not just one big disjunction.

Please try what I suggested. What does the expression look like if n=3?

To be honest, I don't understand the expression entirely, what does the first part of the expression mean, I've never seen that notation.

 

[Dr.Peterson]

To be honest, I don't understand the expression entirely, what does the first part of the expression mean, I've never seen that notation.

Then that's the question you should have asked in the first place.

If the problem came from a textbook, then it should define the notation somewhere; does it have a glossary of symbols, or an index?

I've found it very difficult to locate a definition for you, but it's the same idea as sigma notation, where the notations below and above a large conjunction symbol tell you the range of values for an index. For example, [imath]\displaystyle\bigwedge_{i=1}^3 p_i = p_1\wedge p_2\wedge p_3[/imath].

 

[Albi]

Then that's the question you should have asked in the first place.

If the problem came from a textbook, then it should define the notation somewhere; does it have a glossary of symbols, or an index?

I've found it very difficult to locate a definition for you, but it's the same idea as sigma notation, where the notations below and above a large conjunction symbol tell you the range of values for an index. For example, [imath]\displaystyle\bigwedge_{i=1}^3 p_i = p_1\wedge p_2\wedge p_3[/imath].

Thanks a lot, I'm going to check the textbook in case there is a glossary of symbols.

 

[Albi]

No, that's not what you're being asked! You aren't assuming that one of the p's is true and concluding that the given expression is true; you are to show that the given expression is true IF AND ONLY IF AT MOST ONE of the p's is true. That is entirely different. And the expression is not just one big disjunction.

Please try what I suggested. What does the expression look like if n=3

I think I understand the question now, am I being asked to show that the expression is true when only one of [imath]p_{1}, p_{2},\cdots , p_{n}[/imath] is true and the others are false, right?

 

[JeffM]

I think I understand the question now, am I being asked to show that the expression is true when only one of [imath]p_{1}, p_{2},\cdots , p_{n}[/imath] is true and the others are false, right?

That is not quite how I read the question. You are neglecting the phrase “at most.” So you need to consider the case where none of the propositions is true.

I’d take Dr. Peterson’s advice and build a truth table for three propositions.

 

[Albi]

That is not quite how I read the question. You are neglecting the phrase “at most.” So you need to consider the case where none of the propositions is true.

I’d take Dr. Peterson’s advice and build a truth table for three propositions.

Then I'm writing the case for when at most one of them is true:[math](\neg(p_{1} \land p_{2} \land \cdots \land p_{n-1} ) \vee \neg(p_{2} \land p_{3} \land \cdots \land p_{n}))\newline \neg((p_{1} \land p_{2} \land \cdots \land p_{n-1})\land(p_{2} \land p_{3} \land \cdots \land p_{n}))[/math] If at most one of them is true (say [imath]v(p_{2}) = T)[/imath] then [math]\neg((F \land T \land \cdots \land F)\land (T \land F \land \cdots \land F)) \newline \neg(F \land F) = T[/math] now the case when none of the propositions are true, in which the result is the same.

 

[Dr.Peterson]

I think I understand the question now, am I being asked to show that the expression is true when only one of [imath]p_{1}, p_{2},\cdots , p_{n}[/imath] is true and the others are false, right?

You're missing both "at most" and "if and only if", the two phrases I emphasized.

Then I'm writing the case for when at most one of them is true:[math](\neg(p_{1} \land p_{2} \land \cdots \land p_{n-1} ) \vee \neg(p_{2} \land p_{3} \land \cdots \land p_{n}))\newline \neg((p_{1} \land p_{2} \land \cdots \land p_{n-1})\land(p_{2} \land p_{3} \land \cdots \land p_{n}))[/math] If at most one of them is true (say [imath]v(p_{2}) = T)[/imath] then [math]\neg((F \land T \land \cdots \land F)\land (T \land F \land \cdots \land F)) \newline \neg(F \land F) = T[/math] now the case when none of the propositions are true, in which the result is the same.

How does what you wrote here relate to the expression in the problem?

 

[Albi]

You're missing both "at most" and "if and only if", the two phrases I emphasized.

How does what you wrote here relate to the expression in the problem?

[math]\bigwedge_ {i=1}^{n-1}\bigwedge_{j=i+1}^n = (\neg(p_{1} \land p_{2} \land \cdots \land p_{n-1} ) \vee \neg(p_{2} \land p_{3} \land \cdots \land p_{n}))[/math] that's what the expression means.

 

[Dr.Peterson]

[math]\bigwedge_ {i=1}^{n-1}\bigwedge_{j=i+1}^n = (\neg(p_{1} \land p_{2} \land \cdots \land p_{n-1} ) \vee \neg(p_{2} \land p_{3} \land \cdots \land p_{n}))[/math] that's what the expression means.

Not at all!

Please do as I've suggested, and write it out for n=3:

[math]\bigwedge_ {i=1}^{2}\bigwedge_{j=i+1}^3 (\neg p_i\vee\neg p_j) = \left(\bigwedge_{j=2}^3(\neg p_1\vee\neg p_j)\right)\wedge\left(\bigwedge_{j=3}^3(\neg p_2\vee\neg p_j)\right) = \dots[/math]
That provides valuable practice in understanding the notation.

 

[Albi]

Not at all!

Please do as I've suggested, and write it out for n=3:

[math]\bigwedge_ {i=1}^{2}\bigwedge_{j=i+1}^3 (\neg p_i\vee\neg p_j) = \left(\bigwedge_{j=2}^3(\neg p_1\vee\neg p_j)\right)\wedge\left(\bigwedge_{j=3}^3(\neg p_2\vee\neg p_j)\right) = \dots[/math]
That provides valuable practice in understanding the notation.

I wrote it out for n = 3, did I get it right this time?[math]\bigwedge_{i=1}^{2}\bigwedge_{j=i+1}^3 = (\bigwedge_{j=2}^3( \neg p_{1}\vee \neg p_{j})) \wedge (\bigwedge_{j=3}^3 (\neg p_{2} \vee \neg p_{j})= ((\neg p_{1} \vee \neg p_{2}) \land (\neg p_{1} \vee \neg p_{3})) \land(\neg p_{2} \vee \neg p_{3}) \newline= (\neg(p_{1} \land p_{2}) \land \neg (p_{1} \land p_{3})) \land \neg(p_{2} \land p_{3}) \newline= \neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})) \land \neg (p_{2} \land p_{3}) \newline =\neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})\vee (p_{2} \land p_{3}))[/math] now we consider the cases when there is at most one of the p's true and the case where none of the p's are true.

 

[Dr.Peterson]

I wrote it out for n = 3, did I get it right this time?[math]\bigwedge_{i=1}^{2}\bigwedge_{j=i+1}^3 = (\bigwedge_{j=2}^3( \neg p_{1}\vee \neg p_{j})) \wedge (\bigwedge_{j=3}^3 (\neg p_{2} \vee \neg p_{j})= ((\neg p_{1} \vee \neg p_{2}) \land (\neg p_{1} \vee \neg p_{3})) \land(\neg p_{2} \vee \neg p_{3}) \newline= (\neg(p_{1} \land p_{2}) \land \neg (p_{1} \land p_{3})) \land \neg(p_{2} \land p_{3}) \newline= \neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})) \land \neg (p_{2} \land p_{3}) \newline =\neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})\vee (p_{2} \land p_{3}))[/math] now we consider the cases when there is at most one of the p's true and the case where none of the p's are true.

That's right; and you can probably see how this will extend to greater numbers.

Continue ...

But I hope you realize that "the case when there is at most one of the p's true" includes "the case where none of the p's are true". I would have said, "the cases when there is exactly one of the p's true and the case where none of the p's are true".

And, of course, we still need to be sure we do both directions of the "if and only if".

 

[pka]

View attachment 28438
Guys, can someone help me with this question, I don't know where to start

Having taught symbolic logic, I have a nice collection of textbooks. But none has this notation.
So you may want to take this with a grain of salt.
Given that at most one of [imath]p_1,~p_2,~p_3,~\cdots p_n[/imath] is true then each of the disjunctions, [imath]\bf{\left(\neg p_i\vee\neg p_j\right)} (i\ne j)[/imath] must be true. If each of a sequence is conjunctions is true then the whole proposition is true.
Now suppose there were two of these [imath]p_g~\&~p_h[/imath] the were both true then the term [imath]\bf{\left(\neg p_g\vee\neg p_h\right)}[/imath] would be false so the entire conjunction would be false.

 

[Albi]

Having taught symbolic logic, I have a nice collection of textbooks. But none has this notation.
So you may want to take this with a grain of salt.
Given that at most one of [imath]p_1,~p_2,~p_3,~\cdots p_n[/imath] is true then each of the disjunctions, [imath]\bf{\left(\neg p_i\vee\neg p_j\right)} (i\ne j)[/imath] must be true. If each of a sequence is conjunctions is true then the whole proposition is true.
Now suppose there were two of these [imath]p_g~\&~p_h[/imath] the were both true then the term [imath]\bf{\left(\neg p_g\vee\neg p_h\right)}[/imath] would be false so the entire conjunction would be false.

Yeah, but I think the sequence has to do with conjunctions, anyways thanks a lot for the time.

 

[pka]

Yeah, but I think the sequence has to do with conjunctions, anyways thanks a lot for the time.

YES! That is exactly what I said it was. The whole statement is a conjunction of several disjunctions.

 

[Dr.Peterson]

Yeah, but I think the sequence has to do with conjunctions ...

As you showed, it can be seen either as a conjunction of disjunctions (of negations), in the initial form, or as (a negation of) a disjunction of conjunctions, in your final form:

[math](\neg p_{1} \vee \neg p_{2}) \land (\neg p_{1} \vee \neg p_{3})) \land(\neg p_{2} \vee \neg p_{3}) \newline= (\neg(p_{1} \land p_{2}) \land \neg (p_{1} \land p_{3})) \land \neg(p_{2} \land p_{3}) \newline= \neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})) \land \neg (p_{2} \land p_{3}) \newline =\neg((p_{1} \land p_{2}) \vee(p_{1}\land p_{3})\vee (p_{2} \land p_{3}))[/math]

In either form, you can analyze when it is true, and will get the same result.

In the first form, as pka said, if any pair were both true, then the corresponding disjunction would be false, and the entire conjunction would be false.

In the last form, which you evidently prefer, if any pair were both true, then the entire disjunction would be true, and that would be negated.

And so on.