Burst leaderboard ad
Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic

Logic Puzzle

Okay, hoping someone here can solve this. I can't.

  • Can you compute the NOT’s of 3 input variables, using as many AND/OR gates as you like but only 2 NOT gates?


In other words, from an input of 3 boolean variables X, Y, and Z, you need to output NOTX, NOTY and NOTZ using only 2 NOT gates and as many AND/OR gates as you like.

  • AND takes 2 or more inputs, and it will output TRUE (or 1) if and only if all inputs are TRUE (or 1).
  • OR takes 2 or more inputs, and it will output FALSE (or 0) if and only if all inputs are FALSE (or 0).
  • NOT takes 1 input, and it will output FALSE (or 0) if the input is TRUE (or 1) and TRUE (or 1) if the input is FALSE(or 0).


I found it here, page 4. You can read some of it if you don't get it yet, I guess.

You can't use IF gates (conditionals in general). Only use AND, OR and up to 2 NOT gates.

Here's what I have so far:
Spoiler

This post has been edited by Itu: 11 May 2012 - 04:30 PM

  • #1
  • 11 May 2012 - 04:27 PM
  • wacko
  • Knows more about BCB than Taeshi
    Member
This puzzle can indeed be solved, and you can look up solutions on the internet if you care to. But it's quite a difficult logic problem, I'm not sure why it would be given to 17-year-olds.

In case you want to challenge yourself, I'm not pointing you towards the solution, but I will say you're definitely on the right track with this much:

Spoiler

  • #2
  • 11 May 2012 - 05:41 PM
www.apple.com/store
  • #3
  • 11 May 2012 - 10:15 PM
Posted Image
Suit, this image won't work when I try to post it here.

This post has been edited by Johnny Hurricane: 11 May 2012 - 10:21 PM

  • #4
  • 11 May 2012 - 10:19 PM
It's a 1x1 spacer gif, probably used to deter hotlinking.
  • #5
  • 11 May 2012 - 10:35 PM
The irony is that I tried to post the goodburger "I know some of these words" picture, and you responded to it with more words I don't understand.
  • #6
  • 11 May 2012 - 11:06 PM
Solution:
A = ~[(X&Y)||(Y&Z)||(Z&X)]
B = ~{ [(A||(X&Y&Z)] & [X||Y||Z] }

~X = (A|B) & (B|(Y|Z)) & { [ (A|(X&Y&Z)) & (X|Y|Z) ] | (Y&Z) | (A) }
~Y = (A|B) & (B|(X|Z)) & { [ (A|(X&Y&Z)) & (X|Y|Z) ] | (X&Z) | (A) }
~Z = (A|B) & (B|(X|Y)) & { [ (A|(X&Y&Z)) & (X|Y|Z) ] | (X&Y) | (A) }

(Where X, Y and Z are the input booleans; & is "AND", | is "OR", ~ is "NOT".)

Might not be the only answer, but it can definitely be written in many ways.

Spoiler

  • #7
  • 15 May 2012 - 05:01 PM
  • wacko
  • Knows more about BCB than Taeshi
    Member
Well done on solving a difficult problem, Itu! I verified your proof by hand, at least for the case of ~X. And yes, 'symmetric' is a far better word than 'even'. ;)

There are other ways to arrive at the same thing as well. You might want to take a look at this article.
  • #8
  • 15 May 2012 - 07:32 PM
Page 1 of 1
  • You cannot start a new topic
  • You cannot reply to this topic

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users