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

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

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

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

Таблица 11.1

Из таблицы видно, что число различных двоичных наборов длины n x ₁, x ₂,…, x _n конечно и равно 2 ⁿ.

Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из 2 ⁿ строк, т.е. принимает 2 ⁿ значений. Общее число наборов из 0 и 1 длины 2 ⁿ равно. Это число равно числу различных функций алгебры логики n переменных.

Функция алгебры логики f (x ₁,…, x _i-1, x _i, x _i+1,…, x _n) зависит существенным образом от аргумента x _i, если существуют такие значения a ₁,…, a _i-1, a _i, a _i+1,… a _n переменных x ₁,…, x _i-1, x _i, x _i+1,…, x _n, что f (a ₁,…, a _i-1, 0, a _i+1,… a _n) ≠ f (a ₁,…, a _i-1,1, a _i+1,… a _n). В этом случае переменная x _i называется существенной, в противном случае – несущественной, или фиктивной. Очевидно, что постоянные функции не имеют существенных переменных.

Пример 1. f (x) – функция одной переменной. Ее возможные значения приведены в таблице (табл. 11.2).

Таблица 11.2

Выразим теперь все эти функции через значения аргументов x и y: f ₁ ≡ 1, f ₂ ≡ x ˅ y, f ₃ ≡ x, f ₄ ≡ x ˄ y, f ₅ ≡ x → y, f ₆ ≡ y → x, f ₇ ≡ x ˅ y, f ₈ ≡ x ↔ y, , f ₁₀ ≡ x ↔ y, , f ₁₂ ≡ y, , f ₁₄ ≡ x → y, f ₁₅ ≡ y → x, f ₁₆ ≡ 0.

Каждой формуле алгебры логики соответствует своя функция. Если формулы А и В равносильны, то соответствующие им функции равны: f _A(x ₁, x ₂,…, x _n) = f _B(x ₁, x ₂,…, x _n). Это значит, что при всех значениях переменных x ₁, x ₂,…, x _n значения f _A и f _B совпадают.

Логические функции имеют соответствующие названия. Для двух двоичных переменных существует шестнадцать логических функций, названия которых приведены ниже. На рис. 13.3 представлена таблица, в которой приведены логические функции F ₁, F ₂, F ₃, …, F ₁₆ двух логических переменных A и В.

Функция F ₁ = 0 и называется функцией константы нуля, или генератора нуля.

Таблица 11.3 Логические функции F ₁, F ₂, F ₃,… F ₁₆ двух аргументов А и В

Функция F ₂ = A & B называется функцией конъюнкции.

Функция называется функцией запрета по логической переменной А.

Функция F ₄ = А называется функцией повторения по логической переменной А.

Функция называется функцией запрета по логической переменной В.

Функция F ₆ = В называется функцией повторения по логической переменной В.

Функция называется функцией исключающее «ИЛИ».

Функция F ₈ = A v В называется функцией дизъюнкции.

Функция называется функцией Пирса.

Функция называется функцией эквиваленции.

Функция называется функцией отрицания (инверсии) по логической переменной В.

Функция F ₁₂ = B? A называется функцией импликации B? A.

Функция называется функцией отрицания (инверсии) по логической переменной А.

Функция F ₁₄ = A? B называется функцией импликации A? B.

Функция называется функцией Шеффера.

Функция F ₁₆ = 1 называется функцией генератора 1.

Среди перечисленных выше логических функций переменных можно выделить несколько логических функций, с помощью которых можно выразить другие логические функции. Операцию замены одной логической функции другой в алгебре логики называют операцией суперпозиции или методом суперпозиции. Например, функцию Шеффера можно выразить при помощи логических функций дизъюнкции и отрицания, используя закон де Моргана:

.

Логические функции, с помощью которых можно выразить другие логические функции методом суперпозиции, называются базовыми логическими функциями. Такой набор базовых логических функций называется функционально полным набором логических функций. На практике наиболее широко в качестве такого набора используют три логических функции: конъюнкцию, дизъюнкцию и отрицание. Если логическая функция представлена с помощью базовых функций, то такая форма представления называется нормальной. В предыдущем примере логическая функция Шеффера, выраженная через базовые функции, представлена в нормальной форме.

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

В настоящее время существует достаточно много программных продуктов, с помощью которых можно реализовать различные логические функции и форму их представления, например в виде таблиц истинности. Логические функции широко используются и в программе MS Excel. Для вызова этих функций необходимо выполнить следующие команды: [Кнопка Пуск – Программы – MS Office ХР – Microsoft Excel ] и далее команду: [Вставка – Функция]. В открывшемся окне (рис. 11.1) «Мастер функций – шаг 1 из 2», выберем: «Категория: „Логические“ и далее можно выбрать необходимую логическую функцию: ЕСЛИ, И, ИЛИ, ИСТИНА, ЛОЖЬ, НЕ. В этом же окне можно получить справку по каждой из этих функций.

Рисунок 11.1 Диалоговое окно «Мастер функций – шаг 1 из 2»

Как видно из рис. 11.1, в состав логических функций программы MS Excel входит функционально полный набор логических функций, состоящий из следующих логических функций: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание). Таким образом, с помощью функционально полного набора логических функций программы MS Excel можно реализовать другие функции. Логическая функция ЕСЛИ (импликация), также входящая в логические функции MS Excel, выполняет логическую проверку и в зависимости от результата проверки выполняет одно из двух возможных действий. В данной программе она имеет следующий формат: = ЕСЛИ (арг1;арг2;арг3), где арг1 – логическое условие; арг2 – возвращаемое значение при условии, что значение аргумента арг1 выполняется (ИСТИНА); арг3 – возвращаемое значение при условии, что значение аргумента арг1 не выполняется (ЛОЖЬ). Например, если в произвольную ячейку листа программы MS Excel ввести выражение «= ЕСЛИ (А1 = 5; „пять“; „не пять“)», то при вводе числа 5 в ячейку А1 и нажатии клавиши «Enter» в ячейке А1 автоматически будет записано слово «пять», при вводе любого другого числа в ячейку А1 в ней запишется слово «не пять». Как уже отмечалось, с помощью логических функций программы MS Excel можно представить другие логические функции и соответствующие им таблицы истинности.

Реализуем с помощью логических функций ЕСЛИ и И модифицированную таблицу истинности логической функции F = А & В (конъюнкции), состоящую из двух строк и трех столбцов, которая позволяет при изменении значений (0 или 1) логических переменных А и В автоматически устанавливать, например, в ячейке Е6 значение функции F = А & В, соответствующее значениям этих логических переменных. Для этого в ячейку Е6 введем следующее выражение: «=ЕСЛИ(И(С6;D6);1;0)», тогда при вводе в ячейки С6 и D6 значений 0 или 1 в ячейке Е6 будет выполняться логическая функция F = А & В. Результат этих действий представлен на рис. 11.2.

Рисунок 11.2 Реализация модифицированной таблицы истинности логической функции F = A & В