Jorge S. answered • 11/02/22
Tutor
4.9
(94)
Computer Science/Math Tutoring
PROOF REASONS
--------------------------------------------------------------------------------
1. ๐ and ๐ are integers for which ๐|๐ and ๐|๐ (premise)
2. a is an integer (1,simp rule)
3. b is an integer (1,simp rule)
4. a | b (1,simp rule)
5. b | a (1,simp rule)
6. b = ak for some k in Z (4, definition)
7. a = bk for some k in Z (5, definition)
8. b/k = a for some k in Z (6, algebra)
9. a/k = b for some k in Z (7, algebra)
10. b/i = a for a particular i in Z (8, EI rule)
11. a/j = b for a particular j in Z (9, EI rule)
12. (a/j)/i = a (10,11 subst.rule)
13. a/(ji) = a (12, algebra)
14. a = a(ji) (13, algebra)
15. a/a = ji (14, algebra)
16. 1 = ji (15, algebra)
17. j is an integer (10, definition)
18. i is an integer (11, definition)
19. (1 = -1 x -1) and (1 = 1 x 1) (THEOREM)
20. (1 = -1 x -1) (19, simp rule)
21. (1 = 1 x 1) (19, simp rule)
22. 1 x 1 = ji (16,21,transitive)
23. (1 x 1)/i = j (22, algebra)
24. 1/i = j (23, algebra)
25. ------| not (i = 1 or i = -1) (subpremise)
26. ------| i != 1 and i != -1 (25, demorgans law)
27. ------|(i = 0 (26, equivalence)
------| or i is postive but not 1
------| or i is negative but not 1)
28. ------|-----| i = 0 (sub sub premise)
29. ------|-----| 1 x 1 = j x 0 (22,28, subst.rule)
30. ------|-----| 1 x 1 = 0 (29, algebra)
31. ------|-----| 1 = 0 (30, algebra)
32. ------|-----| FALSE (31, CONTRADICTON)
33. ------| not(i = 0) (28 - 32, IP rule)
34. ------|-----| i is positive but not 1 (sub sub premise)
35. ------|-----| 1/i is not an integer (34, definition of Z)
36. ------|-----| 1/i = j states that (24,35 reanalysis)
------|-----| j is not an integer
37. ------|-----| FALSE (17,36 CONTRADICTION)
38. ------| not(i is positive but not 1) (34-37, IP rule)
39. ------| (i is postive but not 1 (27,33, DS rule)
------| or i is negative but not 1)
40. ------| i is negative but not 1 (38,39, DS rule)
41. ------| 1/i is not an integer (34, definition of Z)
42. ------|(1/i = j states that (24,41 reanalysis)
------| j is not an integer)
43. ------| FALSE (17,42, CONTRADICTION)
44. not(not (i = 1 or i = -1) ) (25-27,33,38-43 IP rule)
45. i = 1 or i = -1 (44, double negation)
46. ------| i = 1 (subpremise)
47. ------| b/1 = a (10,46 subst. rule)
48. ------| b = a (47, algebra)
49. ------| a = b (48, symmetric )
50. if i = 1 then a = b (46-49 CP rule)
51. ------| i = -1 (subpremise)
52. ------| b/-1 = a (10,51 subst. rule)
53. ------| -b = a (52, algebra)
54. ------| a = -b (53, symmetric)
55. if i = -1 then a = -b (51-54 CP rule)
56. (a = b) or (a = -b) (45,50,55, CD rule)
57. a = ยฑb (56, definition of ยฑ)
QED
Jorge S.
The solution is a natural deduction formal proof. Rather than listing out the english, the actual step by step logic of the proof is described (though some steps might have been condensed/slight informally done). However, the above also shows WHY proofs are hard. Proofs are literally their own kind of math, and its taught in a logic course or in the logic chapter of a discrete mathematics course. The most important topic is Natural deduction, but many discrete mathematics courses leave this out (probably for time constraints). Natural deduction teaches the RULES of proofs, literally the theory of how proofs work. Next time you get stuck in a proof remember its because, analogically, they are making the students solve differential calculus problems with arithmetic knowledge only. Proofs are also hard because they are investigative problems. It's a lot like writing a program, the steps must follow logically from previous lines. Because of this it may take HOURS to write a concise logical proof for 1 problem.
Report
11/02/22
Jorge S.
the topics required to understand how to do this problem are 0. brief philosophical topics (sounds weird but its recommended) 1. informal logic 2. propositional logic (STRONGLY RECOMMENDED) 3. natural deduction in propositional logic (STRONGLY RECOMMENDED) 4. predicate logic (STRONGLY RECOMMENDED) 5. natural deduction in predicate logic (STRONGLY RECOMMENDED) 6. sets 7. definition of divides | 8. using formal logic to solve the problem Recommended textbooks: A cartoon introduction to philosophy discrete structures logic and computability by Hein Recall that a proposition is a statement that has a truth value. "I like pizza" "all squares are rectangles" "the bubble sort algorithm is correct" "hex is a shorthand for binary" "the light is on or the light is off" "1 is an element of the Natural numbers" "the successor of 1 is 2" "1 + 1 = 2" "You have work tomorrow" Are all examples of statements that have truth value, and are therefore PROPOSITIONS. This looks like a proof problem, so we need to prove the following proposition "If ๐ and ๐ are integers for which ๐|๐ and ๐|๐, then ๐=ยฑ๐." To do this problem we need to first understand the proposition. "If ๐ and ๐ are integers for which ๐|๐ and ๐|๐, then ๐=ยฑ๐." is a conditional proposition, where conditional propositions have the form: IF A THEN B. therefore A would be "๐ and ๐ are integers for which ๐|๐ and ๐|๐" and B would be "๐=ยฑ๐". A is called the antecedent and B is called the consequent. Now proofs are INVESTIGATIVE problems, there isn't going to be a clear cut way to solve them, therefore its going to take a lot and time and thinking to complete it. So its better that I just explain the proof along the way. There are many ways to prove something, but looking at the problem at the top of my head I want to do a DIRECT PROOF. A DIRECT PROOF of a proposition "IF A THEN B" starts by assuming assuming A is true, then using known facts to DERIVE out the proposition B. Therefore a proof can be represented as a sequence of propositions that are all true from their RESPECTIVE premises/theorems (logic is weird so there will be some scenerios that seem to break this rule): 1. A P (Premise aka the statement we assume true) 2. derived statement 3. Derived statement . . . n. B (Our conclusion we are trying to reach) this is the deduction approach to doing proofs I'll go ahead and list out the proof as a sequence of propositions then explain informally after.11/02/22