Read sections 8.1-8.6 in chapter 8 of the textbook Explorations in Computing.
The commutative rule lets us switch the order of two terms, while the associative rule lets us move parentheses around (or add or remove them) when the connectives are all the same. The above table shows that step 2 was derived from step 1 via the commutative rule, step 3 was derived from step 2 via the associative rule, and step 4 was derived from step 3 via the idempotence rule.
Step Formula Justification (Rule) 1. P ∧ (Q ∧ P) Commutative 2. P ∧ (P ∧ Q) Associative 3. (P ∧ P) ∧ Q Idempotence 4. P ∧ Q
We can also use DeMorgan's law to transform expressions. Here is the proof that ¬(P ∧ Q) ∨ ¬ R is equivalent to ¬ P ∨ ¬ (Q ∧ R):
Similarly. here is the proof that (A ∨ (B ∧ C)) ∧ ¬(A ∨ C) is false, i.e., equivalent to 0:
Step Formula Justification (Rule) 1. ¬(P ∧ Q) ∨ ¬ R DeMorgan's Law 2. (¬ P ∨ ¬ Q) ∨ ¬ R Associative 3. ¬ P ∨ (¬ Q ∨ ¬ R) DeMorgan's Law 4. ¬ P ∨ ¬ (Q ∧ R)
For each of the following proofs, fill in the missing elements.
Step Formula Justification (Rule) 1. [A ∨ (B ∧ C)] ∧ ¬(A ∨ C) Distributive 2. [(A ∨ B) ∧ (A ∨ C)] ∧ ¬(A ∨ C) Associative 3. (A ∨ B) ∧ [(A ∨ C) ∧ ¬(A ∨ C)] Complement: x ∧ ¬ x 4. (A ∨ B) ∧ 0 Dominance: x ∧ 0 5. 0
Step | Formula | Rule |
1. | B ∧ A ∧ C ∧ A | |
? | ||
2. | B ∧ A ∧ A ∧ C | |
? | ||
3. | B ∧ (A ∧ A) ∧ C | |
? | ||
4. | B ∧ A ∧ C | |
? | ||
4. | A ∧ B ∧ C |
Step | Formula | Rule |
1. | A ∧ (A ∨ B) | |
? | ||
2. | (A ∨ 0) ∧ (A ∨ B) | |
? | ||
3. | A ∨ (0 ∧ B) | |
? | ||
4. | A ∨ 0 | |
Identity | ||
5. | ? |
Step | Formula | Rule |
1. | ¬ A ∨ ¬ B ∨ ¬ C | |
? | ||
2. | (¬ A ∨ ¬ B) ∨ ¬ C | |
DeMorgan's Law | ||
3. | ¬(A ∧ B) ∨ ¬ C | |
? | ||
4. | ¬ ((A ∧ B) ∧ C) | |
Associative | ||
5. | ¬ (A ∧ B ∧ C) |
A seven-degment display can be used to form each of the ten decimal digits as shown below.
We can define a circuit abstractly below that requires four Boolean inputs A, B, C, and D, and produces seven Boolean outputs s_{1}, s_{2}, ..., s_{7} to make the segments of the display form digits:
Segment s_{1} should be on for all digits except 1 (0001) and 4 (0100), so a Boolean expression for s_{1} might be: ¬ (¬ A ∧ ¬ C ∧ (B ⊕ D)). This can be simplified using DeMorgan's law to A ∨ C ∨ ¬ (B ⊕ D).
i = 0 while i != 10 do puts i i = i + 1 end
We can also write this code equivalently using an until loop:
i = 0 until i == 10 do puts i i = i + 1 end
Use DeMorgan's Law to convert the following while loops to equivalent until loops. You should focus on translating the while loop condition to an equivalent until loop condition. What the loop computes is irrelevant for the purposes of this question.
x = 0 y = 0 while (x < 5) && (y <= 10) do # some computation with x and y x = x + 1 y = y + 1 end
a = 0 b = 0 c = 0 while (a != 20) || (b == 0 && c < 10) do #some computation with a and b a = a + 1 b = b + 1 c = c + 1 end
Test your program in irb using the MARSLab from RubyLabs. First, make a test machine with your program using the make_test_machine function. Then use the dump function to show how your program is represented in "memory". Then repeat the following until the program halts: execute the step function followed by the dump instruction. Once you are done, copy all of the results from irb into a text file and include this with your homework, along with the MARS program itself, to show that you have tested your solution.
start MOV 0, 1 end start
This is loaded into MARS as follows:
m = make_test_machine("imp.txt", 100)
What does this program do? Explain clearly. (HINT: Look at your textbook!)