A boolean function is a predicate P(B,..., B) depending on n boolean variables B,..., B. For...

  

Transcribed Image Text:

A boolean function is a predicate P(B₁,..., B) depending on n boolean variables B₁,..., B₁. For example, the following truth table specifies one particular boolean func- tion on 3 variables: B₁ B₂ B3 P(B₁, B2, B3) T T T T T F T FFFFFF T T F F FFTTFE F F T T F T F F T T T T F F F F F (a) Using induction, prove: Theorem 5. Every boolean function is equivalent to a boolean function built using only the logical connectives NOT, AND, and OR (-, A, and V). (b) Show that PVQ can be expressed in terms of only P. Q. NOT, and AND. (c) Recall the logical connective NAND from Homework 1, Question 5. Prove: Corollary 6. Every boolean function is equivalent to a boolean function built using only the logical connective NAND. (d) Express the boolean function on 3 variables above in terms of only NAND. What is the fewest number of NAND's you can use in such an expression? A boolean function is a predicate P(B₁,..., B) depending on n boolean variables B₁,..., B₁. For example, the following truth table specifies one particular boolean func- tion on 3 variables: B₁ B₂ B3 P(B₁, B2, B3) T T T T T F T FFFFFF T T F F FFTTFE F F T T F T F F T T T T F F F F F (a) Using induction, prove: Theorem 5. Every boolean function is equivalent to a boolean function built using only the logical connectives NOT, AND, and OR (-, A, and V). (b) Show that PVQ can be expressed in terms of only P. Q. NOT, and AND. (c) Recall the logical connective NAND from Homework 1, Question 5. Prove: Corollary 6. Every boolean function is equivalent to a boolean function built using only the logical connective NAND. (d) Express the boolean function on 3 variables above in terms of only NAND. What is the fewest number of NAND's you can use in such an expression?

Answer rating: 100% (QA)

a Proof We will prove this theorem by induction We will make the assumption that for any boolean function PB1 Bn built using only the logical connectives NOT AND and OR A and V there exists a boolean ... View the full answer