Математические основы информатики: из неопубликованного

Продолжение. Cм. № 1, 2/2008 и курс лекций "Математические основы информатики" (№ 17-24/007)

Булевы и другие логические функции

Элементам математической логики была посвящена лекция 5 предложенного вашему вниманию курса “Математические основы информатики”. В ней мы затронули только самые начала этой очень большой и интересной области математических знаний.
И так же, как по школьной алгебре ни в коем случае нельзя составить образ современной алгебры, которую можно уподобить величайшему зданию фантастической архитектуры, о математической логике нельзя судить по тому весьма скромному изложению, которое представлено в упомянутой лекции. Но без этого фундамента не построить уходящего в высь здания. Поэтому мы кратко повторим опорные понятия той лекции.

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

Операциям над числами уже уделено гораздо большее внимание. Школьник не только учится числа складывать, умножать, вычитать и делить, но и рассматривает различные свойства этих операций, например, переместительный и сочетательный законы сложения и умножения. Выясняется, что для выполнения некоторых операций — в первую очередь вычитания и деления — натуральных чисел недостаточно. Приходится вводить новые числа — отрицательные и дробные. Операция извлечения корня требует введения иррациональных чисел. И снова изучать свойства тех или иных операций. Потом приходит понимание, что операции — это частный случай функций одной или нескольких переменных. Функции надо как-то записывать, возникает язык формальных выражений. И уже нередко забывается, что все начиналось с чисел, которые были содержательно связаны с окружающим миром. Изучаются преобразования алгебраических (или тригонометрических, или логарифмических) выражений, при этом уже не важно, какова числовая природа тех переменных, которые в этих выражениях фигурируют. Выражаясь терминами § 6, мы имеем дело с формальным языком, в котором согласно принятой грамматике языка осуществляется вывод одних выражений из других ¹.

Так вот, в лекции 5 вам были представлены первые персонажи математической логики — высказывания — и простейшие операции над ними. Рассмотрены свойства этих операций. Следуя изложенной выше логике изучения понятий, пора переходить к изучению функций от одной или нескольких переменных, принимающих только два значения. В математической логике эти значения принято обозначать как Истина и Ложь. Впрочем, нередко истину обозначают числом 1, а ложь — числом 0. Это во многих случаях оказывается удобнее, поскольку тогда с помощью последовательностей таких символов можно кодировать разнообразную информацию. А функции тем самым выступают средством формального описания обработки такой информации. Поэтому, в частности, в конце лекции 5, когда речь пошла о математическом моделировании работы сумматора, мы перешли именно на такое обозначение значений аргументов рассматривавшихся там функций. Естественно, что сами функции тоже могут принимать только два значения — те же самые 0 и 1. Вот о таких функциях и пойдет речь в двух ближайших параграфах.

§ 7. Алгебра булевых функций

Функции, аргументы которых принимают значения только 0 и 1 и которые сами принимают только такие же значения, называются булевыми (в честь Дж. Буля, заложившего основы формальной логики) ². Простейшие комбинаторные вычисления показывают, что различных наборов значений n переменных, принимающих только два значения, существует ровно 2ⁿ. Поэтому для каждой булевой функции можно составить полную таблицу всех ее значений. Вот примеры таблиц для двух таких функций от двух переменных x и y.

Таблица 1

Функцию f(x, y), представленную в табл. 1, записывают обычно как x & y и называют конъюнкцией переменных x и y. Другое название для нее — логическая операция И. Именно такой будет эта операция, если считать, что истинное высказывание кодируется единицей, а ложное — нулем. Функцию g(x, y) записывают обычно как и называют дизъюнкцией переменных x и y. Другое название для нее — логическая операция ИЛИ.

В табл. 2 представлены все 4 функции от одной переменой х.

Таблица 2

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

Функций от двух переменных уже 16. Действительно, двухсимвольных последовательностей, составленных из 0 и 1, имеется 4 (все они записаны в первом столбце табл. 1). Каждой такой последовательности можно поставить в соответствие 0 или 1. Две функции на двухсимвольных последовательностях, т.е. от двух аргументов, различаются, если они принимают разные значения хотя бы на одной такой последовательности. Всего же различных способов сопоставить четырем элементам один из двух символов имеется 2⁴, т.е. 16. Вот таблица для всех 16 булевых функций от двух аргументов; в них даны также употребительные обозначения этих функций вместо безликой буквы f и, кроме того, для функций двух переменных знак функции обычно пишут не слева от аргументов, а между ними — мы ведь издавна пишем x + y, а не +(x, y) ³.

Таблица 3

Приведем общепринятые названия некоторых из этих функций (не повторяя тех, которые названы ранее).

Функция x y называется импликацией.

Функция x y называется эквиваленцией.

Функция x y называется сложением по модулю 2.

Функция x | y называется операцией Шеффера (или штрихом Шеффера).

Функция x y называется операцией Пирса (или стрелкой Пирса).

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

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

Рис. 1. Функция как устройство по обработке данных

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

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

Рис. 2. Композиция f₂(f₁(x₁, x₂), x₃) функций f₁ и f₂

Получившееся устройство естественно рассматривать как функцию трех переменных x₁, x₂, x₃. Эту функцию записывают как f₂(f₁(x₁, x₂), x₃). Подстановку одной функции в другую вместо аргумента называют композицией данных функций.

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

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

Рис. 3. Композиция f₂(x₁, f₁(x₂, x₃) функций f₁ и f₂

Даже когда f₁ и f₂ — это одна и та же функция, результат подстановки может зависеть от выбора аргумента. Легко убедиться, например, что

— различные функции: они принимают разные значения для x₁ = 0, x₂ = 1, x₃ = 0. А вот если f₁ и f₂ — это конъюнкции, то результат подстановки не зависит от выбора аргумента: получающиеся функции (x₁ & x₂) & x₃ и x₁ & (x₂ & x₃) совпадают, в чем тоже несложно убедиться, вычислив значения каждой из них для всевозможных трехэлементных последовательностей из 0 и 1 (см. табл. 4). Аналогично можно убедиться в совпадении функций . Это позволяет не писать скобки в выражениях x₁ & x₂ & x₃ и вообще, поскольку любая их расстановка дает один и тот же результат. Именно так мы и будем поступать в дальнейшем.

Таблица 4

Фактически мы доказали равенство двух функций: f(x₁, x₂, x₃) = (x₁ & x₂) & x₃ и g(x₁, x₂, x₃) = x₁ & (x₂ & x₃). Равенство функций понимается в самом обычном смысле — функции равны, если они принимают одинаковые значения на любых одинаковых наборах значений аргументов. Напомним, что равенство функций принято называть тождеством.

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

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

Наше внимание пока было сосредоточено в основном на функциях от одной и двух переменных. Мы даже подсчитали их количество. Впрочем, нетрудно подсчитать количество булевых функций и от n переменных. Оно совпадает с количеством различных таблиц значений. В каждой такой таблице фигурирует 2ⁿ наборов значений аргументов. А для каждого набора есть две возможности для значения функции — либо 0, либо 1. Следовательно, различных таблиц можно составить . Именно столько имеется булевых функций от n переменных.

Для каждой из 16 булевых функций от двух переменных было введено свое обозначение (см. табл. 3). Перспектива заучить 256 обозначений для функций от трех переменных ужаснет, наверное, каждого. По счастью, мы уже обозначили некоторый выход из этой ситуации — выше мы обсудили, что функции от трех переменных можно получать как композицию функций от двух переменных. Вопрос тем самым сводится к тому, хватит ли нам функций от двух переменных, чтобы с помощью операции композиции (примененной, быть может, несколько раз) получить любую булеву функцию. Ответ на этот вопрос мы дадим в следующем параграфе. А сейчас рассмотрим некий особый аспект этого вопроса.

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

Назовем две формулы равносильными, если они задают одну и ту же функцию.

Формулу, в которой присутствуют только операции конъюнкции и отрицания, причем отрицание применяется только к переменным, называют элементарным конъюнктом. Вот примеры: , — элементарные конъюнкты, а формулы элементарными конъюнктами не являются. Если формула является дизъюнкцией нескольких элементарных конъюнктов, то говорят, что формула имеет дизъюнктивную нормальную форму. Отдельный элементарный конъюнкт также считается имеющим дизъюнктивную нормальную форму. Например, формулы имеют дизъюнктивную нормальную форму, а формулы , такой формы не имеют.

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

Теорема 1. Любая формула равносильна некоторой формуле в дизъюнктивной нормальной форме и некоторой формуле в конъюнктивной нормальной форме.

Доказательство проведем индукцией по числу операций в формуле.

База индукции. Если в формуле всего лишь одна операция, то формула имеет вид либо , либо x & y, либо x y, либо x y, либо x y, либо x y, либо x | y, либо x y, либо x y. В последних случаях законы 20–25 обеспечивают выполнение теоремы.

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

— где G и H — формулы, содержащие менее, чем n операций.

В случае 1) мы найдем формулы G₁ и G₂, эквивалентные формуле G и записанные в дизъюнктивной и конъюнктивной нормальных формах соответственно. Применение законов де Моргана и закона двойного отрицания немедленно показывает нам, что F можно представить в конъюнктивной и дизъюнктивной нормальных формах.

В случае 2) мы сначала найдем формулы G₁ и Н₁, эквивалентные формулам G и H соответственно и записанные в дизъюнктивной нормальной форме. Закон дистрибутивности позволяет тогда записать для F эквивалентную формулу в дизъюнктивной нормальной форме ⁴.

Получить для F конъюнктивную нормальную форму еще проще: надо для G и H просто записать эквивалентные им формулы в конъюнктивной нормальной форме.

Случай 3) рассматривается аналогично. Случаи 4)–9) сводятся к случаям 2) и 3) с помощью законов 20–25.

Теорема доказана.

Вопросы и задания

1. а) Проверьте выполнение законов де Моргана.

б) Проверьте выполнение тождеств 20–25.

2. Докажите тождества:

3. а) Преобразуйте в дизъюнктивную нормальную форму выражение

б) Преобразуйте то же выражение в конъюнктивную нормальную форму.

§ 8. Замкнутые и полные множества булевых функций

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

Теорема 2. Любая булева функция представима формулой в дизъюнктивной нормальной форме.

Доказательство. Пусть f(x₁, x₂, …, x_n) — какая-либо булева функция от переменных x₁, x₂, …, x_n. Мы построим нужное выражение в три шага.

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

Таблица 5

Шаг второй. Выберем в этой таблице те строки, в которых значение функции равно 1. Для каждой выбранной строки записываем конъюнкцию, составленную из тождественных функций и отрицания, по следующему правилу: если значение x_k равно 1, то пишем x_k, если значение x_k равно 0, то пишем . Например, для набора значений 100101 пишется такое выражение: . Если на этом шаге получилось более одного выражения, то каждое выражение заключается в скобки, после чего переходим к третьему шагу. Если же была выбрана только одна строка, то полученное выражение и есть нужное представление функции f(x₁, x₂, …, x_n).

Шаг третий. Все выражения, составленные на втором шаге, соединяются знаком дизъюнкции. Полученное выражение представляет исходную функцию f(x₁, x₂, …, x_n).

Из записи выражения для функции f(x₁, x₂, …, x_n) видно, что она получается композицией некоторого количества тождественных функций, отрицаний, конъюнкций и дизъюнкций.

Получается так, что промышленности достаточно освоить выпуск всего трех логических элементов — элемента НЕ, элемента И, элемента ИЛИ — и уже из них можно собирать схему для вычисления любой булевой функции. Впрочем, благодаря законам де Моргана можно обходиться всего двумя элементами, например, парой И и НЕ. А можно взять пару ИЛИ и НЕ. А вот пара И и ИЛИ для этих целей не годится.

Как узнать, будет ли тот или иной набор функций достаточным, чтобы с его помощью построить любую другую булеву функцию? Ответ на этот вопрос получен и носит название теоремы Пo'ста. Но прежде чем ее сформулировать, нам придется дать ряд определений.

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

Функция f(x₁, x₂, …, x_n) называется сохраняющей 0, если f(0, 0, …, 0) = 0. Ясно, что множество всех функций, сохраняющих 0, также является замкнутым. Этому множеству принадлежат функции &, , и 0, но не принадлежит ^–. Это множество мы будем обозначать М₀.

Функция f(x₁, x₂, …, x_n)) называется сохраняющей 1, если f(1, 1, …, 1) = 1. Легко понять, что множество всех функций, сохраняющих 1, является замкнутым. Этому множеству принадлежат функции &, и 1, но не принадлежит -. Это множество мы будем обозначать М₁.

Будем говорить, что набор чисел (a₁, a₂, …, a_n) (b₁, b₂, …, b_n), если неравенство ai bi выполнено для всех i. Функция f(x₁, x₂, …, x_n) называется монотонной, если из выполнения неравенства (a₁, a₂, …, a) (b₁, b₂, …, b_n) следует, что f(a₁, a₂, …, an) f(b₁, b₂, …, b_n). Легко проверить, что множество всех монотонных функций является замкнутым. Монотонными являются функции &, , 0 и 1. Множество монотонных функций обозначим через М₂.

Функция g(x₁, x₂, …, x_nn) называется двойственной к функции f(x₁, x₂, …, x_n), если g(x₁, x₂, …, x_n) = . Функция называется самодвойственной, если она двойственна сама к себе. Функция` самодвойственна, а функции & и таковыми не являются. Множество самодвойственных функций является замкнутым. Обозначим его как М₃.

Чтобы ввести еще один важный замкнутый класс булевых функций, нам потребуется еще одно представление булевой функции, отличное от дизъюнктивной или конъюнктивной нормальных форм. В пунктах а) и в) задания 2 к § 7 фактически показано, что отрицание и дизъюнкцию можно заменить на функции и 1. Кроме того, операцию & нередко записывают как умножение. Да по сути она ведь и есть умножение чисел 0 и 1. Тогда в формуле, записанной в дизъюнктивной (или конъюнктивной) нормальной форме, можно операции отрицания и дизъюнкции заменить на сложение по модулю два (операцию ) с 1, а конъюнкцию записать знаком умножения, который к тому же часто опускают. Например, формула & (у х) преобразуется в выражение (1 х) · (у х ух). Тождество, записанное в пункте г) задания 2 к § 7, показывает, что имеет место дистрибутивность умножения относительно сложения, т.е. можно раскрывать скобки. Тогда выражение (1 х) · (у х ух) преобразуется в у х ух ху х² хух. Законы коммутативности и идемпотентности для операции конъюнкции показывают, что ух = ху, а х² = х. Кроме того, пункт б) задания 2 к § 7 показывает, что сумма двух одинаковых слагаемых равна 0. Тем самым, исходная формула & (у х) преобразуется к виду у ху. По форме записи такая формула похожа на обычный многочлен от переменных в данном случае x и y. Ясно, что и любую формулу можно переработать в многочлен подобного вида. Многочлены от булевых переменных называются многочленами Жегалкина.

Фактически сейчас мы объяснили, что любая булева функция может быть представлена формулой в виде многочлена Жегалкина. В задании 4 к этому параграфу сформулировано утверждение о единственности такого представления. Это позволяет дать следующее определение: булева функция называется линейной, если представляющий ее многочлен Жегалкина не содержит произведений переменных. Например, функции 1 х и x y z являются линейными, а функция 1 х у ху линейной не является. Нетрудно видеть, что композиция линейных функций снова является линейной функцией. Это означает, что множество линейных функций замкнуто. Множество линейных функций обозначим М₄.

Каждое из построенных замкнутых множеств не совпадает с множеством всех булевых функций — ведь для каждого из них мы привели пример булевой функции, не принадлежащей ему. Это означает, что, беря функции только из одного какого-то множества М₀–М₄, мы не можем сконструировать любую наперед заданную булеву функцию. В частности, мы доказали, что, используя только конъюнкции и дизъюнкции, нельзя сконструировать любую булеву функцию.

Множество функций называется полным, если, применяя несколько раз композицию функций, можно из функций данного множества построить любую функцию. К примеру, теорема 2 утверждает, что множество, состоящее из конъюнкции, дизъюнкции и отрицания, является полным. Позже мы убедились, что множество, состоящее из конъюнкции, сложения по модулю 2 и константной функции 1, также является полным. А никакое замкнутое множество, отличное от множества всех функций, полным не является. Теперь мы можем сформулировать теорему Поста, которая позволяет для любого множества функций сказать, является оно полным или нет.

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

Конечно, может оказаться так, что всеми свойствами с приставкой не- обладает какая-нибудь одна функция. Например, такой функцией является операция Пирса. В задании 5 мы предлагаем это проверить. Следовательно, любая функция может быть получена из одной только операции Пирса. Иными словами, можно выпускать только один какой-то логический элемент и из него конструировать все вычислительные устройства.

Но на самом деле уменьшение разнообразия выпускаемых элементов вовсе не так экономично, как это может показаться на первый взгляд. Дело в том, что для получения нужной схемы с использованием одного универсального элемента может потребоваться гораздо больше элементов, чем при применении элементов нескольких видов. Гораздо эффективнее оказывается иметь готовые логические элементы (микросхемы) разных видов и уже из них собирать сложные схемы. Кроме того, одна и та же функция может быть реализована разными выражениями и, значит, разными схемами. Общей теории построения схем с наименьшим числом элементов на сегодняшний день, однако, не существует, хотя и есть отдельные алгоритмы, позволяющие упрощать схемы. Большой вклад в создание таких алгоритмов внесли российские ученые Ю.И. Журавлев, С.В. Яблонский и др.

Вопросы и задания

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

2. Функция f(x, y, z) имеет следующую таблицу значений.

Таблица 6

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

3. а) Проверьте, что множество монотонных функций замкнуто.

б) Докажите, что множество самодвойственных функций замкнуто.

4. Докажите, что представление функции многочленом Жегалкина единственно.

5. а) Проверьте, что операция Пирса не принадлежит ни одному из классов М₀–М₄.

б) Выразите отрицание, конъюнкцию и дизъюнкцию через операцию Пирса.

6. а) Проверьте, что операция Шеффера не принадлежит ни одному из классов М₀–М₄.

б) Выразите отрицание, конъюнкцию и дизъюнкцию через операцию Шеффера.

§ 9. Что сказать, когда сказать нечего

В двузначной логике весь мир четко раскрашен в два цвета — цвет истины и цвет лжи. В жизни это далеко не всегда так. Речь идет, конечно, не о каких-то интригах или борьбе разведки с контрразведкой. Просто нередко оказывается так, что значение той или иной логической переменной (предиката) оказывается неопределенным. Вот пример такого случая.

Пусть в базе данных имеется таблица, содержащая сведения о некоторых гражданах:

Таблица 7

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

Имя = Николай И Отчество = Александрович.

СУБД выдаст однозначный ответ — телефон гражданина Романова. Но у вас может остаться неудовлетворенность — вдруг у Фомина отчество тоже Александрович, и именно о нем вас спрашивали. Просто его отчество вам по каким-то причинам неизвестно.

Конечно, можно составить запрос, в котором будет фигурировать только имя. Тогда вы получите телефоны троих: Романова, Соколова и Фомина.

Если записей в базе данных не очень много, то дальше можно “вручную” отобрать те, которые представляются полезными. Впрочем, если записей полтора десятка, то с базой данных и вообще связываться не стоит. Вот когда счет идет на сотни…

Надо отдать должное разработчикам современных баз данных (довольно типичным представителем которых является БД Access) — они постарались предоставить пользователю средства, позволяющие разруливать подобные ситуации. Для этого полю таблицы (т.е. на самом деле переменной, которая это поле представляет) разрешается принимать особое значение, которое называется “неопределенность”. В БД Access это значение обозначается как Null. Впрочем, это мы в нашем человеческом восприятии интерпретируем данное значение как некую неопределенность, которая в принципе подразумевает некое точное значение (каждому ясно, что у Фомина какое-то отчество, конечно, есть), но указать его мы не можем. Для компьютера значение “неопределенность” по большому счету ничем не лучше (но и не хуже) значений Истина и Ложь. Просто вместо двузначной логики появилась логика трехзначная. И соответствующие логические функции будут не булевыми (т.е. двузначными), а трехзначными. Это новое третье значение мы будем обозначать буквой U (от англ. undefined). И каждая переменная тоже будет принимать три значения: 0, 1 и U.

Как же выглядят операции в трехзначной логике? Ясно, что на значениях 0 и 1 для любых переменных они должны принимать те же значения, что и в булевом случае. Довольно естественно определить операцию отрицания — для нового значения U его отрицание конечно же снова является U. Кроме того, такое определение позволяет для операции отрицания сохранить тождество 13 (закон двойного отрицания) ⁵.

Для конъюнкции, если один из операндов равен 0 (т.е. ложен), то и результат равен 0 вне зависимости от значения второго операнда.
С точки зрения логической интерпретации это вполне естественно: даже если когда-то окажется, что второй операнд — истинное высказывание, все равно результатом будет Ложь. Конъюнкцию 1 и U, а также U и U естественно считать неопределенностью, т.е. U. Аналогичная содержательная интерпретация дизъюнкции приводит к выводам, которые зафиксированы в 3-м и 4-м столбцах табл. 8 ⁶.

Таблица 8

Операции и мы определим, исходя из тождеств 20 и 21 ⁷. Нетрудно проверить, что в этом случае таблица значений для них выглядит так, как показано в 5-м и 6-м столбцах табл. 8. Зато функция = в силу данного нами определения равенства функций имеет таблицу значений, представленную седьмым столбцом в той же табл. 8. Как видите, здесь равенство функций и логическая равносильность уже не совпадают.

Таблица 9

Совершенно так же, как для булевых функций, можно подсчитать, что количество различных трехзначных функций от n аргументов равно . Скажем, функций от двух аргументов будет уже не 16, а 3⁹ = 19 683. В табл. 9 мы приве%