§ 1.3. Исчисление высказываний

а) Общие сведения о задании логических функций

В этом параграфе мы будем рассматривать однородные двузначные логические функции

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

Построим таблицу (табл. 1.5), содержащую столбцов и строк; каждой строке приведем в соответствие одну из независимых переменных, а столбцы пронумеруем цифрами .

Таблица 1.5

столбцов

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

При практическом заполнении такой таблицы это удобно делать следующим образом: в первую строку (соответствующую ) слева направо вписываются пары (01), во вторую — четверки (0011), в третью — восьмерки (00001111) и т. д.

Каждый столбец построенной таким образом таблицы определяет одну из возможных комбинаций значений независимых переменных. Поэтому можно говорить, что ему соответствует одна точка -мерного двоичного (построенного на двухэлементном множестве М) логического пространства. Вся таблица (совокупность всех столбцов) содержит исчерпывающее описание всего -мерного двоичного логического пространства, состоящего из точек; номер столбца k может быть принят за символ точки этого пространства.

Рис. 1.2.

Для более наглядного представления -мерного двоичного логического пространства удобно рассматривать символы 0 и 1 как вещественные числа. Тогда, например, одномерному случаю соответствует геометрический образ, состоящий из двух точек числовой оси (рис. 1.2). Двумерному случаю будут соответствовать четыре вершины единичного квадрата (рис. 1.3), трехмерному случаю — вершины единичного куба (рис. 1.4), и вообще при таком рассмотрении -мерное двоичное логическое пространство представляет собой множество всех вершин -мерного единичного куба.

Задать какую-нибудь конкретную двузначную однородную логическую функцию независимых переменных означает получить указание о том, какое из двух вбзможных значений (0 или 1) принимает логическая переменная у в той или иной точке k двоичного мерного логического пространства (или на той или иной вершине -мерного куба).

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

Таблица 1.6

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

Можно указать удобный способ обозрения и нумерации всех этих функций.

Рис. 1.3.

Рис. 1.4.

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

Таблица 1.7

Эту таблицу удобно заполнять следующим образом: в первый столбец вписываются пары (01), во второй — четверки (ООП), в третий — восьмерки (00001111) и так далее). При этом распределение нулей и единиц в каждой строке, если ее читать справа налево, будет представлять собой двоичную запись номера функции, соответствующей этой строке. Таблицу такого типа будем называть общей таблицей соответствия.

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

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