4. АЛГЕБРА ЛОГИКИ

4.1. Логические функции

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

Основным понятием алгебры логики является понятие высказывания. Высказыванием называется повествовательное предложение, о котором можно сказать, что в данный момент оно истинно или ложно, но не то и другое одновременно. Например, высказывание «Луна – это спутник Земли» истинно, а высказывание «микропроцессор разработан в 1905г.» ложно. «Истинность» или «ложность» предложения есть истинностное значение высказывания.

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

Каждому высказыванию ставят в соответствие переменную, равную «1», если высказывание истинно, и равную «0», если оно ложно. Таким образом, можно определить двухэлементное множество В и двоичные переменные, принимающие значения из В. Его элементы часто обозначают «0» и «1», однако они не являются числами в обычном смысле (хотя по некоторым свойствам и похожи на них). Наиболее распространенная интерпретация двоичных переменных – логическая: «да» – «нет», «истинно» (И) – «ложно» (Л). В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация обычно фиксируется явно: например, в языках программирования (Паскаль, Си и др.) вводится специальный тип переменной – логическая переменная, значения которой обозначаются «true» и «false». В дальнейшем изложении будем считать, что В = {0, 1}, рассматривая «0» и «1» как формальные символы, не имеющие арифметического смысла.

Алгебра, образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от п переменных называется n-арная операция на В. Логическая функция f(x₁,x₂, ... ,x_n) – это функция, принимающая значения «0», «1». Множество всех логических функций будем обозначать Р₂, множество всех логических функций п переменных – P₂(n).

Алгебра, образованная k-элементным множеством вместе со всеми операциями на нем, называется алгеброй k-значной логики, а n-арные операции на k-элементном множестве называются k-значными логическими функциями п переменных; множество всех k-значных логических функций обозначается
P_k .

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

Наборы, на которых функция f = l, часто называют единичными наборами функции f, а множество единичных наборов – единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f.

В табл. 4.1 наборы расположены в определенном порядке – лексико-графическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. При любом фиксированном упорядочении наборов логическая функция п переменных полностью определяется вектор-столбцом значений функции, т.е. 2ⁿ. Поэтому число |Р₂(п)| различных функций п переменных равно числу различных двоичных векторов длины 2ⁿ, т.е. 2^z , где z = 2ⁿ.

Переменная 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) при любых значениях остальных переменных, т. е. если изменение значения х_i в любом наборе значений x₁,x₂, ... , x_i-1, x_i, x_i+1, ... , x_n не меняет значения функции. В этом случае функция f(x₁, ..., x_n) по существу зависит от (п – 1) переменной, т. е. представляет собой функцию g(x₁, ..., x_i-1, x_i+1, .. , x_n) от (п – 1) переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из g введением фиктивной переменной, причем эти функции по определению считаются равными. Например, f(x₁, x₂, x₃) = g(x₁, x₂) означает, что при любых значениях x₁ и x₂ f = g независимо от значения x₃. Смысл удаления фиктивных переменных очевиден, поскольку они не влияют на значение функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению всякую функцию п переменных можно сделать функцией любого большего числа переменных. Поэтому любую конечную совокупность функций можно считать зависящей от одного и того же множества переменных, являющегося объединением множеств переменных всех взятых функций, что часто бывает удобно. В частности, равенство |Р₂(п)| = 2^z , где z = 2ⁿ справедливо при условии, что Р₂(п) содержит все возможные функции п переменных, в том числе и функции с фиктивными переменными.

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