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



Скачать 16.97 Kb.
Дата11.07.2014
Размер16.97 Kb.
ТипДокументы
§7. Нормальные формы формул логики предикатов.
В логике предикатов, как и в логике высказываний, формулы могут иметь нормальную форму, т.е. существуют эквивалентные нормальные формы представления любых предикатных формул. При этом, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную.

Определение.

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



Пример 1.

.

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

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

,

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




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

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

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

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

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

Пример 2.

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



Пример 3.


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

– ПНФ.

Пример 4.



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

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

Пример 5.


Похожие:

Нормальные формы формул логики предикатов iconКонтрольная работа по логике высказываний, нормальной форме формул, теореме Поста и минимизации формул
Предназначены для выполнения контрольной и домашней работ в части логики и исчисления высказываний, нормальной формы формул, полных...
Нормальные формы формул логики предикатов iconЛекция 4 Общезначимые формулы логики предикатов Общезначимые формулы
Для доказательства общезначимости формул логики предикатов используется аппарат логики высказываний, дополненный теоремами для выражений,...
Нормальные формы формул логики предикатов iconПрограмма дисциплины по кафедре Прикладная математика математическая логика утверждена научно-методическим советом университета для направлений подготовки
Охватывает круг вопросов, связанных с изучением формальных теорий, элементов теории множеств, логики высказываний и логики предикатов,...
Нормальные формы формул логики предикатов iconЛабораторная работа №1 По предмету: «Искусственный интеллект.» "Знакомство с Prolog".
Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов...
Нормальные формы формул логики предикатов iconПравила выводимости. Проблема аксиоматического исчисления высказываний. Производные правила вывода. Доказательство некоторых законов логики. Логика предикатов: Понятие предиката
Применение языка логики предикатов для записи математических предложений, определений, построение отрицание предложений
Нормальные формы формул логики предикатов iconПрименение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений
Язык логики предикатов удобен для записи математических предложений и определений. Он дает возможность выражать логические связи...
Нормальные формы формул логики предикатов iconЗначение формулы логики предикатов
Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1 значений входящих в формулу переменных...
Нормальные формы формул логики предикатов icon5. 11. Как упростить логическую формулу?
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для...
Нормальные формы формул логики предикатов iconЛогические операции над предикатами
Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов...
Нормальные формы формул логики предикатов iconВопросы к зачету по дисциплине «Дискретная математика» 3ТО(з)
Конъюнктивная и дизъюнктивная нормальные формы. Непротиворечивость конъюнктивной нормальной формы
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org