Матеріал з Ukrainian Logical Encyclopedia

Універсальна здійсне́нність — властивість формул логіки предикатів.

Термінологія і походження

англ. — universal satisfiability
рос. — универсальная выполнимость

Означення

Словосполучення «універсальна здійсненність» — термін.
Означення: формула називається універсально здійсненною, якщо вона здійсненна на будь-якій моделі (або, що те саме, здійсненна за будь-якої інтерпретації).

Властивості

Універсальна здійсненність та здійсненність пов’язані наступним законом:

Формула φ універсально здійсненна т. і т. т., коли її заперечення ¬φ нездійсненне

або, що те саме,

Формула φ здійсненна т. і т. т., коли її заперечення ¬φ не є універсально здійсненним.

Як властивість універсальна здійсненність нерозв’язна.

Джерела

1. Хермес Г. Проблема разрешимости и игра «домино» //

Эббинхауз Г.-Д., Якобс. К., Ман. Ф.-К., Хермес Г. Машины Тьюринга и рекурсивные функции. Пер. с нем. — М.: Мир, 1972. — С. 150–182.