Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Элементарные булевы функции

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Среди булевых функций особо выделяются так называемые элементарные булевы функции, посредством которых можно описать любую булеву функцию от любого числа переменных.
     1. Булева функция f(x1, x2 ... xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.
     2. Булева функция f(x1, x2 ... xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: 0.
     3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:

x01
f(x)10

     Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».
     4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0001

     Другие названия: логическое умножение (произведение); логическое «и».
     Обозначения: x&y, x⋅y, min(x,y).
     Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».
     5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0111

     Другие названия: логическое сложение (сумма); логическое «или».
     Обозначения: x∨y, max(x,y).
     Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».
     6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1101

     Другое название: логическое следование.
     Обозначения: x→y, x⇒y, x⊃y.
     Запись x→y может читаться так: «из икс следует игрек».
     7. Эквивалентностью называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1001

     Обозначения: x∼y, x↔y.
     Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».
     8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)0110

     Другое название: антиэквивалентность.
     Обозначения: x⊕y, x+y.
     Запись x⊕y может читаться так: «икс плюс игрек».
     9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1110

     Другое название: отрицание конъюнкции, логическое «не-и».
     Обозначение: x|y.
     Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».
     10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:

x0011
y0101
f(x, y)1000

     Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.
     Обозначение: x↓y; для функции Вебба - x°y.
     Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».

     Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.

x00000111
y00111001
z01001011
f(x,y,z)00001011

     Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 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).

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru