3_Алгебра_логики (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004)

3. Алгебра логики.

3.1 Понятие алгебры.

Функцию типа f: Mⁿ→M будем называть n - арной операцией на множестве М; n называется арностью операции f.

Алгеброй А называется совокупность < > множества М с заданными на нём операциями S={f₁₁, f₁₂,..., f_1k, f₂₁, f₂₂, ..., f_2l, ..., f_n1, ..., f_nm}

A=<M,S>, где М - называется основным или несущим множеством (или просто носителем) алгебры А. Вектор арностей алгебры называется её типом, совокупность операций S - сигнатурой алгебры.

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

В этой главе особую роль будет играть двухэлементное множество В и двоичные переменные, принимающие значения из В. Его элементы часто обозначаются 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространённая интерпретация переменных - логическая: 1 - истинно, 0 - ложно. В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация фиксируется явно: например, в языках программирования (Паскаль и др.) вводится специальный тип переменной - логическая переменная, значения которой обозначаются true и false.

Алгебра, образованная множеством В вместе с всеми возможными операциями на нём, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от n переменных называется n - арная операция на B. Множество всех логических функций обозначается P₂, множество всех логических функций от n переменных – P₂(n). Алгебра, образованная к - элементным множеством вместе со всеми операциями на нём, называется алгеброй к - значной логики, а n - арные операции на к - элементном множестве называются к - значными логическими функциями n переменных; множество всех к - значных функций обозначается P_k. Множество всех к - значных логических функций от n переменных обозначается P_k(n).

Всякая логическая функция n переменных может быть задана таблицей истинности, в левой части которой перечислены все 2ⁿ наборов переменных (т.е. двоичных векторов длины n), а в правой части - значения функций на этих наборах. Наборы, на которых функция f = 1, часто называют единичными наборами функции f, а множество единичных наборов - единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f.

В таблице истинности наборы расположены в определённом порядке - лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочением будем пользоваться и в дальнейшем. При любом фиксированном упорядочении наборов логическая функция n-переменных полностью определяется вектор - столбцом значений функции, т.е. 2ⁿ. Поэтому мощность множества |P₂(n)| т.е. число различных логических функций n переменных равно числу различных двоичных векторов длины 2ⁿ, т.е. N = .

Переменная x_i в функции f(x₁, x₂, ..., x_(i-1), x_i, x_(i+1), ..., x_n) называется несущественной (или фиктивной), если f(x₁, x₂, ..., x_(i-1), 0, , x_(i+1), ..., x_n) = f(x₁, x₂, ..., x_(i-1), 1, x_(i+1), ..., x_n) при любых значениях остальных переменных, если изменение значения x_i в любом наборе x₁,..., x_n не меняет значения функции.

В этом случае функция f(x₁,..., x_n) по существу зависит от n-1 переменной, т.е. представляет собой функцию g(x₁, x₂, ..., x_(i-1), x_(i+1), ..., x_n-1) от n-1 переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной x_i, а функция f получена из g введением фиктивной переменной, причём эти функции по определению считаются равными. Например, запись f(x₁, x₂, x₃)= g(x₁, x₂) означает, что при любых значения x₁ и x₂ f = g независимо от значения переменной x_3.

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

В частности, только это доказанное равенство |P₂(n)|= справедливо при условии, что P₂(n) содержит все возможные функции n переменных, в том числе и функции с фиктивными переменными.

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

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

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

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

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

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

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

Число всех возможных различающихся наборов значений п переменных логической функции f (х₁, х₂ ..., х_n) равно 2ⁿ (рав­но числу всех возможных двоичных векторов длины п). Число всех различных функций п переменных равно числу возмож­ных расстановок нулей и единиц в столбце с 2ⁿ строками, т.е. |Р₂ (п)|= 2²ⁿ.

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

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

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

Таблица 3.1

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

Таблица 3.2

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

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

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