б) Функции одной и двух переменных

Рассмотрение этого круга вопросов начнем с анализа простейшего случая, когда функция имеет лишь одну независимую переменную . Для этого случая общая таблица соответствия, совмещенная с таблицей одномерного двоичного логического пространства, имеет вид табл. 1.8.

Таблица 1.8

Здесь число точек логического пространства , число различных функций .

Эти четыре функции вместе с применяемыми для них обозначениями приведены в табл. 1.8. Других функций одного аргумента не существует.

Особенности функций состоят в следующем. Функции не изменяют своих значений при изменении значений аргумента. Эти функции называют функциями-константами. Для них мы будем применять обозначения .

Функция всегда имеет то же значение, что и аргумент для нее имеем очевидную запись .

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

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

Для случая двух независимых переменных общая таблица соответствия представлена табл. 1.9.

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

Заметим, что из 16 различных функций двух независимых переменных шесть встречались среди функций одной независимой переменной. К ним относятся две функции-константы , две функции повторения и две функции отрицания

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

Таблица 1.9.

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

Функция принимает значение 0 тогда и только тогда, когда оба аргумента имеют значение 0. Называют эту функцию дизъюнкцией и читают или .

Функцию называют импликацией, она принимает значение 0 тогда и только тогда, когда первый аргумент имеет значение 1, а второй — значение 0; при ее чтении применяют выражение «если , то или же «из следует .

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

Функция принимает значение 1 тогда и только тогда, когда оба аргумента имеют значение 1. Ее называют конъюнкцией и читают .

Функция носит название функции Шеффера (или штриха , она обращается в и только тогда, когда оба аргумента имеют значение 1.

Функцию называют исключенным ИЛИ; она обращается в 1, когда либо первый, либо второй аргумент равен 1 (но не оба вместе).

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

Функция «азывается функцией Даггера (или стрелкой , ее особенность состоит в том, что она обращается в 1 тогда и только тогда, когда оба аргумента равны 0.

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

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

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

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

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

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

Таблица 1.10

Подобным же образом можно показать, что

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

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

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

В самом деле, помимо установленных тождеств (1.4), (1.5), (1.6), освобождающих от необходимости применять импликацию и эквиваленцию, тем же приемом можно убедиться в справедливости тождеств

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

применение которых позволяет записать любую функцию одного и двух аргументов.

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

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