Not Programming but Discrete Math Problem (logic and propositions)

xSnowmaNx

Gawd
Joined
Aug 11, 2004
Messages
708
I had posted in general mayhem but it seems that was a bad idea http://www.hardforum.com/showthread.php?t=1388879

I'm going to guess this is the best place for me to post seeing as how computer science has strong ties to discrete math.

Here's my question:

Let p, q, and r be the propositions

p : Grizzly bears have been seen in the area.
q : hiking is safe on the trail
r : berries are ripe along the trail

Write these propositions using p, q, and r and logical connectives.

For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area.

The answer is: (q -> (~r ^ ~p)) ^ ~((~r ^ ~p) -> q)

The question I have is, WHY?

This is purely a question on the semantics and interpretation of the sentence as far as I am concerned. I am having huge difficulty in understanding how the words "it is necessary but not sufficient" bring about a conjunction of two different implications. Maybe I just don't understand English?

In case anyone doesn't know:

~ - Negation
^ - conjunction/and
-> - implication (if,then)
 
"necessary" is a long way of saying "implies". Think about the meaning of implication: p->q means that if p is true, q must necessarily be true, but not necessarily the inverse (if the inverse was true, it would be biconditional).

That gives us q -> "berries not be ripe along the trail and for grizzly bears not to have been seen in the area."
Filling in the other two, I get "q -> (~r ^ ~p)".

But the problem says "necessary AND not sufficient". Technically, for all we know from that previous statement, ~r ^ ~p could be sufficient for q (that is, (~r ^ ~p) -> q). Thus, we must add another clause showing that it is in fact NOT sufficient, which is where the second half comes in.
 
I had a quick chat with one of my teachers about this problem, and I've got some of it cleared up, but I'm still having great difficulty in the interpretation of this problem. After my discussion with my teacher, I have come to the conclusion that this problem is explicitly worded in this fashion to make a clear note that p -> q, but not the other way around. Is this correct?

The biggest problem I'm having is with the words necessary and sufficient. Neither of these words were discussed in its use for logic in my class and my book hardly explains it. Perhaps it is assumed people know the absolute definition of these words?

Take for example, the problem I had posted:

Let p, q, and r be the propositions

p : Grizzly bears have been seen in the area.
q : hiking is safe on the trail
r : berries are ripe along the trail

Write these propositions using p, q, and r and logical connectives.

For hiking on the trail to be safe, it is necessary but not sufficient that berries not be ripe along the trail and for grizzly bears not to have been seen in the area.

When I read this sentence the first time, I had translated it in my mind to read it something like this:

For hiking on the trail to be safe, you need to have, but the condition was not met that berries not be ripe along the trail and for grizzly bears not to have been seen in the area.

So I ended up with an answer like so:

~ (~r ^ ~p) -> q

But my answer is clearly wrong because not only am I missing half of the answer, but the half I do have isn't even correct anyways.

So now I'm wondering what the exact meanings of necessary and sufficient are. Based on my readings, discussions, etc, I have come to the conclusion that necessary is used to express the conclusion of a hypothesis, is this correct? So:

q is necessary for p = p -> q
a necessary condition for p is q = p -> q

And sufficient is used to express the hypothesis for a conclusion? So:

p is sufficient for q = p -> q
a sufficient condition for q is p = p -> q
 
Arainach did a pretty good job of explaining it. Perhaps in simpler terms though:


This states ~r ^ ~p is necessary for q:
q -> (~r ^ ~p)
In English, if the trail is safe (q) it implies (->) that there are no bears (~p) and (^) no ripe berries (~r).



This states that ~r ^ ~p is not sufficient for q:
~( (~r ^ ~p) -> q )
In English, it is not true (~) that no ripe berries (~r) and (^) no bears(~p) are sufficient (->) for safe hiking (q).


Necessary and sufficient mean the same thing in logical terms as they do in real life. Often I'll get caught up in trying to interpret their strict logical definition, but I find it's easier just to consider their colloquial English meaning.
 
necessary means condition a must absolutely be present. sufficient means it can be present by itself and requires no other condition to be met.

lightning is necessary and sufficient for thunder. thunder is necessary and sufficient for lightning.
 
Here's how I would explain it, and work with me here

Use Lateral Thinking for this sort of problem.

q = the control value for being able to safely travel on this trail

this value is controlled by (~r ^ ~p)

"~" means that the variable is ~somewhere~ around that value, not an exact value

r = the chance of berries existing on the trail you are traveling

r affects p

p = the chance that a bear will be on that trail

(~r ^ ~p) is an exponential equation (r raised to the power of p)

thus, the more berries along the trail the more bears there will be; the higher this coefficient is, the less safe the trail becomes.
 
Back
Top