Неинтерпретируемая функция

Эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом . Пожалуйста, помогите улучшить статью , предоставив читателю больше контекста . ( Октябрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математической логике , неосмысленные функции ^[1] или символ функции ^[2] является тот , который не имеет никакого другого свойства , чем его имя и п-ичная форма. Функциональные символы используются вместе с константами и переменными для образования терминов .

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

Пример [ править ]

В качестве примера неинтерпретируемых функций для SMT-LIB, если этот ввод передан решателю SMT :

(объявление-удовольствие f (Int) Int)(assert (= (f 10) 1))

решающая программа SMT вернет "Этот ввод допустим". Это происходит потому, что fэто неинтерпретируемая функция (т. Е. Все, что известно о fее сигнатуре ), поэтому вполне возможно, что f(10) = 1. Но применив ввод ниже:

(объявление-удовольствие f (Int) Int)(assert (= (f 10) 1))(assert (= (f 10) 42))

решающая программа SMT вернет «Этот ввод неудовлетворителен». Это происходит потому, что хотя fне имеет интерпретации, но невозможно, чтобы он возвращал разные значения для одного и того же ввода.

Обсуждение [ править ]

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

Свободные теории могут быть решены путем поиска общих подвыражений, образующих замыкание конгруэнции . ^{[ требуется пояснение ]} Решатели включают в себя решатели теорий выполнимости по модулю .

См. Также [ править ]

Заметки [ править ]

Ссылки [ править ]

^ Брайант, Рэндал Э .; Lahiri, Shuvendu K .; Сешия, Санджит А. (2002). «Моделирование и проверка систем с использованием логики счетной арифметики с лямбда-выражениями и неинтерпретируемыми функциями» (PDF) . Компьютерная проверка . Конспект лекций по информатике. 2404 . С. 78–92. DOI : 10.1007 / 3-540-45657-0_7 . ISBN 978-3-540-43997-4.
^ Баадер, Франц ; Нипков, Тобиас (1999). Перезапись терминов и все такое . Издательство Кембриджского университета. п. 34. ISBN 978-0-521-77920-3. CS1 maint: обескураженный параметр ( ссылка )

Эта статья, посвященная формальным методам, является незавершенной . Вы можете помочь Википедии, расширив ее .

[1] Брайант, Рэндал Э .; Lahiri, Shuvendu K .; Сешия, Санджит А. (2002). «Моделирование и проверка систем с использованием логики счетной арифметики с лямбда-выражениями и неинтерпретируемыми функциями» (PDF) . Компьютерная проверка . Конспект лекций по информатике. 2404 . С. 78–92. DOI : 10.1007 / 3-540-45657-0_7 . ISBN 978-3-540-43997-4.

[2] Баадер, Франц ; Нипков, Тобиас (1999). Перезапись терминов и все такое . Издательство Кембриджского университета. п. 34. ISBN 978-0-521-77920-3. CS1 maint: обескураженный параметр ( ссылка )

[1]