精华内容
下载资源
问答
  • 使用Java化简逻辑表达式
    千次阅读
    2020-04-08 13:09:20

    学习数字电路时候有化简逻辑表达式的题目,当时曾想过使用计算机化简,但是没有实际行动。
    毕业五年后给别人补习功课再次接触到逻辑表达式的化简,就想写出这个程序来,本来以为不太复杂,结果代码写了近三天...

    程序中大量使用了递归,可能效率不高,并且比较消耗内存,但是本着解决问题的角度,没有优化这些部分。程序中的simplify方法比较难理解,耗时也最长,写这块代码不知道死了几亿脑细胞。

    其本质思想跟卡诺图化简道理相似,首先展开成变量或的形式,然后展开成所有已知的最小项列表,最后合并最小项,首先处理比较孤立的项,也就是相邻项最少的最小项。

    如果一个变量存在n个相邻项,计算出需要消除n的变量的2^n个最小项,如果这n个最小项都在已知的最小项里,那么可以消除,如果不都在已知的最小项里,那么需要尝试消去n-1个变量,如果还是不行尝试n-2个变量,以此类推,这里有个排列组合的概念,程序中combination方法就是求Cnk组合数的。

    虽说从事软件行业也五年有余了,但是这类的代码写的还是不多,加上本程序未经详细测试,可能存在许多bug,欢迎大佬不吝赐教!

    import java.util.*;
    import java.util.concurrent.CopyOnWriteArrayList;
    import java.util.stream.Collectors;
    
    public class SimplifyLogicalExpression {
    
        public static void main(String[] args) {
    //        String expression = "((A+B)CD+ACD+AB(C+D'))'";
    //        String expression = "A'C'+A'B'+BC+A'C'D";
    //        String expression = "(ABCD+A'B'C'D')'";
    //        String expression = "(A'B)'+(A+C)'";
            String expression = "A'B'C'+A'B'C+AB'C+ABC+ABC'+A'BC'";
    
            System.out.println("expression : " + expression);
            List<String> results = simplifyExpression(expression);
            System.out.println();
            for (String simplify : results) {
                System.out.println("simplify : " + simplify);
            }
        }
    
        private static List<String> simplifyExpression(String expression) {
            int length = getLength(expression);
            if (length > 26) {
                throw new IllegalArgumentException("最多支持26个逻辑变量");
            }
    
            // 打开逻辑表达式, 如: (A+B)'=A'B', (AB)'=A'+B'
            String open = open(expression);
            System.out.println("open : " + open);
    
            // 逻辑表达式相乘, 如: (A+B)(B+C)=AB+AC+B+BC
            String multiply = multiply(open);
            System.out.println("multiply : " + multiply);
    
            // 化简逻辑表达式, 如: A+A'B=A+B, AB+A'C+BC=AB+A'C
            return simplify(multiply, length);
        }
    
    
        /**
         * 展开
         */
        private static String open(String expression) {
            StringBuilder sb = new StringBuilder();
            if (isNot(expression)) {
                String not = notNot(expression);
    
                List<String> res = new ArrayList<>();
                if (isOr(not)) {
                    List<String> src = listOr(not);
                    for (String e : src) {
                        res.add(reverse(e));
                    }
    
                    for (String s : res) {
                        sb.append(isSimple(s) ? s : open(s));
                    }
                    return sb.toString();
                } else {
                    List<String> src = listAnd(not);
                    for (String e : src) {
                        res.add(reverse(e));
                    }
    
                    for (String s : res) {
                        sb.append(isSimple(s) ? s : open(s)).append("+");
                    }
                    return "(" + strip(sb.toString().substring(0, sb.length() - 1)) + ")";
                }
            } else if (isOr(expression)) {
                List<String> list = listOr(expression);
                for (String s : list) {
                    sb.append(isSimple(s) ? s : open(s)).append("+");
                }
                return "(" + strip(sb.toString().substring(0, sb.length() - 1)) + ")";
            } else {
                List<String> list = listAnd(expression);
                for (String s : list) {
                    sb.append(isSimple(s) ? s : open(s));
                }
                return sb.toString();
            }
        }
    
    
        private static boolean isSimple(String str) {
            str = strip(str);
            return str.length() == 1 || str.length() == 2 && str.endsWith("'");
        }
    
        /**
         * 如果满足(A+B)格式,剥离最外层括号
         */
        private static String strip(String str) {
            if (!str.startsWith("(") || !str.endsWith(")")) {
                return str;
            }
            int closeCount = 0;
            int close = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == '(') {
                    close--;
                } else if (c == ')') {
                    close++;
                }
                if (close == 0) {
                    closeCount++;
                    if (i == chars.length - 1 && closeCount == 1) {
                        String res = str.substring(1, str.length() - 1);
                        if (res.startsWith("(")) {
                            return strip(res);
                        } else {
                            return res;
                        }
                    }
                }
            }
            return str;
        }
    
        private static List<String> listAnd(String str) {
            List<String> list = new ArrayList<>();
            int begin = 0;
            int close = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == '(') {
                    close--;
                } else if (c == ')') {
                    close++;
                }
                if (i < chars.length - 1 && chars[i + 1] == '\'') {
                    continue;
                }
                if (close == 0) {
                    list.add(strip(str.substring(begin, i + 1)));
                    begin = i + 1;
                }
            }
            return list;
        }
    
        private static boolean isOr(String str) {
            int close = 0;
            char[] chars = str.toCharArray();
            for (char c : chars) {
                if (c == '(') {
                    close--;
                } else if (c == ')') {
                    close++;
                } else if (close == 0 && c == '+') {
                    return true;
                }
            }
            return false;
        }
    
        private static boolean isAnd(String str) {
            return !isNot(str) && !isOr(str);
        }
    
        private static List<String> listOr(String str) {
            List<String> list = new CopyOnWriteArrayList<>();
            int begin = 0;
            int close = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == '(') {
                    close--;
                } else if (c == ')') {
                    close++;
                }
                if (close == 0) {
                    if (c == '+') {
                        list.add(str.substring(begin, i));
                        begin = i + 1;
                    } else if (i == chars.length - 1) {
                        list.add(str.substring(begin));
                    }
                }
            }
            return list;
        }
    
        /**
         * 整体非判断,如:(A'B+CD')'
         */
        private static boolean isNot(String str) {
            int close = 0;
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == '(') {
                    close--;
                } else if (c == ')') {
                    close++;
                } else if (close == 0) {
                    if (chars[0] == '(' && chars[i - 1] == ')' && c == '\'' && i == chars.length - 1) {
                        return true;
                    } else {
                        return false;
                    }
                }
            }
            return false;
        }
    
        /**
         * 取反
         */
        private static String reverse(String expression) {
            if (isNot(expression)) {
                return notNot(expression);
            }
            if (expression.length() == 1) {
                return expression + "'";
            } else if (expression.length() == 2 && expression.endsWith("'")) {
                return expression.substring(0, 1);
            } else {
                return "(" + strip(expression) + ")'";
            }
        }
    
        /**
         * 整体非的取非
         */
        private static String notNot(String expression) {
            return expression.substring(1, expression.length() - 2);
        }
    
        /**
         * (A+B)(B+C)=AB+AC+B+BC
         */
        private static String multiply(String expression) {
            if (!isAnd(strip(expression))) {
                return strip(expression);
            }
    
            List<List<String>> lists = new ArrayList<>();
    
            List<String> expressions = listAnd(expression);
            for (String and : expressions) {
                List<String> or = listOr(and);
                for (String s : or) {
                    if (s.contains("(") && s.contains(")")) {
                        or.remove(s);
                        or.addAll(listOr(multiply(s)));
                    }
                }
                lists.add(or);
            }
            Set<String> calc = new TreeSet<>(lists.get(0));
            for (int i = 1; i < lists.size(); i++) {
                List<String> multi = lists.get(i);
                Set<String> newCalc = new TreeSet<>();
                for (String c : calc) {
                    for (String m : multi) {
                        newCalc.add(c + m);
                    }
                }
                calc = modify(newCalc);
            }
    
            StringBuilder result = new StringBuilder();
            for (String s : calc) {
                result.append(lowerToUpperCase(s)).append("+");
            }
            return result.substring(0, result.length() - 1);
        }
    
    
        /**
         * a转为A'
         */
        private static String lowerToUpperCase(String s) {
            StringBuilder result = new StringBuilder();
            for (char c : s.toCharArray()) {
                if (c >= 'a' && c <= 'z') {
                    result.append(toOtherCase(c)).append("\'");
                } else {
                    result.append(c);
                }
            }
            return result.toString();
        }
    
        /**
         * a->A,A->a
         */
        private static char toOtherCase(char c) {
            if (c >= 'A' && c <= 'Z') {
                return (char) (c + 32);
            } else if (c >= 'a' && c <= 'z') {
                return (char) (c - 32);
            }
            throw new IllegalArgumentException();
        }
    
        /**
         * 把非转为小写字符
         */
        private static String notToLowerCase(String expression) {
            StringBuilder ss = new StringBuilder();
            char[] chars = expression.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                if (i < chars.length - 1 && chars[i + 1] == '\'' && chars[i] != ')') {
                    ss.append((chars[i] + "").toLowerCase());
                    i++;
                } else {
                    ss.append(chars[i]);
                }
            }
            return ss.toString();
        }
    
        /**
         * 去重 AAB = AB
         * 去除包含反字符的 ABa = 0
         */
        private static Set<String> modify(Collection<String> expression) {
            Set<String> set = new TreeSet<>();
            z:
            for (String s : expression) {
                Set<Character> treeSet = new TreeSet<>();
                for (char c : notToLowerCase(s).toCharArray()) {
                    if (treeSet.contains(toOtherCase(c))) {
                        continue z;
                    }
                    treeSet.add(c);
                }
                set.add(treeSet.stream().map(Object::toString).collect(Collectors.joining("")));
            }
            return set;
        }
    
        /**
         * 化简逻辑表达式
         */
        private static List<String> simplify(String expression, int length) {
            Map<String, MinimumTerm> map = toMinimumTermMap(expression);
            List<List<String>> lists = flatSimplifyResult(simplify(map));
    
            List<List<String>> result = new ArrayList<>();
            int minUse = Integer.MAX_VALUE;
            for (List<String> list : lists) {
                int use = 0;
                for (String s : list) {
                    use += 1 << length - s.length();
                }
                if (minUse > use) {
                    minUse = use;
                    result.clear();
                    result.add(list);
                } else if (minUse == use) {
                    result.add(list);
                }
            }
            return result.stream().map(r -> lowerToUpperCase(String.join("+", r))).collect(Collectors.toList());
        }
    
        /**
         * 使用递归平铺SimplifyResult
         */
        private static List<List<String>> flatSimplifyResult(SimplifyResult result) {
            List<List<String>> lists = new ArrayList<>();
            if (result.others.isEmpty()) {
                List<String> list = new ArrayList<>();
                list.addAll(result.value);
                lists.add(list);
                return lists;
            }
            for (SimplifyResult res : result.others) {
                List<List<String>> r = flatSimplifyResult(res);
                for (List<String> list : r) {
                    list.addAll(result.value);
                }
                lists.addAll(r);
            }
            return lists;
        }
    
        /**
         * 化简逻辑表达式
         */
        private static SimplifyResult simplify(Map<String, MinimumTerm> map) {
            // 复制一个新的map
            List<MinimumTerm> terms = new ArrayList<>(map.values());
            // 按照相邻项的多少排列
            Collections.sort(terms);
            SimplifyResult result = new SimplifyResult();
            for (MinimumTerm term : terms) {
                if (term.use > 0) {
                    continue;
                }
                List<String> list = totalAdjacentTerms(term);
    
                if (allContains(map, list)) {
                    for (String s : list) {
                        map.get(s).use++;
                    }
                    result.value.add(getSimple(term));
                } else {
                    Map<MinimumTerm, List<String>> contains = maxContains(map, term);
                    for (Map.Entry<MinimumTerm, List<String>> entry : contains.entrySet()) {
                        Map<String, MinimumTerm> copy = copy(map);
                        for (String s : entry.getValue()) {
                            copy.get(s).use++;
                        }
                        SimplifyResult res = new SimplifyResult();
                        res.value.add(getSimple(entry.getKey()));
                        res.others.add(simplify(copy));
                        result.others.add(res);
                    }
                    break;
                }
            }
            return result;
        }
    
        private static Map<String, MinimumTerm> copy(Map<String, MinimumTerm> map) {
            Map<String, MinimumTerm> newMap = new HashMap<>();
            map.forEach((k, v) -> newMap.put(k, v.copy()));
            return newMap;
        }
    
        private static Map<MinimumTerm, List<String>> maxContains(Map<String, MinimumTerm> map, MinimumTerm term) {
            Map<MinimumTerm, List<String>> result = new HashMap<>();
            for (int i = 1; i < term.trues; i++) {
                Map<MinimumTerm, List<String>> adjacentTerms = getAdjacentTerms(term, i);
                for (Map.Entry<MinimumTerm, List<String>> entry : adjacentTerms.entrySet()) {
                    if (allContains(map, entry.getValue())) {
                        result.put(entry.getKey(), entry.getValue());
                    }
                }
                if (!result.isEmpty()) {
                    break;
                }
            }
            return result;
        }
    
        private static boolean allContains(Map<String, MinimumTerm> map, List<String> adjacentTerms) {
            boolean contains = true;
            for (String adjacentTerm : adjacentTerms) {
                if (!map.keySet().contains(adjacentTerm)) {
                    contains = false;
                }
            }
            return contains;
        }
    
        private static Map<MinimumTerm, List<String>> getAdjacentTerms(MinimumTerm term, int count) {
            Map<MinimumTerm, List<String>> result = new HashMap<>();
            List<Set<Integer>> lists = combination(term.trues, count, 0);
            for (Set<Integer> list : lists) {
                MinimumTerm copy = term.copy();
                int k = 0;
                for (int i = 0; i < copy.around.size(); i++) {
                    if (!copy.around.get(i)) {
                        continue;
                    }
                    if (list.contains(k)) {
                        copy.around.set(i, false);
                        copy.trues--;
                    }
                    k++;
                }
                List<String> terms = totalAdjacentTerms(copy);
                result.put(copy, terms);
            }
            return result;
        }
    
        /**
         * c n k 组合数
         */
        private static List<Set<Integer>> combination(int n, int k, int begin) {
            List<Set<Integer>> result = new ArrayList<>();
            for (int i = begin; i <= n - k; i++) {
                if (k > 1) {
                    List<Set<Integer>> list = combination(n, k - 1, i + 1);
                    for (Set<Integer> set : list) {
                        set.add(i);
                    }
                    result.addAll(list);
                } else {
                    Set<Integer> set = new HashSet<>();
                    set.add(i);
                    result.add(set);
                }
            }
            return result;
        }
    
        /**
         * n个相邻项组成的2^n个所有项
         * 若ABCD有三个相邻最小项目A'BCD,AB'CD,ABC'D
         * 则返回8个最小项集合 ABCD,ABC'D,AB'CD,AB'C'D,A'BCD,A'BC'D,A'B'CD,A'B'C'D
         */
        private static List<String> totalAdjacentTerms(MinimumTerm term) {
            List<String> terms = new ArrayList<>();
    
            int n = 1 << term.trues;
            for (int i = 0; i < n; i++) {
                char[] chars = Integer.toBinaryString(i).toCharArray();
                int k = chars.length - 1;
                List<Integer> indices = new ArrayList<>();
                for (int j = 0; j < term.around.size(); j++) {
                    if (!term.around.get(j)) {
                        continue;
                    }
                    if (chars.length >= k + 1 && k >= 0 && chars[k] == '1') {
                        indices.add(j);
                    }
                    k--;
                }
                terms.add(getOtherTermValue(term.value, indices));
            }
            return terms;
        }
    
        /**
         * 获取变量个数
         */
        private static int getLength(String expression) {
            Set<Character> set = new HashSet<>();
            for (char c : expression.toUpperCase().toCharArray()) {
                if (c >= 'A' && c <= 'Z') {
                    set.add(c);
                }
            }
            return set.size();
        }
    
        private static Map<String, MinimumTerm> toMinimumTermMap(String expression) {
            Set<MinimumTerm> nodes = new HashSet<>();
            for (String s : expression.split("\\+")) {
                nodes.addAll(toMinimumTerms(s, getLength(expression)));
            }
            Map<String, MinimumTerm> map = new HashMap<>();
            for (MinimumTerm node : nodes) {
                map.put(node.value, node);
            }
            fillAround(map);
            return map;
        }
    
        /**
         * 填充是否存在相邻项
         */
        private static void fillAround(Map<String, MinimumTerm> map) {
            for (Map.Entry<String, MinimumTerm> entry : map.entrySet()) {
                for (int i = 0; i < entry.getValue().value.toCharArray().length; i++) {
                    String otherTermValue = getOtherTermValue(entry.getValue().value, i);
                    boolean contains = map.keySet().contains(otherTermValue);
                    entry.getValue().around.add(contains);
                    if (contains) {
                        entry.getValue().trues++;
                    }
                }
    
            }
        }
    
        private static String getOtherTermValue(String value, int index) {
            List<Integer> indices = new ArrayList<>();
            indices.add(index);
            return getOtherTermValue(value, indices);
        }
    
        private static String getOtherTermValue(String value, List<Integer> indices) {
            for (Integer index : indices) {
                char c = value.charAt(index);
                String prefix = index <= 0 ? "" : value.substring(0, index);
                String suffix = index >= value.length() - 1 ? "" : value.substring(index + 1);
                value = prefix + toOtherCase(c) + suffix;
            }
            return value;
        }
    
        private static String getSimple(MinimumTerm term) {
            char[] chars = term.value.toCharArray();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < term.around.size(); i++) {
                if (!term.around.get(i)) {
                    sb.append(chars[i]);
                }
            }
            return sb.toString();
        }
    
        private static Set<MinimumTerm> toMinimumTerms(String s, int length) {
            List<StringBuilder> terms = listMinimumTerms(notToLowerCase(s), length);
            Set<MinimumTerm> nodes = new HashSet<>();
            for (StringBuilder sb : terms) {
                MinimumTerm term = new MinimumTerm();
                term.value = sb.toString();
                nodes.add(term);
            }
            return nodes;
        }
    
        /**
         * 获取最小项列表
         *
         * @param len 最小项长度
         */
        private static List<StringBuilder> listMinimumTerms(String src, int len) {
            List<StringBuilder> sList = new CopyOnWriteArrayList<>();
            StringBuilder ns = new StringBuilder();
            sList.add(ns);
            for (int i = 'A'; i < 'A' + len; i++) {
                String c = (char) i + "";
                if (src.contains(c)) {
                    for (StringBuilder s : sList) {
                        s.append(c);
                    }
                } else if (src.toUpperCase().contains(c)) {
                    // c是小写字符
                    for (StringBuilder s : sList) {
                        s.append(c.toLowerCase());
                    }
                } else {
                    for (StringBuilder s : sList) {
                        StringBuilder nns = new StringBuilder(s);
                        nns.append(c.toLowerCase());
                        s.append(c);
                        sList.add(nns);
                    }
                }
            }
            return sList;
        }
    
        /**
         * 最小项
         */
        private static class MinimumTerm implements Comparable<MinimumTerm> {
            String value;
            List<Boolean> around = new ArrayList<>();
            int trues = 0;
            int use = 0;
    
            @Override
            public int compareTo(MinimumTerm o) {
                return trues - o.trues;
            }
    
            @Override
            public String toString() {
                return value + around + trues + "/" + use;
            }
    
            MinimumTerm copy() {
                MinimumTerm term = new MinimumTerm();
                term.value = this.value;
                term.around.addAll(this.around);
                term.trues = this.trues;
                term.use = this.use;
                return term;
            }
        }
    
        /**
         * 最小项结果
         */
        private static class SimplifyResult {
            List<String> value = new ArrayList<>();
            List<SimplifyResult> others = new ArrayList<>();
    
            @Override
            public String toString() {
                return value.toString() + (others.isEmpty() ? "" : others.toString());
            }
        }
    }

    程序输出结果如下:

    expression : A'B'C'+A'B'C+AB'C+ABC+ABC'+A'BC'
    open : (A'B'C'+A'B'C+AB'C+ABC+ABC'+A'BC')
    multiply : A'B'C+A'B'C'+A'BC'+AB'C+ABC+ABC'

    simplify : A'B'+AC+BC'
    simplify : B'C+A'C'+AB

    更多相关内容
  • 一、最小项与卡诺图 1.最小项的定义 特点:每项都有n个变量, 每个乘积它中每个变量出现且仅出项1次 最小项具有下列性质: (1)对于任意一个最小项,只有一组变量取值使得它的值为1,而在变量取其他各组值时,这个...
  • 相邻项:指两个最小项仅有一个变量互为相反变量ABC+A‾BC=BCABC+ \overline{A}BC=BCABC+ABC=BC,相邻项可以合并从而化简逻辑函数 卡诺图能把最小项之间的相邻关系可视化,采用相邻项不断合并的方法就能对逻辑函数进行...

    原理分析

    • 卡诺图(Karnaugh Map),简称K图,它是一种根据最小项之间相邻的关系画出的一种方格图,每个小方格代表逻辑函数的一个最小项。
    • 相邻项:指两个最小项仅有一个变量互为相反变量 A B C + A ‾ B C = B C ABC+ \overline{A}BC=BC ABC+ABC=BC,相邻项可以合并从而化简逻辑函数
    • 卡诺图能把最小项之间的相邻关系可视化,采用相邻项不断合并的方法就能对逻辑函数进行化简。

    画法

    • 含n个变量的逻辑函数有2n个最小项,我们要在表格中把有相邻关系的最小项放在相邻的位置,首先要有2n个格子
    • 若含有两个变量A,B
      在这里插入图片描述
    • 若含有三个变量A,B,C
      在这里插入图片描述
    • 注意:多变量的卡诺图中要注意相邻行或列标注的值的关系,比如上图中AB的值作为列,从左到右是00,01,11,10,每个相邻的列的值变化只有一位,也就是按照格雷码的顺序来排,从而保证相邻格子的最小项具有相邻关系
    • 00代表 A B ‾ \overline{AB} AB,01代表 A ‾ B \overline{A}B AB,以此类推
    • 每个格子中根据真值表填入1或0

    化简

    • 用卡诺圈圈出相邻的填1的格子,画卡诺圈的原则:

      • 卡诺圈中填1的小方格的个数应是2的整数次幂,即2,4,8…
      • 应保证卡诺圈的个数最少,即每个卡诺圈中小方格的数尽可能多。
      • 最后把每个卡诺圈中不变的量组合成一个项
      • 填1的小方格可以处在多个卡诺圈中,但每个卡诺圈中至少要有一个填1的小方格在其他卡诺圈中没有出现过
      • 卡诺图的上下,左右边是相邻的

    在这里插入图片描述
    如图中左下角的四格的卡诺圈,两列中D3是不变的,都是0,即 D 3 ‾ \overline{D_3} D3,两行中D1是不变的,所以这个圈对应的项是 D 3 ‾ D 1 \overline{D_3}D_1 D3D1

    • 在卡诺图上如果没有可以合并的填1的小方格,则逻辑函数不能化简,例如左下角的填1的小方格。
      在这里插入图片描述
    • 卡诺圈画法不唯一,因此化简的表达式也不唯一
    • 有无关项的卡诺图要把无关项考虑在内才最简
    • 无关项既可以当1也可以当0,要灵活发挥不要一味当1用

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    多输出电路的卡诺图

    对每个输出分别计算
    在这里插入图片描述
    在这里插入图片描述
    左侧是Sa的卡诺图,右侧是Sb的。

    参考资料

    中国大学mooc 计算机组成原理.东北大学

    数字设计和计算机体系结构,第二版

    展开全文
  • 卡诺图化简逻辑函数

    2020-02-26 15:29:08
    依据 基本原理 化简步骤 上面(1)的3打错了要去掉 例题 逻辑函数的化简结果不是唯一的

    依据
    在这里插入图片描述
    基本原理

    在这里插入图片描述

    化简步骤

    在这里插入图片描述
    在这里插入图片描述
    上面(1)的3打错了要去掉

    例题
    在这里插入图片描述

    在这里插入图片描述
    逻辑函数的化简结果不是唯一的

    展开全文
  • 这是一个使用卡诺图化简法化简逻辑函数的程序 这是什么东西?可以看一下百度百科的介绍 卡诺图-百度百科 https://baike.baidu.com/item/%E5%8D%A1%E8%AF%BA%E5%9B%BE 卡诺图化简法-百度百科 ...
  • 很好用的卡诺图化简软件,直接得到逻辑表达式
  • 卡诺图化简性质 性质1: 深蓝色文字诺图中两个逻辑相邻的1方格的最小项可以合并成一个与项, 消去一个变量。 要注意的是: 逻辑相邻不仅仅是几何位置上的相邻,最左边的列与最右边的列、最上面的行和最下面的行...

    一 卡诺图化简性质

    性质1: 深蓝色文字诺图中两个逻辑相邻的1方格的最小项可以合并成一个与项, 消去一个变量。

    要注意的是: 逻辑相邻不仅仅是几何位置上的相邻,最左边的列与最右边的列、最上面的行和最下面的行都是逻辑相邻的。

    性质2:卡诺图中四个逻辑相邻1方格的最小项可以合并成一个与项,并消去两个变量。

    性质3:卡诺图中八个逻辑相邻的1方格可以合并成一个与项,并消去三个变量。

     

    二 卡诺图化简步骤及举例

    步骤包括:

    (1)画出函数的卡诺图;

    (2)仔细观察卡诺图,找出    个逻辑相邻的1方格,并给它们画上圈,画圈的原则要使圈尽可能大;

    (3)按照卡诺图化简性质,写出最简与或表达式。

    以下看几个例子

    例1  用卡诺图化简函数F(A,B,C,D) = 

    解: (1)画出函数F的卡诺图。

    把逻辑函数写成最小项形式如下:

    原式等于  F(A, B, C, D)  = m3+m9+m11+m13

                                             =

    画出该函数的卡诺图如下图(a) 所示

                 

                                   (a)                                                            (b)

    (2)给逻辑相邻的1方格画圈

    按照逻辑相邻原则画圈, 如上图(b)所示。

    (3)按照卡诺图化简性质,写出两个圈的最简与或表达式,并把它们相或起来, 就得到该逻辑函数的最简与或表达式。

      

    例2: 用卡诺图化简下列函数,并写出最简与或表达式: 

    解: 分几步来解析

    (1)画出函数F的卡诺图

       

    (2) 给逻辑相邻的1方格画圈,按照逻辑相邻原则画圈。

    (3)按照卡诺图化简性质,画出两个圈的与或表达式,并把它们相或起来,就得到最简与或表达式

    本例的画圈,我还是存有疑问的,横圈是否可以只圈最后两格, 不是圈住4格?

     

    在做卡诺图化简要注意事项: 在卡诺图上画圈有几个问题

    (1)将卡诺图中的1方格画圈, 一个也不能漏掉,1方格允许被多次圈用。

    2)圈的个数应尽可能少,因为一个圈和一个与项相对应,圈数越少, 与或表达式的与项就越少
    (3)圈内的1方格数必须为 个,圈的范围越大越好,因为圈越大,可消去的变量就越多,与项中的变量就越少。

    (4)每个圈应至少包含一个新的1方格, 否则这个圈就是多余的。

    (5)在同一个卡诺图中画圈的方式可能不是惟一的,因此用卡诺图化简所得到的最简与或表达式也不是惟一的。

    这里特别提醒注意 第4点, 看一个图加强理解

    用卡诺图化简函数F(A,B, C, D)=, 画图为

    这里绝不能给中间4个1方格 画圈, 因为没有新的1方格,都已被圈过!

     

     

     

     

    展开全文
  • 卡诺图化简1.1相关概念1.2应用卡诺图化简逻辑函数2.异或门 1.卡诺图化简 1.1相关概念 ●卡诺图:真值表的一种巧妙的图形表示。 ●为什么用卡诺图:用代数方法化简很困准,因为它没有固定的步骤,也不知道何时应该终止...
  • 卡诺图,在一张图上圈圈画画,就能搞定逻辑函数的化简问题。 4.1 卡诺图 4.1 卡诺图
  • 2010耳4月 电 脑 学 习 第2期多变量卡诺图化简的算法实现汪 靖’ 林 植摘 要:提出了一种对包含任意多个变量的卡诺圈进行化简的算法。给出了算法整体设计流程图以及关键函数伪代码。借助计 算机实现多变 量卡诺 图的...
  • 卡诺图的构成 1.卡诺图的构成 一种图形化简法,在逻辑设计中广泛应用 卡诺图:一种平面方格图,每个小方格代表一个最小项,又叫“最小项方格图” 卡诺图可以视为真值表图形化的...逻辑函数在卡诺图的表示 标准与-或
  • 逻辑函数卡诺图法化简(一)

    千次阅读 2020-05-02 23:39:10
    目录卡诺图卡诺图表示逻辑函数卡诺图的性质 卡诺图 1.定义:将n个变量的全部最小项用一个小方块表示,并使具有逻辑相邻性地最小项在位置上也相邻的排列...(1)逻辑函数以真值表或者最小项表达式给出:在卡诺图上...
  • 本文写到了最小项的概念以及卡诺图的定义和化简
  • 卡诺图化简下面的函数为最简“与-或”式 一、题目描述 (1) (2) 二、题目解答 (1) (2)
  • 卡诺图的时候需要先将所有变量可能以格雷码的形式排列在方格两侧,所有变量有2^n个,虽然我们常用的变量为四个及以下,可以熟记格雷码,但为了学习还是有必要了解格雷码的编码规则。格雷码的基本特点就是任意两个...
  • 逻辑函数化简软件

    2013-08-20 21:17:52
    4变量卡诺图化简软件 根据真值表自动化简成最简与或表达式 电子技术基础 数字部分 课程设计 作业
  • 逻辑表达式三种化简方法

    万次阅读 多人点赞 2019-07-19 11:48:48
    逻辑表达式三种化简方法 目录: ① 公式化简法 ② 卡诺图化简法 ③ 机器化简法 一、公式法化简:是利用逻辑代数的基本公式,对函数进行消项、消因子。常用方法有: ①并项法 利用公式AB+AB’=A 将两个与项...
  • 数字逻辑——卡诺图化简练习题

    千次阅读 2020-07-06 23:53:55
    一、问题描述 1.用卡诺图化简下列函数,写出最简与或表达式: 2.用卡诺图将下列含有无关项的逻辑函数化简为最简与或表达式: 二、问题解答 2.
  • 卡诺图化简

    千次阅读 2014-04-25 16:06:31
    一 .卡诺图的构成  卡诺图是一种平面方格图,每个小方格代表一个最小项,故又称为最小项方格图。 卡诺图上变量的排列规律使最小项的相邻... 卡诺图化简逻辑函数 1.几个定义   蕴涵项:在函数的“与-或”表
  • 卡诺图及其化简

    万次阅读 2018-06-17 10:17:59
    卡诺图及逻辑化简 以降低电路的价格为目标,对逻辑表达式进行变换的过程,称为逻辑化简。 逻辑化简的实际目标是尽可能地减少表达式中包含的项数以及各项包含的变量数。 2.4.1 真值表与卡诺图 真值表是一维的,...
  • 卡诺图化简法

    万次阅读 多人点赞 2019-03-07 08:42:42
    3.逻辑函数的卡诺图化简法 4.总结 1.学前需要了解知识点 最小项的定义 最小项的表示方法 最小项的相邻性 最小项的定义:一个函数的某个乘积项包含了函数的全部变量,其中每个变量都以原变量或反变量的形式出现...
  • 卡诺图的最简或与式化简

    万次阅读 2019-09-26 21:56:57
    卡诺图的经典用法是进行与或式的化简,而在某些场合,我们需要化简为最简或与式,此时可以先利用卡诺图化简出(Y非)的最简与或式,而后利用摩根定律化简出Y的最简或与式。 卡诺图最简或与式化简在某些场合具有重要...
  • 卡诺图进行数字逻辑化简

    万次阅读 多人点赞 2017-11-03 18:43:14
    电路分为模拟电路与数字电路,模拟电路理论是整个电子电路的基础。但要想组成复杂的处理系统电路,...他的抗干扰能力为什么强我这里就不多说了,下面我只对用卡诺图进行数字电路的逻辑设计和化简做一下讲解。知识来原于
  • 化简表达式-1

    2019-11-07 01:23:52
    最小项: 我们抛去定义,用例子直接说明...在n变量逻辑函数中,若m包含n个因子的乘积项,而且这n个变量均以原变量或者反变量的形式出现一次。则称m为该组变量的最小项。上述例子中,n=3,m=ABC’,原变量没有取反,...
  • 1、最小项的定义及其性质 2、逻辑函数的最小项表达式 3、用卡诺图表示逻辑函数 4、用卡诺图化简逻辑函数 5、含无关项的逻辑函数及其化简 ...
  • 反演,对偶,卡诺图化简的理论依据和实际操作
  • 根据卡诺图绘制电路

    千次阅读 2020-12-07 23:58:11
    本关任务:根据如下卡诺图化简逻辑函数并绘制逻辑电路。
  • 看完这篇还不会化简卡诺图?你来打我

    千次阅读 多人点赞 2020-04-29 21:18:15
    最通俗易懂的的卡诺图化简教程 首先我们来介绍一下什么是卡诺图: 卡诺图是逻辑函数的一种图形表示。一个逻辑函数的卡诺图就是将此函数的最小项表达式中的各最小项相应地填入一个方格图内,此方格图称为卡诺图。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 678
精华内容 271
关键字:

卡诺图化简逻辑表达式

友情链接: fui_v25.zip