COMP 409: Homework 4


    COMP 409 Homework 4
    Sample Solutions
    October 13 2016
    1 NPcompleteness
    1 Reducing Exact Cover to SAT
    To show that 3cover is polyreducible to SAT we need to define a function f that
    maps an instance
    (
    XC
    )
    of the Exact Cover problem to a propositional formula '
    such that C contains an exact cover of X i↵ ' is satisfiable and the function f has to
    be computable in polynomial time
    Let
    (
    XC
    )
    be an instance of the Exact Cover problem with X
    {
    x1xn
    }
    and
    C
    {
    C1Cm
    }
    Thenwedefine
    Bx
    {
    i
    ￿
    x

    Ci
    }which is the set of indices of all sets in C that contain the element x in X Constructing
    this set is in PTIME since for each of the n elements in X we need to check m sets in
    C each of constant size 3 Also define
    I
    {(
    i j
    )￿
    Ci

    Cj
    ≠ ￿}which is a set that contains all pairs
    (
    i j
    )
    of indices of intersecting sets in C Clearly
    constructing this auxiliary set I is in PTIME since there are only m
    (
    m

    1
    )￿
    2 possible
    distinct pairs of sets in C and each Ci contains exactly 3 elements
    Once we have constructed these sets in polynomial time we proceed to build the
    formula ' which is f
    (
    XC
    )
    We define our set of propositions to be
    {
    ci

    1

    i

    m
    }

    Intuitively a satisfying assignment to ' will assign ci to be 1 if Ci is selected in the
    exact cover and 0 otherwise The required formula is

    ￿
    x

    X
    ( ￿
    i

    Bx
    ci
    ) ￿(
    ij
    )∈
    I

    ci
    ∨¬
    cj
    )It follows that the size and computation of this formula are both polynomial in the size
    of the Exact Cover instance since
    ￿
    X
    ￿
    n and
    ￿
    Bx
    ￿ ≤
    m for all x and
    ￿
    I
    ￿ ≤
    m
    (
    m

    1
    )￿
    2
    as discussed above
    The purpose of the first half of ' is to ensure that all of X is covered since at least
    one of the sets Ci has to be included in C

    that contains each x The purpose of the
    second half of ' is to ensure that no two sets Ci and Cj that both contain the same x
    are included in C

    since if both Ci and Cj contain x
    ¬(
    ci

    cj
    )
    ensures they are not
    included together We show that this is a valid reduction
    1Lemma There exists C


    C such that C

    is an exact cover of X i↵ ' is SAT
    Proof


    Let C

    be an exact cover of XWedefine⌧
    {
    ci

    Ci

    C

    }
    Consider
    (
    i j
    ) ∈
    I
    Then by definition of I Ci

    Cj
    ≠ ￿
    SinceC

    is an exact cover every pair of
    sets in C

    are disjoint so we must have Ci
    ￿∈
    C

    or Cj
    ￿∈
    C

    Therefore for all
    (
    i j
    ) ∈
    I ⌧
    ￿ (¬
    ci
    ∨¬
    cj
    )

    Also since C

    is an exact cover of X
    ￿
    C


    X So for all x

    Xwehave
    Bx
    ∩ {
    i

    Ci

    C

    } ≠ ￿
    Therefore for all x

    X ⌧
    ￿ ￿
    i

    Bx ciThus⌧
    ￿
    ' and ' is
    satisfiable


    If ' is SAT then there exists a truth assignment ⌧ such that ⌧
    ￿
    'Define
    C

    {
    Ci

    C


    (
    ci
    )
    1
    }
    Consider Ci and Cj in C

    Then⌧
    (
    ci
    )

    (
    cj
    )
    1 so

    ￿￿ (¬
    ci
    ∨¬
    cj
    )
    Therefore
    (
    i j
    )￿∈
    I and Ci

    Cj
    ￿

    Let x

    XSince⌧
    ￿ ￿
    i

    Bx cithereexistsi

    Bx such that ⌧
    (
    ci
    )
    1 So there
    exists Ci

    C

    such that x

    CiSinceeveryx in X is contained in some element
    of C

    and each element of C

    is also a subset of Xwehave
    ￿
    C


    X
    So C

    satisfies the two conditions for being an exact cover of X
    This proves that Exact Cover is a polynomially reducible to SAT
    2 Reducing 3SAT to Integer Programming
    To reduce 3SAT to IP we need to define a function f that maps a 3CNF formula
    ' to an instance of the Integer Programming (IP) problem which is a set of linear
    inequalities such that ' is satisfiable i↵the set of inequalities has an integral solution
    Further f must be computable in polynomial time
    Let ' be a 3CNF formula and let AP
    (

    ) {
    p1pn
    }
    be the set of atomic propo
    sitions in ' We construct I

    f
    (

    )
    the desired set of linear inequalities First we
    define our set of variables to be
    {
    xiyi

    1

    i

    n
    }
    and we define a mapping v from the
    set of possible literals to the set of variables as follows
    v
    (
    pi
    )
    xi and v

    pi
    )
    yi
    Since logical literals can only have the values 1 (true) and 0 (false) and the variables
    in an IP problem are assumed to be integral we add the following inequalities to I
    to ensure that each variable corresponding to a literal can only have a value of 0 or
    1 and that variables assigned to complementary literals have opposite values For all
    1

    i

    n
    xi

    0 yi

    0
    xi
    +
    yi
    >
    0
    xi
    +
    yi

    1
    These inqualities restrict each xi and yi to complementary boolean values The com
    putation and size of these inequalities is linear in the size of ' since there are 4
    inequalities per atomic proposition Next for each clause
    (





    )
    in the 3CNF
    formula ' we add the following inequality to I
    v
    (

    ) +
    v
    (

    ) +
    v
    (

    ) ≥
    1
    2The computation and size of I is still linear in the length of ' since we added one
    inequality per clause Thus given ' we can compute f
    (

    )
    I in polynomial time
    We next show that f is a valid reduction
    Lemma ' is SAT i↵ I has an integral solution
    Proof


    If ' is SAT then there exists a truth assignment ⌧ such that ⌧
    ￿
    ' Then for
    all 1

    i

    n assign xi


    (
    pi
    )
    and yi

    1


    (
    pi
    )
    We claim that this assignment
    constitutes an integral solution to I Clearly xi

    0 and yi

    0 are satisfied
    Similarly xi
    +
    yi


    (
    pi
    ) +
    1


    (
    pi
    )
    1 so 0

    xi
    +
    y1

    1 is satisfied Also if

    ￿
    pithenxi

    v
    (
    pi
    )
    1 and if ⌧
    ￿ ¬
    pi then yi

    v

    pi
    )
    1


    (
    pi
    )
    1 So for
    any literal ↵if⌧
    ￿
    ↵ then v
    (

    )
    1 Therefore because ⌧ satisfies each clause
    (





    )
    of 'wehavev
    (

    ) +
    v
    (

    ) +
    v
    (

    ) ≥
    1 Thus the assignment satisfies
    each inequality in I and so I has an integral solution


    We first note that the inequalities xi

    0 yi

    0 xi
    +
    yi

    1 restrict the possible
    integral values of xi and yi to the set
    {
    01
    }
    Further the inequality xi
    +
    yi
    >
    0
    ensures that y1

    1

    xi that is xi and yi are complementary
    Given an integral solution to I we define the truth assignment ⌧ as ⌧
    (
    pi
    )
    xi
    which is a valid truth assignment since all xi are only 0 or 1 Then ⌧
    ￿
    pi if xi

    1
    and ⌧
    ￿ ¬
    pi if yi

    1

    xi

    1 So ⌧
    ￿
    ↵ if v
    (

    )
    1 for each literal ↵Sincethe
    integral solution satisfies each inequality v
    (

    )+
    v
    (

    )+
    v
    (

    ) ≥
    1 and each variable
    has value 0 or 1 we must have v
    (

    )
    1 for some literal ↵ in each clause of 'So

    ￿
    ↵ for some literal ↵ in each clause of ' Therefore ⌧ satisfies each clause of
    ' and we have that ' is satisfiable
    This proves that 3SAT is polynomially reducible to IP
    3 NP and coNP
    (a)
    L

    coNP
    ⇐⇒
    x
    ￿∈
    L i↵

    y



    P
    (￿
    x
    ￿)
    A
    (
    x y
    )
    1 (definition of coNP)
    ⇐⇒
    x




    L i↵

    y



    P
    (￿
    x
    ￿)
    A
    (
    x y
    )
    1(sincex
    ￿∈
    L i↵ x




    L)
    ⇐⇒



    L

    NP (definition of NP)
    (b) First we need the following simple result
    Lemma L


    p L i↵ ⌃


    L


    p ⌃


    L
    Proof
    L


    p L i↵

    f st x

    L

    i↵ f
    (
    x
    ) ∈
    L
    i↵

    f st x
    ￿∈
    L

    i↵ f
    (
    x
    )￿∈
    L
    i↵

    f st x




    L

    i↵ f
    (
    x
    ) ∈



    L
    i↵ ⌃


    L


    p ⌃


    L (so the same f is the reduction)
    3Now to the main problem
    L

    coNPC
    i↵ L

    coNP and

    L


    coNPL


    p L (definition of coNPC)
    i↵ ⌃


    L

    NP and

    L


    coNPL


    p L (from part (a) above)
    i↵ ⌃


    L

    NP and

    L


    coNP⌃


    L


    p ⌃


    L (from lemma above)
    i↵ ⌃


    L

    NP and
    ∀(



    L

    ) ∈
    NP⌃


    L


    p ⌃


    L (from part (a) above)
    i↵ ⌃


    L

    NP and

    L
    ′′

    NPL
    ′′

    p ⌃


    L (changing variables)
    i↵ ⌃


    L

    coNPC (definition of NPC)
    (c) Let L be coNP complete and let L be in NP Since L is in NP there exist
    polynomial p and PTIME algorithm A such that for all x



    x

    L i↵there
    exists y



    p
    (￿
    x
    ￿)
    with A
    (
    x y
    )
    1
    Consider an arbitrary L


    coNP Then L


    p L Let f be the required polytime
    reduction Since f is polynomially computable
    ￿
    f
    (
    x
    )￿
    must be polynomial in
    ￿
    x
    ￿

    And because polynomials are closed under functional composition there exists
    a polynomial p

    such that p
    (￿
    f
    (
    x
    )￿) <
    p

    (￿
    x
    ￿)
    for all x



    We can define an
    algorithm A

    which given x



    and a witness y



    p

    (￿
    x
    ￿)
    first computes f
    (
    x
    )
    and then calls A
    (
    f
    (
    x
    )
    y
    )
    SowehaveA

    (
    x y
    )
    A
    (
    f
    (
    x
    )
    y
    )
    Sincef and A are
    both polynomially computable A

    is also polynomially computable
    Then we have for all x




    x

    L
    ′i↵ f
    (
    x
    ) ∈
    L (because f is a reduction)
    i↵

    y



    p
    (￿
    f
    (
    x
    )￿)
    A
    (
    f
    (
    x
    )
    y
    )
    1 (because L is in NP)
    i↵

    y



    p

    (￿
    x
    ￿)
    A

    (
    x y
    )
    1 (because A

    (
    x y
    )
    A
    (
    f
    (
    x
    )
    y
    )
    )
    Thus L

    is in NP Since L

    was arbitrary this proves coNP

    NP
    Now let L
    ′′
    be an arbitrary language in NP Then ⌃


    L
    ′′
    is in coNP Since we
    have proved that coNP

    NP therefore ⌃


    L
    ′′
    must also be in NP But then


    − (



    L
    ′′
    )
    L
    ′′
    is in coNP Thus NP

    coNP
    Therefore we have that coNP

    NP
    42 Satisfiability
    1 Proof by induction on the structure of '
    Basis ' is an atomic proposition We have two subcases
    • ' is pThen'
    [
    p
    ￿

    (
    p
    )]

    (
    p
    )
    and ⌧
    ￿
    AP
    (

    )−{
    p
    }

    ￿￿

    ∩￿ ￿
    Therefore

    ￿
    AP
    (

    )−{
    p
    } ￿

    [
    p
    ￿

    (
    p
    )]
    i↵
    ￿ ￿

    (
    p
    )
    i↵
    ￿

    (
    p
    )
    i↵ ⌧
    (
    p
    )
    1i↵⌧
    ￿
    p
    • ' is q

    pThen'
    [
    p
    ￿

    (
    p
    )]
    q and AP
    (

    ) − {
    p
    } {
    q
    } − {
    p
    } {
    q
    }
    Bythe
    relevance lemma ⌧
    ￿
    q i↵ ⌧
    ￿{
    q
    } ￿
    q
    Inductive Step We have the following cases
    Case 1 '


    )
    In this case AP
    (

    )
    AP
    (

    )
    Then by the induction
    hypothesis ⌧
    ￿
    ✓ i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿

    [
    p
    ￿

    (
    p
    )]
    Wehave

    ￿

    i↵ ⌧
    ￿ (¬

    )i↵ ⌧
    ￿￿
    ✓ (by semantics of
    ¬
    )
    i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿￿

    [
    p
    ￿

    (
    p
    )]
    (by IH)
    i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿ (¬(

    [
    p
    ￿

    (
    p
    )]))
    (by semantics of
    ¬
    )
    i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿ (¬

    )[
    p
    ￿

    (
    p
    )]
    (by defn of substitution)
    i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿

    [
    p
    ￿

    (
    p
    )]
    (because AP
    (

    )
    AP
    (

    )
    )
    Case 2 '
    (



    )
    Then by the induction hypothesis we have that

    (

    ) (

    [
    p
    ￿

    (
    p
    )])(

    ￿
    AP
    (

    )−{
    p
    })
    (1)

    (

    ) (

    [
    p
    ￿

    (
    p
    )])(

    ￿
    AP
    (

    )−{
    p
    })
    (2)
    Then we have

    ￿

    i↵ ⌧
    ￿ (



    )i↵
    (



    )(

    )
    1
    (by correspondence between Philosopher’s and EE view)
    i↵
    ○ (

    (

    )

    (

    ))
    1
    (by EE semantics)
    i↵
    ○ (

    [
    p
    ￿

    (
    p
    )](

    ￿
    AP
    (

    )−{
    p
    })

    [
    p
    ￿

    (
    p
    )](

    ￿
    AP
    (

    )−{
    p
    }))
    1
    (by IH using equations 1 and 2 above)
    i↵
    ○ (

    [
    p
    ￿

    (
    p
    )](

    ￿
    AP
    (

    )−{
    p
    })

    [
    p
    ￿

    (
    p
    )](

    ￿
    AP
    (

    )−{
    p
    }))
    1
    (by the relevance lemma since AP
    (

    ) ∪
    AP
    (

    )
    AP
    (

    )
    )
    i↵
    (

    [
    p
    ￿

    (
    p
    )] ○

    [
    p
    ￿

    (
    p
    )])(

    ￿
    AP
    (

    )−{
    p
    })
    1
    (by EE semantics)
    i↵
    ((



    )[
    p
    ￿

    (
    p
    )])(

    ￿
    AP
    (

    )−{
    p
    })
    1
    (by definition of substitution)
    i↵
    (

    [
    p
    ￿

    (
    p
    )])(

    ￿
    AP
    (

    )−{
    p
    })
    1
    i↵ ⌧
    ￿
    AP
    (

    )−{
    p
    } ￿

    [
    p
    ￿

    (
    p
    )](by correspondence between Philosopher’s and EE view)
    52 We first prove that any formula in DNF can be converted into an equivalent formula
    in CNF and vice versa using only the distributive laws for

    and

    Weprovethisby
    a two step induction
    Lemma 1 If ' is in CNF and qi is a literal for 1

    i

    nthen
    (

    ∨ (
    q1
    ∧⋅⋅⋅∧
    qn
    ))
    can
    be converted to a formula in CNF using only the distributive laws
    Proof Let '

    m
    i

    1ci where ci is a disjunctive clause for 1

    i

    m
    Basis '

    q
    (∧
    m
    i

    1ci
    ) ∨
    q
    ￿￿ ∧
    m
    i

    1
    (
    c1

    q
    )
    ✓ (using the distributive laws) Now
    since ci is a disjunctive clause and q is a literal therefore ci

    q is a disjunctive clause
    Therefore ✓ is in CNF
    Inductive Step Let Q

    n
    i

    1qiThen'
    ∨ (
    q1
    ∧⋅⋅⋅∧
    qn
    +
    1
    ) (

    ∨ (
    Q

    qn
    +
    1
    )) ￿
    ￿((


    Q
    ) ∧ (


    qn
    +
    1
    ))
    (using the distributive laws) Now by IH
    (


    Q
    ) ￿￿
    ✓1 where
    ✓1 is in CNF and using the basis
    (


    qn
    +
    1
    ) ￿￿
    ✓2 where ✓2 is in CNF Then ✓1

    ✓2
    is in CNF too So '
    ∨ (
    q1
    ∧⋅⋅⋅∧
    qn
    +
    1
    ) ￿￿
    ✓1

    ✓2

    ✓ where ✓ is in CNF
    Lemma 2 If ' is in DNF then it can be converted to an equivalent formula in CNF
    using only the distributive laws
    Proof If ' is in DNF and contains a single clause we can easily convert it to CNF
    by assigning each literal to its own singleton disjunctive clause Let '

    m
    i

    1ci where
    ci is a conjunctive clause for 1

    i

    m and m
    >
    1 Let ✓

    m

    1
    i

    1 ciThen'
    (


    cm
    )

    Then by IH we have that ✓
    ￿￿


    where ✓

    is in CNF Consider '

    (



    cm
    )
    Then

    ￿￿


    and '

    has the form required in Lemma 1 above Therefore '

    ￿￿

    ′′
    where

    ′′
    is in CNF Thus '
    ￿￿

    ′′
    where '
    ′′
    is in CNF
    We have shown that any formula in DNF can be converted to an equivalent formula
    in CNF The reverse also holds true and the proof proceeds identically because of the
    symmetry of the distributive laws with respect to

    and

    Next we prove that the
    negation of a CNF formula is equivalent to some DNF formula using only De Morgan’s
    laws
    Lemma 3 If ' is in CNF then


    )
    can be converted to an equivalent formula in
    DNF using only De Morgan’s laws
    Proof We prove the statement by induction
    If ' is in CNF and contains a single disjunctive clause then


    ) (¬(
    l1

    l2
    ∨￿∨
    lk
    )) ￿
    ￿(¬
    l1
    ∧ (¬(
    l2
    ∨￿∨
    lk
    )) ￿￿ ￿ ￿￿(¬
    l1
    ∧¬
    l2
    ∧￿∧¬
    lk
    ) ￿￿(
    l

    1

    l

    2
    ∧￿∧
    l

    k
    )

    ′by k applications of De Morgan’s laws and replacing each negated literal
    ¬
    li by its
    complementary literal l

    iThen'

    is in DNF
    Let '

    m
    i

    1ci where ci is a disjunctive clause for 1

    i

    m and m
    >
    1 Let ✓

    m

    1
    i

    1 ci
    By IH there exists a DNF formula ✓

    such that ✓

    ￿￿(¬

    )
    and by the base case there
    exists a DNF formula ✓
    ′′
    such that ✓
    ′′
    ￿￿(¬
    cm
    )
    Then
    (




    ′′
    ) ￿￿((¬

    ) ∨ (¬
    cm
    )) ￿
    ￿(¬(


    cm
    ))
    ' and
    (




    ′′
    )
    is in DNF
    We now prove that any formula can be written in CNF using only de Morgan’s laws
    and the distributive laws Proof by induction
    Basis '

    p for some proposition pThen' is already in CNF
    6Inductive step We have the following cases
    Case 1 '


    )
    Then by IH ✓
    ￿￿


    where ✓

    is in CNF and by Lemma 3



    ) ￿￿

    ′′
    where ✓
    ′′
    is in DNF Finally by Lemma 2 ✓
    ′′
    ￿￿


    where '

    is in
    CNF Therefore '
    ￿￿


    for some CNF formula '


    Case 2 '
    (



    )
    Then by IH ✓
    ￿￿


    and
    ￿￿


    where✓

    and

    are in
    CNF Then '

    (





    )
    is in CNF too and '
    ￿￿



    Case 3 '
    (



    )
    Then by IH ✓
    ￿￿


    and
    ￿￿


    where✓

    and

    are in
    CNF Further by the converse of Lemma 2 there exist DNF formulas ✓
    ′′
    and

    ′′
    such that ✓

    ￿￿

    ′′
    and

    ￿￿

    ′′
    Then
    (

    ′′


    ′′
    )
    is in DNF too and again by
    Lemma 2 we can find a formula '
    ′′
    in CNF such that '
    ′′
    ￿￿(

    ′′


    ′′
    )

    Therefore '
    ￿￿(



    ) ￿￿(





    ) ￿￿(

    ′′


    ′′
    ) ￿￿

    ′′
    where '
    ′′
    is a formula in
    CNF
    Case 4 '
    (



    )
    Then'
    ￿￿((¬

    ) ∨

    )
    Then this case can be handled
    easily by combining the arguments from case 1 and case 3 above
    Case 5 '
    (



    )
    Then'
    ￿￿(



    ) ∧ (



    )
    Then this case can be
    handled easily by combining the arguments from case 4 and case 2 above
    Thus we have shown that any formula can be converted to CNF using De Morgan’s
    and distributive laws only
    For the second part of the problem we assume that there exists a polytime algorithm
    that translates each formula to its conjunctive normal form We know that VALID is
    coNP complete for formulas in DNF However it is also known that VALID is in P
    for formulas in CNF Thus if we have a polytime algorithm for translating formulas
    into equivalent formulas in CNF given a formula in DNF we could find its equivalent
    formula in CNF in polytime and then check the equivalent formula for validity again
    in polytime Thus we would be able to solve VALID for DNF in polytime This
    would imply that coNP is a subset of P (since VALID for DNF is coNP complete)
    Since P is contained in coNP (in fact in the intersection of NP and coNP) we would
    have that coNP P Since P is closed under complementation we would have P
    coP co(coNP) NP Thus the existence of such an algorithm would lead to the
    surprising result that PNP
    3 The three sentences written by Boole can be interpreted in the following way The
    socalled properties can be thought of as propositions that are true if the property
    is present and false otherwise Let us then define Prop
    {
    A B C D E
    }
    the set of
    propositions in our world where each proposition corresponds to each of the properties
    mentioned by Boole Then we have

    A
    ∧¬
    C
    ) → (
    E
    ∧ ((
    B
    ∧¬
    D
    ) ∨ (¬
    B

    D
    )))
    (
    A

    D
    ∧¬
    E
    ) → (
    B

    C
    )
    (
    A
    ∧ (
    B

    E
    )) ↔ ((
    C
    ∧¬
    D
    ) ∨ (¬
    C

    D
    ))Our interpretation of the first question is what relationships exist among B C and
    D if A1 By setting A1 and using our solver (which works in CNF) to simplify
    7the formulas we get as a result the following formulas containing B C and D
    ¬
    B

    C

    D
    ¬
    B
    ∨¬
    D
    B

    D
    B

    C

    D
    C
    ∨¬
    D
    ¬
    C

    D
    Note that the last two clauses are equivalent to
    (
    C

    D
    )∨(¬
    C
    ∧¬
    D
    )
    which is equivalent
    to C

    D so when property A is present properties C and D are either both present
    or none Likewise from the second and third clauses it can be inferred that B
    ↔ ¬
    D
    and from these two that B
    ↔ ¬
    C as well The first and fourth equations above form a
    tautology so they do not give any interesting information whatsoever This concludes
    all analyses of the above clauses
    To look for independent relations among B C and D our interpretation is that
    regardless of the value of A if there is any relationship of the following that can be
    deduced from the first 3 original formulas
    B

    C
    B

    D
    C

    B
    C

    D
    D

    B
    D

    C
    To check this since we have proved before that
    ∪¬
    ' is UNSAT i↵
    ￿
    ' (a la
    proof by contradiction) we can add the negation of the above relations to our list
    of clauses in CNF form and invoke the split solver if it returns UNSAT it means
    that the relation follows from the above Unfortunately plugging in all of the possible
    implications makes split return SAT so this means that none of the above relations
    can be concluded from the premises
    For the second question making B 1 yields the following clauses with only A C
    and D
    C

    D
    A
    ∨¬
    D
    A

    C
    ∨¬
    D
    A
    ∨¬
    C

    D
    ¬
    A

    C

    D
    ¬
    A
    ∨¬
    C
    ∨¬
    D
    In likewise manner from the last two we can deduce A
    ↔ (
    C

    D
    ) ∧ (¬
    C
    ∨¬
    D
    )
    soif
    property A is present one of C or D are also present but not both The third and
    8fourth imply that
    ¬
    A
    → (
    C

    D
    )
    so the absence of A makes C equal to D Nothing
    interesting can be concluded from the first two though
    3 Adequacy
    1 Inspecting the inequality we see that if p1

    0 then it cannot be satisfied so p1 must
    be 1 Once p1 is 1 if either p2 or p3 are 1 then it is satisfied but not if both are 0
    So a logically equivalent formula is
    'ttof
    (
    p1
    ∧ (
    p2

    p3
    ))One way to prove 'ttof
    ￿￿
    ttof
    (
    p1p2p3
    )
    is to show that



    2PropwhereProp

    {
    p1p2p3
    }
    ttof
    (

    (
    p1
    )

    (
    p2
    )

    (
    p3
    ))
    'ttof
    (

    )
    This is most easily done with a truth
    table since
    ￿
    2Prop
    ￿
    8
    p1 p2 p3 ttof
    (

    )
    'ttof
    (

    )
    0 0 0 0 0
    0 0 1 0 0
    0 1 0 0 0
    0 1 1 0 0
    1 0 0 0 0
    1 0 1 1 1
    1 1 0 1 1
    1 1 1 1 1
    2 succcarry
    (
    pcq
    )
    We assume that the nth bit is the least significant so the increment
    propagates from the nth to the 1st position We also assume the c vector must contain
    for every ci the value of the carry produced by adding ci
    +
    1 to pi (except for cn which
    contains the carry of adding 1 to pn) so as a result c1

    1i↵thereisoverflowThe
    relation between pcq is as follows
    pn
    +
    1

    qn
    +
    2cn
    and for all 1

    i
    <
    n
    pi
    +
    ci
    +
    1

    qi
    +
    2ci
    The relation between pn cn and qn is captured by the formula
    'n
    (
    pn

    cn
    ∧¬
    qn
    ) ∨ (¬
    pn
    ∧¬
    cn

    qn
    )Also for any 1

    i
    <
    n the only possible assignments to ci
    +
    1 pi qi and ci that ensure
    consistency with the increment operation are the following
    ci
    +
    1 pi qi ci
    0 0 0 0
    1 0 1 0
    0 1 1 0
    1 1 0 1
    9From this table we can construct in DNF form the formula 'i that captures the
    relation between ci
    +
    1piqici
    'i [(
    ¬
    ci
    +
    1
    ∧¬
    pi

    qi

    ci )

    ( ci
    +
    1
    ∧¬
    pi

    qi
    ∧¬
    ci )

    (
    ¬
    ci
    +
    1

    pi

    qi
    ∧¬
    ci )

    ( ci
    +
    1

    pi
    ∧¬
    qi

    ci )]
    Then the following formula is logically equivalent to succcarry
    (
    pcq
    )


    ￿
    1

    i

    n
    'i
    By construction this formula ' ensures the correct incrementcarry propagation so
    it only allows (pcq) that represent the original number bitbybit carry and result
    numbers respectively and thus is logically equivalent to succcarry Also since there
    is one constantsized term for the last bit and there are four fourliteral disjunctions
    for every bit from 1 to n1 the size of ' is O
    (
    n
    )

    The automaton is constructed as in the figure above For simplicity of the figure
    we provide an automaton that accepts any length of vectors pqc (top) and then
    10we can intersect it with an automaton that accepts strings of length 3n only (bot
    tom) The order in which the atomic propositions must be fed into this automaton is
    pnqncnp1q1c1 (the figure explicitly shows which transition should correspond
    to which proposition between parenthesis next to the transition label this is for clari
    fication and is not part of the automaton of course) Also note that to avoid cluttering
    the figure all unspecified transitions go to a trap state’ that is never left and so the
    automaton will not accept such strings
    The transitions for the automaton can be derived directly from the truth table above
    (the one used to build the formula) where only those combinations present in the table
    are the ones allowed The states labeled with last carry was 1 and last carry was
    0 help identify in which situation we are ie if the addition of the last pi with ci
    +
    1
    produced a new carry ci or not So making last carry was 1 the initial state is
    equivalent to adding 1 to p and making both labeled states accepting ensures that
    the string seen so far corresponds to a valid increment of p
    The final automaton that accepts 3 vectors of length n only is obtained by intersecting
    the top automaton with the bottom one since the bottom one accepts all strings of
    length 3n and nothing else Since the top automaton has 8 states (including the
    omitted trap state’) and the bottom one has 3n
    +
    1 states the cartesian product
    automaton for the intersection has at most 24n
    +
    8 states which is O
    (
    n
    )

    3
    {∨

    ∧}
    is not adequate
    Let ⌧0

    Prop
    → {
    01
    }
    be defined as ⌧0
    (
    p
    )
    0 for all p

    Prop Then every function f
    in Form
    {∧

    ∨}
    satisfies f
    (
    ⌧0
    )
    0 Proof by induction
    • Base Case if f

    p

    Prop then f
    (
    ⌧0
    )
    p
    (
    ⌧0
    )
    ⌧0
    (
    p
    )
    0
    • Inductive Step
    – f
    ∨(
    f1f2
    )
    By IH f1
    (
    ⌧0
    )
    0 and f2
    (
    ⌧0
    )
    0 and then f
    (
    ⌧0
    ) ∨(
    f1
    (
    ⌧0
    )
    f2
    (
    ⌧0
    ))
    ∨(
    00
    )
    0 by definition of


    – f
    ∧(
    f1f2
    )
    By IH f1
    (
    ⌧0
    )
    0 and f2
    (
    ⌧0
    )
    0 and then f
    (
    ⌧0
    ) ∧(
    f1
    (
    ⌧0
    )
    f2
    (
    ⌧0
    ))
    ∧(
    00
    )
    0 by definition of


    Now the function g
    ¬
    pk for some pk

    Prop does not satisfy the property since
    g
    (
    ⌧0
    ) ¬(
    ⌧0
    (
    pk
    )) ¬(
    0
    )
    1 Then g does not satisfy the property and thus is not
    in Form
    {∨

    ∧}
    sog cannot be constructed with
    {∨

    ∧}
    and thus the set
    {∨

    ∧}
    is not
    adequate
    4
    {↓}
    and
    {￿}
    are adequate
    p q p

    q p
    ￿
    q
    0 0 1 1
    0 1 0 1
    1 0 0 1
    1 1 0 0
    11•
    {↓}
    is adequate We prove by induction that for each formula '

    Form


    ∨}there is a logically equivalent formula

    Form
    {↓}
    Since we know that


    ∨}
    is
    adequate this suces to prove that
    {↓}
    is adequate
    Base Case ' is pwherep

    PropThen' itself is in Form
    {↓}

    Inductive Step We have two subcases
    – '


    )
    By IH there exists ✓


    Form
    {↓}
    such that ✓ is logically
    equivalent to ✓

    And by the truth table for

    above we have



    ) ￿
    ￿(





    )

    Therefore '
    ￿￿(





    ) ∈
    Form
    {↓}

    – '
    (
    ✓1

    ✓2
    )
    By IH there exist ✓

    1 ✓

    2

    Form
    {↓}
    such that ✓1
    ￿￿


    1 and
    ✓2
    ￿￿


    2whichimplies'
    ￿￿(


    1



    2
    )
    And by the truth table of

    we
    have
    (


    1



    2
    ) ￿￿(¬(


    1



    2
    )) ￿￿((


    1



    2
    ) ↓ (


    1



    2
    )) ∈
    Form
    {↓}


    {￿}
    is adequate We prove by induction that for each formula '

    Form


    ∧}there is a logically equivalent formula

    Form
    {￿}
    Since we know that


    ∧}
    is
    adequate this suces to prove that
    {￿}
    is adequate
    Base Case ' is pwherep

    PropThen' itself is in Form
    {￿}

    Inductive Step We have two subcases
    – '


    )
    By IH there exists ✓


    Form
    {￿}
    such that ✓ is logically
    equivalent to ✓

    And by the truth table for
    ￿
    above we have



    ) ￿
    ￿(


    ￿


    )

    Therefore '
    ￿￿(


    ￿


    ) ∈
    Form
    {￿}

    – '
    (
    ✓1

    ✓2
    )
    By IH there exist ✓

    1 ✓

    2

    Form
    {￿}
    such that ✓1
    ￿￿


    1 and
    ✓2
    ￿￿


    2whichimplies'
    ￿￿(


    1



    2
    )
    And by the truth table of
    ￿
    we
    have
    (


    1



    2
    ) ￿￿(¬(


    1
    ￿


    2
    )) ￿￿((


    1
    ￿


    2
    )￿(


    1
    ￿


    2
    )) ∈
    Form
    {￿}

    5
    {
    false
    →}
    is adequate
    We prove by induction that for each formula '

    Form


    ∨}
    there is a logically equiv
    alent formula

    Form
    {
    false
    →}
    Since we know that


    ∨}
    is adequate this suces
    to prove that
    {
    false
    →}
    is adequate
    Base Case ' is pwherep

    PropThen' itself is in Form
    {
    false
    →}

    Inductive Step We have two subcases
    • '


    )
    By IH there exists ✓


    Form
    {
    false
    →}
    such that ✓
    ￿￿


    Also


    ) ￿￿((¬

    ) ∨
    false
    ) ￿￿(


    false
    )
    Therefore '
    ￿￿(



    false
    ) ∈
    Form
    {
    false
    →}

    • '
    (
    ✓1

    ✓2
    )
    By IH there exist ✓

    1 ✓

    2

    Form
    {
    fasle
    →}
    such that ✓1
    ￿￿


    1
    and ✓2
    ￿￿


    2whichimplies'
    ￿￿(


    1



    2
    )
    Therefore '
    ￿￿(


    1



    2
    ) ￿
    ￿((¬


    1
    ) →


    2
    )) ￿￿((


    1

    false
    ) →


    2
    ) ∈
    Form
    {
    false
    →}

    126 + is not adequate
    p q p
    +
    q
    0 0 0
    0 1 1
    1 0 1
    1 1 0
    Let ⌧0

    Prop
    → {
    01
    }
    be defined as ⌧0
    (
    p
    )
    0 for all p

    Prop Then every function f
    in Form
    {+}
    satisfies f
    (
    ⌧0
    )
    0 Proof by induction
    • Base Case if f

    p

    Prop then f
    (
    ⌧0
    )
    p
    (
    ⌧0
    )
    ⌧0
    (
    p
    )
    0
    • Inductive Step
    – f
    +(
    f1f2
    )
    By IH f1
    (
    ⌧0
    )
    0 and f2
    (
    ⌧0
    )
    0 and then f
    (
    ⌧0
    ) +(
    f1
    (
    ⌧0
    )
    f2
    (
    ⌧0
    ))
    +(
    00
    )
    0 by definition of
    +

    Now the function g
    ¬
    pk for some pk

    Prop does not satisfy the property since
    g
    (
    ⌧0
    ) ¬(
    ⌧0
    (
    pk
    )) ¬(
    0
    )
    1 Then g does not satisfy the property and thus is not in
    Form
    {+}
    sog cannot be constructed with
    {+}
    and thus the
    {+}
    is not adequate
    13

    《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
    该内容是文档的文本内容,更好的格式请下载文档

    下载pdf到电脑,查找使用更方便

    pdf的实际排版效果,会与网站的显示效果略有不同!!

    需要 3 香币 [ 分享pdf获得香币 ]

    下载pdf

    相关文档

    4.超市服务手册-4

    济南易格商务咨询有限公司超市培训文件 文件编号 :EAGER2002-004 超 市 服 务 手 册 编制:高国彬( Maidi ) ...

    14年前   
    30554    0

    信息4

    郯城县司法局多措并举深化“放管服”改革不断优化营商环境为进一步畅通便民服务渠道,满足群众公共法律服务需求,郯城县司法局紧紧围绕服务全县经济发展的大局,发挥司法行政职能作用,聚焦“放管服”改革,...

    4年前   
    502    0

    2017年4月辞职信4

    2017年4月辞职信4  尊敬的xxx领导:  很遗憾在这里我要跟您们提出辞职!  哭有时,笑有时,欢乐有时,悲伤也有时!人生如此,在公司的短暂工作也是如此。  我从来不觉得自己会亲手递上这份...

    7年前   
    451    0

    4A Module 4 The natural world教学设计

    在语境中学习单词:复习动物叫声(moo, baa, oink, peep),并学习掌握新的动物叫声(nay, baa)。能用They go…句型来描述各类农场动物的叫声。

    5年前   
    1651    0

    27漏4 第4位老师 教案

     关注学生语言实践  提升语文核心素养                                ------《漏》(第一课时)教学设计 执教:谢文静      单位:阜阳市清河路第一小学...

    4年前   
    804    0

    管理评审会议记录4月4日

    会议记录 表格编号:QR-0209 会议主题 2003年品质管理体系管理评审 会议时间 2003年4月4日 会议地点 会议室 主持人 记录人 出席人员 ...

    11年前   
    12052    0

    4A Module 4 The Natural World教学设计

    在语境中学习单词:peanut butter, candy, sketchbook, cap, camera词组:in the picnic basket, go to Century Park...

    5年前   
    1871    0

    Unit4sectionA4(4a-4c)导学案人教版八年级英语下册

    1)阅读短文,能按要求找到相应的信息。2)通过阅读提高学生们的阅读能力。3)了解在如果生活中发生了一些不尽如人意的问题,应当如何面对理性地去解决。

    1年前   
    272    0

    第4周第4课时八下4-3运用公式法(1)

    能用提供因式法、公式法(直接利用公式不超过两次)进行因式分解(指数是正整数)。

    5年前   
    1110    0

    英语-教学总结4

    小学英语教师工作总结时光飞逝,岁月如流。仔细回味,充满着生机和活力的小学英语已经陪我走过了又一个年头。我也已经不知不觉完成了一年的小学英语工作。在这一年里,我付出辛劳,收获成功,与我的学生们一...

    4年前   
    680    0

    力帆软文-4

    力帆520登陆龙江力帆集团作为新汽车产业政策实施后第一个获得轿车生产资格的企业,年初推出了第一款自主品牌轿车力帆520。时尚外观、卓越动力、丰富配置是力帆520三个突出特点。精湛的做工及流线造...

    11年前   
    563    0

    调侃4

    调侃1.高中时全校必须穿校服,有一复读的学生从来都不穿。管这方面的老师天天蹲在门口检查。一日,老师看到此同学没穿校服,问其为什么不穿。此同学大怒,曰:我妈又没死,为什么要穿孝服?7.生物课上,...

    11年前   
    507    0

    抵押合同(4)

    抵押合同(4)   合同编号: 年 字第 号   抵押人名称 ,住所 ...

    10年前   
    25864    0

    《管理语论》4

    卷四·一个过程:调控信息·反馈 你能得到多少,往往取决于你能知道多少。误人无过真假,成败全在取舍。知好意知歹意,可知真意;通外情通内情,能得实情。信息对我们的价值,决定我们对信息的看法。你对事...

    11年前   
    359    0

    员工手册 (4)

    美的企业集团员工手册内容 (修订稿) 第一部分:公司概况及发展 1、 美的企业集团简介 2、 美的集团大事记 3、 “十五”发展蓝图 第二部分:企业文化理念 1、 美的商标寓意 ...

    10年前   
    25616    0

    员工请假办法4

    员工请假办法      第一章 总 则 第一条 为规范公司考勤制度,统一公司请假政策,特制定本办法。 第二章 请假程序 第二条 员工填写请假单,注明请假种类、假期...

    14年前   
    10574    0

    系统化4

    宽带网系统是智能房产管理、生活、通信智能化的神经系统,它以控制、通信、计算机管理为内容,以综合布线为基础,实现控制管理整体智能化。系统的功能实现可以灵活充分的利用每根“神经”,使系统的集中管理...

    8年前   
    3142    0

    说课稿 (4)

    《海底世界》说课稿一、说教材《海底世界》是部编版教材小学语文第六册的第七单元的一篇课文,这是一篇有关海洋的常识性课文,全文用生动形象的语言介绍了海底的景色奇异、物产丰富。全文共有7个自然段。第...

    4年前   
    755    0

    工厂实习报告_4

    工厂实习报告  工厂实习报告篇1   一、实习说明   (1)实习时间:20XX年12月6日至20XX年6月21日   (2)实习地点:安徽芜湖美的制冷设备有限公司分体分厂   ...

    2年前   
    407    0

    4 现场服务记录

    实施/服务记录公司名称 联系人 电话传真日期 签到时间 离开时间服务性质 无偿 □ ...

    11年前   
    935    0