Reducible Boolean functions.

DOI10.1090/S0002-9904-1936-06285-3MaRDI QIDQ2605675zbMATH OpenWikidataFDO

Authors J. C. C. McKinsey

Publication date 1936

Published in Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/S0002-9904-1936-06285-3

Review text

Das Symbol \(\boldsymbol\oplus\) bedeute jede der vier Verknüpfungen \(\times\), \(+\), \(\bigcirc \), \(\bigtriangleup\) (vgl. die vorstehend besprochene Arbeit von \textit{B. A. Bernstein}) in einer \textit{Boole}schen Algebra. Eine notwendige und hinreichende Bedingung für das Zerfallen einer \textit{Boole}schen Funktion \(f\) in zwei \textit{Boole}sche Funktionen \(g\), \(h\) bezüglich \(\boldsymbol\oplus\), \[ f(x_1,\dots,x_n) = g(x_1,\dots,x_p)\boldsymbol\oplus h(x_q,\dots,x_n)\qquad (q\leqq p + 1), \] ist das Bestehen der Identität \[ \begin{gathered} f(x_1,\dots, x_{q-1}, z_q,\dots, z_p, x_{p+1},\dots, x_n)\boldsymbol\oplus f(y_1,\dots, y_{q-1}, z_q,\dots, z_p, y_{p+1},\dots, y_n)=\\ f(x_1,\dots, x_{q-1}, z_q,\dots, z_p, y_{p+1},\dots, y_n)\boldsymbol\oplus f(y_1,\dots, y_{q-1}, z_q,\dots, z_p, x_{p+1},\dots, x_n).\end{gathered} \] Eine entsprechende Bedingung gibt Verf. auch dafür an, daß \(f\) auf folgende Weise in drei Funktionen zerfällt: \[ \displaylines{\rlap{\qquad\!(*)} \hfill f(x_1,\dots,x_n)=g_1(x_1,\dots,x_p)\boldsymbol\oplus g_2(x_{p+1},\dots,x_q)\boldsymbol\oplus g_3(x_{q+1},\dots,x_n). \hfill} \] Schließlich folgt aus diesen beiden Sätzen: Wenn \(f\) auf zwei verschiedene Weisen zerfällt, \[ \begin{gathered} f(x_1,\dots, x_n)=h_1(x_1,\dots, x_p)\boldsymbol\oplus h_2(x_{p+1},\dots, x_n)\\ \;=h_3(x_1,\dots,x_q)\boldsymbol\oplus h_4(x_{q+1},\dots, x_n)\qquad(p<q),\end{gathered} \] so gibt es drei Funktionen \(g_1\), \(g_{2}\), \(g_{3}\), so daß (*) gilt. (III 5 B.)

This page was built for publication: Reducible Boolean functions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2605675)