Boolean Functions – How many unique boolean functions in two variables are there

Question

Boolean Functions – How many unique boolean functions in two variables are there?
– Of those unique boolean functions, how many depend on neither input (i.e., are constant)?
– Of those unique boolean functions, how many depend on only one of the two inputs (i.e., the other input has no eect on the output)?
– Of those unique boolean functions that depend on both inputs, how many of them are identiable / named in common terms (i.e., and, or, etc.)?
– Using only and, or, not, can you construct formulae for all unique boolean functions on two inputs?

• Play a few rounds of minesweeper, as carefully and as thoughtfully as you can. Try to identify at least dierent three clue congurations that let you reason about whether a square is mined or safe, and identify the logical structure of the inference rule you used.

Explanation / Answer

2 binary input can create 4 (2^2) different combinations.

These 4 outputs can be mapped to a 4 bit binary number, e.g.

X and Y are binary inputs, and the result X OR Y can be mapped to 0111

Thus we can easily map this output to any one of 16 4bit binary number, hence we can have 16 different function.

Let me now provide logic for each of them:

F0: 0000 (0)
F1: 0001 (A & B)
F2: 0010 (A&B’)
F3: 0011 (A)
F4: 0100 (A’&B)
F5: 0101 (B)
F6: 0110 (A’&B OR A&B’) (XOR)
F7: 0111 (A OR B)
F8: 1000 (A’ & B’)
F9: 1001 (A’ & B’ OR A&B) (XNOR)
F10:1010(B’)
F11:1011(A OR A’&B’)
F12:1100(A’)
F13: 1101(A’ OR AB)
F14: 1110 (A’ OR B’)
F15: 1111 (1)

So only F0 and F15 are independent of the input.

If you face any doubt, feel free to ask in the comment section.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.