WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
WolframOne
Mathematica
WolframAlpha Notebook Edition
Programming Lab
Finance Platform
SystemModeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Application Server
Enterprise Mathematica
WolframAlpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
WolframAlpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
WolframAlpha
WolframAlpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
WolframAlpha for Mobile
WolframAlphaPowered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledgebased programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technologyenabling science of the computational universe.
Wolfram Notebooks
The preeminent environment for any technical workflows.
Wolfram Engine
Software engine implementing the Wolfram Language.
Wolfram Natural Language Understanding System
Knowledgebased broadly deployed natural language.
Wolfram Data Framework
Semantic framework for realworld data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering WolframAlpha.
All Technologies »
Solutions
Engineering, R&D
Aerospace & Defense
Chemical Engineering
Control Systems
Electrical Engineering
Image Processing
Industrial Engineering
Mechanical Engineering
Operations Research
More...
Finance, Statistics & Business Analysis
Actuarial Sciences
Bioinformatics
Data Science
Econometrics
Financial Risk Management
Statistics
More...
Education
All Solutions for Education
Trends
Machine Learning
Multiparadigm Data Science
Internet of Things
HighPerformance Computing
Hackathons
Software & Web
Software Development
Authoring & Publishing
Interface Development
Web Development
Sciences
Astronomy
Biology
Chemistry
More...
All Solutions »
Learning & Support
Learning
Wolfram Language Documentation
Fast Introduction for Programmers
Wolfram U
Videos & Screencasts
Wolfram Language Introductory Book
Webinars & Training
Summer Programs
Books
Need Help?
Support FAQ
Wolfram Community
Contact Support
Premium Support
Paid Project Support
Technical Consulting
All Learning & Support »
Company
About
Company Background
Wolfram Blog
Events
Contact Us
Work with Us
Careers at Wolfram
Internships
Other Wolfram Language Jobs
Initiatives
Wolfram Foundation
MathWorld
ComputerBased Math
A New Kind of Science
Wolfram Technology for Hackathons
Student Ambassador Program
Wolfram for Startups
Demonstrations Project
Wolfram Innovator Awards
Wolfram + Raspberry Pi
Summer Programs
More...
All Company »
Search
WOLFRAM COMMUNITY
Connect with users of Wolfram technologies to learn, solve problems and share ideas
Join
Sign In
Dashboard
Groups
People
Message Boards
Answer
(
Unmark
)
Mark as an Answer
GROUPS:
Mathematics
Discrete Mathematics
Logic and Boolean Algebra
Wolfram Language
Wolfram High School Summer Camp
2
Nika Chuzhoy
[WSC21] Implementing ManyValued Logic in the Wolfram Language
Nika Chuzhoy
Posted
17 days ago
120 Views

0 Replies

2 Total Likes
Follow this post

The purpose of this project was to explore manyvalued logic using computational methods.
Introduction
In standard Boolean logic, there are only two possible states: True and False, or 1 and 0. However, manyvalued logic allows for there to be varying degrees of truth. There are many ways for systems of manyvalued logic to be defined, but for this project, I used a generalized system for
k
valued logic based on Łukasiewicz's finitevalued logic.
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:
I
n
[
]
:
=
M
V
a
l
u
e
s
[
k
_
]
:
=
R
a
n
g
e
[
0
,
1
,
1
/
(
k

1
)
]
List the possible truth states for 5valued logic:
I
n
[
]
:
=
M
V
a
l
u
e
s
[
5
]
O
u
t
[
]
=
0
,
1
4
,
1
2
,
3
4
,
1
We also need to redefine the standard logical operations (AND, OR, NOT, etc) so that they work with many valued logic.
I
n
[
]
:
=
M
N
o
t
[
a
_
]
:
=
1

a
M
A
n
d
[
a
_
,
b
_
]
:
=
M
i
n
[
a
,
b
]
M
O
r
[
a
_
,
b
_
]
:
=
M
a
x
[
a
,
b
]
M
N
a
n
d
[
a
_
,
b
_
]
:
=
M
N
o
t
[
M
A
n
d
[
a
,
b
]
]
M
N
o
r
[
a
_
,
b
_
]
:
=
M
N
o
t
[
M
O
r
[
a
,
b
]
]
M
X
o
r
[
a
_
,
b
_
]
:
=
A
b
s
[
a

b
]
M
E
q
u
a
l
[
a
_
,
b
_
]
:
=
1

A
b
s
[
a

b
]
M
I
m
p
l
i
e
s
[
a
_
,
b
_
]
:
=
1

U
n
i
t
S
t
e
p
[
a

b
]
(
a

b
)
M
A
l
t
I
m
p
l
i
e
s
[
a
_
,
b
_
]
:
=
M
i
n
[
1
,
1

a
+
b
]
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.
I
n
[
]
:
=
M
C
o
l
o
r
V
i
s
u
a
l
T
a
b
l
e
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
M
o
d
u
l
e
{
l
i
s
t
,
h
e
a
d
e
r
}
,
l
i
s
t
=
T
a
b
l
e
[
A
p
p
e
n
d
[
i
n
p
u
t
,
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
i
n
p
u
t
]
]
]
,
{
i
n
p
u
t
,
T
u
p
l
e
s
[
M
V
a
l
u
e
s
[
k
]
,
{
L
e
n
g
t
h
[
v
a
r
s
]
}
]
}
]
;
h
e
a
d
e
r
=
{
F
l
a
t
t
e
n
[
A
p
p
e
n
d
[
v
a
r
s
,
"
o
u
t
"
]
]
}
;
l
i
s
t
=
J
o
i
n
[
h
e
a
d
e
r
,
l
i
s
t
]
;
G
r
i
d
l
i
s
t
,
S
e
q
u
e
n
c
e
I
c
o
n
T
r
u
t
h
t
a
b
l
e
f
o
r
M
A
n
d
[
p
,
q
]
i
n
3

v
a
l
u
e
d
l
o
g
i
c
:
I
n
[
]
:
=
M
C
o
l
o
r
V
i
s
u
a
l
T
a
b
l
e
[
M
A
n
d
[
p
,
q
]
,
3
,
{
p
,
q
}
]
O
u
t
[
]
=
p
q
o
u
t
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:
I
n
[
]
:
=
M
T
a
b
l
e
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
#
]
]
&
/
@
T
u
p
l
e
s
[
M
V
a
l
u
e
s
[
k
]
,
{
L
e
n
g
t
h
[
v
a
r
s
]
}
]
I
n
[
]
:
=
M
T
a
b
l
e
[
M
A
n
d
[
p
,
q
]
,
3
,
{
p
,
q
}
]
O
u
t
[
]
=
0
,
0
,
0
,
0
,
1
2
,
1
2
,
0
,
1
2
,
1
Testing the Operators
Using FullSimplify, we can verify whether known identities in 2valued logic generalize to manyvalued logic. As an example, here are the equivalents of De Morgan's laws using manyvalued logic connectives:
Verify that the logical expressions are always equivalent:
I
n
[
]
:
=
F
u
l
l
S
i
m
p
l
i
f
y
[
M
N
o
t
[
M
O
r
[
A
,
B
]
]
M
A
n
d
[
M
N
o
t
[
A
]
,
M
N
o
t
[
B
]
]
,
{
0
<
=
A
<
=
1
,
0
<
=
B
<
=
1
}
]
F
u
l
l
S
i
m
p
l
i
f
y
[
M
N
o
t
[
M
A
n
d
[
A
,
B
]
]
M
O
r
[
M
N
o
t
[
A
]
,
M
N
o
t
[
B
]
]
,
{
0
<
=
A
<
=
1
,
0
<
=
B
<
=
1
}
]
O
u
t
[
]
=
T
r
u
e
O
u
t
[
]
=
T
r
u
e
Functional Completeness
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 2variable connectives in 2valued logic.
Confirm that all 2variable truth tables in 2valued logic are expressible as a nesting of applications of MNand:
I
n
[
]
:
=
A
l
l
T
r
u
e
[
{
{
0
,
0
,
0
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
p
]
,
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
p
]
]
,
2
,
{
p
,
q
}
]
,
{
0
,
0
,
0
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
q
]
,
M
N
a
n
d
[
p
,
q
]
]
,
2
,
{
p
,
q
}
]
,
{
0
,
0
,
1
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
M
N
a
n
d
[
q
,
q
]
]
,
M
N
a
n
d
[
p
,
M
N
a
n
d
[
q
,
q
]
]
]
,
2
,
{
p
,
q
}
]
,
{
0
,
0
,
1
,
1
}
=
=
M
T
a
b
l
e
[
p
,
2
,
{
p
,
q
}
]
,
{
0
,
1
,
0
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
q
]
,
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
q
]
]
,
2
,
{
p
,
q
}
]
,
{
0
,
1
,
0
,
1
}
=
=
M
T
a
b
l
e
[
q
,
2
,
{
p
,
q
}
]
,
{
0
,
1
,
1
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
M
N
a
n
d
[
p
,
q
]
]
,
M
N
a
n
d
[
q
,
M
N
a
n
d
[
p
,
q
]
]
]
,
2
,
{
p
,
q
}
]
,
{
0
,
1
,
1
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
M
N
a
n
d
[
q
,
q
]
]
,
2
,
{
p
,
q
}
]
,
{
1
,
0
,
0
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
M
N
a
n
d
[
q
,
q
]
]
,
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
M
N
a
n
d
[
q
,
q
]
]
]
,
2
,
{
p
,
q
}
]
,
{
1
,
0
,
0
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
q
]
,
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
M
N
a
n
d
[
q
,
q
]
]
]
,
2
,
{
p
,
q
}
]
,
{
1
,
0
,
1
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
q
,
q
]
,
2
,
{
p
,
q
}
]
,
{
1
,
0
,
1
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
q
]
,
2
,
{
p
,
q
}
]
,
{
1
,
1
,
0
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
p
,
p
]
,
2
,
{
p
,
q
}
]
,
{
1
,
1
,
0
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
p
,
M
N
a
n
d
[
q
,
q
]
]
,
2
,
{
p
,
q
}
]
,
{
1
,
1
,
1
,
0
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
p
,
q
]
,
2
,
{
p
,
q
}
]
,
{
1
,
1
,
1
,
1
}
=
=
M
T
a
b
l
e
[
M
N
a
n
d
[
M
N
a
n
d
[
p
,
p
]
,
p
]
,
2
,
{
p
,
q
}
]
}
,
#
&
]
O
u
t
[
]
=
T
r
u
e
The number of possible 2variable operators in kvalued logic is
k
^(
k
^2). As this number is small in 2valued 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
In 2valued 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 2valued 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 singlevariable operator "MNext," which cyclically shifts the value of the input over by 1/(
k
1).
I
n
[
]
:
=
M
N
e
x
t
[
a
_
,
k
_
]
:
=
M
o
d
[
(
k

1
)
*
a
+
1
,
k
]
/
(
k

1
)
T
r
u
t
h
t
a
b
l
e
f
o
r
M
N
e
x
t
i
n
5

v
a
l
u
e
d
l
o
g
i
c
:
I
n
[
]
:
=
M
C
o
l
o
r
V
i
s
u
a
l
T
a
b
l
e
[
M
N
e
x
t
[
p
,
5
]
,
5
,
{
p
}
]
O
u
t
[
]
=
p
o
u
t
0
1
4
1
4
1
2
1
2
3
4
3
4
1
1
0
The Algorithm
To prove that an operator in kvalued logic is functionally complete, it is enough to show that it can be used to reach k^(k^2) different 2variable 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:
R
e
a
c
h
e
d
O
p
e
r
a
t
o
r
s
=
{
X
,
Y
}
;
where X and Y are 2variable functions that return the value of the xinput and the yinput, 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.
R
e
a
c
h
e
d
O
p
e
r
a
t
o
r
s
=
{
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
O
t
h
e
r
O
p
e
r
a
t
o
r
s
=
{
o
1
,
o
2
,
o
3
,
.
.
.
}
;
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
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:
I
n
[
]
:
=
f
[
x
_
/
;
N
u
m
e
r
i
c
Q
[
x
]
,
y
_
/
;
N
u
m
e
r
i
c
Q
[
y
]
]
:
=
#
1
F
l
a
t
t
e
n
P
o
s
i
t
i
o
n
T
u
p
l
e
s
R
a
n
g
e
0
,
1
,
1
L
e
n
g
t
h
[
#
1
]

1
,
2
,
{
x
,
y
}
1
&
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
[
t
a
b
l
e
_
]
:
=
f
[
#
1
,
#
2
]
@
t
a
b
l
e
&
The result worked, but was very inefficient.
I
n
[
]
:
=
X
[
x
_
,
y
_
]
:
=
x
Y
[
x
_
,
y
_
]
:
=
y
I
n
[
]
:
=
O
r
i
g
i
n
a
l
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
t
a
b
l
e
_
,
k
_
]
:
=
M
o
d
u
l
e
[
{
u
=
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
[
t
a
b
l
e
]
}
,
F
i
x
e
d
P
o
i
n
t
[
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
A
p
p
e
n
d
[
{
#
}
,
T
a
b
l
e
[
M
T
a
b
l
e
[
u
[
f
1
[
x
,
y
]
,
f
2
[
x
,
y
]
]
,
k
,
{
x
,
y
}
]
,
{
f
1
,
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
/
@
#
}
,
{
f
2
,
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
/
@
#
}
]
]
]
,
k
^
2
]
]
&
,
{
M
T
a
b
l
e
[
X
[
p
,
q
]
,
k
,
{
p
,
q
}
]
,
M
T
a
b
l
e
[
Y
[
p
,
q
]
,
k
,
{
p
,
q
}
]
}
]
]
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.
I
n
[
]
:
=
F
a
s
t
e
r
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
t
a
b
l
e
_
,
k
_
]
:
=
(
M
o
d
u
l
e
[
{
u
=
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
[
t
a
b
l
e
]
,
O
l
d
T
a
b
l
e
s
=
{
}
,
N
e
w
T
a
b
l
e
s
=
{
M
T
a
b
l
e
[
X
[
p
,
q
]
,
k
,
{
p
,
q
}
]
,
M
T
a
b
l
e
[
Y
[
p
,
q
]
,
k
,
{
p
,
q
}
]
}
}
,
W
h
i
l
e
[
L
e
n
g
t
h
[
N
e
w
T
a
b
l
e
s
]
>
0
,
O
l
d
T
a
b
l
e
s
=
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
A
p
p
e
n
d
[
O
l
d
T
a
b
l
e
s
,
N
e
w
T
a
b
l
e
s
]
]
,
k
^
2
]
;
N
e
w
T
a
b
l
e
s
=
C
o
m
p
l
e
m
e
n
t
[
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
M
T
a
b
l
e
[
u
[
f
1
[
x
,
y
]
,
f
2
[
x
,
y
]
]
,
k
,
{
x
,
y
}
]
,
M
T
a
b
l
e
[
u
[
f
2
[
x
,
y
]
,
f
1
[
x
,
y
]
]
,
k
,
{
x
,
y
}
]
}
,
{
f
1
,
M
a
p
[
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
,
O
l
d
T
a
b
l
e
s
]
}
,
{
f
2
,
M
a
p
[
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
,
N
e
w
T
a
b
l
e
s
]
}
]
]
,
k
^
2
]
]
,
O
l
d
T
a
b
l
e
s
]
]
;
O
l
d
T
a
b
l
e
s
]
)
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:
I
n
[
]
:
=
C
o
m
b
i
n
e
[
u
_
L
i
s
t
,
f
1
_
L
i
s
t
,
f
2
_
L
i
s
t
,
k
_
]
:
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
u
[
[
F
l
a
t
t
e
n
[
P
o
s
i
t
i
o
n
[
T
u
p
l
e
s
[
R
a
n
g
e
[
0
,
1
,
1
/
(
k

1
)
]
,
2
]
,
{
f
1
[
[
i
]
]
,
f
2
[
[
i
]
]
}
]
]
]
]
,
{
i
,
L
e
n
g
t
h
[
u
]
}
]
]
The final product:
I
n
[
]
:
=
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
t
a
b
l
e
_
,
k
_
]
:
=
(
M
o
d
u
l
e
[
{
O
l
d
T
a
b
l
e
s
=
{
}
,
N
e
w
T
a
b
l
e
s
=
{
M
T
a
b
l
e
[
X
[
p
,
q
]
,
k
,
{
p
,
q
}
]
,
M
T
a
b
l
e
[
Y
[
p
,
q
]
,
k
,
{
p
,
q
}
]
}
}
,
W
h
i
l
e
[
(
L
e
n
g
t
h
[
O
l
d
T
a
b
l
e
s
]
<
k
^
(
k
^
2
)
)
&
&
(
L
e
n
g
t
h
[
N
e
w
T
a
b
l
e
s
]
>
0
)
,
N
e
w
T
a
b
l
e
s
=
C
o
m
p
l
e
m
e
n
t
[
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
{
T
a
b
l
e
[
{
C
o
m
b
i
n
e
[
t
a
b
l
e
,
t
1
,
t
2
,
k
]
,
C
o
m
b
i
n
e
[
t
a
b
l
e
,
t
2
,
t
1
,
k
]
}
,
{
t
1
,
O
l
d
T
a
b
l
e
s
}
,
{
t
2
,
N
e
w
T
a
b
l
e
s
}
]
,
T
a
b
l
e
[
C
o
m
b
i
n
e
[
t
a
b
l
e
,
t
1
,
t
2
,
k
]
,
{
t
1
,
N
e
w
T
a
b
l
e
s
}
,
{
t
2
,
N
e
w
T
a
b
l
e
s
}
]
}
]
,
k
^
2
]
]
,
O
l
d
T
a
b
l
e
s
]
;
O
l
d
T
a
b
l
e
s
=
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
A
p
p
e
n
d
[
O
l
d
T
a
b
l
e
s
,
N
e
w
T
a
b
l
e
s
]
]
,
k
^
2
]
]
;
O
l
d
T
a
b
l
e
s
]
)
Testing
To show that ReachableOperators works, we can first run it on 2valued logic.
I
n
[
]
:
=
A
l
l
O
p
e
r
a
t
o
r
O
u
t
s
[
k
_
]
:
=
T
u
p
l
e
s
[
R
a
n
g
e
[
0
,
1
,
1
/
(
k

1
)
]
,
k
^
2
]
I
s
C
o
m
p
l
e
t
e
[
t
a
b
l
e
_
,
k
_
]
:
=
I
f
[
L
e
n
g
t
h
[
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
t
a
b
l
e
,
k
]
]
k
^
(
k
^
2
)
,
T
r
u
e
,
F
a
l
s
e
]
A
l
l
C
o
m
p
l
e
t
e
O
p
e
r
a
t
o
r
s
[
k
_
]
:
=
S
e
l
e
c
t
[
A
l
l
O
p
e
r
a
t
o
r
O
u
t
s
[
k
]
,
I
s
C
o
m
p
l
e
t
e
[
#
,
k
]
&
]
While impractical for any highervalued logic, we can use AllCompleteFunctions to return all the functionally complete operators in 2valued logic.
I
n
[
]
:
=
A
l
l
C
o
m
p
l
e
t
e
O
p
e
r
a
t
o
r
s
[
2
]
O
u
t
[
]
=
{
{
1
,
0
,
0
,
0
}
,
{
1
,
1
,
1
,
0
}
}
Sure enough, these happen to be the two tables corresponding to NOR and NAND in 2valued logic.
I
n
[
]
:
=
M
T
a
b
l
e
[
M
N
a
n
d
[
p
,
q
]
,
2
,
{
p
,
q
}
]
M
T
a
b
l
e
[
M
N
o
r
[
p
,
q
]
,
2
,
{
p
,
q
}
]
O
u
t
[
]
=
{
1
,
1
,
1
,
0
}
O
u
t
[
]
=
{
1
,
0
,
0
,
0
}
Results
As the number of possible truth tables surpasses 4 billion once we get to 4valued logic systems, the efficiency of the algorithm continues to be an issue. However, we can still generate lists of reachable tables for operators in 3valued logic systems, as well as for operators for which the number of reachable tables are low.
Find all 82 tables reachable by MNor in 3valued logic:
I
n
[
]
:
=
S
h
o
r
t
[
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
M
T
a
b
l
e
[
M
N
o
r
[
p
,
q
]
,
3
,
{
p
,
q
}
]
,
3
]
]
O
u
t
[
]
/
/
S
h
o
r
t
=
1
,
1
2
,
0
,
1
2
,
1
2
,
0
,
0
,
0
,
0
,
1
,
1
2
,
0
,
1
,
1
2
,
0
,
1
,
1
2
,
0
,
7
8
,
1
,
1
,
1
,
1
,
1
2
,
1
,
1
,
1
2
,
1
,
1
,
1
,
1
,
1
,
1
2
,
1
,
1
,
1
,
1
Find all truth tables reachable by MOr in 5valued logic:
I
n
[
]
:
=
R
e
a
c
h
a
b
l
e
O
p
e
r
a
t
o
r
s
[
M
T
a
b
l
e
[
M
O
r
[
p
,
q
]
,
5
,
{
p
,
q
}
]
,
5
]
O
u
t
[
]
=
0
,
0
,
0
,
0
,
0
,
1
4
,
1
4
,
1
4
,
1
4
,
1
4
,
1
2
,
1
2
,
1
2
,
1
2
,
1
2
,
3
4
,
3
4
,
3
4
,
3
4
,
3
4
,
1
,
1
,
1
,
1
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
0
,
1
4
,
1
2
,
3
4
,
1
,
1
4
,
1
4
,
1
2
,
3
4
,
1
,
1
2
,
1
2
,
1
2
,
3
4
,
1
,
3
4
,
3
4
,
3
4
,
3
4
,
1
,
1
,
1
,
1
,
1
,
1
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 3valued logic:
I
n
[
]
:
=
I
s
C
o
m
p
l
e
t
e
[
M
T
a
b
l
e
[
M
N
a
n
d
[
p
,
q
]
,
3
,
{
p
,
q
}
]
,
3
]
O
u
t
[
]
=
F
a
l
s
e
Show that MNor is not functionally complete in 5  valued logic :
I
n
[
]
:
=
I
s
C
o
m
p
l
e
t
e
[
M
T
a
b
l
e
[
M
N
o
r
[
p
,
q
]
,
5
,
{
p
,
q
}
]
,
5
]
O
u
t
[
]
=
F
a
l
s
e
However, proving that an operator
is
complete is much more timeconsuming. Given an hour, ReachableOperators can show that MNext[MAnd] and MNext[MOr] can be used to generate nearly all of the operators in 3valued logic, but it takes considerably longer to find the remainder.
Function Analysis
Over the course of this project, I took several techniques for Boolean analysis and adapted them for use on functions in manyvalued logic.
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.
I
n
[
]
:
=
I
s
T
a
u
t
o
l
o
g
y
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
A
l
l
T
r
u
e
[
M
T
a
b
l
e
[
e
x
p
r
,
k
,
v
a
r
s
]
,
#
1
&
]
I
n
[
]
:
=
I
s
C
o
n
t
r
a
d
i
c
t
i
o
n
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
A
l
l
T
r
u
e
[
M
T
a
b
l
e
[
e
x
p
r
,
k
,
v
a
r
s
]
,
#
0
&
]
Show that a == !!a in 6valued logic is a tautology:
I
n
[
]
:
=
I
s
T
a
u
t
o
l
o
g
y
[
M
E
q
u
a
l
[
a
,
M
N
o
t
[
M
N
o
t
[
a
]
]
]
,
6
,
{
a
}
]
O
u
t
[
]
=
T
r
u
e
Show that MXor[a,a] in 4valued logic is a contradiction:
I
n
[
]
:
=
I
s
C
o
n
t
r
a
d
i
c
t
i
o
n
[
M
X
o
r
[
a
,
a
]
,
4
,
{
a
}
]
O
u
t
[
]
=
T
r
u
e
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 manyvalued logic function to be balanced if its outputs contain an equal amount of each possible truth value.
I
n
[
]
:
=
I
s
B
a
l
a
n
c
e
d
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
S
a
m
e
Q
@
@
(
C
o
u
n
t
[
M
T
a
b
l
e
[
e
x
p
r
,
k
,
v
a
r
s
]
,
#
]
&
/
@
M
V
a
l
u
e
s
[
k
]
)
Show that MNot[a] is balanced in 7valued logic:
I
n
[
]
:
=
I
s
B
a
l
a
n
c
e
d
[
M
N
o
t
[
a
]
,
7
,
{
a
}
]
O
u
t
[
]
=
T
r
u
e
Symmetricity
A Boolean function is symmetric if changing the order of its inputs will never change the output.
I
n
[
]
:
=
I
s
S
y
m
m
e
t
r
i
c
[
e
x
p
r
_
,
k
_
,
v
a
r
s
_
_
]
:
=
S
a
m
e
Q
@
@
T
a
b
l
e
[
M
T
a
b
l
e
[
e
x
p
r
,
k
,
v
]
,
{
v
,
P
e
r
m
u
t
a
t
i
o
n
s
[
v
a
r
s
]
}
]
Show that MAnd[p,q] is symmetric in 5valued logic:
I
n
[
]
:
=
I
s
S
y
m
m
e
t
r
i
c
[
M
A
n
d
[
p
,
q
]
,
5
,
{
p
,
q
}
]
O
u
t
[
]
=
T
r
u
e
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.
I
n
[
]
:
=
U
n
w
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
R
a
n
d
o
m
i
z
e
r
[
e
x
p
r
_
,
k
_
,
v
a
r
_
,
v
a
r
s
_
]
:
=
M
o
d
u
l
e
[
{
v
a
l
1
,
v
a
l
2
,
v
a
r
I
n
d
e
x
,
v
a
r
s
1
,
v
a
r
s
2
,
o
u
t
1
,
o
u
t
2
}
,
{
v
a
l
1
,
v
a
l
2
}
=
R
a
n
d
o
m
S
a
m
p
l
e
[
M
V
a
l
u
e
s
[
k
]
,
2
]
;
v
a
r
I
n
d
e
x
=
F
l
a
t
t
e
n
[
P
o
s
i
t
i
o
n
[
v
a
r
s
,
v
a
r
]
]
[
[
1
]
]
;
v
a
r
s
1
=
R
a
n
d
o
m
C
h
o
i
c
e
[
S
e
l
e
c
t
[
T
u
p
l
e
s
[
M
V
a
l
u
e
s
[
k
]
,
L
e
n
g
t
h
[
v
a
r
s
]
]
,
#
[
[
v
a
r
I
n
d
e
x
]
]
v
a
l
1
&
]
]
;
v
a
r
s
2
=
R
e
p
l
a
c
e
P
a
r
t
[
v
a
r
s
1
,
v
a
r
I
n
d
e
x
v
a
l
2
]
;
o
u
t
1
=
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
v
a
r
s
1
]
]
;
o
u
t
2
=
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
v
a
r
s
2
]
]
;
I
f
[
o
u
t
1
o
u
t
2
,
0
,
1
]
]
Take the average of many randomized tests.
I
n
[
]
:
=
U
n
w
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
[
e
x
p
r
_
,
k
_
,
v
a
r
_
,
v
a
r
s
_
,
s
a
m
p
l
e
S
i
z
e
_
]
:
=
R
a
t
i
o
n
a
l
i
z
e
[
N
e
s
t
[
U
n
w
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
R
a
n
d
o
m
i
z
e
r
[
e
x
p
r
,
k
,
v
a
r
,
v
a
r
s
]
+
#
&
,
0
,
s
a
m
p
l
e
S
i
z
e
]
/
s
a
m
p
l
e
S
i
z
e
,
0
.
1
]
Find the unweighted influence of the variable p in MOr[p,q] for 3valued logic:
I
n
[
]
:
=
U
n
w
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
[
M
O
r
[
p
,
q
]
,
3
,
p
,
{
p
,
q
}
,
1
0
0
0
]
O
u
t
[
]
=
5
6
9
1
0
0
0
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.
I
n
[
]
:
=
W
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
R
a
n
d
o
m
i
z
e
r
[
e
x
p
r
_
,
k
_
,
v
a
r
_
,
v
a
r
s
_
]
:
=
M
o
d
u
l
e
[
{
v
a
l
1
,
v
a
l
2
,
v
a
l
D
i
s
t
a
n
c
e
,
v
a
r
I
n
d
e
x
,
v
a
r
s
1
,
v
a
r
s
2
,
o
u
t
1
,
o
u
t
2
,
o
u
t
D
i
s
t
a
n
c
e
}
,
{
v
a
l
1
,
v
a
l
2
}
=
R
a
n
d
o
m
S
a
m
p
l
e
[
M
V
a
l
u
e
s
[
k
]
,
2
]
;
v
a
l
D
i
s
t
a
n
c
e
=
A
b
s
[
v
a
l
1

v
a
l
2
]
;
v
a
r
I
n
d
e
x
=
F
l
a
t
t
e
n
[
P
o
s
i
t
i
o
n
[
v
a
r
s
,
v
a
r
]
]
[
[
1
]
]
;
v
a
r
s
1
=
R
a
n
d
o
m
C
h
o
i
c
e
[
S
e
l
e
c
t
[
T
u
p
l
e
s
[
M
V
a
l
u
e
s
[
k
]
,
L
e
n
g
t
h
[
v
a
r
s
]
]
,
#
[
[
v
a
r
I
n
d
e
x
]
]
v
a
l
1
&
]
]
;
v
a
r
s
2
=
R
e
p
l
a
c
e
P
a
r
t
[
v
a
r
s
1
,
v
a
r
I
n
d
e
x
v
a
l
2
]
;
o
u
t
1
=
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
v
a
r
s
1
]
]
;
o
u
t
2
=
R
e
p
l
a
c
e
A
l
l
[
e
x
p
r
,
T
h
r
e
a
d
[
v
a
r
s
v
a
r
s
2
]
]
;
o
u
t
D
i
s
t
a
n
c
e
=
A
b
s
[
o
u
t
1

o
u
t
2
]
;
o
u
t
D
i
s
t
a
n
c
e
/
v
a
l
D
i
s
t
a
n
c
e
]
I
n
[
]
:
=
W
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
[
e
x
p
r
_
,
k
_
,
v
a
r
_
,
v
a
r
s
_
,
s
a
m
p
l
e
S
i
z
e
_
]
:
=
R
a
t
i
o
n
a
l
i
z
e
[
N
e
s
t
[
W
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
R
a
n
d
o
m
i
z
e
r
[
e
x
p
r
,
k
,
v
a
r
,
v
a
r
s
]
+
#
&
,
0
,
s
a
m
p
l
e
S
i
z
e
]
/
s
a
m
p
l
e
S
i
z
e
,
0
.
1
]
F
i
n
d
t
h
e
w
e
i
g
h
t
e
d
i
n
f
l
u
e
n
c
e
o
f
t
h
e
v
a
r
i
a
b
l
e
p
i
n
M
O
r
[
p
,
M
A
n
d
[
q
,
r
]
]
f
o
r
3

v
a
l
u
e
d
l
o
g
i
c
:
I
n
[
]
:
=
W
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
[
M
O
r
[
p
,
M
A
n
d
[
q
,
r
]
]
,
3
,
p
,
{
p
,
q
,
r
}
,
1
0
0
0
0
]
O
u
t
[
]
=
1
4
3
0
9
2
0
0
0
0
Plot an approximation of the respective weighted influences of both variables in MAnd[x,y] for 2, 3, and 4valued logic:
I
n
[
]
:
=
B
a
r
C
h
a
r
t
3
D
T
a
b
l
e
[
W
e
i
g
h
t
e
d
I
n
f
l
u
e
n
c
e
[
M
A
n
d
[
x
,
y
]
,
k
,
#
,
{
x
,
y
}
,
1
0
0
0
]
&
/
@
{
x
,
y
}
,
{
k
,
{
2
,
3
,
4
}
}
]
,
S
e
q
u
e
n
c
e
I
c
o
n
O
u
t
[
]
=
Experimentation
It can be interesting to compare the characteristics of differentlyvalued 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 2variable truth table:
I
n
[
]
:
=
R
a
n
d
o
m
T
r
u
t
h
T
a
b
l
e
[
k
_
]
:
=
T
a
b
l
e
[
R
a
n
g
e
[
0
,
1
,
1
/
(
k

1
)
]
[
[
R
a
n
d
o
m
I
n
t
e
g
e
r
[
{
1
,
k
}
]
]
]
,
k
^
2
]
Define a function to create a random logical function on two variables:
I
n
[
]
:
=
M
a
k
e
R
a
n
d
o
m
F
u
n
c
t
i
o
n
[
k
_
]
:
=
T
a
b
l
e
T
o
F
u
n
c
t
i
o
n
[
R
a
n
d
o
m
T
r
u
t
h
T
a
b
l
e
[
k
]
]
Check if a random 2variable function in 3valued logic is symmetric:
I
n
[
]
:
=
I
s
S
y
m
m
e
t
r
i
c
[
M
a
k
e
R
a
n
d
o
m
F
u
n
c
t
i
o
n
[
3
]
[
p
,
q
]
,
3
,
{
p
,
q
}
]
O
u
t
[
]
=
F
a
l
s
e
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 2variable connectives reachable by nesting the operator. Other potential avenues of exploration might include investigating how the influence of variables changes for differentlyvalued logic systems or writing a function to minimize expressions in manyvalued logic.
Although not explored in this project, manyvalued logic has applications in a variety of fields, including philosophy, linguistics, and artificial intelligence (see: https://plato.stanford.edu/entries/logicmanyvalued/#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/notes129multivaluedlogic/.
Attachments:
Computational Essay.nb
POSTED BY:
Nika Chuzhoy
Answer
Mark as an Answer
Reply

Flag
Reply to this discussion
in reply to
Add Notebook
Community posts can be styled and formatted using the
Markdown syntax
.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Publish anyway
Cancel
Reply Preview
Attachments
Remove
Add a file to this post
Follow this discussion
or
Discard
Group Abstract
Be respectful. Review our
Community Guidelines
to understand your role and responsibilities.
Community Terms of Use
Feedback
Enable JavaScript to interact with content and submit forms on Wolfram websites.
Learn how »