Как найти значение истинности предиката – Сайт, где вы сможете решить свои вопросы

Логика предикатов

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

Понятие предиката

В высказывании все четко: это — конкретное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

Определение 18.1. Определенным на множествах M_1,M_2,ldots,M_n n-местным предикатом называется предложение, содержащее переменных x_1,x_2,ldots,x_n , превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M_1,M_2,ldots,M_n соответственно.

Для n-местного предиката будем использовать обозначение P(x_1,x_2,ldots,x_n) . Переменные называют предметными, а элементы множеств M_1,M_2,ldots,M_n , которые эти переменные пробегают, — конкретными предметами. Всякий n-местный предикат P(x_1,x_2,ldots,x_n) , определенный на множествах , представляет собой функцию п аргументов, заданную на указанных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-высказыванием.

Рассмотрим пример. Предложение “Река впадает в озеро Байкал” является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной переменной название “Баргузин”, получим высказывание “Река Баргузин впадает в озеро Байкал”. Это высказывание истинно. Подставив вместо предметной переменной название “Днепр”, получим ложное высказывание “Река Днепр впадает в озеро Байкал”.

Другой пример. Предложение (выражение) “ x^2+y^2 leqslant 9 ” является двухместным предикатом, заданным над множествами mathbb{R},mathbb{R} . Множества, на которых задан двухместный предикат, совпадают (говорят, что “двухместный предикат задан на множестве $mathbb{R}^2$ “). Пара действительных чисел 2, 2 превращает данный предикат в истинное высказывание: “ 2^2+2^2 leqslant 9 “, а пара чисел 2, 3 — в ложное: “ 2^2+3^2 leqslant 9 “.

Отметим еще один подход к понятию предиката. Как отмечалось, предикат P(x_1,x_2,ldots,x_n) , определенный на множествах M_1,M_2,ldots,M_n , превращается в конкретное высказывание , если вместо предметных переменных подставить в него конкретные предметы (элементы a_1,a_2,ldots,a_n ) из множеств соответственно. Это высказывание может быть либо истинным, либо ложным, т. е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию аргументов, заданную на множествах M_1,M_2,ldots,M_n принимающую значение в двухэлементном множестве {0;1} . Иногда эту функцию и называют предикатом.

Классификация предикатов

Определение 18.2. Предикат P(x_1,x_2,ldots,x_n) , заданный на множествах M_1,M_2,ldots,M_n , называется:

а) тождественно истинным, если при любой подстановке вместо переменных x_1,x_2,ldots,x_n любых конкретных предметов a_1,a_2,ldots,a_n из множеств M_1,M_2,ldots,M_n соответственно он превращается в истинное высказывание P(a_1,a_2,ldots,a_n) ;

б) тождественно ложным, если при любой подстановке вместо переменных x_1,x_2,ldots,x_n любых конкретных предметов из множеств M_1,M_2,ldots,M_n соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов a_1,a_2,ldots,a_n из множеств M_1,M_2,ldots,M_n соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат P(x_1,x_2,ldots,x_n) последний превратится в истинное (ложное) высказывание P(a_1,a_2,ldots,a_n) .

Приведем примеры предикатов.

Одноместный предикат “Город расположен на берегу реки Волги”, определенный на множестве названий городов, является выполнимым, потому что существуют города, названия которых превращают данный предикат в истинное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержимого, но не тождественно ложного предиката (продумайте!).

В другом примере одноместный предикат “ sin^2x+cos^2x=1 “, определенный на множестве действительных чисел, тождественно истинный. Наконец, двухместный предикат “ x^2+y^2<0 “, заданный также на множестве действительных чисел, является тождественно ложным предикатом, потому что любая пара действительных чисел превращает его в ложное высказывание (не удовлетворяет ему).

Отметим некоторые достаточно очевидные закономерности взаимосвязей между предикатами различных типов (рекомендуется осмыслить их):

1) каждый тождественно истинный предикат является выполнимым, но обратное неверно;
2) каждый тождественно ложный предикат является опровержимым, но обратное неверно;
3) каждый не тождественно истинный предикат будет опровержимым, но, вообще говоря, не будет тождественно ложным;
4) каждый не тождественно ложный предикат будет выполнимым, но, вообще говоря, не будет тождественно истинным.

Множество истинности предиката

Определение 18.3. Множеством истинности предиката P(x_1,x_2,ldots,x_n) , заданного на множествах M_1,M_2,ldots,M_n , называется совокупность всех упорядоченных n-систем (a_1,a_2,ldots,a_n) , в которых a_1in M_1,a_2in M_2,ldots,a_nin M_n , таких, что данный предикат обращается в истинное высказывание P(a_1,a_2,ldots,a_n) при подстановке x_1=a_1,x_2=a_2,ldots,x_n=a_n . Это множество будем обозначать $P^{+}$ . Таким образом,

$P^{+}= bigl{(a_1,a_2,ldots,a_n)colon, lambda bigl(P(a_1,a_2, ldots, a_n)bigr)= 1bigr}.$

Множество $P^{+}$ истинности “-местного предиката P(a_1,a_2,ldots,a_n) представляет собой n-арное отношение между элементами множеств M_1,M_2,ldots,M_n . Если предикат P(x) — одноместный, заданный над множеством , то его множество истинности $P^{+}$ является подмножеством множества $Mcolon, P^{+}subseteq M$ .

Например, множеством истинности двухместного предиката “Точка принадлежит прямой “, заданного на множестве всех точек плоскости и на множестве всех прямых этой плоскости, является бинарное отношение принадлежности (инцидентности) между точками и прямыми плоскости. Другой пример. Множество истинности двухместного предиката S(x,y)colon~ x^2+y^2=9 , заданного на множестве $mathbb{R}^2$ , есть множество всех таких пар действительных чисел, которые являются координатами точек плоскости, образующими окружность с центром в начале координат и радиуса 3. Наконец, если A(x)colon “ |a|>2 ” — одноместный предикат над mathbb{R} , то $A^{+}= (-infty;-2)cup(2;+infty)$ , или $A^{+}= mathbb{R} setminus[-2;2]$ .

В терминах множества истинности легко выразить понятия, связанные с классификацией предикатов (определение 18.2). В самом деле, n-местный предикат P(x_1,x_2,ldots,x_n) , заданный на множествах M_1,M_2,ldots,M_n , будет:

а) тождественно истинным тогда и только тогда, когда $P^{+}=M_1times M_2times ldotstimes M_n$ ;
б) тождественно ложным тогда и только тогда, когда $P^{+}=varnothing$ ;
в) выполнимым тогда и только тогда, когда $P^{+}nevarnothing$ ;
г) опровержимым тогда и только тогда, когда $P^{+}ne M_1times M_2times ldotstimes M_n$ .

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

Равносильность и следование предикатов

Определение 18.4. Два n-местных предиката P(x_1,x_2,ldots,x_n) и Q(x_1,x_2,ldots,x_n) , заданных над одними и теми же множествами M_1,M_2,ldots,M_n , называются равносильными, если набор предметов (элементов) a_1in M_1, a_2in M_2, ldots, a_nin M_n превращает первый предикат в истинное высказывание P(a_1,a_2,ldots,a_n) в том и только в том случае, когда этот набор предметов превращает второй предикат в истинное высказывание Q(a_1,a_2,ldots,a_n) .

Другими словами (на языке множеств истинности), предикаты P(x_1,x_2,ldots,x_n) и Q(x_1,x_2,ldots,x_n) равносильны тогда и только тогда, когда их множества истинности совпадают. $P^{+}=Q^{+}$ .

Утверждение о равносильности двух предикатов и символически будем записывать так: PLeftrightarrow Q . Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех n-местных предикатов, определенных на множествах M_1,M_2,ldots,M_n , распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на множествах и принимающую значения в двухэлементном множестве {0;1} ). Переход от предиката P_1 к равносильному ему предикату P_2 называется равносильным преобразованием первого. Это понятие очень важно для школьной математики, потому что изучаемые в ней уравнения и неравенства представляют собой частные виды предикатов. Решение уравнения и неравенства есть поиск их множеств истинности. При таком поиске мы проделываем над уравнением и неравенством различные преобразования, и здесь важно, чтобы эти преобразования были равносильными, т. е. чтобы найденное множество оказалось бы множеством истинности именно исходного уравнения или неравенства. Аналогична ситуация при решении систем уравнений или неравенств.

Рассмотрим простой пример. Пусть требуется решить уравнение (найти множество истинности предиката): 4x-2=-3x-9 . Преобразуем его равносильным образом:

4x-2=-3x-9quad Leftrightarrowquad 4x+3x=-9+2quad Leftrightarrowquad x=-1

Ответ: {-1} — множество всех решений данного уравнения (множество истинности данного предиката).

Отметим следующее немаловажное обстоятельство: может быть так, что два предиката равносильны, если их рассматривать над одним множеством, и неравносильны, если их рассматривать над другим (в частности, объемлющим первое) множеством. Такова, например, ситуация с предикатами: sqrt{xcdot y}=15 и sqrt{x}cdotsqrt{y}=15 .

Определение 18.5. Предикат Q(x_1,x_2, ldots,x_n) , заданный над множествами M_1,M_2, ldots, M_n , называется следствием предиката P(x_1,x_2,ldots,x_n) , заданного над теми же множествами, если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат P(x_1,x_2,ldots,x_n) .

Другими словами (в терминах множеств истинности), можно сказать, что предикат является следствием предиката тогда и только тогда, когда $P^{+}subseteq Q^{+}$ .

Утверждение о том, что предикат является следствием предиката , будем символически записывать так: PRightarrow Q .

Например, одноместный предикат, определенный на множестве натуральных чисел, “ делится на 3″ является следствием одноместного предиката, определенного на том же множестве, “ делится на 6″. Из двух предикатов, упомянутых перед последним определением, первый будет следствием второго, если считать, что оба предиката заданы на множестве mathbb{Z} целых чисел.

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

Теорема 18.6. Каждые два тождественно истинных (тождественно ложных) предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом.

Теорема 18.7. Каждый тождественно истинный n-местный предикат является следствием любого другого n-местного предиката, определенного на тех же множествах. Каждый n-местный предикат является следствием любого тождественно ложного n-местного предиката, определенного на тех же множествах.

Теорема 18.8. Пусть P(x_1,x_2,ldots,x_n) и Q(x_1,x_2,ldots,x_n) — два n-местных предиката, определенные на одних и тех же множествах, такие, что Q(x_1, x_2, ldots, x_n) есть следствие . Тогда:

а) если P(x_1,x_2,ldots,x_n) тождественно истинный (выполнимый), то и Q(x_1, x_2, ldots, x_n) тождественно истинный (выполнимый);

б) если Q(x_1,x_2,ldots,x_n) тождественно ложный (опровержимый), то и P(x_1, x_2, ldots, x_n) тождественно ложный (опровержимый).

Доказательство теоремы 18.8:

а) Поскольку PRightarrow Q , поэтому $P^{+}subseteq Q^{+}$ . Если теперь тождественно истинный предикат, то

$P^{+}= M_1times M_2times ldotstimes M_n$ (где M_1,M_2,ldots,M_n — множества, на которых определены n-местные предикаты и ).

Но $Q^{+}subseteq M_1times M_2times ldotstimes M_n$ . Поэтому $Q^{+}= M_1times M_2times ldotstimes M_n$ , а, значит, предикат — тождественно истинный предикат. Если же — выполнимый предикат, то $P^{+}nevarnothing$ . Но $P^{+}subseteq Q^{+}$ . Тогда $Q^{+}nevarnothing$ и — выполнимый предикат.

б) Пусть — тождественно ложный предикат. Тогда $Q^{+}=varnothing$ . Но $P^{+}subseteq Q^{+}$ , поэтому $P^{+}=varnothing$ . Следовательно, предикат — тождественно ложный. Наконец, пусть — опровержимый предикат. Тогда $Q^{+}ne M_1times M_2times ldotstimes M_n$ . Поскольку, кроме того,

$P^{+}subseteq Q^{+}$ и $P^{+}subseteq M_1times M_2times ldotstimes M_n$ , то $P^{+}ne M_1times M_2times ldotstimes M_n$ .

Следовательно, предикат — опровержимый.

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Источник

Предикаты. Операции над предикатами

При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение %%P(x) : x^2 + 1 > 2%% с переменной %%x in mathbb R%%. Это предлождение не является высказыванием, так как нельзя сказать истинно оно или ложно. Однако, если заменить переменную %%x%% на какое-либо значение, например, %%x = 1%%, получаем высказывание %%2 > 2%%, которое является ложным. Заменив переменную %%x%% на значение %%x = 2%%, получим истинное высказывание %%5 > 2%%. Итак есть выражение %%P(x)%% не являющиееся высказыванием, но превращающееся в него при замене переменной %%x%% на ее произвольное значение из соответствующего множества.

Определение

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

Примеры

Следующие предложения являются одноместными предикатами:

%%P(x): x^ 2 + 1 > 2%%, где %%D%% — множество действительных чисел.
%%Q(x):%% Длина отрезка равна %%1%%, где %%D%% — множество всех отрезков прямой.

Следующие предложения не являются одноместными предикатами:

%%1 > 2%%.
Прямая %%x%% параллельна прямой %%y%%.

%%n%%-местный предикат

%%n%%-местым предикатом с областью определения %%D = D_1 times D_2 times ldots times D_n%% называется предикат %%P(x_1, x_2, ldots, x_n)%% от %%n%% переменных, который превращается в высказывание при замене переменных %%x_1, x_2, ldots, x_n%% на их значения из множеств %%D_1, D_2, ldots, D_n%% соответственно.

Тогда предложение прямая %%x%% параллельна прямой %%y%% является двуместным предикатом %%P(x, y)%%, где %%X, Y%% — множество всех прямых.

Область определения предиката

Рассмотрим %%n%%-местный предикат %%P(x_1, x_2, ldots, x_n)%%. В этом случае переменные берутся из множеств %%D_1, D_2, ldots, D_n%% соответственно. Можно рассмотреть множество %%D = D_1 times D_2 times ldots times D_n%% — декартово произведение множеств %%D_1, D_2, ldots, D_n%%, элементами которого являются всевозможные упорядоченные %%n%%-ки %%(d_1, d_2, ldots, d_n)%% элементов исходных множеств.

Множество %%D%% называется областью определения предиката.

Область истинности

Областью истинности предиката %%P(x_1, x_2, ldots, x_n)%% называется множество всех %%n%%-ок %%(d_1, d_2, ldots, d_n) in D%% таких, что при замене %%x_1%% на %%d_1%%, %%x_2%% на %%d_2%%, …, %%x_n%% на %%d_n%% получается истинное высказывание.

Пример

На множестве %%D = { 1, 2, 3, 4, 5, 6, 7, 8, 9}%% рассмотрим одноместный предикат %%P(x): x%% — простое число. Найти область истинности предиката %%P(x)%%.

Обозначим область истинности буквой %%A%%. Тогда %%A%% состоит из таких элементов, при которых выполняется предикат %%P(x)%%. Поэтому %%A = {2, 3, 5, 7}%%.

Операции над предикатами

Аналогично операциям для высказываний вводятся операции для предикатов.

Пусть %%P(x)%% и %%Q(x)%% — одноместные предикаты, определенные на множестве %%D%%.

Отрицанием предиката %%P(x)%% называется новый предикат, обозначаемый %%overline{P(x)}%% и являющийся ложным для тех и только тех %%x%%, для которых предикат %%P(x)%% истинный.

Конъюнкцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) land Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% истинны.

Дизъюнкцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) lor Q(x)%% и являющийся ложным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% ложны.

Импликацией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) rightarrow Q(x)%% и являющийся ложным для тех и только тех %%x%%, для которых предикаты %%P(x)%% истинный, а %%Q(x)%% ложный.

Эквиваленцией предикатов %%P(x)%% и %%Q(x)%% называется новый предикат, обозначаемый %%P(x) leftrightarrow Q(x)%% и являющийся истинным для тех и только тех %%x%%, для которых предикаты %%P(x)%% и %%Q(x)%% имеют одинаковые значения.

Применяя операции над предикатами, мы получаем составные предикаты, которые будем называть формулами алгебры предикатов.

Предикаты %%P(x)%% и %%Q(x)%% эквивалентные , если для любого значения переменной %%x%% их значения истинности совпадают. Обозначают $$P(x) equiv Q(x).$$

Законы алгебры предикатов

Для предикатов справедливы все законы, аналогичные законам алгебры логики высказываний¹.

В случае тождественно истинных и тождественно ложных предикатов имеем следующие определения.

Предикат %%P(x_1, x_2, ldots, x_n)%% называется тождественно истинным если при любой замене переменных %%x_1, x_2, ldots, x_n%% на их значения предикат превращается в истинное высказывание.

Предикат %%P(x_1, x_2, ldots, x_n)%% называется тождественно ложным если при любой замене переменных %%x_1, x_2, ldots, x_n%% на их значения предикат превращается в ложное высказывание.

Высказывание является частным случаем предиката, когда в предикате нет переменных. То есть высказывание является предикатом %%0%% порядка (от %%0%% переменных).

1. Законы алгебры логики высказываний.

Источник

Высказывания и предикаты. Кванторы

Высказывания
Предикаты
Кванторы
Примеры

п.1. Высказывания

Высказывание – это повествовательное предложение, про которое можно однозначно сказать, истинно оно или ложно.

Например:
«Число 13 – нечётное» – высказывание, истинное
«2 + 2 = 5» – высказывание, ложное
«Мы живём в XXI веке» – высказывание, истинное
«Который час?» – не высказывание, т.к. вопросительное предложение
«Вася Пупкин – хороший человек» – не высказывание, т.к. неоднозначно. Но, если определить множество людей, которые оцениваются, и правила их оценки так, что предложение приобретёт однозначность, оно станет высказыванием.

Высказывания обозначают большими латинскими буквами (A, B, C, X, Y, Z, …)

Например:
A: натуральное число a делится на 2;
B: натуральное число a чётное.
Заметим, немного забегая наперёд, что в данном случае из А следует В, и из В следует А. Говорят, что эти высказывания эквивалентны: A ⇔ B.

п.2. Предикаты

Предикат – это предложение с переменной P(x), которое становится высказыванием при подстановке определённого значения переменной.
Предикат P(x) является функцией, которая определена на некотором множестве значений {x}, и ставит ему в соответствие два значения {0; 1} – истина или ложь.

Например:
P(x): x – объект с четырьмя ногами
При x = слон – предикат становится истинным высказыванием, P(“слон” )=1
При x = муравей – предикат становится ложным высказыванием, т.к. у муравья 6 ног, P(муравей)=0
При x = стол – предикат становится истинным высказыванием, P(“стол” )=1
При x = человек – предикат становится ложным высказыванием, т.к. у человека 2 ноги, P(человек)=0

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

Например:
P(x):|x| ≥ 0 – выполняется при любом значении x, это тождественный предикат.
(mathrm{P(x)=1, forall xin mathbb{R}})

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

Например:
P(x, y): x делится на y – двуместный предикат, который становится истинным высказыванием на парах значений переменных (15;5), (14;7), (16;4) и т.д.
P(a, b):(a + b)² = a² + 2ab + b² – является тождественным двуместным предикатом, т.к. выполняется для любых a и b.

п.3. Кванторы

Квантор – логическая операция, ограничивающая область истинности предиката и создающая высказывание.

Вид квантора

Обозначение

Читается

Всеобщности

∀

«для любого…», «для всех…», «любой…»

Существования

∃

«существует…», «найдётся…»

Единственности и существования

∃!

«существует точно одно такое, что…», «существует и единственно…»

Пусть P(x) – одноместный предикат. Чтобы установить истинность высказывания (∃x)P(x), достаточно найти хотя бы один такой x*, что P(x* ) становится истинным высказыванием.

Например:

Высказывание

Формула

Доказательство истинности

Существуют натуральные числа, которые делятся на 13

(mathrm{(exists xin mathbb{N})x : 13})

Например x = 26

Существуют треугольники, у которых все углы равны

(∃ΔABC) ∠A = ∠B = ∠C

Например, равносторонний треугольник со стороной 1

Пусть P(x) – одноместный предикат. Чтобы установить ложность высказывания (∀x)P(x), достаточно найти хотя бы один такой x*, что P(x* ) становится ложным высказыванием.

Например:

Высказывание

Формула

Доказательство ложности

Любое натуральное число делится на 5

(mathrm{(forall xin mathbb{N})x : 5})

Например x = 6 на 5 не делится

У любого выпуклого четырехугольника диагонали перпендикулярны

(∀ABCD) AC ⊥ BD

Например, у прямоугольника со сторонами 3 и 4 угол между диагоналями ≈ 74° ≠ 90°

Пусть P(x) – одноместный предикат. Чтобы установить истинность высказывания (∀x)P(x), необходимо доказать, что предикат P(x) является тождеством.

Например:

Высказывание

Формула

Доказательство истинности (тождественности)

Разность квадратов двух любых выражений равна произведению суммы и разности

(mathrm{(forall x,y)x^2-y^2=(x+y)(x-y)})

Сумма углов любого треугольника равна 180°.

(∀ABC) ∠A + ∠B + ∠C = 180°

Третий класс задач (теорема) – самый сложный, т.к. требует не просто одного примера, а доказательства в общем случае.

п.4. Примеры

Пример 1. Запишите по два высказывания (A – истинное, B – ложное), относящиеся к
а) физике
A: Плотность равна отношению массы тела к его объему.
B: КПД механизма может быть больше 1.
б) химии
A: Гидроксид натрия – сильное основание.
B: Сульфат натрия – нерастворимая соль.
в) географии
A: На Земле шесть материков.
B: На Земле три океана.

Пример 2. Запишите по два предиката, относящиеся к
а) физике
A(h): Потенциальная энергия прямо пропорциональна высоте h.
B(v): Сила лобового сопротивления прямо пропорциональна квадрату скорости v².
б) химии
A(x,y): Между основанием x и кислотой y проходит реакция нейтрализации.
B(x): Металл x вытесняет водород из HCl.
в) географии
A(x,y,z): День x является днём y солнцестояния в z полушарии.
B(x,y): Река x впадает в море y.

Пример 3. С каким из кванторов предикат x² + 4 = 12 станет истинным высказыванием?
Если запишем (∀x) x² + 4 = 12 – это ложное высказывание, т.к., например, при x=0 оно не выполняется.
Если запишем (∃x) x² + 4 = 12 – это истинное высказывание, т.к., например, при (mathrm{x=2sqrt{2}}), оно выполняется.
Если запишем (∃x!) x² + 4 = 12 – это ложное высказывание, т.е. решений у данного уравнения не одно, а два: (mathrm{x_{1,2}=2sqrt{2}})
Ответ: квантор существования ∃.

Пример 4. Найдите область истинности предиката: $$ P(x): left{ begin{array}{ l } mathrm{x^2-11x+28geq 0} & \ mathrm{x^2-11x+18lt 0} & end{array}right. $$ Решаем систему: $$ left{ begin{array}{ l } mathrm{(x-4)(x-7)geq 0} & \ mathrm{(x-2)(x-9)lt 0} & end{array}right. $$ Пример 4
Область истинности предиката: x ∈ (2;4] ∪ [7;9)
P(x) = 1 приx ∈ (2;4] ∪ [7;9)

Источник

Гусева
А.И. Дискретная
математика: Математическая логика

Лекции 14-15

Исчисление
предикатов

Основные понятия

Одноместным предикатом P(x)
называется всякая функция одного
переменного, аргумент который х
определен на некотором множестве М,
а значение функции определены на
множестве {0,1}[1].

Множество М, на котором задан
предикат, называется областью
определения предиката.

Множество I_p,
на котором предикат принимает только
истинные значения, называется областью
истинности предиката P(x).

Предикат P(x)
называется тождественно истинным
(тождественно ложным) на множестве
М, если I_p=М
(I_p=0).

N-местным
предикатом Q(x₁,
x₂,…,x_n)
называется всякая функция n
переменных, определенная на множестве
и принимающая значение на множестве
{0,1}.

Предикат P(x)
является следствием Q(x)
()
, если

Предикаты P(x)
и Q(x)
равносильны (),
если
,
т.е. они являются следствием друг друга.

Логические операции над предикатами

Так как предикаты принимают значения
0 и 1, к ним можно применять все операции
алгебры высказываний. Пусть на некотором
множестве М заданы два предиката P(x)
и Q(x).

Конъюнкцией двух предикатов
P(x)
и Q(x)
называется новый предикат
,
который равен 1 при тех и только при тех
значениях
,
при которых каждый из предикатов
принимает значение «истина», и принимает
значение «ложь» во всех остальных
случаях.

Очевидно, что областью истинностью
предиката

является
.

Дизъюнкцией двух предикатов
P(x)
и Q(x)
называется новый предикат
,
который равен 0 при тех и только при тех
значениях
,
при которых каждый из предикатов
принимает значение «ложь», и принимает
значение «истина» во всех остальных
случаях.

Очевидно, что областью истинностью
предиката

является
.

Отрицанием предиката P(x)
называется новый предикат
,
который равен 0 при всех значениях
,
при которых P(x)
равен значению «истина», и равен 1 при
всех значениях
,
при которых P(x)
равен значению «ложь».

Очевидно, что областью истинностью
предиката

является
.

Импликацией предикатов P(x)
и Q(x)
называется новый предикат
,
который равен 0 при тех и только при тех
значениях
,
при которых P(x)
принимает значение «истина», а Q(x)
– значение «ложь», и принимает значение
«истина» во всех остальных случаях.

Очевидно, что областью истинностью
предиката

является
.

Задача 1

Заданы предикаты
,
и

на множестве натуральных чисел N:
:
«число Х делится на 5»

:
«число Х четное».

Найти область истинности предикатов

,

Решение

Так как I_p
= {5, 10, 15, 20, …. 5n,
..} и I_Q
= {2, 4, 6, 8, 10, … 2n,
..}, то

={10,
20, …,20n,..},

={2,
4, 5, 6, 8, 10, … 2n,5n,
..},

={5,
10, 15,… ,5n,
..}
{1, 3, 5, … 2n-1,
..}= {1, 3, 5, 7, 9, 10, … 2n-1,5n,
..}.

Задача 2

Задан
предикат
:>0
на
множестве рациональных чисел R.
Найти
область истинности предиката
.

Решение

Найдем область, на которой данный
предикат может быть определен. Поскольку
знаменатель дроби не может быть равен
0, то
.
Для того, чтобы наша дробь была
положительной, необходимо, чтобы знаки
числителя и знаменателя совпадали:

Отсюда

Кванторные
операции над предикатами

Задан предикат,
определенный на множестве М.
Если а – некий элемент из
множества М, то его подстановка
вместо х в предикат,
превращает этот предикат в высказывание

.

В логике предикатов существуют две
кванторные операции, которые превращают
одноместный предикат в высказывание и
связывают переменные.

Пусть задан предикат,
определенный на множестве М.

Тогда под выражением
понимаем
высказывание, истинное тогда и только
тогда, когда

истинен для каждого элемента х
из М, и ложное в противном
случае. Это высказывание не зависит от
х, его словесное выражение
выглядит так «Для любого х

истинно». Символ

называется квантором всеобщности.

Переменная х в предикате

свободна, в высказывании

переменная х связана квантором
всеобщности.

Под выражением
понимаем
высказывание, истинное тогда и только
тогда, когда существует элемент х
из М, для которого

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

истинно». Символ

называется квантором существования.

Переменная х в предикате

свободна, в высказывании

переменная х связана квантором
существования.

Кванторные
операции применяются и к многоместным
предикатам.

Например, применение кванторной операции

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

Рассмотрим предикат
,
определенный на множестве M={a₁,
a₂,…,a_n}.
Если

тождественно истинен, то истинными
будут высказывания
….
При этом истинными будут выказывание

и конъюнкция
.
Если найдется хотя бы один элемент
a_jиз М, на котором
,
то ложными будут высказывания

и конъюнкция
.
Следовательно, существует равносильность

Рассмотрим предикат
,
определенный на множестве M={a₁,
a₂,…,a_n}.
Если

тождественно ложен, то ложными будут
высказывания
….
При этом ложными будут выказывание

и дизъюнкция
.
Если найдется хотя бы один элемент
a_jиз М, на котором
,
то истинными будут высказывания

и дизъюнкция
.
Следовательно, существует равносильность

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

Исчисление предикатов

Исчисление предикатов – это формальная
теория, в которой определены следующие
компоненты [2].

Алфавит:

связки основные

вспомогательные

служебные символы ( , )

кванторы всеобщности

существования

предметные константы a,
b,…a₁,
b₁,

переменные x,y,….x₁,y₁

предметные предикаты P,
Q, R,
….

функторы f,
g, h,….

Формулы: (определены в нотации
Бэкуса-Наура)

<формула> ::=
<атом> ││<формула>
<формула>
│

<переменная>
<формула> │
<переменная><формула>

<атом> ::=
<предикат>( <список термов> )

<список
термов> ::= <терм> │<терм> , <список
термов>

<терм> ::=
<константа> │<переменная> │<функтор>
(<список термов> )

Аксиомы:

Кроме того, выполняется любая система
аксиом исчисления высказываний.

Правила вывода:

,
,

Исчисление предикатов, в котором кванторы
могут связывать только предметные
переменные, но не предикаты или функторы,
называется исчислением первого
порядка.

Исчисления, в которых кванторы связывают
не только предметные переменные, но и
предикаты, функторы и т.д., называются
исчислениями высших порядков.

Равносильные формулы

Рассмотрим основные равносильности
исчисления предикатов. Их можно разбить
на четыре группы [1,3].

1. Равносильности для двойственности

2. Равносильности для конъюнкции и
квантора всеобщности

3. Равносильности для дизъюнкции и
квантора существования

4. Вынесение константы

Задача 3

Доказать равносильность.

Решение

Если предикаты P(x)
и Q(x)
тождественно истинны, то тождественно
истинен предикат
,
а поэтому, будут истинны высказывания

т.е. обе части равносильности принимают
значение истина.

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

Предваренная нормальная
форма

Говорят, что формула исчисления предикатов
имеет нормальную форму, если она содержит
только операции конъюнкция, дизъюнкция
и кванторные операции, а оперция отрицания
отнесена к элементарным формулам.

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

Среди нормальных форм выделяют
предваренные нормальные формы (ПНФ), в
которых кванторные операции либо
полностью отсутствуют, либо они
используются после всех операций алгебры
логики.

Например, приведем рассматриваемую
формулу к ПНФ

А для формулы необходимы следующие
преобразования.

Теорема

Всякая
формула исчисления предикатов может
быть приведена к предваренной нормальной
форме

Общезначимость и
выполнимость

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

Формула А выполнима, если
существует область, на которой она
выполнима.

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

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

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

Разрешимость

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

Ответ на этот вопрос для бесконечных
областей дает теорема Черча.

Теорема Черча

Проблема
разрешимости исчисления предикатов в
общем виде неразрешима

Очевидно, что проблема разрешимости
для конечных областей разрешима.

Литература

Лихтарникова
Л.М., Сукачева Т.Г. Математическая
логика/Курс лекций. – СПб.: Издательство
«Лань», 1998.-288с
.Новиков Ф.А.
Дискретная математика для программистов.
– СПб.: Питер, 2001. – 304с
Горбатов В.А.
Фундаментальные основы дискретной
математики. – М.: Наука. Физматлит,
1999.-544с

Соседние файлы в папке ДМ_К1

#
10.05.2014205.31 Кб291.doc
#
10.05.2014198.66 Кб3710.doc
#
#
#
10.05.2014158.21 Кб942.doc
#
10.05.2014144.9 Кб473.doc
#
10.05.2014123.39 Кб244.doc
#
10.05.2014127.49 Кб235.doc
#
10.05.2014119.81 Кб246.doc

Источник

Определение. Предикатом называется повествовательное предложение, содержащее предметные переменные, определённые на соответствующих мно- жествах; при замене переменных конкретными значениями (элементами) этих множеств предложение обращается в высказывание, т. е. принимает значение «истинно» или «ложно».

Определение. Предикатом называется функция P : M ⁿ → B , где B = { 0,1 } , M – любое множество, т. е. функция P , сопоставляющая вектору (x₁ , x₂ ,…, x_n ) значения 0 или 1.

Множество M называется предметной областью предиката P ,

x₁ , x₂ ,…, x_n – предметные переменные,

P – предикатный символ,

n – местность предиката,

декартово произведение M × M × … × M область определения предиката P .

Обозначение: P (x₁ , x₂ ,…, x_n– n – местный предикат, заданный на множестве M .

Определение. Областью истинности предиката P называется подмножество I_p ⊆ Mⁿ его предметной области, на элементах которого значения предиката равны 1.

Область истинности предиката, выраженного предикатной формулой, определяется областями истинности составляющих и применяемыми в формуле операциями: I_PvQ = I_P ∪ I_Q, I_{P ∧ Q} = I_P ∩ I_Q , I_P→Q = I_P ∪ I_Q, I_P = I_P .

Задача 3.1. Найти область истинности предиката

P ( X, Y ) = (( X + Y ) – нечётно ) ∨ (( X – Y ) делятся на 3) , где X = {1;3;6;7}, Y = {2;4;5}.

Решение.

Составим таблицы истинности для предикатов P₁ ( X, Y ) = (( X + Y) – нечётно), P₂( X, Y ) = (( X – Y ) – делятся на 3) , P = P₁ ∨ P₂.

I_P = I _P₁∨P₂ = I_P1 ∪ I_P2 = {(1,2), (1,4), (3,2), (3,4), (6,5), (7,2), (7,4)} ∪ {(1,4), (7,4)} = {(1,2), (1,4), (3,2), (3,4), (6,4), (7,2), (7,4)}.
Ответ: I_P = {(1,2), (1,4), (3,2), (3,4), (6,4), (7,2), (7,4)}.

Задача 3.2. Найти область истинности предиката

P ( X ) = (( число 3 не делитель x ) → ( x ≤ 6 ))

на множестве однозначных натуральных чисел.

Решение.

Определим области истинности предикатов P₁ = {число 3 не не делитель x},

P₂ = {x ≤ 6}, P = P₁→ P₂ .

I_P₁ = {1,2,4,5,7,8}, I_P₂ = {1,2,3,4,5,6}, I_P = I_P₁→P₂ = I_P₁ = {1,2,3,4,5,6,9}.

Ответ: I _P = {1,2,3,4,5,6,9}.

Задачи для самостоятельного решения

Найти область истинности предиката

P ( X, Y ) = ((( X – Y ) – нечетно ) ∧ ( min ( X, Y) – четно )), где X = {2;5;6;8};
P ( X ,Y ) = (( X + Y )) – делится на 3) → (( X + Y ) > 5), где X = {2;5;6;8}, Y = {3;6;9};
P ( X, Y ) = ((( X – Y ) – нечётно ) ∧ ( |Y-X| ≤ 1 )), где X = {5;8;9}, Y = {4;7;8;10};
P ( X, Y ) = (( X – Y ) – чётно ) ∨ (( X + Y ) – делится на 3), где X = {5;8;9}, Y = {4;7;8;10};
P ( X ) = (( число 3 делитель x ) ∨ ( x ≤ 6 )), заданного на множестве однозначных натуральных чисел;
P ( X ) = ((( число 3 делитель x ) ∧ ( x > 6 )), заданного на множестве однозначных натуральных чисел;
P ( X ) = (( x ≥ 3 ) ∧ ( x ≤ 10 )), заданного на множестве всех действительных чисел;
P ( X ) = (( x² ≤ 4 ) ∧ ( x -1 ≥ 1 )), заданного на множестве всех действительных чисел;
P ( X ) = (( x ≤ 0 ) ∧ ( x² – 2x ≤ 0 )), заданного на множестве всех действительных чисел;
P ( X ) = (( x³ – 6x² +11x – 6 = 0 ) ∧ ( x² – 4x + 3 = 0 )),заданного на множестве всех действительных чисел.

Источник

Логика предикатов

Понятие предиката

Классификация предикатов

Множество истинности предиката

Равносильность и следование предикатов

Предикаты. Операции над предикатами

Определение

Примеры

%%n%%-местный предикат

Область определения предиката

Область истинности

Пример

Операции над предикатами

Законы алгебры предикатов

Высказывания и предикаты. Кванторы

п.1. Высказывания

п.2. Предикаты

п.3. Кванторы

п.4. Примеры

Лекции 14-15

Решение

Задача 2

Решение

Исчисление предикатов

Равносильные формулы

Решение

Предваренная нормальная форма

Общезначимость и выполнимость

Вам также может понравиться

Как найти тангенс угла 75 градусов равен

Правила кирхгофа как найти направление тока

Как составить акт действие

Добавить комментарий Отменить ответ

Предваренная нормальная
форма

Общезначимость и
выполнимость