Лекция 9

Тема:

VI. Основы алгебры логики

1. Основные понятия алгебры логики

(продолжение)

Литерал – это логическая переменная или ее инверсия (отрицание). Переменная А и ее инверсия ┐А – это одна переменная с различными значениями, но это – два литерала.

Неполностью определенная ЛФ n переменных – это логическая функция, заданная на наборе, меньшем, чем 2ⁿ.

Суперпозиция – это подстановка в ЛФ вместо ее аргументов других ЛФ.

Функционально полная система ЛФ – это система, с помощью ЛФ которой, применяя операции суперпозиции и подстановки, можно получить любую сложную ЛФ.

Таблица истинности – это таблица, в которой приведены все возможные наборы аргументов некоторой ЛФ и соответствующие им ее значения.

Терм – это группа логических переменных в прямой или инверсной форме (группа литерал) некоторой ЛФ, объединенных одним и тем же знаком логической связки – логического сложения или умножения.

В терме каждая переменная или ее отрицание встречается только один раз, т. е. в терм может входить или переменная ЛФ, или ее отрицание.

Ранг терма – это количество переменных и их инверсий, т. е. количество литерал, входящих в терм. Терм, в который входят все переменные или их отрицания данной ЛФ, имеет максимальный ранг.

2. Основные элементарные логические функции

• Абсолютно истинная функция (константа единицы): f(x) = 1 при любых значениях аргумента

• Абсолютно ложная функция (константа нуля): f(x) = 0 при любых значениях аргумента

• Тождественная (равнозначная) функция: f(x)  x — повторяет значение своего аргумента

• Функция НЕ (NOT) — функция логического отрицания: f(x) =  x — принимает значение, обратное значению аргумента

• Функция ИЛИ (OR) — функция дизъюнкции (логического сложения): f(x₁, x₂) = x₁ + x₂ = x₁  x₂ — истинна тогда, когда истинна хотя бы одна из переменных

• Функция И (AND) — функция конъюнкции (логического умножения): f(x₁, x₂) = x₁  x₂ = x₁  x₂ = x₁&x₂ — истинна тогда, когда все ее переменные одновременно истинны

• Функция И-НЕ (AND-NOT) — функция Шеффера (штрих): f(x₁, x₂) = x₁/x₂ — ложна тогда, когда все переменные одновременно истинны

• Функция ИЛИ-НЕ (OR-NOT) – функция Пирса (Вебба, стрелка): f(x₁, x₂) = x₁  x₂ = x₁ O x₂ — истинна тогда, когда все переменные ложны

• Функция ЕСЛИ-ТО (IF-THEN) — функция импликации: f(x₁, x₂) = x₁  x₂ — ложна тогда, когда x₁ (посылка) – истинно и x₂ (следствие) – ложно

• Функция исключающее ИЛИ (XOR) — функция неравнозначности (функция суммирования по модулю 2): f(x₁, x₂) = x₁  x₂ = x₁  x₂ — истинна тогда, когда одна переменная ложна, а другая – истинна

Любые операции над логическими переменными можно свести к определенной совокупности элементарных ЛФ. Элементарные логические операции в компьютере выполняются поразрядно так же, как над двоичными числами.

3. Свойства элементарных логических функций, двойственные аксиомы и теоремы алгебры логики

Некоторые законы алгебры также применимы к алгебре логики: логические выражения, содержащие операции дизъюнкции и конъюнкции, можно преобразовывать (раскрывать скобки, выносить общий множитель, переставлять местами члены и т. д.) по правилам алгебры, считая формально дизъюнкцию операцией сложения, а конъюнкцию – операцией умножения.

3.1. Свойство коммутативности.

Свойство коммутативности для умножения (конъюнкции):

A·B = B·A

Свойство коммутативности для сложения (дизъюнкции):

A+B = B+A

3.2. Свойство ассоциативности.

Свойство ассоциативности для умножения (конъюнкции):

A(B·C) = (A·B)C

Свойство ассоциативности для сложения (дизъюнкции):

A+(B+C) = (A+B)+C

3.3. Свойство дистрибутивности.

Свойство дистрибутивности для умножения по отношению к сложению:

A(B+C) = A·B+ A·C

Свойство дистрибутивности для сложения по отношению к умножению:

A+BC = (A+B)(A+C)

3.4. Двойственные аксиомы и теоремы алгебры логики.

Двойственность определяется как изменение всех знаков операции И на знаки операции ИЛИ, всех знаков операции ИЛИ на И, всех нулей на единицы, а всех единиц — на нули; является одним из основных свойств алгебры логики и означает, что, если f(A, B, C) и f(A, B, C) – двойственные функции, то

f(A, B, C) = f(A,B,C)

1) A = 1, если A  0	A = 0, если A  1
2) если A = 0, тоA = 1	если A = 1, тоA = 0
3) 0 + 0 = 0	0  0 = 0
4) 0 + 1 = 1	1  0 = 0
5) 1 + 1 = 1	1  1 = 1
6)0 = 1	1 = 0
7) A + 0 = A	A  1 = A
8) A + 1 = 1	A  0 = 0
9) A + A = A	A  A = A
10) A = A
11) A +A = 1	AA = 0
12) теорема де Моргана A + B + C =ABC	ABC =A + B + C
13) закон поглощение A(A + B) = A	A + AB = A
14) A +AB = A + B	A(A + B) = AB
15) закон склеивания AB +AB = B(A +A) = B	(A + B)(A +B) = A

Законы де Моргана, иллюстрирующие свойства двойственности:

ABC =A +B +C

A+ B + C =ABC

Следствия законов де Моргана:

ABC = A +B +C

A + B + C = ABC

Таким образом, есть возможность выражать конъюнкцию через дизъюнкцию, или дизъюнкцию – через конъюнкцию и отрицание. Законы де Моргана и следствия из них справедливы для любого количества переменных.