逻辑表达式化简器 - 使用 Prime Implicant 算法

#include <stdio.h> #include <stdlib.h> #include <string.h>

#define MAX_TERMS 16 #define MAX_VARS 26

/* 化简结果 */ struct result { int terms[MAX_TERMS]; int num_terms; };

/* 存储初始表达式 */ struct expression { char input[100]; };

/* 存储化简结果 */ struct equation { int variables[MAX_VARS]; int num_vars; struct result *minimum_terms; };

/* 获取二进制表示中 1 的个数 */ int bitcount(unsigned int bits) { int count = 0; while(bits) { count++; bits &= bits - 1; } return count; }

/* 计算两个二进制表示不同的位数 */ int hamming_distance(unsigned int a, unsigned int b) { return bitcount(a ^ b); }

/* 将两个二进制表示的值合并，如果有不同的地方则为 -1 */ int merge(unsigned int a, unsigned int b) { unsigned int x = a ^ b;

if(bitcount(x) != 1) {
    return -1;
}

int i = 0;
while(x) {
    i++;
    x >>= 1;
}

return i;

}

/* 对一个数值获取其二进制表示中从左至右的某一位的值 */ int get_bit(unsigned int x, int pos) { return (x >> pos) & 1; }

/* 判断两个 term 是否属于同一组 */ int group_has_term(unsigned int group, int num) { return get_bit(group, num); }

/* 根据某个值，寻找它能够合并的 group / struct result find_mergeable(struct result* groups, int num_groups, int val) { int i, j; struct result *res = NULL;

for(i = 0; i < num_groups && !res; i++) {
    for(j = 0; j < groups[i].num_terms; j++) {
        if(merge(groups[i].terms[j], val) != -1) {
            res = &groups[i];
            break;
        }
    }
}
return res;

}

/* 添加一个 term 到某个 group 中 / void add_term(struct result group, int term) { group->terms[group->num_terms++] = term; }

/* 在 groups 中删除掉一个 group */ void drop_group(struct result *groups, int group_num, int num_groups) { int i; for(i = group_num + 1; i < num_groups; i++) { groups[i - 1] = groups[i]; } }

/* 从所有的 term 中找出不相交并且最小的子集，并返回包含这些子集的结果集 / struct result find_minimum_terms(unsigned int *terms, int num_terms) { int i, j, k; int num_groups = num_terms; struct result groups[MAX_TERMS]; struct result *minimum_terms = NULL;

/* 初始化 groups，每个单独的 term 属于一个不同的 group */
for(i = 0; i < num_terms; i++) {
    groups[i].terms[0] = terms[i];
    groups[i].num_terms = 1;
}

/* 尝试对所有的 group 合并，直至合并不再发生 */
while(num_groups > 1) {
    struct result new_groups[MAX_TERMS];
    int num_new_groups = 0;

    /* 遍历所有的 group */
    for(i = 0; i < num_groups; i++) {
        for(j = i+1; j < num_groups; j++) {
            int m = merge(groups[i].terms[0], groups[j].terms[0]);

            /* 如果两个 group 可以合并，则将它们合并 */
            if(m != -1) {
                struct result *merge_group = &new_groups[num_new_groups++];
                merge_group->num_terms = 0;

                /* 将两个 group 的 term 合并到一个新的 group 中 */
                for(k = 0; k < groups[i].num_terms; k++) {
                    add_term(merge_group, groups[i].terms[k]);
                }
                for(k = 0; k < groups[j].num_terms; k++) {
                    add_term(merge_group, groups[j].terms[k]);
                }

                /* 标记之前的 groups 已经被合并 */
                groups[i].num_terms = groups[j].num_terms = 0;
            }
        }
    }

    /* 将未被合并的 groups 添加到新的 groups 中 */
    for(i = 0; i < num_groups; i++) {
        if(groups[i].num_terms > 0) {
            new_groups[num_new_groups++] = groups[i];
        }
    }

    /* 将新的 groups 覆盖到旧的 groups */
    memcpy(groups, new_groups, num_new_groups * sizeof(struct result));
    num_groups = num_new_groups;
}

/* 将包含最少的 term 的 group 作为最小项 */
minimum_terms = &(groups[0]);
for(i = 1; i < num_groups; i++) {
    if(groups[i].num_terms < minimum_terms->num_terms) {
        minimum_terms = &(groups[i]);
    }
}

return minimum_terms;

}

/* 将表达式中的字符映射为二进制数值 */ unsigned int map_input(char input) { if(input == '-') { return 2; } else if(input >= 'A' && input <= 'Z') { return 1 << (input - 'A'); } else { return 0; } }

/* 获取所有的 term 的二进制表示 */ void generate_terms(unsigned int *terms, int num_terms, char *input) { int i; for(i = 0; i < num_terms; i++) { unsigned int term = 0; int j; for(j = 0; input[j]; j++) { term |= map_input(input[j * num_terms + i]) << j; } terms[i] = term; } }

/* 将某个变量添加到一个 equation 中，如果已经添加过，则返回之前的索引 */ int add_variable(struct equation *eq, int var) { int i; for(i = 0; i < eq->num_vars; i++) { if(eq->variables[i] == var) { return i; } } eq->variables[eq->num_vars++] = var; return i; }

/* 获取某个 term 的字符表示 */ void unmap_term(char *output, int num_vars, unsigned int term) { int i; for(i = 0; i < num_vars; i++) { if(get_bit(term, i) == 1) { output[i] = 'A' + i; } else if(get_bit(term, i) == 0) { output[i] = 'A' + i; output[i + num_vars] = '''; } else { output[i] = '-'; } } output[2 * num_vars] = '\0'; }

/* 对所有的最小项进行 prime implicant 算法 */ void find_prime_implicants(struct result *prime_implicants, int *num_pi, unsigned int *terms, int num_terms, int num_vars) { int i, j;

/* 初始化初始 equation */
struct equation *eq_list = (struct equation*) malloc(num_vars * sizeof(struct equation));
for(i = 0; i < num_vars; i++) {
    eq_list[i].num_vars = 0;
    eq_list[i].minimum_terms = NULL;
}

/* 获取所有的变量，并插入到对应的 equation 中 */
for(i = 0; i < num_terms; i++) {
    for(j = 0; j < num_vars; j++) {
        if(get_bit(terms[i], j) != 2) {
            int var = add_variable(&eq_list[j], j);
            eq_list[j].minimum_terms = find_minimum_terms(terms, num_terms);
            add_term(&eq_list[j].minimum_terms[var], i);
        }
    }
}

/* 递归地求解所有的最小项 */
struct result candidates[MAX_TERMS * 2];
int num_candidates = 0;

for(i = 1; i < num_terms; i++) {
    candidates[num_candidates].terms[0] = terms[i - 1];
    candidates[num_candidates].terms[1] = terms[i];
    candidates[num_candidates].num_terms = 2;
    num_candidates++;
}

i = 0;
while(i < num_candidates) {
    struct result *ci = &candidates[i];

    /* 首先，判断当前的 candidate 是否为 prime implicant，并将之存储到 pi_list 中 */
    int is_pi = 0;
    for(j = 0; j < num_terms; j++) {
        if(hamming_distance(terms[j], ci->terms[0]) == 0) {
            is_pi = 1;
            break;
        }
    }
    if(is_pi) {
        prime_implicants[(*num_pi)++] = *ci;
    }

    /* 其次，将所有未被包含的最小项添加到当前的 candidate 中 */
    for(j = 0; j < num_terms; j++) {
        int k;
        for(k = 0; k < ci->num_terms; k++) {
            if(ci->terms[k] == terms[j]) {
                break;
            }
        }
        if(k == ci->num_terms) {
            is_pi = 0;
            int has_mergeable = 0;
            struct result *mergeable = find_mergeable(ci, ci->num_terms, terms[j]);

            /* 利用 prime implicant 来尽可能的合并每个 term */
            if(mergeable) {
                has_mergeable = 1;
                for(k = 0; k < mergeable->num_terms; k++) {
                    if(hamming_distance(mergeable->terms[k], terms[j]) > 1) {
                        has_mergeable = 0;
                    }
                }
                if(has_mergeable) {
                    mergeable->terms[mergeable->num_terms++] = terms[j];
                }
            }

            /* 如果无法使用 prime implicant 合并，则创建一个新的 candidate */
            if(!has_mergeable) {
                struct result *new_ci = &candidates[num_candidates++];
                new_ci->num_terms = ci->num_terms + 1;
                memcpy(new_ci->terms, ci->terms, ci->num_terms * sizeof(int));
                new_ci->terms[new_ci->num_terms - 1] = terms[j];
            }
        }
    }

    i++;
}

free(eq_list);

}

/* 将两个 result 中都存在的 term 进行合并 */ void merge_terms(unsigned int *output, int *num_terms, struct result *r1, struct result *r2) { int i, j;

for(i = 0; i < r1->num_terms; i++) {
    for(j = 0; j < r2->num_terms; j++) {
        if(r1->terms[i] == r2->terms[j]) {
            output[(*num_terms)++] = r1->terms[i];
        }
    }
}

}

/* 化简表达式 */ void simplify_expression(struct expression *exp) { int i, j; int num_terms = strlen(exp->input) / 4; unsigned int terms[MAX_TERMS]; int num_vars = strlen(exp->input) / num_terms; struct result minimum_terms; struct result prime_implicants[MAX_TERMS]; int num_pi = 0; unsigned int final_terms[MAX_TERMS]; int num_final_terms = 0; char output_buffer[2 * MAX_VARS + 1];

/* 将表达式中的字符转换成二进制位 */
generate_terms(terms, num_terms, exp->input);

/* 获取所有的最小项 */
minimum_terms = *find_minimum_terms(terms, num_terms);

/* 对最小项进行 prime implicant 分解 */
find_prime_implicants(prime_implicants, &num_pi, terms, num_terms, num_vars);

/* 将 prime implicant 以及未被完全包含的最小项合并成 final terms */
for(i = 0; i < minimum_terms.num_terms; i++) {
    int has_match = 0;
    for(j = 0; j < num_pi; j++) {
        if(group_has_term(&prime_implicants[j], minimum_terms.terms[i])) {
            has_match = 1;
            break;
        }
    }
    if(!has_match) {
        final_terms[num_final_terms++] = minimum_terms.terms[i];
    }
}
for(i = 0; i < num_pi; i++) {
    struct result *pi = &prime_implicants[i];
    for(j = 0; j < minimum_terms.num_terms; j++) {
        if(group_has_term(&minimum_terms, pi->terms[j])) {
            break;
        }
    }
    if(j == minimum_terms.num_terms) {
        merge_terms(final_terms, &num_final_terms, &prime_implicants[i], &minimum_terms);
    }
}

/* 对所有的 final terms 进行可化简操作 */
printf("化简后的表达式：");
for(i = 0; i < num_final_terms; i++) {
    unmap_term(output_buffer, num_vars, final_terms[i]);
    printf("%s", output_buffer);
    if(i != num_final_terms - 1) {
        printf(" + ");
    }
}
printf("\n");

}

int main(void) { struct expression exp;

printf("请输入逻辑表达式（如 AB+AC）：");
scanf("%s", exp.input);

simplify_expression(&exp);

return 0;

}

/* 例如，输入为 AB+ABC，则输出结果为： 化简后的表达式：AB */