Здравствуйте, Пользователь из России!
Реализован алгоритм Куайна
Программа ниже. Комментарии в программе.
Выводятся результаты всех промежуточных этапов.
Будут вопросы - спрашивайте в мини-форуме.
[code h=200]
#include <windows.h>
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <conio.h>

typedef struct _DNF
{
unsigned int mask;
unsigned int np;
}DNF;

//подсчитывает число бит в двойном слове
int CalcBits(unsigned int data)
{
int cnt = 0;
int i;

for (i=0; i<32; i++, data>>=1)
cnt += (1 == (data & 1));
return cnt;
}

//определяет минимальную СДНФ по сокращенной
//параметры:
//адрес массива СДНФ, адрес индекса сокращенной СДНФ, адрес массива количеств имликант
void GetMinSDNF(DNF** pdnf, int* current, int* N)
{
int i, j, mi, ni, mj, nj;
int cnt, k;
int cb1, cb2;
int *NonNucleus = NULL; //матрица для поиска импликант, которые не являются ядром
//импликантная матрица для поиска минимальной СДНФ
//добавлены нулевые элементы для состояния строк и столбцов
int *Implicants = (int*)calloc((N[*current]+1)*(N[0]+1)*sizeof(int), sizeof(int));

//формируем импликантную марицу
printf("Implicants array:\n"); //выведем заголовок

for(i=1; i<=N[*current]; i++) //по всем импликантам сокращенной СДНФ
{
mi = pdnf[*current][i-1].mask; //маска элементов импликанты
ni = pdnf[*current][i-1].np; //значения элементов импликанты
for(j=1; j<=N[0]; j++) //по всем импликантам исходной СДНФ
{
mj = pdnf[0][j-1].mask; //маска
nj = pdnf[0][j-1].np; //значения
//пишем 1, если импликанта исходной СДНФ поглощается
//импликантой сокращенной СДНФ, или 0, если иначе
Implicants[i*(N[0]+1)+j] = (mi & nj) == (mi & ni);
printf("%d ", Implicants[i*(N[0]+1)+j]); //выведем
}
printf("\n");
}

//ищем ядро СДНФ (столбики матрицы, в которых ровно одна единица)
for(j=1; j<=N[0]; j++) //по столбикам импликантной матрицы
{
cnt = 0; //считаем
for(i=1; i<=N[*current]; i++) //по строкам
cnt += Implicants[i*(N[0]+1)+j];
if (cnt == 1)
Implicants[j] = 1; //пометим, что импликанта исходной СДНФ поглощается
} // импликантой сокращенной, которая в ядре!
//будем формировать минимальную СДНФ в другом массиве
N[(*current)^3] = 0; //обнулим счетчик

//найдем импликанты сокращенной СДНФ, которые в ядре
for(j=1; j<=N[0]; j++) //по всем столбцам импликантной матрицы
{ // (по всем импликантам исходной СДНФ)
if(Implicants[j]==1) //ядро?
{
//найдем индекс импликанты сокращенной СДНФ, которая в ядре
for(i=1; i<=N[*current]; i++) //по всем импликантам сокращенной СДНФ
{
if (Implicants[i*(N[0]+1)+j]) //признак поглощения есть?
break;
}

Implicants[i*(N[0]+1)] = 1; //помечаем импликанту сокращенной СДНФ, которая в ядре

//скопируем в минимальную СДНФ маску и значения импликанту, которая в ядре
pdnf[(*current)^3][N[(*current)^3]].mask = pdnf[*current][i-1].mask;
pdnf[(*current)^3][N[(*current)^3]++].np = pdnf[*current][i-1].np; //увеличиваем счетчик

//найдем и пометим импликанты основной СДНФ, которые поглощаются "ядровой" импликантой
for(k=1; k<=N[0]; k++) //по всем импликантам основной СДНФ
{
if (k != j) //в ядре - обходим
{
if (Implicants[i*(N[0]+1)+k]) //поглощается?
Implicants[k] = 2; //помечаем!
}
}
}
}

//осталось просмотреть те импликанты основной СДНФ,
//которые не поглощаются "ядровыми" импликантами сокращенной СДНФ
//ищем те импликанты сокращенной СДНФ, которые поглощают максимум импликант основной СДНФ
//если одинаковые, то берем ту импликанту, в которой меньше элементов импликанты
//иначе берем первую попавшуюся
do
{
//построим дополнительный массив (для удобства расчета)
//для тех импликант основной СДНФ,
//которые не поглощаются "ядровыми" импликантами и для тех
//импликант сокращенной СДНФ, которые не являются ядром
//посчитаем количество тех и других, т.е. размерность матрицы
ni = nj = 0;
for(j=1; j<=N[0]; j++)
nj += (0==Implicants[j]); //количество импликант основной СДНФ
for(i=1; i<=N[*current]; i++)
ni += (0==Implicants[i*(N[0]+1)]); //количество импликант сокращенной СДНФ

//проверим, все ли ипликанты основной СДНФ поглощены
// если =0, то значит сокращенная СДНФ уже является минимальной СДНФ
if (nj)
{
//выделим память под матрицу
NonNucleus = (int*)realloc(NonNucleus, ni*nj*sizeof(int));

//заполним массив, mi - индекс строк
for(mi=0,i=1; i<=N[*current]; i++) //по всем строкам импл матрицы
{
if (0 == Implicants[i*(N[0]+1)]) //не в ядре?
{
for(mj=0,j=1; j<=N[0]; j++) //по всем столбцам, mj - индекс столбца
{ //только для имликант основной СДНФ, которые еще не учтены
if (0 == Implicants[j])
//запишем в ячейку признак поглощения и индексы в импл матрице!
NonNucleus[mi*nj+mj++] = Implicants[i*(N[0]+1)+j] + ((i-1)<<24) + (j<<16);
}
mi++; //на следующую строку
}
}

//найдем строку, в которой отмечены макс количество поглощений!
//посчитаем для первой, считаем ее максимальной
for(cnt=j=0; j<nj; j++)
cnt += NonNucleus[j] & 0xff; //считаем число поглощений
i = 0; //номер строки с макс суммой

for(k=1; k<ni; k++) //по всем остальным
{
for(mj=j=0; j<nj; j++)
mj += NonNucleus[k*nj+j] & 0xff;//считаем
if (mj > cnt) //и сравниваем
{
cnt = mj; //новый максимум
i = k; // и индекс строки
}
if (mj == cnt) //если равно
{ //сравним число элементов импликантов
//для этого считаем число бит маски
cb1 = CalcBits(pdnf[*current][(NonNucleus[k*nj]>>24)&0xff].mask);
cb2 = CalcBits(pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].mask);

if (cb1 < cb2)
{
cnt = mj; //новые значения
i = k;
}
}
}
//запишем найденную импликанту в минимальную СДНФ (используем сохраненный индекс строки)
pdnf[(*current)^3][N[(*current)^3]].mask = pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].mask;
pdnf[(*current)^3][N[(*current)^3]++].np = pdnf[*current][(NonNucleus[i*nj]>>24)&0xff].np;

//пометим все поглощенные имликанты основной СДНФ
//могут остаться еще непоглащенные!
for(j=0; j<nj; j++)
Implicants[(NonNucleus[i*nj+j]>>16)&0xff] = 3*(NonNucleus[i*nj+j]&0xff);
}
else
break; //если все поглощаются, то выход!
}while (true); //на повтор анализа

*current ^= 3; //минимальная СДНФ становится текущей!
free(Implicants); //освобождаем память!
free(NonNucleus);
}

//поиск сокращенной СДНФ
//*current - индекс текущей СДНФ
//(*current)^3 - индекс, куда пишем результат
void GetShortSDNF(DNF** pdnf, int* current, int* N)
{
int i, j, k=1, l, mask;
int mi, ni, mj, nj;

while(k) //циклим, пока что-то склеивается
{
//проверяем по всем парам импликант, склеиваются ли они
for(i=k=0; i<N[*current]-1; i++) //по всем импликантам СДНФ
{
for(j=i+1; j<N[*current]; j++)
{
//только для одинаковых элементов импликант
if (pdnf[*current][i].mask == pdnf[*current][j].mask)
{
//смотрим, чем отличаются
mask = (pdnf[*current][i].np & pdnf[*current][i].mask) ^
(pdnf[*current][j].np & pdnf[*current][j].mask);
switch (mask) //если изменение только в одном бите, значит
{ // импликанты склеиваются!
case 0x01:
case 0x02:
case 0x04:
case 0x08:
case 0x10:
case 0x20:
case 0x40:
case 0x80:
//есть склеивание! - пишем в результат
//оставляем общие элементы
//количество пока не увеличиваем!
pdnf[(*current)^3][k].mask = pdnf[*current][i].mask & ~mask;
pdnf[(*current)^3][k].np = pdnf[*current][i].np;
//проверим на совпадение!
for(l=0; l<k; l++)
{
mi = pdnf[(*current)^3][l].mask;
ni = pdnf[(*current)^3][l].np;
mj = pdnf[(*current)^3][k].mask;
nj = pdnf[(*current)^3][k].np;

if ((mi == mj) && (mi & ni) == (mj & nj))
break; //такое уже есть! - выходим
}
if (l==k) //если дошли до конца - совпадения нет
k++; //увеличиваем счетчик
break;
}
}
}
}
if (k) //что-то склеилось?
{ //проверим на поглощение
for(i=0; i<N[*current]; i++) //по всем текущей СДНФ
{
mi = pdnf[*current][i].mask;//маска
ni = pdnf[*current][i].np; //значения

for(j=0; j<k; j++) //по всем результата
{
mj = pdnf[(*current)^3][j].mask;
nj = pdnf[(*current)^3][j].np;
//поглощается?
if (((mi | mj) == mi) && ((mj & ni) == (mj & nj)))
break; //да!
}
if (j == k) //дошли до конца - не поглощается
{ //значит - копируем в результат
pdnf[(*current)^3][k].mask = pdnf[*current][i].mask;
pdnf[(*current)^3][k++].np = pdnf[*current][i].np;
}

}

(*current) ^= 3; //меняем текущего на результат
N[*current] = k; //и сохраняем количество
}
}
}

//получение исходной СДНФ по строке таблицы истинности
int GetSDNF(char* sTrueTable, DNF** ppdnf, int *pcnt)
{
int len = strlen(sTrueTable); //длина строки
int i, count, imask;

switch (len) //ждем степень двойки
{

case 2:
*pcnt = 1;
break;
case 4:
*pcnt = 2; //количество элементов импликант
break;
case 8:
*pcnt = 3;
break;
case 16:
*pcnt = 4;
break;
case 32:
*pcnt = 5;
break;
case 64:
*pcnt = 6;
break;
case 128:
*pcnt = 7;
break;
case 256:
*pcnt = 8;
break;
default:
return -1; //ошибка!
}
//выделяем память под СДНФ
ppdnf[0] = (DNF*)realloc(ppdnf[0], 2*len*sizeof(DNF)); //исходная
ppdnf[1] = (DNF*)realloc(ppdnf[1], 2*len*sizeof(DNF)); //два массива для сокращенной СДНФ
ppdnf[2] = (DNF*)realloc(ppdnf[2], 2*len*sizeof(DNF)); //выбирается *current
//здесь же и минимальная
imask = (1<<*pcnt)-1; //маска для всех *pcnt элементов
for(count=i=0; i<len; i++) //по всем символам строки
{
if (sTrueTable[i] == '1') //1 - импликанта участвует в СДНФ
{ //запишем в массив [0] - основная СДНФ
//и в массив [1] для дальнейших расчетов
ppdnf[0][count].mask = imask; //все элементы
ppdnf[0][count].np = i; //значения
ppdnf[1][count].mask = imask; //запишем и в массив с индексом 1
ppdnf[1][count++].np = i; // для поиска сокращенной СДНФ
}
else if (sTrueTable[i] != '0') //ждем только 0 или 1
return -1; //ошибка!
}
return count; //вернем количество импликант основной СДНФ
}

//вывод одной СДНФ, с адресом pdnf, N - количесво импликант,
//cnt - максимальное количество элементов импликант
void OutSDNF(DNF *pdnf, int N, int cnt)
{
int i, j, k;

if ((N == 1) && (0 == pdnf[0].mask))
printf ("1\n"); //тождественная истина
else
{
for(i=0; i<N; i++) //по всем импликантам
{
for(k='a',j=cnt-1; j>=0; j--,k++) //в обратном порядке
{
if (pdnf[i].mask & (1<<j)) //если задан в маске
{
if (pdnf[i].np & (1<<j)) //если 1
printf("%c",k);
else
printf("~%c",k); // отрицание, или 0
}
}
printf(" V "); //знак дизъюнкции
}
printf("\x8\x8\x8 \n"); //вытрем последнюю дизъюнкцию
}
}

int main(int argc, char *argv[])
{
int N[3], cnt;
int current = 1;
DNF *pdnf[3] = {NULL, NULL, NULL}; //три массива СДНФ
char sTrueTable[512]; //строка для ввода таблицы истинности

while(1) //продолжаем, пока не откажемся
{
printf("\nEnter true table: ");
scanf("%s", sTrueTable); //вводим строку из 0 и 1

if ((N[0] = N[1] = GetSDNF(sTrueTable, pdnf, &cnt)) < 0) //формируем основную СДНФ
{
printf("Enter correct data!\n");//ошибка!
continue; //и на повтор
}

printf("Source SDNF:\n");
OutSDNF(pdnf[0], N[0], cnt); //выведем основную СДНФ

GetShortSDNF(pdnf, ¤t, N); //формируем сокращенную СДНФ
printf("Short SDNF:\n");
OutSDNF(pdnf[current], N[current], cnt); //выведем сокращенную СДНФ

GetMinSDNF(pdnf, ¤t, N); //формируем минимальную СДНФ
printf("Min SDNF:\n");
OutSDNF(pdnf[current], N[current], cnt); //выведем минимальную СДНФ

printf("Continue ? (Y,N) "); //спрашиваем продолжать ли дальше?
cnt = toupper(_getche());
printf("\n");

if (cnt != 'Y')
break; //выходим
}

free (pdnf[0]); //освобождаем память
free (pdnf[1]);
free (pdnf[2]);

return 0;
}
[/code]