Results 1 to 3 of 3

Math Help - Prove Functional Completeness

  1. #1
    Junior Member
    Joined
    Aug 2009
    Posts
    71

    Prove Functional Completeness

    Hello, I believe I just need a nudge in the right direction with the following problem:

    A set of logical operators is functionally complete if every compound proposition is logically equivalent to one using only the operators in the set. Prove that NOT and OR form a functionally complete set of operators.

    I am not quite sure how to approach the problem. It seems to be the case that two statements can be equivalent by using only the two operators. In this case OR and NOT.

    Thanks for any and all help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    From
    Rez
    Posts
    21
    I believe a set of operators is functionally complete if every boolean operation (AND, OR, and NOT) can be implemented using them. You already have OR and NOT, so all you need to do is prove that you can implement AND using OR and NOT.

    You can use deMorgan's Law: NOT((NOT a) OR (NOT b)) = a AND b
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2009
    Posts
    71
    Thank you for your help. That makes complete sense.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove Or Disprove Completeness of Z
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 26th 2011, 02:10 PM
  2. Completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: January 12th 2010, 08:17 AM
  3. a question on completeness within functional analysis
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: January 4th 2010, 10:42 PM
  4. NP Completeness
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 7th 2009, 02:02 PM
  5. completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: August 13th 2009, 07:30 PM

Search Tags


/mathhelpforum @mathhelpforum