логика 2 тема

20 Февраль 2014 →

92

. Курс лекций по математической ловимо

/1ОГИКЛ ПРЕДИКАТОВ

93

§ 5. Значение формулы логики предикатов

О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний, 2) значений свободных предметных переменных из множества М, 3) значений предикатных переменных.

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

В качестве примера рассмотрим формулу

(1)

в которой двухместный предикат Р(х,у) определен на множестве М ж М , где М = {0,1,2,...,п,...} .

В формулу (1) входит переменный предикат Р(х,у),

предметные переменные х, у, г, две из которых у и г -связанные кванторами, а х - свободная.

Возьмем за конкретное значение предиката Р(х,у) фиксированный предикат Р°(х,у): «х< у», а свободной переменной х придадим значение х° - 5 е М - Тогда при значениях у, меньших х° = 5 предикат .Р0(*°,гл принимает значение ложь, а импликация р(х, у) -> Р(у, г) при всех г е М принимают значение истина, то есть

высказывание Зу Уг{Р°(х,у}--> Р°(у,ги имеет значение «истина».

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

Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

Определение 2. Две формулы логики предикатов А я В называются равносильными, если они равносильны на всякой области.

Здесь, как в алгебре высказываний, для равносильных формул принято обозначение А е В .

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Рассмотрим основные из этих равносиль-ностей. Пусть а{х) и В(х — переменные предикаты, а С - переменное высказывание.

Тогда^

15 формул не от сканировались (писать в ручную )

Равносильность 1 означает тот простой факт, что,

если не для всех х истинно а(х), то существует х, при

котором будет истиной а(#).

Равносильность 2 означает тот простой факт, что, если не существует х, при котором истинно а(х) , то для

всех х будет истиной а(х).

Равносильности 3 и 4 получаются из равносильностей 1. и 2. соответственно, если от обеих их частей взять отрицания и воспользоваться законом двойного отрицания.

Докажем равносильность 5. Если предикаты а(х) и В(х) одновременно тождественно истинные, то будет тождественно истинным и предикат -А(*)& В(я:), а поэтому будут истинными высказывания:

УхА(х), УхВ(х), Чх[А(х)&В(х)]

То есть в этом случае обе части равносильности 5 принимают значение «истина».

Пусть теперь хотя бы один из предикатов, например, -А(лс), будет не тождественно истинным. Тогда не

тождественно истинным будет и предикат а(д:)& В(лс), а поэтому ложными будут высказывания

УхА(х), УхА(х)&УхВ(х), Ух[А(х)&В(х)],

то есть и в этом случае обе части равносильности 5 принимают одинаковые (ложные) значения. Этим исчерпывается доказательство равносильности 5.

Докажем равносильность 8. Пусть переменное высказывание С принимает значение «ложь». Тогда тождественно

истинным будет предикат С -> В(х) и, очевидно, истин-

ными будут высказывания С -» У#В(лс) и Ул|С -> В(х)1 ,

то есть в этом случае обе части равносильности 8 принимают одинаковые (истинные) значения.

Пусть теперь переменное высказывание С принимает значение «истина». Если при этом переменный предикат является тождественно истинным, то будет тождественно

истинным и предикат С -> -В(лг) , и, значит, истинными

будут высказывания УхВ(х) , С -» УдсВ(дг) , УхС ->• В(#)] ,

то есть и в этом случае обе части равносильности 8 принимают одинаковые (истинные) значения.

Если же предикат в(х) не является тождественно истинным, то не будет тождественно истинным и предикат С -> В(дс) , а поэтому ложными будут высказывания

(лг) , С ->• УхВ(х) , У*[С -> В(х)] .

Следовательно, и здесь обе части равносильности 8 принимают одинаковые (ложные) значения. Этим исчерпывается доказательство равносильности 8.

Аналогично доказывают остальные из перечисленных равносильностей.

В заключение отметим, что формула Удг| а(дг) v В(лс)| не равносильна формуле УхА(я:) v УлгВ(лс) , а формула

зх[а(л:)&в(х)] не равносильна формуле ЗхА(х)& ЗхВ(х) . Однако, справедливы равносильности

/хА(х) v УхВ(х) з УхА(х) v УуВ(у) з

= Vx(x) v УуВ(у)) а Ух/у(А(х) v В(у)) ,

ЗхА(х)& ЗхВ(х} = ЗхА(х)& ЗуВ(у) = Зх(А(х)&ЗуВ(у)) * ЗхЗу(А(х]&В(у)) .

§ 7. Общезначимость и выполнимость формул

Определение 1. Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула А принимает истинные значения-.

Определение 2. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.

Из определения 2 следует, что, если формула выполнима, то это еще не означает, что она выполнима в любой области.

Определение 3. Формула А называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Определение 4. Формула А называется общезначимой, если она тождественно истинная на всякой области.

Определение 5. Формула А называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Из приведенных определений следует:

1. Если формула А общезначима, то она и выполнима на всякой области.

Если формула А тождественно истинная в областиМ, то она и выполнима в этой области.

Если формула А тождественно ложная в областиМ, то она не выполнима в этой области.

Если формулаА не выполнима, то она тождественноложна на всякой области.

В связи с данными определениями естественно выделить два класса формул логики предикатов: выполнимых и не выполнимых формул.

Отметим, что общезначимую формулу называют логическим законом.

Приведем соответствующие примеры:

Пример 1. Формула УхЗуР(х, у) выполнима. Действительно, если Р[х, у) —предикат «х< у*, определенный в области м = Е х Е , где Е - {0,1,2,..., п,...} , то фор-

мула УхЗуР(х,у) тождественно истинная в области М, и, следовательно, выполнима в этой области. Однако, если предикат « х < у » рассматривается в конечной об-

ласти М1 - Е± х Е± , где е! = {0,1,2,..., а] , то формула

Чх~ЗуР(х, «/) будет тождественно ложной в области М^, и, следовательно, не выполнима в области М1. При этом ясно, что формула УхЗуР(х, у) не общезначима.

р(#)& Р(у И

выполнима.

Пример 2. Формула

Действительно, если р(х) - предикат «Число х - четно», определенный в области м = Е х Е • где #= (0,1,2, ...,п,...} , то эта формула тождественно истин-

ная в области М, и, следовательно, выполнима в области М. Однако, если предикат «Число х четно» рассматри-

вать в области Л/1 = е! х Е± , где Е1 - множество четных

чисел, то формула 3*Эм р(*)& Р(у) будет тождественно ложной в области М^ и, следовательно, не выполнимой.

100

. Курс лекций по математической логике

ЛОГИКА ПРЕДИКАТОВ

101

Пример 3. Формула V*Р(х) v Р(х) тождественно истинная в любой области М. Значит, она является общезначимой, то есть является логическим законом (закон исключенного третьего).

Пример 4. Формула V* [р(#)& Р(#)| тождественно ложная в любой области М, и поэтому она не выполнима.

Легко установить связь между общезначимостью и выполнимостью формул логики предикатов.

Теорема 1. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

Доказательство. Необходимость. Пусть формула А

общезначима. Тогда, очевидно, А - тождественно ложная формула в любой области, и поэтому формула А не выполнима.

Достаточность. Пусть формула А не выполнима в любой области. Тогда по определению невыполнимой

формулы А — тождественно ложная в любой области. Значит, формула А - тождественно истинная формула в любой области, и, следовательно, она общезначима.

Теорема 2. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы формула А была не общезначима.

Доказательство. Необходимость. Пусть формула А выполнима. Это означает, что существует область М и набор значений переменных, входящих в формулуА, при которых формула А принимает истинное значение. Очевидно, что на этом наборе значений переменных формула А принимает ложное значение, и, следовательно, формула А необщезначима.

Достаточность. Пусть формула А не общезначима. Тогда существует область М и набор значений переменных, входящих в формулу, при которых формула А принимает ложное значение. На этом наборе значений переменных формула А принимает значение «истина», и поэтому формула А выполнима.

§ 8. Пример формулы, выполнимой

в бесконечной области и невыполнимой

ни в какой конечной области

выполнима в бесконечной области и невыполнима ни в какой конечной области.

Допустим, что формула (1) выполнима в некоторой области М. В таком случае должен существовать фикси-

рованный предикат Р (лг, {/) , для которого формула (1)

принимает значение 1. Тогда для всех элементов х, у, г и хотя бы для одного элемента и из области М формула

принимает значение 1. Но в этом случае принимают значение 1 и формулы

Р*(х, у) (2)

Р*(х,х). (3)

Кроме того, для любого х из области М существует хотя бы один элемент и, для которого

Р*(х,и)(4)

тоже принимает значение 1.

Нетрудно убедиться, что в таком случае предикат

Р (х>у) представляет собой предикат, устанавливающий

отношение порядка между элементами области М. Действительно, из истинности формул (2) и (3) следует, что

предикат Р (х,у) удовлетворяет аксиомам порядка:

1- Р (х,х) ложь

2. Р*(х, у) ->. [р*(у, г) -> Р*(*,г)) -истина.

. Курс лекций по математической логике

„ОГИКАПРЕДИКАТОВ

103

В связи с этим условимся Р (#, у) выражать словами «х предшествует у». Как видно из истинности формулы (4), для каждого х должно существовать такое и, что

истинно Р*(х,и, то есть «х предшествует и». Возьмем

произвольный элемент области хг; среди элементов области должен найтись такой элемент лг2, что «#, предшествует х2* . Точно также должен найтись такой элемент ха, что *х2 предшествует л:8» и т. д. Получаем последовательность элементов

*!> Х2' '"' Хп'"'( )

В силу аксиом 1 и 2 каждый элемент этой последовательности отличен от каждого элемента с меньшим индексом, так как будет иметь место «л^ предшествует л-п». Но это означает, что любые два элемента последовательности (5) различны и область М бесконечна.

Покажем, что существует область, на которой формула (1) выполнима. Пусть М = {0,1,2,...,п,...} , а Р(х,у)

означает «х>у*. Тогда Р(х,у) означает «х< у». При

такой замене предиката Р(х,у) формула (1) принимает вид

УхУу/гЗих < х&((х < у) (у < г х < г))&(* < и)1

Очевидно, что на множестве М - {0,1,2,..., п,...} эта

формула истинна.

Из доказанного ясно, что, если область, на которой рассматривается формула (1), конечна, то формула (1) тождественно ложна на М, и, значит, не выполнима.

§ 10. Проблема разрешимости для общезначимости

и выполнимости, неразрешимость ее в общем случае

(без доказательства)

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

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

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

В 1936 году американский математик А.Черч доказал, что проблема разрешимости логики предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить, к какому классу формул относится любая формула логики предикатов.


See also:
Учебный материал
Похожие записи
  • тест метрология 1
    ООП: 260902.65 - Конструирование швейных изделийДисциплина: Метрология, стандартизация и сертификацияГруппа: бкид-1 Дата...
  • тест Мен в МП пол 3 курс студ
    Раздел 1. Общие подходы к менеджменту. 1. Английское слово «менеджмент» употребляется, когда...
  • тест КП 3
    ТЕСТЫ ПО КОНСТИТУЦИОННОМУ ПРАВУ РФ РАЗДЕЛ 1. Основы теории конституционного права. Конституционное...

Комментарии закрыты.