Функции алгебры логики

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 18:45, 26 декабря 2016.

Функция а́лгебры ло́гики (или бу́лева фу́нкция) — отображение , где — булево множество.

Обозначения:

  • - арность или количество аргументов функции;
  • - множество всех функций алгебры логики;
  • - множество функций от n аргументов.

Формы представления

Табличное представление функций алгебры логики

Функцию алгебры логики можно задать, перечислив её значения для каждого входного булевого вектора, например

x1 x2 xn-1 xn f(x1,x2,…,xn)
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 0

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

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

  • Как построить по данной функции представляющую её формулу?
  • Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
    • В частности: существует ли способ приведения произвольной формулы к эквивалентной ей канонической форме такой, что две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?
  • Как по данной функции построить представляющую её формулу с теми или иными заданными свойствами (например, наименьшего размера), и возможно ли это?

Дизъюнктивная нормальная форма (ДНФ)

Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций.

Простой конъюнкцией называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.

Например   — является ДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .

Конъюнктивная нормальная форма (КНФ)

Конъюнктивная нормальная форма или КНФ — это конъюнкция простых дизъюнкций.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза.

Пример формулы в КНФ - .

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

Алгебраическая нормальная форма (АНФ или полином Жегалкина)

Алгебраическая нормальная форма или полином Жегалкина — форма представления логической функции в виде полинома с коэффициентами "0" и "1", в котором в качестве произведения используется операция конъюнкции («И», AND), а в качестве сложения — сложение по модулю 2 (исключающее «ИЛИ», XOR).

Способы получения АНФ:

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

Множество всех возможных булевых функций замкнуто.

Предполные классы

  • Класс функций, сохраняющих константу 0:
    .
  • Класс функций, сохраняющих константу 1:
    .
  • Класс самодвойственных функций:
    .
  • Класс монотонных булевых функций:
    .
  • Класс линейных булевых функций:
    .

Все остальные замкнутые классы булевых функций, отличные от , целиком содержатся хотя бы в одном из пяти описанных выше классов.

Другие замкнутые классы

Также можно выделить следующие замкнутые классы:

  • Класс конъюнкций K, являющийся замыканием множества . Он представляет собой множество функций вида .
  • Класс дизъюнкций D, являющийся замыканием множества . Он представляет собой множество функций вида .
  • Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
  • Класс функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
  • Класс функций, для которых выполнено условие , где — одна из переменных функции.
  • Класс функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
  • Класс функций, для которых выполнено условие , где — одна из переменных функции.

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

Полнота системы, критерий Поста

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

« Система булевых функций F является полной тогда и только тогда, когда она целиком не принадлежит ни одному из замкнутых классов . »

Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента. Максимально возможное число булевых функций в базисе — 4.

Классификация

Функции алгебры логики можно классифицировать:

  • По количеству аргументов функции, различают нульарные (n = 0, булевы константы), унарные (n = 1), бинарные (n = 2), тернарные (n = 3) булевы функции и функции от большего числа операндов;
  • По зависимости значения функции от перестановки её входных аргументов различают симметричные булевы функции (значение которых зависит только от количества единиц на входе) и несимметричные булевы функции (значение которых так же зависит от перестановки её аргументов);
  • По принадлежности к основным замкнутым классам (линейные, самодвойственные функции);
  • По количеству единиц и нулей в таблице истинности различают сбалансированные булевы функции (с одинаковым количеством "0" и "1" в векторе значений) и несбалансированные булевы функции.

Примечания

  1. Важно! Если что, метод треугольника может быть доказан полным перебором для нужного вам числа аргументов.

Список источников