![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Применяя к переменным предикатам операции ;
; →; ↔; Ї;
;
, получим формулы логики предикатов,
Формулой логики предикатов называется выражение, составленное из переменных предикатов с помощью логических операций и кванторов и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.
Пример.
(( х) W(х, у)
В) → U(z) — формула логики предикатов. Формула логики предикатов называется тавтологией, если при подстановке любых конкретных предикатов она всегда обращается в тождественно истинный предикат.
Формулы
Определение формулы лежит в основе так называемой логики предикатов первого порядка, в которой разрешается квантифицировать (связывать кванторами) только предметные переменные. Логика предикатов первого порядка включает в себя все формулы логики высказываний, все равносильности исчисления высказываний, а также большинство правил вывода умозаключений из классической логики. Поэтому язык логики предикатов дает возможность анализировать рассуждения естественного языка и науки, делать выводы в различных формальных системах.
Так, высказывательная форма является формулой. В то же время высказывательная форма
не будет формулой, поскольку в формуле
переменная х связана квантором существования, тогда как в формуле Q(x) эта же переменная свободна.
В чем ценность формальных теорий?
Для описания каких объектов используется логика предикатов?
Вообще говоря, ценность любой формальной теории заключается в возможности описывать с ее помощью произвольные объекты и связи между ними.
Теоремы.
К числу основных равносильностей логики предикатов относят:
1. .
2. .
3. .
4. .
5. .
6. .
Сформулируем следующие правила.
(1) Формула логики предикатов называется атомарной, т.е. элементарной, если в ней нет связанных переменных.
(2) Пусть F — формула, тогда неF — тоже формула. Свободные и связанные переменные формулы неF — это соответственно свободные и связанные переменные формулы F.
(3) Пусть F и G — формулы, причем в них нет предметных переменных, которые были бы связаны в одной формуле и свободны в другой.
Тогда F G, F
G, F → G, F ↔ G — формулы, в которых свободные переменные формул F и G остаются свободными, а связанные — связанными.
(4) Пусть F — формула, содержащая свободную переменную х. Тогда ( х)F, (
х)F — тоже формулы, в которых переменная х связана, а остальные свободные переменные, входящие в F, остаются свободными.
Заметим, что по определению формулы никакая переменная не может быть одновременно свободной и связанной.
Значение формулы определено лишь тогда, когда задана какая-то интерпретация входящих в нее символов.
Под интерпретацией понимают систему М=<М,f>, состоящую из непустого множества М и соответствия f, которое сопоставляет каждой формуле определенный предикат. При заданной интерпретации предметные переменные пробегают множество М, а логические символы и символы кванторов имеют свой обычный смысл.
Равносильные формулы логики предикатов
Пусть формулы F и G имеют одно и то же множество свободных переменных (в частности, пустое). Формулы F и G равносильны в данной интерпретации, если они принимают одинаковые значения на любом наборе свободных переменных, т. е. выражают в данной интерпретации один и тот же предикат.
Формулы F и G равносильны на множестве М, если они принимают одинаковые значения во всех интерпретациях заданных на множестве М.
Формулы F и G равносильны в логике предикатов, если они равносильны на всех множествах (F =G).
Рассмотрим правила перехода от одних формул к другим, им равносильным.
(1) Перенос квантора через отрицание. Пусть W(х) — формула, содержащая свободную переменную х. Тогда справедливы равносильности:
,
,
,
.
(2) Вынос квантора за скобки. Пусть формула W(х) содержит свободную переменную х, а формула В не содержит переменной х. Формулы W(х) и В удовлетворяют третьему правилу создания формул. Тогда справедливы равносильности:
,
,
,
.
(3) Перестановка одноименных кванторов. Имеем
,
.
(4) Переименование связанных переменных. Заменяя связанную переменную формулы W другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получим формулу, равносильную W.
Приведенные и нормальные формы в логике предикатов
Рассмотрим способ упрощения формул, опирающийся на приведенные равносильности.
Формулы, в которых из логических символов имеются только символы конъюнкция, дизъюнкция и отрицание, причем символ отрицания встречается над символами предикатов, будем называть приведенными.
Пример.
Формула ( x1) A1(1)(x2)
(
x1)не(А2(2)(x2,x3)) — приведенная;
Формула не( x2) A1(1)(x2) → А2(1)(x1) — неприведенная.
Для любой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают.
Такая приведенная формула называется приведенной формой данной формулы.
В логике высказываний мы ввели две нормальные формы — дизъюнктивную нормальную форму и конъюнктивную нормальную форму.
В логике предикатов также имеется нормальная форма, цель которой — упрощение процедуры доказательств.
Приведенная формула называется нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди (т.е. логические символы и символы предикатов стоят в области действия каждого квантора).
Для любой приведенной формулы существует равносильная ей нормальная формула той же длины (под длиной формулы будем понимать общее число входящих в нее символов предикатов, логических символов и символов кванторов).
Нормальная формула называется нормальной формой данной формулы.
Приведем несколько формул, находящихся в нормальной форме:
,
,
.
Дата публикования: 2014-11-04; Прочитано: 375 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!