1

Given a function F that accepts two pairs of 2 bit integers (from 0 to 3), that returns the integer division of the two integers as a two bit integer. Is said function a universal operator? (Assume division by 0 is not possible).

(1,0) / (1,0) = (1,0)

We've never really been taught the proper way to prove such things, only to insert values and check if it's possible to implement NOT+OR / NOT+AND / NAND / NOR.

However, with this function, I don't understand:

  1. How it's possible to have two outputs?
  2. What values to insert?

Here's how far I got:

F(1,0,1,0) = (0)(1)    <---- Means we can now use 0 and 1 + made 1 (right?)
F(0,  0,1,0) = (0)(0)    <---- Means we made 0.
F(1,0, 1, 0) = (0)(1)   <---- we can change 0 to 1. (How does that help?)

For clarity, consider the following (partial) truth table:

1,0,1,0   1,0
0  0  0  0  = x  x
0  0  0  1  = 0  0
0  0  1  0  = 0  0
0  0  1  1  = 0  0
0  1  0  0  = x  x
0  1  0  1  = 0  1
0  1  1  0  = 0  0
0  1  1  1  = 0  0
1  0  0  0  = x  x
1  0  0  1  = 1  0
Alex Osheter
  • 231
  • I don't really understand what you are asking. – kimchi lover Feb 16 '20 at 12:38
  • I'm asking if F is universal, and (assuming it is) what's the proof? I don't know how to approach this problem. – Alex Osheter Feb 16 '20 at 12:54
  • And I'm asking, what does "universal" mean here? – kimchi lover Feb 16 '20 at 12:56
  • A universal operator is an operator which, given two inputs can produce NOT & AND. Or NOT & OR. Or NAND. Or NOR. Essentially meaning that using this one function (and the right input) you can achieve any desirable output. – Alex Osheter Feb 16 '20 at 15:27
  • So this function takes in 2-bit numbers and returns a 2-bit binary number? How then can it take in single bit numbers and generate a 1-bit output? Because that is what the AND, OR, NOT, NAND, etc. all do. Indeed, I know what universal operators are in the context of boolean logic, but in this context I am not sure what you are looking for. So, can you please specify exactly what is meant by 'universal function' in this context? Also, I see that when you try to divide by $0$, you get $x$'s at the output? So ..., how does that factor into the 'universality' of the operator? – Bram28 Feb 17 '20 at 21:05

0 Answers0