...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete mathematics and applications >Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms
【24h】

Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms

机译：极化多项式形式的布尔代数函数系统和三值逻辑函数系统的复杂性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A polarized polynomial form (PPF) (modulo k) is a modulo k sum of products of variables X_1,...,X_n or their Post negations, where the number of negations of each variable is determined by the polarization vector of the PPF. The length of a PPF is the number of its pairwise distinct summands. The length of a function f(X_1,...,X_n) of k-valued logic in the class of PPFs is the minimum length among all PPFs realizing the function. The paper presents a sequence of symmetric functions f_n (x_1,...,x_n) of three-valued logic such that the length of each function f_n in the class of PPFs is not less than [3~(n+1)/4], where [a denotes the greatest integer less or equal to the number a. The complexity of a system of PPFs sharing the same polarization vector is the number of pairwise distinct summands entering into all of these PPFs. The complexity L_k~(PPF) (F) of a system F = {f_1,...,f_m} of functions of k-valued logic depending on variables x_1,...,x_n in the class of PPFs is the minimum complexity among all systems of PPFs {p_1,...,p_m} such that all PPFs P_1,..., P_m share the same polarization vector and the PPF p_j realizes the function f_j j= 1,...,m. Let L_k ~(PPF) (m,n) = max L_k~(PPF) (F), where F runs through all systems consisting of m functions of k-valued logic depending on variables x_1,..., x_n. For prime values of k it is easy to derive the estimate L_k~(PPF) (m,n) ≤ k~n. In this paper it is shown that L_2~(PPF) (m,n) = 2~n and L_3~(PPF) (m,n) = 3~n for all m ≥ 2, n = 1，2，... Moreover, it is demonstrated that the estimates remain valid when consideration is restricted to systems of symmetric functions only.
机译：极化多项式（PPF）（模k）是变量X_1，...，X_n或它们的后求反的乘积的模k和，其中每个变量的求反次数由PPF的极化矢量确定。 PPF的长度是其成对的不同求和数。 PPF类中的k值逻辑函数f（X_1，...，X_n）的长度是实现该功能的所有PPF中的最小长度。本文提出了三值逻辑的对称函数f_n（x_1，...，x_n）的序列，使得PPF类中每个函数f_n的长度不小于[3〜（n + 1）/ 4 ]，其中[a 表示小于或等于数字a的最大整数。共享相同极化矢量的PPF系统的复杂性是进入所有这些PPF的成对不同求和数。根据PPF类中变量x_1，...，x_n的k值逻辑函数的系统F = {f_1，...，f_m}的系统复杂度L_k〜（PPF）（F）是最小复杂度PPF {p_1，...，p_m}的所有系统中，使得所有PPF P_1，...，P_m共享相同的极化矢量，PPF p_j实现函数f_j j = 1，...，m。令L_k〜（PPF）（m，n）=最大L_k〜（PPF）（F），其中F遍历由m个具有k值逻辑的m个函数组成的所有系统，具体取决于变量x_1，...，x_n。对于k的素值，很容易得出估计值L_k〜（PPF）（m，n）≤k〜n。本文表明，对于所有m≥2，n = 1，2，。，L_2〜（PPF）（m，n）= 2〜n，L_3〜（PPF）（m，n）= 3〜n。而且，证明了当考虑仅限于对称函数系统时，估计仍然有效。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号