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

Пример.

Определение.

Определение.

Система функций называется минимально полным базисом, если удаление из неё любой функции превращает эту систему в неполную.

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

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

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

Определить с помощью теоремы Поста, является ли система функционально полной?

Операцию отрицания можно представить полиномом Жегалкина в виде , следовательно, функция отрицания линейна. Функция отрицания является самодвойственной, не сохраняет 0, не сохраняет 1(определяется с использованием таблицы истинности), немонотонна. Импликация является нелинейной функцией, т.к. её полином Жегалкина имеет вид , она несамодвойственна, не сохраняет 0, сохраняет 1 (можно определить по таблице истинности), немонотонна. Следовательно, для каждого класса Поста в данной системе имеется хотя бы одна функция, которая этому классу Поста не принадлежит. По теореме Поста такая система булевых функций является функционально полной.

Дата добавления: 2014-10-22