Функции алгебры логики

Функцией алгебры логики или булевой функции от nпеременных f(x₁, x₂, ... , x_n) называется функция, принимающая значения из множества {0,1}, и аргументы которой также принадлежат множеству {0,1}.

Функция у = f(x₁, x₂, ... , x_n) задается своей таблицей истинности (таблица 3.3).

Таблица 3.3

Значения аргументов функции f заданы всевозможными наборами нулей и единиц, начиная от набора из всех нулей и кончая набором, когда все значения аргументов равны единице.

Так как f принимает значения 0 и 1, то ее можно описать перечислением наборов входных переменных, на которых f = 1 или f = 0. Так как в таблице столбцы x₁,…,x_n одни и те же, то их можно не писать. Получим компактное представление булевой функции, например, < 0011…10 >.

Поскольку каждая переменная может принимать два значения, х_i Î {0,1}, i = 1,n, число всевозможных наборов значений функции f от n переменных равно 2n . Таким образом, таблица истинности функции f от n переменных имеет 2nстрок.

В свою очередь на каждом из 2nнаборов значений аргументов функция f ( x₁, x₂, ... ,x_n ) также может принимать два значения - 0 или 1, f Î {0,1}.

Поэтому число различных функций от n переменных равно . Рассмотрим функции одной переменной, у = f(х). Их число равно = 4.

Это, в - первых, функции - константы - тождественный ноль, у = 0 и тождественная единица, у = 1. Их таблицы истинности приведены в таблицах 3.4 и 3.5, соответственно. Для обоих значений аргумента значение функции сохраняет постоянную величину.

Из двух оставшихся функций одна повторяет значение переменной, у = х. Вторая функция инвертирует значение переменной, у = х. Ее называют отрицанием переменной х. Таблицы истинности 3.6 и 3.7 определяют эти функции.

Таблица 3.4 Таблица 3.5 Таблица 3.6 Таблица 3.7

Рассмотрим функции от двух переменных у = f( x₁, x₂ ). Их число равно

= 2⁴ = 16.

Таблица истинности этих функций задана таблицей 3.8.

Таблица 3.8

Функции f₁ и f₁₆ - это функции-константы. Функция f₁ (x₁, x₂₎ = 0 называется тождественный ноль, а функция f₁₆(x₁, x₂₎ = 1 - тождественная единица.

Функция f₄ (x₁, x₂₎ = х₁ называется повторением аргумента x₁, а функция f₆ (x₁, x₂) = х₂ - повторением аргументаx₂.

Функция f₁₃ (x₁, x₂₎ = х₁ называется отрицанием переменной x₁ - "НЕ x₁", а функция f₁₁(x₁, x₂₎ = х₂ - отрицанием переменной х₂ - "НЕ x₂".

Функция f₂ (x₁, x₂₎ = х₁ L x₂ = х₁ × x₂ называется конъюнкциейх₁ и x₂. Еще ее называют функцией "И" или "логическое умножение".

Функция f₈ (x₁, x₂₎ = х₁ x₂ называется дизъюнкцией переменных х₁ и x₂. Другие ее названия - "ИЛИ", понимаемое в неразделительном смысле или "логическое сложение".

Функция f₁₄(x₁, х₂₎ = x₁ ® х₂ = x₁ v х₂ называется импликацией переменных x₁ и х₂.

Функция f₇( x₁, х₂₎ = x₁ Å х₂ = x₁ × х₂ v x₁ × х₂ называется сложение по модулю два. Она равна 1, когда значения ее аргументов различны, и 0, когда они равны. По другому ее называют "исключающее ИЛИ" либо "неравнозначность".

Функция f₁₀(x₁, х₂₎ = x₁ ~ х₂ = x₁ × х₂ Ú x₁ × х₂ называется эквиваленцией или равнозначностью. Она принимает значение 1, когда равны ее значения аргументов, и 0, когда они не равны.

Функция f₉(x₁, х₂₎ = x₁ х₂ = x₁ v х₂ называется стрелка Пирса.

Функция f₁₅(x₁, х₂₎ = x₁ х₂ = x₁ × х₂ называется штрих Шеффера. Оставшиеся три функции f₃, f₅ и f₁₂ специальных названий не имеют. Они легко выражаются через вышеперечисленные функции.

f₃(x₁, х₂₎ = x₁ × х₂

f₅(x₁, х₂₎ = x₁ × х₂

f₁₂(x₁, х₂₎ = x₁ Ú х₂

Таким образом, в булевых функциях мы оперируем с формальными переменными. Из переменных выкинута семантика, нас не интересует их смысловое значение. Это позволило придать булевым функциям однозначную математическую трактовку и использовать их для описания управляющих устройств.

Пример. Даны логические функции

f= и g = X1

Построить для них таблицы истинности.

X1	X2	X3							f	g=X1 X2

Таким образом, функции f и g на любых одинаковых наборах принимают одинаковые значения.