Логический базис

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:26, 7 июня 2016.
TemplateDifinitionIcon.svg Определение «Определение - Логический базис (Булев базис)»
  • Набор простейших функций, с помощью которого можно выразить любые другие, сколь угодно сложные логические функции, называется функционально полным набором, или логическим базисом.
  • Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента.

Любую булеву функцию с произвольным количеством аргументов можно построить через подстановку элементарных функций вместо аргументов (суперпозицию).

Инверсия (логическое отрицание, "НЕ")

a
0 1
1 0

Конъюнкция (логическое умножение, "И")

a b a˄b
0 0 0
0 1 0
1 0 0
1 1 1

Дизъюнкция (логическое сложение, "ИЛИ")

a b a˅b
0 0 0
0 1 1
1 0 1
1 1 1

Виды базисов

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

Число операций, составляющих базис Базисы
1 {↓},{/}
2 {0,→}, {И, НЕ}, {НЕ,→}, {ИЛИ, НЕ}, {+(mod 2),→}
3 {0,И,НЕ}, {0,ИЛИ,НЕ}, {+(mod 2), И, НЕ}, {+(mod 2),ИЛИ,НЕ},{+(mod 2), ИЛИ, 1}, {+(mod 2),И,1}

где ↓ - стрелка Пирса, / - штрих Шеффера, → - имликация

Пример использования

Рассмотрим пример использования базиса {И,НЕ} Пусть есть выражение вида a̅˄b̅ , тогда навесив инверсию над всем выражением и используя закон де Моргана, получим:

Литература

  • Яблонский С.В. - Введение в дискретную математику
  • Конспект лекций О.Б. Лупанова - Введение в математическую логику (2007)