Студопедия — Пренексная нормальная форма в логике предикатов
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Пренексная нормальная форма в логике предикатов






Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной формой, если она получается из некоторой формулы ψ АВ, находящейся в ДНФ (КНФ), заменой всех пропозициональных переменных x1, …, xn на некоторые атомарные формулы φ 1, …, φ n сигнатуры Σ соответственно.

Говорят, что формула φ сигнатуры Σ находится в пренексной нормальной форме (ПНФ), если она имеет вид Q1x1…Qnxnψ, где Qi, ‑ кванторы (1≤ i≤ n), n ψ – дизъюнктивная нормальная форма.

Теорема 1. Для любой формулы φ сигнатуры Σ существует ПНФ ψ, эквивалентная формуле φ;.

Опишим алгоритм приведения формулы к ПНФ:

1) выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность φ → ψ ≡ φ ∨ ψ;

2) используя законы де Моргана (φ ∧ ψ)≡ φ ∨ ψ, (φ ∨ ψ)≡ φ ∧ ψ

3) и эквивалентности xφ ≡ xφ, xφ ≡ ,

переносим все отрицания к атомарным подформулам и сокращаем двойные отрицания по правилу φ ≡ φ;

4) приводим формулу к виду Q1x1…Qnxnψ, где Qi, ‑ кванторы (1≤ i≤ n), n ψ – бескванторная формула, пользуясь эквивалентностями

x(φ ∧ ψ)≡ xφ ∧ ψ, x(φ ∨ ψ)≡ xφ ∨ ψ,

x(φ ∧ ψ)≡ xφ ∧ ψ, x(φ ∨ ψ)≡ xφ ∨ ψ,

xφ ≡ x(φ) xφ ≡ x(φ)

5) используя закон дистрибутивности

φ ∧ (ψ ∨ χ)≡ (φ ∧ ψ)∨ (φ ∧ χ),

преобразуем формулу ψ к дизъюнктивной нормальной форме.

Пример 10. Формулу χ x yφ (x, y)→ x yψ (x, y) привести к ПНФ, считая формулы φ и ψ атомарными.

Решение. Избавившись от импликации, получаем

χ ≡ ( x yφ (x, y))∨ x yψ (x, y).

Переносим отрицание к атомарной подформуле φ (x, y):

χ ≡ x yφ (x, y)∨ x yψ (x, y).

Так как в формуле x yψ (x, y) переменные х, у являются связанными, то по пп. 2΄, 3΄ утверждения 2 имеем

χ ≡ x y(φ (x, y)∨ x yψ (x, y)).

Пусть u, v ‑ некоторые новые переменные. Тогда по пп. 4, 4΄ утверждения 2 получаем

χ ≡ x y(φ (x, y)∨ u v ψ (u, v)),

откуда по по пп. 2΄, 3΄ утверждения 2

χ ≡ x y u v(φ (x, y)∨ ψ (u, v)).

Формула φ (x, y)∨ ψ (u, v) является дизъюнктивной нормальной формой, а значит, формула x y u v(φ (x, y)∨ ψ (u, v)) является ПНФ.







Дата добавления: 2014-11-10; просмотров: 3775. Нарушение авторских прав; Мы поможем в написании вашей работы!



Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Дренирование желчных протоков Показаниями к дренированию желчных протоков являются декомпрессия на фоне внутрипротоковой гипертензии, интраоперационная холангиография, контроль за динамикой восстановления пассажа желчи в 12-перстную кишку...

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

КОНСТРУКЦИЯ КОЛЕСНОЙ ПАРЫ ВАГОНА Тип колёсной пары определяется типом оси и диаметром колес. Согласно ГОСТ 4835-2006* устанавливаются типы колесных пар для грузовых вагонов с осями РУ1Ш и РВ2Ш и колесами диаметром по кругу катания 957 мм. Номинальный диаметр колеса – 950 мм...

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия