Булевы функции, способы их задания. Элементарные функции. Алгебра логики, ее формулы

Определение. Пусть`х<sup>n</sup> ― n-мерный двоичный вектор. Функция f(`хⁿ),`х ⁿ Î E₂ⁿ, принимающая значения 0 и 1, называется булевой функцией или функцией алгебры логики.

По числу переменных n функции алгебры логики называют одноместными ( n = 1), двухместными ( n = 2 ) и т.д.

Способы представления функций алгебры логики f (хⁿ)зависят от представления всех наборов значений E₂ⁿ, которые принимает вектор её переменных`хⁿ . Наиболее просто все возможные наборы можно перечислить в таблице, где они располагаются в лексикографическом порядке по возрастанию соответствующих им двоичных чисел. Значения истинности функции f помещаются в отдельном столбце, который называется вектором истинности функции f (хⁿ). Вся конструкция называется таблицей истинности функции f (х ⁿ).

Рассмотрим элементарные функции, которые являются базовыми в алгебре логики.

1. Константы. Функции, определенные при любом числе переменных n и принимающие на всех наборах только одно значение истинности (0 или 1 ).

2. Одноместные функции, не являющиеся константами. Обозначив переменную в них через х, получим следующие таблицы истинности:

Определение. Функцию f₁ называют тождественной. Обозначают: f₁(х)= х. Функцию f₂называют отрицанием. Обозначают: f₂(х) = Ø х либо f₂(х) =`х.

3. Двуместные функции. Рассмотрим следующие двуместные функции, не являющиеся константами и которые нельзя свести к одноместным функциям. Переменные обозначим через х и у:

Определение. Функцию f₃называют конъюнкцией (логическим умножением). Способы обозначения следующие: f₃(х, у)= х & у , либо f₃(х, у) = ху , либо f₃(х, у) = х Ù у.

Функцию f₄называют дизъюнкцией (логическим сложением). Обозначают: f₄(х, у) = х Ú у .

Функцию f₅называют сложением по модулю 2. Обозначают: f₅(х, у) = х Å у .

Функцию f₆называют эквивалентностью. Обозначают как: f₆(х, у)= х º у либо f₆(х, у) = х « у.

Функцию f₁называют импликацией. Обозначают: f₁(х, у)= х® у либо х É у.

Функцию f₈называют штрих Шеффера. Обозначают: f₈(х, у)= х| у .

Функцию f₉называют функцией Вебба или стрелкой Пирса. Обозначают: f₉(х, у) = х ¯ у .

Определение. Символы Ø , &, Ú, Å, º, ®, |, ¯ ― называют логическими связками.

Для упрощения записи выражений приняты следующие соглашения о силе логических связок:

1) Ø― самая сильная (при отсутствии скобок применяется ранее других),

2) & ― вторая по силе,

3) связки Ú, Å, ®,|,¯равносильны,

4) связка ºсамая слабая.

Равносильные связки выполняются в порядке слева направо.

Функции 0, 1, f₁– f₉ называют элементарными. При помощи этих функций можно выразить более сложные n-местные функции алгебры логики (n ³3).

Определение. Соседними по переменной х_i называют пары булевых векторов`a=(a<sub>1</sub>..., a<sub>i-1</sub>, 0, a<sub>i+1</sub>,..., a<sub>n</sub>)и`b=(a₁,..., a_i-1, 1,a_i+1, ...,a_n), различающиеся только по одной переменной х_i. Существенными называются такие переменные х_i функции f(хⁿ), для которых существует хотя бы одна пара соседних по х_i наборов значений переменных`aи`b, на которой f(a)¹ f(b). Если же изменение только одной переменной не влечет изменение функции, то эта переменная называется фиктивной.

Фиктивные переменные могут быть исключены из формульного выражения функции. Очевидно, у констант все переменные являются фиктивными, у функций f₁― f₉ ― все переменные являются существенными.

Пример 1. Найти существенные и фиктивные переменные функции трех переменных f(х, у, z), таблица истинности которой приведена ниже.

Решение.

1. На наборах (0, 0, 0), (1, 0, 0), соседних по х, f(0, 0, 0)¹ f(1, 0, 0), следовательно, переменная х ― существенная.

2. Так как на всех парах наборов, соседних по у ― (0, 0, 0) и (0, 1, 0), (0, 0, 1)и (0, 1, 1), (1, 0, 0)и (1, 1, 0), (1, 0, 1)и (1, 1, 1)―функция принимает одинаковые значения, то у ― фиктивная переменная.

3. На наборах (0, 0, 0), (0, 0, 1), различающихся только значениями переменной z, f(0, 0, 0) ¹ f(0, 0, 1), следовательно, переменная z ― существенная.

Ответ: переменные х, z ― существенные, у ― фиктивная.

Для функции из примера 1 можно предложить формулу f(х, у, z) = x Å`z, в которую не входит фиктивная переменная у.

Наряду с элементарными, выделим и другие наиболее употребительные типы булевых функций.

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

Данные функции имеют очевидный логический смысл и простую физическую реализацию. К пороговым относятся обе одноместные функции, существенно зависящие от своей переменной ― тождественная функция f₁(х) = х и отрицание f₂(х) =`х. Среди двуместных функций пороговыми являются 4 функции: 1) конъюнкция f₃ = &, 2) дизъюнкция f₄= Ú, 3) штрих Шеффера f₈=| , 4) функция Вебба f₉ =¯.

Пороговый (скачкообразный) принцип действия рассмотренных двухместных функций f₃, f₄, f₈ , f₉позволяет ввести их аналоги на случай произвольных n - местных функций.

Определение. Обобщенными пороговыми называют следующие n - местные функции:

1) обобщенная конъюнкция &(х ⁿ), равная 1 при`х ⁿ = (1, 1, ..., 1)и 0 на всех остальных наборах,

2) обобщенная дизъюнкция Ú (х ⁿ), равная 0 при `х ⁿ = (0, 0, ..., 0)и 1 на всех остальных наборах,

3) обобщенная функция Шеффера | (`х <sup>n</sup>), равная 0 при `х ⁿ = (1, 1, ... , 1) и 1 на всех остальных наборах,

4) обобщенная функция Вебба ¯ (`х <sup>n</sup>), равная 1 при `х ⁿ =(0, 0, ... , 0)и 0 на всех остальных наборах.

Принципиальная схема функционального элемента, реализующего обобщенную конъюнкцию &(хⁿ), может быть представлена (рис.2.1 а) в виде последовательного соединения входов 1,...,n, соответствующих переменным (х₁,..., х_n). Сигнал от входа В к выходу&схемы передается только при одновременной подаче дополнительных сигналов на все входы 1,...,n. В противном случае цепь разрывается. Схема обобщенной дизъюнкции Ú(`хⁿ), может быть представлена (рис.1.1 б) в виде параллельного соединения входов 1,...,n. В ней для появления выходного сигнала достаточно его подачи хотя бы на один из входов.

а) б)

Рис.1.1

Применяя дополнительно отрицание к входам схемы, аналогично можно представить обобщенные функции Вебба (Рис.1.2 а) и Шеффера (Рис 1.2 б).

а) б)

Рис.1.2

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