Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Отношение логического следования. Определение І.Формулы G совместимы по истинности, если и только если модель, в которой каждая формула из G принимает значение «истина»
|
|
Определение І.Формулы G совместимы по истинности, если и только если модель, в которой каждая формула из G принимает значение «истина». В противном случае эти формулы несовместимы по истинности.
Определение П.Формулы G совместимы по ложности, если и только если существует модель, в которой каждая формула из G принимает значение «ложь». В противном случае эти формулы несовместимы по ложности.
Проиллюстрируем приведенные определения на примерах. Возьмем формулы:
$х P(x, y) и $x Ø P(x, y)
и покажем, что они совместимы по истинности.
Для этого достаточно указать конкретную модель M = < U, I>, в которойобе формулыбудут истинными.
В качестве универсума рассуждения U выберем множество городов. Пусть функция І сопоставляет двухместной предикаторной константе P множество таких пар городов, первый из которыхт расположен южнее другого, причем предметной переменной у приписано значение город Киев.
Рассмотрим теперь случай, когда в формуле P(x, y) переменная х означает Одессу. Поскольку Одесса расположена южнее Киева, то пара < Одесса, Киев> содержится в I(P), так что в этом случае | P(x, y) |M = и. А отсюда следует, что | $х R(x, y Ž M = и.
Пусть теперь переменная х означает Львов. Поскольку этот город не расположен южнее Киева, то пара < Львов, Киев > не содержится в І(P), и в этом случае |P(x, y)| M = л.
Тогда |Ø P(x, y)| M = и. Отсюда следует, что |$x Ø P(x, y)| M = и.
Таким образом, формулы $х P(x, y) и $x Ø P(x, y) в модели M = < U, I> принимают значение «истина», что свидетельствует об их совместимоти по истинности.
Покажем теперь, что формулы:
" х Ø P(x, y) и " x P(x, y)
совместимы по ложности. Возьмем ту же модель M = < U, I>. В предыдущем примере мы установили, при каком значении предметных переменных |P(x, y)| M = и. В этом же случае будем иметь | Ø P(x, y) Ž M = л, азначит и Ž " x Ø P(x, y) Ž M = л. Также было установлено, когда |P(x, y | M = л. В этом случае и Ž " xP(x, y) Ž M = л.
Выходит, что в данной модели M = < U, I> формулы
" х Ø P(x, y) и " x P(x, y) совместимы по ложности.
С помощью довольно простых рассуждений можно показать, что формулы
а) " х Ø P(x, y) и " x P(x, y) являются несовместимыми по истинности, а
б) $x P(x, y) и $x Ø P(x, y) являются несовместимыми по ложности.
1. Чтобы показать несовместимость по истинности формул
" x Ø P(x, y) и " x P(x, y),
предположим противное. Тогда Ž Ø P(x, y) Ž M = и и Ž P(x, y) Ž M = и. Но признание истинности формулы Ø P(x, y) обязывает нас указать на ложность формулы P(x, y). Следовательно, наше предположение приводит к противоречию.
2. Для того, чтобы установить несовместимость по ложности формул
$х P(x, y) и $x Ø P(x, y),
предположим, что они совместимы по ложности в некоторой модели M = < U, I>.
Тогда Ž P(x, y) Ž M = л и Ž Ø P(x, y) Ž M = л. Но признание ложности формулы Ø P(x, y) вынуждает признать истинность формулы P(x, y). Таким образом, мы пришли к противоречию. Значит, рассмотренные формулы несовместимы по ложности.
Подведем некоторые итоги. Формулы " х Ø P(x, y) и " x P(x, y) находятся в отношении противоположности, посколькуони совместимы по ложности и несовместимы по истинности, а формулы $х P(x, y) и $x Ø P(x, y) находятся в отношении подпротивности, поскольку они совместимы по истинности и несовместимы по ложности.
Определение Ш.Из множества формул G логически следует В (что записывается как G |=В), если и только если не существует модели, в которой каждая из формул G принимает значение «истина», а формула В – значение «ложь».
Проиллюстрируем примером данное определение. Покажем, что
из Р(а) и Q(a)логически следует $x (P(x) & Q(x)), то есть что
P(a), Q(a) |= $x (P(x) & Q(x)).
Предположим, что из Р(а) и Q(a) не следует $x (P(x) & Q (x)), т.е.
P(a), Q(a)Ø |= $x (P(x) & Q(x)).
В таком случае существует модель M = < U, I>, в которойформулы Р(а) и Q(a) – истинны, а формула $х (P(x) & Q(x)) - ложна.
Истнность формул Р(а) и Q(a) означает, что І(а) Î І(Р) и І(а) Î І(Q). Поэтому, если произвольной предметной переменной х приписать значение І(а), то
Ž P(x) Ž M = и и Ž Q(x) Ž M | = и.
Отсюда следует, что Ž P(x) & Q(x) Ž M = и при приписывании переменной х значения І(а). Выходит, что Ž $x (P(x) & Q(x)) Ž M = и, что противоречит сделанному допущению. Итак, из формул P(a) и Q(a) логически следует формула $х (P(x) & Q(x)).