Элементарные булевы функции
Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
1. Булева функция f(x1, x2 ... xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.
2. Булева функция f(x1, x2 ... xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0.
3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:
x | 0 | 1 |
f(x) | 1 | 0 |
Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».
4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 0 | 0 | 0 | 1 |
Другие названия: логическое умножение (произведение); логическое «и».
Обозначения: x&y, x⋅y, min(x,y).
Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».
5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 0 | 1 | 1 | 1 |
Другие названия: логическое сложение (сумма); логическое «или».
Обозначения: x∨y, max(x,y).
Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».
6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 1 | 1 | 0 | 1 |
Другое название: логическое следование.
Обозначения: x→y, x⇒y, x⊃y.
Запись x→y может читаться так: «из икс следует игрек».
7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 1 | 0 | 0 | 1 |
Обозначения: x∼y, x↔y.
Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».
8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 0 | 1 | 1 | 0 |
Другое название: антиэквивалентность.
Обозначения: x⊕y, x+y.
Запись x⊕y может читаться так: «икс плюс игрек».
9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 1 | 1 | 1 | 0 |
Другое название: отрицание конъюнкции, логическое «не-и».
Обозначение: x|y.
Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».
10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:
x | 0 | 0 | 1 | 1 |
y | 0 | 1 | 0 | 1 |
f(x, y) | 1 | 0 | 0 | 0 |
Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.
Обозначение: x↓y; для функции Вебба - x°y.
Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».
Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.
x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) = 0.
Вектором значений булевой функции y=f(x1, x2 ... xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).
Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности