Results 1 to 3 of 3

Thread: 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: Feb 26th 2011, 01:10 PM
  2. Completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Jan 12th 2010, 07:17 AM
  3. a question on completeness within functional analysis
    Posted in the Differential Geometry Forum
    Replies: 9
    Last Post: Jan 4th 2010, 09:42 PM
  4. NP Completeness
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 7th 2009, 01:02 PM
  5. completeness
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Aug 13th 2009, 06:30 PM

Search Tags


/mathhelpforum @mathhelpforum