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

Логические функции


expand

Термин «функция» в математике означает правило, согласно которому каждому элементу из множества аргументов ставится в соответствие элемент из множества значений. В случае логической функции множество значений представлено двумя элементами {0;1}

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

"Функция от 0 переменных" = "нульарная операция" = { константа 0; константа 1 }
"Функция от 1 переменной" = "унарная операция " = { повторение переменной; инверсия переменной }
"Функция от 2 переменных" = "бинарная операция " = { конъюнкция; дизъюнкция и т.д. }
. . .
"Функция от n переменных" = "n-арная операция" = F( x1,x2 ... xn )

Разделение функций на операции и не операции зависит от выбранного Вами базиса. Например, базис И-ИЛИ-НЕ, принятый в булевой алгебре, как оптимальный, подразумевает, что есть три операции, а все остальное – уже безымянные функции.

Некоторые графические формы представления функции:
Функция F(a,b,c) в табличном виде
Функция F(a,b,c) в табличном виде
Комбинационная схема функции F(a,b,c)
Комбинационная схема функции F(a,b,c)
Функция F(a,b,c) в виде бинарного дерева
Функция F(a,b,c) в виде бинарного дерева

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

Аналитический способ представления функции:

F(a,b,c) = a → b ⊕ c
В произвольном базисе

F(a,b,c) = ¬a ∨ (a∧¬b∧c) ∨ (a∧b∧¬c)
В базисе И-ИЛИ-НЕ


Для сокращения записи формулы знак конъюнкции часто опускают: ¬a ∨ (a¬bc) ∨ (ab¬c)
Знаки инверсии ¬ заменяют на линию над переменной: ᖰaᖳ ∨ (aᖰbᖳc) ∨ (abᖰcᖳ)
В данной формуле скобки можно убрать, так как их отсутствие не меняет порядок выполнения операций: ᖰaᖳ ∨ aᖰbᖳc ∨ abᖰcᖳ

Как узнать порядок выполнения операций, если в формуле отсутствуют скобки? Каждая операция имеет приоритет. Операция с бОльшим приоритетом выполняется раньше. Операции с равным приоритетом выполняются слева направо.

Приоритет логических операций
Приоритет логических операций
Пример 1. Заполнить таблицу истинности по формуле a → b ↓ b ∧ ᖰcᖳ


Для трех переменных понадобится 23 = 8 строк в таблице. Каждая строка будет представлять наборы значений переменных. Наша задача - найти результат выполнения операций для каждого набора.

Набор № 0 = 0002-8, a = 0 b = 0 c = 0
  1. b ∧ ᖰcᖳ = 0 ∧ ᖰ0ᖳ = 0 ∧ 1 = 0
  2. a → b = 0 → 0 = 1
  3. 0 ↓ 1 = 0
Набор № 1 = 0012-8, a = 0 b = 0 c = 1
  1. b ∧ ᖰcᖳ = 0 ∧ ᖰ1ᖳ = 0 ∧ 0 = 0
  2. a → b = 0 → 0 = 1
  3. 0 ↓ 1 = 0
Набор № 2 = 0102-8, a = 0 b = 1 c = 0
  1. b ∧ ᖰcᖳ = 1 ∧ ᖰ0ᖳ = 1 ∧ 1 = 1
  2. a → b = 0 → 1 = 1
  3. 1 ↓ 1 = 0
Набор № 3 = 0112-8, a = 0 b = 1 c = 1
( a → b ) ↓ ( b ∧ ᖰcᖳ ) = ( 0 → 1) ↓ ( 1 ∧ ᖰ1ᖳ ) = ( 0 → 1) ↓ ( 1 ∧ 0 ) = 1 ↓ 0 = 0

Набор № 4 = 1002-8, a = 1 b = 0 c = 0
( a → b ) ↓ ( b ∧ ᖰcᖳ ) = ( 1 → 0) ↓ ( 0 ∧ ᖰ0ᖳ ) = ( 1 → 0) ↓ ( 0 ∧ 1 ) = 0 ↓ 0 = 1

Набор № 5 = 1012-8, a = 1 b = 0 c = 1
( a → b ) ↓ ( b ∧ ᖰcᖳ ) = ( 1 → 0) ↓ ( 0 ∧ 0 ) = 0 ↓ 0 = 1

Набор № 6 = 1102-8, a = 1 b = 1 c = 0
( a → b ) ↓ ( b ∧ ᖰcᖳ ) = 1 ↓ 1 = 0

Набор № 7 = 1112-8, a = 1 b = 1 c = 1
( a → b ) ↓ ( b ∧ ᖰcᖳ ) = 0
Таблица истинности функции F(a,b,c) =  a  →  b  ↓  b ∧ ¬c
Таблица истинности функции F(a,b,c) = a → b ↓ b ∧ ¬c
Пример 2. Написать формулу, исходя из данных таблицы истинности
Запишем правила для каждого набора, в котором результат = 1
Таблица истинности функции F(a,b,c)
Таблица истинности функции F(a,b,c)

Строка 0: Функция принимает значение 1, если a = 0 И b = 0 И c = 0
ᖰaᖳ∧ᖰbᖳ∧ᖰcᖳ


Строка 3: Функция принимает значение 1, если a = 0 И b = 1 И c = 1
ᖰaᖳ∧b∧c


Строка 5: Функция принимает значение 1, если a = 1 И b = 0 И c = 1
a∧ᖰbᖳ∧c


Строка 6: Функция принимает значение 1, если a = 1 И b = 1 И c = 0
a∧b∧ᖰcᖳ

В таблице показаны все состояния одновременно, однако в реальных вычислениях может участвовать только один набор(одна строка) в каждый момент времени. По мере того, как мы проходимся по таблице, функция F(a,b,c) примет значение 1 в (Строке 0) ИЛИ в (Строке 3) ИЛИ в (Строке 5) ИЛИ в (Строке 6).
F(a,b,c) = (ᖰaᖳ∧ᖰbᖳ∧ᖰcᖳ) ∨ (ᖰaᖳbc) ∨ (aᖰbᖳc) ∨ (abᖰcᖳ)
Логическая функция может быть описана различными формулами. В результате выполнения задания 2 мы получили дизъюнкцию выражений. Такая форма называется дизъюнктивно нормальная форма (ДНФ), в следующих главах мы ознакомимся с другими способами записи функций.