发表于 更新于 分类于 ， 本文字数： 430 阅读时长 ≈ 2 分钟

\(1.2.\)Boolean function construction

1.Basic method

  Our goal is to create a boolean function that fits in the given truth table. To achieve this, we can do the following steps:

  1. Select the line that has the bool value 0and 1 separately.
  2. For each line that has the bool value 0, create a function that is able to get the value.
  3. Combine these functions with or, thus get a new function(say f1).
  4. Do the same thing for bool value 1，and get a new function f2.
  5. Combine the two function with and : f1 and f2.

  Take this truth table as an example:

  • For line 1, 3, 5 that equal 1, we each get: NOT x, NOT x, NOT y.
  • Thus the new function for 1 is NOT x OR NOT x OR NOT y.(Actually, it could have multiple forms)
  • For line 2, 4, 6, 7, 8, we each get: NOT z, NOT y, NOT x, NOT x, NOT x, NOT x.
  • Thus the new function for 0 is NOT x OR NOT y OR NOT x OR NOT x OR NOT x OR NOT x OR NOT x OR NOT x.
  • Combine the two new functions, we get the final result: (NOT x OR NOT x OR NOT y) AND (NOT x OR NOT y OR NOT x OR NOT x OR NOT x OR NOT x OR NOT x OR NOT x).

  Once we get the final result, we can use boolean function calculation to simplify it.

2.Simplify the system

  Actually, we don't need OR to join the process, we can complete the task only by AND and NOT. This is because the De Morgan's laws allow us to transform an OR into AND clause.

  Furthermore, we define NAND as NOT AND. For example, x NAND y is equal to NOT x AND y. We can prove that every boolean function can be represented by only the NAND statement.

  \(proof:\)Since we are able to represent all boolean functions by AND and NOT, we only need to represent AND and NOT using NAND:

  • NOT x can be represented by x NAND x, this is obvious.
  • x AND y can be represent by (x NAND y)NAND(x NAND y). We can rewrite the statement as NOT(NOT x AND y), the statement in the parentheses is x NAND y itself, so it is transform into NOT x NAND y. Using NOT representation again, and we get the result.