Это новый материал из книги, которую сейчас пишу.
Точнее, схемы-то старые. Новым является математическое доказательство.
Прошу критиковать и указать на ошибки, особенно в математических преобразованиях.
СТАНДАРТНАЯ И НЕСТАНДАРТНАЯ
ЛОГИЧЕСКАЯ СХЕМА «И»Стандартная логическая схема «И» для N логических переменных — это схема, содержащая N икон Вопрос, которые:
расположены на одной вертикали;
в каждой иконе Вопрос содержится одна переменная.
Стандартная схема «И» для трех логических переменных представлена на рис. 84, слева.
Нестандартная логическая схема «И» для N логических переменных — схема, полученная с помощью рокировки стандартной схемы «И» (рис. 84, справа).
Стандартная и нестандартная схемы «И» равносильны. Они описывают один и тот же алгоритм.
Рис. 84. Стандартная (слева) и нестандартная (справа) схема «И»
Вложение:
Рис. 84 Фрагмент Схема И .png [ 77.54 КБ | Просмотров: 11025 ]
ЧЕМ РАЗЛИЧАЮТСЯ СТАНДАРТНАЯ
И НЕСТАНДАРТНАЯ СХЕМЫ «И»Отличия показаны на рис. 84. Они выявляются с помощью трех проверок.
1. Как размещены иконы Вопрос?
В стандартной схеме они лежат на шампуре (рис. 84, слева).
В нестандартной — расположены лесенкой (рис. 84, справа).
2. Где находится главный выход?
В стандартной схеме он лежит на шампуре.
В нестандартной — расположен справа.
3. Где находится инверсный выход?
В стандартной он находится справа.
В нестандартной — лежит на шампуре.
ВЫВОД ФОРМУЛЫ ДЛЯ ИНВЕРСНОГО ВЫХОДАНа рис. 84 (внизу) представлены две формулы.
Заменим верхнюю черту (знак отрицания) на ¬, а знак V на + (знак логического сложения). Получим.
Z = A & B & C (1)
¬Z = ¬A + A & ¬B + A& B & ¬C (2)
Наша цель — доказать, что, взяв отрицание от формулы (1), мы получим формулу (2), то есть:
¬(A & B & C) = ¬A + A & ¬B + A& B & ¬C (3)
Таким образом, мы должны доказать равенство (3).
Сначала упростим левую часть уравнения (3). Для этого используем формулу де Моргана ¬(a & b) = ¬a + ¬b.
В результате получим
¬(A & B & C) = ¬A + ¬B + ¬C (4)
Затем упростим правую часть уравнения (3). Учитывая свойство дистрибутивности, a & b + a & c = a & (b + c), преобразуем
¬A + A & ¬B = (¬A + A) & (¬A + ¬B) = 1 & (¬A + ¬B) = ¬A + ¬B.
Отсюда следует, что
¬A + A & ¬B = ¬A + ¬B (5)
Принимая во внимание (4) и (5), уравнение (3) принимает вид
¬A + ¬B + ¬C = ¬A + A &¬B + A& B & ¬C (6)
Поскольку уравнения (3) и (6) равносильны, наша задача сводится к необходимости доказать равенство (6)
Преобразуем правую часть равенства (6).
¬A +¬B + A & B & ¬C = ¬A + (¬B + B) & (¬B + A & ¬C) = ¬A + 1 & (¬B + A & ¬C) = ¬A + ¬B + A & ¬C = ¬B + (¬A + A) & (¬A +¬C) = ¬B +1 & (¬A +¬C) = ¬A +¬B +¬C
Отсюда вытекает, что равенство (6) доказано и, следовательно, наша задача полностью решена.
Таким образом, обе формулы на рис. 84, описывающие главный и инверсный выход логической схемы «И», являются доказанными и правильными.
Вход
FAQ
Поиск
