实现使用K-map简化布尔表达式时对单元格进行分组的功能

Question

为了使用卡诺图实现 5 变量布尔表达式的简化，我编写了一个 JavaScript 函数来对单元格进行分组（其输入是指定最小项的整数列表）：

function groupMinterms(minterms) {
  // Define the size of the 5-variable K-map (32 cells)
  const mapSize = 32;

  // Create an empty array to store groups
  const groups = [];

  // Validate input (check for valid minterms within K-map range)
  for (const minterm of minterms) {
    if (minterm < 0 || minterm >= mapSize) {
      throw new Error(`Invalid minterm: ${minterm}. Must be between 0 and ${mapSize - 1}`);
    }
  }

  // Create a helper function to check if two minterms can be grouped
  function canGroup(m1, m2) {
    const diff = m1 ^ m2; // XOR operation to find the difference between minterms
    return (diff & (diff + 1)) === 0; // Check if only one bit differs (power of 2)
  }

  // Loop through each minterm
  for (let i = 0; i < minterms.length; i++) {
    const minterm1 = minterms[i];
    let foundGroup = false;

    // Check for wrapping around groups
    for (let j = 0; j < groups.length; j++) {
      const firstMinterm = groups[j][0];
      const lastMinterm = groups[j][groups[j].length - 1];

      if ((canGroup(minterm1, firstMinterm) && (minterm1 + 1) % mapSize === firstMinterm) ||
          (canGroup(minterm1, lastMinterm) && (lastMinterm + 1) % mapSize === minterm1)) {
        groups[j].push(minterm1);
        foundGroup = true;
        break;
      }
    }

    // Check existing groups without wrapping
    if (!foundGroup) {
      for (let j = 0; j < groups.length; j++) {
        if (groups[j].some(m => canGroup(m, minterm1))) {
          groups[j].push(minterm1);
          foundGroup = true;
          break;
        }
      }
    }

    // If not added to an existing group, create a new group
    if (!foundGroup) {
      groups.push([minterm1]);
    }
  }

  return groups;
}

// Example usage with the corrected output
const minterms = [1, 2, 5, 7, 11, 19];
const groups = groupMinterms(minterms);

console.log("Minterms:", minterms);
console.log("Groups:", groups);

但是当我运行代码时，minterms = [1, 2, 5, 7, 11, 19]，我收到输出（单元格组）

Groups: [ [ 1, 2, 5 ], [ 7 ], [ 11 ], [ 19 ] ]

这和我使用在线工具得到的结果不一样，应该是

Groups: [[1, 5], [5, 7], [2], [11], [19]]

我的代码中有什么不准确的地方？提前致谢

Answer 1

K 图（卡诺维奇图）中的块始终包含 2、4、8、... 个单元，即两个单元的整数次方。第一步，将两个相邻单元合并以形成 2 单元块。这对应于具有

n-1

变量的小项。由于合并，一个变量消失了。

两个在一个可变位置不同的 2-cell 块相应地合并为 1 个 4-cell 块。等等...

您的组逻辑有缺陷，因为它允许并生成具有其他单元格编号的组。例如您的小组

[1, 2, 5]

。单元格

1

和

2

无法合并，因为它们的两个位置不同。只有

1

和

5

只有一个位置不同。

您在网上找到的解决方案是正确的。您可以在这里说服自己：