Ternary logic
| This page uses content from Wikipedia. The original article was at Ternary logic. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
In logic, a three-valued logic (also trivalent, ternary, or trinary logic, sometimes abbreviated 3VL) is any of several many-valued logic systems in which there are three truth values indicating true, false and some indeterminate third value. This is contrasted with the more commonly known bivalent logics (such as classical sentential or boolean logic) which provide only for true and false. Conceptual form and basic ideas were initially created by Łukasiewicz, Lewis and Sulski. These were then re-formulated by Grigore Moisil in an axiomatic algebraic form, and also extended to n-valued logics in 1945.
|
|
| ||||||||||||||||||||||||||||||||||||||||
|
| |||||||||||||||||||||||||||||||||||||||||
Task:
- Define a new type that emulates ternary logic by storing data trits.
- Given all the binary logic operators of the original programming language, reimplement these operators for the new Ternary logic type trit.
- Generate a sampling of results using trit variables.
- Kudos (κῦδος) for actually thinking up a test case algorithm where ternary logic is intrinsically useful, optimises the test case algorithm and is preferable to binary logic.
Note: Setun (Сетунь) was a balanced ternary computer developed in 1958 at Moscow State University. The device was built under the lead of Sergei Sobolev and Nikolay Brusentsov. It was the only modern ternary computer, using three-valued ternary logic
ALGOL 68
File: Ternary_logic.a68 <lang algol68># -*- coding: utf-8 -*- #
MODE TRIT = STRUCT(BITS trit); INT trit width = 1, trit base = 3; FORMAT trit fmt = $c("⌊","⌈","?" #|"~"#)$;
- These values treated are as per "Balanced ternary" #
- eg true=1, maybe=0, false=-1 #
TRIT true =INITTRIT 4r1 #⌈#, maybe=INITTRIT 4r0 #?#,
false=INITTRIT 4r2 #⌊#;
TRIT flip=true, flop=false, flap=maybe;
OP REPR = (TRIT t)STRING:
IF t = false THEN "⌊"
ELIF t = maybe THEN "?"
ELIF t = true THEN "⌈"
ELSE raise value error(("invalid TRIT value",INITINT t));~
FI;
- Define some OPerators for coercing MODES #
OP INITTRIT = (BOOL in)TRIT:
(in|true|false);
OP B = (TRIT in)BOOL:
(in=true|TRUE|:in=false|FALSE|
raise value error(("invalid TRIT to BOOL coercion: """, REPR in,""""));~
);
- These values treated are as per "Balanced ternary" #
- n.b true=1, maybe=0, false=-1 #
- Warning: BOOL ABS FALSE (0) is not the same as TRIT ABS false (-1) #
OP INITINT = (TRIT t)INT:
IF t=true THEN 1
ELIF t=maybe THEN 0
ELIF t=false THEN -1
ELSE raise value error(("invalid TRIT value",REPR t));~
FI;
OP INITTRIT = (INT in)TRIT: (
TRIT out;
trit OF out:= trit OF
IF in= 1 THEN true
ELIF in= 0 THEN maybe
ELIF in=-1 THEN false
ELSE raise value error(("invalid TRIT value",in));~
FI;
out
);
OP INITTRIT = (BITS b)TRIT:
(TRIT out; trit OF out:=b; out);
- Define the OPerators for the TRIT MODE #
- These can be optimised by peekng at the binary value #
- These operators are as per "Balanced ternary" #
- Warning: "both" is ignored as it isn't Ternary #
OP LT = (TRIT a,b)BOOL: a EQ false AND b NE false OR a EQ maybe AND b EQ true,
LE = (TRIT a,b)BOOL: a EQ b OR a LT b, EQ = (TRIT a,b)BOOL: trit OF a = trit OF b, NE = (TRIT a,b)BOOL: NOT (a EQ b), GE = (TRIT a,b)BOOL: NOT (a LT b), GT = (TRIT a,b)BOOL: NOT (a LE b);
- A solo, unique and rather confusing CMP OPerator #
PRIO CMP = 5; OP CMP = (TRIT a,b)TRIT:
IF a < b THEN false ELIF a = b THEN maybe ELIF a > b THEN true FI;
- ASCII OPerators #
OP < = (TRIT a,b)BOOL: a LT b,
<= = (TRIT a,b)BOOL: a LE b, = = (TRIT a,b)BOOL: a EQ b, /= = (TRIT a,b)BOOL: a NE b, >= = (TRIT a,b)BOOL: a GE b, > = (TRIT a,b)BOOL: a GT b;
- Non ASCII OPerators
OP ≤ = (TRIT a,b)BOOL: a LE b,
≠ = (TRIT a,b)BOOL: a NE b, ≥ = (TRIT a,b)BOOL: a GE b;
OP - = (TRIT t)TRIT:
IF t=maybe THEN maybe
ELIF t=true THEN false
ELIF t=false THEN true
ELSE raise value error(("invalid TRIT value",REPR t)); ~
FI;
- Warning: This routine ASSIGNS "out" AND returns "carry" #
OP +:= = (REF TRIT out, TRIT arg)TRIT:
IF out = maybe THEN out := arg; maybe ELIF arg = maybe THEN # out:= out# arg ELIF out = arg THEN out := -out; arg ELIF out = -arg THEN out:=maybe; maybe ELSE raise value error((REPR out," + ",REPR arg)); ~ FI;
OP + = (TRIT a, b)TRIT:
(TRIT out:=a; VOID(out+:=b); out);
OP - = (TRIT a, b)TRIT:
a + -b;
OP * = (TRIT a, b)TRIT:
IF a = maybe OR b = maybe THEN maybe ELIF a = b THEN true ELSE false FI;
OP ODD = (TRIT t)BOOL:
t /= maybe;
COMMENT
Kleene logic truth tables:
END COMMENT
OP AND = (TRIT a,b)TRIT: (
[,]TRIT( # ∧ maybe, true, false, # #maybe# (maybe, maybe, false), #true# (maybe, true, false), #false# (false, false, false) )[@0,@0][ABS trit OF a, ABS trit OF b]
);
OP OR = (TRIT a,b)TRIT: (
[,]TRIT( # ∨ maybe, true, false, # #maybe# (maybe, true, maybe), #true# (true, true, true), #false# (maybe, true, false) )[@0,@0][ABS trit OF a, ABS trit OF b]
);
PRIO IMPLIES = 1; # 1.9 # OP IMPLIES = (TRIT a,b)TRIT: (
[,]TRIT( # ⊃ maybe, true, false, # #maybe# (maybe, true, maybe), #true# (maybe, true, false), #false# (true, true, true) )[@0,@0][ABS trit OF a, ABS trit OF b]
);
PRIO EQV = 1; # 1.8 # OP EQV = (TRIT a,b)TRIT: (
[,]TRIT( # ≡ maybe, true, false, # #maybe# (maybe, maybe, maybe), #true# (maybe, true, false), #false# (maybe, false, true) )[@0,@0][ABS trit OF a, ABS trit OF b]
);
- Non ASCII OPerators
OP ¬ = (TRIT a)TRIT: NOT b,
∨ = (TRIT a,b)TRIT: a OR b, ∧ = (TRIT a,b)TRIT: a AND b, & = (TRIT a,b)TRIT: a AND b, ⊃ = (TRIT a,b)TRIT: a IMPLIES b, ≡ = (TRIT a,b)TRIT: a EQV b;
- </lang>File: test_Ternary_logic.a68
<lang algol68>#!/usr/local/bin/a68g --script #
- -*- coding: utf-8 -*- #
PR READ "prelude/general.a68" PR PR READ "Ternary_logic.a68" PR
[]TRIT trits = (false, maybe, true);
FORMAT col fmt = $" "g" "$; FORMAT row fmt = $l3(f(col fmt)"|")f(col fmt)$; FORMAT row sep fmt = $l3("---+")"---"l$;
PROC row sep = VOID:
printf(row sep fmt);
PROC title = (UTF op)VOID:(
print(("Operator: ",op));
printf((row fmt," ",REPR false, REPR maybe, REPR true))
);
PROC print bool op table = (STRING op name, PROC(TRIT,TRIT)BOOL op)VOID: (
title(op name);
FOR i FROM LWB trits TO UPB trits DO
row sep;
TRIT ti = trits[i];
printf((col fmt, REPR ti));
FOR j FROM LWB trits TO UPB trits DO
TRIT tj = trits[j];
printf(($"|"$, col fmt, op(ti,tj)))
OD
OD;
print(new line)
);
PROC print trit op table = (STRING op name, PROC(TRIT,TRIT)TRIT op)VOID: (
title(op name);
FOR i FROM LWB trits TO UPB trits DO
row sep;
TRIT ti = trits[i];
printf((col fmt, REPR ti));
FOR j FROM LWB trits TO UPB trits DO
TRIT tj = trits[j];
printf(($"|"$, col fmt, REPR op(ti,tj)))
OD
OD;
print(new line)
);
printf((
$"Comparitive table of coercions:"l$, $" TRIT BOOL INT"l$
));
FOR it FROM LWB trits TO UPB trits DO
TRIT t = trits[it]; IF t = maybe THEN printf(($" "g" "$, REPR t, " ", INITINT t, $l$)) ELSE printf(($" "g" "$, REPR t, B t, INITINT t, $l$)) FI
OD;
printf((
$l"Specific test of the IMPLIES operator:"l$,
$" "g" implies "g" is "b("not ","")"a contradiction!"l$,
B false, B false, B(false IMPLIES false),
B false, B true, B(false IMPLIES true),
B false, REPR maybe, B(false IMPLIES maybe),
B true, B false, B(true IMPLIES false),
B true, B true, B(true IMPLIES true),
REPR maybe, Btrue, B(maybe IMPLIES true),
$" "g" implies "g" is "g" a contradiction!"l$,
B true, REPR maybe, REPR (true IMPLIES maybe),
REPR maybe, B false, REPR (maybe IMPLIES false),
REPR maybe, REPR maybe, REPR (maybe IMPLIES maybe),
$l$
));
printf($l"Kleene logic truth table samples:"l$);
print trit op table("CMP", (TRIT a,b)TRIT: a CMP b); print trit op table("EQV", (TRIT a,b)TRIT: a EQV b); print trit op table("IMPLIES", (TRIT a,b)TRIT: a IMPLIES b); print trit op table("AND", (TRIT a,b)TRIT: a AND b); print trit op table("OR", (TRIT a,b)TRIT: a OR b) CO; print trit op table("+", (TRIT a,b)TRIT: a + b); print trit op table("-", (TRIT a,b)TRIT: a - b); print trit op table("*", (TRIT a,b)TRIT: a * b); print bool op table("EQ", (TRIT a,b)BOOL: a EQ b); print bool op table("<=", (TRIT a,b)BOOL: a <= b) END CO</lang> Output:
Comparitive table of coercions: TRIT BOOL INT ⌊ F -1 ? +0 ⌈ T +1 Specific test of the IMPLIES operator: F implies F is not a contradiction! F implies T is not a contradiction! F implies ? is not a contradiction! T implies F is a contradiction! T implies T is not a contradiction! ? implies T is not a contradiction! T implies ? is ? a contradiction! ? implies F is ? a contradiction! ? implies ? is ? a contradiction! Kleene logic truth table samples: Operator: CMP | ⌊ | ? | ⌈ ---+---+---+--- ⌊ | ? | ⌊ | ⌊ ---+---+---+--- ? | ⌈ | ? | ⌊ ---+---+---+--- ⌈ | ⌈ | ⌈ | ? Operator: EQV | ⌊ | ? | ⌈ ---+---+---+--- ⌊ | ⌈ | ? | ⌊ ---+---+---+--- ? | ? | ? | ? ---+---+---+--- ⌈ | ⌊ | ? | ⌈ Operator: IMPLIES | ⌊ | ? | ⌈ ---+---+---+--- ⌊ | ⌈ | ⌈ | ⌈ ---+---+---+--- ? | ? | ? | ⌈ ---+---+---+--- ⌈ | ⌊ | ? | ⌈ Operator: AND | ⌊ | ? | ⌈ ---+---+---+--- ⌊ | ⌊ | ⌊ | ⌊ ---+---+---+--- ? | ⌊ | ? | ? ---+---+---+--- ⌈ | ⌊ | ? | ⌈ Operator: OR | ⌊ | ? | ⌈ ---+---+---+--- ⌊ | ⌊ | ? | ⌈ ---+---+---+--- ? | ? | ? | ⌈ ---+---+---+--- ⌈ | ⌈ | ⌈ | ⌈
C
Implementing logic using lookup tables. <lang c>typedef char trit;
- define TRITTRUE 0
- define TRITMAYBE 1
- define TRITFALSE 2
char* tritString[3] = {"FALSE", "MAYBE", "TRUE"};
trit tritNot[3] = {TRITFALSE , TRITMAYBE, TRITTRUE}; trit tritAnd[3][3] = { {TRITTRUE, TRITMAYBE, TRITFALSE},
{TRITMAYBE, TRITMAYBE, TRITMAYBE},
{TRITFALSE, TRITFALSE, TRITFALSE} };
trit tritOr[3][3] = { {TRITTRUE, TRITTRUE, TRITTRUE},
{TRITTRUE, TRITMAYBE, TRITMAYBE},
{TRITTRUE, TRITMAYBE, TRITFALSE} };
trit tritThen[3][3] = { { TRITTRUE, TRITMAYBE, TRITFALSE},
{ TRITTRUE, TRITMAYBE, TRITMAYBE},
{ TRITTRUE, TRITTRUE, TRITTRUE } };
trit tritEquiv[3][3] = { { TRITTRUE, TRITMAYBE, TRITFALSE},
{ TRITMAYBE, TRITMAYBE, TRITMAYBE},
{ TRITFALSE, TRITMAYBE, TRITTRUE } };
int main() {
trit op1 = TRITTRUE; /* Declare. Initialize for CYA */ trit op2 = TRITTRUE; /* Declare. Initialize for CYA */
/* Demo 'not' */
for( op1 = TRITTRUE; op1 <= TRITFALSE; ++op1 )
{
printf("Not %s: %s\n", tritString[op1], tritString[tritNot[op1]]);
}
/* Blank line */
printf("\n");
/* Demo And */
for( op1 = TRITTRUE; op1 <= TRITFALSE; ++op1 )
{
for( op2 = TRITTRUE; op2 <= TRITFALSE; ++op2 )
{
printf("%s AND %s: %s\n", tritString[op1], tritString[op2], tritString[tritAnd[op1][op2]]);
}
}
return 0;
}</lang>
Output: <lang text>Not FALSE: TRUE Not MAYBE: MAYBE Not TRUE: FALSE
FALSE AND FALSE: FALSE FALSE AND MAYBE: MAYBE FALSE AND TRUE: TRUE MAYBE AND FALSE: MAYBE MAYBE AND MAYBE: MAYBE MAYBE AND TRUE: MAYBE TRUE AND FALSE: TRUE TRUE AND MAYBE: TRUE TRUE AND TRUE: TRUE</lang>
Java
<lang java5>public class Logic{ public static enum Trit{ TRUE, MAYBE, FALSE;
public Trit and(Trit other){ if(this == TRUE){ return other; }else if(this == MAYBE){ return MAYBE; }else{ return FALSE; } }
public Trit or(Trit other){ if(this == TRUE){ return TRUE; }else if(this == MAYBE){ return (other == TRUE) ? TRUE : MAYBE; }else{ return other; } }
public Trit tIf(Trit other){ if(this == TRUE){ return other; }else if(this == MAYBE){ return (other == TRUE) ? TRUE : MAYBE; }else{ return TRUE; } }
public Trit not(){ if(this == TRUE){ return FALSE; }else if(this == MAYBE){ return MAYBE; }else{ return TRUE; } }
public Trit equals(Trit other){ if(this == TRUE){ return other; }else if(this == MAYBE){ return MAYBE; }else{ return other.not(); } } } public static void main(String[] args){ for(Trit a:Trit.values()){ System.out.println("not " + a + ": " + a.not()); } for(Trit a:Trit.values()){ for(Trit b:Trit.values()){ System.out.println(a+" and "+b+": "+a.and(b)+ "\t "+a+" or "+b+": "+a.or(b)+ "\t "+a+" implies "+b+": "+a.tIf(b)+ "\t "+a+" = "+b+": "+a.equals(b)); } } } }</lang> Output:
not TRUE: FALSE not MAYBE: MAYBE not FALSE: TRUE TRUE and TRUE: TRUE TRUE or TRUE: TRUE TRUE implies TRUE: TRUE TRUE = TRUE: TRUE TRUE and MAYBE: MAYBE TRUE or MAYBE: TRUE TRUE implies MAYBE: MAYBE TRUE = MAYBE: MAYBE TRUE and FALSE: FALSE TRUE or FALSE: TRUE TRUE implies FALSE: FALSE TRUE = FALSE: FALSE MAYBE and TRUE: MAYBE MAYBE or TRUE: TRUE MAYBE implies TRUE: TRUE MAYBE = TRUE: MAYBE MAYBE and MAYBE: MAYBE MAYBE or MAYBE: MAYBE MAYBE implies MAYBE: MAYBE MAYBE = MAYBE: MAYBE MAYBE and FALSE: MAYBE MAYBE or FALSE: MAYBE MAYBE implies FALSE: MAYBE MAYBE = FALSE: MAYBE FALSE and TRUE: FALSE FALSE or TRUE: TRUE FALSE implies TRUE: TRUE FALSE = TRUE: FALSE FALSE and MAYBE: FALSE FALSE or MAYBE: MAYBE FALSE implies MAYBE: TRUE FALSE = MAYBE: MAYBE FALSE and FALSE: FALSE FALSE or FALSE: FALSE FALSE implies FALSE: TRUE FALSE = FALSE: TRUE