лекционный материал. Логические элементы компьютера
 Скачать 134.72 Kb.
|
Тема: Логические элементы компьютера1. Логические формулы. Таблица истинности логической формулы2. Основные законы алгебры логики. Упрощение логических формул3. Логическая функция§ 7. Логические основы ЭВМ. Базовые логические элементы§ 8. Логические элементы компьютера. Триггер и сумматор1. Логические формулы. Таблица истинности логической формулы.С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой. Определение логической формулы: Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы. Если А и В — формулы, то A, А . В , А v В , А B , А В — формулы. 3. Никаких других формул в алгебре логики нет. В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул. В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) C. Такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика". Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях — значение "ложь". Такие формулы называются выполнимыми. Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Например, формула А v А, соответствующая высказыванию "Этот треугольник прямоугольный или непрямоугольный" истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями. В качестве другого примера рассмотрим формулу А . А, которой соответствует, например, высказывание "Катя самая высокая девочка в классе, и в классе есть девочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо А обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями. Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры логики обозначается символом "=" Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы. Нами рассмотрены пять логических операций: отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция. Импликацию можно выразить через дизъюнкцию и отрицание: А В = Аv В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А В = (А v В) . (Вv А). Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания ("не"), затем конъюнкция ("и"), после конъюнкции — дизъюнкция ("или") и в последнюю очередь — импликация. Таблица истинности логической формулы – таблица, выражающая соответствие между всевозможными наборами значений переменных и значениями формулы. Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1). Если формула содержит три переменные, то таких наборов восемь: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1). Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д. Т.е., если N – количество переменных, то 2N – количество наборов значений переменных.
Удобной формой записи при нахождении значений формулы, содержащей несколько логических операций, является таблица, в которой кроме значений переменных и значений формулы также указаны и значения промежуточных формул. Примеры. 1. Составим таблицу истинности для формулы х · у (х у) х, которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы.
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной. 2. Таблица истинности для формулы:(х у) · (х · у)
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной. 3. Таблица истинности для формулы: (х у) х · z
Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Тема: