17. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли.

Бинарная операция — это отображение множества A ´ A в множество A, при этом образ пары (x, y) обозначим, например, x · y, где · — символ операции. Здесь A — произвольное непустое множество и A´A — множество всех упорядоченных пар (x, y) — таких, что x, y Î A. Непустое множество A называется основным множеством операции.

Можно составить иерархию множеств с бинарной операцией (разумеется, вместо · может быть вставлена любая — +, –, *, È, Ç, Å, Ä, Ñ, ° и т.д. и т.п.).

Свойства бинарных операций

• Ассоциативность

• Коммутативность

• Дистрибутивность слева и справа

• Существование нейтрального элемента

• Разрешимость уравнений

• Существование обратного элемента

ТАБЛИЦЫ КЭЛИ ВСЕХ БУЛЕВЫХ БИНАРНЫХ ОПЕРАЦИЙ

0  0 1 Функция f₀(x₁,x₂)=0



0  0 0 (константа нуль, false, ложь)

1  0 0 0000

  0 1 f₁(x₁,x₂)=x₁&x₂=x₁x₂=x_1*x₂=x₁x₂=x₁x₂



0  0 0 (конъюнкция, and, и)

1  0 1 0001

  0 1 Функция f₂(x₁,x₂)=x₁x₂=x₁x₂



0  0 0 (левая коимпликация)

1  1 0 (лат. conversus = обратный) 0010

x₁  0 1 Функция f₃(x₁,x₂) = x₁



0  0 0 (первый операнд)

1  1 1 0011

  0 1 Функция f₄(x₁,x₂)=x₁x₂=x₁x₂



0  0 1 (правая коимпликация)

1  0 0 (лат. conversus = обратный) 0100

x₂  0 1 Функция f₅(x₁,x₂) = x₂



0  0 1 (второй операнд)

1  0 1 0101

  0 1 f₆(x₁,x₂)=x₁x₂x₁x₂=x₁x₂



0  0 1 (неравнозначность, исключающее

1  1 0 и ли,xor, сложение по модулю 2) 0110

  0 1 f₇(x₁,x₂)=x₁@x₂= x₁+x₂= x₁x₂



0  0 1 (дизъюнкция, or, или)

1  1 1 (лат. vel = или) 0111

  0 1 f₈(x₁,x₂)= x₁x₂=x₁x₂



0  1 0 (функция Вебба)

1  0 0 1000

  0 1 f₉(x₁,x₂)=x₁x₂x₁x₂=x₁ x₂=x₁ x₂



0  1 0 (эквивалентность)

1  0 1 1001

x₂  0 1 Функция f_A (x₁,x₂)= f₁₀ (x₁,x₂)=x₂



0  1 0 (отрицание второго операнда)

1  1 0 1010

  0 1 f_B (x₁,x₂)=f₁₁(x₁,x₂)=x₂x₁=x₁x₂=x₁x₂



0  1 0 (правая импликация)

1  1 1 1011

x₁  0 1 Функция f_C(x₁,x₂)=f₁₂(x₁,x₂)=x₁



0  1 1 (отрицание первого операнда)

1  0 0 1100

  0 1 f_D(x₁,x₂) =f₁₃(x₁,x₂)=x₁x₂=x₁x₂=x₁x₂



0  1 1 (импликация, левая импликация)

1  0 1 1101

  0 1 f_E(x₁,x₂)=f₁₄(x₁,x₂)=x₁  x₂=x₁x₂



0  1 1 (несовместность, штрих Шеффера)

1  1 0 1110

1  0 1 Функция f_F(x₁,x₂)=f₁₅(x₁,x₂)=1



0  1 1 (константа единица, true, истина)

1  1 1 1111

Встречаются и другие названия: f₈ называют также стрелкой Пирса и обозначают: х₁х₂.

Законом противоречия называют упоминавшееся уже тождество хх=0; законом исключенного третьего — тождество хх=1. Используют также тождества 1=0 и 0=1.

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

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

₀=0 — это константа 0, ложь;

₁(х)=х — это единичное отображение множества {0, 1} на себя, х остается неизменным;

₂(х)=х — это отрицание х;

₃(х)=1— это константа 1, истина.

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

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

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

Пусть дано множество (конечное или бесконечное) исходных функций ={f₁, ..., f_m}. Символы переменных х₁, ..., х_n, ... и констант 0 и 1считают формулами глубины 0. Любая формула имеет глубину k+1, если она имеет вид f_i(F₁, ..., F_nl), где f_i, ni — количество аргументов f_i, а F₁, ..., F_nl — формулы, максимальная из глубин которых равна k.

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

Примеры различной записи одной и той же формулы:

1) and(x, or(y, z)); 2) x(yz) или x and (y or z); 3)x y z  

ТАБЛИЦА КЭЛИ ДЛЯ ОПЕРАЦИИ АВТОРИТЕТ ТАБЛИЦА КЭЛИ, КОРЕЙСКИЙ ВАРИАНТ