Функция однократного чтения - Википедия - Read-once function

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

Точнее, в выражении требуется использовать только операции логическое соединение, логическая дизъюнкция, и отрицание. Применяя Законы де Моргана, такое выражение может быть преобразовано в выражение, в котором отрицание используется только для отдельных переменных (при этом каждая переменная появляется только один раз). Путем замены каждой отрицательной переменной новой положительной переменной, представляющей ее отрицание, такая функция может быть преобразована в эквивалентную положительный Булева функция с однократным чтением, представленная выражением с однократным чтением без отрицаний.^[1]

Примеры

Например, для трех переменных а, б, и c, выражения

${ Displaystyle а клин б клин с}$

${ Displaystyle а клин (б ви с)}$

${ Displaystyle (а клин b) vee c}$, и

${ displaystyle a vee b vee c}$

все функции доступны для однократного чтения (как и другие функции, полученные путем перестановки переменных в этих выражениях). Однако логическое медиана операция, заданная выражением

${ Displaystyle (а ви б) клин (а ви с) клин (б клин с)}$

не читается один раз: эта формула имеет более одной копии каждой переменной, и нет эквивалентной формулы, которая использует каждую переменную только один раз.^[2]

Характеристика

В дизъюнктивная нормальная форма (положительной) функции однократного чтения обычно не выполняется однократное чтение. Тем не менее, он несет важную информацию о функции. В частности, если сформировать граф совместной встречаемости в котором вершины представляют переменные, а ребра соединяют пары переменных, которые обе встречаются в одном предложении конъюнктивной нормальной формы, тогда граф совместного появления функции однократного чтения обязательно является cograph. Точнее, положительная булева функция читается один раз тогда и только тогда, когда ее граф совместного появления является кографом, и, кроме того, каждый максимальная клика графа совместной встречаемости образует одну из конъюнкций (простых импликант) дизъюнктивной нормальной формы.^[3] То есть, когда она интерпретируется как функция на множествах вершин своего графа совместного вхождения, функция однократного чтения истинна для множеств вершин, содержащих максимальную клику, и ложна в противном случае. Например, медианная функция имеет тот же график совместной встречаемости, что и конъюнкция трех переменных: треугольный график, но трехвершинный полный подграф этого графа (весь граф) образует подмножество предложения только для конъюнкции, а не для медианы.^[4]Две переменные положительного одноразового выражения являются смежными в графе совместной встречаемости тогда и только тогда, когда их наименьший общий предок в выражении - союз,^[5] поэтому дерево выражений можно интерпретировать как cotree для соответствующего cograph.^[6]

Другая альтернативная характеристика положительных функций однократного чтения объединяет их дизъюнктивные и конъюнктивная нормальная форма. Положительная функция данной системы переменных, которая использует все свои переменные, считывается один раз тогда и только тогда, когда каждая простая импликанта дизъюнктивной нормальной формы и каждое предложение конъюнктивной нормальной формы имеют ровно одну общую переменную.^[7]

Признание

Можно распознать функции однократного чтения по их дизъюнктивным выражениям нормальной формы в полиномиальное время.^[8]Также возможно найти выражение однократного чтения для положительной функции однократного чтения, которому предоставляется доступ к функции только через «черный ящик», который позволяет ее вычислять в любой момент. назначение истины, используя только квадратичное число оценок функций.^[9]

Примечания

Рекомендации