Минимизация булевых функций

 

Консольная программа, реализующая 2 алгоритма:

1. Простой рекурсивный алгоритм построения Совершенной ДНФ

2. Построение Сокращённой ДНФ по алгоритму Блейка-Порецкого

Итак, пост достаточно большой. Основное внимание, однако, я постараюсь уделить конкретно реализации алгоритма на C++.

Для реализации я выбрал следующую тактику. Функциональное программирование с выносом функций и объявлений в заголовочный файл, а также использование поля имён для доступа к одному массиву (передавать по ссылке я ещё не умел).

Необходимо было: 

1. реализовать чтение введенных векторов и их запись в массив

2. обеспечить все функции доступом к этим массивам

3. при построении СокрДНФ удалять повторяющиеся точки

4. реализовать алгоритм Блейка-Порецкого

По структуре программа разбита на

файл MainCode.cpp - выводит то, что мы видим в консоли

файл MainHead.h - содержит наше поле имён namespace names

файл Functions.h - реализует функции для Блейка-Порецкого

файл ComDNF.h - реализует некоторые функции для СовДНФ

Cсылка для загрузки проекта Microsoft Visual Studio C++

Некоторые функции:

// построение списка троичных векторов
// возвращает строку - изначально введёную ДНФ
string Read (int strokes, int Vars)
{
    cout << "        Пожалуйста, введите все конъюнкции из ДНФ" << endl << endl;
    SetColor (Green);
    string str, dnf; bool minus = false;
    for (int j=0; j<strokes; j++) // этот цикл - количество первичных троичных векторов
    {
        cout << "        "; cin >> str;
        if (dnf.length() > 0) {dnf.insert(dnf.length(), " v ");} dnf.insert(dnf.length(), str);

        FormCompleteDNF (str, Vars);

        for (int i=0; i<str.length(); i++) // этот цикл - количество символов в каждой элем. конъюнкции
        {
            if (str.at(i) == '-') {minus = true;}
            else 
            {
                if (str.at(i) == 'a') { if(minus) {ShortDNF[j][0] = 0; minus = false;} 
                else ShortDNF[j][0] = 1; } else
                if (str.at(i) == 'b') { if(minus) {ShortDNF[j][1] = 0; minus = false;} 
                else ShortDNF[j][1] = 1; } else
                if (str.at(i) == 'c') { if(minus) {ShortDNF[j][2] = 0; minus = false;} 
                else ShortDNF[j][2] = 1; } else        
                if (str.at(i) == 'd') { if(minus) {ShortDNF[j][3] = 0; minus = false;} 
                else ShortDNF[j][3] = 1; } else
                if (str.at(i) == 'e') { if(minus) {ShortDNF[j][4] = 0; minus = false;} 
                else ShortDNF[j][4] = 1; } else
                {
                    SetColor (LightRed);
                    cout << endl << "        Неверный символ! Перезагрузитесь." << endl; 
                    SetColor (LightGray);
                }
            }

        }
    }
    SetColor (LightGray);
    return dnf;
}

// векторы поглащаемые данным
// проверяет, поглащается ли данный вектор Вектор1 вектором Вектор2
// вернуть результат: "false", "true", "equal"
string Absorption(int Vector1, int Vector2, int Vars)
{
    bool ortogonal = false;
    int equal=0;
    // учёт удалённого вектора
    if (ShortDNF[Vector1][0] == -100 || ShortDNF[Vector2][0] == -100) return "false";
    else
    {
        for (int i=0; i<Vars; i++)
        {
            // учёт ортогональности
            if ( abs(ShortDNF[Vector2][i] - ShortDNF[Vector1][i]) == 1 ) ortogonal = true;
            // учёт равенства
            if ( ShortDNF[Vector2][i] == ShortDNF[Vector1][i] ) equal++;
            // учёт случая типа: поглащает ли вектор 1011 вектор 1-11
            if ( ShortDNF[Vector2][i] - ShortDNF[Vector1][i] < -5 ) ortogonal = true;
        }
        if (ortogonal)        return "false"; else
        if (equal == Vars)    return "equal"; else
                            return "true";
    }
}

// поиск смежного вектора среди предыдущих
// возвращает адрес (номер строки) вектора, смежного вектоу Alpha, иначе -1
int SearchAdjacent (int Alpha, int Vars)
{
    bool bAdjacent = true; int i;
    for (i=Alpha-1; i>=0; i--)
    {
        if (ShortDNF[i][5] == 0)
        {
            int adjacent = 0;
            for (int j=0; j<Vars; j++)
            {
                if ( (ShortDNF[Alpha][j] == 1 && ShortDNF[i][j] == 0 ) ||  

                     (ShortDNF[Alpha][j] == 0 && ShortDNF[i][j] == 1 ) )
                    adjacent++;
            }
            if (adjacent == 1) {bAdjacent = true; break;}
        }
    }
    if (bAdjacent) { ShortDNF[i][5] = 1; return i; }
    else return -1;
}