Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Основные общезначимости алгебры предикатов
1. 2. 3. 4. 5. Докажем формулу . Так как единственная переменная в обеих частях эквиваленции связана, то обе они являются высказываниями. Поэтому для доказательства общезначимости формулы, покажем, что истинностные значения левой и правой части совпадают для любых одноместных предикатов , определённых на произвольном множестве M. Пусть , тогда по определению операции утверждения существования для некоторого a из M. Следовательно, , где M. Воспользовавшись снова определением операции утверждения существования, получим, что или , а, следовательно, истинна и их дизъюнкция . Пусть теперь , тогда или . В первом случае получим, что M, , во втором – M, . Однако в обоих случаях существует такой элемент M, что , в первом случае , во втором – . А это означает, что . На множестве формул алгебры предикатов можно ввести отношение эквиваленции. Определение. Формула алгебры предикатов U называется эквивалентной формуле V (обозначается U º V), если их эквиваленция общезначима. Множество формул алгебры предикатов можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [ U ]. Определение. Формула алгебры предикатов называется приведенной, если она содержит операции утверждения всеобщности, существования, конъюнкции, дизъюнкции и операцию отрицания, относящуюся к атомарным формулам. Теорема 3.1. Каждый класс эквивалентности [ U ] может быть представлен приведенной формулой, т.е. для любой формулы U существует эквивалентная ей приведенная формула V. Для формул алгебры предикатов существуют предваренные нормальные формы. Определение. Предваренной нормальной формой (ПНФ) формулы алгебры предикатов называется формула, имеющая вид , где – некоторые кванторы, а U – бескванторная приведенная формула. Выражение называется префиксом, а U – матрицей нормальной формы. Будем говорить, что бескванторная формула U находится в ДНФ (КНФ), если U получается из формулы алгебры высказываний, находящейся в ДНФ (КНФ), подстановкой вместо пропозициональных переменных некоторых атомарных формул. ПНФ называется пренексной нормальной формой (ПННФ), если её матрица имеет вид ДНФ, и предклазуальной (пкнф), если – КНФ. Построим ПН-форму для формулы . Преобразуем формулу к приведенному виду º º º º . Так как для квантора " и операции Ú нет соответствующей эквивалентности, то переименуем связанную переменную y второго операнда дизъюнкции и вынесем кванторы по переменным, от которых не зависит другой операнд вперёд º º º º . В первом операнде конъюнкции последней формулы переменные x и y – связанные, а z – свободная, а во втором – наоборот. Переобозначив снова связанные переменные, получим º º º º . Полученная предваренная нормальная форма является предклазуальной. Использование формул алгебры предикатов в информационных технологиях породило необходимость преобразования формул в бескванторные, так как работать с такими формулами значительно легче, чем с формулами, содержащими кванторы. Основой такого преобразования являются аксиомы Сколема: 1) Þ ; 2) Þ . Возможность удаления кванторов всеобщности непосредственно следует из определения операции, так как для произвольного x. Формула U находится в клазуальной нормальной форме, если она получена из формулы, находящейся в предклазуальной нормальной форме, удалением кванторов существования в соответствии с аксиомами Сколема и последующим удалением всех кванторов всеобщности. Процесс такого преобразования называется сколемизацией. Так клазуальная нормальная форма для формулы предыдущего примера имеет вид .
|