Привести формулу к нормальной приведенной форме
Привести формулу к нормальной приведенной формеПредваренная, сколемовская нормальная и сколемовская стандартная формы
=== Скачать файл ===
Архитектура- Астрономия- Биология- Биотехнологии- Военное дело- Высокие технологии- География- Геология- Государство- Демография- Дом- Журналистика и СМИ- Изобретательство- Иностранные языки- Информатика- Искусство- История- Компьютеры- Косметика- 55 Кулинария- Культура- Лингвистика- Литература- Маркетинг- Математика- Машиностроение- Медицина- Менеджмент- Механика- Науковедение- Образование- Охрана труда- Педагогика- Полиграфия- Политика- Право- Приборостроение- Программирование- Производство- Промышленность- Психология- Религия- Связь- Сельское хозяйство- Социология- Спорт- Строительство- Торговля- Транспорт- Туризм- Физика- Философия- Финансы- Химия- Экология- Экономика- Электроника- Электротехника- Энергетика- Юриспруденция- Ядерная техника- Помимо эквивалентностей логики высказываний для логики предикатов справедливы следующие эквивалентности , , - предикаты, a - высказывание:. Расширение области действия кванторов не зависит от: Формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам. Например, для формулы нормальной формой будет. Предварённая нормальная форма ПНФ - нормальная форма, в которой кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики. Всякую формулу логики предикатов можно свести к ПНФ, если использовать следующий алгоритм:. Исключение логических связок и. Продвижение знака отрицания до атома. Многократно пока это возможно делаются замены:. Для вынесения кванторов используются формулы эквивалентности для исчисления предикатов. Пусть произвольная формула логики предикатов. Формулу получим из формулы заменой связанных переменных другими переменными, отличными от всех свободных переменных формулы , причем заменяемая переменная в формуле должна меняться одинаковым образом всюду в области действия квантора, связывающего данную переменную, и в самом кванторе. В этом случае равносильно. Таким образом, переименовывать связанные переменные необходимо только в самом кванторе и в области. Одинаковые переменные, для которых связывающие их кванторы имеют различные области действия, могут переименовываться разным образом или одна из них может переименовываться, а другая нет. Нормальная формула имеет вид. Переименовываем переменную в кванторе и в области действия этого квантора на. В полученной формуле переменную можно переименовать на в первой посылке и на во второй посылке, либо оставить во второй посылке без изменения. Квантор существования можно вынести за знак дизъюнкции, так как второй член дизъюнкции не зависит от и может рассматриваться как константа. Так как выражение не содержит операций импликации и эквиваленции, то нет необходимости в первом шаге. Отсюда возникает задача устранения кванторов существования в формулах, представленных в ПНФ. Это можно сделать путем введения сколемовских функций. Последовательно слева направо вычеркиваем каждый квантор существования, например , заменяя все вхождения переменной на новый еще не использованный функциональный символ , в качестве аргументов берем все переменные, связанные предшествующими кванторами всеобщности. Функциональный символ называется сколемовской функцией. Формула логики предикатов, полученная после выполнения шагов 1 и 2, называется сколемовской нормальной формой СНФ. Для получения СНФ вычеркиваем фактор существования и все вхождения переменной заменяем на константу поскольку квантору не предшествует ни один квантор всеобщности, то есть сколемовская функция не зависит ни от одной переменной, то есть эта функция является константой. На следующем шаге вычеркиваем квантор существования и все вхождения переменной заменяем на функцию. На последнем шаге вычеркиваем квантор. Переход от ПНФ к сколемовской нормальной форме не затрагивает свойство формулы быть невыполнимой противоречивой. Это доказывается следующей теоремой. Пусть формула задана в ПНФ и преобразована в СНФ. Тогда в ПНФ логически невыполнима тогда и только тогда, когда невыполнима СНФ для. Однако следует заметить, что если имеется выполнимая формула , то может оказаться, что СНФ для будет невыполнимой. Рассмотрим теперь преобразование бескванторной части к виду так называемых дизъюнктов. Дизъюнктом называется формула вида , где — произвольная литера. По определению он всегда ложен. Предполагается, что в формуле исключены скобки между одинаковыми связками, то есть нет выражений вида , , ,. Если таких вхождений нет, то - формула находится в КНФ. Заменить формулу на формулу. Кроме того, в алгоритме надо предусмотреть приведение подобных членов, а также всевозможные склеивания и поглощения. Итак, последовательным применением алгоритма приведения к ПНФ, алгоритма получения СНФ и алгоритма приведения к КНФ с сохранением свойства невыполнимости любая формула может быть представлена набором дизъюнктов, объединенных кванторами общности. Такую формулу будем называть формулой, представленной в сколемовской стандартной форме ССФ. В дальнейшем формулы вида , где — дизъюнкты, а — различные переменные, входящие в эти дизъюнкты, будет удобно представлять как множество дизъюнктов. Формула является логическим следствием формул тогда и только тогда, когда формула общезначима. Формула является логическим следствием формул тогда и только тогда, когда формула противоречива. Сначала приведем это выражение к ССФ. Все четные числа делятся на число ;. Число не является простым. Пусть переменные в нижеследующих выражениях выбираются из множества действительных чисел, а алгебраические знаки имеют свои обычные значения. Определить, истинны ли эти выражения:. Выразить области истинности предиката через области истинности предикатов и , если:. Пусть все приведенные предикаты определены на множестве действительных чисел. Привести следующие формулы логики предикатов сначала к предваренной нормальной форме ПНФ , затем к сколемовской нормальной форме СНФ и стандартной сколемовской форме ССФ. Пусть и два одноместных предиката, определенных на множестве таким образом, что высказывание - всегда истинно. Доказать, что высказывание - всегда ложно. Дать словесную формулировку следующим формулам:. Укажите, какие из следующих утверждений истины, а какие ложные. Нам важно ваше мнение! Был ли полезен опубликованный материал? A Спектральные характеристики для вещественной формы. FUTURE SIMPLE Формы простого будущего времени II. Заполнение титульного листа формы Расчета II. Формы проявления девиантного поведения. Порядок заполнения и представления статистической карточки формы N 6 Ocмoглacиe и его формы. Teст Колмогорова-Смирнова для количественной проверки формы распределения VI. Порядок заполнения и представления статистической карточки формы N 3 VI. Формы и методы обучения. Главная Случайная страница Контакты Спросить на ВикиКак. Равносильности логики предикатов Помимо эквивалентностей логики высказываний для логики предикатов справедливы следующие эквивалентности , , - предикаты, a - высказывание: Комбинация кванторов и отрицаний: Расширение области действия кванторов: Например, для нормальной формы предваренной нормальной формой будет. Всякую формулу логики предикатов можно свести к ПНФ, если использовать следующий алгоритм: Многократно пока это возможно делаются замены: После выполнения четвертого шага получаем ПНФ. Остановимся более подробно на третьем пункте алгоритма - переименовании переменных. Таким образом, переименовывать связанные переменные необходимо только в самом кванторе и в области действия этого квантора. Главная Случайная страница Контакты Спросить на ВикиКак END RotaBan. Многократно используя этот подход, получаем. Сколемовская нормальная форма СНФ строится в соответствии со следующими правилами: Формула логики предикатов представляется в ПНФ. Рассмотрим алгоритм равносильного преобразования произвольной бескванторной формулы в КНФ. Перейти к шагу 2. Преобразовать формулу в КНФ. Доказательство правильности логического вывода основано на следующих теоремах. Получаем СНФ, которая одновременно является и ССФ. Контрольные вопросы и упражнения Задание 1 Какие из следующих выражений являются предикатами. Выделите среди предикатов высказывания. Число - простое; 2. Все четные числа делятся на число ; 8. Все четные числа делятся на 2; 9. Имеется бесчисленное множество различных простых чисел; Задание 2 Пусть переменные в нижеследующих выражениях выбираются из множества действительных чисел, а алгебраические знаки имеют свои обычные значения. Определить, истинны ли эти выражения: Задание 3 Для действительных чисел записать на языке предикатов предложения, выражающие: Задание 4 Выразить области истинности предиката через области истинности предикатов и , если: Задание 5 Указать свободные и связанные переменные: Задание 6 Пусть все приведенные предикаты определены на множестве действительных чисел. Задание 7 Найти отрицание следующих формул. Задание 8 Привести следующие формулы логики предикатов сначала к предваренной нормальной форме ПНФ , затем к сколемовской нормальной форме СНФ и стандартной сколемовской форме ССФ. Задание 9 Пусть и два одноместных предиката, определенных на множестве таким образом, что высказывание - всегда истинно. Дать словесную формулировку следующим формулам: Задание 12 Доказать следующие равносильности. Задание 13 Какие из заданных формул являются общезначимыми? Задание 14 Доказать тождественную ложность формул.
Как вылазят зубы у детей очередность схема
Правила постановление правительстваот 05.05 2012 458
Перевод денег с банковской карты на телефон
Расписание трамваев бийск маяковского
Каталог производителей люков нажимных под плитку
Задачи модель управления запасами