Алгебра логики

Логические операции

Конъюнкция

\(p\) \(q\) \(p\,\&\,q\)
0 0 0
0 1 0
1 0 0
1 1 1

Дизъюнкция

\(p\) \(q\) \(p\vee q\)
0 0 0
0 1 1
1 0 1
1 1 1

Строгая дизъюнкция

\(p\) \(q\) \(p\oplus q\)
0 0 0
0 1 1
1 0 1
1 1 0

Импликация

\(p\) \(q\) \(p\rightarrow q\)
0 0 1
0 1 1
1 0 0
1 1 1

Эквивалентность

\(p\) \(q\) \(p\equiv q\)
0 0 1
0 1 0
1 0 0
1 1 1

Инверсия/отрицание

\(p\) \(\;\overline{p}\;\)
0 1
1 0

Итого

\(p\) \(q\) \(\;\overline{p}\;\) \(p\,\&\,q\) \(p\vee q\) \(p\oplus q\) \(p\rightarrow q\) \(p\equiv q\)
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
1 1 0 1 1 0 1 1

Законы алгебры логики

Логическая переменная
Переменная, значением которой может быть любое высказывание.
Логическая формула
любая переменная, а так же любая из констант “0” (“ложь”) и “1” (“истина”)
Любая комбинация логических формул, составленная с помощью логических операций.
Эквивалентные формулы
формулы, зависящие от одного набора переменных, при одинаковых значениях переменных имеющие одинаковые значения
Законы коммутативности
\[x \,\&\,y = y \,\&\,x\] \[x \vee y = y\vee x\]
Законы ассоциативности
\[ (x \,\&\,y) \,\&\,z = x \,\&\,(y \,\&\,z)\] \[ (x \vee y) \vee z = x \vee(y \vee z)\]
Законы поглощения (0 и 1)
\[x\vee 0 = x\] \[x\,\&\,1 = x\]
Законы дистрибутивности
\[ x\,\&\,(y\vee z) = (x\,\&\,y) \vee(x\,\&\,z)\] \[ x\vee(y\,\&\,z) = (x \vee y) \,\&\,(x\vee z)\]
Закон противоречия
\[ x \,\&\,\;\overline{x}\; = 0\]
Закон исключения третьего
\[ x \vee\;\overline{x}\; = 1\]
Закон равносильности
\[ x \,\&\,x = x\] \[ x \vee x = x \]
Закон двойного отрицания
\[\;\overline{\;\overline{x}\;}\; = x \]
Законы де Моргана
\[ \;\overline{x\,\&\,y}\; = \;\overline{x}\; \vee\;\overline{y}\; \] \[ \;\overline{x\vee y}\; = \;\overline{x}\; \,\&\,\;\overline{y}\; \]
Законы поглощения (переменной)
\[ x\vee(x\,\&\,y) = x\] \[ x\,\&\,(x\vee y) = x\]

Доказательство 1 закона де Моргана:

\(x\) \(y\) \(x\,\&\,y\) \(\;\overline{x\,\&\,y}\;\) \(\;\overline{x}\;\) \(\;\overline{y}\;\) \(\;\overline{x}\; \vee\;\overline{y}\;\)
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

3 и 6 столбец одинаковы, следовательно, соответствующие формулы эквивалентны.

Тавтология
логическая формула, которая всегда истинна.

Например, \(x\,\&\,\;\overline{x}\;\)

Булевы функции

Булева функция
функция \(f(x_1, x_2, \ldots, x_n) \in \{0,1\}\), где \(x_1, x_2, \ldots, x_n\).

Логические функции могут быть заданы таблично, либо аналитически.

В общем случае, булева функция \(n\) аргументов – отображение \(\lbrace 0, 1\rbrace^n \to \lbrace 0, 1 \rbrace\).

\(\lbrace 0, 1\rbrace^n\) можно интерпретировать как \(n\)-битное двоичное число.

\(\exists 2^n\) различных \(n\)-битных двоичных чисел. Каждому из них можно сопоставить значение функции 0 или 1.

Общее число различных булевых функций \(n\) аргументов равно \(2^{2^n}\).

\(\exists 16\) различных функций \(\{0, 1\}^2 \to \{0, 1\}\). Особо интересными из них являются:

  • Штрих Шеффера \[f(x,y) = \;\overline{a \,\&\,b}\; = a | b\]
  • Стрелка Пирса \[f(x,y) = \;\overline{a \vee b}\; = a \downarrow b\]

Канонические формы логических функций

Для любой логической существует бесконечно много различных эквивалентных логических формул.

Нормальная форма
выражение через дизъюнкцию, конъюнкцию и отрицание переменных
Элементарная конъюнкция
конъюнкция одной или нескольких переменных, или их отрицаний.
\(x_1 \,\&\,x_2 \,\&\,\;\overline{x_3}\;\)
Элементарная дизъюнкция
дизъюнкция одной или нескольких переменных, или их отрицаний.
\(x_1 \vee x_2 \vee\;\overline{x_3}\;\)
Дизъюнктивная нормальная форма (ДНФ)
дизъюнкция не повторяющихся элементарных конъюнкций.
\(x_1 \,\&\,x_2 \,\&\,\;\overline{x_3}\; \vee x_1 \,\&\,\;\overline{x}\;_2 \,\&\,\;\overline{x_3}\; \vee\ldots\)
Конъюнктивная нормальная форма (КНФ)
конъюнкция не повторяющихся элементарных дизъюнкций.
\((x_1 \vee x_2 \vee\;\overline{x_3}\;) \,\&\,(x_1 \vee\;\overline{x}\;_2 \vee\;\overline{x_3}\;) \,\&\,\ldots\)
Совершенная ДНФ (СДНФ)
ДНФ, в которой каждая элементарная конъюнкция состоит из \(k\) переменных \(x_1, x_2, \ldots, x_k\), причем на \(i\)-том месте конъюнкции стоит переменная \(x_i\) или ее отрицание \(\;\overline{x_i}\;\), и все элементарные конъюнкции различны.
Совершенная КНФ (СКНФ)
КНФ, в которой каждая элементарная дизъюнкция состоит из \(k\) переменных \(x_1, x_2, \ldots, x_k\), причем на \(i\)-том месте дизъюнкции стоит переменная \(x_i\) или ее отрицание \(\;\overline{x_i}\;\), и все элементарные дизъюнкции различны.
Теорема о существовании СДНФ
Пусть \(f(x_1, x_2, \ldots, x_n)\) – булева функция от \(n\) переменных, не равная тождественно нулю. Тогда существует СДНФ, выражающая функцию \(f\).
Теорема о существовании СКНФ
Пусть \(f(x_1, x_2, \ldots, x_n)\) – булева функция от \(n\) переменных, не равная тождественно единице. Тогда существует СКНФ, выражающая функцию \(f\).

Доказательство (СДНФ)

Лемма

\[f(x_1,\ldots,x_i,\ldots,x_n) = \;\overline{x_i}\; f(x_1,\ldots,0,\ldots,x_n) \\ \vee x_i f(x_1,\ldots,1,\ldots,x_n)\]

\[x_i = 0:\:f(x_1,\ldots,x_i,\ldots,x_n) = 1 f(x_1,\ldots,0,\ldots,x_n) \\ \vee 0 f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,0,\ldots,x_n)\]

\[x_i = 1:\:f(x_1,\ldots,x_i,\ldots,x_n) = 0 f(x_1,\ldots,0,\ldots,x_n) \\\vee 1 f(x_1,\ldots,1,\ldots,x_n) = f(x_1,\ldots,1,\ldots,x_n)\]

Применяя лемму:

\[f(x_1,\ldots,x_n) = \;\overline{x_1}\; \ldots \;\overline{x_n}\; f(0, \ldots, 0) \\ \vee\;\overline{x_1}\;\ldots \;\overline{x_{n-1}}\; x_n f(0, \ldots, 0, 1) \\ \ldots \\ \vee x_1 \ldots x_n f(1, \ldots, 1)\]

Опускаем конъюнкции, где \(f=0\), в остальных опускаем \(f=1\).

Получили СДНФ по определению, следовательно, она существует по построению. \(\blacksquare\)

Для \(f\equiv 0\) СДНФ не будет иметь ни одного члена.

Доказательство (СКНФ)

Лемма

\[f(x_1,\ldots,x_i,\ldots,x_n) = (x_i \vee f(x_1,\ldots,0,\ldots,x_n)) \\ \,\&\,(\;\overline{x_i}\; \vee f(x_1,\ldots,1,\ldots,x_n))\]

\[x_i = 0:\:f(x_1,\ldots,x_i,\ldots,x_n) = (0 \vee f(x_1,\ldots,0,\ldots,x_n)) \\ \,\&\,(1 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,0,\ldots,x_n) \]

\[x_i = 1:\:f(x_1,\ldots,x_i,\ldots,x_n) = (1 \vee f(x_1,\ldots,0,\ldots,x_n)) \\\,\&\,(0 \vee f(x_1,\ldots,1,\ldots,x_n)) = f(x_1,\ldots,1,\ldots,x_n) \]

Применяя лемму:

\[f(x_1,\ldots,x_n) = (\;\overline{x_1}\; \vee\ldots \vee\;\overline{x_n}\; \vee f(1, \ldots, 1)) \\ \,\&\,(\;\overline{x_1}\; \vee\ldots \vee\;\overline{x_{n-1}}\; \vee x_n \vee f(1, \ldots, 1, 0)) \\ \ldots \\ \,\&\,(x_1 \vee\ldots \vee x_n \vee f(0, \ldots, 0))\]

Исключим дизъюнкции с \(f=1\), опустим в остальных дизъюнкциях \(f=0\).

СКНФ по определению, следовательно, она существует по построению. \(\blacksquare\)

Для \(f\equiv 1\) СКНФ не будет иметь ни одного члена.

Полные системы булевых функций

Полная система булевых функций
система булевых функций \(\lbrace f_1, \ldots, f_n \rbrace\), позволяющая выразить произвольную логическую функцию.

По теоремам о существовании СДНФ и СКНФ, система функций \(\lbrace \,\&\,, \vee, \neg \rbrace\) – полная.

Если \(\lbrace f_1, \ldots, f_n \rbrace\) — полная, и каждая из \(f_1, \ldots, f_n\) выражается через \(g_1, \ldots, g_n\), то \(\lbrace g_1, \ldots, g_n \rbrace\) – полная.

\(\lbrace \vee, \neg \rbrace\) и \(\lbrace \,\&\,, \neg \rbrace\) – полные.

\(f(x,y) = x | y\), \(f(x,y) = x \downarrow y\) – сами по себе образуют полные системы.

\(x\) \(y\) \(x|y\) \(x\downarrow y\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(1\) \(0\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(0\)

\(x|y = \;\overline{x\,\&\,y}\;\), другое название: “И-НЕ”.

\(x\downarrow y = \;\overline{x\vee y}\;\), другое название: “ИЛИ-НЕ”.

Полнота штриха Шеффера:

  • \(x|y = \;\overline{x\,\&\,y}\;\)
  • \(x|x = \;\overline{x\,\&\,x}\; = \;\overline{x}\;\)
  • \(x \,\&\,y = \;\overline{\;\overline{x\,\&\,y}\;}\; = \;\overline{x | y}\; = (x|y)|(x|y)\)

Полнота стрелки Пирса:

  • \(x\downarrow y = \;\overline{x\vee y}\;\)
  • \(x\downarrow x = \;\overline{x\vee x}\; = \;\overline{x}\;\)
  • \(x \vee y = \;\overline{\;\overline{x\vee y}\;}\; = \;\overline{x\downarrow y}\; = (x\downarrow y)\downarrow(x \downarrow y)\)

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