• идемпотентностей aЪ a=a, aЩ a=a;
• коммутативностей aЪ b=bЪ a, aЩ b=bЩ a;
• ассоциативностей aЪ (bЪ c)=(aЪ b)Ъ c, aЩ (bЩ c)=(aЩ b)Щ c;
• дистрибутивностей aЩ (bЪ c)=aЩ bЪ aЩ c; aЪ bЩ c=(aЪ b)Щ (aЪ c);
• двойного отрицания ШШ a=a;
• де-Моргана Ш aЪ Ш b=Ш (aЩ b), Ш aЩШ b=Ш (aЪ b);
• склеивания aЩ bЪ aЩ Ш b=a, (aЪ b)Щ (aЪШ b)=a;
• поглощения aЪ aЩ b=a, aЩ (aЪ b)=a;
• законы нуля (лжи) aЪ 0=a, aЩ 0=0, aЩ Ш a=0;
• законы единицы (истины) aЪ 1=1, aЩ 1=a, aЪ Ш a=1.

 
 
 
 
 
 
 
 

0 0 1 Функция f0(x1,x2)=0 0 0 0 (константа нуль, false, ложь) 1 0 0 0000

Щ 0 1 f1(x1,x2)=x1&x2=x1x2=x1*x2=x1Чx2=x1Щ x2 0 0 0 (конъюнкция, and, и) 1 0 1 0001

| ╝ 0 1 Функция f2(x1,x2)=x1ЩШ x2=x1|╝ x2 0 0 0 (левая коимпликация) 1 1 0 (лат. conversus = обратный) 0010

x1 0 1 Функция f3(x1,x2) = x1  0 0 0 (первый операнд) 1 1 1 0011

╛ | 0 1 Функция f4(x1,x2)=Шx1Щ x2=x1╛| x2 0 0 1 (правая коимпликация) 1 0 0 (лат. conversus = обратный) 0100

x2 0 1 Функция f5(x1,x2) = x2 0 0 1 (второй операнд) 1 0 1 0101

Е 0 1 f6(x1,x2)=Шx1Щ x2Ъx1Щ Шx2=x1Е x2 0 0 1 (неравнозначность, исключающее 1 1 0 или,xor, сложение по модулю 2) 0110

Ъ 0 1 f7(x1,x2)=x1@x2= x1+x2= x1Ъx2 0 0 1 (дизъюнкция, or, или) 1 1 1 (лат. vel = или) 0111

° 0 1 f8(x1,x2)= Ш x1Щ Шx2=x1° x2 0 1 0 (функция Вебба) 1 0 0 1000

~ 0 1 f9(x1,x2)=Шx1Щ Ш x2Ъx1Щ x2=x1 ╨ x2=x1 ~x2 0 1 0 (эквивалентность) 1 0 1 1001

Ш x20 1 Функция fA(x1,x2)= f10 (x1,x2)=Шx2 0 1 0 (отрицание второго операнда) 1 1 0 1010

╛ 0 1 fB(x1,x2)=f11(x1,x2)=Шx2Ъ x1=x1Мx2=x1╛ x2 0 1 0 (правая импликация) 1 1 1 1011

Ш x10 1 Функция fC(x1,x2)=f12(x1,x2)=Шx1 0 1 1 (отрицание первого операнда) 1 0 0 1100

╝ 0 1 fD(x1,x2) =f13(x1,x2)=Шx1Ъ x2=x1Йx2=x1╝ x2 0 1 1 (импликация, левая импликация) 1 0 1 1101

╫ 0 1 fE(x1,x2)=f14(x1,x2)=Шx1 Ъ Шx2=x1╫ x2 0 1 1 (несовместность, штрих Шеффера) 1 1 0 1110

1 0 1 Функция fF(x1,x2)=f15(x1,x2)=1  0 1 1 (константа единица, true, истина) 1 1 1 1111

 

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

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

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

x	j 0	j 1	j 2	j 3
0	0	0	1	1
1	0	1	0	1

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

j ₀=0 ≈ это константа 0, ложь;

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

j ₂(х)=Шх ≈ это отрицание х;

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

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

x	y	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	fA	fB	fC	fD	fE	fF
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

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

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

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

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

1) and(x, or(y, z)); 2) xЩ(yЪ z) или x and (y or z); 3)xy z Ъ Щ