Бір рет оқу функциясы - Read-once function - Wikipedia
Математикада а бір рет оқу функциясы ерекше түрі болып табылады Логикалық функция сипаттауы мүмкін Логикалық өрнек онда әрқайсысы айнымалы тек бір рет пайда болады.
Дәлірек айтсақ, өрнек тек амалдарын қолдану үшін қажет логикалық байланыс, логикалық дизъюнкция, және жоққа шығару. Өтініш беру арқылы Де Морган заңдары, мұндай өрнекті терістеу тек жеке айнымалыларда қолданылатынға айналдыруға болады (әр айнымалы бір рет қана пайда болады). Әрбір жоққа шығарылатын айнымалыны оның терістеуін білдіретін жаңа оң айнымалыға ауыстыру арқылы мұндай функцияны эквивалентке айналдыруға болады оң бір рет оқылған логикалық функциясы, бір рет оқылу өрнегімен ұсынылған.[1]
Мысалдар
Мысалы, үш айнымалы үшін а, б, және в, өрнектер
- , және
барлығы бір рет оқылады (осы өрнектердегі айнымалыларды ауыстыру арқылы алынған басқа функциялар сияқты). Алайда, логикалық медиана өрнекпен берілген операция
бір рет оқылмайды: бұл формулада әр айнымалының бірнеше данасы бар, және әр айнымалыны бір рет қолданатын баламалы формула жоқ.[2]
Сипаттама
The дизъюнктивті қалыпты форма (оң) бір рет оқылатын функцияның өзі бір рет оқылмайды. Осыған қарамастан, ол функция туралы маңызды ақпаратты қамтиды. Атап айтқанда, егер а бірге пайда болу графигі онда шыңдар айнымалыны бейнелейді, ал шеттері конъюнктивті қалыпты форманың бір тармағында кездесетін айнымалылар жұбын қосады, сонда «бір рет оқылған» функциясының қатар жүру графигі міндетті түрде карта. Нақтырақ айтқанда, оң логикалық функция бір рет оқылады, егер оның бірге жүру графигі график болса және оған қосымша максималды клик қатар жүру графигі дизъюнктивті қалыпты форманың конъюнкцияларының бірін (жай импликанттар) құрайды.[3] Яғни, оның бірге пайда болу графигінің шыңдарындағы функция ретінде түсіндірілгенде, бір рет оқылатын функция максималды кликаны қамтитын шыңдар жиынтығы үшін дұрыс болады, ал басқаша жалған. Мысалы, медианалық функция үш айнымалының, а үшбұрыш графигі, бірақ осы графиктің үш вертикальды толық графикасы (бүкіл график) тек медиана үшін емес, тек конъюнкция үшін сөйлемнің ішкі жиынын құрайды.[4]Бір рет оқылатын оң өрнектің екі айнымалысы, егер олар болған жағдайда ғана, қатар жүру графигінде қатар орналасқан ең төменгі жалпы ата өрнекте конъюнкция,[5] сондықтан өрнек ағашын тиісті кографқа арналған котрит ретінде түсіндіруге болады.[6]
Бір рет оқылатын позитивті функциялардың тағы бір балама сипаттамасы олардың дизъюнктивті және конъюнктивті қалыпты форма. Барлық айнымалыларды қолданатын берілген айнымалылар жүйесінің позитивті функциясы, егер дисъюнктивті қалыпты форманың әрбір қарапайым импликанты мен конъюнктивалық қалыпты форманың әр сөйлемі дәл бір айнымалыға ие болса ғана оқылады.[7]
Тану
Бір рет оқылатын функцияларды олардың ішіндегі әдеттегі формалық өрнектерінен тануға болады көпмүшелік уақыт.[8]Сондай-ақ, функцияны тек «қара жәшік» арқылы бағалауға мүмкіндік беретін, оң оқылым функциясы үшін бір рет оқылатын өрнекті табуға болады. шындықты тағайындау, функцияны бағалаудың тек квадраттық санын қолдану.[9]
Ескертулер
- ^ Голумбич және Гурвич (2011), б. 519.
- ^ Голумбич және Гурвич (2011), б. 520.
- ^ Голумбич және Гурвич (2011), Теорема 10.1, б. 521; Golumbic, Mintz & Rotics (2006).
- ^ Голумбич және Гурвич (2011), Мысалдар f2 және f3, б. 521.
- ^ Голумбич және Гурвич (2011), Лемма 10.1, б. 529.
- ^ Голумбич және Гурвич (2011), 10.4 ескерту, 540-541 бб.
- ^ Гурвич (1977); Мундичи (1989); Карчмер және басқалар. (1993).
- ^ Голумбич және Гурвич (2011), Теорема 10.8, б. 541; Golumbic, Mintz & Rotics (2006); Golumbic, Mintz & Rotics (2008).
- ^ Голумбич және Гурвич (2011), Теорема 10.9, б. 548; Англуин, Геллерштейн және Карпинский (1993).
Әдебиеттер тізімі
- Англуин, Дана; Хеллерштейн, Лиза; Карпинский, Марек (1993), «Оқылым формулаларын сұраулармен оқып үйрену», ACM журналы, 40 (1): 185–210, CiteSeerX 10.1.1.7.5033, дои:10.1145/138027.138061, МЫРЗА 1202143.
- Голумбич, Мартин С.; Гурвич, Владимир (2011), «Бір рет оқу функциясы» (PDF), Крамада, Ив; Хаммер, Питер Л. (ред.), Логикалық функциялар, Математика энциклопедиясы және оның қосымшалары, 142, Cambridge University Press, Кембридж, 519–560 б., дои:10.1017 / CBO9780511852008, ISBN 978-0-521-84751-3, МЫРЗА 2742439.
- Голумбич, Мартин Чарльз; Минц, Авиад; Ротикс, Уди (2006), «Факторинг және бір реттік функцияларды тану, графиктерді пайдалану және қалыптылық және ішінара байланысты функциялардың оқылымдылығы к-ағаштар », Дискретті қолданбалы математика, 154 (10): 1465–1477, дои:10.1016 / j.dam.2005.09.016, МЫРЗА 2222833.
- Голумбич, Мартин Чарльз; Минц, Авиад; Rotics, Udi (2008), «Факторингтің бір рет оқылатын логикалық функцияларының күрделілігін жақсарту», Дискретті қолданбалы математика, 156 (10): 1633–1636, дои:10.1016 / j.dam.2008.02.011, МЫРЗА 2432929.
- Гурвич, В.А. (1977), «Қайталаусыз логикалық функциялар», Успехи Математических Наук, 32 (1(193)): 183–184, МЫРЗА 0441560.
- Карчмер, М .; Линиал, Н.; Ньюман, Мен .; Сакс, М.; Уигдерсон, А. (1993), «Бір рет оқылатын формулалардың комбинаторлық сипаттамасы», Дискретті математика, 114 (1–3): 275–282, дои:10.1016 / 0012-365X (93) 90372-Z, МЫРЗА 1217758.
- Мундичи, Даниэль (1989), «Айнымалысы жоқ монотонды буль формулаларымен есептелген функциялар», Теориялық информатика, 66 (1): 113–114, дои:10.1016/0304-3975(89)90150-3, МЫРЗА 1018849.