Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Рk(х1, х2, ..., хk): Мk → {1,0}

⇐ Предыдущая107108109110111112113114115116Следующая ⇒


Например, если Х — множество действительных чисел, то х2 > 1 — одноместный предикат.

Если X, У — множества действительных чисел, то ху = 5 — двуместный предикат.

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

Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в истинное высказывание, он называется тождественно истинным.

Если предикат при подстановке любых конкретных элементов из соответствующих множеств обращается в ложное высказывание, он называется тождественно ложным.

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

Например, если к предикатам «х = y» и «х < у» — обозначим их соответственно Р(х, у) и Q(x, у) — применить операцию конъюнкции, то получим новый предикат Р(х, у) Q(x, у).

Язык логики предикатов.

Символами X, Y, Z, Xi, Yi,... в логике предикатов принято обозначать предметные переменные, т.е. от­дельные предметы — имена. Они могут быть простыми и сложны­ми. Если такие предметы (имена) не содержат дополнительной информации о себе, то они называются собственными (простыми), например «земля», «студент» и др. Если такое имя содержит наряду с самим предметом его отдельные свойства, то оно является слож­ным, например «автор романа «Анна Каренина», «перпендикуляр­ные прямые», «взаимно-однозначное соответствие» и др.

Символами а, b, с, ai bi... принято обозначать константы или предметные постоянные, т. е. конкретные значения имен предметов из указанной предметной области. Высказывательные формы, вхо­дящие в предикаты, называют также препозиционными функция­ми, или предикаторами.

Любое непустое множество содержит два подмножества: само себя и пустое. Это свойство автоматически выделяет из области определения два случая.

Тождественно-истинным называется предикат, истинный всю­ду на области определения: Т(Р) = D(P).

Тождественно-ложным называется предикат, множество истинности которого пусто: Т(Р) = 0.

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

Логические операции (связки) над предикатами

Связки, анало­гичные связкам булевой алгебры и исчисления высказываний, соответствуют логическим операциям над предикатами. Операции над n -местными предикатами вводятся аналогично одноместным.

Пусть, например, Р(х,...) и Q(x,...) — предикаты, которые
определены на множестве D, причем Т(Р) и T(Q) — их множества истинности.

Отрицанием предиката Р(х,.. .) называется предикат Р(х), также определенный на множестве D и истинный при тех значениях переменной х, при которых Р(х,. ..) ложен, т.е. Т(Р) = D\T(P) (рис. 5.1).

Рассмотрим примеры.

1. Для предикатов Р(х): «х — четное число» и Q(x): «х кратно 7» конъюнкцией Р(х) л Q(x) служит предикат «х — четное и кратное 7 число» или «х — число, кратное 14».

Рис. 5.1. Множество истинности Рис. 5.2. Множество истинности

предиката Р(х) конъюнкции предикатов

Пример.

Предикат Р(х): «х — простое число» определен на множестве D = Z целых чисел, а его областью истинности являют­ся только простые числа, т. е. числа, имеющие два делителя: х и 1. Тогда предикат «х — составное (целое) число», также определен­ный на Z, будет отрицанием предиката Р(х), т.е. , а его обла­стью истинности будет множество всех ц елых составных чисел (имеющих три и более делителей): \T(P).

Аналогично вводятся и остальные операции.

Конъюнкция предикатов Р(х,...) и Q(x,...) есть новый преди­кат , определенный на множестве D и истинный при тех значениях переменной х, при которых истинны одновременно оба предиката Р(х, ...) и Q(x,. ..), поэтому (рис. 5.2).

Пример.

Для предикатов P(x): «x – четное число» и Q(x): «x – кратное 7» конъюнкцией служит предикат «x – четное и кратное 7 число» или «x –число, кратное 14»

Пример.

Решить систему неравенств означает: решить первое неравенство, т.е. определить Т(Р1), решить второе неравенство — определить Т(Р2): ,<=> . Определить, при каких х верны и первое, и второе неравенства. В данном случае система означает конъюнкцию высказываний <=> 5 < х =< 8, а ответ является пересечением Т(Р1) и T(Р2) (рис. 5.3), т. е. интервалом 5 < х < 8.

Рис. 5.3. Графическое решение системы неравенств

Обратите внимание, что в итоговый ответ вошла конъюнкция высказываний, эквивалентных данным в условии, а не самих ис­ходных.

Дизъюнкцией предикатов Р(х,...) и Q(x,...) называется пре­дикат Р(х)vQ(x), определенный на множестве D и истинный при тех значениях переменной х, при которых истинен хотя бы один из предикатов Р(х) или Q(x).

Поэтому (рис. 5.4).

Рис. 5.4. Множество истинности дизъюнкции предикатов

Пример.

Для предикатов Р(х): «х— число, кратное 3» и Q(x): «х — число, оканчивающееся на 3», определенных на N, дизъюнк­цией Р(х)vQ(x) служит предикат: «х — число или кратное 3, или оканчивающееся цифрой 3».

Так, при решении уравнений (неравенств), левая часть кото­рых есть произведение нескольких множителей, а правая — нуль, они разбиваются на совокупность уравнений (неравенств).

Пример.

х2 - 8х - 20 = 0 <=> (х - 10)(х + 2) = 0 <=> х - 10 = 0 (Р1) или х + 2 = 0 (Р2). Таким образом, нужно найти T(P1) = {10}, T(Р1) = {-2} и их объединение: Т(Р) = {-2, 10}.

Импликацией предиката Р(х,...) в Q(x, ...) называется преди­кат Р(х) → Q(x), определенный на множестве D и ложный только при тех значениях переменной х, при которой предикат Р(х,...) истинен, а предикат Q(x,...) ложен. В полном соответствии с формулой алгебры логики имеем: и (рис. 5.5).

Рис. 5.5. Множество истинности импликации предикатов

Пример.

Импликацией предикатов Р(х): «х — нечетное число» и Q(x): «х кратно 5», определенных на , служит предикат Р(х) → Q(x): «Если х — нечетное число, то х кратно 5».

Здесь Т(Р) = {y|(ymod2) = 1} = {1, 3, 5,...};

T(Q) = {y|(ymod5) = 0}= {0, 5, 10,...}.

Тогда D/T(Р) = {у| (ymod2) = 0} ={0, 2, 4,...};

Импликация верна, если число кратно двум или пяти.

Замечание. Поскольку в данном нами алфавите связка → является основной, a и - дополнительными, то дадим введение конъюнкции и дизъюнкции через и :

,

.

Эквиваленцией предикатов Р(х,...) и Q(x,...) называется пре­дикат Р(х) в Q(x), определенный на множестве D и истинный при тех значениях переменной х, при которых либо оба предиката истинны, либо оба предиката ложны.

Поэтому .

В силу законов Де Мор­гана . Если Т(Р) = T(Q), то Т(Р = Q) = D.

Пример.

Эквивалентны преди­каты Р(х): «х — натуральное число, кратное 3» и Q{x): «х — нату­ральное число, сумма цифр которого делится на 3».

Кванторы

Помимо операций алгебры высказываний, в логике предикатов есть две операции, которые связаны с природой предикатов. Пусть дан предикат Р(х), зависящий от одной переменной и определенный на поле М.

а) Выражение ( х)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен для всех предметов из поля М. Выражение ( х)Р(х) читается «для всякого х, Р(х)», здесь символ — квантор общности.

б) Выражение ( х)Р(х) означает высказывание, истинное только в том случае, когда предикат Р(х) истинен хотя бы для одного предмета из поля М. Выражение ( х)Р(х) читается «существует х, что Р(х) », символ — квантор существования.

Рассмотрим примеры применения операций квантирования к предикатам. Пусть даны предикаты над полем натуральных чисел:

1) х2 = х х, тогда ( х) (х2 = х х) — истинное высказывание;

2) х + 2 = 7, тогда ( х) (х+2 = 7) — ложное высказывание; а ( х) (х + 2 = 7) — истинное высказывание;

3) х + 2 = х, тогда ( х) (х + 2 = х) — ложное высказывание.

Название Прочтение Обозначение
Квантор общности «все», «всякий», «каждый», «любой»
Квантор существования «Хотя бы один», «найдется», «существует»

Квантор общности — это оператор, приводящий в соответствии любому заданному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 1 тогда и только тогда, когда у = 1 при всех значениях х.

Квантор существования — это оператор, приводящий в соответствии любому одноместному предикату у = Р(х) такую двузначную логическую переменную z, которая принимает значение 0 тогда и только тогда, когда у = 0 при всех значениях х.

Рассмотрим некоторые общие свойства введенных операторов. В соответствии с определениями кванторов логическая переменная z в выражениях

z = ( х)Р(х)

z = ( х)Р(х)

уже не является функцией предметной переменной х.

Для того чтобы отметить отсутствие функциональной зависимости z от х, предметную переменную х в таких случаях называют связанной. Несвязанные переменные называют свободными.

Например, в предикате

( х) A(х,y) ( z) B(z,v)

переменные х и z — связанные, а у и v — свободные.

Если квантор общности или квантор существования применяется не к одноместному предикату, а к какому-нибудь k -местному предикату, то в результате этого получается снова предикат, но за счет связывания одной предметной переменной получаемый предикат будет ( k-1)-местным.

Кванторы.

Для количественных характеристик обычно исполь­зуют понятия «все», «некоторые», «существуют» и др., кото­рые называют кванторами (от лат. quantum — сколько). Мы часто пользовались символами и , заменяющими слова «любой» и «существует». Покажем действие этих кванторов в высказыва­тельных формах. Часть формулы, на которую распространяется действие квантора, называется областью действия этого кван­тора. Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действий квантора, после которого стоит переменная. Все прочие вхождения — свободные. Напри­мер, в выражении переменная х связывает свойство пре­диката и квантор общности. Грубо говоря, от этой переменной, ее конкретного вида и имени, ничего не зависит, т.е. и суть одно и то же. Так, можно произвольно называть индекс суммирования в рядах и переменную интегрирования в определенных интегралах. В частности, в определении множества как совокупности всех объектов, удовлетворяющих характери­стическому свойству, использовалась запись G = {х\Р(х)}. Оче­видно, что в предикате со связанной переменной ее так же легко можно заменить на любую другую. При этом множество все равно будет совокупностью тех же элементов, удовлетворяющих свой­ству Р. Переменная, не являющаяся связанной, называется сво­бодной, если после подстановки вместо нее имени некоторых конкретных объектов предикат превращается в осмысленное пред­ложение.

Между кванторами и и логическими операциями существу­ет тесная связь. Пусть предикат Р(х) определен на конечном мно­жестве D= {a1, а2,...,аn}. Тогда высказывание будет истинным только в том случае, если истинны одновременно все высказывания Р(а1), Р(а2),..., Р(ап), т.е. если истинна их конъ­юнкция: . Аналогично высказывание означает, что оно истинно, когда истинно хотя бы одно из высказываний Р(а1), Р(а2),…, Р(ап). Тогда должна быть ис­тинной дизъюнкция высказываний . По­этому для конечной области определения выполняются равно­сильности: и .

Таким образом, кванторы общности и существования являют­ся дополнениями и аналогами соответственно логических опера­ций конъюнкции и дизъюнкции.

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

Пример.

Записать с помощью формул логики предикатов следующее утверждение: «Для лечения любого известного компьютерного вируса имеются программы. Существуют новые (неизвестные) компьютерные вирусы, для лечения которых программы еще не разработаны»

Решение.

Введем обозначения элементарных формул:

A(x) – известен компьютерный вирус x;

B(x) – для лечения вируса x существует программа ;

Тогда с помощью логических связок и кванторов получим формулы:

- против вируса x нет программы;

- любой вирус известен;

- существуют новые (неизвестные) вирусы;

- если вирус давно известен, то имеется программа для его лечения;

- существуют (появились) новые вирусы, для лечения которых программы еще не разработаны.

Тогда формализованное исходное утверждение примет вид:

Отношение следования и равносильности между высказывательными формами связаны с тождественно-истинными импликацией и эквиваленцией, следовательно, их можно записать с помощью кванторов общности:

тождественно

тождественно

Пример.

Запись х2 - 5х = 0 <=> х(х - 5) = 0 является не форму­лой, а истинным высказыванием о равносильности двух формул, представленных в виде уравнений. В то же время справедлива за­пись (х2 - 5х = 0) ≡ (х(х - 5) = 0), выражающая истинное высказывание, которое включает операцию эквиваленции в каче­стве составляющей.

Поэтому логическое следование можно определить через имп­ликацию, а равносильность через эквиваленцию. Так, для эквива­ленции справедливо: «Две высказывательные формы Q1 и Q2 ис­тинны или ложны (Q1 <=> Q2) одновременно с высказыванием », что и было ранее введено.

Существует различие в употреблении знаков и «»,«», «» и «».

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

Знаки «» и «» обозначают определенные отношения между высказывательными формами, не входя в них в качестве состав­ной части.

Квантификация многоместных высказывательных форм

Пусть Q(x1, х2,..., хn) — n -местная высказывательная форма. Ее замену на высказывательную форму xi Q(x1, х2,..., хn) либо на xi Q(x1, х2,..., хn) называют квантификацией высказывательной формы Q(x1, х2,..., хn) по переменной xi.

В процессе такой квантификации эта i -я переменная связыва­ется одним из кванторов, а n -местная высказывательная форма превращается в (п- 1) -местную.

Это аналогично тому, что если функцию f(x1, х2, …, хn) проинтегрировать от а до b по пере­менной xi, то полученный результат будет функцией от п -1 пе­ременной и не будет зависеть от хi: I(х1,…, хi-1, xi+1, …, хn) = Так, интеграл от функции одной (п = 1) переменной является константой и вообще ни от чего не зависит.

Пусть дана двухместная высказывательная форма х - у < 0, определенная на . Произведем квантификацию по переменной у («навесим» квантор общности). Получим одномест­ную высказывательную форму со свободной пере­менной х. Если для фиксированного х = х0 будет выполнено , то эта высказывательная форма превращается в истин­ное высказывание, например, при х = -2, а при х = 3 — в ложное.

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

При «навешивании» кванторов на двухместную высказывательную форму Q(x,у) можно получить одну из восьми комбинаций:

1) — «для любого х и любого у Q(x,у)»;

2) — «для любого у и любого х Q(x,у)»;

3) ) — «существует х и существует у, такие, что Q(x,у)»;

4) — «существует у и существует х, такие, что Q(x,у))»;

5) — «существует х, такой, что для любого у Q(x,у)»;

6) — «для всякого х существует у, такой, что Q(x,у)»;

7) — «существует у, такой, что для любого х Q(x, у)»;

8) — «для всякого у существует х, такой, что Q(x, у)».

Очевидно, что первое и второе высказывания, а также третье и четвертое тождественны между собой, их значения истинности совпадают. Между остальными полученными высказываниями нельзя установить тождественности: если истинно высказывание 5, то истинным будет и высказывание 8, причем обратное неверно. Аналогично, если истинно высказывание 7, то истинно и выска­зывание 6, но не наоборот. То есть, если кванторы одноименны (1 — 4), то их порядок не играет роли и полученные высказывания эквивалентны. Если кванторы разноименные (5 — 8), то их поря­док в полученном высказывании принципиально важен.

Например, для двухместного предиката «Город х находится в стране у» высказывание имеет вид 0 -местного пре­диката и читается «В каждой стране у есть некоторый город х». Оно будет истинным, в то время как высказывание чита­ется «Существует город х, находящийся во всех странах у» будет ложным.

Пусть даны х, у — две различные переменные, F(x), Ф(х) и Q(x,у) — любые формулы логики предикатов и М — формула, не содержащая свободных вхождений х. Тогда справедливы равно­сильности, представленные с учетом двойственности кванторов и в табл. 5.5.

Таблица 5.5

Следствия и равносильности логики предикатов

Равносильности для Правила Равносильности для
Правила перестановки кванторов
Перенос отрицания с квантора на предикат
 
 
 
 
⇐ Предыдущая107108109110111112113114115116Следующая ⇒


Дата публикования: 2014-11-04; Прочитано: 1101 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...