Results 1 to 2 of 2

Math Help - Not Functionally Complete

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    178

    Not Functionally Complete

    Show that each set of gates in not functionally complete.

    {AND}

    {AND, OR}

    While I can picture and understand why these gates are not functionally complete, I don't know how to show this using Boolean expressions (edit: answer does not use any math; only words) My biggest problem is how to start. If I can get the start, I should be able to take it from there.
    Last edited by Truthbetold; September 30th 2010 at 06:51 PM. Reason: Clarify something
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    The short answer is that AND and OR are monotonic with respect to the usual ordering on {0, 1}, while NOT is non-monotonic.

    For the long answer, one has to define a Boolean formula (or circuit). It is defined inductively.

    1. If x is a variable, then it is a formula.
    2. If A and B are formulas, then A AND B, as well as A OR B, are formulas.

    Then, given a valuation f : V -> {0, 1}, where V is the set of variables, one extends it to formulas as usual, so that f(A) is in {0, 1}.

    For two valuations f1, f2 : V -> {0, 1}, write f1 <= f2 if f1(x) <= f2(x) for all x in V.

    Then one shows by induction on formulas that for any formula A and two valuations f1 <= f2, f1(A) <= f2(A). Therefore, negation is not expressible by any formula.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. IS it complete?
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: May 25th 2011, 12:47 AM
  2. Not functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 17th 2010, 05:15 AM
  3. functionally complete set of connectives
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 15th 2010, 12:50 PM
  4. Complete Set
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 4th 2009, 04:17 AM
  5. is this complete ?
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: December 21st 2007, 12:55 PM

/mathhelpforum @mathhelpforum