Функциональная полнота множества логических операций, Критерии кратко

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

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

Таким образом также является функционально полной системой. Но также может быть выражено (в соответствии с законом де Моргана) как:

также может быть определена через подобным образом.

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

Итак и одна из является минимальной функционально полной системой.

Критерий полноты

Критерий Поста описывает необходимые и достаточные условия функциональной полноты множеств булевых функций. Об этом говорит сайт https://intellect.icu . Был сформулирован американским математиком Эмилем Постом в 1941 году.

Критерий:

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

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

В таблице приведены свойства, которыми обладают элементарные булевы функции (символ * - отмечает свойство, которым обладает данная функция).

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

Минимальные множества бинарных операций

Множества из одного элемента

(штрих Шеффера), (стрелка Пирса)

Множества двух элементов

Множества трех элементов

, (см. алгебра Жегалкина), (инверсный к предыдущему)

Функциональная полнота системы булевых функций

Определение. Множество функций N называется функционально полной системой (ФПС), если любая булева функция представима суперпозицией функций из N.

Договоримся опускать аргументы при перечислении функций множества N и рассматривать термин ''система'' в данном контексте как синоним множества.

Пример 1. Множество N₁={, , ^–} является функционально полной системой, так как любую булеву функцию, кроме константы 0, можно представить совершенной ДНФ, то есть суперпозицией функций из N₁ а константу 0 – формулой xx . •

Пример 2. Множество N₂={, , 1} является ФПС, так как любую булеву функцию можно представить полиномом Жегалкина, то есть суперпозицией функций из N₂, а полином 0 – формулой 1 1. •

Следующая теорема позволяет сводить вопрос о функциональной полноте одних систем к вопросу о полноте других систем.

Теорема о двух функционально полных системах. Если даны два множества N₁ и N₂ булевых функций и известно, что N₁ – функционально полная система, а каждая функция из N₁ представима суперпозицией функций из N₂, то N₂тоже является функционально полной системой.

Доказательство. Рассмотрим произвольную булеву функцию f(x₁, …, x_n). Она может быть представлена суперпозицией функций из множества N₁={f₀,f₁ …, f_m}, так как N₁ – ФПС:

По условию теоремы каждая из функций f₀, f₁ …, f_m может быть представлена суперпозицией функций из N₂, значит, функция f(x₁, …, x_n) представима суперпозицией функций из N₂, следовательно, N₂ – ФПС. •

Пример 1. N₁={ , ^–,}, N₂={, ^–}. Как показано ранее, N₁ – ФПС. Конъюнкция и инверсия содержатся в N₂, а дизъюнкция представима суперпозицией функций из N₂: x y = , значит, N₂ – ФПС. •

Пример 2. N₁={, ^–}, N₂={↓ }. Как показано в предыдущем примере, N₁ – ФПС. Инверсия и конъюнкция могут быть представлены суперпозицией стрелки Пирса: x = x↓ x, xy == (x↓ x)↓ (y↓ y), следовательно N₂ – ФПС. •

Вау!! 😲 Ты еще не читал? Это зря!

• Замкнутые классы булевых функций
• Критерий Поста
• логических операции
• булевы функции
• Математическая логика
• предполные классы
• функциональная полнота информационной системы ,

Исследование, описанное в статье про функциональная полнота, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое функциональная полнота и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.