Report

Propositional Equivalence Goal: Show how propositional equivalences are established & introduce the most important such equivalences. Equivalence Name p T ≡ p; pF≡p Identity p T ≡ T; pF≡F Domination p p ≡ p; pp≡p Idempotent ( p) ≡ p p q ≡ q p; Double negation pq≡qp Copyright © Peter Cappello Commutative 2 Equivalence Name (p q) r ≡ p (q r ) (p q) r ≡ p (q r ) Associative p (q r ) ≡ (p q) (p r ) p (q r ) ≡ (p q) (p r ) Distributive (p q) ≡ p q (p q) ≡ p q DeMorgan p (p q ) ≡ p p (p q ) ≡ p Absorption p p ≡ T p p ≡ F Negation Copyright © Peter Cappello 3 Exercise A tautology is a compound proposition that always is true. Is the following a tautology? ( (p q) ( p r) ) (q r) Copyright © Peter Cappello 4 The Satisfiability Problem Satisfiability Problem Given a function of boolean variables, is there an assignment of values to its variables that makes it true? Is f( p, q, r ) = ( (p q) ( p r) ) (q r) satisfiable? Satisfiability is important in CS theory, algorithms, program correctness, AI, hardware design, etc. Algorithm 1. Construct the truth table. 2. If any assignment (row) evaluates to true, return true; 3. Else return false. If the formula has n variables, how many rows does the truth table have? Copyright © Peter Cappello 5 An example satisfiability problem • Let p( row, col, n ) denote the proposition “Box( row, col ) contains number n.” • Using such propositions, design a compound proposition that is satisfiable if & only if 1 3 n appears in some box, for 1 ≤ n ≤ 4. 4 1 Copyright © Peter Cappello 6 Problem Give logical expressions for a 2-bit adder, where • true corresponds to 1 • false corresponds to 0 For example, 01 + 11 = 100. • Input: Operand 1: a1 a0 Operand 2: b1 b0 • Output s2 s1 s0 That is, define 3 Boolean functions: • s 0 ( a1 , a0 , b1 , b 0 ) = ? • s 1 ( a1 , a0 , b1 , b 0 ) = ? • s 2 ( a1 , a0 , b1 , b 0 ) = ? Copyright © Peter Cappello 7 Can you define a Boolean function in the C programming language? boolean[] adder( boolean a1, boolean a0, boolean b1, boolean b0 ) { . . . } Or, for an n-bit adder: boolean[] adder( boolean[] a, boolean[] b ) { . . . } For an n-bit adder, it may be useful to compute, for 0 ≤ i ≤ n, a sum bit, si and a carry bit, ci. For the sum bit, si, we may use: si = ai bi ci-1, where c-1 = 0 and sn = cn-1. The equation above is called a recurrence equation. What is a recurrence equation for the carry bit, ci? Copyright © Peter Cappello 8 Unraveling the for loop, suggests a diagram: sn sn-1 cn-1 s2 cn-2 an-1 bn-1 c2 s1 c0 c1 a2 b2 s0 a1 b1 0 a0 b0 Each box above has 3 inputs & 2 outputs, and is called a full adder. A harder problem: Compute these sum & carry bits in parallel. Copyright © Peter Cappello 9 END Copyright © Peter Cappello 2011 10