Пусть в экономике существуют l продуктов. Присвоим каждому из товаров индекс \(h,\) \({h = 1},\ldots,l\). Набор из l потребительских благ обозначим через \(x\). Потребительский набор товаров, или потребительская корзина, \(x\) – это произвольный вектор, состоящий из неотрицательных действительных чисел. Множество потребляемых продуктов, или потребительское множество X – это совокупность всех \(x\). Оно представляет собой весь неотрицательный вещественный ортант1 \(R_{+ {}^{l}}\).
В дальнейшем анализе будем опираться на важные информационные предпосылки. Мы полагаем наличие полноты информации хотя бы у одного хозяйствующего субъекта или у всех экономических агентов в совокупности. Другими словами, не допускается ситуация, когда массивы или элементы информации не доступны ни одному из субъектов в экономике. В данном разделе будет использоваться еще более сильное предположение о полной рациональности всех экономических агентов. Тем самым, исключается ограниченная рациональность. Под ограниченной рациональностью понимается отсутствие информации у субъекта о полном наборе возможных вариантов собственных поступков, а также действий остальных контрагентов и внешних сил или же его незаинтересованность в использовании имеющейся информации в планировании своего поведения.
Использование аппарата математической логики позволяет рассматривать базовые предпосылки рациональности потребительских предпочтений не как аксиомы, а в качестве подлежащих доказательству утверждений. Это дает возможность выстроить как ординалистскую теорию потребительского выбора, так и теорию принятия общественных решений на едином, мощном фундаменте.
Пусть \(x_{1}\), \(x_{2}\), \(x_{3}\) – это варианты организации хозяйственной деятельности, а \(\succsim_{i}\) – упорядочение этих альтернатив некоторым индивидуумом, которого мы обозначим индексом i. Выражение \(x_{1}\succsim_{i}x_{2}\) означает, что альтернатива \(x_{1}\) является для него предпочтительной или безразличной по отношению к \(x_{2}\). Присвоим значение 1 выбранной альтернативе, а 0 – отвергнутой. Тогда отношение \(x_{1}\succsim_{i}x_{2}\) можно представить как булеву функцию, заданную таблично (табл. 1.2).
Таблица 1.2. Отношение предпочтения как булева функция
| \(x_{1}\) | \(x_{2}\) | \(x_{1}\succsim_{i}x_{2}\) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Функцию \(f\left( {x_{1},\ldots,x_{n}} \right)\), независимые переменные которой определены на множестве \({E^{2} = \{}0,1\}\) (\(x_{i} = \alpha_{i}\), где \(\alpha_{i}\in E^{2},{i = 1},\ldots,n\)), называют булевой функцией, или функцией алгебры логики2, если она принимает значения \(f{\left( {\alpha_{1},\ldots,\alpha_{n}} \right) = \delta_{i}},{i = 0,1},\ldots,{2^{n} - 1}\), так же на множестве \(E^{2}\).
Очевидно, что множество булевых значений \(\alpha_{1},\ldots,\alpha_{n}\) конечно и саму функцию можно задать, расположив наборы переменных в лексикографическом порядке, т.е. по возрастанию, и указав ее значения на каждом наборе коэффициентов (табл. 1.3).
Таблица 1.3. Табличное представление булевой функции
| \(x_{1}\) | \(x_{2}\) | … | \(x_{n - 1}\) | \(x_{n}\) | \(f\left( {x_{1},\ldots,x_{n}} \right)\) |
| 0 | 0 | … | 0 | 0 | \(\delta_{0}\) |
| 0 | 0 | … | 0 | 1 | \(\delta_{1}\) |
| 0 | 0 | … | 1 | 0 | \(\delta_{2}\) |
| … | … | … | … | … | … |
| \(\alpha_{1}\) | \(\alpha_{2}\) | … | \(\alpha_{n - 1}\) | \(\alpha_{n}\) | … |
| … | … | … | … | … | … |
| 1 | 1 | … | 1 | 1 | \(\delta_{2^{n} - 1}\) |
Приведем примеры булевых функций одной и двух переменных (табл. 1.4-1.5).
Таблица 1.4. Булевы функции одной переменной
| x | 0 (тождественный нуль) | 1 (тождественная единица)3 | x (тождественная функция) | \(\overline{x}\) (отрицание, или инверсия) |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Константы 0 и 1 – это две особенные функции, которые не имеют существенных переменных. Некоторая, i-я булева переменная является существенной, если найдется такой набор значений остальных переменных \(\left( {\alpha_{1},\ldots,\alpha_{i - 1},\alpha_{i + 1},\ldots,\alpha_{n}} \right)\), что изменение i-й переменной при неизменных остальных переменных приводит к изменению значения функции4: \(f\left( {\alpha_{1},\ldots,\alpha_{i - 1},0,\alpha_{i + 1},\ldots,\alpha_{n}} \right)\neq f\left( {\alpha_{1},\ldots,\alpha_{i - 1},1,\alpha_{i + 1},\ldots,\alpha_{n}} \right)\).
Таблица 1.5. Элементарные булевы функции двух переменных
| \(x_{1}\) | \(x_{2}\) | \(f_{1}\) | \(f_{2}\) | \(f_{3}\) | \(f_{4}\) | \(f_{5}\) | \(f_{6}\) | \(f_{7}\) |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
Функция логического умножения, или конъюнкция, \(f_{1}{\left( {x_{1},x_{2}} \right) = {x_{1} \land x_{2}} = x_{1}}\bullet{x_{2} = x_{1}}x_{2}\) отвечает на вопрос, является ли истинным утверждение, состоящие из двух положений и совпадающее как с одним из них, так и с другим. Очевидно, что если хотя бы одно из утверждений, составляющих данное, является ложными, то и итоговое утверждение будет ложным. Итоговое утверждение будет истинным, только если оба из его составляющих будут верными.
Функция логического сложения, или дизъюнкция, \(f_{2}{\left( {x_{1},x_{2}} \right) = x_{1}}\vee x_{2}\) отвечает на вопрос, является ли истинным утверждение, состоящие из двух положений и совпадающее хотя бы с одним из них. Очевидно, что если оба из утверждений, составляющих данное, являются ложными, то и итоговое утверждение будет ложным. Если хотя бы одно из утверждений, составляющих данное, верно, то и итоговое утверждение будет истинным.
Логическая функция суммы по модулю два \(f_{3}{\left( {x_{1},x_{2}} \right) = x_{1}}\bigoplus x_{2}\) определяется по аналогии с тем же алгебраическим понятием – как остаток от деления \(\left( {x_{1} + x_{2}} \right)\) на 2.
Эквивалентность \(f_{4}{\left( {x_{1},x_{2}} \right) = x_{1}}\qquad{x_{2} = x_{1}}\equiv x_{2}\) подразумевает истинное утверждение, только если значения переменных совпадают.
При определении импликации5 \(f_{5}{\left( {x_{1},x_{2}} \right) = x_{1}}\rightarrow x_{2}\) учитывается, что, поскольку ложное утверждение не несет в себе никакой позитивной информации, из неверного утверждения может следовать как ложь, так и истина.
Последние булевы функции двух переменных – это штрих Шеффера \(f_{6}{\left( {x_{1},x_{2}} \right) = {x_{1}/x_{2}}}\) и стрелка Пирса \(f_{7}{\left( {x_{1},x_{2}} \right) = x_{1}}\downarrow x_{2}\), которые представляют собой соответственно отрицание конъюнкции \(f_{6}{\left( {x_{1},x_{2}} \right) = \overline{x_{1}\land x_{2}}}\) и дизъюнкции \(f_{7}{\left( {x_{1},x_{2}} \right) = \overline{x_{1}\vee x_{2}}}\).
Свойства элементарных булевых функций позволяют сформулировать базовые законы формальной логики (табл. 1.6).
Доказательство данных законов осуществляется путем обоснования эквивалентности соответствующих формул6, т.е. равенства реализуемых ими булевых функций7.
Таблица 1.6. Элементарные булевы функции и законы формальной логики
| Название закона | Формулировка закона |
|
Ассоциативности: а) конъюнкции; б) дизъюнкции; в) суммы по модулю два |
а) \({x_{1} \land \left( {x_{2} \land x_{3}} \right)} = {\left( {x_{1} \land x_{2}} \right) \land x_{3}}\); б) \(x_{1}\vee{\left( {x_{2}\vee x_{3}} \right) = \left( {x_{1}\vee x_{2}} \right)}\vee x_{3}\); в) \(x_{1}\bigoplus{\left( {x_{2}\bigoplus x_{3}} \right) = \left( {x_{1}\bigoplus x_{2}} \right)}\bigoplus x_{3}\) |
|
Коммутативности: а) конъюнкции; б) дизъюнкции; в) суммы по модулю два |
а) \({x_{1} \land x_{2}} = {x_{2} \land x_{1}}\); б) \(x_{1}\vee{x_{2} = x_{2}}\vee x_{1}\); в) \(x_{1}\bigoplus{x_{2} = x_{2}}\bigoplus x_{1}\) |
|
Дистрибутивности – а) конъюнкции относительно дизъюнкции; б) дизъюнкции относительно конъюнкции |
а) \(\left( {x_{1}\vee x_{2}} \right) \land x_{3}\) \({}\left( {x_{1} \land x_{3}} \right)\vee\left( {x_{2} \land x_{3}} \right)\); б)\(\left( {x_{1} \land x_{2}} \right)\vee x_{3}\) \({}{\left( {x_{1}\vee x_{3}} \right) \land \left( {x_{2}\vee x_{3}} \right)}\) |
| Двойного отрицания | \(\overline{\overline{x}} = x\) |
| Де Моргана | \({\overline{x_{1}\land x_{2}} = {\overline{x}}_{1}}\vee{\overline{x}}_{2}\); \(\overline{x_{1}\vee x_{2}} = {{\overline{x}}_{1} \land {\overline{x}}_{2}}\) |
| Поглощения |
\(x_{1}\vee{\left( {x_{1} \land x_{2}} \right) = x_{1}}\); \({x_{1} \land \left( {x_{1}\vee x_{2}} \right)} = x_{1}\) |
| Противоречия8 | \({x \land \overline{x}} = 0\) |
| Исключенного третьего | \(x\vee{\overline{x} = 1}\) |
| Идемпотентности | \({x \land x} = x\); \(x\vee{x = x}\) |
|
Операций с константой: а) умножения на константу; б) сложения с константой |
а) \({x \land 1} = x\), \({x \land 0} = 0\); б) \(x\vee{1 = 1}\), \(x\vee{0 = x}\) |
Пример 1.1. Закон исключенного третьего9: \(x\vee{\overline{x} = 1}\)
| x | \(\overline{x}\) | \(x\vee\overline{x}\) |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
Итак, формула \(x\vee\overline{x}\) эквивалентна тождественной единице.
Пример 1.2. Закон де Моргана: \({\overline{x_{1}\land x_{2}} = {\overline{x}}_{1}}\vee{\overline{x}}_{2}\)
| \(x_{1}\) | \(x_{2}\) | \(x_{1} \land x_{2}\) | \(\overline{x_{1}\land x_{2}}\) | \({\overline{x}}_{1}\) | \({\overline{x}}_{2}\) | \({\overline{x}}_{1}\vee{\overline{x}}_{2}\) |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Итак, \({\overline{x_{1}\land x_{2}} = {\overline{x}}_{1}}\vee{\overline{x}}_{2}\), поскольку левая и правая формулы реализуют эквивалентные булевы функции. Остальные свойства элементарных булевых функций доказываются аналогично10.
Итак, упорядочение \(x_{1}\succsim_{i}x_{2}\) – это отношение следования, или импликации, \(x_{1}\rightarrow x_{2}\). Действительно, в отношении упорядоченности \(x_{1}\) «следует за» \(x_{2}\).
Обычно от ординалистской, или порядковой, функции предпочтений экономического субъекта требуют, чтобы она представляла собой (отличное от константы) отношение полного предпорядка11, т.е. удовлетворяла следующим свойствам рационального выбора.
Первое свойство – это сравнимость любых возможных вариантов организации хозяйственной деятельности, или полнота данного множества. Для любых вариантов \(x_{1}\) и \(x_{2}\) верно \(\left( {x_{1}\succsim_{i}x_{2}} \right)\vee\left( {x_{2}\succsim_{i}x_{1}} \right)\):
\(\left( {x_{1}\succsim_{i}x_{2}} \right)\vee{\left( {x_{2}\succsim_{i}x_{1}} \right) = 1}.(1.1)\)
Выкладки, приведенные в табл. 1.7, доказывают полноту предпочтений.
Таблица 1.7. Полнота предпочтений
| \(x_{1}\) | \(x_{2}\) | \(x_{1}\succsim_{i}x_{2}\) | \(x_{2}\succsim_{i}x_{1}\) | \(\left( {x_{1}\succsim_{i}x_{2}} \right)\vee\left( {x_{2}\succsim_{i}x_{1}} \right)\) |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
В частности, при \(x_{1} = x_{2}\) следствием полноты предпочтений становится их рефлексивность (табл. 1.8):
\(x_{1}\succsim_{i}{x_{1} = 1}.\)
Таблица 1.8. Рефлексивность предпочтений
| \(x_{1}\) | \(x_{2} = x_{1}\) | \(x_{1}\succsim_{i}x_{1}\) |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Второе свойство – это транзитивность отношения упорядоченности. Формула \({\left( {x_{1}\succsim_{i}x_{2}} \right) \land \left( {x_{2}\succsim_{i}x_{3}} \right)}\rightarrow\left( {x_{1}\succsim_{i}x_{3}} \right)\) верна для любых наборов \(x_{1}\), \(x_{2}\), \(x_{3}\):
\({\left( {x_{1}\succsim_{i}x_{2}} \right) \land \left( {x_{2}\succsim_{i}x_{3}} \right)}\rightarrow{\left( {x_{1}\succsim_{i}x_{3}} \right) = 1.}(1.2)\)
Транзитивность предпочтений доказана в табл. 1.9.
Таблица 1.9. Транзитивность предпочтений
| \(x_{1}\) | \(x_{2}\) | \(x_{3}\) | \(x_{1}\succsim_{i}x_{2}\) | \(x_{2}\succsim_{i}x_{3}\) |
\(\left( {x_{1}\succsim_{i}x_{2}} \right) \land {}\) \(\left( {x_{2}\succsim_{i}x_{3}} \right)\) |
\(\left( {x_{1}\succsim_{i}x_{3}} \right)\) |
\(\left( {x_{1}\succsim_{i}x_{2}} \right) \land {}\) \(\left( {x_{2}\succsim_{i}x_{3}} \right)\rightarrow\left( {x_{1}\succsim_{i}x_{3}} \right)\) |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Свойства (1.1) – (1.2) выполняются только для трех булевых функций двух переменных – тождественной единицы и импликаций \(x_{1}\rightarrow x_{2}\), \(x_{2}\rightarrow x_{1}\). Поэтому, если переменные не являются фиктивными, т.е. отношение предпочтения отлично от константы, то свойства (1.1) – (1.2) можно использовать в качестве аксиом рационального упорядочения хозяйственных альтернатив.
Обозначим через \(\succ_{i}\) отношение строгого предпочтения. Оно означает, что должны одновременно выполняться соотношения \(x_{1}\succsim_{i}x_{2}\) и \(\overline{x_{2}\succsim_{\overset{˙}{i}}x_{1}}\), или в формальной записи:
\(x_{1}\succ_{i}{x_{2} = {\left( {x_{1}\succsim_{i}x_{2}} \right) \land \left( \overline{x_{2}\succsim_{\overset{˙}{i}}x_{1}} \right)}}.\)
Доказательство этого свойства отношения строго предпочтения приведено в табл. 1.10.
Таблица 1.10. Отношение строго предпочтения
| \(x_{1}\) | \(x_{2}\) | \(x_{1}\succ_{i}x_{2}\) | \(x_{1}\succsim_{i}x_{2}\) | \(x_{2}\succsim_{i}x_{1}\) | \(\overline{x_{2}\succsim_{\overset{˙}{i}}x_{1}}\) |
\(\left( {x_{1}\succsim_{i}x_{2}} \right) \land {}\) \(\left( \overline{x_{2}\succsim_{\overset{˙}{i}}x_{1}} \right)\) |
| 0 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
Очевидно, что, если \(x_{1}\) хуже, чем \(x_{2}\), то \(x_{2}\) лучше, чем \(x_{1}\):
\(\left( \overline{x_{1}\succsim_{i}x_{2}} \right)\rightarrow{\left( {x_{2}\succ_{i}x_{1}} \right) = 1.}(1.3)\)
Кроме того, аналогично нестрогому отношению предпочтения (1.2), легко доказать, что строгое предпочтение транзитивно:
\({\left( {x_{1}\succ_{i}x_{2}} \right) \land \left( {x_{2}\succ_{i}x_{3}} \right)}\rightarrow{\left( {x_{1}\succ_{i}x_{3}} \right) = 1.}(1.4)\)
Обозначим через \(\sim_{i}\) отношение безразличия. Оно означает, что одновременно должны выполняться соотношения \(x_{1}\succsim_{i}x_{2}\) и \(x_{2}\succsim_{i}x_{1}\):
\(x_{1}\sim_{i}{x_{2} = {\left( {x_{1}\succsim_{i}x_{2}} \right) \land \left( {x_{2}\succsim_{i}x_{1}} \right)}}.\)
Доказательство этой характеристики отношения безразличия приводится в табл. 1.11.
Таблица 1.11. Отношение безразличия
| \(x_{1}\) | \(x_{2}\) | \(x_{1}\sim_{i}x_{2}\) | \(x_{1}\succsim_{i}x_{2}\) | \(x_{2}\succsim_{i}x_{1}\) | \(\left( {x_{1}\succsim_{i}x_{2}} \right) \land \left( {x_{2}\succsim_{i}x_{1}} \right)\) |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Обозначим через S множество допустимых альтернатив и назовем его предъявлением. Пусть C(S) – множество таких альтернатив \(x_{1}\) в S, что для каждого \(x_{2}\) в S \(x_{1}\succsim_{i}x_{2}\). Несложно проверить, что:
\(x_{1}\succ_{i}x_{2}\Longleftrightarrow x_{1}–\mathit{единственный}\mathit{элемент}вC\left( \left\{ {x_{1},x_{2}} \right\} \right).(1.5)\)
Очевидно, \({\left( \overline{x_{1}\succsim_{\overset{˙}{i}}x_{2}} \right) \land \left( \overline{x_{2}\succsim_{\overset{˙}{i}}x_{1}} \right)}\rightarrow\left( {x_{1}\succ_{i}x_{2}} \right)\), а значит, \(C(\left\{ {x_{1},x_{2}} \right\}{) = \left\{ {x_{1},x_{2}} \right\}}\). Итак, знание C(S), где \(S = \left\{ {x_{1},x_{2}} \right\}\) – множество, состоящее из двух альтернатив, полностью определяет отношения \(\succ_{i}\) и \(\sim_{i}\), а значит, и \(\succsim_{\overset{˙}{i}}\). Но, по определению, знание \(\succsim_{\overset{˙}{i}}\) полностью определяет функцию выбора C(S) для всех возможных наборов альтернатив S. Итак, выбор в произвольном множестве определяется выбором во всевозможных соответствующих ему двухэлементных подмножествах12.
Здесь и далее будем обозначать через \(R_{+ {}^{l}}\) неотрицательный ортант l-мерного пространства действительных чисел: \(R_{{+ {}^{l}}\equiv{\{{x\in R^{l},x\geqslant 0}\}}}\).↩︎
См.: Редькин Н.П. Дискретная математика. 2-е изд. – СПб.: Лань, 2006. В силу того, что каждая переменная \(x_{i}\) может принимать два значения {0, 1}, количество возможных значений аргумента, состоящего из n переменных, равно \(2^{n}\).↩︎
Булевская тождественная единица известна как один из аристотелевских законов формальной логики – «закон тождества», который утверждает, что всякая мысль обязана иметь строго определенный смысл (см.: Нуреев Р.М. Курс микроэкономики. – М.: Норма, 2008).↩︎
В противном случае переменная называется несущественной, или фиктивной.↩︎
С данной функцией непосредственно связан логический закон достаточного основания (Лейбница), который требует, чтобы каждое верное утверждение обосновывалось другими, справедливость которых была уже прежде установлена (Пригожин И., Стенгерс И. Порядок из хаоса. – М.: Едиториал УРСС, 2003).↩︎
Формулой над некоторым множеством булевых функций M называется такая функция алгебры логики, аргументом которой является либо булева переменная, либо значение некоторой логической функции из данного множества M.↩︎
Булевы функции равны, когда каждая из них представляет собой другую с точностью до изъятия и/или добавления фиктивной переменной.↩︎
Закон противоречия, известный еще со времен Аристотеля, гласит, что два противоположных суждения о едином предмете не могут быть справедливыми одновременно. На данном законе основан, в частности, принцип доказательства утверждения от противного \((\left( {{\overline{x}}_{1}\rightarrow x_{2}} \right)\vee\left( {{\overline{x}}_{1}\rightarrow{\overline{x}}_{2}} \right))\rightarrow x_{1}\): если отрицание \(x_{1}\) ведет к противоречию, то \(x_{1}\) – истинно (Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М.: Изд-во Моск. ун-та, 1982).↩︎
В соответствии с аристотелевым законом исключенного третьего из двух одновременных противоположных суждений о едином предмете одно – обязательно будет справедливым (Нуреев Р.М. Указ. соч.).↩︎
Любая булева функция \(f\left( {x_{1},\ldots,x_{n}} \right)\) может быть реализована в виде совершенной дизъюнктивной нормальной формы \(f{\left( {x_{1},\ldots,x_{n}} \right) =}\begin{matrix} \left( {\sigma_{1},\ldots,\sigma_{n}} \right) \\ {f{\left( {\sigma_{1},\ldots,\sigma_{n}} \right) = 1}} \\ \end{matrix}\left( {x_{1}^{\sigma_{1}}\ldots x_{n}^{\sigma_{n}}} \right)\), если \(f\left( {x_{1},\ldots,x_{n}} \right)\) не равна тождественно нулю; и в виде совершенной конъюнктивной нормальной формы \(f{\left( {x_{1},\ldots,x_{n}} \right) = \underset{\begin{matrix} {({\sigma_{1},\ldots,\sigma_{n}})} \\ {f{{({\sigma_{1},\ldots,\sigma_{n}})} = 0}} \\ \end{matrix}}{}}\left( {x_{1}^{{\overline{\sigma}}_{1}}\vee\ldots\vee x_{n}^{{\overline{\sigma}}_{n}}} \right)\), если \(f\left( {x_{1},\ldots,x_{n}} \right)\) не равна тождественной единице. Здесь \({\sigma_{i} = (}0,1)\), \(x_{i}^{\sigma_{i}} = \left\{ \begin{matrix} {x_{i}\mathit{при}{\sigma_{i} = 1},} \\ {{\overline{x}}_{i}\mathit{при}{\sigma_{i} = 0},} \\ \end{matrix} \right.\), i=1,...,n; то есть \(x_{i}^{\sigma_{i}} = 1\) и \(x_{i}^{\sigma_{i}} = 0\) тогда и только тогда, когда \(x_{i} = \sigma_{i}\). Таким образом, любая булева функция может быть реализована в виде формулы через инверсию, дизъюнкцию и конъюнкцию и даже только через отрицание и конъюнкцию, поскольку \(x_{1}\vee{x_{2} = \overline{{\overline{x}}_{1}\land{\overline{x}}_{2}}}\); либо только через инверсию и дизъюнкцию в силу тождества \({x_{1} \land x_{2}} = \overline{{\overline{x}}_{1}\vee{\overline{x}}_{2}}\). Кроме того, любая булева функция может быть представлена своим полиномом Жегалкина \(f{\left( {x_{1},\ldots,x_{n}} \right) = \underset{i_{1}i_{2}\ldots i_{k}}{\bigoplus}}{a_{i_{1}i_{2}\ldots i_{k}}x_{i_{1}}x_{i_{2}}\cdots x_{i_{k}}}\), где \({a_{i_{k}} = (}0,1)\), а значит, реализована формулой над системой булевых функций, состоящей из 0, 1, конъюнкции и суммы по модулю два. Системы булевых функций, задающие произвольную булеву функцию, называются функционально полными.
Например, совершенная конъюнктивная и дизъюнктивная нормальная формы для функции, реализованной формулой \(f{\left( {x_{1},x_{2},x_{3}} \right) = \left( {x_{1}\bigoplus x_{2}} \right)}\rightarrow\left( {x_{2} \land x_{3}} \right)\), таковы: \(f{\left( {x_{1},x_{2},x_{3}} \right) = {\overline{x}}_{1}}{\overline{x}}_{2}{\overline{x}}_{3}\vee{\overline{x}}_{1}{\overline{x}}_{2}x_{3}\vee{\overline{x}}_{1}x_{2}x_{3}\vee x_{1}x_{2}{\overline{x}}_{3}\vee x_{1}x_{2}{x_{3} = {\left( {x_{1}\vee{\overline{x}}_{2}\vee x_{3}} \right) \land \left( {{\overline{x}}_{1}\vee x_{2}\vee x_{3}} \right) \land \left( {{\overline{x}}_{1}\vee x_{2}\vee{\overline{x}}_{3}} \right)}}\). В качестве еще одного примера выпишем полином Жегалкина для одной из элементарных булевых функций двух переменных – “штриха Шеффера” \((f_{6})\): \(f{\left( {x_{1},x_{2}} \right) = 1}\bigoplus x_{1}x_{2}\). В справедливости этих утверждений можно убедиться, рассмотрев табличное представление соответствующих формул.
Отметим, что помимо функций алгебры логики существуют функции k-значной логики, которые, как и их переменные, принимают значения из множества \({E^{k} = \{}0,1,\ldots,{k - 1}\}\) (Редькин Н.П. Дискретная математика. 2-е изд. – СПб.: Лань, 2006).↩︎
Иногда такое отношение называют слабым упорядочением (Эрроу К.Дж. Коллективный выбор и индивидуальные ценности. – М.: Изд-во ГУ ВШЭ, 2004; Debreu G. Theory of value. – N.Y.: Willey; L.: Chapman & Hall, 1959).↩︎
Эрроу К.Дж. Коллективный выбор и индивидуальные ценности. – М.: Изд-во ГУ ВШЭ, 2004.↩︎