Основные логические функции

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

Основные объекты, изучаемые в этом разделе, — формулы алгебры логики, состоящие из букв, знаков логических операций и скобок. Буквы обозначают логические (двоичные) переменные, которые принимают только два значения -«ложь» и «истина». Знаки операций обозначают логические операции (логические связки). Каждая формула задает логическую функцию — функцию от логических переменных, которая сама может принимать только два логических значения.

Итак, пусть В = {0, 1} — бинарное множество, элементами которого являются формальные символы 1 и 0, не имеющие арифметического смысла и интерпретируемые как {«да», «нет»}, {«истинно», «ложно»} и т.д.

Алгебра логики — алгебра, образованная множеством В ={0, 1} вместе со всеми возможными операциями на нем.

Функцией алгебры логики (или логической функцией) f от п переменных f (х1, х2 …, хn) называется п-арная логическая операция на В, т.е.f: Вn —> В. Множество всех логических функций (логических операций) обозначается Р2, множество всех логических операций п переменных — Р2 (п).

Любую логическую функцию f (х1, х2 …, хn) можно задать таблицей истинности, в левой части которой выписаны все возможные наборы значений ее аргументов х1, х2 …, хn,, а правая часть представляет собой столбец значений функций, соответствующих этим наборам. Набор значений переменных, на котором функция принимает значение f=1, называется единичным набором функции f; множество всех единичных наборов — единичным множеством функции f. Аналогично набор значений, на котором / = 0, называется нулевым набором функции f, а множество нулевых наборов — нулевым множеством.

Число всех возможных различающихся наборов значений п переменных логической функции f (х1, х2 …, хn)  равно 2n (равно числу всех возможных двоичных векторов длины п). Число всех различных функций п переменных равно числу возможных расстановок нулей и единиц в столбце с 2n строками, т.е. |Р2 (п)|= 22n.

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

φ0 и φ3, — константы 0 и 1 соответственно. Значения этих функций не зависят от переменнойх, в таких случаях говорят, что переменная х является несущественной (фиктивной) для этих функций;

φ1(х) =х (повторение переменной).

Таблица 3.1

Множество всех логических функций двух переменных Р2(2) —  бинарных логических операций — представлено в табл. 3.2 своими таблицами истинности; |Р2(2)| = 16 функций, из которых шесть имеют фиктивные переменные.

Таблица 3.2

Продолжение таблицы

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

φ1(х1, х2) — конъюнкция (логическое умножение, операция И), обозначается:

х1 & х2, х1 · х2 (часто х1  х2), х1 Λ х2;

φ7(х1, х2) — дизъюнкция (логическое сложение, операция ИЛИ), обозначается:

 х1 ٧ х2, иногда х1 + х2 и т.п.

Логические функции трех и более переменных обычно задаются (наряду с таблицами истинности) также формулами бинарных операций. Например, выражение f (х1, х2, х3) = (х1 ٧ х2) → (х1 & х3) означает, что функция трех переменных f задана формулой, состоящей из символов этих переменных х1, х2, х3, над которыми выполняются одна унарная операция отрицания и три бинарные операции: дизъюнкция (٧), импликация (→) и конъюнкция (&).

Наиболее употребляемыми являются операции: ¬, ٧, &, →, ~, mod2, |, ↓. Значение любой логической формулы, содержащей знаки этих операций, можно вычислить для любого набора значений переменных, используя табл. 3.1 и 3.2.

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

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

Стандартный метод установления эквивалентности двух формул:

1) по каждой формуле восстанавливается таблица истинности;

2) полученные таблицы сравниваются по каждому набору значений переменных, (стандартный метод требует 2 • 2n вычислений).