Функция однократного чтения

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

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

Примеры

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

$a\wedge b\wedge c$

$a\wedge (b\vee c)$

$(a\wedge b)\vee c$, и

$a\vee b\vee c$

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

$(a\vee b)\wedge (a\vee c)\wedge (b\vee c)$

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

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

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

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

Признание

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

Ссылки

• Англуин, Дана ; Хеллерштейн, Лиза; Карпински, Марек (1993), «Изучение формул однократного чтения с помощью запросов», Journal of the ACM , 40 (1): 185–210, CiteSeerX   10.1.1.7.5033 , doi : 10.1145/138027.138061 , MR   1202143 , S2CID   6671840 .
• Голумбик, Мартин С .; Гурвич, Владимир (2011), «Функции однократного чтения» (PDF) , в Crama, Yves; Хаммер, Питер Л. (ред.), Булевы функции , Энциклопедия математики и ее приложений, том. 142, Издательство Кембриджского университета, Кембридж, стр. 519–560, doi : 10.1017/CBO9780511852008 , ISBN.  978-0-521-84751-3 , МР   2742439 .
• Голумбик, Мартин Чарльз ; Минц, Авиад; Ротикс, Уди (2006), «Факторизация и распознавание однократно читаемых функций с использованием кографов и нормальности, а также читаемость функций, связанных с частичными k- деревьями», Discrete Applied Mathematics , 154 (10): 1465–1477, doi : 10.1016/ ж.дам.2005.09.016 , МР   2222833 .
• Голумбик, Мартин Чарльз ; Минц, Авиад; Ротикс, Уди (2008), «Улучшение сложности факторизации однократно читаемых логических функций», Discrete Applied Mathematics , 156 (10): 1633–1636, doi : 10.1016/j.dam.2008.02.011 , MR   2432929 .
• Gurvič, V. A. (1977), "Repetition-free Boolean functions" , Uspekhi Matematicheskikh Nauk , 32 (1(193)): 183–184, MR  0441560 .
• Карчмер, М.; Линиал, Н. ; Ньюман, И.; Сакс, М .; Вигдерсон, А. (1993), «Комбинаторная характеристика формул однократного чтения», Discrete Mathematics , 114 (1–3): 275–282, doi : 10.1016/0012-365X(93)90372-Z , MR   1217758 .
• Мундичи, Даниэле (1989), «Функции, вычисляемые с помощью монотонных булевых формул без повторяющихся переменных», Theoretical Computer Science , 66 (1): 113–114, doi : 10.1016/0304-3975(89)90150-3 , MR   1018849 .