Студопедия Главная Случайная страница Обратная связь

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

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




Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной формой, если она получается из некоторой формулы ψ АВ, находящейся в ДНФ (КНФ), заменой всех пропозициональных переменных 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; просмотров: 1427. Нарушение авторских прав

codlug.info - Студопедия - 2014-2017 год . (0.007 сек.) русская версия | украинская версия