13. Алгебра логики. Логические переменные. Логические операции. Таблица истинности

Логическая (двоичная) переменная характеризует простое высказывание, которое содержит одну законченную мысль и может быть истинным или ложным. Она обозначается буквой и может принимать значения 1и 0.

Логическая функция - это сложное высказывание, состоящее из нескольких простых, связанных между собой соединительными союзами. Она записывается аналитически в виде y = f(x1, x2,..., xn), где xi - двоичная переменная, и также может принимать значения 1 и 0.

Входной набор - это определенная комбинация двоичных переменных (аргументов) в логической функции. Максимальное число входных наборов определяется выражением m = 2n, где n - число переменных. Максимальное число логических функций n переменных определяется числом N = 2m.

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

Функции двух переменных представлены в табл.

х1х2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
00 01 10 11	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

Отметим наиболее часто используемые функции из числа приведенных в таблице:

f₀ (x1, x2) = 0 - тождественный ноль (константа 0);

f₁ (x1, x2) = x₁ ∙ x₂ – конъюнкция (логическое произведение, И). Иногда употребляется знак & или /\;

f₃ (x1, х2) = x₁ − повторение x₁;

f₅ (x1, x2) = x_{2 −} повторение x₂;

f₆ (x1, x2) = x₁  x₂ − сложение по модулю 2 или mod 2;

f₇ (х1, х2) = x₁ + x₂ − дизъюнкция (логическое сложение, ИЛИ или V);

f₈ (x1, x2) = x₁ ↓ x₂ − функция Вебба (стрелка Пирса, ИЛИ-НЕ);

f₉ (х1, х2) = x₁ ~ x₂ − эквивалентность;

f₁₃(x1, x2) = x₁ → x₂ − импликация;

f₁₄(x1, x2) = x₁ | x₂ − штрих Шеффера (И-НЕ);

f₁₅(x1, x2) = 1 − тождественная единица (константа 1).

Логическое отрицание (функция НЕ). Логическим отрицанием высказывания x называется такое сложное высказывание f(x), которое истинно, когда x ложно, и наоборот.

Логическое умножение (конъюнкция). Конъюнкция (функция И) двух переменных x₁ и x₂ − это сложное высказывание, которое истинно только тогда, когда истинны x₁ и x₂, и ложно для всех остальных наборов переменных. Логическая функция конъюнкции имеет вид f=x₁·x₂. Для обозначения операции конъюнкции используются также символы & и Λ.

Логическое сложение (дизъюнкция). Дизъюнкция (функция ИЛИ) двух переменных x₁ и x₂ – это сложное высказывание, которое истинно тогда, когда истинна хотя бы одна из переменных x₁ и x₂, и ложно, когда они обе ложны. Логическая функция дизъюнкции имеет вид f=x₁+x₂. Для обозначения операции дизъюнкции используется также символ V.

Отрицание конъюнкции (операция Шеффера). Отрицание конъюнкции (функция И-НЕ) двух переменных x₁ и x₂ – сложное высказывание, ложное только при истинности обоих аргументов x₁ и x₂.

Отрицание дизъюнкции (операция Пирса (Вебба)). Отрицание дизъюнкции (функция ИЛИ-НЕ) двух переменных x₁ и x₂ – сложное высказывание, истинное только тогда, когда оба аргумента принимают ложное значение.

Сложение по модулю 2 (исключающее ИЛИ). Сложение по модулю 2 − это сложное высказывание, которое истинно только тогда, когда истинна только одна из переменных x₁ и x₂. Логическая функция ”сумма по модулю 2” имеет вид f=x₁x₂.

Импликация. Это высказывание, принимающее ложное значение только в случае, если x₁ истинно, а x₂ ложно.