Many-Valued Logics Citation Webb, Donald Loomis (1936) Many-Valued Logics. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/N5WZ-W144. https://resolver.caltech.edu/CaltechETD:etd-04222008-093535 Abstract No abstract. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Bell, Eric Temple Thesis Committee: Unknown, Unknown Defense Date: 1 January 1936 Record Number: CaltechETD:etd-04222008-093535 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-04222008-093535 DOI: 10.7907/N5WZ-W144 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 1457 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 23 Apr 2008 Last Modified: 03 Oct 2019 23:08 Thesis Files Preview PDF - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

'Ihesis by Donald L. 'iiebb In Partial Fulf 1llment of the Requirements for the Degree of Doctor of Philosophy Calii'o:rnia Institute -:;f Icich.r. .ology ?asadena, California. 1936 This thesis is not intended to add any substance to the philosophical controversies being ,_ -zed about trmany-valued logics". Its purpose is to dcvelope, for the first time as far as th8 r:-riter knows, the interesting n:athematical theory which lies behind these logics. It is ~~<n ef1ort to provide c. s&ne method of attack on discovering the properties of operations on a .finite number of elements to a finite number of elements. It is likely that the greatest practical application in the future of the study of these logics will lie in the discovery of relations between operations on a finite number of elements and the principles upon which they are based. Consider the case when n is 2, the Boolean Algebra, and all of the binary operations on two elements such that the result of the oper~1tion is again one of two elements. Study of all possible combinations shows that there are 16 operRtions definable thf~t satisfy these conditions. The relationships between these operE-tions and th0ir properties can be fairly easily established by trial and error methods because Now tc.lrn n as 3. of the smallness of their nurrrber. All of the possible binary operations on 3 elements to 3 elements are 16,183 in number. In case we wish to select a purticular bi.nary opera.;... tion, the methods of trial and error are impractical. This problem was faced when the problem of finding a single binary operation which v'ou.lcl generate ee.ch of the oth'0r binary operations was suggested. The analogous csse Ior n is 2 w&s solved by in- pect1on of the 16 operations. The number- of bin.::-cry operations 2 on n elements to n elements is nn • 2 Lewis and LaI1i£forr. have proven propositions in 3-va.lued To do this they made a table in which they plc.tced the logic. results of a;:,PJ...ying <:3a~h of 3 truth-values to the proposition. If the p:roposition h...:.J. the truth-value acertainly truen in each case, chan the proposition VfaS said to b,~ assertable. It is ob- vious that for the ;:;ase of a general !! we can not make out a table oi' th:L3 sort. :aec,i,_:,~s, this would involve the proving of a p!'oposi tion for each value of n. I1ecc-.use of these d.ifficul ties we a.bandon this m-athod and 6.evelope a more general one. Then we prove propo~itions which will hold for any finite integral value of n. The.se proofs .hold. as -well f'or n = l,J00,000 as n ::. 2. Surn.:v1arizing '!:>rle.f ly tl:e results of t;he fol.!..owing chapters, v;e have: (1) Gew::rallzed !.llS..;.1y results of the Boolean Algebra, obtaining a single binary opera tlon~ which will genera tc.~ ~... 11 of th'~ remaining 011<:.n"a. tious of the logic; genr:;rt~lized the Bool~~an expe1nsion. (2) Obtuined more cowpletely the prop(,;rties of five types of iruplicat,ion, one uf whli::h wus defined by Lukasiewicz. (3) Discovered ·whieh of t.ne import<.!'.nt propositions of W11i tehiaad and Russell l:&rr·y over to L n for five different types of implication. In closing, I '.. ish to express my ap}ireciation to Professor E.T. Bell for Lis dlrE.~~tior.. of this thesis e;,nd his many suggestions relc:.ting to thi.s work. CHAPTSR ONE THE DEVELOPhlEllT 011' THE ALGJZBHA OF N-VALUJ.rn LOGIC INTRODUCTION. In 1920 Lukasiewicz1 defined in terms of a matrix a "three-valued logicn. A Y'3c.:r lat~::r Post 2 generalized tno-valued truth systems, giving an m-valued system. 'I.tis sys- tem was defined in terms of two operators which were generc.11zatio:ns o:f the negation and disjunction of tv'ro-valued logic. Lukasiewicz 1 gave a short characterization of an n-valued system in 192iZ. This w;:,,s followed by a paper 3 in 1930 defining implication and :negation for an n-vo.lued system. Lewis 4 and Langford extended the resuits concerning tLe three-valued. logic given by Lukasievdcz and Tars1d in their papers by using the truth-tables in terms of which Post had defined his n-val- ued system. l. See J. Lukasiewicz and. A. Tarski, "Untersuchu.11gen flberpen Aussagenkalkill", £•.h• 22£_.d.§.£.. tl d. J:&.i. Q2. Vareovie, XXIII (1930), Classe III, p. 32, footnote 5; p. 39, footnote 17. This paper is referred to as LT in subseqm::nt references. 2. E.L. Post,"Introduction to a General Theory of Propositionsn, ~· Jour. of~., XLIII (1921), p~. 163-185. ularly pp. 180-185. 3. See partic- Heferred to as P. LUkasiewicz, 11 Philosophlsche Bemerkungen zu mehrwertigen Systemen des Aussagenkalktlls n, f.•li· §..Q.£. d •.§.g_. et Q.. Let .. .slit Varsovie ,X.XIII (1930), Clc:.sse III, PP• 51 ff. Called L. 4. Levris and Langford: Sxgibolic ]dogie, Century Co., 1932. in particular Chapter VII. Henceforth called LL. See In ttiis c,,&pter "-\'e d;;;fine the implic.·,t.i.on and negative of LukasiewL:z in t;,JrfLS of 'the n~ga.tiv;:; o.nd disjunctive of Post. 5 These ir~ turn are define·.i in terms of & singl1a O}JJr&tor , The oper<:: tors of Post nre introduced sinc0 they will all.ow us to generate the mo.tr:ix of any or.;er functic'n on n truth-v.slues. This 5tet0n:ent muy not be me.de about the illlplicc:ition and negation of Luke.siewicz since they a.re not symbolically complete6. To the ~.>.bove operB.tors •ve ac.d thre'.3 oth,;:~rs, equivalence and two products, pq :.nd pxq. V'!i th these relations ;::e develop an extension of' the algebra on two truth-values to n truth-v<:<.lt(es. A la.rge portion of the propert::i..es of Chapter Two of' §.y:mbolic Logic by Lewis ::..nJ. Langi' ord h:;,.ve be .Jl1 generalized. i~lization By gener- 're rne~m t..nht in the case when n is two the generalized property becomes the Boolean pro~0rty of ~hich it ib the gen- pro 1.Josit.i.ons list.e.:i by 1!:hit2he&d E.:.nd Bussell as th<;; most impor- --------·-----·;\.;bb,"Definition of Post's Gener::lized i~eg2.tive and .Maximum 5. iL Tt:lrn.:.s of one Binary Oper2.tion 11 , Amer • .J...9.£t .. £!_ ~. 1 LVIII (1936), k·. 13~-S-LA. n\.:...tur0. ~'lee P p. 183, ~15. n,o.•=·-',...)-.;_\/• -'..... q. • , ~"Jn .r:' ' V ,. l _ was 6. Post w,;.s familiar with cc result of this f V ·.,, Eis operc:;.tor "'as liefined by '1'1.·P. r~.c"'t'in·itJ..·o r1 ... 1_.,.._t the' > - .J,, - • - - - - - •- • 4. 7 0 ""'"Gr ,,_,te1··:: ,-.1,ov <v J. , .< <.<. •) v j. < <,:;i, J:' p\q.:=.Al'tn(PVmq). For this stateu:e.nt I 8Jr, ir. c..ebted to i~r. J.C.•..:. tic.:ansey of the University of C;:;.lif'ornia. .ror· t:iw :.. efinition of nsymbol- ic<';cli.y compl::te" see L:... p<:i.ge 2:51. 5 ~:Le notatioL used foliov;s tE&.t of Vu:i.itehead and Bussell. Np wc.s i.ntr-o(.iuced instead of NP to avoid confusion with Post •s neg«4tion. IL is mor,;; c1:mveni8n.t to have the subscript of the = truth--VHlues, t 1 , r;:,,.nge i J,l, ••. ,n-1 than .J..H the traditional manner sir~ce this aLL'.)vrs the use of congruences. NOTi'.TI'.JN AND D2'l.:\ll'IION3. Let 11i be c-. logic of n, -/,-here n is a, positive integer, truth-values t 0 , ti., ••• , tn-i. The t1 are marks such th:.it to et.~ch of the t. any one of the n .J. o:r the systeiit u:ay be assigned.. truth-vc-~lues One interpretation that may be given to them is th<.4t ti is less likely to be true ti:·1an t. if J i<j, ti is as likely to be true as t j if i and ti is more likely to be true tr.an t j if i >J. Then tn-i is ta'.ce:n to be ce1·tainly trLl.e and t 0 c:ertciirily fc.lse. the remaind1sr =j, During of this chapter ~-• mei.y be interpreted as being c;2rtz.inly true since we c~.;e_pt a vroposi tlon o.s being assertable when we ean show tt. a t 1 t has the t:ruth-v2. lue t,,_, for c.11 pos- sible truth-values tLa.t the c:olliponent elementCi.ry .Propositions may assume. Sinc3 these demonstrations i1epend upon the subscripts and not upon the truth-values correlated Tith the subscript, we can corr·elate any tru'th-value with t 11 -t and obtain a series of propositions having the truth-value correlated to t~_, for all possi- ble truth-values of its component propositions. Let Ln be the logic based on the implication and. negHtion of .Lukasiewicz7 and in the co.se of L3 , as modified by Lewis and 7. See LT and L. 6 s1·~ni_fie3 <. cion~J that pis .._ • ~· '· l r J .i.Jr1 ~t~ ·V\.< • of+, - , ·, :, >, <:, ,~LDi J..r~-su. ••. , e, h, i, J, k by~. b.. S usual, i .. o~lo~~-i:J~g If p has the truth-value t 1 , [P]' = i ~ ( 1-i, Ci, ••• , r; a, b, ••• , e >] 1. (i = o, l, ••• ,n-1) .. Df' Df ind.icates f(p,q, ••• ,r;a,b, ••• ,e) is considered as a con- venient method o.t' writing f( [p]', f9.)', ••• , f!J';a,b, ••• ,e) where p, q, • •• , r €. Lzi; ~. a, b, ••• , e E A. r~;EJ; •.. ,(!1!a,b, ••• ,e) may be any rational poly- nomial with arguments and operations in A. D)J' = i, [q]' = j , •.• ,(r]' = k f ~1~1Sl) ••• ,f!'J a, b, •. , e) =c, then [r (I.1, q, ••• ,r; a, b, ••• , e ~ : d 3. where If for c:: d .mod n, O~ d~ n. If we enclose a system of brackets in another set of bra.ckets, "e shall consiaer tt:.e ex}!res;:;ion to mean tL.b.t ·.·.e shall operate with the inr.er bracii;.ets be.fore consL:ering the outer set of brackets; e.g., by (_[taj'+~ 8. See LL Ch~~ter VII. 9. Gee P. we mean [1-rjJ • 7 The chief 1.lii'f e:Cdfo..:'.~ bJtwe 1..:in [ J and [ ] is t.nat aJ.l op1 er& tious indicated in LJ' are i.ri. Ln wLL.. e ""LL op,.::;r,, tlo:ns indi- cated in[] c:~re ln A. [PJlf ~]. .An ~3::;.r::mple is [P:> qJ' =(:"1-l+q-I:} if This st.'.':lt8:.r:.ent mit;ht be vieitten. as i'o1.10·;7S: If J! tlas t:ne truth-value t 1 ana q the truth-value t,, ':there ,j i)d, then the truth-v0.lue of ti.:::>tj is tk '.Vhere Ic ::: n-lt'j-i. It is conv,:;nient to d,:;fine: If (P) :: i - ' [Ci] - j ' (. qfl = j where ~··~. (..~.,/:r.. \l!' -- i Df then i~j vthe:re i 7j. = i, Lei] = j ' then i ~j [min(p ,q)] = j i,1rhere If fi'] - 1 v.zhc.,r·a D.f 1 <_j. It is evi·.ient from th·:; prop9r'ties of '..;ongrw.:n:es tr:;.c;..t [[.:':]+ ~ may be written as ~+b]. Ac·.:oriir..;:_:ly, 'Nf3 s:<~z,li con- sider [at may~(p,q)] to Jl,can[~J+ [uu..A(p,q2JJ, etc. Dots <::.re used h<?re &.s ir~ the t 1 ·io-v2~1ued logic for :;.mnctu- at ion. The t~uth-tuble for pf q is elven by: 1 l.Jl ~":llcQ : [1+ m~~x(p,q)J D.f Other I• ···') \,). ·- ....' ' 1 '•. • ,r.,..-.,, 1.02 Df 1.03 Df 1.04 Df 1.05 , / '\T ) .1 }-' • v. l'tq Po1 • -- • .i.\iH(~r.... Df 8 We shall at tinli.?S find it mor:..:: convenient to u::e p.q tt.an pq. In such inst2.nces p. q vdll be co.nsid8red 1::~s lu~~'£«:;1y ::cno lher way of writing pq. 1. 06 p :J q • =. ( pc.)[11-1-p] D:f l. 07 p ~q • =: p :::> q • q .::> p Df 1.08 pxq .=. (p'tl- 1Vqh-)i Df THEOHEMS EEA.DILY l) :..0UCI.8LE. .i?rom the prece,.,dng Jefini tions we can reajily show the follov:ing theorems corn::erning their properties. l.l [Ph]'= [_P+-h] [Ph]'=~"-') Proof: p•-f ~+max( [Ph-J [P•j~ (1.o:z,1.01) =[ 1-t-(Ph-•JJ Continuing this process 1 [P11] = [l-t-[ph-J'J= [2 + ~h-~= ••• • f!1+ [P°Jj Or ~j' = [_h-t PJ • 1.2 (pVqJ' •[max(p,q)] Proof: [PV a:J' =~P/ q)11-1]~ Il.+rr.ax(p,q)tn-1] = ~ax(p,q)j (l.03,l.l) I i'Jp] =[n-1-pJ Proot: [!ip)' = fp +2n-8p-3:) ::.[:.'1-1-pj 1.3 1.4 ~'fl Proof: I (l.04 1 1.1) = Enin(p,q~ [PQ] :. [n-l-max(n-1-p,n-l-q)] (1.05,l.3,l.2) If ~] ~ [9] , [n-1-~>JE-l-c_!J anu )Rq]':: [f] If [P] >~] , fr_i-J..-i¥E_i-l-qJ ~nQ ~q] ' If (P] = (q], fri-1-p] =~1-l-q_] ~nd Hence~ [pq]'= [min(p,q~ =[q) fr<U' =[P] =[q] 9 [P :::> q_]' =- n-1 l. 5 ii [f)f2[q] = [n-l+c;-p] it· u~ >[9.J ?roof: (?:J aJ' = [au.n(p,q)tn-1-~J 1 If [P]"~ fg} , QI :::H1) :: (? +,.1-l-P] : r,.-1 If [P]:;>[c~, 1. G [?~q] = 1 (l.06,1.1) = [n-l+q-pJ [p qJ' : n-1 if o,lld or,,ly if [?] :: [q1 :: [n-l+c:-P] if U='J > [9.] :: rn-l+P--0 it g>J <Lcil (l.07,l.~,l.5) ?roof: .Frorr. 'Lhis 1°osu...1.t ,,,,e reuiily see t.hat 1.07 implias that t· .ro proposi -cions ruay be asserted as equ.i vu...i..en't when and only 1 when they hc.vc; the same truth-table. Using 1.6 ;.:nd the pre- CGding th;;;;orems we im.u1e,;,iately get the foi.lowing r,'Jlations of equivalence between the operations in 1r1 ·.;;ith those of Ln and 'rhe diff.srence in notation of truth-valuJ::s must be con- Pn• siderad. \n in 1ri becomes n~l in L.n and tn-m in Pn. [n-l+q-rj in Ln becor!les Ll: -t q-p} in L,n 1. 7 16 p.:) q.:::. pCq; l.a'' Np.::;:..(Np); l • o" .,, p .J q. E £n, l'-Ip. ELn, and [J. +q-p] in Pn. pCq • E Ln .. (Np) E~· w.... p~ q.:,.p~, p ::::> q. :>q :=..p yq 1.10 Proof: [p ?q. :> qJ'::. f!i-lty-(n-1)] :: {S] if [_P]~@. J Since (:i-1+ q-PJ::>Et] if CPJI n-1 =(qJ if' (P)= n-1, l:J. See LL p. ,.;;13 footnote or L p. 72. 11. See i.ii.J p. 214. pEq Thus v1e is UJLefined for L;n• have 10 ~:;:>q.~q1 = [n-l+q-(n-1)-qt-p] =[P} if [.~>B] [_p:Jq•::> qj' = n-1 if [PJ =n-1 Hence, 1.11/J. 1.12 11 ( [13-\ n-1 q1 = ~uax(p,qj] ;; [Pv ~ p~cj~::.pOq; pVq. 6 L3 , pOq. € 1.3· pq.:::-.pAq; pq.eLz;, pAq.e 13· ~::>Q.:) 1 1 i . p .:::: ·~ p, p ·=·~P 13 1.13 and \. (i =:~, 0, ••• ,n-1); p , pi. c Lu; :1. - Al')'JP, A4,.P.£.Pn• 1.1~' pVq.=..pVnq; [P >tq] 1.15 f pVq. e in' =0 if' f?~ =0 = [max(p,q~ if Proof: pVnq• E Pn• I [P~~O rp'1-q]' :! /...:'ri-rmax( [n-lt-pl, rn-.l-rql )1 . 'J e !J u ~ (l .os,1.1,1.2 ) [?q]' = O, [pit<!]' : [l+n-:iJ : O If [pq(? o, [Ei21.x( f!1-l+~, [!i-l+:J ~ = [_n-lt-max(p,qi} I Or [!>ic qj' = g.-rn-1 ill"'-~· (p, c J] ::: E!· ·~:{ (1J, . )j if [PcJ =I 0 • If 1.16 pVq.:.qVp 1.11 (pVq)Vr.~.pV(qVr) Proof: EpVq)Vr]' :: [max fmax( ,q) ,r}] :::: [t::":~{p,w.e;:x(~-1,r)}] :: ~V(qVr~ 1.18 pq.:=-qp 1.19 (pq)l... -;::;.p(qr) 1.21 px (qxr) •:=- (pxq}xr Proof: If [<pq)r] 1 :: Cl then 1 l.(31 reduces to L.18, if }Jpq)~/ 0 then 1.21 reduc0s to 1.17 ------------·--·---·-· 12. See Li, p. 214. 13. See P p. 180. 11 1.22 Proof: p(qVr) .. =::pq. V.pr By 1.16 with_,ut los3 of generality Y;e can ta'-'.:e [<fi ~ [r]. J, then [? (qVr )j\\f ::: [q] snd {Rq. V. prJ = [?J I If (13 &[q1 /' [r If Bl/ fPJ ~ f!-1 , then [p (qVr )]' : [P] <:4nu 1 [P<'i• V. p-r] : [P] If~> [r} >{Pl , then [P(qVr~' =[I1 and [pq. V•PrJ = IPJ • pV(qr).-=..,(pVq)(pVr) 1 l.23 Proof: 1 .. 24 Similar to th:'"'t of 1.8;2. pV(qVr).=::pVq.V.pVr = ~axfmax(11,q) :tnc.'cx(p,r)}] • Proof: ~ax\),max(q,r)TI 1 .. 25 Proof: 1 px(qVr).:=;pxq .. V.p"X.r [PJ = 0, ~" ( q_Vr )]' :: 0 und [_P xc_. V. p·.crj' =0 If J9.]:: O, (:lVr]'=[!J cLnd ipxq.V.pxr]' = [P.,.r]' I Hence CT))l(qVr)] ::: [pxq.V.pxr] if [:ll :: O.. If I Similarly for [r] :: o. If [~~to, [C.U.fO, [!J=F o, then w<:: c:«n replc.ce x by V Ei.:i:~d 1.25 bec:omes i.;~4. 1.26 Proof: - • V • DQ P •::; ·p .... ... "" IP· V.pqJ' = [m:.:.x {p,min(p,q)}] If [?] ~ [9] t.hen fp. V. pq] =[~ 1 If fp]>[q] then l?•V.pq]'=&ryJ 1,.09 pVqVr.:.pV(qVr), pqr.=.p(qr), pxqxr.=.px(qxr) Df Df l.011 D.f are b ny elenrnnt<.:.ry pro 1;osi tions .. l.;~7 [xij' = 1 if £~] = n-i =0 if [x] -:f n-i 12 Proof: Ii' [x] =n-j where j=f 1 then [xJJ'= [n-j+j] = o. But / xj occurs in x , hence [xi] =- 0 i:f [x]:fn-i (1.4, l.09, 1 1.010,1.18). If [x] = n-i, [x~{= O, [!ri+~f: 1 and [xi]'= 1, since t 0 does not occur in Xi. l.~38 f:x 1xyjx ••• xzkJ =l 1 if = 0 Proof: [.x] ::: n-1,[yJ =n-j, ••• ,}?] = n-k otherwise. (l.27,1.15). 1.29 Proof: l. ...,rz.o (l.4,1.27). i-i j X~11'X'"!==· t 0 Proof: (l.15,l.87). 1.31 1.012 By F(x,y, ••• ,z) we represent any function. of x,y, ••• ,z. Or to be more explicit, if f!~J::; 1, Df f.¥J = j, ••• , f!.J: k, then F(x,y, ••• ,z) has a deflnita vo.lue h. F'(t1,tj,•••,tk) has the truth-value that F(x,y, .... ,z) has when x,y, •• j,z are replaced by t 1 ,tj, ••• ,tk . 1.013 If then F(x,y, ••• ~ 11-1 ..,, - , res1;,3c:tively. 71-1 T1-l .,.,_, ,z).=·Zf···.Z.JAi·J·· .. 11 X(X 11_ix.Y"/l_.x ••• xz _KJJ =• J J i :oo .K "' } } 11 ) ? [:··>[Ai j ... ~(X 11 _/-YJt-j x .... xz.,,_¥)}, where Ai- J.... K f?';,, I '\ I I I l .::o J=o J J represents some :..:.e.i: ini te truth-value th \\'hi ch depends upon F(x,y, ••• ,z), is ~aid. to be the norwal form for F(x,y, ••• ,z). 13 if [_x.J :: i The above is a proof th<..t :fi"'(x,y, ••• ,z) :.nc.y t:dways be ex- Proof: If [x] for [>0 1 a gerieraliz;;J:.::1..on of' (1 =0,l, ••• ,n-1). ( l • 4 , l. • :z? ) • x(/Vx) : 0 in .;:.,. ,,_,__ • 1.05 c<..n bG used as a proof tliLt £<.ny fun.::tio.n. F(x,y, .... ,z) ~.s.n b2 g0rL"::rated from plq· In SU(!h ;;,;. proof v.·e wo·uli.i subs t.i tu.te ( t )k, ·,~-here I 0 k :: [F (ti , t j , ••• , th)] for F( ti, t j, ••• , ·th) as the coeffi;,;ie.u.t, oi X::i-i Yn-j •• • Zn-h'" Then, sinee we h<.;;.Ve obtained. t 0 in. t<'ffuis of pf q, w:e· :~<we obtained F(x,y, ••• ,z) in terms oi' p,q. '.£his ma;r a ....so be consi:0red as a mec..n.s of J.etermining an expression for b.ny single V<_,_lw::d function on a finite m:m1ber oi' elements Lo -~ fini l.e IlllLL-8!' of clements. ·ye also sc;e 1,_W:'. t in Lq 1. 3b be,::;o . Les tiw Boolr)<:,n expansion. '"' CHAPTER THO I.MP LI CATION In L0;:_, ;,re f incl the. t p .:::> p anQ p :'.) q. q :::> r : :::::> : p :> r hold • How- ever in Ln the imp . . ic<.< tion of' Lu1':as1ewi-:~z fails to possess the latter property, that of tr<:;.nsitivity. There nre ;:, grea.t number 15 . . ..t '~ •• i . o·f poss:i. bl e c 11ol.ces 01-~ r.nL. t r ..1.·"'es usr"1 ning .unpJ. ca. t ion re l a ti ons • > If by piq wt: ruc:c..n 11 p illlvlies q 11 anu if we t0ke [piq]' =n-1 if and only if [PJ~ [q] it is inter~sting to o.iscover the neces~>o.ry and sufficient conclitions that must be imposed upon piq before the pro:r;osition piq.qir:I:pir holds in 111 • Using our earlier interpretation for truth-v&lues we see that the condition ~Iq] , = n-1 ii' and only if [PJ ~ f9J involves the principle "a lJro1~;osition implies anj' which is equally or mo1'e prob&ble; and 16 ., ' or l ess pro b R bl e. 11 i s i mp li ea by· any wh'ic h 1 s equai~y l An investigation of the possibilities of piq dei'in::id in the above manner lec..ds us to 13. l -~he followir1g theorem; If [?Iq]' = n-1 •,vhen and only when (Ij ~ [q] then 1:n order for [piq.qir:I:pir]':: n-1 t 1 , tj, tk 1. it is necessary c.•ud sufficiz:;nt that If (P]) (q) ;> (r] then and 2. where p,q,r may assu.i.11e any truth-value [picy '~ [pirJ' [pirJ 'f- [q Ir.J' And if p,q,r hli.ve pc.rticul<-<I' truth-values, say t 1 , t j, and tk res pee ti vely, 15. See in particular 16. LL p. 230 .. where LL p;i. 229 and ~~30. i > j /' k then either 15 (9111/~ tph] ( 1 or IPiaJ'=)£Ir] [qir] =[pir] ;~nd [PI~' 2 ~I1J' <-.nd I I (q!rj ) fpI1] r.nc t)rocf ~ I [?I~ >k:Lrj' 1 !i' L. I ~..i.w.ul t&J:leously. hoL:.:.t..11g [t-] :=- t_r] =u-l., ;~. ,.. "'·' ··1·· J..u.Ul'.\. .J..il;; ·rr··:..._:.t" T nirJ/ - ll - 1 e r-.""r. f!'..t..'i•L:. [PJ>~l a. [xJ~ lSJ • '.!.'hen [p!q .. qlr: I: pI1f lk;co1,.es [plq. I. pir]' ~ince r;:; I rJ;'I' -- .,.1-J... , t9 Thc:c•3f 01 e, ii' [Ij) [!] ~ [cij then 1 jpirJ~g)Ir] ii:.. or·,:,e.r i'o:. ti4e proposition piq.q!r:I:pir to hol< S..i...n.i..::c by l::.y.._:.otl1·::;;;:.;is i.f b. fpiq] =n-1 ii' and only I [p] < [9] • [cl] 2 [p] / [r] . f.?I<.:.c~Ir:I:pI:]\,u:::ci12es §.Ir.I.pl-ft since [pic~/ = n-1. ::i.:~~n,:e, ~s ~be vs, if' [cJ ~ [P] "> [r] then '< g)IrJ I . §Ir]== .. • [i~> [Cl];> [r] • In plc;..qir:I:pir i'r·o.a1 .§;. .::,fo.L J2. we see tlJ.at the I [qlij .?, [>Ir] I [?rqJ) [prfl 1 mu;;; t hold. 1 6 If these cone i tiN-:.s .r,old U>Iq.qI1:J'6 ~Ir]' in. the <.tbove stt~te:rnient, I ~Iq.qir:I:pI~~n-1. otberv.i.se by hy,otLesis Ihen, irorder for the equality sign to hold, fo1 ec . . ~.:.cti.c;uL~r ~><:!t of truth-values ~rn.ch t:h<...t (P] /' [?J 7 [t'] , it :1.:1 nuce;;;,s fi.r:;t :.nci suff ici~0 nt that either r; , :rt r; ~- ,..,1 ~1IrJ :; tPJ.Ij ~irqJ' L (?rrJ' or - [:lir]' > fpI:J' [Piq)' : ~Ir]'. The &11ove ccndi tions &.r'.:; evic:.ently suffiL;ient. n)2 sine:; i..:· [P] ~ 2, rpr ""' ,..,l I -l!' _., '1J :;3nce !;n 1 "f"" :-il I.: --».J-"j -- '1 (q] = l, [rJ = 0 7 J. - , . ) J f:,, -_,, r-'-,. • "'\~ '"" ... 0 Ii' _, ..,-';1 4-J I --~ LL-{~" a [? ::> c,. CJ:> r :;::> : p;:> .r.;]' -; (n-J:t·T1-3-(r:-::)] - n-2. Df' e.m~ Df' 6.03 Df Df 17 6.05 Df pI~q.=.pI~~.V.q.V.Np "' .,,; FrorJ th :s 3 J e.~'L1.i.. t,.._.:;_:,3 by n.:.ec:•llS =n-.l. ii' s.~2 IT_;I 1 cij 01· crie \..l'l.30I"G;t:S oL the [f] <[cij = ~1-lt-q-£iJ if [P] >[cg • p 1~ : .lh~J"l)'.) t " •· ~) '"') • \...t.. if [i:-]~[:11 (~. 3 = 0 if [p] / tJ 1 P:rcioi': If [p]~[<!J than q]' = n-1 c..n.0. ~1 q. I l. (pI qf ] :: (t,._, ! 1 1 1 1 fr-:-·nce ~I 2 q]' :: [N fpl q.I (pI 1 <;)iJJ'::: n-1 if fp] ~ [q] • 1 1 wr If ff]>~:] ti"en so..y = i ,,here if n-1 ~ then [!>r 2 ~ = [riit 1 1 1 tit-l1]'= [n-1-(n-lB ~ o. 1 6. <~ [_pI 3 qj' = = Proof: ri.-l if [8 5 [q] [ct] if fp] / LciJ [PI~::q]' = n-1 / {?r.~cij = o 6.5 (pI 4 q]' fpr 1 c~ if 1 if [p].:'.: [ci.J, Proof: Same type as in !:3. 4.• B.6 [pI 5 q] = n-1 Pro0f: (G.3 1 1.~) I i.f 1 [P]<(qj = [Np.V.aj ii' [_;J;{q] chec\:{ t.r~e C:)ndi tior:.s [?I;:4•V.a] 1 = n-1. [~ > ~1], hs.n~e fF1 8 q. v.qJ' = [qj in this case. = n-1 i..f (P] ~ [q] =[t•-1-;J i.r G:iJ / E1] By theorems fie;11ce tJ' = O. 18 of (J:~ - n-l, fir·7 - ,. [i] :: n-:.::, J.:J ;,_JJ n> 2 that ~I5cJ ') ~Is:r]' [lI5 :rj' ~15 r]' 'rhus > 1Ne c:::."11 say -~--.:, pl (; is not tr ....nsitive. 5 Vie '-:'. .08 '.~.• I.piq 2.oz ~) .16 piq.I.Hc~INp :.. .. 17 p.I.qir:l:~.I.pir c;_!r.I:pI(..I.plr piq. I :qir. I .pI1· ;.:::.OJ pip ~?..21 p.I:q.I.pq 3.27 pq.I.q 3.31 :1. I. qil': I: pc1. I. r ::t p.:c_. qir: I; pir ~t~ {, ·t,,...·t_. plq.pir;l.~).I.q_1· :;:,.35 p.pit_t.I.q J.1st these 19 3.45 piq.I:pr.I.qr 0.47 plr.qis.I:pq.I.rs 4.01 pEq.=.piq.qip 4.1 piq.E.NqINp 4.11 pEq .E.NpENq 4.13 p.E.N(Mp) 4 .. 2 pEp 4.21 pEq.E.qEp 4.22 pEq.qEr:I:pEr 4.24 p.E.pp 4.25 p.E.pVp 4.3 pq.E.qp 4.31 pVq.K.qVp 4.02 (pq)r.E.p(~r) 4.&3 (pVq)Vr.E.pV(qVr) 4.4 p.qVr:E:pq.V.pr 4.41 p.V.qr:E:pVq.pVr 4.71 piq.E:p.E.pq 4.73 q.!:p.E.pq 5.1 pq.I.pEq 5.32 p.I.qEr:E:pq.E.pr 5.6 p.Nq.I.r:E:p.I.qVr Dt Utilizing the results of theorems c;.:::,6.Z,G.4,,G.5, and 6.6 we obte.in the follovring table or results. able and N for not Ei.::isertable. opposite 2.02 and uw'ier pI1 q. ~hus, A stands fo:c a~'sert- in the t;:, ble we find A That means if we replace I by r in 2.02 above, the proposition is asser~able in 1n• the table reads in the same manner. 1 The rest of 20 pI q 1 Pl2q pI q 3 pI q 4 PI5q ;~:. 02 A N A N A 2.Q(j A A N N A 2.15 A A N N A 2.16 A A ~Ir ~1 A 2.17 A A N rJ A 2.04 A N A N A 2.05 A A A N A 2.06 A A A N A s.oe A A A A A 2.21 A N N A A 3.2 A N A ~,\T ;.1 A 6.26 A }. A A A 3.27 A A A A A Z.3 A li A N A ~3.31 u A A n N 0.3::5 N .A ti h A li 3.35 M A J~ l{ }1 3.~3 A A A A A 3.45 A A A A A ;_).47 A A A A A 4.1 A A N N A 4.11 A A N N A t.1.13 A A A .A A 11...t. •-.J -? A A A A A 4.~n A A A A A 4.22 :r:r A A A N 21 pilq pI2q pI7q ..., pl,,q '"'' pli::q !±. ,)4 A A A A A 4.25 A A A A A 4.3 A A A A A 4.01 A A A .A A 4.32 A A A A A 4.33 A A A A A .{.4 A A A A A 4.41 A A A A A 4-.71 A A A A A 4.73 A N A N A 5.1 A N A 1\f ... , A 5.32 N N A N N 5.6 M N N "' i• N 33 30 21 33 0 Total of Ats The above table is verified ::;.n succ:eeding pc.ges. The five propositions 1,-vhich Luk 0:sievdcz 14 states as bein H sufficient condition that the systecrn Ln w.a.y be put on a postulational be.sis hold in Ln, for p! 1 q. They follow: p.I1.qI p, pI1 q.I 1 :qI r.I1.pI 1 r, pI 1 q.I 1 q:I :qI1 y.I 1 p, 1 1 1 pI1 q.I .qI 1 p:I 1 ;qI p, NpI 1 Nq.I 1 .qI p. 1 1 1 By utilizing definition 4.01 pE q.=.pI 1 q .. qI ? (i ::. 0 1 1, ••• ,5) 1 1 we obtain the following t:neorems con(;crning th1~ truth-tables of pEiq: 6.,7 J:~. [PE;~qJ'= n-1 if [PJ =[_q) = 0 otherv'ise. See LT p. 41 (following_ Theorem 26). 22 6 .8 6.9 ~E3 oJ = n-1 1 if [P] ::. @.] - [?q] 1 otherv.'ise (PE4 oJ' = ~-1 if l_PJ .,. [qJ = [.t·Ip.l~qJ' oth::;rwi~e 6 .10 V)E~/·J ' = n-1 if [IJ] ~ f:] ri(~'T,-, "IT ) (N~J,.c1.•'-'•P:J - i:r )11 t_x";).v.c1 1 Below \'."8 1:'1<-~v1~ J:.roven the results of the t;::-.bl8. v:c first 11st the proposition number c...nc. then have fiv~_; sub-nUEbers under this he<::~ding. The fir~;t sub-nurilber relers to the ViH'ifiC<-"tion of the result for pI q, the De;:;oncl for pI 2q, etc .. 1 2.02 q.I.piq True for piq when [I~~ [ci] • 1. [El> [q]. f!>I 1q]/ :: §-lt-c_-;;-j But [SJ< ~-1+<;-P] since ~-1-P] 2: O. Hence t.~e proposition holds for c:..ll[PJ, [9,J. 2. [q.] :: 1, then Let [p]::: 2, = O, .so .-1oes not hoLt when n >B. 3. If [~:>~] then ~I 3 q] = @1 therefore tlJ:sorew holds. [1.I_i.pI 2 qJ 1 1 4. Let [q]-= n-2, [PJ = n-1, th·:::n thi:~ors.w. docs not hold for n :> :~. 5. ;3.03 f?J >[q]. [ c!I > f!!p] I evidently holus. pINq.I.qINp True if [Ei-1-Pj 2_ ~ • 23 ~l-1-pJ <:::~) • 1. Then [pr 1 Neg'= [p.-l+n-l-q-I1 si:r:ice [PJ >(:•-1-cf} hnd '~lso [aI 1 Np]' =~1-l+n-l-0-i:J tt<'~~i!:L tl'.e 1;roposition hold. =o = [:I 2 IIp] ,:r.en[?-1-P]<[G]· 2. 1rolds since JPI~~~·Jcj' ~. Proposition does not hold vhen n:;>:=: forfpJ= n-1, El] ::: n-g. 4. P:::·o;.:osition does not hold when n. /2 for [P]:: n-:2, [q] = n-1. 5. 1Nhen [NPJ<aJ, and [qI~}JP]' =~!q.V.Np]~ [PI!.}It] :: (Ep.V.N~! Theorem holds. 2.15 then 1 llic~'<fp] 1 Npiq.I.Nqip. True if ~'Sq]~ 2.16 IPJ. piq.I.NqINp. Proof same type c..s in }.~.03. 8.17 N~INp.I.pio. C.04 p.I.Qir:I:q.I.pir. True if ~>] ~[!]. [13 >[r]. 1. True if (q]~ (!i-1-tr-p] Tr.:ke [q);> ~-11-r-12], then (q]> [r] ::enc: [n-1-q+r] <. fp]. Ac::orc:irigly, JS•Ii..pI 1 rJ' a1-:;.ci = ~-lt-n-lt-r-p-q] [f.I 1 .qI 1i;J' = &'l--l+n-l+r-p-q] theorem ;:;oes not holc'1 for n > ~~ .. 3. (p] >fr]. Holds if ~]~ [:]. 24 •1.. Does :lot hold i'or n / :~ 'r:tten [P] 5. [p] ;>[rJ. =~IJ• V.rJ 1 • ilolils if [<.!JL_frip.,V.r] 1 Tnen f!?I 5(( [c!}:>~i;.:1.V .. r]r, t~~er;. [oJ>[!] ,[q]7nip] , 1 Take ~· neuce JP]>LJlq]~ c:n,1 re ·- .p~- ~,1 1 =~q G.· •V• ·'" .. , ...1 1 ~p.~.~ ~.~ 5 5 <.ind f£.I 5 .qI 0 2.J5 = n-:~, [q] = n-1, [rJ = n-3. 1J1= fuq. V.~~·p. V.~f i!H.1king theorem hold. qir.I:plq.I.pir. True if [0 {::[!] • 1. [~>fr] .. [~ :>fp]>[rJ, ~I 1 cJ1 [nI1 q.I 1 .pI1 rJ @-I 1 r] 1 1 = n-1 .:~n(i ~I 1 r] = fri-ltr-~ making 1 :: JEi-1-t-r-pJ = jE-lt-r-qJ, but (E-l+r·-~E.t-1 -i-r-~ making theorerL holci. for this case. G~ >L<il >I!J ' [pI 1 q.I .p1 1 r'] = (E-l+r-<U -= [9I 1 r]~ so th·::orem holds. 1 1 [PJ >[r] ~ [qJ, !JI r]~~I cD so t~n:::oreo holc.s. 1 1 2. Holds. 3. 1 / ~ > {!], [pI 3 rJ ~ (!:'] [qJ~[r], holds since t.i.i.en [9I 0 r] 1 :: [r]. = [9I.~il • u:J ~""~ [?J )' fl]:?Ii], ~I~'.'.}-t•Ic .pI 3 1]' = [r] = [gr 3 r] [q]? [;)]:> [!] , [FI" ~.I 3 .pI-:srl' : - 6 fr] 1 1 • .:J_.l;:'.lse if [p] 5. :: 1, [q] = l, [rJ :: 0 [pJ /[r], then [PI 5 r] 1 = ~P· V·1· and n> ,;,. 25 the th,.; 2.06 theorem piq.I:~Ir.I~pir True .ror [p]? IJ:'J • 1. [q]/[PJ7 ~J,[PI 1 :J , = [:1-l-tr-p], [qI 1rJ'= fr.-l+r-q] since fr1-l+r-p]~ [n-lt-r-C'J, E!I..L .I1 .. pI 1 rJ' = n-1. [?] >&.] > fr] fqI_r.I 1 .,c;I 1 r1'::: [n-l+n-l+T-p-(n-1)-r+c{l L .L ..i.. -- J :..J :: [!i-l+q-p] But [?I cJ'= [!1-11-c;_-ri)so theoreni holds. 1 fr:J>uJ~[cU: [Pr 1riJ'= [ri-l+q-p] aLd ~Ill r .I1 .}).l _;_rJ' :: E_i-l+r-i} But (':1-1-+ r-p]L- [E1-l:f- q_-p] so thcore1,, hol:ls. 3. [p] )'[.:], fpI;;;r] r =[}J. fpJ~[_rJ, then [qr 0 r.I;_-1.pI2:.r] 1 = [r] cc.nd(EI~,<] = [cJ~[rJ. 1 [9.] >[!'], 4. 1 then f2"-I;:/•I 0 .pl;:;_r) = n-l. :fot c:sssrt::.;:;13 i'or n )'2 if LP] =1, [j] = O, [r] = o. I 5. (P]>~J 1 fFir rJ = gr~1. v. rJ. I 1 [qJ '§ f!J, lqI 5 r]' = r.-1, (5iI 5 r. I 5 • pI 5 r]' ::: G'\lp. V·'€J '· 26 '.2,.08 plp Evident. True .fo.c ff1] ;- [:i] . i. [P]>~), [Pt 1 cU'= [:i-1t-q-cl~Ui1J. 2. ~~<..)t <:J.s:..,erL<-hie for[p]== ..... , 3. '(ot ;,:=:>se:ct.'. b.:c 4. 'i'l'kd 0 for[p]::: l, :;:~L>3 ;.·;hen [.?] >[q]' [q] = U v;l:E:n n>;~. ru - 0 v·ten n /:2 .. r~)I4ca I= UJrJ ~ 5. (P]>(a], (pI 5cD' = fr1p.v.cJ'?EIP]~ True ~·.·hHn ff] ~ DJ • 1. [P] <[Ci]' TJFm [ q .Il · lJ~/ = n-1. Q?J = 1, [q] =~3~ Go].z[SJ, [PI 3 :q.I3 .pcJ' =[PI;:;I:]' =n-1. 2. 3.26 ~fot '·' _sc1'1A:~bi.c for pq.I.p True if fp] ~ [q]. ~.hen n ? ;2 • 27 If [t")] >BJ tlten we h.-_,ve qlp TNh-Lch fo~~ ;:;ile:3e values is asc:artabJ..:~ ~.3 :·or (:} Ll- ::'iv2 tytieS of irL'.)lL:etion. pq.I.r:I:p.I.qir Tru'3 for 1. (g] >[rJ • [:i]>[r], [qI1 r]'= ['l-l+r-q] [P]~~-i-l+r-q] true [p]>[n-1-t-r-q_], then Since [_P];>f!] 3. I -=- ~-ltn-1-tr-q-Ij U'Jq. Il ·:l '= f-ltr-min(p ,q)] I 'l'l1er0fore [pq.1 1 2. E.r 1 .qI 1 rj .r]'L.[j:.r 1 .qI 1 ~' an~i theorem holds. Not L.;:;32r-t;'"blra for n,> 2 ''!hen r [q]>f!] , [qI;s~ :: [r] Holds if [_P ]~/!]. . ( ( CPJ>[r], [f.I 3 .qI 3r] =[j:], ~q.Iz.rJ =fr], so theorem holds. For n) 2 the theorer.;1 is not £»ssert:::.ble for[~ - 2 1 [qJ = i, IE] = ~). 5. !il>f:"]' fur5:c]':: fr1q. v.rJ: [!3~fr4q. V.r]' lioL.is. [Pp(!-iq.v.rj: ~o [pq.1::;·1)':: fl~p.v.~iq.V.r)~ making proposition ho~d. 28 p.I.qir:I:p~.I.r 0.31 True ii' [pg';::-fr] . 1. Ho-c ;_:~'..,c;r-cc:;b.lc :.'or n.> :2 2. If v;Lf.;n 1}1] =- l, [p]~j,[C.]>J!J the::n [f.I 2 .qr 2 f?q. I~~. rJ 1 =O, rue. ::if11~ t :J 1 :: EJ :: l, [:] - O. o, ;:;.na ·c.:i:_ •. o!·e~. t . .olc:. UJ ,> ~J .• BJ >I:J , IR_q. I;;). i:J /=[!] and [p •I 0 • q I;: rJ = f:J . c.s sc:rt;,t.l.e for r. 7'.J·"' when [p] 4. - l, [j] -- l, [r] -- o.. =:: . Not sert[: 1Jl.e for 1172 V'lien [rJ ..,. - 1, [Si] :: 1, fr] ::. o. ·f Holc,s s irw e for t. J. I ~Jot E~s piq.qir:I:pir ~~. i53 For r:roof s see earilie:r: pc:;.rt '.J;. tne :..'t~ pt er. 2. .Assert&bJ...e. 4. Assertf' ble. 5. Not ~ssert~ble. p.piq :L.q 3.35 True ',(t.en 1. [?]~RJ Hot :3ss2rk,ble iDr n:;:> '~ wnen fr] = l, =O. 3. tJ;.[q], ~.pI 3 q:I 3 :qJ' == fEq.I 3 .q] = n-1. 0 /._J. Holds sir::ce ·:-ian [iJJ)>lg] , ~I 2 D/ 1 5. 0.43 '.'lot <:.3.:oGrtc.ble .f'e>r n / ;>, :rot ~.i:,3::;r::?.ble for n />;>, piq.pir:l:).I.qr True when [P]~ 8JrJ 1 (E] = 1, §J = o. :~~hen [PJ = l, [q] "" o. when 29 l. [q]~ [:] >[p], then [_PI 1 q] ' :: [n-l+p-qJ, [PI1 r]/' =[n-ltp-r] or fPI 1 cJ~ [?I 1rJ/' (?.I .(~r1, 1 so tllGorem ho..L(ls for this casQ. [rJ > Cg]> [PJ , s.~.: . '.c=: 6"· "bov·:: since c:; 2. 3. .:~nd r E;.re syrunetr lcal. / [CJ]> [?] or [r] >f;_:i] , Ll:en [?I;/l • pI;~r] = 0 = [ p. I 2 • qrJ r 1 [P]> [qrJ 1, [P.I 3 .qrJ ;;;; [qr]~ c;,nd cit!~t-;r [pI 25] 1 = q or 1 1 fpI 0 rJ 1 = [r], so [pI 3 c;.pI~r] = [9.r] rnakinr~ 1:he theorem hold. [Np. V ·~' [9] >[!J . The c:<:,se is the same for 3.45 piq.I:pr.I.qr True \&;hen [P] &-[:tJ, /j]~ [pVqJ I 1. [p] :>f!J /B], [pr.I 1 .qrJ1 = [rI1 qJ : : [!1-ltq-rJ 2. [PJ >[rJ /[q], 1 fPI 1cJ' = [!l-lf~-PJ< [?-1-t-q-rJ. 3. &7)] ;>~']/[SJ], [pr.IE.qrJ : I ~r.1~;.·qr] :: 0 :: [PI q]~ 2 [q] = f_pI 3 cJ'. (. [P]>{j]-;{q_J, [pr.I~0 .qr] :: [![r]; [!}I 11 cJ'= [Np] 1 1 But QJp]<.~rr]r. 1 5. [P] >f] 7§], [pr.I~.,:;_rJ ~ [1'4r.v.c] GT y ... 5 ('J:::-{( -- [ 1\··n ll.t1• 1 B.47 '7 11 1 r1 ( fi• 11 11/ .oj~L::'r• • ·~ pir.qis:I:pQ.I.rs True if fPoJ~ [rs]'. 1. [Fq]'>~s]', hrlc. tcke [PJ~{9-]. J, [s] ~ fp], Lhen ~q. I 1 . rs] ::: fI~-l+s-~ [sJ ~ jj I 30 [9r1 sJ' :: [:vi-lt s-cJ ~ frl-H-s-p] I ,/ Hence (pI 1. r.ql .....1 sJ.;fPq_.I1 .rsJ. (r]>[_s], (tj<.[P], tnen [l>q.I 1 .rs]' = (n-1-tr-p], so [?1 1 .qI 1 s]~ t"Jq.I 1 .r~' and (;>I r]' 1 ment for 2. f?]>[q] is tLe st:.:Le ;.s in lhr2 ::bove ce:..se, m<:;king proposi~ion the hold. / {pqf:>Es]' t.hen ei tn·:;or (?I 5~rJ = 0 If 3. [?oJ~ J!s]', ~]~[r], [ pl.,r.qlr,""7 (.) re) '3 [Pq°f>g.-sJ,t.sJ~fr'], 4. and [qI 4 ~ 1 ::. [ or §I 2 s] 1 =0 then [Pci.I;5 .rs]' = fr,], 1 :: fr,]. ·chen [pq.I<: .r-t]/= [;T).V.~~q]/ 1 LJfoJ 1, nc<"1{in.g D)I 4 r. qI 4 sJ ~~l~. V .1-~·i3y. The trr:.:,_t,;;.:_:nt;. i:. U>..: Sc.L:!e i":)r r.:.: .._,. = ~-ltr-p] [s]>[r]. r-. ~1 1 , e3 r, ] ~ [ r.J ;i ' · [ -~ ol / - r· · ·v.· s.J;-] I >t.!"~ , ti1en ;iq • ..1.C. :c~ - L}.~i.'. "'v .. :,c;. il( p~ but [qI :::] 5 = Dic;.v.g ~[J~,.-,.".:~·q.V.'J , ,:;-,,,_clL~, 1 1 1 ;:;_u2 .',, .,, L.·--' r:c:J :> Ld-.J r;. 1 is o.C ~ Tru.e for [?]~ >J ~. GJJ, v,l.en Uiq]~ ~JIJJ • 1 0 =(!1-lt-c;- 2] : J.. [P] -;:;.E:iJ , ::;~ti\iLg 0J<~(> [Ip]', ~Il Z... ·;ot c:.S') -•r·t :tL•i..e .i.'m:· n / -;:~ .., c'?I.J. [)] l, §] = 0. :.:.. \ot <.:.S:JCl't::.;)le f )1· .Cl/.: V'Le..'.l [p] ::: ..i., [q] ~ ·). 5. [lj > ~], mc.i.ing [kJ1> E'P] , 1 1 1 :: ~I 5 cJ = [:p.Y .q_J = ~·iq.I 5 .Np]~ 1 1 31 4.11 pEq:E:Np.E.Mq True when [P] = (q] • 1. [PJ >[qj, then [PE1 q] 1 = [n-1-rq-pJ, anci Eip.E1 .Nq] =[n-lt-q-p]. 1 [!>J <[9], then IPE1 q] : : ~-1-rp-q], and 1}'Jp.E1 .Nq] =f!.1-1-rp-q] • ( I 1 2. [!>]f-\g], then [pE 2 qJ :: 0 and f!-Jp.E 2 .N<U = O. 3. Not ass0rtable for n>B when TPJ • O, and [qJ = 1. 4. Not as:,~artable for n >2 when l.PJ =o, and 19-J =1. 1 = li-Jp.V.q]: and u~·p.E 5 .Ncir =[Np.V.qJ fP]<[qJ, then f?E 5 qJ 1 ~ lj'lq.V.p] 1, and f~·p.E 5 .Nq] =fuq.V.~. 5. fP] >[q], then [pE5q] 1 1 • 1 4.13 p.E.N(Up) True since [N(Np)J' 4.2 = [n-l-(n-1)-rp] = [P]. pEp Obviously true. 4.21 pEq.E.qEp By inspection of theorems l.6, 6.7, 6.8, 6.9, and 6.10 it is evident that [pE1 q_J 4.22 1 = [9E1 p] / {i =1,2,3,4,5). pEq.qEr:I:pEr True when [PJ = [q], or [_PJ =[r], or 13] = {!']. IPJ :: 1, ~] :: 2, f!J = O. 1. Not assertable for n> 2 when 2. If [P]]i[r] then either [PJt[q], or [q]:f[r], in which case rJ = 0 = ~E2 q.qE2 rJ making the theorem hold. 3. [PJ=f [g], L<lJ f [r], [P]f [r], then [!>E3 q.qE 3 r ] = {J?qrJ and [pE 3 r ] =[pr] thus making [}fE3 q .qE3 tJL. [pE3r] [?E 2 1 1 1 1 4. 1 , 1 1 • [P]f (q], ~J:f/}'], [p]~[r], then [PE4 q.qE4 rJ 1 =J!lp.Nq.N~" = f1p.N:J', thus making [PE4 q.qE4 r]/_:: fpE4 r ]~ 5. Not assertable for n,. 2 when [P] = o, [q] =1, frj = n-1. If we prove thB.t a proposition pE1 q (i =1,2,3,4,5) is asand [PE4 rJ' sertable for some particular i then pEjq, where the truth-values of p and q do not change as j chang .;s, is assertable for all j 32 = l,S, ••• ,5), since [PEkq] / = n-1 (k = l,:"3, .... ,5) if and only if [P] = [q]. 'Ne have utilized this f ;:ct in propositions (j 4.24,4.25,4.3,4.31,4.32,4.33,4•4,4.41 giving in each case the proof i'or pE1 q, or where the proof for pE1 q 4.24 rn.ay be i'ounci. p.E.pp [PP] r = [P] • 4.25 p.E.pVp [pVp]' = [P] • -· 4 .0 pq.E.qp (1.18). 4.31 pVq. E.qVp (l.16). 4.32 (pq)r.E.p(qr) (1.19). 4.33 (pVq)Vr.E.pV(qVr) (1.17). 4.4 p.qVr:E:pq.V.pr (l.22). ~.~l p.V.qr:E:pVq.pVr (l.23). 4.71 piq.E:p.E.pq Obviously true when [P]~[c{J • 1 1 1. [P],>&], then [pI qJ =)!1-l+q-p], an<i[?.E1 .pqJ =[n-lM-PJ 1 / 2. [r:-] >@.], then [PI 2 q]' O, and [:p.E 2 .pqJ O. = = 3. [~ >13], then [pI 3 qJ' =[q], and [p.E 3 .p<fJ = Lei]. I 4. [P] >[q], then [pl ci,] = [Jip]', snd [j.E4 .poJ = f_:l>{r2Y· 4 1 5. [PJ~l<lJ, then [pI 5 = frrp.V.q] 1, and [p.E5 .pq]' =frrp.V. qJ~ 1 iJ 1 33 4.73 q.I:p.B.pq True when ®-::-Tu.]. 1. LP]/ fg], then IP.E 1 .pq]' = E-lt-q-p]. But [q]L (!i-ltq-pJ. 2. Not asserte. ble for n ;>2 when [pJ = 2, [q] l. = 3. [p])[CU , then 4.. fi?.E3 .pqJ =§.]. }Jot assertable for n > 2 when [?] :: n-1, 5. LP]>[_q], then ~)·E5.pqJ 5.1 = n~p.V.qr. But q = 1. Np.V .. q • pq.I.pEq True when [pJ • 1. ;~. [q]. [?] / §], fpE1 qJ =[n-1-t-Q-P], [P] <[q], fpE1 q] ' = [n-1+ p-q], Not assertable for n ;> 2 3. [P]tE(l , then (pE3 qJ I but [q]~ §-l+q-p]. but [p]~fp.-l+p-q_J • when fj>J when [PJ :::. n-1, 5. [P]< {9], [PE5<1j:;-J' = [p.V.Nq] ,' ~:nd (P] > [qJ , similar to =1, &J :: 2. = fPqJ'• 4. Not assertable for n/ 2 5.32 [9] J5J =. n-2. ,1' I /£<l.l~fP.V.N<iJ. [p] <Lq] • p.I.qEr:E:pq.E.pr True if fg] = [!] • :: 1, (q] = l, }!] =o. 1. Not assertable for n > 2 when [p] 2. Not &ssertable for n:;> 2 when fp] = 1, [g] = 2, f 3. [PJ ~Jg] >f!], then f!?.I 3 .qE3 r] and (pq.E3 .pr]' ~E3r]' = ~] :: 1 .. = [r] = \!]. (cij >{P]/ ~], then [p.I 3 .qE3 rJ' = [r] 1 and [pq.E3 .pr] = [pE3r]'= [r]. Similarly we can show that hold. JP]>[:]/ l9J, and /!]> [p] -;-[SJ 34 This obviously holds, mo.kine:-. thr::; proposition hold for r,q,r ranging over all po::.;sible truth-values. 4. Not assertable for n > :2 when [P] 5. Not as.serte:,ble for n,> 2 when 5.6 =n-1, [9] =1, [r] = o. [p] = l, [q] :: 1, [r] =O. p.Nq:I.r.:E:p.I.qVr 1. 2. ~~. 4. f-; ..J. -- 1, ~] - o. Not assertablc for n>2 when [P] -- l, [q] - 1, [r] :: o. <issertable f'or n>2 when[P] ::. n-1, c<n - l, [r] -- o. N'ot c.;.ssertablf3 .ror n>2 when[p] -- n-1, [q] - l, LFJ -- o. Not tissert:·,ble for n>2 when [P] = n-l, [q] - n-2, [r] -- 1. !lot r~s ::;er table for n>2 when [PJ ':. 1, [er] ~Tot Considering now the five propositions of Lukasiewicz: p:I 1 :qI1 p, 1 ~qI 1 r.I 1 .pI1r, pI 1 q.I 1q:I 1 :qI1 p.I 1 p, pI q.I1.qI 1 p:I 1 ;qI1 p, Np.I1.Nq:I1.qI 1 p. 1 pI q.I 1 The first, second and fifth of these propositions we h&ve proven already. rl'hey are res~ectively, 2.02, 2.06 and 2.17. Consider- ing the remaining two we find that they both hold. The proofs follow: pilq.Ilq:Il~qilp.Ilp [P]~ ~], (qI 1 p .. I 1 ·rj' = [n-l+p-(n-1~ :: [P] and [pI 1 cg': [n-lt-Q-rjl[q) so that [PI q.I 1 1 [P]<(Q), (PI 1q.I 1tj]'= [9.J = @.I 1:;.I1pJ'· Thus the proposition hold(j. pI1 q.I 1 .qI1 p:I1 :qI1 p [9.] 4fp], obviously true. (<3 >[p), (qI1 p)' = ~-l+P-ct) : ~Il q.I1 .qI 1 pJ'· ciJ'= fp]• CHAP'J:SR THHEE THE ARITR\ir~'I'IC OF N-VJ.,LUS!) .L.OGIC It11Tr~ODU(;T1or;. This chapter is b"'-sed lc:rgely upon efforts to extend the results given L:. LLe j;&pers "Arithmetic of Logicn by Dr. E.T. Bell J.5 and HQn Bell's Arithmetic of Boolean Algebra." li:ost of the oper:,~tions t!mt v.'e shall use are by W.P,. Hurwitz16 • geri:::r&lizc..tions of those giveri by H~:ll .:inu Hurwitz.. However, in a few cases the obvious generaliz0tion i;.; founC:, to be defective, anJ we h&ve to seek more obscure ge.r1eralizations, ti~es, or even at operations that are not gener&liz&tions of the correspond- ing operations in ths above mentioned pc:~pers. This chepter is mermt to be merely a short exploration of the possibilities of this tOi)ic. Many continuations of.' some of the items of tr.J.s section will prob<~.bly be evident. However, lHclt of time s.na sp<:..ce prevent c) more thorough trec:~tment of this subject. Later the writer intends to more thoroughly explore the generalizations ol' the ideas in the pc.tpers or Bsll and Hurwitz, as well as attempting to s.dc..pt the results in the papers of Bern17 19 stein , Stone 18 , and Von NeumHnn to a logic of n-values. 15 • l\v. Tr<::.ns. ~· .. th ~· 0 -C..' £Q.£.•, .... ~ (1''"7) a.:. , ""ll • pp. 5°7 o..1 -o Henceforth referred to as B. 1'.' 1 o. Trc:.:ns. 17. Bernstein, non .Finite Boolean Algobras", A ~· . • tl !>2.& 1. r· 22£.·, ~··· b.J (1···a.:-..0 8) , .f ·p. 4n.,... . ··4·• · {;,,;..,-4~ Amer Called H. --- Jour. of ~· ..........__ Math., LVII (1935), pp. 736-742. 18. - Stone, Proc. of .__. .N.::i.t. Acad. ...._.... of Sciences, 20, pp. 197-202. 19. J. Von Neumann and M.B. Stone, Fux1d&menta 1Iatbe.mE.ticae, XXV (1935), pp. 353-378. 36 We :Jhe.11 s2y that we have develo 1. . ed th(:: <lr i tr.unetie of n-vhlueci logic if systl':'!.GiS 1~··:? w~.lch satisfy s::1all consult the p<:·.r)ers of Bell a.n'. Hurwitz. s.re li:.:.ted in brief on tLe fo..L.Lowing They p<ge~,. In the Doolc;an c2._se two t?ets of oper«·.tioi's, duals of eflch otl:·:r, nre given wh1eh fort> tLe arithm,:;tic of log:lc. We shall enlEcrge the number of theorems in Chapter Jne so as to cover the dui:tls of many of the theorems that c..1·;;:::i<:·r.. Howevnr, 1 t is well to remember t!lht the dual case can be worked out ecS easily as the NOIA'.i'I 1JN. We shalJ. state our postulc:;. tes for an abstract ring R"'", as in B p. 59~, in which the operations S,.P.L,G,C,D,R may be read as, respectively, sum, product, L.C ... £4., G.C.D., divid.es,,rmd residual. In Ln we use the same letters, avoiding the use oC the small l(~tters since many «.re in use as propositions. Various definitions will. be introduced as they ~;re needed. POSTtJLLTES F'Of!. S ,P ,L,G,C ,D,R. These postulates are from B and retain &s rmch as possible of the notation used there. Postulates for S and P. R-.'t- • If x,y ere any tv:o <=ilem~nts of n·i<-, xSy, xPy are uniquely 1 determined elements of R*, ~md xSy R*9• ...., -- ySx, yPx = xPy. If x,y,z c'.T8 ~ny three eler:1er.-ts of R~~' (xSy)Sz (xPy)Pz = xS(ySz), xP(ySz.) = (xPy)S(xPz). xP{yPz), 37 H*.v. D by g, There exist in H* h«'O distinct unique elements, d(rn.oted :::.nd. Z;,, ~ccL.ec'. D1 ...... $ th2 unity, zero of R ~1-, ::>u:..:h that if y is xDx, xDy. y:Jz: ::::> : xDz, = y, whore xDy is uniquely si6ni:fi.-EJ!t for u~1 :..'.h x =F ~ ~:.nd y in R*, with the 8X-:!eption th;;c.t l:.DZ:.. is s1gnifieant but indetermiu.ate in R*. P4. xGy P5 .. .xG(yGz) :: yGx, -- (xGy)Gz - :xGyGz, P6. (:;..Gy) Dx. (xGy) Jy, P7. zDx.zDy:::>:zD(xGy), PS. xLy P9. xL(yLz) plO. x:9(xLy).yD(xLy), Pl.l. xDz..yDz::>: (xLy)Dz, ::: yI;x, - xLyLz, -- (xLy)Lz = where x,y :.:,ra any ele::ients in :=t~&- a.nJ. xLy c;.nc~ xGy are uniquely Let xCy be e. rel£,tion in R;'" such th&.t, ii' ·x,y,z,w are elements in R*, xCy is u..'1.iquely signif ic:::mt in R,,,. a.nd the postulates Pl2- Pl5 are satisfied: Pl2. xCY:> yCx, Pl3. xCy.yCz::>:xGz, Pl4. xCy.zCw: ::>: (xSz)C(ySw), 38 xCy.zCw:~: (xPz)C(yPw). Pl5. ,. '). In A ~ostul~tes G is SEid to b.: .:;,ri-c::ir!etic i.!Ongruence if to the Pl2-Pl5 &re ~~ ed th~ po~t~l~tes Pl6. Pl7. where qmt Pl8. =m, t~nd q =G.C.D. of k,m; a.= a mod m. Abstraction of the resiclua.l. Let 2, b,h,m for tl:e mo!i:ent clenot<;; elemf.:mts of R*. m is uniquely determined by (g PL?-. {aD(hPb)} .[rr:.Dh '.Ihen,, 1f ur:ity in R*), ].[m =t- ,g , where h runs through a.ll 31:::.:L(ffJ.ts in :tvi-, WE: shall call m, the residu;::.,l of b with rBs1,e::.:t to a, ard v:;a sh.'.;tll write m : bRa. In addition to the sets of postulates listed by I'r. E.T. Bell, it is vve::.l to list £, set of postulates for equali ty. r.m~ In tlF:\ Bo;)le8.n G:,se ths proparties of id entity, 3ymmetry, trunsitivlty are sati,:.;fle:i by Boolean equivc::.l.e:.1c:e. This the types of eaui VE~.l'::n~e 1 '~l-1i::::h 1 ;;e ---.c::.;.'in. .~ci arc not t::·:, nsi ti ve. the threA tyres Hh .!..Ch <'"·I'e tr nsit.i.vo (p!::;2q, pEz,q, ,::~n(t PE4q), vre ;1h~~11 three. use pE 2 q ;:dnce this ;:.(..;:; the simplBst t:cuth-te;.ble of the Usi11g our earli2:r· ir1t~0 rpr.,2L~tion for tTu~h-vz-.clUGs, pE 0 q .... st<:<.tes th;.. t either p is t?:.uivalent to q, or p is not equiv5.lent Of 39 S3~fi by theorems 6.7,6.8, The S8t and 6.9. of postul;:·.tes giv-en helow c:_r~ those given by Dr. E. V. Huntington2 :) with the exception th:::c.. t it h.:.s he,:::n necessary to che!nge the operations listed in posr;ul~te D. nAn obvious set of posT,ulates for E-, b, c,... = is as follows, where are un;.lers tood to be elements 01' "L.J:i.e elf.SS K. - a.• Postulate B. If a =c. Postulrtte D. If :x =y, then f(x'"o.,b,c, •• ) =f(y,a,b,c ••• ) Postulate C. If a :: b, and b = c, then a where f(x,a,b,c, ••• ) is any element 01· r,he cL::.ss K built up fro;n tha elements ::-;_,a,b,c, ••• , by successive ap[-;lications of the op·2rgtor I and f(y,';i.,o,c,, •• ) is the element obtained from f (x,u, b, c.:, ••• ) by wr:l. ting y in plc..ce of x throughout. n p.E.,q sc:tisfies these post.ul.Lttes because of the following ~_, theorems: A: 4.2. Postul2te B: 4.::-31. Postul~te Thi.:3 is & strongHr t:hc<orem than pEq.I.qEp. Postulate C: 4.22. PostulE: te D: Sine;_.; we hPve defined operc. tions as only operating on the truth-tables of a function, if two propostions have identical truth-tables one mo.y replllce the other. But our definition of equi vcJ.ence imylies -r;hc:.t if two propositions 20. Huntington, Tr<cms. Amar. M.0.th. Soc., 35 (1833), p.880. 40 "'"~ 1.f xEnY holds ;:,, fies Post~late T~I>~ f~IT: ·_ in Ln· Cc)!• r'::i)li':Ge ;\ by y w.her:Jv2r Y occurs vri thout D. Ir:. "'or<:L.r:.g out ANl; f''.-\GLU:;T L·: L....:....:. • "i O·..:l ..L,_.,,. Hemern ber il!..P.'. ..;.... 1..0 1,_·---. . .r .e tb~ tr:Jlsf orms of t~:~ory; 7.01 xSy.=.xVy Df 7.02 xey.:.xy Df 7 .1 :xPy Hnd :xSy sc.tisfy _t)o~:tu.L.tes B;x- 11 H* 8 , P-* 3 • Proof': R*i is so. ti~fied :.>ince x.Sy aU<~~ :xPy e:.re 1.:miqu1:::ly determined by 1.2 and l.4,. xBy.E.y.3x Also (4.31), xPy .. E.yP.x R* 2 is satisfied sir.:c:e c ) S' Z •.~, ·Q ( YS Z ) ( Xu;/ t<; .Xv xP(ysz).E.(xPy)S(xPz) (4.4). '·St 0 ...v_. •. x ~.. of the sum. r:-.nd -.~:ro~me t in Ln fl!VICY•jf•J • U-1. .. J. ~ c: J..,, ·r -'-'n.• 7. ms n .... _n -! : .i..ln x....,~ Proof: Pl. ) X~J:.K_ :· .· . Df 41 inspection of th 1~ p:coof TiLL show t,, rt I mc:~y be any one of the five tyoes of impl.ici:::.tion t.L<~t ~~·e h;. ve de- fined. P~. xDy.yDx:I:xEy v y..Ey Wf: s defir::.ed ia t:':ris fc, shion. By 6.3 x divides y "y) when t" \-·,_,) [·J?[_Y]. xDy may be regarded as division in Ln. Tm~ L .. C .. I.l. AND G.G.D. I)J L.....u. • 7.04 xGy.=.xvy Dt 7.05 xLy.=.xy Df 7 7 • t,.) xGy satisfies postulat'3s P4, P5, PS anC. P7. Proof: P4. xGy.E .. yGx ""1') ( t.'"'·•D P5. xG(yGz).E.(xGy)Gz (4.30) P6. (xGy)Dx. (xGy)Dy Thi!:. 1s true since P7. zDx.zDy:I:z:C(..Gy). This may be written as xI.-.z.yI0z:I:(xVy)I0z ~ ~ ~ which is evid~ntly true. I may be anyone of tb3 defined implications. 7 .4 xLy satisfies postul2.tes ?8,F9,Pl0,Pll. Proof: PB. xLy.E.yLx P9. xL(yLz).E.(xLy)Lz PlO. xD(xLy).yD(xLy). This Jiay be w1•itten as xy.I-,.x:xyI,J.y ..., 'Nhi;h is obviously true. ~ Pll. (1.32) xDz.yDz:I: (xLy}Dz. This beco1nes Then by 7.6 and 7.4 wr-; c::'.n r~onsider th.:.:,.t xGy ?.nd xLy are transforms of the G.C.D. and .. .LI .... ..il 42 We can rewrite Pl9 in 1n in the form f .fyDx~ • l[YJ f- n-11 { pD (xPq) where x i:J allowed to rwve any truth-v~~li;.e such tt..<-<t [ pD(xPq)1 holds. If [q} L fp] rr· [0J '.L'Les•.? concitio!1s 2.r..3: t,hr:~n ~,: can assu11••::: &ny Vhlue :-.n1 1 [Y] :: n·-1. >[p] then (:J ~ I}j . So ifLtJ ::: ~J, then yDx. This leGds us to the d3finiLion 7.12 y.S.qRp Y"nen [q] < [p] , [JrJ :: n-1 ['!) )' ~], ~nd fy 1?16 or Pl7. I!J = [PJ (6.4) y satisfies the &bove c.~on<li t_u)il f'o:C' & residual. Thu.s we could call )';2 0 .g.yp0 algebraic congru- ence since they satisfy tfo~ four po~~tn.l.at1-}S given for :tlgebraic cong.:.'uence. Y.eeping the definitions thc:-t we ha.v~ made previously for the sum, rroduet, divides, residu~l-> an6 L .. C. Y., wli.en n> 2, 11' we r-.c::ept IIurwitz•s definition for congru.enee 2 2, it is 1mposRih1e to satL>.fy Pl 7. As surn.Lng tl"l<-; t X=z y mod p r_rhen x.B.zVrp and y.E.• zVqp, then if we t:;;ke 2.x.B.zVrp end I zy. E. zVqp where [~<[z] ~ l:?'-Y] 2.nd (1) (t-2) zx :::; zy mod p, 2'~ ::=y ~ f[!], then but mod qRp only when 21. See Hp. 421, (c). 22. H p. 421. 43 In ct::59 f?'·] = n-1, tLen (qHr] '::::: n-1 if C.:) ho leis. (:iR~tn-1 in general. '.I::ris le;,:::.::o u;.;; to the c•:.)nclusicn that defining l..he sum> product e.n< res ic;~.uc,1 7.07 7 .13 Proof: But by Pl9 ~,.s ';·2 hc.:.ve, V'."e sre unable Df (x-=..y mod. p) .=.xVp. E.yVp :xVp.E.yVp .S"':tisfies postulv.tes Pl.,::, ••• ,.?l~5,Pl8. Pl2, ••• ,Pl5 ar~ evident. Pl6: .:nsn If' [x)>[P] +' / f:cvp.E. t,) v1~ = o, c!1d. (PD~ / : o. If \"t:JE[P] (.:ir pDx} ;:;• _,_ vpj/th'-'!Il ['"V:') .;,,_..•-_.•LO.. J.':.. n-1, or the statement 1s true. Hurwitz 1nter~:rets ?16 to se<y: x =-0 mod p if ::cnl only i f pDx. :i sta terilent in Ln Y:::/- o. sirr,~e p eor:.·.·~'. (1.i Vl'.'.e 'l'liis fanalogue occurs in .A. spection of .xVp.E.yVp verifies P18: This is too restrictive xVp.E.XVp is otviousLy :tru2. Gi1.i;; \'\':~ :i. wl.~en pDy and can a:u-end Hurwitz ts s1:e.tement. 44 ANOTHER EXAMPLE OF THE ARITHMETIC OF 1:ri· Deserting the operations de.fined in the earlier part of this chapter, we find that we can develope an arithmetic on the This analogy with A is much subscripts of the truth-values. more striking for n;> 2 than for n elements available. = 2, when we only have two The operations which we shall use are de- fined below: 7.010 Df 7.011 Df 7.012 Df They lead us to the .following theorems: 7. 20 IP + qJ = [P + qJ I Proof: fp -t q]' ::: [P(q]Y = [P-t q_J • 7 .21 p+q.E.q+p Proof: [pt q] :: [9 r i::J • Note that we e,re retaining E from the previous section, meaning by E E.). :..., 7.22 Pt(qt-r).E.(P-t q)t-r Proof: [Pt- (q t-r))' ::. \_P-tq-tr] = l(p-t q)-t rJ. p +q t-r.=.p t (qf-r) 7 .013 Df f P] = [n-rj 1 Proof: f P] = [ (Np) ]' = [_n-1-ptl] = 0-PJ. I 7.23 1 +(-q) 7 .014 p-q. =.p 7.24 p-p.E.t0 Df Proof: (P-PJ' =. [PT n-~ : 7 .25 fpoq]' = [pq] Proof: 7.26 Proof: [n] =o. (Notice absence of prime on [pqJ) fPocfl' = [P[P(q-i.l]J'~ [_P+ pq-p] =[pq] • poq.E.qop [P<ij = [jP]. 45 7.27 po(qor).E.(poq)or Proof: Fo(qor)] = [_Pqr] = ~poq)or] 7.015 poqor.=.(poq)or 7 .28 po(q + r) .E.poq+- por 1 Proof: [po(q+ r)]' 7.29 / Df = [?[q+rJ'] =- @Cq-tr)] = fpqt Pij = [_poqt-por]' pot1 .E.p Proof: [_PotJ' = [l.p] =fp]. 7 .. 30 P-tt 0 .. E.p Proof: [P-t- t 0 ] ' 7.31 = [Pt- 0] = (P] • (-p)oq.E.-(poq) Proof: [(-p)oq]':. ~n-p)q] 7.32 = [nq-pq] = (n- f?qJ} (-p)o(-q).E.poq Proof: ~-p)o(-q}] 7 .33 1 =[Cn-p) (n-q)_J =[nz.-np-nq-r pq] =[Pq]. p +x.E.q :E:x.E.q-p Proof: Vmere J 0 .c..[x ..c...n then there is evidently only one value of x such that fpt- xJ =-[q]. rel.: tionship. But [x] = [q+n-p]satisfies this Therefore the the.or em holds .. 1z1 is a ring under oper&tions 7.34 Proof: pf-q and poq. (The following numettals refer to the postulates on p. 37 of B.L. van der Waerden: Moderne Algebra, Vol. I.) I. Pos tul<o~ tes on add.i tion. (a) (7 .. 22). (b) (7 .21). (c) (7. 33). II. Postulates on multiplication. (a) I.LI. (7.27) Distributive laws. (a) (7 .28) (b) (7.28,7.26). 46 p+q and poq are generalizations of the two operations that Stone 23 used as a basis for his ring in L2 • It is well to note that poq is a generalization of pq in L~> Many other theorems could be developed about the above operations, but those given are suffi~i,"nt to indicate a. few of their properties and also the method to be used in working out new theorems. 23. M.H. Stone, Proc. N.A.S., 21 (1935), pp. 103-105 47 CHAPTER FOUR Reprinted from the Proceedings of the NATIONAL ACADBMY OF SCIENCES, Vol. 21, No. 5, pp. 252-254. May, 1935. GE1.YERATION OF ANY N-1/ALUED LOGIC BY ONE BINARY OPERATION1 BY DONALD L. WEBB DEPARTMENT OF MATHEMATICS, CALIFORNIA INSTITUTE UF TECHNOLOGY Communicated April l, 1935 A two-valued logic was shown in 1913 by Sheffer 2 to be obtainable by the iteration of a single binary operation. It was proved in 192;) by Zylinski3 that Sheffer's function and its "dual," also introduced by Sheffer, are the only binary operations such that the iteration of either one will generate the two-valued logic of functions of two propositions. Zylinski's proof was by means of a truth table of -± columns and 16 rows, corresponding to the two possible values (a or b) which an arbitrary function <I>(x, y) can assume in a two-valued system. While theoretically applicable to an n-valued system, the method of direct inspection of the truth table is impracticable. Following another method we prove that: Any n-valued logic, where n ~ 2, can be generated by the iteration of one binary operation. Designate the n truth values which an "elementary proposition" may take in an n-valued logic by the marks ao, ai, .. ., a 11 _ 1 . For convenience, drop the a and retain only the subscript, so that our marks are now 0, 1, ... , n -1. It is to be observed that these numbers denote merely n distinct marks without any arithemetical significance. Let p· and q be any elementary propositions. Construct a truth table for two elementary propositions, p, q, of two columns and n 2 rows with then marks, 0, l, ... , n-1 by assigning in the ith row of the tabletop the value [i-1-(i-l)'J/n, and to q the value (i-1)', where j' = j mod n, j' ;::;: 0 and i = 1, 2 . . . . , n1:" Denote the statement, p has the value i, by p = i; let pf3q denote any function of p, q whose values are in the range 0, 1, ... , n-1, when p = i, q = j and i, j are in the same range; let if3j = k denote that if p = i and g = j then pf3q = k, where k is in the range. Define the stroke, "/,"function, p/q, by ilJ = 0 if i ~ j; iii= (i + 1)' (i,j = 0, 1, .. ., n-1). From this binary operation we shall generate all functions of two variables in then-valued logic. The proof will consist in exhibiting the particular general column of the p, q truth table in which the n 2 marks ts (s = 1, 2, ... , n 2) are arbitrary elements of the set 0, I, ... , n-1 as a function constructed on p, q by means the stroke /. As a notational definition we write po - p, pi - pi-lJpi-1 (i = 1, ... , n-1), in which the exponents are superscripts. Define Ri,j(p, o) to be a function of p and q such that in row j of the truth table, R;,j(p, q) = i and in every ··::r VoL. 21, 1935 MATHEMATICS: D. L. WEBB 253 other row R;,;(P, q) = 0 (i = 0, 1, ... , n- l; j = 1, 2, ... , n 2). For brevity we shall write Ri.i for Ri,1(p, r;). Similarly, any function F(p, q) of p, q will be written F. From the definition of Plq it is evident that p 1 can be obtained by operating with the cyclic substitution S = (0,1. .. , n-1) on the values of p0 • Similarly, pi can be obtained by operating on the values of p0 with the ith power, Si, of S. Hence R1,J and (Pallt- 1 1(p 0 IP 1) are equivalent for the values of a, b indicated next, which we shall write R1.j ·=· (Pallr- 1 [(p 0 1p 1), a = bt l)'J/nl ', lr=---fw- (i ±)']'.--* By means of R 1, i we obtain R;, i in terms of p, q and p\q. For, Ro,;·=· P0 IP1. R;,; ·=· CR1.j/- 2 [(R0,;)i-i (i = 2, 3, ... , n-1). Define Pa1q = p0 \qn-i, Pa2q = R1,1!Ro,i, Pa;q - N;_ 2 advff_ 2 (i = 3, 4, [i 1 (i ... , n). Mo = Ro,i. Mh = Mh- 1ah+ 1(Rh,h+ 2ah+1Rh,(h+1ln+J, Nh = Mhah+1R1,1· Then we see that pa 3q has the property Oa 3i = i; ia 30 = i (i = 0, 1, 2). Hence, by an easy mathematical induction, we prove that if Panq = Nn_ 2 a1M~_ 2 , then Oani = i; ianO = i (i = 0, 1, ... , n-1). Let T;(p, q) be any function of p, q and define T1anT2anT3 = (T1anT2)anT3 T1anT2anT3anT4 = ((T1anT2)anT3)anT4 T1anT2anT3an ... anTj = ( .. . ((T1anT2)anT3)an ... anTj· From the properties of Panq it follows that Oa,,Oan . .. anOanianOan . .. anO = i (i = 0, 1, ... , n-1). Hence we can construct any function F(p, q) of p, q having the values t; in row i of the truth table, where t; is any one of the marks 0, 1, ... , n-1, as follows: This follows immediately from Panq by inspection of the rows m the following table, · l1 anOanOan . .. anOan . .. anO = t1 Oant2anOan . .. ClnOan . .. arnO = l2 Now F(p, q) is any function defined by the truth table of the n-valued ¥ a-::. { n -[j - i - { j - i) /JI n ]' , b =f n - l j - i ;'_]' • / MATHEMATICS: D. L. WEBB 254 PROC. N. A. S. logic. Hence, if n ~ 2, any function of two propositions p, q can be constructed from p, q and pjq in the manner just indicated. To extend this result to a function of m propositions, P1, P2, ... , Pm, we make the additional definitions and take the steps indicated below. Define ir,n = i mod nr where i is any positive integer and i,,n ~ 0. Now we shall construct a truth table on Pi. ... , Pk by assigning to Ps (s = 1, 2, ... , k) the value Ps = {[(j- l) - (j - lh-s,n]/nk-s\i,,, in thejth row (j = l, 2, ... , nk). Let RL = Ru(Pi. ... , h) be defined on a truth table of Pi. ... , Pk as R7,i = i in row j, and RL = 0 elsewhere. Let SJ (R~-u) 1 (j = 1, 2, ... , nk). It is evident that a function F(P1, ... , Pk) will exist in a truth table on Pi. ... , Pk+t and will be the function obtained from the Pi. ... , h truth table by replacing each row by n 1 consecutive identical rows. This, then, increases the number of rows from nk to nk +t. Hence, we can prove RL·=c·Ri,h(sf- 1,pk) whereh = (j-1) ,n + 1, l= [j-l-(j-1) ,nl/n+ = 1 1 1(j=1,2, ... ,nk; k = 3,4, ... ,m). Having determined R~i• we proceed to construct any F(pli ... , Pm) in terms of P1, ... , Pm and the stroke, " [", by using the same procedure as for m = 2. For if l; is the value of F(Pi. ... , Pm) in row i, then it follows that Thus any function on any number of propositions Pi, ... , Pm can be constructed by means of a single binary operation, the stroke, ''I''. 1 The author is under obligations to Dr. E. T. Bell for his suggestions, aiding both in the solution of this problem and its presentation. 2 Sheffer, H. M., Trans. Amer. Math. Soc., 14, 481--488 (1913). 3 Zylinski, E., Fund. Math., 7, 203-209 (1925). , . , o<..n .·- 5:.0 DEFINITION OF POST'S GENERALIZED NEGATIVE ;\ND MAXIMUM IN TERMS OF ONE BINARY OPERATION. By DONALD L. WEBB. In 1921 Post 1 demonstrated that it was possible to construct a function for any order table in a system of m truth-values by the use of two primitive functions, ,_,mp and p V ,,, q which are generalizations of the functions~ p and p V q in the two-valued case. Recently we 2 haYe been able to show that a function on m truth-values for any order table can be constructed in terms of one binary operation, using in this demonstration a negative that corresponds to Post's ~mp, a binary operator po:,,,, q which, for the value combinations used in the interpolation formula, corresponds to Post's p Vin q, and a binary operator p I q which has no equivalent among the operators employed by Post. In the latter paper all operators were defined in terms of p I q. In this paper by redefining the truth-table of p I q we are enabled to define Post's ,_,mp and p Vm q in terms of the" I "function, thus greatly simplifying the proof that any m-valued logic can be generated by one binary operation. We find too that p I q as so defined reduces in the two-valued case to one of Sheffer's functions,3 as it evidently must. The notation used in this paper is patterned after that of Post so as to avoid confusion. Let t 0 , ti, · · ·, tm-i, where m is any positive integer, signify the m truth values that an elementary proposition can assume in a m-valued logic. Denote by p, q elementary propositions. Let p = ti signify that the proposition p has the truth-value ti. Make the two additional arithmetical definitions: min ( i, j) = i = i if J. if = i,. mod n, ( i = i < j i > j; 0, 1, 2, · · ·) ( i, j = o, 1, 2, . . . ) 0 <in< n. Hence, p I q is defined: if p = ti, q = ti ( i, j = 0, 1, · · · , m tk where k = [min(i, j) l]m. + p Iq = 1), then 1 E. L. Post, American Journal of Mathematics, vol. 43 (1921), pp. 163-185. D. L. Webb, Proceedings of the National A..caderny of Sciences, vol. 21 (1935), pp. 252-254. 3 H. M. Sheffer, Transactions of the American Mathematical Society, vol. 14 (1913), pp. 481-488. 2 13 193 194 DONALD L. WEBB. THEOREM 1. ,...._,,,,, p = p I p. + If p = t;, then p I p = tk where k = ( i 1) 111· Thus p I p cyclically permutes the truth-values t;, giving p I p and ,.......,.,,, p the same truth-table. Therefore the two are equivalent. Using Post's definition, ,_, 2 p = -'m ----:mp, etc., we may write "' THEOREM 2. p V m q = ,._,:;:-1 (p [ q). By repeating the above process we find that if p = l;, ,._,~ p = tk, where k = (i h)m (h = 2, 3, · · ·, m-1). Hence, if p = t;, q = tJ, then 1 ,_,:;:- (p I q) = tk where k = {[min(i,j) l}m m- l}m, or~= min(i, j). But p V m q 4 as given by Post has the same truth-table, making the two equivalent. . Since Post has shown that we can generate a function of any order in a m-valued truth system by means of ,._,mp and p V m q, then, by using the above theorems, we can generate a function of any order in a m-valued truth system in terms of " [ ". + + + CALIFORNIA INSTITUTE OF TECHNOLOOY. 4 This is called a maximum since the higher truth-value has the smaller subscript.