Главная Случайная страница


Полезное:

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

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






ПОНЯТИЕ ПРЕДИКАТА И КВАНТОРНЫХ ОПЕРАЦИЙ





В алгебре логики высказывания структура высказываний и их содержание во внимание не принимаются. В то же время существуют рассуждения, зависящие от содержания используемых в них высказываний. Например, всякий ромб - параллелограмм; АВСМ - ромб, следовательно, АВСМ - параллелограмм. Таким образом, возникает необходимость в построении такой логической системы, средствами которой можно анализировать структуру утверждений, составленных из элементарных высказываний. Такой логической системой является логика предикатов, содержащая логику высказываний в качестве своей части.

В логике предикатов элементарное утверждение расчленяется на субъект (подлежащее) и предикат (сказуемое). Субъект - это то, о чем что-то утверждается в высказывании; предикат это то, что утверждается о субъекте. Например, в высказывании «6 - четное число», 6 - субъект; четное число- предикат. Заменим число 6 переменной х, получим утверждение «х- четное число». При одних значениях х это утверждение даёт истинные высказывания, а при других значениях х - ложные высказывания. Последнее утверждение является функцией одной переменной, определенной, например, на множестве N,и принимающей значения на множестве {0,1}.

Определение 1.1. Одноместным предикатом Р(х) называется произвольная функция от переменной х, определенная на множестве D, принимающая значения из множества {0,1}.

Множество D, на котором определен предикат Р(х), называется областью определения предиката Р или его универсом. Множество всех элементов хÎ D, при которых предикат принимает значение 1 (истина), называется множеством истинности предиката Р(х). Например, предикат - « х - четное число» определен на множестве натуральных чисел N , множеством истинности для него является множество всех четных чисел. Предикат S(х) - «-1£ sin (х) £ 1» определен на множестве действительных чисел R и его множество истинности - R.

Определение 1.2. п - местным предикатом Р ( ,…, ) называется функция п переменных , … , определенная на множестве = D ´ …´ D,



принимающая значения из множества {0,1}.

Предикат Q (x,y,z): является трехместным предикатом; предикат P ( ,…, ): - п - местный.

Выражение Р ( ,…, ) называют элементарной формулой или атомом. Класс формул содержит все элементарные формулы и составные формулы, построенные из элементарных многократным применением всех операции логики высказываний: Ø, Ù, Ú, ® и др. Кроме того вводится две новые операции " («для любого») и $ («для некоторых» или «существует»). Утверждение «для всех х верно P (х)» символически записывается "х P(х). Символ " называется квантором всеобщности. Утверждение "х P(х) истинно, если истинно P(с), какой бы конкретный предмет с из универса предиката P мы ни подставляли вместо х. Например, высказывание "х ( ³ 0) истинно, если универс - множество действительных чисел. Это высказывание ложно, если универс содержит комплексные числа, т.к. .

Символ $ называется квантором существования. Утверждение «существует такое х, что P(х)» символически записывается $х P(х). Символ $ называется квантором существования. Высказывание $х P (х) истинно, если в универсе найдется, хотя бы одно значение с, при котором P(с) истинно.

$х P (х) ложно, если при любом значении с ложно P(с). Пусть задан предикат Р(х): «число х кратно 3». Тогда на множестве натуральных чисел N высказывание $х Р(х) истинно, а "х Р(х) - ложно. По старшинству (в отношении расстановки скобок) кванторы имеют самый высокий приоритет. Формула

"х Р ® Q означает ("х Р) ® Q, а не "х (Р ® Q).

Кванторные операции применяются и к многоместным предикатам. В предикатах, зависящих от нескольких переменных, кванторы можно использовать несколько раз. Предикат " x " y " z Q (x,y,z) читается «для каждого x, для каждого y, для каждого z имеет место Q (x,y,z)», этот предикат истинен, когда для любого набора значений x,y,z из универса истинно. Высказывание $х $y $z Q (x,y,z) истинно, если универс для Q содержит, хотя бы один набор значений, для которых .

Предикат " Р ( ,…, ) зависит от (п - 1)- переменной в отличие от предиката Р ( ,…, ), который зависит от п переменных. Истинностное значение предиката " Р ( ,…, ) можно установить, если задать значения , …, , п ³ 2. Рассмотрим предикат P (x,y) « х:y - y делитель х», определенный на множестве N. Предикат "х Р(х, y) - «y - делитель любого х » зависит от y и не зависит от х, он истинен для y=1 и ложен для всех остальных значений y. Предикат $y Р(х, y) - «существует такое y, которое является делителем х» зависит от х и не зависит от y. Он будет истинен для любого значения х. Применение кванторных операций " и $ приводит к восьми возможным высказываниям:

1."y "х Р(х, y) - «для всякого y и для всякого х выполняется: y - делитель х».

2. $y " х Р(х, y) - «существует y, которое является делителем любого х».



3. "y$ х Р(х, y) - «для всякого y существует х такое, что х делится на y ».

4. $y $ х Р(х, y) - «существует y и существует х, такие, что y - делитель х».

5."х "y Р(х, y) - «для всякого х и для всякого y выполняется: y - делитель х».

6. "х $y Р(х, y) - «для всякого х существует такое y, что х делится на y».

7. $х $y Р(х, y) - «существует х и существует y, такие что y - делитель х».

8. $х"y Р(х, y)- «существует х такое, что для всякого y выполняется: х делится на y».

Легко видеть, что высказывания 1, 5 и 8 ложные, а высказывания 2, 3, 4, 6 и 7 истинны.

В формуле "х P(х) ($х P(х)) подформулу P называют областью действия вхождения квантора "х ($х). Вхождение переменной х в произвольную формулу Ф называют связанным, если х лежит в области действия некоторого вхождения квантора " или $. Если вхождение переменной х в формулу Ф не является связанным, то его называют свободным. Рассмотрим формулу: "х (Р(х) Ù $х Q (x, z) ®$y R(х, y)) Ú Q (z, x).

Отметим индексами все вхождения переменных, связанных кванторами. Расставлять индексы нужно начинать изнутри, продвигаясь наружу в соответствии с построением формулы из ее атомов Р(х), Q (x, z), R(х, y), Q (z, x).

"х3 (Р(х3) Ù $х1 Q (x1, z) ®$y2R(х3, y2)) Ú Q (z, x).

Вхождения переменных, оставшихся без индексов (два z и одно x), свободны.

Для формулы Ф запись Ф( ,…, ) обозначает, что все ее свободные переменные входят в последовательность ,…, .






Date: 2015-06-06; view: 354; Нарушение авторских прав

mydocx.ru - 2015-2020 year. (0.008 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию