Lecture notes for CSC 173, Thurs. Nov. 18 through Tues. Nov. 30, 2004 Read Chaps. 12 and 13. Much of this material will be review from Math 150 or elsewhere. ------------------------------------------------------------------------ propositional logic v. 1st-order predicate logic (v. higher-order calculi) applications to circuits theorem proving computing (Prolog) ======================================================================== Propositional Logic Propositional logic is a mathematical model (or algebra) for reasoning about the truth of logical expressions (propositions). Logical expressions can be manipulated according to algebraic laws, allowing us to reason formally (using deductive reasoning) about a set of premises. Resolution is one particularly important technique that can be used to prove a hypothesis from a set of premises. Propositional logic can be used in: * the composition of logical expressions in programs * automatic reasoning systems * deductive proofs of program correctness * the programming language Prolog, as a model of computation * the design of digital circuits Although propositional logic is powerful enough to be used in these many different contexts, like any formal system, there are limits to its applicability. ------------------------------------------------------------------------ Logical Expressions We can define logical expressions using a recursive definition: 1. Propositional variables (whose value is TRUE or FALSE) and the propositional constants TRUE and FALSE are logical expressions. 2. If LE1 and LE2 are logical expressions, then LE1 AND LE2 is a logical expression, whose value is TRUE if both LE1 and LE2 have the value TRUE, and is FALSE otherwise. 3. If LE1 and LE2 are logical expressions, then LE1 OR LE2 is a logical expression, whose value is TRUE if either LE1 or LE2 have the value TRUE, and is FALSE otherwise. 4. If LE1 is a logical expression, then NOT LE1 is a logical expression, whose value is TRUE is LE1 has the value FALSE, and is FALSE otherwise. The precedence levels of logical operators is: 1. NOT \not ~ ! 2. AND \wedge & && 3. OR \vee | || As usual, we use parentheses to override precedence. By assigning values to the variables in a logical expression, we also assign a value to the expression itself. Example: given the expression "(p AND q) OR r", if p=TRUE, q=TRUE, and r=FALSE, then the value of the expression is TRUE. ------------------------------------------------------------------------ Boolean Functions and Truth Tables The meaning (or value) of a logical expression is a Boolean function from the set of possible assignments of truth values for the variables in the expression to the values {TRUE,FALSE}. Example: given the expression "(p AND q) OR r", we can describe the Boolean function that determines the value of the expression by considering all combinations of value assignments for p, q, and r. p q r (p AND q) OR r ------------------------------ T T T T T T F T T F T T T F F F F T T T F T F F F F T T F F F F The above table describing the Boolean function "(p AND q) OR r" is called a truth table. In a truth table, there is a column for each variable in the expression, and each row in the table corresponds to an assignment of values to variables. The final column gives the value of the expression for the particular set of variable assignments given in the row. We can define the basic operators in terms of a truth table as follows (where we use 1 and 0 instead of TRUE and FALSE): p q p AND q p OR q NOT p ------------------------------------ 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 Note that a truth table for a function of N variables has 2^N rows. ------------------------------------------------------------------------ Other Functions of Two Variables We have seen a few functions of two variables, but there are many more. In fact, there are 16 different Boolean functions of two variables. Why 16? Because each function corresponds to a different assignment of values to the last column of a truth table with four rows, and there are 16 different such assignments. In general, there are 2^2^N different Boolean functions of N variables. Here are some additional functions of two variables that are frequently used: p q p->q p==q p NAND q p NOR q ------------------------------------------- 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 0 Comments on these functions: * Implication: "p -> q" or "p implies q" means that whenever p is TRUE, so is q. The only way "p -> q" can be FALSE, is if p is TRUE, and q is FALSE. p->q == ~p | q * Equivalence: "p == q" means that p and q have the same value. * NAND: "p NAND q" is the same as "NOT (p AND q)". * NOR: "p NOR q" is the same as "NOT (p OR q)". * NAND and NOR have the very nice property that they are easily implemented by simple electronic circuits (take ECE to learn how). They are also *complete* (see below): you can build any Boolean function out of NAND or NOR. * Equivalence is generally assumed to have lowest precedence. We can add NAND and NOR to the hierarchy, but that gets confusing enough that your safest just sticking in the parentheses. ------------------------------------------------------------------------ Computing Expressions with Truth Tables We can compute the value of an expression using truth tables. We create a table for all possible values of the variables, and all subexpressions in the expression. Compute the value of the following expression E for all possible truth assignments: (p -> q) -> (q -> r) p q r p->q q->r E --------------------------- 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 Note that the column for the value of q->r is the same as the column for the value of the entire expression E. We've established the equivalence of those two columns, which means: (p -> q) -> (q -> r) == q->r. If we draw an expression tree for E, we build truth table columns from the leaves up. ------------------------------------------------------------------------ Generating Expressions from Functions We are often given a Boolean function in truth table form and must derive a corresponding logical expression. For example, digital circuits are constructed from digital elements that compute the basic Boolean operations (such as NOT and NAND). Given a specific function expressed as the results of variable assignment (such as a function that adds two bits together and produces a sum and a carry bit), expressed in truth table form, we'd like the corresponding logical expression so that we can construct a circuit for the function. We can construct such a logical expression directly from the truth table for the function. The resulting expression uses only AND, OR, and NOT as operators. ------------------------------------------------------------------------ Example: Exclusive Or Expression from Truth Table Exclusive or (XOR) is another well-known function of two variables. The truth table for XOR is: p q XOR --------------- 0 0 0 0 1 1 1 0 1 1 1 0 We can construct an expression for XOR in terms of AND, OR, and NOT, using the following reasoning: * The second row tells us that p XOR q is TRUE when p is FALSE and q is TRUE. In other words, p XOR q is TRUE if NOT p AND q is TRUE. * The third row tells us that p XOR q is TRUE when p is TRUE and q is FALSE. In other words, p XOR q is TRUE if p AND NOT q is TRUE. * The other rows tell us that p XOR q is FALSE in all other cases. * So p XOR q is TRUE if NOT p AND q is TRUE, or if p AND NOT q is true. From the above, we determine that the following is a logical expression for the function p XOR q: (NOT p AND q) OR (p AND NOT q) ------------------------------------------------------------------------ Conjunctive and Disjunctive Normal Forms A Boolean expression is in disjunctive normal form if it is expressed as the sum (OR) of products (AND). That is, a Boolean expression B is in disjunctive normal form if it is written as: A1 OR A2 OR A3 OR ... An where each Ai is expressed as T1 AND T2 AND ... AND Tm where each Ti is either a simple variable, or the negation (NOT) of a simple variable. Each of the terms Ai is called a minterm. A Boolean expression is in conjunctive normal form if it is expressed as the product (AND) of sums (OR). That is, a Boolean expression B is in conjunctive normal form if it is written as: O1 AND O2 AND O3 AND ... On where each Oi is expressed as T1 OR T2 OR ... OR Tm where each Ti is either a simple variable, or the negation (NOT) of a simple variable. Each of the terms Oi is called a maxterm. ------------------------------------------------------------------------ Normal Forms in Truth Tables Conjunctive and disjunctive normal forms are duals of each other; either one may be used to generate a logical expression from a truth table. With these normal forms, we can be more precise about how to generate a logical expression from a truth table. To construct a logical expression in disjunctive normal form from a truth table: * Build a minterm for each row of the table where the function is true. * For each variable whose value is 1 in that row, we include the variable in the minterm; if a variable is 0 in that row, we include the negation of the variable in the minterm. * The expression consists of the OR of all the minterms. We could, of course, construct an expression in conjunctive normal form by using maxterms and AND. (One term for every *false* row, each of which says how to prevent that row.) ------------------------------------------------------------------------ A Logical Expression for an Adder A binary integer adder can be constructed from a series of one-bit adders. A one-bit adder takes two one-bit operands (x and y) and a carry bit from the previous one-bit adder (ci), and produces the sum of those bits, and a carry-out bit (co). We can define a Boolean function corresponding to the adder in the form of a truth table. We can then construct logical expressions for s and co, from which we could build a circuit. x y ci co s --------------------- 0 0 0 0 0 0 0 1 0 1 s : NOT x AND NOT y AND ci 0 1 0 0 1 s : NOT x AND y AND NOT ci 0 1 1 1 0 co: NOT x AND y AND ci 1 0 0 0 1 s : x AND NOT y AND NOT ci 1 0 1 1 0 co: x AND NOT y AND ci 1 1 0 1 0 co: x AND y AND NOT ci 1 1 1 1 1 co,s: x AND y AND ci The logical expression for s is: (NOT x AND y AND ci) OR (x AND NOT y AND ci) OR (x AND y AND NOT ci) OR (x AND y AND ci) The logical expression for co is: (NOT x AND NOT y AND ci) OR (NOT x AND y AND NOT ci) OR (x AND NOT y AND NOT ci) OR (x AND y AND ci) ------------------------------------------------------------------------ Completeness of Boolean Operators The previous construction of a logical expression from a truth table showed how to represent any Boolean function as a sum of products or product of sums. Since we can represent any Boolean function using AND, OR, and NOT, these operators form a complete set for Boolean functions. We can show that the NAND operator alone is sufficient to generate every Boolean function, by showing how to implement AND, OR, and NOT in terms of NAND. p q p NAND 1 q NAND 1 p NAND q E1 E2 -------------------------------------------- 0 0 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 E1: p AND q == ((p NAND q) NAND TRUE) E2: p OR q == ((p NAND TRUE) NAND (q NAND TRUE)) E3: (NOT p) == (p NAND TRUE) A similar construction can be used to show that NOR is also sufficient to generate every Boolean function. Thus, we can generate digital circuits for any Boolean function using just NAND or NOR operators (or components). ------------------------------------------------------------------------ Tautologies A tautology is a logical expression that is always TRUE, regardless of the assignment of truth values to the variables in the expressions. Examples of tautologies: * TRUE * TRUE OR p * p OR NOT p * NOT (p AND NOT p) * p == p * (p OR q) == p OR (NOT p AND q) * (p == q) -> (p -> q) If we can establish that "LE1 == LE2" is a tautology, then no matter what values we assign to the variables in LE1 and LE2, we know that "LE1 == LE2" has the value TRUE. If "LE1 == LE2" is a tautology, then we can substitute LE2 for LE1 (or vice versa) in any expression, without changing the value of the expression. ------------------------------------------------------------------------ The Tautology Problem It is an interesting question to ask whether a given logical expression is a tautology. This question is known as the "tautology problem." To solve the tautology problem, we need only construct the truth table for the logical expression. If the expression has the value TRUE for all possible assignment values for the variables in the expression (that is, if the entire column for the expression in the truth table is TRUE), then the expression is a tautology. Note that the truth table will have 2^k rows and n columns, where the original expression has k variables and n operators. Thus, this algorithm requires O(2^kn) time, ie. exponential time. There is no known algorithm for the tautology problem that takes less than exponential time. Such problems are called "intractable" because large instances of the these problems cannot be solved in a reasonable amount of time. Another such intractable problem is the "satisfiability problem" which asks whether there is an assignment of truth values to variables in a logical expression that makes the expression TRUE. There is no known algorithm for this problem that is more efficient than cycling through all possible combinations of truth assignments for the variables. Satisfiability is the canonical NP-complete problem. The tautology problem is believed to be harder: i.e., not in NP. (The problem is that you can't even check the correctness of a 'yes' or 'no' answer in polynomial time.) ------------------------------------------------------------------------ Algebraic Laws for Logical Expressions As with arithmetic expressions, there are algebraic laws for logical expressions that establish the equivalence of two expressions. Each of these laws can be proven by showing the equivalence is a tautology. * AND and OR are commutative p AND q == q AND p p OR q == q OR p * AND and OR are associative p AND (q AND r) == (p AND q) AND r p OR (q OR r) == (p OR q) OR r * AND is distributive over OR; OR is distributive over AND p AND (q OR r) == (p AND q) OR (p AND r) p OR (q AND r) == (p OR q) AND (p OR r) * TRUE is the identity for AND; FALSE is the identity for OR p AND TRUE == p p OR FALSE == p * FALSE annihilates AND; TRUE annihilates for OR p AND FALSE == FALSE p OR TRUE == TRUE * AND and OR are idempotent p AND p == p p OR p == p ------------------------------------------------------------------------ DeMorgan's Laws DeMorgan's Laws are algebraic laws (or equivalences) that allow us to rewrite any logical expression so that NOT is only applied to propositional variables (and not to other logical expressions). DeMorgan's Laws: 1. NOT (p AND q) == (NOT p) OR (NOT q) 2. NOT (p OR q) == (NOT p) AND (NOT q) These laws state that the negation of the conjunction (or disjunction) of two propositions is logically equivalent to the disjunction (or conjunction) of their negations. By repeated application of DeMorgan's laws, we can push the NOT operators inward in an expression until they apply to variables only. This is an important step in transforming expressions into conjunctive or disjunctive normal form. Example: NOT ((p AND q) OR (NOT p AND r)) == NOT (p AND q) AND NOT (NOT p AND r) == (NOT p OR NOT q) AND (p OR NOT r) Example: NOT (NOT p OR (q AND ( NOT(r OR NOT s) ) ) == NOT NOT p AND NOT (q AND (NOT(r OR NOT s)) == p AND (NOT q OR NOT (NOT(r OR NOT s)) == p AND (NOT q OR NOT (NOT r AND NOT NOT s) == p AND (NOT q OR (r OR NOT s) ) ------------------------------------------------------------------------ Laws of Implication * (p -> q) AND (q -> p) == (p == q) Two expressions are equivalent if they imply each other. * (p == q) -> (p -> q) If two expressions are equivalent, they imply each other. * ((p -> q) AND (q -> r)) -> (p -> r) Implies is transitive. * (p -> q) == (NOT p OR q) We can express "implies" in terms of NOT and OR. * (p1 AND p2 AND ... pn -> q) == (NOT p1 OR NOT p2 OR ... NOT pn OR q) We can express a series of implicants using NOT and OR. * (p -> q) == (NOT q -> NOT p) This equivalence is known as the contrapositive law. * ((p -> q) AND (NOT p -> q)) == q This equivalence follows from expressing implies in terms of NOT and OR: (Not p OR q) AND (p OR q) == q. ======================================================================== Reasoning with Propositional Logic We can use propositional logic to reason formally about (or construct proofs of) propositions. A deductive argument takes as given a set of premises (or hypotheses) which are known to be true and attempts to prove a conclusion valid by a sequence of steps, termed inferences. Each inference follows from the premises or a previous inference by the application of an inference rule. Given premises (or inferences) P1..Pn, we can infer expression E if P1 AND P2 AND .. Pn -> E is a tautology. * Whenever E is a tautology, P1 AND P2 AND .. Pn -> E is a tautology. * Given two premises P1 and P2, we can infer P1 AND P2. * If P1 and (P1 -> P2) are given or inferred, then we can infer P2 by the rule of *modus ponens* (p AND (p->q) -> q). * If NOT P2 and (P1 -> P2) are given or inferred, then we can infer NOT P1 by the rule of *modens tollens*. * If P1 and (P1==P2) are given or inferred, we can infer P2. ------------------------------------------------------------------------ Proving Tautologies Using Inferences Prove (p -> q) AND (NOT p -> q) == q: 1. (p -> q) AND (NOT p -> q) Given 2. (NOT p OR q) AND (NOT NOT p OR q) Rewriting -> in terms of NOT and OR 3. (NOT p OR q) AND (p OR q) Elimination of double negation 4. ((NOT p OR q) AND p) OR ((NOT p OR q) AND q) Distribute AND over OR 5. ( NOT p AND p OR q AND p) OR (NOT p AND q OR q) Distribute AND over OR 6. (q AND p) OR (NOT p AND q OR q) Eliminate p AND NOT p 7. (q AND p) OR q Subsumption 8. q Subsumption QED ------------------------------------------------------------------------ Deductive Proof If the weather is warm and the sky is clear, then either we go swimming or we go boating. It is not the case that if the sky is clear then we go swimming. Therefore, if we do not go boating, then the weather is not warm. We can rewrite this argument formally, using the following variables to correspond to each of the propositions in the argument: w = weather is warm c = sky is clear s = we go swimming b = we go boating If the weather is warm and the sky is clear, then either we go swimming or we go boating: (w AND c) -> (s OR b) It is not the case that if the sky is clear then we go swimming. NOT (c -> s) Therefore, if we do not go boating, then the weather is not warm. NOT b -> NOT w To prove the conclusion given the premises, we need to be able to infer the conclusion from the premises. 1. (w AND c) -> (s OR b) Premise 1 2. NOT (c -> s) Premise 2 3. NOT (w AND c) OR (s OR b) L1, rewriting -> 4. (NOT w OR NOT c) OR (s OR b) L3, DeMorgan's law 5. NOT (NOT c OR s) L2, rewriting -> 6. c AND NOT s L5, DeMorgan's law 7. c L6 8. NOT s L6 9. (NOT w OR b) OR (NOT c OR s) L4, assoc/comm OR 10. (NOT w OR b) OR s L7,L9, (F OR p == p) 11. NOT w OR b L8,L10, (p OR F == p) 12. w -> b L11, rewriting -> 13. NOT b -> NOT w QED L12, contrapositive law ------------------------------------------------------------------------ Finding Proofs The previous examples of proofs show how to start with a set of premises and prove a conclusion (or infer an equivalence). In proving an equivalence using inferences, we repeatedly simplify a complex logical expression until the result is the simplified expression for which equivalence is desired. In proving a conclusion from a set of premises, we repeatedly establish inferences from the premises until we are able to infer the conclusion. In each case, the process is somewhat ad hoc, with no guarantee that the simplifications we choose will lead to the desired conclusion (or equivalence) quickly. Since the best known algorithm for the tautology problem is exponential, there is no optimal algorithm for finding a proof that doesn't explore all possible simplifications (in the worst case). However, there are heuristic techniques that help direct our search for a proof in the right direction. Resolution is one such technique. ======================================================================== Resolution The idea of resolution is simple: if we know p OR q and p -> r then we can deduce q OR r Put another way: (p OR q) AND (NOT p OR r) -> q OR r This is the *Resolution Tautology*. In order to apply resolution in a proof: 1. we express our hypotheses and conclusion as a product of sums (conjunctive normal form), such as those that appear in the Resolution Tautology. 2. each maxterm in the CNF of the hypothesis becomes a clause in the proof. 3. we apply the resolution tautology to pairs of clauses, producing new clauses. 4. if we produce all the clauses of the conclusion, we have proven it. ------------------------------------------------------------------------ Creating CNF 1) get rid of all operators except AND and OR 2) use DeMorgan's laws to push NOTs inward 3) distribute to push ORs inside ANDs Example: p OR (q AND NOT(r AND (s -> t))) p OR (q AND NOT(r AND (-s OR t))) p OR (q AND (-r OR NOT(-s OR t))) p OR (q AND (-r OR (s AND -t))) (p OR q) AND (p OR (-r OR (s AND -t))) (p OR q) AND (p OR -r OR s) AND (p OR -r OR -t) ------------------------------------------------------------------------ Proof with Resolution Given the following hypotheses: 1. If it rains, Joe brings his umbrella (r -> u) 2. If Joe has an umbrella, he doesn't get wet (u -> NOT w) 3. If it doesn't rain, Joe doesn't get wet (NOT r -> NOT w) prove that Joe doesn't get wet (NOT w) We first put each hypothesis in CNF: 1. r -> u == (NOT r OR u) 2. u -> NOT w == (NOT u OR NOT w) 3. NOT r -> NOT w == (r OR NOT w) We then use resolution on the hypotheses to derive the conclusion (NOT w): 1. NOT r OR u Premise 2. NOT u OR NOT w Premise 3. r OR NOT w Premise 4. NOT r OR NOT w L1, L2, resolution 5. NOT w OR NOT w L3, L4, resolution 6. NOT w L5, idempotence 7. QED ------------------------------------------------------------------------ Proofs by Contradiction using Resolution We can combine resolution with proof by contradiction (where we assert the negation of what we wish to prove, and from that premise derive FALSE) to direct our search towards smaller and smaller clauses, with the goal of producing FALSE. This approach (working toward smaller clauses) constitutes a heuristic that helps guide us toward an efficient proof. Proof by contradiction: (NOT p -> 0) == p We use proof by contradiction to drive our search for a proof; we are looking for the smallest possible goal clause (false), so any use of equivalences or resolution that brings us to simpler expressions is working towards that goal. We can redo the previous proof (about Joe and his umbrella) using proof by contradiction with resolution: 1. NOT r OR u Premise 2. NOT u OR NOT w Premise 3. r OR NOT w Premise 4. w Negation of conclusion 5. r 3, 4 resolution 6. u 1, 5 resolution 7. NOT w 2, 6 resolution 8. FALSE 4, 7 resolution ------------------------------------------------------------------------ Proof by Resolution: Example 2 If either C173 or C108 is required, then all students will take computer science. C173 and C252 are required. Prove that all students will take computer science. We formalize the proof as follows: P1. (C173 OR C108) -> ACS P2. C173 P3. C252 Prove: ACS We then rewrite our hypotheses in conjunctive normal form: P1: (NOT C173 OR ACS) (NOT C108 OR ACS) P2: C173 P3: C252 Then we use proof by contradiction, by asserting the clauses of the premises and the negation of the conclusion, and deriving false. 1. NOT C173 OR ACS Premise 2. NOT C108 OR ACS Premise 3. C173 Premise 4. C252 Premise 5. NOT ACS Negation of conclusion 6. NOT C173 1, 5 resolution 7. FALSE 3, 6 resolution ------------------------------------------------------------------------ Proof by Resolution: Example 3 Either Heather attended the meeting or Heather was not invited. If the boss wanted Heather at the meeting, then she was invited. Heather did not attend the meeting. If the boss did not want Heather there, and the boss did not invite her there, then she is going to be fired. Prove Heather is going to be fired. 1. A OR NOT I Premise 2. NOT W OR I Premise 3. NOT A Premise 4. W OR I OR F Premise 5. NOT F Negation of conclusion 6. W OR I 4, 5 resolution 7. I 2, 6 resolution, idempotence 8. A 1, 7 resolution 9. FALSE 3, 8 resolution ------------------------------------------------------------------------ Proof by Resolution: Example 4 Either taxes are increased or if expenditures rise then the debt ceiling is raised. If taxes are increased, then the cost of collecting taxes rises. If a rise in expenditures implies that the government borrows more money, then if the debt ceiling is raised, then interest rates increase. If taxes are not increased and the cost of collecting taxes does not increase then if the debt ceiling is raised, then the government borrows more money. The cost of collecting taxes does not increase. Either interest rates do not increase or the government does not borrow more money. Prove either the debt ceiling isn't raised or expenditures don't rise. 1. T OR NOT E OR D Premise 2. NOT T OR C Premise 3. (E AND NOT G) OR NOT D OR I Premise 4. T OR C OR NOT D OR G Premise 5. NOT C Premise 6. NOT I OR NOT G Premise 7. D AND E Negation of conclusion 8. (E AND NOT G) OR I L3, L7, resolution 9. C OR NOT D OR G L2, L4, resolution 10. C OR G L7, L9, resolution 11. G L5, L10, resolution 12. NOT I L6, L11, resolution 13. E AND NOT G L8, L12, resolution 14. NOT G L13, tautology 15. FALSE L11, L14, contradiction ------------------------------------------------------------------------ Proof by Resolution: Example 5 Reprise: If the weather is warm and the sky is clear, then either we go swimming or we go boating. It is not the case that if the sky is clear then we go swimming. Prove: if we do not go boating, then the weather is not warm. w = weather is warm c = sky is clear s = we go swimming b = we go boating premise 1: (w AND c) -> (s OR b) NOT (w AND c) OR (s OR b) (NOT w OR NOT c) OR (s OR b) (NOT w OR NOT c OR s OR b) premise 2: NOT (c -> s) NOT (NOT c OR s) c AND NOT s negated conclusion: NOT (NOT b -> NOT w) NOT (b OR NOT w) NOT b AND w 1. NOT w OR NOT c OR s OR b premise 1 2. c premise 2a 3. NOT s premise 2b 4. NOT b negated conclusion 1 5. w negated conclusion 2 6. NOT w OR s OR b 1 & 2 7. NOT w OR b 6 & 3 8. NOT w 7 & 4 9. FALSE 8 & 5 ------------------------------------------------------------------------ Prolog is a programming language based on the resolution principle. It isn't a pure realization of resolution -- there is no way to express negative terms as facts (only as possibilities), and (conversely) there are ways to express things beyond even first-order predicate calculus -- but basically it works by resolution. ======================================================================== Circuit Design A gate is a basic (indivisible) electronic device that computes a Boolean function. * A gate has one or more inputs (which are simply voltage levels) and produces an output (voltage level). * AND, OR, NOT, NAND, and NOR gates are particularly easy to implement electronically (with any number of inputs), and therefore are the gates used in practice. A circuit is a combination of gates, where the outputs of some gates are the inputs of others. * Each circuit may have one or more inputs, which are actually inputs to the gates in the circuit. * A circuit may have one or more outputs. ------------------------------------------------------------------------ Combinational vs Sequential Circuits Combinational circuits: * produce an output that is a boolean function (combination) of the input values. * are acyclic in that there are no cycles between the inputs of a gate and its outputs. * have no memory; there is no way to remember previous inputs or outputs. * are used to decode instructions and perform arithmetic. Sequential circuits: * produce an output that depends not only on the current input values, but also on the previous sequence of input values. * are cyclic; the output of a gate at some moment in time eventually feeds into the input of that gate at some future time. * can remember results of previous operations, and use those results as input. * are used to build registers and memory units. ------------------------------------------------------------------------ Combinational Circuit for an Encoder for a 7 Segment Display Consider a 7-segment display such as those used in most calculators: A ------- | | F | | B | G | ------- | | E | | C | | ------- D We would like to design a combinational circuit that takes 10 different inputs (corresponding to the decimal digits 0-9) labeled i0..i9 and lights up the display segments A-G as needed to display the decimal digit specified in the input. In particular, if input i0 is 1, then outputs A, B, C, D, E, and F should be 1 (producing a 0 on the display). The boolean expressions describing each of the outputs are: A = i0 + i2 + i3 + i5 + i7 + i8 + i9 B = i0 + i1 + i2 + i3 + i4 + i7 + i8 + i9 C = i0 + i1 + i3 + i4 + i5 + i6 + i7 + i8 + i9 D = i0 + i2 + i3 + i5 + i6 + i8 E = i0 + i2 + i6 + i8 F = i0 + i4 + i5 + i6 + i8 + i9 G = i2 + i3 + i4 + i5 + i6 + i8 + i9 We can build this circuit with 7 OR gates (one for each segment in the display) some of which take up to 9 inputs. ------------------------------------------------------------------------ A Sequential Circuit The following is a sequential circuit, because the output of the AND gate is an input to the OR gate and vice versa. x------------->| |AND)---*---> z *-->| | | | *--|-----------* | | | *-----------* | | *----->) | )OR>----* y ------------>) What does this circuit do? * If x = y = 1, then z=1. * If x=0, then z=0. * If x=1, and y=0, then the circuit depends on the previous value of z. The output of the circuit (z) is 1 if at some point in the past x and y were 1, and x has remained 1 ever since. ------------------------------------------------------------------------ Constraints on Circuit Design In designing efficient digital circuits there are numerous constraints to be considered, all of which impact the cost or speed of the resulting circuit. * Circuit speed: every gate in the circuit introduces a delay (which may be as small as 10^-10 seconds), so the number of gates on the path between the input and output determines how quickly the output will be computed. * Size limitations: the more gates we use in a circuit, the larger it will be. Large circuits are more expensive (in part because they have a higher failure rate) and slower, since signals must propagate from one end of the circuit to another, and the propagation speed is limited by the speed of light. * Fan-in and Fan-out: The fan-in and fan-out of a gate is the number of inputs and outputs, respectively. Large fan-in or fan-out makes for slower gates. ------------------------------------------------------------------------ A Ripple-Carry Adder We have already seen how to construct a one-bit adder, which takes two input operands (x and y) and a carry-in bit (ci), and produces the sum (z) and a carry-out bit (co). x y ci z co --------------------- 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 The logical expression for z is: (~x y ci) + (x ~y ci) + (x y ~ci) + (x y ci) The logical expression for co is: (~x ~y ci) + (~x y ~ci) + (x ~y ~ci) + (x y ci) A 32-bit ripple-carry adder is simply a sequence of 32 one-bit adders, where the carry-out bit from adder[i] provides the carry-in bit for adder[i+1]. The carry-in[0] is 0, and the sum is carry-out[31], z[31], z[30],..., z[0]. In a ripple-carry adder, the carry bits ripple through the circuit from adder[0] up to adder[31]. Thus, the delay of a ripple-carry adder of N bits is proportional to N. We would like to design an adder with a smaller delay, especially for larger word sizes (64 bits or more). ------------------------------------------------------------------------ Design of a Divide-and-Conquer Adder To add two N-bit numbers, we can use a divide-and-conquer approach in which we build a circuit that adds two N/2-bit numbers, and then use two such circuits and combine their results. To build a 32-bit adder, we would use two 16-bit adders to add the left and right halves of the operands in parallel, and then we would combine the results. * Each 16-bit adder would be composed of two 8-bit adders. * Each 8-bit adder would be composed of two 4-bit adders. * Each 4-bit adder would be composed of two 2-bit adders. * Each 2-bit adder would be composed of two 1-bit adders. Since we cannot know whether the lower half of the operands will result in a "carry" into the upper half, how can the two adders function in parallel? * we compute two sums for the upper half of the operands; one assuming there is a carry, and the other assuming there is no carry. * we use additional circuitry to select which of the two sums to use in the result. ------------------------------------------------------------------------ Design of an N-Adder Suppose we have two N-bit operands, expressed in binary form as x1..xN and y1..yN. We will design an N-adder that computes: * the sum without carry, s1..sN, the N-bit sum of x1..xN and y1..yN assuming no carry into the sum of xN and yN. * the sum with carry, t1..tN, the N-bit sum of x1..xN and y1..yN assuming there is a carry into the sum of xN and yN. * the carry-propagate bit, p, which is 1 if there is a carry out of the leftmost place (x1 and y1), on the assumption there is a carry into the rightmost place. * the carry-generate bit, g, which is 1 if there is a carry out of the leftmost place (x1 and y1) even if there is no carry into the rightmost place. We will first show how to build a 1-bit adder component, and then show how to build an N-adder out of 1-bit adders. ------------------------------------------------------------------------ A 1-bit Adder A 1-adder computes the following Boolean functions: x y s t p g -------------------------- 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 The corresponding logical expressions are: s = (~x y) + (x ~y) t = (~x ~y) + (xy) p = x + y g = xy ------------------------------------------------------------------------ A 2-bit Adder from 1-bit Adders We can build a 2-bit adder using two 1-bit adders. -------- x1 ------>| Low | -----> sL --------------------> s1 | Order| -----> tL --------------------> t1 y1 ------>| 1-bit| -----> gL -------* | Adder| -----> pL ----* | -------- | | | | | | | *--->|F|-----> g -------- *------>|I|-----> p x2 ------>| High | -----> sH ----------->|X|-----> s2 | Order| -----> tH ----------->|I|-----> t2 y2 ------>| 1-bit| -----> gH ----------->|T| | Adder| -----> pH ----------->| | -------- The sum of the low-order bits (s1 or t1) doesn't depend on whether there is a carry from the low-order bits to the high-order bits, so we compute the sum of x1 and y1 into sL and tL, and produce those values as the resulting sum of the low-order bits (with different assumptions about carry-in bits). The sum of the high-order bits (s2 and t2) does depend on whether there is a carry (gL and pL), so we take the carry bits from the first adder, and the summation results from the second adder, and combine them together in the circuit labeled FIXIT to get the final result. ------------------------------------------------------------------------ Combining the Results of 1-bit Adders FIXIT computes its outputs using the following expressions: * p = gH + pH pL: that is, if there is a carry into the low-order part of the circuit, there is a propagation carry out of the high-order part of the circuit if both the lower-order and high-order bits propagate a carry (pH pL) or if there is a carry out of the high-order bits (gH). * g = gH + pH gL: that is, if there is no carry into the low-order part of the circuit, there is a carry out of the high-order part if there is a carry out of the high-order bits anyway (gH) or if there is a carry from the low-order bits (gL), and the high-order bits propagate that carry (pH). * s2 = (sH ~gL) + (tH gL): that is, the sum of the high order bits (under the assumption of no carry in from the right end of the circuit) is sH if there is no carry generated from the low-order bits, and tH otherwise. * t2 = (sH ~pL) + (tH pL): that is, the sum of the high order bits (under the assumption of a carry in from the right end of the circuit) is tH if there is a carry propagated through the low-order bits, and sH otherwise. We can generalize this construction to N bits, and create an N-adder where the circuit delay is 3(log N + 1), rather than the O(N) delay in the ripple-carry adder. ------------------------------------------------------------------------ Sequential Circuits for Memory Elements A memory element is a collection of gates capable of producing its last input as output. Memory elements are sequential circuits; that is, circuits whose behavior depends not only on the current inputs, but also on the past history. A flip-flop is a 1-bit memory element. A typical flip-flop circuit takes two inputs and produces a single output. * Input data-in is the binary data value to be stored in the memory element. * Input load determines whether the circuit is being asked to load a new binary value. Whenever load=0, the circuit produces as output the stored value (which is the last value loaded into the memory element). Whenever load=1, the circuit stores the value of data-in and produces it as output. ------------------------------------------------------------------------ Flip-Flop Circuit Here is a sequential circuit for a binary flip-flop: *----------------------* | | *-->|AND| | load----->|NOT|---->| 1 |------>|OR|---*--- data-out | *-->| 1| | | | | *------------>|AND|---* data-in ----------->| 2 | When load is 0: * the gate labeled AND2 produces a zero, and therefore doesn't affect data-out. * the gate labeled AND1 produces the previous value of the flip-flop as its output, which becomes data-out. * so, the circuit simply outputs the previous stored value. When load is 1: * the gate labeled AND1 produces a zero, and therefore doesn't affect data-out. * the gate labeled AND2 produces the value of data-in, which becomes data-out. * so, the circuit simply outputs data-in. ------------------------------------------------------------------------ Another useful combinatorial circuit: Multiplexor (MUX) A MUX takes a bunch of inputs and a selector (itself encoded as several binary bits) and chooses the input indicated by the selector. We used a simple MUX in the divide-and-conquer adder to choose between the s and t sums (with or without incoming carry). 1-MUX (1 control bit; 2^1 = 2 inputs): output = x y1 + ~x y2 y1 y2 | | x --+-----------(---+ | | | | | +---NOT-+ | | | | | | | ----- ----- AND AND | | \ / --- OR | 2-MUX (2 control bits; 2^2 = 4 inputs): picture p. 725 AU one wide AND gate for every input, fed by the input and the appropriate plain or negated control bits; one very wide OR gate to pull together the outputs of the ANDs. Generalization has unacceptable fan-in. Divide-and-conquer 2d-MUX - Feed high-order d control bits into 2^d d-MUXes, each of which also takes a contiguous group of 2^d inputs. - Feed low-order d control bits into a final d-MUX, which also takes the outputs of the high-order d-MUXes as inputs. - Delay is 2d, plus 1 for initial inversion of control inputs. Suppose the straightforward MUX is limited to gates with fixed fan-in. Then its AND and OR gates have to be simulated with binary trees, giving the same big-O number of gate delays as the divide-and-conquer MUX. What about total number of gates (chip area)? Turns out the divide-and-conquer MUX is smaller by a factor of approximately d. BIG WIN. NB: The divide-and-conquer adder built an N-input circuit from 2 N/2-input circuits and some patch-up circuitry. The divide-and-conquer MUX built a 2^d-input circuit from 2^d-1 2^d-1 circuits (and some patch-up). Put another way, the MUX built an N-input circuit from sqrt(N) sqrt(N) circuits, which is kind of cool.