Творческий проект по предмету
"Информационные и электронные технологии"
Школа № 1006
Судакова Ольга и Золотарёва Татьяна
ЭЛЕМЕНТЫ БИНАРНОЙ ЛОГИКИ
1. Объекты бинарной логики.
Бинарная (двоичная, математическая, формальная) логика в качестве объектов рассматривает логические утверждения (суждения, высказывания).
Любое утверждение в её рамках может быть либо истинным (true), либо ложным (false), - "третьего не дано".
Условимся в первом случае присваивать утверждению значение "логической единицы", а во втором - "логического нуля".
Теперь любое утверждение можно рассматривать как некую "логическую переменную" со значениями 1 либо 0. Например, пусть утверждению "Жизнь на Земле существует" соответствует логическая переменная с именем x. Тогда x = 1 и т. д.
Для сложных комбинаций утверждений возможно определение функций (операций, действий) над логическими переменными. Таким образом, возникает "алгебра логики" или "булева алгебра" - по имени создателя такой алгебры английского математика и логика Буля (Bool) со своими действиями, свойствами и теоремами. Булева алгебра является логической базой цифровой техники.
Мы будем представлять логические функции одновременно в нескольких равноценных формах:
1) логическая формула: алгебраическая (аналитическая) форма;
2) диаграмма Венна: на некотором участке плоскости условно очерчена область, для точек которой данное утверждение истинно, - для остальных точек плоскости оно ложно; любой точке плоскости соответствует какое-то истинное утверждение, а любому "заведомо ложному" утверждению не соответствует ни одна точка;
3) таблица истинности: таблица состояний функции, в которой непосредственно указываются её значения для всех возможных комбинаций значений логических переменных (всего в такой таблице 2n строк, где n - число логических переменных, 2 - число возможных состояний каждой переменной);
4) временнaя диаграмма: график зависимости состояния функции от времени, на котором каждая строка таблицы состояний отображается на некотором промежутке времени (такте) либо высоким (high) уровнем графика (логическая единица), либо низким (low) уровнем (логический нуль);
5) пространственная диаграмма: отображает таблицу истинности в декартовых координатах (до 4-х логических переменных);
6) логическая схема: состоит из "логических элементов", условно изображающих те или иные логические функции.
Для алгебраического представления логических функций, их таблиц истинности, временных диаграмм и логических схем будут использованы модели в Mathcad 2000, MS Excel 2000 и Electronics Workbench 5.12.
2. Некоторые логические функции.
2.1. Функции одной логической переменной (унарные).
Формально с любым утверждением можно либо согласиться, либо нет. Первому случаю соответствует функция "Логическое тождество (эквивалентность)".
Определим в Mathcad целочисленные переменные x, y и z, принимающие значения 0 либо 1. Определим также вышеназванную функцию переменной x как EQV(x):
Определим теперь вторую из двух возможных унарную функцию "Логическое отрицание (НЕ, NOT, инверсия)" как NOT(x):
На рисунке приведена также панель логических (булевых) операторов Mathcad.
Начертим общую для двух функций диаграмму Венна:
Создадим в Excel таблицу истинности для функции логического отрицания:
Рассмотрим наиболее распространенные правила алгебры логики на примерах с минимальным количеством переменных, где А=0, В=1, так как высказывание А ложно, а В - истинно. Высказывания могут быть простыми и сложными: простые содержат одно законченное утверждение, сложные образуются из двух или большего числа простых высказываний, связанных между собой некоторыми логическими связями.
Функцию НЕ в символах алгебры логики записывают X=A'.
Правило 1. X=A·0=0 Логическое произведение любого аргумента на 0 всегда равно 0.
Правило 2. X=A·1=A Логическое произведение любого аргумента на 1 равно значению аргумента.
Правило 3. X=A·A=A Логическое произведение одних и тех же аргументов равно аргументу.
Правило 4. А·А'=0 Логическое произведение аргумента с его инверсией равно нулю.
Правило 5. X= A+ 0=A
Правило 6.X=A+1=1
Правило 7. X=A+A=A
Правило 8.X=A+A'=1
Правило 9.X=A"=A Двойная инверсия аргумента дает его истинное значение.
Правило 10.X=AB=BA
Правило 11.X=A+B=B+A
Правило 12.X=(AB)C=A(BC)
Правило 13. X=(A+B)+C=A+(B+C)
Правило 14. X=A(B+C)=AB+AC
Правило 15. X=A+(BC)=(A+B)(A+C)
Правило 16.X=A+AB=A
Правило 17.X=A+A'B'=A+B
Правило 18.(AB)'=A'+B' (тождество де Моргана)
Правило 19.(A+B)'=A'B' (тождество де Моргана)
Схемные изображения в Electronics Workbench логических элементов (Logic Gates) рассмотренных функций:
Второй элемент называется инвертором (обратим внимание на изображение инверсного выхода элемента). На рисунке приведена также панель логических элементов.
Построим в Electronics Workbench временную диаграмму на виртуальных моделях элементов, для чего входные значения получим из генератора слова (Word Generator), подав затем их и выходные значения на логический анализатор (Logic Analyzer):
В шестнадцатиразрядном генераторе слова каждые 4 двоичные разряда (полубайт) кодируются шестнадцатеричной цифрой от 0 до F. В нашем случае, например, значению переменной x = 1 в генераторе соответствует двоичный код 0000 0000 0000 0001 и шестнадцатеричный код 0001, как на рисунке выше.
На рисунке приведена также панель инструментов (Instruments).
2.2. Функции двух логических переменных (бинарные).
Из более чем десятка таких функций рассмотрим только две: любая из них в комбинации с логическим отрицанием образует так называемый "логический базис", достаточный для синтеза остальных функций, а также произвольных логических функций.
1) Определим бинарную функцию "Константа 0".
Создадим соответствующую таблицу истинности в Excel:
Создадим соответствующую таблицу истинности в Excel:
4) Определим бинарную функцию " Запрет по Y (отрицание импликации)".
Для этого определим эту функцию в программе Electronics Workbench Professional Edition для того, чтобы выявить понятную формулу для таких программ, как Microsoft Excel и Mathcad Professional.
При этом стоит учесть, что в этой программе А=X, В=Y. Причем в Electronics Workbench Professional Edition и вообще принято считать, что X является старшим разрядом, а Y- младшим. Но некоторые программы, например Mathcad Professional, определяют X младшим разрядом, а Y- старшим.
В программе Electronics Workbench Professional Edition откроем Logic Converter определим значения А и В и их конечный итог для функции "Запрет по Y". И, выбрав в Conversions кнопку , создадим конечную формулу.
По этой формуле в Mathcad Professional определим бинарную функцию
В Microsoft Excel создадим таблицу истинности:
5) Определим бинарную функцию " Переменная X".
Точно так же как и в предыдущий раз выявим в программе Electronics Workbench Professional Edition понятную формулу для таких программ, как Microsoft Excel и Mathcad Professional.
6) Определим бинарную функцию Запрет по X(отрицание импликации)".
7) Определим бинарную функцию " Переменная Y".
8) Определим бинарную функцию " Сумма по модулю 2".
Подводя итог всему выше изложенному, приходим к выводу, что Mathcad, Microsoft Excel и Electronics Workbench могут работать только с четырьмя логическими функциями: отрицание, И, ИЛИ, исключительное ИЛИ. Но существует логический (булев, Boolean) базис, который помогает реализовывать любые функции. Такой базис образуют логические комбинации 2-И-НЕ и 2-ИЛИ-НЕ. В Logic Converter Electronics Workbench используется первая.
Синтезируем, например, функцию "Штрих Шеффера".
Определим в логическом конверторе таблицу истинности, соответствующую рассмотренной выше логической функции; получим для нее логическую формулу (СДНФ), логическую схему, а также схему в базисе 2-И-НЕ:
ЗАЧЕТНЫЕ ВОПРОСЫ.
Функция задана таблицей истинности.
1. Записать СДНФ и определить в Mathcad.
2. Создать логическую схему, а так же схему в базисе 2-И-НЕ в логическом конверторе Workbench.
3. Создать логическую схему в базисе 2-ИЛИ-НЕ и доказать их эквивалентность: в Mathcad, Workbench, в Logic Converter, в логическом анализаторе, в Excel.
Примерные ответы на данные вопросы на примере логической функции "Штрих Шеффера".
2. Создадим логическую схему и схему в базисе 2-И-НЕ в логическом конверторе:
3. Воспользуемся правилами 9 и 19: A'B' = (AB)', AB = A"B" = (A' + B')' для создания в базисе логической схемы 2-ИЛИ-НЕ. Нетрудно показать, что объединение входов дизъюнктора с отрицанием или конъюнктора с отрицанием (левых частей тождеств де Моргана) дает инвертор:
А'B' + A'B + AB' = A'B' + A'B" + A"B' = (A + B)' + (A + B')' + (A' + B)' = ((A + B)' + (A + B')') + (A' + B)' = (((A + B)' + (A + B')')')' + (A' + B)' = (((((A + B)' + (A + B')')')' + (A' + B)')')'
А'B' + A'B + AB' = A'B' + A'B" + A"B' = (A + B)' + (A + B')' + (A' + B)' = ((A + B)' + (A + B')') + (A' + B)' = (((A + B)' + (A + B')')')' + (A' + B)' = (((((A + B)' + (A + B')')')' + (A' + B)')')' 
