Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Этапы получения предварённой формы.Содержание книги
Поиск на нашем сайте
1. Исключить связки эквивалентности и импликации. 2. Преобразовать все вхождения отрицания, состоящие непосредственно перед атомами. Многократно (пока это возможно) делаются замены: 3. Переименовать (если необходимо) связанные переменные таким образом, чтобы никакая переменная не имела бы одновременно свободных и связанных вхождений: " X A (X) º " T A (T) X, T Î M. Остановимся более подробно на этом пункте алгоритма. Пусть Р произвольная формула логики предикатов. Формулу Р получим из формулы Р заменой связанных переменных другими переменными, отличными от всех свободных переменных формулы Р, причем заменяемая переменная в формуле Р должна меняться одинаковым образом всюду в области действия квантора, связывающего данную переменную, и в самом кванторе. В этом случае Р равносильно Р. Таким образом, переименовывать связанные переменные необходимо только в самом кванторе и в области действия этого квантора. Одинаковые переменные, для которых связывающие их кванторы имеют различные области действия, могут переименовываться разным образом или одна из них может переименовываться, а другая нет. 4. Удаление тех квантификаций, область действия которых не содержит вхождений квантифицированной переменной. Вынесение кванторов (перемещение всех квантификаций в начало формулы). Для этого используется правила: (" X A & " X B) º" X (A & B), (" X A (X) & B) º" X (A (X) & B), если В не содержит X, (A & " X B (X)) º" X (A & B (X)), если A не содержит X, ($ X A (X) & B) º $ X (A (X) & B), если В не содержит X, (A & $ X B (X)) º $ X (A & B (X)), если A не содержит X. А также используются формулы эквивалентности для исчисления предикатов. Помимо эквивалентностей логики высказываний для логики предикатов справедливы следующие эквивалентности (А (х), В (х), Р (x, y) – предикаты, С – высказывание): Комбинация кванторов: 1. " x " yP (x, y) = " y " xP (x, y), 2. $ x $ yP (x, y) = $ y $ xP (x, y), 3. " x $ yP (x, y) ≠ $ y " xP (x, y). Комбинация кванторов и отрицаний: ; ; . Расширение области действия кванторов (С не зависит от х): 1. C &" xB (x) = " x [ C&B (x)], 2. C Ú" xB (x) = " x [ C Ú B (x)], 3. C →" xB (x) = " x [ C→B (x)], 4. " x [ B (x) →C ] = $ xB (x) →C, 5. $ x [ C Ú B (x)] = C Ú$ xB (x), 6. $ x [ C & B (x)] = C &$ xB (x), 7. $ x [ C → B (x)] = C → $ xB (x), 8. $ x [ B (x) → C ] = " xB (x) →C. Расширение области действия кванторов: 1. " xA (x)&" xB (x) = " x [ A (x)& B (x)], 2. $ x [ A (x)Ú B (x)] = $ xA (x)Ú$ xB (x), 3. $ xA (x)&$ xB (x) = $ x $ y [ A (x) &B (y)], 4. $ x [ A (x)& B (x)] → $ xA (x)&$ xB (x), 5. " xA (x)Ú" xB (x) → " x (A (x)Ú B (x)).
После выполнения четвертого шага получаем ПНФ. Одна формула может допускать много эквивалентных предварённых форм. Вид результата зависит от порядка применения правил, а также от произвола при переименовании переменных.
|
||||
Последнее изменение этой страницы: 2021-11-27; просмотров: 91; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.227.140.100 (0.007 с.) |