Boolean representation of logical statements of more than two extreme conditions

Question

I had a question to determine the highest and and lowest and the middle paid of three employees. I tried to solve the problem using logical values T or F, then getting the connection between the truth tables, but I got stuck since the first statement concerns the highest and the second concerns the lowest paid and there is a hole about the middle one that I could't represent, using truth values since not highest may be lowest or middle and vice versa. The question is below from Rosen discrete math book.

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 what Steve knows? If so, who is paid the most and who the least? Explain your reasoning.

Answer 1

You could do this with a truth table, but it will be a good bit of work.

As atomic claims we can define:

$F1$: Fred has the highest pay

$F2$: Fred has the middle pay

$F3$: Fred has the lowest pay

(Same for Janice and Maggie)

Now add the following claims to express that Fred has exactly one of the highest, middle, and lowest pays:

$F1 \lor F2 \lor F3$

$\neg (F1 \land F2)$

$\neg (F1 \land F3)$

$\neg (F2 \land F3)$

(Same for Janice and Maggie)

And also add that exactly one of the three people has the highest pay:

$F1 \lor J1 \lor M1$

$\neg (F1 \land J1)$

$\neg (F1 \land M1)$

$\neg (J1 \land M1)$

(Same for middle and lowest pay)

And of course we have the given information:

$\neg F1 \rightarrow J1$

$\neg J3 \rightarrow M1$

Put all $26$ claims on a $2^9=512$ row truth-table, and you'll get your answer! Easy peasy! :)

If that truth-table sounds like a bit much ... here is a formal proof in Fitch (I only included the relevant assumptions of the 26 as the premises):

$ \def\fitchproof#1#2{\begin{array}{|l}#1 \\ \hline #2\end{array}} $

$\fitchproof{ 1. \neg(F1 \land M1) \\ 2. \neg(J1 \land M1) \\ 3. ~\neg(J1 \land J3) \\ 4. \neg (J3 \land M3) \\ 5. M1 \lor M2 \lor M3 \\ 6. \neg F1 \rightarrow J1 \\ 7. \neg J3 \rightarrow M1} { \fitchproof{8. M1} { \fitchproof { 9. F1 } { 10. F1 \land M1 \quad \land \text{ Intro } 9,8 \\ 11. \bot \quad \bot \text{ Intro } 10,1 } \\ 12. \neg F1 \quad \\ 13. J1 \quad \rightarrow \text{Elim}\\ 14. J1 \land M1 \quad \land \text{ Intro } 13,8\\ 15. \bot \quad \bot \text{ Intro } 14,2 } \\ 16. \neg M1 \quad \neg \text{ Intro } 8-15\\ \fitchproof { 17. \neg J3 } { 18. M1 \quad \rightarrow \text{ Elim } 17,7\\ 19. \bot \quad \bot \text{ Intro } 18,16 } \\ 20. J3 \quad \neg \text{ Intro } 17-19\\ \fitchproof { 21. \neg F1 } { 22. J1 \quad \rightarrow \text{ Elim } 21,6\\ 23. J1 \land J3 \quad \land \text{ Intro } 22,20\\ 24. \bot \quad \bot \text{ Intro } 23,3 } \\ 25. F1 \quad \neg \text{ Intro } 21-24\\ \fitchproof { 26. M1 } { 27. \bot \quad \bot \text{ Intro } 26,16\\ 28. M2 \quad \bot \text{ Elim } 27 } \\ \fitchproof { 29. M2 } { } \\ \fitchproof { 30. M3 } { 31. J3 \land M3 \quad \land \text{ Intro } 20,30\\ 32. \bot \quad \bot \text{ Intro } 26,16\\ 33. M2 \quad \bot \text{ Elim } 32 } \\ 34. M2 \quad \lor \text{ Elim } 5,26-28,29-29,30-32 } $

Answer 2

OK, claim $1$: if Fred is not the highest paid, then Janice is. This means Maggie is not the highest paid (because then claim $1$ becomes $True\implies False$ which cannot be).

Claim $2$: If Janice is not the lowest paid, then Maggie is paid the most. However, we know Maggie is not paid the most, so Janice is the lowest paid (because $A\implies B$ is the same as $\neg B\implies \neg A$, so we know if Maggie is not paid the most, then Janice is the lowest paid, and we know Maggie is not paid the most. Therefore, Janice is the lowest paid).

Now, since Janice is the lowest paid, we know (because Maggie is not the highest paid) that Fred must be the highest paid. So its Fred>Maggie>Janice.

---

Brute force:

Claim one says: "If $F$ is not the highest, then $J$ is the highest.

Claim two says: "If $J$ is not the lowest, then $M$ is the highest.

There are only $6$ possible ways this goes:

• F>M>J - This option is possible

• F>J>M - This option is not possible because it conflicts with claim $2$.

• M>F>J - This option conflicts with claim $1$

• M>J>F - This option conflicts with claim $1$

• J>M>F - This option conflicts with claim $2$

• J>F>M - This option conflicts with claim $2$

  So the only possible option is F>M>J.

Answer 3

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.

$$(F{\lt}J\vee F{\lt}M)\to (F{<}M{<}J\vee M{<}F{<}J)\tag 1$$

Clearly that means that: $$F{<}J\to (F{<}M{<}J\vee M{<}F{<}J) \tag{1.1}$$ ... and, less obviously, that: $$F{<}M\to (F{<}M{<}J)\tag {1.2}$$

Second, he knows that if Janice is not the lowest paid, then Maggie is paid the most.

$$(F{<}J\vee M{<}J)\to (F{<}J{<}M\vee J{<}F{<}M) \tag 2$$

Likewise, this infers that: $$F{<}J\to F{<}J{<}M \tag{2.1}$$ ... and also that: $$M{<}J\to \bot\tag{2.2}$$

Is it possible to determine the relative salaries of Fred, Maggie, and Janice from what Steve knows? If so, who is paid the most and who the least? Explain your reasoning.

Fred cannot be paid less than Jannice (1.1 and 2.1 contradict), and Fred cannot be paid less than Maggie (1.2 and 2.1 contradict), and Maggie cannot be paid less than Jannice (2.2).   Which means Fred is paid the most, and Jannice the least. $$J{<}M{<}F\tag{done}$$