![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Определение 1. Формула Bлогики предикатов называется выполнимой в области M, если существуют значения переменных, входящих в эту формулу и принадлежащих множеству M, при которых формула Bпринимает истинные значения. Это определение очень похоже на то определение, которое мы дали для квантора существования в подразд. 3.1 относительно одного предиката. Данное определение отличается тем, что оно применяется не к отдельному предикату, а к формуле, состоящей из нескольких предикатов.
Определение 2. Формула Bназывается выполнимой, если существует область, на которой эта формула выполнима.
Это определение не следует понимать так, что если формула выполнима, то она выполнима в любой области. Для выполнимости формулы достаточно существования любой области, на которой она выполнима.
Определение 3. Формула Bназывается тождественно истинной в области M, если она принимает истинные значениядля всех значений переменных, входящих в эту формулу и принадлежащих множеству M.
Это определение по форме похоже на определение 2 подразд. 3.1., но отличается от него тем, что то определение давалось для предиката, а данное – для формулы, т.е. для предложения, состоящего из нескольких предикатов.
Определение 4. Формула Bназывается общезначимой, если она тождественно истинная на всякой области. Ранее в подразд. 2.9., мы вскользь упомянули о понятии общезначимость и отметили, что его используют иногда для обозначения тождественно истинных формул алгебры логики и обозначают символом ╞. Таким образом, мы видим, что преемственность и аналогия полностью сохраняются. И в алгебре логики, и в логике предикатов термин общезначимость употребляется для обозначения одинаковых по смыслу понятий – тождественно истинных формул. Только в логике предикатов понятие тождественно истинной формулы более широкое, чем в алгебре логики.
Определение 5. Формула называется тождественно ложной в области M, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и принадлежащих множеству M.
Как нетрудно видеть, это определение с точностью до обозначений совпадает с определением тождественно ложного предиката (определение 2, подразд. 3.1) и тождественно ложной формулы алгебры логики (определение 2, подразд. 1.3).
Из приведенных определений вытекают следующие свойства формул логики предикатов.
1. Если формула Bобщезначимая, то она и выполнима на всякой области.
2. Если формула B тождественно истинная в области M, то она и выполнима в этой области.
3. Если формула B тождественно ложная в области M, то она и не выполнима в этой области.
4. Если формула B не выполнима, то она тождественно ложна на всякой области.
На основании приведенных определений выделяют два класса формул логики предикатов: выполнимых и не выполнимых формул.
Рассмотрим примеры выполнимых, невыполнимых и общезначимых формул.
Пусть формула задана в виде: , где предикат
означает
и определен на области
, где
(символ
означает, что рассматриваемая переменная x принимает значения от a до b, то же самое и для
). Ясно, что в этом случае формула
тождественно истинная в области M, а поэтому и выполнима в этой области.
Если же предикат рассматривать в другой области, например
, где
, то формула
является тождественно ложной. Поскольку рассматриваемая формула не является тождественно истинной на всякой области, то она и не общезначима.
Рассмотрим другой пример. Пусть заданы предикаты: P(x)– “число кратно 7”, Q (у) – “число
кратно 3” и
, определенные в области
, где
. На какой области формула
выполнима, невыполнима и является ли она общезначимой? Дадим ответы на эти вопросы.
Так как для предиката P(x) , а для предиката Q(x)
, то для предиката
. А это означает, что существуют такие
и
, что среди натуральных чисел N всегда найдется такое число, при котором будет истинна формула
. Это число
. Например, для чисел
и
существует число
(это же число принадлежит и каждому в отдельности множеству
и
). Следовательно, рассматриваемая формула является истинной на множестве
, т.е. она выполнима в этой области (на этом множестве), а следовательно, и в области M.
Кроме того, какие бы числа y и y мы ни взяли соответственно из и
для них всегда найдется такое число из
, что будет истинна формула
, т.е. эта формула тождественно истинная в этой области.
Если же предикат мы будем рассматривать в области
, где
, то формула
является тождественно ложной. Действительно, среди пар чисел множества
не найдется ни одной такой пары чисел, для которой были бы истинны предикаты
. Следовательно, на множестве
формула
является тождественно ложной, а значит, и невыполнимой. И, наконец, эта формула не общезначима, так как. не является тождественно истинной на всякой области.
Интерес представляют общезначимые формулы, так как они являются логическими законами. Такой простейшей формулой является формула . Причем, независимо от конкретного смыслового содержания предиката
, эта формула является тождественно истинной в любой области M. Действительно,
.
Если квантор всеобщности применить к конъюнкции любого предиката и его отрицанию
, т.е.
, то получим тождественно ложную формулу в любой области
. Действительно,
В то же время значит, формула
является логическим законом.
Рассмотрим еще один пример, показывающий, как с помощью равносильных преобразований устанавливается общезначимость формул логики предикатов:
.
Таким образом, мы получили заданную формулу, которая является тождественно истинной для любых двух одноместных предикатов и в любой области (поскольку область заранее не оговаривалась). Значит, формула общезначима.
Дата публикования: 2015-01-10; Прочитано: 1107 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!