I've been playing a bit with ternary logic and arithmetic. The initial reason I started thinking about this is that it annoyed me how in binary a n-bit signed integer can represent the range [- 2^(n-1) ; 2^(n-1) - 1], which isn't symmetrical. Of course that's only a convention (although one that is very convenient for several reasons) and it could as well represent [- 2^(n-1) + 1/2 ; 2^(n-1) - 1/2], but then 0 wouldn't be represented.

In ternary, a n-"tit" signed integer can represent all the integers in [-(3^(n-1) - 1)/2 ; (3^(n-1) - 1)/2]. So a 3-tit signed integer can represent the 27 numbers between -13 and +13, for example.

Let's see how to construct such a numbering system. We could use 3's complement for negative numbers. For example, with 2-tit numbers:
12 = -4
20 = -3
21 = -2
22 = -1
00 = 0
01 = 1
02 = 2
10 = 3
11 = 4
Now that's very ugly, and there is no obvious way to determine whether a number is negative or positive from it's ternary representation. I don't like it.

So instead of assigning to each tit a value in {0, 1, 2}, we can instead assign them a value in {-1, 0, 1}. For convenience and legibility, I will note the different symbols as {1̃, 0, 1}, but remember that 1̃ has a value of -1. With those values, and a classic positional system, we can easily represent all natural numbers.
The positive numbers are:
0, 1, 11̃, 10, 11, 11̃1̃, 11̃0, ...
(0, 1, 2, 3, 4, 5, 6, ...)
The negative numbers are:
1̃, 1̃1, 1̃0, 1̃1̃, 1̃11, 1̃10, 1̃11̃, ...
(-1, -2, -3, -4, -5, -6, -7, ...)

This system has some nice properties:
1. All natural numbers have a unique representation
2. The range that can be represented by an n-tit number is symmetrical with regards to 0
3. The leftmost non-0 tit contains the sign information
4. The opposite of a number can be easily computed by replacing all 1s by 1̃s and all 1̃s by 1s
5. It's a positional system, so usual algorithms for addition and multiplication apply.
6. A n-tit variable can represent ~60% more values than a n-bit variable

We can also have a gray-like code. Here's how to generate a sequence where each consecutive term only differs by one tit:
1. Start with the sequence S ← {1̃, 0 1}
2. T and U both take the elements of S
3. S is reversed
4. Each element t of T has the tit 1̃ appended to its left
5. Each element s of S has the tit 0 appended to its left
6. Each element u of U has the tit 1 appended to its left
7. S ← T | S | U where "|" represents the concatenation operator.
8. Redo steps 2 to 7 until the sequence is long enough.

For example, with 2-tit numbers, we get:
1̃1̃ 1̃0 1̃1 01 00 01̃ 11̃ 10 11


Now let's do some logic!
We could easily emulate binary logic, for example by interpreting 0 as a boolean 0 and 1̃ and 1 as a boolean 1. That's not fun though, and wouldn't allow us to compute on ternary numbers, so let's invent toolean logic.
I tried coming up with a few logic gates, as extensions to the ones we're used to with booleans.

"and", it's a ternary multiplication. Notice how the lower-right quadrant is the same as with the boolean and. I'll note the operator as ⋅
 a⋅b | 1̃ 0 1
----+-------
1̃ | 1 0 1̃
0 | 0 0 0
1 | 1̃ 0 1
That one has some nice properties:
(a ⋅ b) ⋅ c = a ⋅ (b ⋅ c) = a ⋅ b ⋅ c
a ⋅ a = abs(a) (that is, 1̃→1, 0→0 and 1→1)
1̃ ⋅ a = neg(a) (that is, 1̃→1, 0→0 and 1→1̃)
1 ⋅ a = a
0 ⋅ a = 0
a ⋅ b = neg(a) ⋅ neg(b)

"or", it's a ternary saturating addition. Again the lower-right quadrant is the same as with the boolean or. I'll note the operator as +
a+b | 1̃ 0 1
----+-------
1̃ | 1̃ 1̃ 0
0 | 1̃ 0 1
1 | 0 1 1
That one isn't as nice, so I would be happy if you have better suggestions. In particular, I hate that (a + b) + c ≠ a + (b + c). Still, a few interesting properties:
neg(a) + neg(b) = neg(a + b)
a + a = a
0 + a = a
a + neg(a) = 0

"xor", isn't an overflowing addition (half adder), because I wanted the lower-right cadrant to stay the same as the boolean xor. I'll note the operator as ⊕
 a⊕b | 1̃ 0 1
----+-------
1̃ | 0 1̃ 0
0 | 1̃ 0 1
1 | 0 1 0
Again, I hate that (a ⊕ b) ⊕ c ≠ a ⊕ (b ⊕ c)
Some properties:
a ⊕ b = (a + b) + ((a + b) ⋅ a ⋅ b) (can this expression be simplified?)
a ⊕ a = 0
0 ⊕ a = a
a ⊕ neg(a) = 0

There is no "not", because why would not(0) be 1 over 1̃? In any case both variant can be implemented as (a ⊕ 1) and (a ⊕ 1̃) respectively.


Can the logic operators do arithmetic? Yes they can!
Here's the truth table for a half adder
| 1̃ 0 1
----+-------
1̃ | 1 1̃ 0
0 | 1̃ 0 1
1 | 0 1 1̃
That is, (a ⊕ b) + ((a + b) ⋅ neg(a ⋅ b)). Can this expression be simplified?

And here's the truth table for a full adder
| 1̃1̃ 1̃0 1̃1 01 00 01̃ 11̃ 10 11
----+------------------------------
1̃ | 1̃0 1̃1 01̃ 00 01̃ 1̃1 01̃ 00 01
0 | 1̃1 01̃ 00 01 00 01̃ 00 01 11̃
1 | 01 00 01 11̃ 01 00 01 11̃ 10
Now I haven't got a clue as to where to start to get a toolean expression out of this.


What do you think about all this? Did I make any mistake?
Some more things I want to look into:
1. Other properties of toolean logic, especially to help find and simplify expressions
2. Find an expression for the full adder
3. Design ternary CMOS circuits
4. Check out what people smarter than me have written, but I want to play around a bit more before.

I can't figure out why there are 3 digits on the right side of the truth tables.

Ah, got it.

"Not", "and" and "or" should also satisfy De Morgan's laws. Then (3) would be trivial.

If i'm correct, then there are only 5 ternary logics which are:
1. extension of boolean logic
2. satisfying to De Morgan's laws
3. commutative, associative and distributive over "and" and "or"
4. have following properties: a&0=0, a&1=a, a|0=a

P90879
Is that not a standard way to present truth table? The formatting is like so:
| input1
-------+--------
input2 | output

And with more than 2 inputs:
| input1input2
-------------+--------------
input3input4 | output
with input1input2 represented in the order of a gray code. For example, the full-adder's truth table is a 3×3×3 cube that was "unfolded" to a 3×9(×1) rectangle.
Usually I would format them a bit better by specifying which column represents which input/output, but I didn't bother here, since all the operators I presented are commutative.

I hate truth tables presented like
input1 | input2 | output
They are cumbersome and they don't help with getting an expression out of them.

P90882
That would be ideal, but I couldn't find a set of operators that works. I at least want to find a set of associative and distributive operators (that are useful. I don't care about a null operator or similar).
How does De Morgan's laws relate to designing CMOS circuits? As far as I'm aware, they only helps with simplifying expressions.

P90905
AFAIK De Morgan's laws allow to implement any boolean function as a combination of NAND op.

P90904
Nice, how did you find these? An exhaustive search?
I like your notation, with i instead of 1̃. Faster to type, and less compatibility issues.

What additional properties do your operators have?
1. and | i 0 1 or | i 0 1 not |
-----+------- ----+------- -----+---
i | 0 0 i i | i i 1 i | 1
0 | 0 0 0 0 | i 0 1 0 | 1
1 | i 0 1 1 | 1 1 1 1 | 0
a + a = a
a + 1 = 1
a ⊕ b := a⋅not(b) + not(a)⋅b = (a+b) ⋅ not(a⋅b)
 a⊕b | i 0 1
----+-------
i | i i 1
0 | i 0 1
1 | 1 1 0
a⊕not(a) = 1

2. and | i 0 1 or | i 0 1 not |
-----+------- ----+------- -----+---
i | i 0 i i | i i 1 i | 0
0 | 0 0 0 0 | i 0 1 0 | 1
1 | i 0 1 1 | 1 1 1 1 | 0
a + a = a
a + 1 = 1
a ⋅ a = a
not(not(a)) = abs(a)
a ⋅ not(a) = 0
a ⊕ b := a⋅not(b) + not(a)⋅b = (a+b) ⋅ not(a⋅b)
 a⊕b | i 0 1
----+-------
i | 0 i 0
0 | i 0 1
1 | 0 1 0
a⊕a = 0

3. and | i 0 1 or | i 0 1 not |
-----+------- ----+------- -----+---
i | i 0 i i | i i 1 i | 1
0 | 0 0 0 0 | i 0 1 0 | 1
1 | i 0 1 1 | 1 1 1 1 | 0
a + a = a
a + 1 = 1
a ⋅ a = a
a + not(a) = 1
a ⊕ b = a⋅not(b) + not(a)⋅b = (a+b) ⋅ not(a⋅b)
 a⊕b | i 0 1
----+-------
i | i i 1
0 | i 0 1
1 | 1 1 0
a⊕not(a) = 1

4. and | i 0 1 or | i 0 1 not |
-----+------- ----+------- -----+---
i | i 0 i i | i i 1 i | i
0 | 0 0 0 0 | i 0 1 0 | 1
1 | i 0 1 1 | 1 1 1 1 | 0
a + a = a
a + 1 = 1
a ⋅ a = a
not(not(a)) = a
a ⊕ b := a⋅not(b) + not(a)⋅b = (a+b) ⋅ not(a⋅b)
 a⊕b | i 0 1
----+-------
i | i i i
0 | i 0 1
1 | i 1 0
a⊕i = i

5. and | i 0 1 or | i 0 1 not |
-----+------- ----+------- -----+---
i | i 0 i i | i i i i | 0
0 | 0 0 0 0 | i 0 1 0 | 1
1 | i 0 1 1 | i 1 1 1 | 0
a + a = a
a + i = i
a ⋅ a = a
not(not(a)) = abs(a)
a ⋅ not(a) = 0
a ⊕ b := a⋅not(b) + not(a)⋅b = (a+b) ⋅ not(a⋅b)
 a⊕b | i 0 1
----+-------
i | 0 i 0
0 | i 0 1
1 | 0 1 0
a⊕a = 0

I like 2 the best. Mostly because a⊕a shouldn't be anything other than 0. Compared to 5, I prefere having a+1=1 over a+i=i.

P90906
You still need to implement that NAND gate though. And such circuit wouldn't be optimal compared to one that mixes multiple gate types.

>>P90907
Yes, that's an exhaustive search.

BTW there is only one logic which satisfy P90904 and P90907/2 (without abs) and doesn't require De Morgan.

P90908
Wrong, there are at least 6 of them if you rewrite 0, 1 and i with each other.

P90907
> And such circuit wouldn't be optimal compared to one that mixes multiple gate types.
Debatable.

P90904
I don't think any of those operator sets is complete though. For example, how do you get a "neg" operator out of these?
neg(a) | i 0 1
--------+-------
| 1 0 i

I tried an exhaustive search myself with other constraints. In particular, I removed the requirement that it should extend the boolean logic.
1. "or" and "and" are associative, commutative and verify a+a=a and a⋅a=a
2. The logic satisfies de Morgan's laws
3. "not" is "interesting". That one is arbitrary, but it verifies not(0)≠0 and not(not(0))=0

Attached is my ugly hardcoded code and the 12 logics that satisfy these constraints

P90947
I forgot:
4. "and" distributes over "or", but "or" doesn't distribute over "and"

P90931
Let's say you want a 4-input OR. You can use 8 transistors to make a 4-input NOR and 2 transistors to make an inverter: 10 transistors.
Or you can use 8 transistors to make 4 inverters and 8 transistors to make a 4-input NAND: 16 transistors. The switching speed should be about the same, but the second version takes 60% more area and power.

P90497
You have a mistake somewhere, making (⋅) equal to (+) also satisfies your laws but such logics are not present in the attachment.

P90993
That is if you don't impose De Morgan laws.

P90993
The logic is there. The function "choose2" returns each pair of different values from the input array. In any case, the constraint would be implicitly in P90949

Constraints:

not(0)≠0
not(not(0))=0
a+a=a
a⋅a=a
a+b=b+a
a⋅b=b⋅a
a+(b+c)=(a+b)+c
a⋅(b⋅c)=(a⋅b)⋅c
a⋅(b+c)=a⋅b+a⋅c
not(a+b)=not(a)⋅not(b)
not(a⋅b)=not(a)+not(b)

Results:

...
and | 0 1 i or | 0 1 i not |
-----+------- ----+------- -----+---
0 | 0 1 1 0 | 0 1 1 0 | i
1 | 1 1 1 1 | 1 1 1 1 | 1
i | 1 1 i i | 1 1 i i | 0
...
and | 0 1 i or | 0 1 i not |
-----+------- ----+------- -----+---
0 | 0 i i 0 | 0 i i 0 | 1
1 | i 1 i 1 | i 1 i 1 | 0
i | i i i i | i i i i | i
...

P91016
Sorry I misunderstood your statement.
These examples don't respect point 4 in P90949, since a+(b⋅c)=(a+b)⋅(a+c)

I think I've found a "nand" equivalent. As in, this single operator is enough to generate any other operator. Let's note it ↑
| i 0 1
----+-------
i | 0 1 i
0 | 1 1 1
1 | i 1 0
For example:
neg(a) = (a↑i)↑1

Added: a+(b⋅c)≠(a+b)⋅(a+c)

Results: 0, lol

BTW no logic with a+not(a)=0 so far.

Given toolean logic L, toolean vector [tex: x_0] and scalar [tex: y_0], what would be the function y(x)={[tex: y_0] if [tex: x=x_0]; 0 otherwise}?

*toolean scalar

P91042
That's strange. Can I see your code?

P91145
I don't know how you could possibly get a general solution for that, and I'm pretty sure most logics can't generate all such operators.
With P91031's "↑", you can have
0 = {0 if x=y₀; 0 otherwise}
(x↑1)↑x = {1 if x=0; 0 otherwise}
(x↑i)↑(x↑i) = {1 if x=i; 0 otherwise}
(x↑1)↑(x↑1) = {1 if x=1; 0 otherwise}
((x↑i)↑i)↑1 = {i if x=0; 0 otherwise}
((x↑i)↑x)↑i = {i if x=1; 0 otherwise}
(((x↑1)↑x)↑i)↑i = {i if x=i; 0 otherwise}
These are all (one of) the shalowest way to get their respective operator.

I checked that this operator can be used to generate all unary functions. I guess an exhaustive listing could prove whether it can generate all binary functions (I haven't coded it yet), but would that be enough to generate all n-ary functions?

P91031
P91162
I can confirm that it can generate all binary operators. And that extends to all n-ary operators (Proof from Waclaw Sierpinski: https://eudml.org/doc/213088)

P91172
Can't read french. Is this done by constructing multiplexers?

P91162
Is that the only NAND-like operator?

P91162
WTF
In boolean they are trivial, like
y(x1, x2, x3, x4) = !x1 & x2 & x3 & !x4 for y(x...)={1 if x==0110; 0 otherwise}

P91174
>Can't read french.
Lol, git gud. But yeah

P91176
Probably not, but I haven't ran an exhaustive search for those.
Thanks for the code, I see I made a dum-dum now. I assumed "Not(a+b) === Not(a)*Not(b)" and "Not(a*b) === Not(a)+Not(b)" were equivalent, which they are not, since not(not(a))≠a. What language is that btw? Looks convenient.


If I didn't make any other mistake, there is no logic that verify:
1. "or" and "and" are associative and commutative
2. None of the operators is a constant
3. The logic satisfies de Morgan's laws
4. "and" distributes over "or"
5. The set of operators is complete, in that it can be used to generate all binary operators by composition.

I can find some if I loosen any of those conditions though. Attached are the logics I found by removing the distributy constraints. Obviously, there are duplicates then.

P91183
> What language is that btw?
Why, it's Haskell.

> I can find some if I loosen any of those conditions though. Attached are the logics I found by removing the distributy constraints.
I would like to remove 3 (De Morgan) instead. Those look like being ad hoc for boolean logic.

P91229
>Why, it's Haskell.
I really should use more functional programming, it makes the code so much clearer.

>I would like to remove 3 (De Morgan) instead.
Fair enough. I'm running the search for those.

P91176
I've found 333 of them. I should have optimised my code better, because it took 12h.
Results and code attached. "ternary_ops.py" is a bunch of helper functions, "find_nands.py" is the script that runs the search.

>>P91261
> 12h
Dude, just use CVC.