Due: Tuesday, April 7th by 6:00 PM
Complete the problems on the following pages.
Collaboration policy. You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, you must complete the problems in Cozy on your own. Moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.
Late policy. You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.
Solutions submission. Submit your solution at http://cozy.cs.washington.edu
Each part of each task is listed as its own problem.
You have unlimited attempts on each part.
All completed parts get full credit and uncompleted parts get no credit.
Make sure that you understand each step that Cozy performs for you. In Part 2, you will not have Cozy's help to make sure each step is performed correctly.
vs.
vs.
Cozy's documentation for equivalence check problems is available here.
In short: start by filling in the truth table. If the formulas are equivalent, then you should click the “Equivalent” button to confirm that they are equivalent. If the formulas are not equivalent, you should indicate a row where they differ by checking the box on that row and then click the “Different” button to confirm that they are not equivalent.
Prove the following assertions using a sequence of logical equivalences.
In addition to Cozy's documentation, a reference sheet of logical equivalences is on the website.
Hints: For equivalences where one side is much longer than the other, a good heuristic is to start with the longer side and try to apply the rules that will shorten it. In some cases, it may work better to work to shorten both sides to the same expression and then combine those two sequences into one.
Cozy's documentation for equivalence proof problems is available here.
In short: select the rule to apply and a direction — either replacing the left-side with the right-side (“left-to-right”) or vice versa (“right-to-left”) – and then click “Apply”.1 Cozy will apply the rule and produce resulting formula on the line. You can work forward from the top formula or backward from the bottom formula or both! The chain is complete when the two sides reach the same formula.
Prove the following assertions using a sequence of boolean algebra steps.
In addition to Cozy's documentation, a reference sheet of Boolean algebra rules is on the website.
Cozy's documentation for Boolean algebra problems is available here.
In short: instead of giving the rule name and having Cozy produce the next formula, you are asked to type in the formula yourself. Cozy will then automatically check whether that formula can be produced by any combination of commutativity, associativity, distributivity (and over or), identity, domination, idempotency, De Morgan, or double negation. If it can, then you do not need to provide any justification!
If the formula you typed cannot be produced by those rules, Cozy will ask you to identify a rule that can produce the formula, and it will only accept the rule if it does indeed produce that formula. The listed rules include the familiar De Morgan (or over and), negation (now called “complementarity”) and absorption. However, they also include some new rules used only in Boolean algebra: uniting, consensus, and factoring. See Cozy's documentation for precise statements of those new rules.