A simple proof of functional completeness in many-valued logics based on Ł ukasiewicz's $C$ and $N$.
Robert E. Clay · Notre Dame Journal of Formal Logic · 1962
Past investigations, [l], [2] and [3], have used the integers 2, 2, . . ., n as truth-values for an w-valued logic.In such a logic, the truth-functions associated with C and N have the following definitions C(p, £) = max (2, q~P + D; N(p) = n-p + L Here we shall use n + 2 -valued logics with truth-values 0, 2, ...,«.As a result, the above definitions simplify to C(p, q) = max (0, qp); N(p) = n-p.Not only does this simplify the computations involved, but also makes a simple line of proof apparent.No logical tools are used, and the only nontrivial number-theoretic result used is "If (a, b) = d, then there are integers x and y for which ax + by = d.n Theorem 1.Any function which takes the value 0 once and n otherwise is generated by C and N. 1. C(p,p) = 0. 2. N(0) = n.3# α m^i> * * * Λπ) = m i n ("' Pi + Pi + * ' + Pπ) i s g enerated f o r m > L Proof is by induction.C(0, pj = p x = min (72, ^) = α^).Suppose that Ot^ is generated for & > 2. ^\θi k (p l9 . . .,^)) = max(0, Λ-(p χ + . . .+ ^).(Λ, b)-d means that d is the greatest common divisor of a and b.All functions used in this paper will have 0, 2, ... , w as the domain for each argument and will take values in this set.