我有一个考试题我没能解决：
我需要构建一个接收 4 位数字的数字逻辑电路，true如果数字是，则返回0，7或14。我只有一个XOR门（2 个输入）、一个NOR（3 个输入）、一个NAND（2 个输入）和一个 3-to-8 解码器。
我认为这个问题是无法解决的，我没有找到任何可以做到这一点的组合。知道如何解决吗？
数字逻辑电路 - 试题
电器工程
数字逻辑
电路分析
逻辑门
布尔代数
2022-01-03 05:03:53
4个回答
我用 C# 编写了一个算法，它尝试了这些Nor 3->1 Xor 2->1 Nand 2->1和Decoder 3->8.
在运行750 万年2 小时后，它返回42 False。我相信这证明了这个问题没有答案，因为该算法检查了所有可能的组合。:)
我被要求描述它，所以下一部分是部分代码的解释。TL;DR - 你可以跳到最后的代码:)
让我们谈谈输入线，它们有 0 或 1 个状态，并且对于每个可能的输入（0 到 15），它们具有不同的值：
对于第一行，它看起来像： 0 1 0 1 0 1 ... 第二个是： 0 0 1 1 0 0 1 1... 第三个： 0 0 0 0 1 1 1 1 .... 像二进制数数......你明白了：P
所以我创建了一个对象，代表他每个状态的每一行：
class BitLine{
bool[] IsActiveWhenInputIs = new bool[16];
}
正如它所说的 bitLine.IsActiveWhenInputIs[5] 返回输入为 5 时该行是否处于活动状态。
这是一个完全创建输入行的代码：
var bitLineList = new BitLine[6]; // initialize new array of bitLines
for (int i = 0; i < 6; i++) bitLineList [i] = new BitLine(); // initialize each bitLine
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 4; j++)
{
int checker = 1 << j; // check whether the j-th bit is activated in the binary representation of the number.
bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0); // if it's active, the AND result will be none zero, and so the return value will be true - which is what we need :D
}
}
我们还将创建“始终为真”和“始终为假”的位线 - 以提供恒定的“0”输入或“1”输入。
for (int i = 0; i < 16; i++){
bitLineList[4].IsActiveWhenInputIs[i] = false;
bitLineList[5].IsActiveWhenInputIs[i] = true;
}
现在，如果您注意到，我们正在寻找的实际上是一个特定的位线，当输入为 0、7、14 时为真。让我们在我们的类中表示它：
var neededBitLine = new BitLine();
for (int i = 0; i < 16; i++){
neededBitLine.IsActiveWhenInputIs[i] = ((i % 7) == 0); // be true for any number that is devideble by 7 (0,7,14)
}
这让事情变得非常简单：我们实际上正在寻找一种从输入位线“伪造”这个 requiredBitLine 的方法（这就是我向程序表示我想要输出的方式）。
现在，这就是我们继续进行的方式：每次我们在我们的位线上使用一些逻辑元素，比如Xor, Nor，Nand甚至Decoder，我们实际上是在创建一个新的位线\s。我们知道从 0 到 15 的每个可能输入中每一行的值，因此我们也可以计算每个可能输入中的新 bitLine\s 值！
Nand Nor 和 Xor 都很简单：
void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
}
}
void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
}
}
void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
}
}
对于每个可能的输入，它代表新的 BitLine 将如何操作。
处理解码器有点棘手，但想法是“如果输入的位表示二进制数 x，那么第 x 输出位线将为真，而所有其他位线将为假。不像其他函数，这个得到一个位线数组，并在数组中添加 8 个新的位线。
void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
{
for (int optionNumber = 0; optionNumber < 8; optionNumber++)
{
for (var i = 0; i < 16; i++)
{
int sum = 0;
if (b1.IsActiveWhenInputIs[i]) sum += 4;
if (b2.IsActiveWhenInputIs[i]) sum += 2;
if (b3.IsActiveWhenInputIs[i]) sum += 1;
lines[listOriginalLength+optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
}
}
}
现在我们有了所有的基本元素，让我们来谈谈算法：
我们将做一个递归算法，在每个深度它会尝试在当前可用的位线上使用另一个元素（nor\nand\xor\decoder），然后将元素设置为下一个递归深度不可用。每当我们到达底部并且没有更多元素可以使用时，我们将检查是否有我们正在寻找的位线。
此代码在任何给定时间检查当前行组是否包含我们正在查找的行：
bool CheckIfSolutionExist(List<BitLine> lines, int linesLength BitLine neededLine)
{
for(int i = 0; i<linesLength; i++){
if (lines[i].CheckEquals(neededLine))
{
return true;
}
}
return false;
}
这是它用来检查两行是否相等的函数：
bool CheckEquals(BitLine other)
{
for (var i = 0; i < 16; i++)
{
if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
{
return false;
}
}
return true;
}
好的，现在对于主要部分，这是主要算法：
bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if ((!nand) && (!nor) && (!xor) && (!decoder))
{
return CheckIfSolutionExist(lines, listLength, neededLine);
}
else
{
if (HandleNand(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleNor(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleXor(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleDecoder(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
return false;
}
}
此函数接收可用位线列表、列表长度、表示每个元素当前是否可用的布尔值（xor/nor/nand/decoder）和表示我们正在搜索的位线的位线。
在每个阶段，它都会检查我们是否还有其他元素要使用，如果没有 - 它会检查我们是否归档了所需的位线。
如果我们还有更多元素，那么对于每个元素，它都会调用一个函数，该函数应该使用这些元素创建新的位线，然后调用下一个递归深度。
下一个处理函数都非常简单，它们可以翻译为“从可用位线中选择 2\3，并使用相关元素组合它们。然后调用递归的下一个深度，只是这次它不会包含这个元素！”。
这些是功能：
bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nand)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Nand(lines[i], lines[j],lines[listLength]);
if (Solve(lines,listLength+1, false, nor, xor, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleXor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (xor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Xor(lines[i], lines[j],lines[listLength]);
if (Solve(lines,listLength+1, nand, nor, false, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Nor(lines[i], lines[j], lines[k],lines[listLength]);
if (Solve(lines,listLength+1, nand, false, xor, decoder, neededLine))
{
return true;
}
}
}
}
}
return false;
}
bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (decoder)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Decoder(lines[i], lines[j], lines[k],lines,listLength);
if (Solve(lines,listLength+8, nand, nor, xor, false, neededLine))
{
return true;
}
}
}
}
}
return false;
}
就是这样，我们只需用我们正在寻找的所需线路调用此函数，它会检查电气部件的所有可能组合，以检查它们是否可以以这样的方式组合，最终将成为一条线路输出所需的值。
*注意我一直使用同一个列表，所以我不需要一直创建新的位线实例。出于这个原因，我给它一个 200 的缓冲区。
这是完整的程序：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp2
{
public class BitLine
{
public bool[] IsActiveWhenInputIs = new bool[16];
public static void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
}
}
public static void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
}
}
public static void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
}
}
public static void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
{
for (int optionNumber = 0; optionNumber < 8; optionNumber++)
{
for (var i = 0; i < 16; i++)
{
int sum = 0;
if (b1.IsActiveWhenInputIs[i]) sum += 4;
if (b2.IsActiveWhenInputIs[i]) sum += 2;
if (b3.IsActiveWhenInputIs[i]) sum += 1;
lines[listOriginalLength + optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
}
}
}
public bool CheckEquals(BitLine other)
{
for (var i = 0; i < 16; i++)
{
if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
{
return false;
}
}
return true;
}
}
public class Solver
{
bool CheckIfSolutionExist(List<BitLine> lines, int linesLength, BitLine neededLine)
{
for (int i = 0; i < linesLength; i++)
{
if (lines[i].CheckEquals(neededLine))
{
return true;
}
}
return false;
}
bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nand)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Nand(lines[i], lines[j], lines[listLength]);
if (Solve(lines, listLength + 1, false, nor, xor, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleXor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (xor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Xor(lines[i], lines[j], lines[listLength]);
if (Solve(lines, listLength + 1, nand, nor, false, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Nor(lines[i], lines[j], lines[k], lines[listLength]);
if (Solve(lines, listLength + 1, nand, false, xor, decoder, neededLine))
{
return true;
}
}
}
}
}
return false;
}
bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (decoder)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Decoder(lines[i], lines[j], lines[k], lines, listLength);
if (Solve(lines, listLength + 8, nand, nor, xor, false, neededLine))
{
return true;
}
}
}
}
}
return false;
}
public bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if ((!nand) && (!nor) && (!xor) && (!decoder))
{
return CheckIfSolutionExist(lines, listLength, neededLine);
}
else
{
if (HandleNand(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleNor(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleXor(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleDecoder(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
return false;
}
}
}
class Program
{
public static void Main(string[] args)
{
List<BitLine> list = new List<BitLine>();
var bitLineList = new BitLine[200];
for (int i = 0; i < 200; i++) bitLineList[i] = new BitLine();
// set input bit:
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 4; j++)
{
int checker = 1 << j;
bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0);
}
}
// set zero and one constant bits:
for (int i = 0; i < 16; i++)
{
bitLineList[4].IsActiveWhenInputIs[i] = false;
bitLineList[5].IsActiveWhenInputIs[i] = true;
}
list.AddRange(bitLineList);
var neededBitLine = new BitLine();
for (int i = 0; i < 16; i++)
{
neededBitLine.IsActiveWhenInputIs[i] = (i%7==0); // be true for any number that is devideble by 7 (0,7,14)
}
var solver = new Solver();
Console.WriteLine(solver.Solve(list, 6, true, true, true, true, neededBitLine));
Console.ReadKey();
}
}
}
希望这次是一个有效的解释：P
这是一个非答案，丢弃最明显的解决方案。
我将按其权重对位进行编号：\$ b_1 \$、\$ b_2 \$、\$ b_4 \$ 和 \$ b_8 \$。
由于位 \$ b_2 \$ 和 \$ b_4 \$ 在所有有效数字中都相等，我们可以实现逻辑表达式：
$$ ( \text{nor} ~ \{ x=0, x=3, x=6 \} ) ~ \text{nand} ~ ( b_2 ~ \text{xor} ~ b_4 ) $$
其中 x 是 { \$ b_1 \$, \$ b_4 \$, \$ b_8 \$ }，使用 3-8 解码器实现。
但是，先前表达式的简化为：
$$ ( x=0 ~ \text{or} ~ x=3 ~ \text{or} ~ x=6 ) ~ \text{or} ~ ( b_2 = b_4 ) $$
这不是预期的：
$$ ( x=0 ~ \text{or} ~ x=3 ~ \text{or} ~ x=6 ) ~ \text{and} ~ ( b_2 = b_4 ) $$
出于这个原因，我认为问题中可能存在错误，将“nand”门作为“nor”门。
您的问题的有效答案是任何始终返回 true 的电路。因为如果输入数字是 0、7 或 14，它也会返回 true。
我认为这个问题应该明确要求一个电路，如果输入数字是 0、7 或 14，则输出为真。否则输出假。
这是可行的。作为提示，对于所有这些位模式，中间两位都是相等的，因此对它们进行异或运算将产生 0，然后可以与其他两位一起作为解码器的输入。其余的门应用于三个解码器输出以提供正确的单比特输出。
其它你可能感兴趣的问题