and ! operators sufficient to make every possible logical expression?

 

The logical expression ( a && b ) (both a and b have boolean values) can be written like !(!a || !b) , for example. Doesn't this mean that && is "unneccesary"? Does this mean that all logical expressions can be made only using || and ! ?

Yes, as the other answers pointed out, the set of operators comprising of || and ! is functionally complete. Here's a constructive proof of that, showing how to use them to express all sixteen possible logical connectives between the boolean variables A and B :

  • True: A || !A A || !A
  • A NAND B: !A || !B !A || !B
  • B implies A: !B || A !B || A
  • A implies B: !A || B !A || B
  • A OR B: A || B A || B
  • Not B: !B
  • Not A: !A
  • A XOR B: !(!A || B) || !(A || !B) !(!A || B) || !(A || !B)
  • A XNOR B: !(!A || !B) || !(A || B) !(!A || !B) || !(A || B)
  • A: A
  • B: B
  • A NOR B: !(A || B)
  • A does not imply B: !(!A || B)
  • B does not imply A: !(!B || A)
  • A AND B: !(!A || !B)
  • False: !(A || !A)

    • Note that both NAND and NOR are by themselves functionally complete (which can be proved using the same method above), so if you want to verify that a set of operators is functionally complete, it's enough to show that you can express either NAND or NOR with it.

    Here's a graph showing the Venn diagrams for each of the connectives listed above:

    在这里输入图像描述

    [source]

    What you are describing is functional completeness.

    This describes a set of logical operators that is sufficient to "express all possible truth tables". Your Java operator set, { || , ! }, is sufficient; it corresponds to the set {∨, ¬}, which is listed under the section "Minimal functionally complete operator sets".

    The set of all truth tables means all possible sets of 4 boolean values that can be the result of an operation between 2 boolean values. Because there are 2 possible values for a boolean, there are 24, or 16, possible truth tables. 

    A B | 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
----+------------------------------------------------
T T | T  T  T  T  T  T  T  T  F  F  F  F  F  F  F  F
T F | T  T  T  T  F  F  F  F  T  T  T  T  F  F  F  F
F T | T  T  F  F  T  T  F  F  T  T  F  F  T  T  F  F 
F F | T  F  T  F  T  F  T  F  T  F  T  F  T  F  T  F

    Here is a table of the truth table numbers (0-15), the || and ! combinations that yield it, and a description. 

    Table  |  Operation(s)                    | Description
-------+----------------------------------+-------------
  0    | A || !A                          | TRUE
  1    | A || B                           | OR
  2    | A || !B                          | B IMPLIES A
  3    | A                                | A
  4    | !A || B                          | A IMPLIES B
  5    | B                                | B
  6    | !(!A || !B) || !(A || B)         | XNOR (equals)
  7    | !(!A || !B)                      | AND
  8    | !A || !B                         | NAND
  9    | !(A || !B) || !(!A || B)         | XOR
 10    | !B                               | NOT B
 11    | !(!A || B)                       | NOT A IMPLIES B
 12    | !A                               | NOT A
 13    | !(A || !B)                       | NOT B IMPLIES A
 14    | !(A || B)                        | NOR
 15    | !(A || !A)                       | FALSE

    There are plenty of other such functionally complete sets, including the one element sets {NAND} and {NOR}, which don't have corresponding single operators in Java.

    Yes.

    All logic gates can be made from NOR gates.

    Since a NOR gate can be made from a NOT and an OR, the result follows.

    链接地址: http://www.djcxy.com/p/58902.html

    上一篇: 我如何处理未经检查的投射警告？

    下一篇: 和！ 运营商足以让每一个可能的逻辑表达？