Основные элементарные логические функции
Основные понятия алгебры логики
VI. Основы алгебры логики
(продолжение)
Литерал – это логическая переменная или ее инверсия (отрицание). Переменная А и ее инверсия ┐А – это одна переменная с различными значениями, но это – два литерала.
Неполностью определенная ЛФ n переменных – это логическая функция, заданная на наборе, меньшем, чем 2n.
Суперпозиция – это подстановка в ЛФ вместо ее аргументов других ЛФ.
Функционально полная система ЛФ – это система, с помощью ЛФ которой, применяя операции суперпозиции и подстановки, можно получить любую сложную ЛФ.
Таблица истинности – это таблица, в которой приведены все возможные наборы аргументов некоторой ЛФ и соответствующие им ее значения.
Терм – это группа логических переменных в прямой или инверсной форме (группа литерал) некоторой ЛФ, объединенных одним и тем же знаком логической связки – логического сложения или умножения.
В терме каждая переменная или ее отрицание встречается только один раз, т. е. в терм может входить или переменная ЛФ, или ее отрицание.
Ранг терма – это количество переменных и их инверсий, т. е. количество литерал, входящих в терм. Терм, в который входят все переменные или их отрицания данной ЛФ, имеет максимальный ранг.
· Абсолютно истинная функция (константа единицы):f(x) = 1 при любых значениях аргумента
· Абсолютно ложная функция (константа нуля): f(x) = 0 при любых значениях аргумента
· Тождественная (равнозначная) функция:f(x) º x — повторяет значение своего аргумента
· Функция НЕ (NOT) — функция логического отрицания: f(x) =ù x —принимает значение, обратное значению аргумента
· Функция ИЛИ (OR) — функция дизъюнкции (логического сложения): f(x1, x2) = x1 + x2 = x1Ú x2 — истинна тогда, когда истинна хотя бы одна из переменных
· Функция И (AND) — функция конъюнкции (логического умножения): f(x1, x2) = x1 × x2 = x1 Ù x2 = x1&x2 —истинна тогда, когда все ее переменные одновременно истинны
· Функция И-НЕ (AND-NOT) — функция Шеффера (штрих):f(x1, x2) = x1/x2 — ложна тогда, когда все переменные одновременно истинны
· Функция ИЛИ-НЕ (OR-NOT) – функция Пирса (Вебба, стрелка): f(x1, x2) = x1 ¯ x2 = x1 O x2 — истинна тогда, когда все переменные ложны
· Функция ЕСЛИ-ТО (IF-THEN) — функция импликации:f(x1, x2) = x1 ® x2 — ложна тогда, когда x1 (посылка)– истинно и x2 (следствие)– ложно
· Функция исключающее ИЛИ (XOR) — функция неравнозначности (функция суммирования по модулю 2):f(x1, x2) = x1 " x2 = x1 Å x2 — истинна тогда, когда одна переменная ложна, а другая – истинна
Любые операции над логическими переменными можно свести к определенной совокупности элементарных ЛФ. Элементарные логические операции в компьютере выполняются поразрядно так же, как над двоичными числами.