Теория

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

Базовые операции

Рассмотрим множество из двух элементов: $\{0, 1\}$.

Определим на нём три операции:

1) логическое сложение $\lor$, по-другому его называют логическое ИЛИ;

2) логическое умножение $\land$, по-другому его называют логическое И;

3) логическое отрицание $\lnot$, по-другому его называют инверсией.

Обозначения $\lor$ и $\land$ переняты из общей теории множеств. Там похожие символы $\cup$ и $\cap$ используются для обозначения объединения и пересечения множеств. Потому что алгебра логики строится на основе алгебры множеств, где каждое множество - это высказывание. Об этом подробнее будет рассказано в строгом доказательстве. Но мы будем строить новую алгебру с умножением и сложением, определёнными совсем не так, как вы привыкли.

Да, в множестве натуральных чисел умножение даёт что-то сильно большее, чем хотя бы один из множителей. А в нашей алгебре умножение, наоборот, будет давать что-то сильно меньшее. Здесь умножение и сложение нам интересны именно как операции, обладающие некоторыми свойствами, а не как "что-то похожее на сложение и умножение натуральных чисел". Хотя мы ещё встретим аналоги, но они нужны нам для понимания, а не для обоснования.

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

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

A	B	Логическое ИЛИ	Логическое И
0	0	0	0
0	1	1	0
1	0	1	0
1	1	1	1

Определение

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

A	Отрицание
0	1
1	0

Определение

Отрицание истинно тогда и только тогда, когда ложна его предпосылка.

Будем называть наше множество с тремя операциями и двумя элементами множеством логики.

Строгое доказательство*

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

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

Построение кольца множеств через операции симметрической разности и объединения вообще первично и именно из-за него кольцо и называется кольцом. Потому что оно замкнуто относительно этих двух операций. А полукольцо замкнуто только относительно симметрической разности. А потом уже по аналогии с кольцом множеств вывели множество-кольцо. Например, множество-кольцо целых чисел.

Строим заново

Мир давно перешёл на цифровые вычислители, базовая единица хранения информации давно не высказывание, а бит. Бит - величина, которая может принимать значение равное только нулю или единице. Все сложные операции сводятся к трём базовым: сложение, умножение, отрицание. правильнее строить алгебру логики в классическом смысле над множеством этих самых двух элементов $\{0, 1\}$. Иными словами вместо алгебры логики как алгебры множеств мы докажем, что наше множество логики является множеством-алгеброй.

Кстати, в алгебре логики есть заменитель симметрической разности. Это - xor, исключающее ИЛИ. Ради интереса можете попробовать построить алгебру в классическом смысле над последовательностью битов при помощи ИЛИ и исключающего ИЛИ.

Чтобы доказать, что множество логики является алгеброй, и мы по праву называем его алгеброй, нужно сначала доказать несколько промежуточных утверждений. Определения взяты Из курса алгебры Э.Б. Винберга.

Группы

$a,b,c \in A$ означает, что элементы $a,b,b$ лежат в множестве $A$

Аддитивной абелевой группой называется множество A с операцией сложения, обладающей следующими свойствами:

1) $a+b=b+a$ для любых $a,b \in A$ коммутативность

2) $(a+b)+c=a+(b+c)$ для любых $a,b,c \in A$ ассоциативность

3) в $A$ существует такой нейтральный элемент $O$ (ноль), что $a+O=a$ для любого $a\in A$

4) для любого элемента $a\in A$ существует такой элемент $-a$(противоположный элемент), что $a+(-a)=O$

Утверждение

Множество логики является аддитивной абелевой группой

В нашем случае операция сложения - это $\lor$, а $O$ - это ложь или значение 0. Я специально написал $O$ вместо $0$, чтобы ещё раз показать, что в общем случае нейтральный элемент может и не быть нулём. Например, в нашем случае мы можем говорить, что нейтральный элемент - это именно ложь. А нулём мы её просто записываем.

Каждый из пунктов доказывается через рассмотрение всех вариантов. Доказательство каждого пункта таких утверждений не представляет никакого интереса, поэтому рассмотрим только одно.

Дальше по тексту, если утверждение доказывается перебором всех вариантов, я буду писать "доказывается таблицей истинности".

Докажем утверждение, что для любых элементов множества логики выполняется ассоциативность сложения

a	b	c	(a+b)+c	a+(b+c)
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

Мы перебрали все варианты элементов $a, b, c$ и все значения первого и второго выражения совпали. Это доказывает их равенство. Обратите внимание, что строк таблицы у нас стало 8. В общем виде строки таблицы будет $2^n$, где $n$ - кол-во аргументов в выражении. Если у вас нет под рукой компьютера, а вам надо сократить громоздкое логическое выражение или доказать равенство двух более сложных выражений, то один из способов это сделать - как раз таблицы истинности. Просто столбцов понадобится больше. В этом случае выражение разделяют на действия и для каждого из них, в соответствии с его порядком, выделяют свой столбец.

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

1) $ab=ba$ для любых $a,b \in A$ коммутативность

2) $(ab)c=a(bc)$ для любых $a,b,c \in A$ ассоциативность

3) в $A$ существует такой единичный элемент $I$(единица), что $aI=a$ для любого $a\in A$

4) для любого элемента $a\in A$ существует такой элемент $a^{-1}$(обратный элемент), что $aa^{-1}=I$

Утверждение

Множество логики является мультипликативной абелевой группой

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

Кольцо

Кольцом называется множество $K$ с операциями сложения и умножения, обладающими следующими свойствами:

1) относительно сложения $K$ есть абелева группа(называемая аддитивной группой кольца $K$)

2) $a(b+c)=ab+ac$ и $(a+b)c=ac+bc$ для любых $a,b,c \in K$ (дистрибутивность умножения относительно сложения)

Кольцо $K$ называется коммутативным, если умножение в нём коммутативно, т.е.

$ab=ba$ для любых $a,b \in K$

Кольцо $K$ называется ассоциативным, если умножение в нём ассоциативно, т.е.

$(ab)c=a(bc)$ для любых $a,b,c \in K$

Элемент $I$ кольца называется единицей, если

$aI=Ia=a$ для любого $a \in K$

Полем называется коммутативное ассоциативное кольцо с единицей, в котором всякий ненулевой элемент обратим.

Утверждение

Множество логики является полем

Первый пункт определения кольца нами уже доказан, дистрибутивность второго пункта доказывается таблицей истинности, коммутативность и ассоциативность - тоже.

В итоге получим, что множество логики является полем.

Алгебра

Векторным (или линейным) пространством над полем $K$ называется множество $V$ c операциями сложения и умножения на элементы поля $K$, обладающими следующими свойствами:

1) относительно сложения V усть абелева группа;

2) $\lambda(a+b)=\lambda a + \lambda b$ для любых $\lambda \in K, a,b\in V$;

3) $(\lambda+\mu)a = \lambda a+ \mu a$;

4) $(\lambda \mu)a=\lambda(\mu a)$ для любых $\lambda, \mu \in K, a \in V$;

5) $1a=a$ для любого $a\in V$

Утверждение

Множество логики является векторным пространством над самим собой

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

Алгеброй над полем $K$ называется множество $A$ с операциями сложения, умножения и умножения на элементы поля $K$, обладающие следующими свойствами:

1) относительно $+$ и $*$ на элементы поля $A$ есть векторное пространство;

2) относительно сложения и умножения $A$ есть кольцо;

3) $(\lambda a)b=a(\lambda b)=\lambda(ab)$ для любых $\lambda \in K, a,b \in A$

Утверждение

Множество логики является алгеброй над самим собой

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

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

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

Пусть у нас есть вещественный вектор $(x,y)$, т.е. и первая, и вторая его координаты - тоже вещественные числа, на полем вещественных чисел $\R$. Множество, образующее пространство, - это множество пар вещественных чисел.

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

Те же рассуждения можно провести если построить алгебру, например, из вещественных чисел над полем этих же вещественных чисел. Тогда мы бы получили алгебру, если бы дистрибутивность сложения относительно умножения работала $a+(b*c)=(a+b)*(a+c)$ и $(a+b)c=ac+bc$. Очевидно, что для вещественных чисел это не работает. Т.о. множество вещественных чисел может быть пространством относительно сложения и умножения над самим собой, а алгеброй нет.

А вот множество логики - да. Для него дистрибутивность пересечения относительно объединения и, наоборот, дистрибутивность объединения относительно пересечения доказываются таблицей истинности. Дистрибутивность ещё называют распределительным законом.

$x\land (y\lor z)=(x\land y)\lor (x\land z),$

$x\lor (y\land z)=(x\lor y)\land (x\lor z)$

Логические элементы*

Этот раздел тоже не обязателен для решения задачи, но довольно полезен. В нём используются иллюстрации из книги Чарльза Петцольда "Код". Настоятельно рекомендую к прочтению. Скачать pdf можно здесь.

Заметим, что в алгебре логики дистрибутивность работает и для xor. По-другому он называется исключающее ИЛИ, обозначается как $\oplus$.

$x\land (y\oplus z)=(x\land y)\oplus (x\land z)$

Может показаться, что xor - бесполезная операция. Зачем нужно исключающее или? Да, он отвечает на вопрос, правда ли что два элемента не равны. Но есть ли от него какой то действительный прок? Конечно же, есть. Главное назначение $\oplus$ - это, как ни удивительно, сложение.

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

О текущем моменте

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

В современных вычислениях решает количество

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

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

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

Исходные данные называются Датасет(Dataset).

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

Подробнее про работу процессора здесь

Операции

Отрицание исключающего или $\oplus$ - это эквивалентность $\equiv$. Два логических значения эквивалентны тогда и только тогда когда они либо оба равны $0$, либо оба равны $1$.

$$a\equiv b=\lnot(a\oplus b)=(a\lor \lnot b)\land(\lnot a\lor b)$$

Есть ещё одна операция. Это следствие $\to$. Из лжи может следовать, что угодно, из истины - только истина. Поэтому следствие ложно тогда и только тогда, когда из истины следует ложь, в остальных случаях оно истинно.

$$a\to b = \lnot a \lor b$$

Для нахождения значений сложных выражений, нужно определиться с порядком действий.

Порядок приоритета операций:

1) Скобки

2) $\lnot$

3) $\land$

4) $\lor$, $\oplus$

5) $\to$

6) $\equiv$

Тождества

$$x\lor \lnot x=1\\ x\lor 1=1\\ x\lor x=x\\ x\lor 0=x\\ x\land\lnot x=0\\ x\land x=x\\ x\land 0=0\\ x\land 1=x\\ x\lor \lnot x=1\\ x\lor 1=1\\ x\lor x=x\\ x\lor 0=x\\ x\land\lnot x=0\\ x\land x=x\\ x\land 0=0\\ x\land 1=x\\$$

Доказательства тождеств опустим в силу их интуитивности

Свойства

Все приведённые дальше свойства можно доказать при помощи таблицы истинности. Поэтому дальше они просто приведены без доказательств.

Инволютивность отрицания, закон снятия двойного отрицания:

$$\lnot \lnot x=x$$

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

$$x\land y=y\land x,\\ x\lor y=y\lor x,\\ x\oplus y=y\oplus x,\\ x\equiv y=y\equiv x,\\ x\land y=y\land x,\\ x\lor y=y\lor x,\\ x\oplus y=y\oplus x,\\ x\equiv y=y\equiv x,$$

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

$$(x\land y)\land z = x\land(y\land z) \\ (x\lor y)\lor z = x\lor(y\lor z) \\ (x\oplus y)\oplus z = x\oplus(y\oplus z)\\ (x\equiv y)\equiv z = x\equiv(y\equiv z)\\ (x\to y)\to z = x\to(y\to z)\\ (x\land y)\land z = x\land(y\land z)\\ (x\lor y)\lor z = x\lor(y\lor z)\\ (x\oplus y)\oplus z = x\oplus(y\oplus z)\\ (x\equiv y)\equiv z = x\equiv(y\equiv z)\\ (x\to y)\to z = x\to(y\to z)\\$$

Дистрибутивность мы уже рассмотрели:

$$x\land (y\lor z)=(x\land y)\lor (x\land z),\\ x\lor (y\land z)=(x\lor y)\land (x\lor z),\\ x\land (y\oplus z)=(x\land y)\oplus (x\land z).\\ x\land (y\lor z)=(x\land y)\lor (x\land z),\\ x\lor (y\land z)=(x\lor y)\land (x\lor z),\\ x\land (y\oplus z)=(x\land y)\oplus (x\land z).$$

Законы де Мо́ргана:

$$\lnot(x \land y)=\lnot x \lor \lnot y,\\ \lnot(x \land y)=\lnot x \lor \lnot y,\\ \lnot(x\lor y)=\lnot x \land \lnot y.$$

Законы поглощения:

$$x\land (x\lor y)=x, \\ x\land (x\lor y)=x,\\ x\lor (x\land y)=x.$$

Если вам лень составлять таблицу истинности, а компьютера под рукой нет, то есть приёмы упрощения логической функции, например: карта Карно, метод Куайна - Мак-Класки