The purpose of this project was to explore many-valued logic using computational methods.
Introduction
Introduction
In standard Boolean logic, there are only two possible states: True and False, or 1 and 0. However, many-valued logic allows for there to be varying degrees of truth. There are many ways for systems of many-valued logic to be defined, but for this project, I used a generalized system for k-valued logic based on Łukasiewicz's finite-valued logic.
The Implementation
The Implementation
To start, we let the set of possible truth states for a system of k-valued logic equal a range of values between 0 and 1 that are increasing by 1/(k-1).
Define the set of possible truth states for a system of k values:
In[]:=
MValues[k_]:=Range[0,1,1/(k-1)]
List the possible truth states for 5-valued logic:
In[]:=
MValues[5]
Out[]=
0,,,,1
1
4
1
2
3
4
We also need to redefine the standard logical operations (AND, OR, NOT, etc) so that they work with many valued logic.
In[]:=
MNot[a_]:=1-aMAnd[a_,b_]:=Min[a,b]MOr[a_,b_]:=Max[a,b]MNand[a_,b_]:=MNot[MAnd[a,b]]MNor[a_,b_]:=MNot[MOr[a,b]]MXor[a_,b_]:=Abs[a-b]MEqual[a_,b_]:=1-Abs[a-b]MImplies[a_,b_]:=1-UnitStep[a-b](a-b)MAltImplies[a_,b_]:=Min[1,1-a+b]
Visualizing the Operators
Visualizing the Operators
To better visualize the new operators, I wrote a function that generates truth tables when given a logical expression, a list of variables, and k, the number of states in the logic system.
In[]:=
MColorVisualTable[expr_,k_,vars__]:=Module{list,header},list=Table[Append[input,ReplaceAll[expr,Thread[varsinput]]],{input,Tuples[MValues[k],{Length[vars]}]}];header={Flatten[Append[vars,"out"]]};list=Join[header,list];Gridlist,
Truth table for MAnd[p,q] in 3-valued logic:
In[]:=
MColorVisualTable[MAnd[p,q],3,{p,q}]
Out[]=
p | q | out |
0 | 0 | 0 |
0 | 1 2 | 0 |
0 | 1 | 0 |
1 2 | 0 | 0 |
1 2 | 1 2 | 1 2 |
1 2 | 1 | 1 2 |
1 | 0 | 0 |
1 | 1 2 | 1 2 |
1 | 1 | 1 |
To extract only the column of outputs from the truth table, I wrote MTable:
To extract only the column of outputs from the truth table, I wrote MTable:
In[]:=
MTable[expr_,k_,vars__]:=ReplaceAll[expr,Thread[vars#]]&/@Tuples[MValues[k],{Length[vars]}]
In[]:=
MTable[MAnd[p,q],3,{p,q}]
Out[]=
0,0,0,0,,,0,,1
1
2
1
2
1
2
Testing the Operators
Testing the Operators
Using FullSimplify, we can verify whether known identities in 2-valued logic generalize to many-valued logic. As an example, here are the equivalents of De Morgan's laws using many-valued logic connectives:
Verify that the logical expressions are always equivalent:
In[]:=
FullSimplify[MNot[MOr[A,B]]MAnd[MNot[A],MNot[B]],{0<=A<=1,0<=B<=1}]FullSimplify[MNot[MAnd[A,B]]MOr[MNot[A],MNot[B]],{0<=A<=1,0<=B<=1}]
Out[]=
True
Out[]=
True
Functional Completeness
Functional Completeness
The Problem
The Problem
A logical operator is considered to be functionally complete if it can be used to generate all possible truth tables by nesting itself in certain ways. To prove that an operator is functionally complete, it is enough to show that it can be used to generate all possible operators on two variables, as these can be combined to create truth tables with any greater number of variables.
For example, the operator NAND is complete on two variables because it can be combined to generate all 16 possible 2-variable connectives in 2-valued logic.
Confirm that all 2-variable truth tables in 2-valued logic are expressible as a nesting of applications of MNand:
In[]:=
AllTrue[{{0,0,0,0}== MTable[MNand[MNand[MNand[p,p],p],MNand[MNand[p,p],p]],2,{p,q}],{0,0,0,1}==MTable[MNand[MNand[p,q],MNand[p,q]],2,{p,q}],{0,0,1,0}==MTable[MNand[MNand[p,MNand[q,q]],MNand[p,MNand[q,q]]],2,{p,q}],{0,0,1,1}== MTable[p,2,{p,q}],{0,1,0,0}==MTable[MNand[MNand[MNand[p,p],q],MNand[MNand[p,p],q]],2,{p,q}],{0,1,0,1}== MTable[q,2,{p,q}],{0,1,1,0}==MTable[MNand[MNand[p,MNand[p,q]],MNand[q,MNand[p,q]]],2,{p,q}],{0,1,1,1}==MTable[MNand[MNand[p,p],MNand[q,q]],2,{p,q}],{1,0,0,0}==MTable[MNand[MNand[MNand[p,p],MNand[q,q]],MNand[MNand[p,p],MNand[q,q]]],2,{p,q}],{1,0,0,1}==MTable[MNand[MNand[p,q],MNand[MNand[p,p],MNand[q,q]]],2,{p,q}],{1,0,1,0}==MTable[MNand[q,q],2,{p,q}],{1,0,1,1}==MTable[MNand[MNand[p,p],q],2,{p,q}],{1,1,0,0}==MTable[MNand[p,p],2,{p,q}],{1,1,0,1}==MTable[MNand[p,MNand[q,q]],2,{p,q}],{1,1,1,0}==MTable[MNand[p,q],2,{p,q}],{1,1,1,1}==MTable[MNand[MNand[p,p],p],2,{p,q}]},#&]
Out[]=
True
The number of possible 2-variable operators in k-valued logic is k^(k^2). As this number is small in 2-valued logic, functional completeness is normally proven by hand. However, for greater values of k this number becomes very large, so it makes sense to take a computational approach.
Note
Note
In 2-valued logic, the only functionally complete operators are NAND and NOR. However, our equivalents of these operators can't be functionally complete in any other k-valued logic, and neither can any combination of our versions of the standard logical operators. This is because our operators were specifically designed to behave exactly like 2-valued logic when given only 0's and 1's. Thus, there is no way they can be nested to return an intermediate truth value, such as 1/2, when the inputs are only 0 or 1.
We will need new operators to investigate for completeness. For this purpose I included the single-variable operator "MNext," which cyclically shifts the value of the input over by 1/(k-1).
In[]:=
MNext[a_,k_]:=Mod[(k-1)*a+1,k]/(k-1)
Truth table for MNext in 5-valued logic:
In[]:=
MColorVisualTable[MNext[p,5],5,{p}]
Out[]=
p | out |
0 | 1 4 |
1 4 | 1 2 |
1 2 | 3 4 |
3 4 | 1 |
1 | 0 |
The Algorithm
The Algorithm
To prove that an operator in k-valued logic is functionally complete, it is enough to show that it can be used to reach k^(k^2) different 2-variable truth tables. However, proving that an operator is not functionally complete is more complicated.
To begin, let the operator we're testing for completeness = u[x_,y_].
We gradually construct a list of operators that can be generated by u, using only x and y as inputs. We initialize this list as:
ReachedOperators={X,Y};
where X and Y are 2-variable functions that return the value of the x-input and the y-input, respectively.
We then generate new operators by combining pairs of connectives within ReachedOperators by applying u to them. We add these new operators to the list.
ReachedOperators={X,Y,u[X,Y],u[X,X],u[Y,Y],u[X,X]};
Some of these functions may be identical. We remove the duplicates by deleting operators with the same truth tables.
We repeat this process until we reach a point where testing all possible nestings of pairs of operators in the list does not yield any new operators.
If Length[ReachedOperators] = k^(k^2), u is functionally complete. Additionally, if Length[ReachedOperators] < k^(k^2), u can't be functionally complete. We can prove this by contradiction.
Suppose u is functionally complete, but Length[ReachedOperators] < k^(k^2). Then there must be some set of other operators which are reachable by u but can't be created by nesting two connectives in ReachedOperators within u. Let
Out of all the operators within OtherOperators, select one with the least number of nested u's. Call it f. Since f is reachable from u, there must be 2 operators g and h such that f = u[g,h]. From the choice of f, operators g and h must be in ReachedOperators, so we have reached a contradiction.
Older Implementations
Older Implementations
On my first attempt, I more or less directly translated the algorithm into a function that would return all the reachable truth tables from an operator. To convert easily between operators and their truth tables, I used MTable (shown above) and created TableToFunction:
The result worked, but was very inefficient.
To speed up the program, I made some alterations. Most importantly, I rewrote the code so that no pairs of operators would be nested together more than once.
To speed up the program, I made some alterations. Most importantly, I rewrote the code so that no pairs of operators would be nested together more than once.
Final Implementation
Final Implementation
In a final attempt to make the program more efficient, I rewrote the code to work only with truth tables, rather than creating functions representing the operators.
This necessitated writing Combine, a function to nest the truth tables of operators:
The final product:
The final product:
Testing
Testing
To show that ReachableOperators works, we can first run it on 2-valued logic.
While impractical for any higher-valued logic, we can use AllCompleteFunctions to return all the functionally complete operators in 2-valued logic.
Sure enough, these happen to be the two tables corresponding to NOR and NAND in 2-valued logic.
Results
Results
As the number of possible truth tables surpasses 4 billion once we get to 4-valued logic systems, the efficiency of the algorithm continues to be an issue. However, we can still generate lists of reachable tables for operators in 3-valued logic systems, as well as for operators for which the number of reachable tables are low.
Find all 82 tables reachable by MNor in 3-valued logic:
Find all truth tables reachable by MOr in 5-valued logic:
Similarly, when an operator is not functionally complete, we can usually prove it in a reasonable amount of time, so long as the k-value is low:
Similarly, when an operator is not functionally complete, we can usually prove it in a reasonable amount of time, so long as the k-value is low:
Confirm that MNand is not functionally complete in 3-valued logic:
Show that MNor is not functionally complete in 5 - valued logic :
However, proving that an operator is complete is much more time-consuming. Given an hour, ReachableOperators can show that MNext[MAnd] and MNext[MOr] can be used to generate nearly all of the operators in 3-valued logic, but it takes considerably longer to find the remainder.
Function Analysis
Function Analysis
Over the course of this project, I took several techniques for Boolean analysis and adapted them for use on functions in many-valued logic.
Tautologies and Contradictions
Tautologies and Contradictions
A tautology is a statement that will always return true regardless of the truth values of its inputs. Conversely, a contradiction is always false regardless of the values of its inputs.
Show that a == !!a in 6-valued logic is a tautology:
Show that MXor[a,a] in 4-valued logic is a contradiction:
Balancedness
Balancedness
A Boolean function is considered to be balanced if the set of all possible outputs contains as many 1's as 0's. Thus, we can consider a many-valued logic function to be balanced if its outputs contain an equal amount of each possible truth value.
Show that MNot[a] is balanced in 7-valued logic:
Symmetricity
Symmetricity
A Boolean function is symmetric if changing the order of its inputs will never change the output.
Show that MAnd[p,q] is symmetric in 5-valued logic:
Influence
Influence
In Boolean logic, the influence of a variable in a Boolean expression is the probability over all possible input values that changing the value of the variable will change the output of the expression.
In order to allow for logic systems with very large numbers of truth values, I decided to approximate this probability by generating random values for the variables, rather than finding every possible set of values for the inputs and every possible new variable value.
Create one randomized set of input values and test what happens when the designated variable is changed by a random amount.
Take the average of many randomized tests.
Find the unweighted influence of the variable p in MOr[p,q] for 3-valued logic:
However, I wasn't sure this measure was ideal. For some cases, I wanted to be able to distinguish between changing the variable's truth value by a small amount and getting a very different output, and changing the variable by a large amount and only getting a slightly different output.
Therefore, rather than returning "1" if the output changes and "0" if the output stays the same, WeightedInfluenceRandomizer divides the amount by which the output changes by the amount the variable was changed.
However, I wasn't sure this measure was ideal. For some cases, I wanted to be able to distinguish between changing the variable's truth value by a small amount and getting a very different output, and changing the variable by a large amount and only getting a slightly different output.
Therefore, rather than returning "1" if the output changes and "0" if the output stays the same, WeightedInfluenceRandomizer divides the amount by which the output changes by the amount the variable was changed.
Plot an approximation of the respective weighted influences of both variables in MAnd[x,y] for 2, 3, and 4-valued logic:
Experimentation
Experimentation
It can be interesting to compare the characteristics of differently-valued logics, as well as to analyze operators that aren't combinations of standard connectives. For this purpose, I wrote two functions to help introduce randomness.
Define a function to generate a random 2-variable truth table:
Define a function to create a random logical function on two variables:
Check if a random 2-variable function in 3-valued logic is symmetric:
Conclusion
Conclusion
In the future, I would like to adapt my algorithm for testing for functional completeness to work with sets of multiple operators. I would also like to test more operators in general. For values of k higher than 3, it may be interesting to see which operators can surpass a certain threshold of a number of 2-variable connectives reachable by nesting the operator. Other potential avenues of exploration might include investigating how the influence of variables changes for differently-valued logic systems or writing a function to minimize expressions in many-valued logic.
Although not explored in this project, many-valued logic has applications in a variety of fields, including philosophy, linguistics, and artificial intelligence (see: https://plato.stanford.edu/entries/logic-manyvalued/#AppManValLog ).
The standard operators used in this project were taken straight out of Stephen Wolfram's A New Kind of Science: https://www.wolframscience.com/nks/notes-12-9--multivalued-logic/.