Propositional Logic · Functional Completeness

Lesson 12

Nikolai Chukhin · Alexander S. Kulikov

Problem. Mark all bases that are complete.

5 points

  1. \(\{\operatorname{OR}_{2}, \operatorname{NOT}_{1}\}\)

  2. \(\{\operatorname{AND}_{2}, \operatorname{OR}_{2}\}\)

  3. \(\{\operatorname{AND}_{2}, \operatorname{XOR}_{2}\}\)

  4. \(\{\operatorname{AND}_{2}, \operatorname{XOR}_{2}, 1\}\)

  5. \(\{\operatorname{NAND}_{2}\}\)

  6. \(\{\operatorname{NAND}_{2}, \operatorname{XOR}_{2}\}\)

  7. \(\{\operatorname{XOR}_{2}\}\)

  8. \(\{\operatorname{XOR}_{2}, 1\}\)

  9. \(\{\operatorname{XOR}_{2}, \operatorname{NOT}_{1}\}\)

  10. \(\{\operatorname{XOR}_{2}, \operatorname{AND}_{2}, \operatorname{OR}_{2}\}\)