Computing and Data Science

Logic

Sign in to Overleaf and use this template to write your solutions. Here is a \(\LaTeX\) reference sheet.

These exercises are intended to be completed by hand.
  1. Given the truth table: \[\begin{array}{|c c|c|} \hline \rule{0pt}{2.5ex} A & B & Output \\ \hline 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \hline \end{array} \]
    1. Write a Boolean expression for this truth table.
    2. Draw the corresponding circuit.
  2. Write the Boolean expression and truth table for the circuit below.
  3. Choose four of the following Boolean expressions. Write the truth table and draw the corresponding circuit diagram.
    1. \(\quad A \land (A \lor B) \)
    2. \( \quad A \lor (A \land B) \)
    3. \( \quad (A \lor B) \land (\neg A \lor B) \)
    4. \( \quad A \lor \neg A \)
    5. \( \quad \neg ( A \land B ) \)
    6. \( \quad \neg A \lor \neg B \)
    7. \( \quad \neg (A \lor B) \)
    8. \( \quad A \land \neg B \)
    9. \( \quad \neg (A \land B \lor C) \)
    10. \( \quad \neg \neg (A \lor B) \)
    11. \( \quad \neg(A \land B) \lor (B \land \neg C) \)
    12. \( \quad (A \land \neg B) \lor (\neg A \land B) \)
  4. An Exclusive OR, or XOR, will output True only if the inputs are different. We write \(A\) XOR \(B\) as \[A \oplus B\] and have the truth table: \[\begin{array}{|c c|c|} \hline \rule{0pt}{2.5ex} A & B & A \oplus B \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \hline \end{array} \] Using AND, OR, and NOT, create a circuit that will output \(A \oplus B\).
  5. Create a circuit for adding two 1-bit numbers. This circuit takes two input bits, \(b_1\) and \(b_2\), and has two output bits, \(s_2\) and \(s_1\text{.}\) When adding two 1-bit numbers together, we can get \(0\), \(1\), or \(10\), which is why we need two bits for the output.
    1. Create the truth tables for \(s_2\) and \(s_1\text{.}\)
    2. Draw the circuit.
  6. A famous puzzle goes like this:
    1. The Brit lives in the Red house.
    2. The Swede keeps Dogs as pets.
    3. The Dane drinks Tea.
    4. The Green house is exactly to the left of the White house.
    5. The owner of the Green house drinks Coffee.
    6. The person who smokes Pall Mall rears Birds.
    7. The owner of the Yellow house smokes Dunhill.
    8. The man living in the centre house drinks Milk.
    9. The Norwegian lives in the first house.
    10. The man who smokes Blends lives next to the one who keeps Cats.
    11. The man who keeps Horses lives next to the man who smokes Dunhill.
    12. The man who smokes Blue Master drinks Beer.
    13. The German smokes Prince.
    14. The Norwegian lives next to the Blue house.
    15. The man who smokes Blends has a neighbour who drinks Water.
    Who owns the fish?

    It will be nice to find the answer, but the important piece of this puzzle is the logic. As you solve, you will make conclusions based on what you already know. Write logical expressions (using AND, OR, and NOT) that demonstrate why each conclusion must be true. For example,
    • The Norwegian lives in the first house, therefore the Brit does NOT live in the first house AND the Swede does NOT live in the first house AND the Dane does NOT live in the first house AND the German does NOT live in the first house.
    • The Brit lives in the Red house AND the Brit does NOT live in the first house, therefore...

    You do not need to completely solve the puzzle in this manner, but it would also be good for you to solve the puzzle!