Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is trivial and non-trivial gate in computing?

  1. Dec 19, 2014 #1
    My question seems like it should be posted in Computer Engineering section, but below is how I found this word.

    I was reading the textbook:
    Quantum Computation And Quantum Information - by Michael A. Nielsen and Issac L. Chuang.
    and I came across with the this word;

    "1.3.1 Single qubit gates
    Classical computer circuits consist of wires and logic gates. The wires are used to carry information around the circuit, while the logic gates perform manipulations of the information, converting it from one form to another. Consider, for example, classical single bit logic gates. The only non-trivial member of this class is the NOT gate, whose operation is defined by its truth table, in which 0 → 1 and 1 → 0, that is, the 0 and 1 states are
    interchanged."

    I was wondering the meaning of this word, and I googled, then one source came;
    ----------
    logic gate (plural logic gates)

    1. a physical device, typically electronic, which computes a Boolean logical output (0 or 1) from Boolean input or inputs according to the rules of some logical operator.
      There are six non-trivial, symmetric, two-input, Boolean logic gates: AND, OR, XOR, NAND, NOR and XNOR.
    ----------
    http://en.wiktionary.org/wiki/logic_gate

    so,what is the meaning of trivial and non-trivial gate in "conventional" logic gate and what are the full examples?
     
  2. jcsd
  3. Dec 19, 2014 #2

    DaveC426913

    User Avatar
    Gold Member

    Oh I see. They're talking about single input gates.

    So, it can take one input (0 or 1), and provide one output (0 or 1).

    A logic gate that is defined by the truth table (0>0, 1>1) is trivial because it does absolutely nothing. It might as well not be there at all.
    So - of the two possible gates - the only non-trivial single bit gate is the NOT, which is defined as (0>1,1>0).
     
  4. Dec 20, 2014 #3
    I'm confused.
    trivial = single input?

    wiktionary says
    There are six non-trivial, symmetric, two-input, Boolean logic gates: AND, OR, XOR, NAND, NOR and XNOR.

    but these logic gates mentioned above are not single input gates.

    how do I distinguish that with

    The only non-trivial member of this class is the NOT gate

    ???

    or are you talking about

    trivial = does absolutely nothing?
     
  5. Dec 20, 2014 #4

    DaveC426913

    User Avatar
    Gold Member

    No. "Single input "means only one input signal (the gate is a back box that has a single "wire" going in). In the binary world that wire can only send a 0 or a 1 into the gate.

    A gate that takes a 0 as input and outputs a 1, or takes a 1 and outputs a 0 could be useful in a circuit.

    A gate that takes a 0 as input and outputs a 0, or takes a 1 and outputs a 1 accomplishes nothing - it might as well not be in the circuit at all.


    Yes, so for TWO-input gates (so the gate is a black box with two "wires" in), your input choices are: 00, 01,10,11
    There are 6 ways inside the black box you could manipulate it so that the output is useful.

    No, they're two-input gates.




    That is referring to the single-input gates, as described at the top of this post.

    I'd have said 'nothing useful', but yes. (I can imagine trivial gates that do something, just not a useful something. eg. a single-input gate could take either zero or one and always output a zero. They seem to consider that trivial if I read between the lines.)

    Here's five two-input gates and one single-input gate (NOT).

    fig-arch-gates.png
     
    Last edited: Dec 20, 2014
  6. Dec 21, 2014 #5
    I see... Thank you very much.

    Now I understand.
     
  7. Dec 23, 2014 #6

    DaveC426913

    User Avatar
    Gold Member

    Glad I could help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What is trivial and non-trivial gate in computing?
  1. Trivial spin problem (Replies: 17)

Loading...