Week 3 at a glance

We will be learning and practicing to:

• Model systems with tools from discrete mathematics and reason about implications of modelling choices. Explore applications in CS through multiple perspectives, including software, hardware, and theory.

  • Determining the properties of positional number representations, including overflow and bit operations

  • Connecting logical circuits and compound proposition and tracing to calcluate output values

• Translate between different representations to illustrate a concept.

  • Translating between symbolic and English versions of statements using precise mathematical language

• Use precise notation to encode meaning and present arguments concisely and clearly

  • Listing the truth tables of atomic boolean functions (and, or, xor, not, if, iff)

• Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.

  • Evaluating compound propositions

  • Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan’s Law

  • Judging logical equivalence of compound propositions using truth tables

  • Rewriting compound propositions using normal forms

  • Judging whether a collection of propositions is consistent

TODO:

Week 3 Monday: Fixed-width Addition and Circuits

Fixed-width addition: adding one bit at time, using the usual column-by-column and carry arithmetic, and dropping the carry from the leftmost column so the result is the same width as the summands. Does this give the right value for the sum?

In a combinatorial circuit (also known as a logic circuit), we have logic gates connected by wires. The inputs to the circuits are the values set on the input wires: possible values are 0 (low) or 1 (high). The values flow along the wires from left to right. A wire may be split into two or more wires, indicated with a filled-in circle (representing solder). Values stay the same along a wire. When one or more wires flow into a gate, the output value of that gate is computed from the input values based on the gate’s definition table. Outputs of gates may become inputs to other gates.

Example digital circuit:

Draw a logic circuit with inputs \(x\) and \(y\) whose output is always \(0\). Can you use exactly 1 gate?

Week 3 Wednesday: Propositional Logic

Fixed-width addition: adding one bit at time, using the usual column-by-column and carry arithmetic, and dropping the carry from the leftmost column so the result is the same width as the summands. In many cases, this gives representation of the correct value for the sum when we interpret the summands in fixed-width binary or in 2s complement.

For single column:

Draw a logic circuit that implements binary addition of two numbers that are each represented in fixed-width binary:

• Inputs \(x_0, y_0, x_1, y_1\) represent \((x_1 x_0)_{2,2}\) and \((y_1 y_0)_{2,2}\)

• Outputs \(z_0, z_1, z_2\) represent \((z_2 z_1 z_0)_{2,3} = (x_1 x_0)_{2,2} + (y_1 y_0)_{2,2}\) (may require up to width \(3\))

First approach: half-adder for each column, then combine carry from right column with sum of left column

Write expressions for the circuit output values in terms of input values:

\(z_0 = \underline{\phantom{x_0 \oplus y_0\hspace{3in}}}\)

\(z_1 = \underline{\phantom{(x_1 \oplus y_1) \oplus c_0}\hspace{2.5in}}\)

\(z_2 = \underline{\phantom{(c_0 \land (x_1 \oplus y_1)) \oplus c_1}\hspace{2in}}\)

There are other approaches, for example: for middle column, first add carry from right column to \(x_1\), then add result to \(y_1\)

Logical operators aka propositional connectives

Truth tables: Input-output tables where we use \(T\) for \(1\) and \(F\) for \(0\).

Input		Output
		Conjunction	Exclusive or	Disjunction
\(p\)	\(q\)	\(p \land q\)	\(p \oplus q\)	\(p \lor q\)
\(T\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)
\(F\)	\(T\)	\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)	\(F\)	\(F\)

Input	Output
	Negation
\(p\)	\(\lnot p\)
\(T\)	\(F\)
\(F\)	\(T\)

Week 3 Friday: Logical Equivalence

Given a truth table, how do we find an expression using the input variables and logical operators that has the output values specified in this table?

Application: design a circuit given a desired input-output relationship.

Expressions that have output \(mystery_1\) are

Expressions that have output \(mystery_2\) are

Idea: To develop an algorithm for translating truth tables to expressions, define a convenient normal form for expressions.

Definition An expression built of variables and logical operators is in disjunctive normal form (DNF) means that it is an OR of ANDs of variables and their negations.

Definition An expression built of variables and logical operators is in conjunctive normal form (CNF) means that it is an AND of ORs of variables and their negations.

Proposition: Declarative sentence that is true or false (not both).

Propositional variable: Variable that represents a proposition.

Compound proposition: New proposition formed from existing propositions (potentially) using logical operators. Note: A propositional variable is one example of a compound proposition.

Truth table: Table with one row for each of the possible combinations of truth values of the input and an additional column that shows the truth value of the result of the operation corresponding to a particular row.

Logical equivalence : Two compound propositions are logically equivalent means that they have the same truth values for all settings of truth values to their propositional variables.

Tautology: A compound proposition that evaluates to true for all settings of truth values to its propositional variables; it is abbreviated \(T\).

Contradiction: A compound proposition that evaluates to false for all settings of truth values to its propositional variables; it is abbreviated \(F\).

Contingency: A compound proposition that is neither a tautology nor a contradiction.

Label each of the following as a tautology, contradiction, or contingency.

\(p \land p\)

\(p \oplus p\)

\(p \lor p\)

\(p \lor \lnot p\)

\(p \land \lnot p\)

Extra Example: Which of the compound propositions in the table below are logically equivalent?

Review Quiz

1. Fixed-width addition: Recall the definitions of signed integer representations from class: sign-magnitude and 2s complement.

   1. Recall the definitions of signed integer representations from class: sign-magnitude and 2s complement.

      1. What is the least integer that can be represented in sign-magnitude width \(4\)?

      2. What is the greatest integer that can be represented in sign-magnitude width \(4\)?

      3. What is the least integer that can be represented in 2s complement width \(4\)?

      4. What is the greatest integer that can be represented in 2s complement width \(4\)?

   2. 1. In binary fixed-width addition (adding one bit at time, using the usual column-by-column and carry arithmetic, and ignoring the carry from the leftmost column), we get: \[\begin{aligned} &1110 \qquad \text{first summand}\\ +&0100 \qquad \text{second summand}\\ &\overline{0010} \qquad \text{result} \end{aligned}\] Select all and only the true statements below:

         1. When interpreting each of the summands and the result in binary fixed-width 4, the result represents the actual value of the sum of the summands.

         2. When interpreting each of the summands and the sum in sign-magnitude width 4, the result represents the actual value of the sum of the summands.

         3. When interpreting each of the summands and the sum in 2s complement width 4, the result represents the actual value of the sum of the summands.

      2. In binary fixed-width addition (adding one bit at time, using the usual column-by-column and carry arithmetic, and ignoring the carry from the leftmost column), we get: \[\begin{aligned} &0110 \qquad \text{first summand}\\ +&0111 \qquad \text{second summand}\\ &\overline{1101} \qquad \text{result} \end{aligned}\] Select all and only the true statements below:

         1. When interpreting each of the summands and the result in binary fixed-width 4, the result represents the actual value of the sum of the summands.

         2. When interpreting each of the summands and the sum in sign-magnitude width 4, the result represents the actual value of the sum of the summands.

         3. When interpreting each of the summands and the sum in 2s complement width 4, the result represents the actual value of the sum of the summands.

2. Circuits

   1. 1. Consider the logic circuit

         

         Calculate the value of the output of this circuit (\(y_1\)) for each of the following settings(s) of input values.

         1. \(x_1 = 1\), \(x_2 = 1\)

         2. \(x_1 = 1\), \(x_2 = 0\)

         3. \(x_1 = 0\), \(x_2 = 1\)

         4. \(x_1 = 0\), \(x_2 = 0\)

      2. Consider the logic circuit

         

         For which of the following settings(s) of input values is the output \(y_1 = 0\), \(y_2 = 1\)? (Select all and only those that apply.)

         1. \(x_1 = 0\), \(x_2 = 0\), \(x_3 = 0\), and \(x_4 = 0\)

         2. \(x_1 = 1\), \(x_2 = 1\), \(x_3 = 1\), and \(x_4 = 1\)

         3. \(x_1 = 1\), \(x_2 = 0\), \(x_3 = 0\), and \(x_4 = 1\)

         4. \(x_1 = 0\), \(x_2 = 0\), \(x_3 = 1\), and \(x_4 = 1\)

   2. Recall this circuit from class:

      

      Which of the following is true about all possible input values \(x,y,z,w\)? (Select all and only choices that are true for all values.)

      1. The output \(out\) is set to \(1\) exactly when \(x\) is \(0\), and it is set to \(0\) otherwise.

      2. The output \(out\) is set to \(1\) exactly when \((xyzw)_{2,4} < 8\), and it is set to \(0\) otherwise.

      3. The output \(out\) is set to \(1\) exactly when \((wzyx)_{2,4}\) is an even integer, and it is set to \(0\) otherwise.

   3. 1. Consider the logic circuit

         

         For which of the following settings(s) of input values is the output \(y_1 = 0\)? (Select all and only those that apply.)

         1. \(x_1 = 0\), \(x_2 = 0\), \(x_3 = 0\), and \(x_4 = 0\)

         2. \(x_1 = 1\), \(x_2 = 1\), \(x_3 = 1\), and \(x_4 = 1\)

         3. \(x_1 = 1\), \(x_2 = 0\), \(x_3 = 0\), and \(x_4 = 1\)

         4. \(x_1 = 0\), \(x_2 = 0\), \(x_3 = 1\), and \(x_4 = 1\)

      2. Consider the logic circuits

         

         For which of the following settings(s) of input values do the outputs of these circuits have the same value, i.e. \(y_1 = z_1\)? (Select all and only those that apply.)

         1. \(x_1 = 1\), \(x_2 = 1\)

         2. \(x_1 = 1\), \(x_2 = 0\)

         3. \(x_1 = 0\), \(x_2 = 1\)

         4. \(x_1 = 0\), \(x_2 = 0\)

3. Compound Propositions

   1. Recall the definition of DNF (disjunctive normal form) and CNF (conjunctive normal form). In particular, remember that to build an expression in DNF whose output matches a given truth table, we focus on the rows of the truth table that output \(T\); To build an expression in CNF whose output matches a given truth table, we focus on the rows of the truth table that output \(F\). Select all and only true statements about an expression that has output \(?\) in the truth table below:

      Input			Output
      \(p\)	\(q\)	\(r\)	?
      \(T\)	\(T\)	\(T\)	\(T\)
      \(T\)	\(T\)	\(F\)	\(T\)
      \(T\)	\(F\)	\(T\)	\(F\)
      \(T\)	\(F\)	\(F\)	\(T\)
      \(F\)	\(T\)	\(T\)	\(F\)
      \(F\)	\(T\)	\(F\)	\(F\)
      \(F\)	\(F\)	\(T\)	\(T\)
      \(F\)	\(F\)	\(F\)	\(F\)

      1. An expression in DNF that has output \(?\) is \[(p \land q \land r) \lor (p \land q \land \lnot r) \lor (p \land \lnot q \land \lnot r) \lor (\lnot p \land \lnot q \land r)\]

      2. An expression in DNF that has output \(?\) is \[(\lnot p \land \lnot q \land \lnot r) \lor (\lnot p \land \lnot q \land r) \lor (\lnot p \land q \land r) \lor (p \land q \land \lnot r)\]

      3. An expression in CNF that has output \(?\) is \[(p \lor \lnot q \lor r) \land (\lnot p \lor q \lor r) \land (\lnot p \lor q \lor \lnot r) \land (\lnot p \lor \lnot q \lor \lnot r)\]

      4. An expression in CNF that has output \(?\) is \[(\lnot p \lor q \lor \lnot r) \land ( p \lor \lnot q \lor \lnot r) \land ( p \lor \lnot q \lor r) \land (p \lor q \lor r)\]

   2. For each of the following compound propositions, determine if it is in DNF, CNF, both, or neither.

      1. \((x \lor y \lor z) \land (x \land \lnot y \land z)\)

      2. \(\lnot (x \land y \land z) \land \lnot (\lnot x \land y \land \lnot z)\)

4. Logical equivalence.

   For each of the following propositions, indicate exactly one of:

   • There is no assignment of truth values to its variables that makes it true,

   • There is exactly one assignment of truth values to its variables that makes it true, or

   • There are exactly two assignments of truth values to its variables that make it true, or

   • There are exactly three assignments of truth values to its variables that make it true, or

   • All assignments of truth values to its variables make it true.

   1. \(x \land y \land (x \lor y)\)

   2. \(\lnot x \land y \land (x \lor y)\)

   3. \(x \land \lnot y \land (x \land y)\)

   4. \(\lnot x \land (y \lor \lnot y)\)

   5. \(x \land (y \lor \lnot x)\)