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

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

§7. Нормальные формы формул логики предикатов.

В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т. е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.

Говорят, что формула логики предикатов имеет приведенную нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

.

Получили приведенную нормальную форму исходной формулы.

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т. е. ПНФ формулы логике предикатов имеет вид

,

где под символом понимается один из кванторов или , а формула А кванторов не содержит.

Процедура получения (приведения) ПНФ. Состоит в следующем:

1. Используя формулы 18, 19 (отнесенные к предикатам), заменить операции и

на .

2. Используя форм, а также форм, 17, представить предикатную формулу таким образом, чтобы символы отрицания относились непосредственно к символам предикатов (и, таким образом, мы приводим исходную формулу к приведенной форме).

3. Для формул, содержащих подформулы вида , вести новые переменные, позволяющие использовать соотношения 46, 47, 49, 50 или 53, 54.

4. С помощью формул 35 – 38, 46, 47, 49, 50, 53, 54 получить формулу в виде ПНФ.

обозначим в предикате Q переменную y через z

обозначим в предикате Q переменную x через z

– ПНФ.

последний предикат не зависит от переменной z

два первых предиката не зависят от переменной u — ПНФ.

Читайте также:  Leeco le 2 игры

Определение. Формула логики предикатов, в которой из операций логики высказываний имеются только конъюнкция, дизъюнкция и отрицание, причем отрицание относится только к элементарным предикатам, называется Приведенной формой предиката.

Теорема 1. Для всякого предиката существует равносильная ему приведенная нормальная форма.

Доказательство. Действительно, все операции в данной предикатной формуле можно выразить через конъюнкцию, дизъюнкцию и отрицание (например, в виде ДНФ). Если после этого некоторые отрицания будут относиться к частям формулы, содержащим кванторы, то отрицания можно “снять” с кванторов согласно равносильностям 1 и 2, а “снять” отрицания с конъюнкций и дизъюнкций можно, следуя законам де Моргана. После всех описанных преобразований предикат, очевидно, будет представлен в приведенной форме.

Определение. Предикатная формула вида , где КI – кванторы, ХI – различные связанные переменные, а F Предикатная формула без кванторов, находящаяся в приведенной форме, называется Предваренной нормальной формой предиката.

Теорема 2. Для всякого предиката существует равносильная ему предваренная нормальная форма.

Доказательство. Согласно теореме 1 можно считать, что предикат уже преобразован в приведенную форму. Если никакая операция навешивания квантора при этом не находится в области действия операций и , то приведенная форма уже является предваренной нормальной. Поэтому предположим, что описанные ситуации имеют место, и будем называть такие явления (когда какой–либо квантор находится в области действия данной операции или ) Беспорядками.

Для данной формулы число беспорядков конечно, так как конечно число символов. Выберем какой-либо беспорядок (скажем, первый слева) и покажем, что путем тождественных преобразований его можно убрать. Возможны два случая:

1) Беспорядок имеет вид: "X Р или $Х Р, где Р – не зависит от Х. Тогда "Х или $Х можно просто отбросить, поскольку "ХР º Р и $ХР º Р.

Читайте также:  Приложение ant radio service что это

2) Беспорядок имеет вид: "ХР(Х) или $ХР(Х). Если переменная Х еще встречается в формуле, то предварительно сделав замену согласно формулам

Где T – переменная, не встречающаяся в формуле, беспорядок представляется в виде правой части одной из формул 10 13. Применяя эти формулы (т. е., заменяя правые части на левые), беспорядок устраняется.

Проделав такие преобразования конечное число раз, все беспорядки будут ликвидированы, что и требовалось доказать.

Пример. Привести к предваренной нормальной форме следующий предикат:

Для того, чтобы оценить ресурс, необходимо авторизоваться.

Учебное пособие предназначено для студентов МАТИ, изучающих дисциплины "Математическая логика и теория алгоритмов" и "Дискретная математика", обучающихся по специальностям "Информатика и вычислительная техника" и "Системы автоматизированного проектирования". Оно ставит своей целью помочь студентам лучше усвоить теоретический и практический материал. Пособие посвящено изучению важных разделов математической логики (алгебры высказываний, логики предикатов) и теории алгоритмов. Его основу составляют конспекты лекций, которые читались студентам. Данное пособие содержит большое количество примеров, иллюстрирующих основные понятия указанных разделов математической логики и теории алгоритмов и утверждения, касающиеся этих понятий. Издание также может быть полезно для студентов других специальностей и преподавателей.

Ссылка на основную публикацию
Adblock detector