Логические операции
Основные логические операции над высказываниями, используемыми в ЭВМ, включают отрицание, конъюнкцию, дизъюнкции, стрелку Пирса и штрих Шеффера. Рассмотрим эти логические операции.
1. Отрицание (обозначается также ØX, ~X).
Отрицание (NOT, читается «не X») – это высказывание, которое истинно, если X ложно, и ложно, если X истинно.
2. Конъюнкция XY (X&Y, XÙY).
Конъюнкция XY (AND, логическое умножение, «X и Y») – это высказывание, которое истинно только в том случае, если X истинно и Y истинно.
3. Дизъюнкция X+Y (XÚY).
Дизъюнкция X+Y (OR, логическая сумма, «X или Y или оба») – это высказывание, которое ложно только в том случае, если X ложно и Y ложно.
4. Стрелка Пирса X ¯ Y.
Стрелка Пирса X ¯ Y (NOR (NOT OR), ИЛИ-НЕ) – это высказывание, которое истинно только в том случае, если X ложно и Y ложно.
5. Штрих Шеффера X | Y.
Штрих Шеффера X | Y (NAND (NOT AND), И-НЕ) – это высказывание, которое ложно только в том случае, если X истинно и Y истинно.
Определить значения логических операций при различных сочетаниях аргументов можно из таблицы истинности.
Таблица истинности для основных логических операций, используемых в ЭВМ
X | Y | ![]() | XY | X + Y | X ¯ Y | X | Y |
Чтобы определить значение операции 0 + 1 в таблице истинности, необходимо на пересечении столбца X + Y (определяет операцию) и строки, где X = 0 и Y = 1 (так первый аргумент равен 0, а второй – 1), найти значение 1, которое и будет являться значением операции 0 + 1.
В алгебре высказываний существуют две нормальные формы: конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ).
КНФ – это конъюнкция конечного числа дизъюнкций нескольких переменных или их отрицаний (произведение сумм). Например, формула X(Y + Z) находится в КНФ.
ДНФ – это дизъюнкция конечного числа конъюнкций нескольких переменных или их отрицаний (сумма произведений). Например, формула X + YZ находится в ДНФ.
Логические операции обладают свойствами, сформулированными в виде равносильных формул.
Снятие двойного отрицания (отрицание отрицания):
![]() ![]() ![]() ![]() | Закон «исключения третьего»:
X+ ![]() ![]() ![]() ![]() ![]() |
Порядок применения формул при преобразованиях - перечисленные формулы рекомендуется применять в следующем порядке:
1) преобразование стрелки Пирса (6.22) и штриха Шеффера (6.23);
2) законы де Моргана (6.8)-(6.9);
3) формулы дистрибутивности (6.6)-(6.7);
4) элементарные поглощения (6.18)-(6.21).
Обычно формула приводится к ДНФ, а затем отдельные слагаемые поглощаются.
Логические функции
Логическая функция (функция алгебры высказываний) f(X1, X2, …, Xn) от n переменных – n-арная операция на множестве [0; 1]. В этой функции логические переменные X1, X2, …, Xn представляют собой высказывания и принимают значения 0 или 1.
Существует различных логических функций от n переменных.
Логические операции, рассмотренные в предыдущем разделе, можно рассматривать как логические функции от двух переменных.
Набор функций, с помощью которого можно представить (выразить) все логические функции, называется функционально-полным или базисом. Основными базисами являются:
1) булевый базис, состоящий из конъюнкции, дизъюнкции и отрицания;
2) базис NOR, состоящий из стрелки Пирса;
3) базис NAND, включающий штрих Шеффера.Рассмотрим некоторые способы представления логических функций.
Аналитический. Функция задается в виде алгебраического выражения, состоящего из функций одного или нескольких базисов, применяемых к логическим переменным.
Табличный. Функция задается в виде таблицы истинности (соответствия), которая содержит 2n строк (по числу наборов аргументов), n столбцов по числу переменных и один столбец значений функции. В такой таблице каждому набору аргументов соответствует значение функции.
Числовой. Функция задается в виде десятичных (восьмеричных, шестнадцатеричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Нумерация наборов начинается с нуля. Аналогичным образом логическая функция может быть задана по нулевым значениям.
Классификация ЭВМ
Дата добавления: 2016-05-31; просмотров: 2297;