Что такое порядок местность предиката

Источник

Логика высказываний (стр. 6 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Прямая теорема равносильна обратно противоположной:

.

Эта равносильность имеет специальное название – закон контрапозиции. Заметим, что обратная и противоположная теоремы также связаны законом контрапозиции.

Пример. Вместо доказательства утверждения “Если нечетное число, то m и n нечетны” () согласно закону контрапозиции можно доказывать утверждение (): “Если хотя бы одно из чисел m или n четно, то четно”.

К методам косвенного доказательства относятся доказательства “от противного”. Схемы таких доказательств основаны на равносильностях (справедливость которых можно проверить по таблице истинности):

;

;

.

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

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

Не всякие логические рассуждения могут быть проведены средствами логики высказываний. Иногда нам требуется исследовать саму структуру предложений. Это можно сделать с помощью логики предикатов. Предложение “x белого цвета” не является высказыванием, но если вместо x подставить конкретное значение, например “ снег” или “жираф”, получим высказывание. Это предложение описывает свойство x “быть белого цвета” и является одноместным предикатом. Если рассмотрим предложение “x больше ростом, чем y”, то подставляя конкретные пары значений , будем получать высказывания, принимающие значение “истина” или “ложь”. Это предложение описывает свойство пары объектов и является двухместным предикатом.

В общем случае n-местным предикатом называется функция, аргументы которой являются элементами произвольного множества M, а значения принадлежат множеству <И, Л>, т.е. <И, Л>. Элементы множества M называются предметными переменными. Количество предметных переменных есть порядок (местность) предиката. Множество значений предметных переменных, на котором предикат принимает значение И, называется множеством истинности предиката. Например, определим на множестве M=N одноместный предикат – “x делится на 2”. Его множеством истинности является множество целых положительных чисел. На множестве M=R зададим двухместный предикат – “x меньше y”. Его множество истинности можно изобразить на плоскости как множество точек, лежащих выше прямой .

Пусть два предиката P и Q определены на одном и том же множестве M. Так как предикаты могут принимать только два значения (истина или ложь), то к ним можно применить операции логики высказываний, образуя новые предикаты, при этом порядок (местность) предиката не меняется: . В качестве упражнения дайте определение этим предикатам самостоятельно.

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

Рассмотрим эти операции вначале для одноместных предикатов.

Пусть – одноместный предикат, определенный на множестве M. Тогда под выражением будем понимать высказывание, которое принимает значение истина тогда и только тогда, когда истинно для каждого элемента x множества M. Это высказывание уже не зависит от x. Переменную x в предикате называют свободной, а в высказывании – связанной квантором всеобщности.

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

Операции квантификации являются обобщением операций конъюнкции и дизъюнкции на случай бесконечного множества M предметной переменной. Действительно, пусть множество M конечно: . Тогда И означает, что для всех элементов множества M выполняется свойство P, т.е.

Равенство Л означает, что найдется хотя бы один элемент такой, что Л, т.е.

Операция квантификации понижает порядок (местность) предиката, а одноместный предикат превращает в высказывание ( 0-местный предикат).

Применение одной кванторной операции к двухместному предикату превращает его в одноместный предикат: – здесь связана переменная y, а переменная x осталась свободной; а двух – в высказывание –“для любого x найдется y такой, что ” (если предикат означает “”). Если на двухместный предикат навешивают два одноименных квантора, то их можно менять местами, если же кванторы разноименные, то этого делать нельзя.

Пример. Пусть предикат выражает свойство “покупателю x подходит по размеру пара ботинок y”. Тогда высказывание может служить рекламой обувного магазина: “каждому покупателю мы подберем подходящую по размеру пару ботинок”, а высказывание – нет (“у нас есть пара ботинок, подходящая по размеру любому покупателю”).

2.3. Формулы логики предикатов

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

Пример. Пусть задана формула . Рассмотрим две ее интерпретации:

I1: M=N, ;

I2: M=Z, .

В первом случае F=И – это утверждение о существовании наименьшего натурального числа. Во втором случае F=Л.

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

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

2.4. Равносильные преобразования формул

Две формулы логики предикатов называются равносильными, если они принимают одинаковые истинностные значения при любых значениях переменной в любой интерпретации. Все равносильности логики высказываний (табл. 1.5) справедливы в логике предикатов. Кроме этого, в логике предикатов есть равносильности, связанные с преобразованиями формул, содержащих кванторы (табл. 2.1).

Источник

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

Как организовать Wi Fi на 41 км через холмистую местность
Здравствуйте товарищи. Такой непростой (для меня) вопрос. Расстояние 41 км, прямой видимости нет.

Выполнимость формулы(ДНФ)
Здравствуйте, уважаемые! Дана формула: A->B A+BC Мое решение, использую ДНФ: Вот только я.

С ДНФ и КНФ установить выполнимость формул
С ДНФ и КНФ установить выполнимость формул

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

Можете почитать здесь здесь. Похожее обсуждение было здесь. Это касается местности.
Если лень переходить по ссылкам, то если в предикате m кванторов, а переменных в выражении после квантора n, то местность предиката равна n-m.

Что касается выполнимости. Предикат выполним, если выполнима формула, с учётом предикатов. Формула выполнима, если она истинна хотя бы на одной интерпретации. Формула истинна на интерпретации, если истинна на всех наборах значений.

Интерпретации:
x>0, y>0;
x>0, y=0;
x>0, y 0;
x=0, y=0;
x=0, y 0;
x 0

С использованием ДНФ и КНФ установить выполнимость формулы.
Что значит выполнимость формулы? Упростить? или Что с ней делать?

Выяснить, все ли его цифры разные
Дано трехзначное натуральное число. Выяснить, все ли его цифры разные

Дано 4-х значное число. Выяснить, различны ли его цифры
Помогите пожалуйста. Дано 4-х значное число.Выяснить различны ли его цифры. Если можно подробно.

Источник

MT1102: Линейная алгебра (введение в математику)

При изучении высказываний мы отмечали, что утверждение с переменными не является высказыванием. Можно, например, рассмотреть предложение %%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%%. Одноместный предикат будем называть унарным или предикатом от одной переменной.

Примеры

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

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

%%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%% называется областью определения предиката.

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

Пример

На множестве %%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%% и являющийся ложным для тех и только тех %%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_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%% переменных).

Источник

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

Пусть М — произвольное непустое множество, и n Î N È <0>. М n — n-я декартова степень множества М.

Определение 8.2. Любое отображение Р: М n ® W называется n-местным предикатом на множестве М. n-местный предикат, содержащий переменные x₁, …, x_n обозначим через Р(x₁, …, x_n). Переменные x₁, …, x_n принимают значения из множества М. Если a — значение предиката Р(x₁, …, x_n) при x₁ = a₁, …, x_n = a_n, то будем писать P(a₁, …, a_n) = a.

Пример 8.3.M = N, n = 1. Тогда предложение «Х есть простое число» есть 1-местный предикат на множестве N. Обозначим это предложение через Р(х). Тогда Р: N ® W, где

Замечание 8.5. Любой n-местный предикат Р(x₁, …, x_n) на множестве М при фиксации переменных x₁, …, x_n превращается в высказывание.

Замечание 8.6. Под 0-местным предикатом понимается произвольное высказывание. При этом нуль-местных предикатов ровно два — истинный и ложный. Множество М 0 — одноэлементно, (содержит единственную последовательность элементов множества М длины нуль). Поэтому М 0 ® Ω отождествляются с элементами множества Ω (нуль-местных предикатов ровно два — истинный и ложный).

Замечание 8.7. По n-местному предикату Р(x₁, …, x_n) естественным образом определяется n-арное отношение R на множестве М: » (a₁, …, a_n) Î М n положим (a₁, …, a_n) Î R Û Р(a₁, …, a_n) º и. Тем самым устанавливается взаимооднозначное соответствие между множествами n-арных отношений и всех n-местных предикатов на множестве М. В связи с этим множество М с системой определенных на нем предикатов s называется, как и множество М с системой отношений, моделью сигнатуры s и обозначается М(s).

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

1. Пусть Р(x₁, …, x_n) произвольный предикат на М. Заменив в нем х₁ некоторым элементом а Î М, мы получим новый, (n – 1)-местный предикат на М, который будем обозначать в виде Р(а, x₂, …, x_n) или каким-либо иным образом, например, q(x₂, …, x_n). Аналогично, новые предикаты можно получать из предиката Р(x₁, …, x_n), заменяя в нем какую-либо другую переменную или даже несколько переменных элементами из М. Ясно, что заменив к переменных, получим (n – k)-местный предикат.

Пример 8.8. Рассмотрим 3-местный предикат

на множестве N. Заменив х на 2, получим новый 2-местный предикат P(2, y, z)

который можно записать, например, в виде «Число z на две единицы больше числа y».

2. Пусть Р(x₁, …, x_n) — произвольный предикат на множестве М и n ³ 2. Заменим х₁ на х₂ (или, как говорят, отождествим переменные х₁, х₂). В результате получим (n – 1)-местный предикат Р(x₁, х₂, х₃, …, x_n). Аналогично можно получить из предиката Р(x₁, …, x_n) новые предикаты, отождествляя какие-либо другие переменные.

Пример 8.9.Отождествляя переменные х и у в предикате из примера 8.7, получим 2-местный предикат

на множестве N. Этот новый предикат можно записать, например, в виде предложения «Число z в два раза больше числа у».

3. Учитывая связь понятия предиката с понятием высказывания, можно определить логические операции для предикатов. Если Р — n-местный предикат, а q — m-местный предикат, и переменные, входящие в Р, не входят в q, то через P Ú q обозначим (m + n)-местный предикат, значение которого при конкретных значениях переменных равно дизъюнкции соответствующих значений предикатов P и q. Аналогично определяются конъюнкция и импликация предикатов, а также отрицания предиката.

4. Кроме операций &, Ú, ®,` для предикатов на множестве можно определить еще логические операции навешивания кванторов всеобщности и существования. Рассмотрим n-местный предикат Р(x₁, …, x_n) на множестве М.

· Добавив к нему фразу «Для всех х₁» или «Для всякого х₁», получим новое предложение, которое обозначим в виде

Из построения этого предложения видно, что при замене в нем переменных х₂, …, х_n соответственно элементами а₂, …, а_n получится высказывание

которое истинно в том и только том случае, когда высказывание Р(а, а₂, …, а_n) истинно при любом а Î М. Таким образом, (8.1) является (n – 1)-местным предикатом. При этом говорят, что предикат (8.1) получен из предиката Р навешиванием квантора всеобщности по переменной х₁. Отметим, что квантор всеобщности » можно навешивать и по другим переменным.

· Добавляя перед предикатом Р(x₁, …, x_n) фразу «Существует х₁, такое что», получим новое предложение, которое обозначается в виде

Пример 8.10. Пусть Р(х, у) есть предикат на N

зависит только от переменной х. При х = 1 оно принимает значение «и», так как 1 делит любое натуральное число. При любом другом значении х из N оно принимает значение «л», т.е.

«у

зависит только от переменной у и принимает значение «л» при любом значении у, поскольку в N не существует чисел, делящихся на все натуральные числа, т.е. «х P(x, y) = л.

Пример 8.11.Р(х, у) — то же самое, что и в примере 8.10, тогда

Источник