# Need formal proof

1. Dec 18, 2011

### renz15

Hello, I'm new here at this forum.

Our teacher gave us this assignment.

Steve would like to determine the relative salaries of three coworkers using two facts. First, he knows that if Fred is not the highest paid of the three, then Janice is. Second, he knows that if Janice is not the lowest paid, then Maggie is paid the most. Is it possible to determine the relative salaries of Fred, Maggie, and Janice from TCSS312A 2002 Discrete Structures Autumn what Steve knows? If so, who is paid the most and who the least? Explain your reasoning.

I already know the answer that Fred is the highest paid and Janice is the lowest by using this reasoning.
(1) if Fred is not the highest paid of the three, then Janice is
(2) if Janice is not the lowest paid, then Maggie is paid the most

If the first statement is true, the Janice will be the highest paid and that will contradict the second statement that says Maggie is paid the most.

If the first statement is false, that would mean that Fred is the highest paid and because of that the second statement will be false and Janice will be the lowest paid.

My problem is I can't think of a way to prove this by using truth table, direct proof or indirect proof.

I've tried to prove it by truth table and here it is.

Symbols:
p = Fred is the highest paid q = Janice is the highest paid
r = Maggie is the highest paid s = Janice is the lowest paid

Premises:
[1] ~p → q = If Fred is not the highest paid of the three, then Janice is. (GIVEN)
[2] ~s → r = If Janice is not the lowest paid, then Maggie is paid the most. (GIVEN)
[3] p v q v r = Only one of the workers can be the highest paid.
[4] q → ~s = Janice cannot be both the highest and the lowest paid at the same time

My conclusion is p -> s. But the rows 2 and 4 have true premises and wrong conclusions. What is the wrong part. And if you can please give other formal proof.
Code (Text):

P   q   r   s   ~p  ~q  ~r  ~s  ~p → q    ~s → r    p v q v r    q  → ~s  p->s
T   T   T   T   F   F   F   F      T       T       T          F          T
T   T   T   F   F   F   F   T      T       T       T          T          F
T   F   T   T   F   T   F   F      T       T       T          T          T
T   F   T   F   F   T   F   T      T       T       T          T          F
T   T   F   T   F   F   T   F      T       T       T          F          T
T   T   F   F   F   F   T   T      T       F       T          T          F
T   F   F   T   F   T   T   F      T       T       T          T          T
T   F   F   F   F   T   T   T      T       F       T          T          F
F   T   T   T   T   F   F   F      T       T       T          F          T
F   T   T   F   T   F   F   T      T       T       T          T          T
F   F   T   T   T   T   F   F      F       T       T          T          T
F   F   T   F   T   T   F   T      F       T       T          T          T
F   T   F   T   T   F   T   F      T       T       T          F          T
F   T   F   F   T   F   T   T      T       F       T          T          T
F   F   F   T   T   T   T   F      F       T       T          T          T
F   F   F   F   T   T   T   T      F       F       F          T          T

Last edited: Dec 18, 2011
2. Dec 18, 2011

### Fredrik

Staff Emeritus
Hello, and welcome.

I'm not sure I understand what this problem is asking. Steve is supposed to determine the "relative salaries" of three coworkers, but what does that mean. It sounds to me that he's only supposed to order them according to their salaries. So what does Steve have to do with anything? You concluded that he is the highest paid. Are we supposed to order a set of four or a set of three? If Steve is in the set, then does the "Janice is" part of the first statement say something different about Janice than the "Maggie is paid the most" part of the second says about Maggie? (Janice is paid the most of the three, but Maggie is objectively paid the most, i.e. paid the most of the four).

3. Dec 18, 2011

### renz15

Oops, sorry, that's a mistake. Fred is the highest paid. I'm gonna edit it right away.

4. Dec 18, 2011

### Fredrik

Staff Emeritus
I should warn you that I've never taken a class about these things, so I don't know exactly what your teacher would consider a "formal proof". I should also tell you that the forum policy is to only offer hints, not complete solutions, so even if I knew exactly what the formal proof should look like, I couldn't just tell you.

I assume that you know that even if you prove that p→s, that doesn't mean that you have proved that the correct order is Fred, Maggie, Janice.

You will have to be more careful with some of your statements if you're going to hand this in to your teacher. I first read "if the first statement is true" as "if axiom 1 is true", but it seems that you meant "if Fred is not paid the most". (Axiom 1 can be true even if Janice isn't paid the most).

There are a few different ways to find the correct order. The method you used is fine (if my understanding of what you meant is correct). By the way, axiom 1 alone implies that Maggie isn't paid the most. Another method is to just write down the six possible ways to order the three employees

FJM
FMJ
JFM
JMF
MFJ
MJF

and then for each one, write down the numbers of the axioms that are made false by that ordering.

Uh, wait, can we be sure that they all have different salaries?

Last edited: Dec 18, 2011
5. Dec 18, 2011

### Deveno

the key to solving this formally, is to realize there is some relationship between q and s. they aren't independent (they are both statements about Janice).

i don't think p→s is the "proper" conclusion. that still doesn't tell us "the answer", it tells us that:

FJM

is one valid combination (there might be others that don't start with F). a "definitive" statement would be:

p&s, which leaves no doubt.

6. Dec 18, 2011

### Fredrik

Staff Emeritus
Assuming that they all have different salaries...

It's much easier (for me at least) to treat this with a mathematical notation. F,J and M are variables that represent members of the set {1,2,3}. No two of them have the same values.

Axiom 1: F≠1 → J=1
Axiom 2: J≠3 → M=1

It's very easy to use the axioms to prove that M≠1, and that this implies F=1,M=2,J=3. (Consider the contrapositives of the axioms). Isn't that the formal proof you're looking for? If you want to, you can do it with the mathematical notation first, and then translate it into statements about your p,q,r,s.

Also, if you write down the six orderings, and for each one determine the truth values of the axioms, you will see that only FMJ is consistent with both being true. Would that not be considered a formal proof?

Is there a specific set of proof rules that you're allowed to use?

7. Dec 18, 2011

### renz15

^
We are only allowed to use proof by using truth table, direct proof, indirect proof and proof by resolution.

EDIT:
Somebody told me that my 3rd premise is wrong and the correct one is [P > ~(Q v R)] & (~Q v ~R) and the conclusion should be p & s. When I tried it using truth table, it worked. Now my problem is I don't quite understand why it should be [P > ~(Q v R)] & (~Q v ~R). Can you explain it to me? Thanks~

Last edited: Dec 18, 2011
8. Dec 18, 2011

### Fredrik

Staff Emeritus
I'm not familiar with the terms "direct proof", "indirect proof" and "proof by resolution". Can you explain what you mean by those? Suppose that you prove that Maggie is not paid the most by deriving a contradiction from the assumption that she is, and then prove that "Maggie is not paid the most" implies both "Janice is paid the least" and "Fred is paid the most". Does such a proof fall into one of those three categories?

Note that each of the orderings, FJM, FMJ, etc., assigns a truth value to statements like "Fred is paid the most". What if you for each ordering write down a truth table for each of the axioms to show that only FMJ will make both axioms true? This will clearly work, but it seems like an unnecessary amount of work.

Edit: If you're looking for something really super formal, like the kind of proofs discussed here, where at each step, you explain which proof theory axioms you use, then I think you would need to post those axioms. Note that the first proof in that post tells us that if p and q are axioms, then "p and q" is a theorem. I thought that was kind of amusing at the time.

Last edited: Dec 18, 2011
9. Dec 18, 2011

### renz15

Those proofs are done using the rules of replacement and rules of inference (e.g. modus tollen, modus ponens, dilemma, contapositive, material implication.)

And I'm going to repost this.
Now, this is my only problem. It says, [P then not(q or r)] and (not q or not r). Please explain why it should be like that or can you think of a more easily understandable premise(because I'm suppose to explain it to my classmates) to say that at most one of Fred, Janice and Maggie is the highest paid.

10. Dec 18, 2011

### Fredrik

Staff Emeritus
The problem with "p or q or r" is that this is true iff at least one of p,q and r is true. I think you want a statement that's true iff exactly one of p, q and r is true. Maybe you should use a truth table to find out if
"p implies not (q or r)" and "not q or not r" ​
is a statement of that sort. Hm, the second part ensures that q and r are not both true, and the first part only ensures that if p is true, then q and r are both false. So I'd say that the statement doesn't have what I thought was the desired property. The statement is true if p,q and r are all false. Edit: No, it's not. My mistake. Maybe it does have the desired property then.

I'm going to bed soon, and I won't be here for most of tomorrow, but I'm sure someone else can help out. There are certainly people here who are better at this stuff than I am.

Last edited: Dec 18, 2011
11. Dec 20, 2011

### praeclarum

Assume ~p. Then, by (1), q. Then, by (4), ~s. Then by (2), r. But ~(q^r). So it is a contradiction. Therefore, p.