我正在用C#为一个项目创建一个布尔代数简化器。为了简化布尔代数表达式,我采取以下方法:
1) 简化每个变量上的 NOT,并在适用的情况下应用 De Morgan 定律
2) 简化表达式中的括号(如果有的话)
3) 展开可以展开的表达式中的任何括号
4) 简化表达式中的每个项。例如,对于表达式 A+B•A,B•A 将是一个项。将这些变量应用 NOT,并在与数组中每个变量的索引相对应的列表中表示。例如,Nots [0] 包含表达式中第一个变量上的 NOT 的数量。在程序的这一点上,没有通过 NOT 门连接任何变量。
5) 在可能的情况下进行因式分解
6) 如果表达式无法因式分解,则已经简化。如果已经因式分解,则从步骤 2 开始重复直到当表达式通过这些步骤时不再改变。
我无法创建适用于所有/大多数情况的因式分解子程序。我已经创建了一个因式分解子程序并将其放在下面。我尝试让它仅扩展最多两个括号,并且这些括号不包含括号,以使我的子程序更容易创建。然而,对我来说创建这样的算法是相当困难的。
如果有人能够提供一些伪代码,或者解释如何创建这样的算法,指出我的代码中的错误,甚至提供一些我可以分析和理解的代码,我将非常感激。下面显示了代码:(警告:由于缺乏经验,它是可怕的编程。)
private bool Factorise(ref List<string> Expression, ref List<int> NOTsNew)
{
string PreviousExpression = convertexpressionlisttostring(Expression);
// loop and get each indiviual variable - no duplicates
// loop through expression for every variable and see if it occurs more than once
List<List<string>> itemsthatappearwithinexpression = new List<List<string>>();
List<string> charactersthatappearwithinexpression = new List<string>();
List<string> Notsofcharactersthathappearwithinexpression = new List<string>();
List<string> numberoftimescharacterappears = new List<string>();
List<string> positionofitemswithinexpression = new List<string>();
itemsthatappearwithinexpression.Add(charactersthatappearwithinexpression);
itemsthatappearwithinexpression.Add(Notsofcharactersthathappearwithinexpression);
itemsthatappearwithinexpression.Add(positionofitemswithinexpression);
itemsthatappearwithinexpression.Add(numberoftimescharacterappears);
for (int i = 0; i < Expression.Count; i++)
{
if (Expression[i] != "•" && Expression[i] != "+" && Expression[i] != "⊕")
{
if (itemsthatappearwithinexpression[0].Count == 0)
{
itemsthatappearwithinexpression[0].Add(Expression[i]);
itemsthatappearwithinexpression[1].Add(NOTsNew[i].ToString());
itemsthatappearwithinexpression[2].Add(i.ToString());
}
bool matched = false;
for (int y = 0; y < itemsthatappearwithinexpression[0].Count; y++)
{
if (itemsthatappearwithinexpression[0][y] == Expression[i] && itemsthatappearwithinexpression[1][y] == NOTsNew[i].ToString())
{
matched = true;
break;
}
}
if (!matched)
{
itemsthatappearwithinexpression[0].Add(Expression[i]);
itemsthatappearwithinexpression[1].Add(NOTsNew[i].ToString());
itemsthatappearwithinexpression[2].Add(i.ToString());
}
}
}
for (int x = 0; x < itemsthatappearwithinexpression[0].Count; x++)
{
int occurances = 1;
for (int c = 0; c < Expression.Count; c++)
{
int position = int.Parse(itemsthatappearwithinexpression[2][x]);
if (NOTsNew[c] == NOTsNew[position] && c != position && itemsthatappearwithinexpression[0][x] == Expression[c])
{
occurances++;
}
}
itemsthatappearwithinexpression[3].Add(occurances.ToString());
}
for (int i = 0; i < itemsthatappearwithinexpression[0].Count; i++)
{
if (i < itemsthatappearwithinexpression[0].Count - 1)
{
if (itemsthatappearwithinexpression[3][i] == itemsthatappearwithinexpression[3][i + 1] && int.Parse(itemsthatappearwithinexpression[2][i]) == (int.Parse(itemsthatappearwithinexpression[2][i + 1]) - 2))
{
itemsthatappearwithinexpression[0][i] = itemsthatappearwithinexpression[0][i].ToString() + itemsthatappearwithinexpression[0][i + 1].ToString(); // chars, nots, position, occurances
itemsthatappearwithinexpression[1][i] = itemsthatappearwithinexpression[1][i].ToString() + itemsthatappearwithinexpression[1][i + 1].ToString(); // Nots[0]
itemsthatappearwithinexpression[0].RemoveAt(i + 1);
itemsthatappearwithinexpression[1].RemoveAt(i + 1);
itemsthatappearwithinexpression[2].RemoveAt(i + 1);
itemsthatappearwithinexpression[3].RemoveAt(i + 1);
}
}
}
List<int> positionsoffirstcharinmatches = new List<int>();
string factorisedexpression = "";
bool donextthing = false;
List<int> NOTsinfactorisation = new List<int>();
for (int d = 0; d < itemsthatappearwithinexpression[0].Count; d++)
{
int counter = 0;
bool singularexpansion = false;
if (itemsthatappearwithinexpression[0][d].Length == 1)
{
singularexpansion = true;
}
if (int.Parse(itemsthatappearwithinexpression[3][d]) > 1)
{
for (int i = 0; i < Expression.Count; i++)
{
bool Continue = false;
if (singularexpansion && Expression[i] == itemsthatappearwithinexpression[0][d] && NOTsNew[i] == NOTsNew[int.Parse(itemsthatappearwithinexpression[2][d])])
{
Continue = true;
}
if (i+2 <= Expression.Count-1 && !singularexpansion && Expression[i] == itemsthatappearwithinexpression[0][d][0].ToString() && Expression[i+2] == itemsthatappearwithinexpression[0][d][1].ToString() && NOTsNew[i] == int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()) && NOTsNew[i+2] == int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()))
{
Continue = true;
}
donextthing = false;
if (Continue)
{
if (i != 0)
{
if (Expression[i - 1] == "•")
{
positionsoffirstcharinmatches.Add(i - 2);
if (counter == 0)
{
if (singularexpansion)
{
factorisedexpression += itemsthatappearwithinexpression[0][d] + "•(" + Expression[i - 2] + Expression[i - 3];
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d]));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(NOTsNew[i - 2]);
NOTsinfactorisation.Add(0);
counter++;
}
else
{
positionsoffirstcharinmatches.Add(i);
factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + Expression[i - 2] + Expression[i - 3];
//string NOTsOfAdjacentVariables = itemsthatappearwithinexpression[1][d];
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(NOTsNew[i - 2]);
NOTsinfactorisation.Add(0);
counter++;
}
}
else
{
if (i >= Expression.Count - 3)
{
factorisedexpression += Expression[i - 2] + ")";
NOTsinfactorisation.Add(NOTsNew[i - 2]);
NOTsinfactorisation.Add(0);
}
else
{
factorisedexpression += Expression[i + 3] + Expression[i + 2];
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(NOTsNew[i + 2]);
}
}
}
else
{
donextthing = true;
}
}
else
{
donextthing = true;
}
if (donextthing)
{
positionsoffirstcharinmatches.Add(i);
if (counter == 0)
{
if (singularexpansion)
{
positionsoffirstcharinmatches.Add(i + 2);
factorisedexpression += itemsthatappearwithinexpression[0][d] + "•(" + Expression[i + 2] + Expression[i + 3];
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d]));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(NOTsNew[i + 2]);
NOTsinfactorisation.Add(0);
counter++;
}
else
{
bool useone = false;
if (Expression[i]+Expression[i+2] == itemsthatappearwithinexpression[0][d] || Expression[i + 2] + Expression[i] == itemsthatappearwithinexpression[0][d])
{
useone = true;
}
positionsoffirstcharinmatches.Add(i+2);
if (useone)
{
factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + "1" + Expression[i + 3];
}
else
{
factorisedexpression += itemsthatappearwithinexpression[0][d][0] + "•" + itemsthatappearwithinexpression[0][d][1] + "•(" + Expression[i + 2] + Expression[i + 3];
}
//string NOTsOfAdjacentVariables = itemsthatappearwithinexpression[1][d];
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][0].ToString()));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(int.Parse(itemsthatappearwithinexpression[1][d][1].ToString()));
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(0);
if (useone)
{
NOTsinfactorisation.Add(0);
}
else
{
NOTsinfactorisation.Add(NOTsNew[i + 2]);
}
NOTsinfactorisation.Add(0);
counter++;
}
}
else
{
if (i == Expression.Count - 3)
{
if (Expression[i]+Expression[i+2] == itemsthatappearwithinexpression[0][d] || Expression[i + 2] + Expression[i] == itemsthatappearwithinexpression[0][d])
{
factorisedexpression += "1" + ")";
NOTsinfactorisation.Add(0);
}
else
{
factorisedexpression += Expression[i + 2] + ")";
NOTsinfactorisation.Add(NOTsNew[i + 2]);
}
NOTsinfactorisation.Add(0);
}
else
{
factorisedexpression += Expression[i + 3] + Expression[i + 2];
NOTsinfactorisation.Add(0);
NOTsinfactorisation.Add(NOTsNew[i + 2]);
}
}
}
}
}
}
else
{
}
}
// character • () --> A•B + A•C Xor A•D = A•(B+C XOR D) - find every instance of the object - get the operator before the object and place the o
//int n = 5; //Expression
positionsoffirstcharinmatches = intbubblesorthightolow(positionsoffirstcharinmatches);
List<int> PositionstoremovefromExpression = new List<int>();
for (int i = 0; i < positionsoffirstcharinmatches.Count; i++)
{
if (positionsoffirstcharinmatches[i] < Expression.Count - 3)
{
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 3);
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 2);
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 1);
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i]);
}
else
{
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 2);
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i] + 1);
PositionstoremovefromExpression.Add(positionsoffirstcharinmatches[i]);
}
}
PositionstoremovefromExpression = intbubblesorthightolow(PositionstoremovefromExpression);
PositionstoremovefromExpression = PositionstoremovefromExpression.Distinct().ToList();
for (int i = 0; i < PositionstoremovefromExpression.Count; i++)
{
NOTsNew.RemoveAt(PositionstoremovefromExpression[i]);
Expression.RemoveAt(PositionstoremovefromExpression[i]); // A • B + C • A
}
for (int i = 0; i < factorisedexpression.Length; i++)
{
try
{
Expression[PositionstoremovefromExpression[PositionstoremovefromExpression.Count - 1] + i] = factorisedexpression[i].ToString();
NOTsNew[PositionstoremovefromExpression[PositionstoremovefromExpression.Count - 1] + i] = NOTsinfactorisation[i];
}
catch (Exception)
{
Expression.Add(factorisedexpression[i].ToString());
NOTsNew.Add(NOTsinfactorisation[i]);
}
}
if (PreviousExpression == convertexpressionlisttostring(Expression))
{
return false;
}
else
{
return true;
}
}
列表表达式是一个字符串列表,其中包含表达式中的每个字符。例如,对于 A + B,列表将是 ["A","+","B"]。NOTsNew 列表是前面提到的列表,其中包含每个变量上的 NOT。只要我花时间理解它,并在必要时进行调整并提及这一点,我就可以在我的项目中使用他人的代码,因此我不会作弊。 P.S. 上面的一些代码可以放入子程序中,但我目前正在尝试获得一些可工作的代码,然后将其缩短为单独的子程序。
Expression
?你没有在任何地方对它进行赋值。修改列表并不等同于覆盖变量。 - Jeroen van Langen