Эскорт-услуги в Москве от Queens Palace


GOUSPO студенческий портал!

форум, учебники, лекции, и многое другое

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

Тема 6. Логика предикатов

План:

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

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

3. Кванторы

4. Понятие о многоместных предикатах

Цель. Формирование представлений о предикате как предложение с переменной, канторах, множества определения и множества истинности предиката.

Теоретически сведения

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

1.1. Общие понятия

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

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

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

  1. Любое неравенство является предикатами.

Например:  X>10; 3х4-5x < 30 – неравенства, при подстановке в которое вместо X  конкретных значений (чисел), будут получатся либо истинные, либо ложные высказывания.

  1. Любое уравнения является предикатами.
  2. Он получил специальность тракториста. Это предикат, вместо слова он можно подставить конкретную фамилию и это предложение превратится в высказывание.

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

Предикаты обозначаются:  A(x),  D(x; y) и др.

Например:

1. A(x)=Число x делятся на 2

2. B(x;y)=Числа x и y есть решения уравнения x+y=10

3. Выражение z(z+1) делится на 2.

4. Любое натуральное число четное.

Для каждого предиката можно указать область определения и множество истинности.

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

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

Если некоторое множество X – область определения предиката, а множество T множество его истинности,  то, очевидно, что множество T подмножество множества X, ТÌХ

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

1.2 Алфавит исчисления предикатов.

1. A, B, C, D …Z, Y, X – обозначение предикатов (с индексами или без таковых)

x, y, z, …  обозначение переменных (с индексами или без таковых)

2. x0 , y0 , z0 – постоянные значения, константы

3. Ç,  È,  ù ,  ®,  «, Î,  Ï  и другие  символы логических операций и теории переносятся без изменения в исчисление предикатов.

4. квантор общности и $ квантор существования

5. Могут использовать иные, заранее оговоренные или интуитивно понятные символы.

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

Каждому предикату присваивается имя.

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

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

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

Примеры высказывательных форм: 2k, m + n, , m>n+1 и др.

Рассмотрим двуместную высказывательную форму: x ³ y+2. Пусть  x определено на множестве Mx ={3;5}, y – на множестве My={1;5;8}. Этой форме соответствуют два предиката. Один    P1 задан на множестве, образованным декартовым произведением X1= Mx x My

Другой P2 задан на множестве, образованным декартовым произведением X2= My x Mx

Это значит, что двуместной высказывательной форме соответствует два предиката. Чтобы установить взаимно-однозначное соответствие между ними, на установит линейный порядок с помощи отношения предшествует.  Порядок может определять алфавитом и (или) индексами при переменных, располагая их в порядке возрастания.

Принято называть:

1. Одноместный предикат – свойством (предикат свойство).

2. Двуместный, трехместный, … , n-местный предикат – отношением (предикат – отношение)

3. Нульместный предикат – высказыванием.

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

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

Пусть даны два предиката, определенные на одном множестве. Высказывательные формы Q и G назовем равносильными, если при любом наборе значений переменных, входящих в них, высказывательные формы принимают одинаковые значения истин­ности: Q Þ G.

Очевидно, что если Q Þ G, а G Þ Q, то QÞG Тогда T(Q) = T(G), т.е. множества истинности равносильных предикатов также совпадают.

Примеры  равносильности высказывательных форм, заданных на множестве R.

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

Отношение равносильности высказывательных форм  рефлексивно и симметрично.

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

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

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

Отношения следования и равносильности для высказывательных форм зависят от того множества, на котором оно рассматривается.

Задание 6-1.Указать область определения и множество значений предикатов:

1. х+1=10

2. Космическое тело  x – спутник Солнца.

3. Если число x – делится на 4, то оно делится на 2.

4. Не верно, что елки растут в саду.

5. Некоторые уравнения не имеют решения.

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

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

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

Пусть даны предикаты,  заданные на множестве D, причем предикат

A(X) имеет множество истинности P

В (Х) имеет множество истинности Q.

1. Отрицание. К (Х) = ù А (Х). Множество истинности Т= ù P=D\ P – дополнение множества истинности предиката А (Х) до множества D.

2. Конъюнкция предикатов. К (Х)=А (Х) Ç В (Х). Множество истинности Т=РÇQ

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

3. Дизъюнкция предикатов. S(Х)=А (Х) È В (Х). Множество истинности Т=РÈQ

Дизъюнкция предикатов, например, используется при решении системам уравнений или неравенств, решение которых есть дизъюнкция. множеств истинности (множеств решений) каждого уравнения или неравенства.

4. Импликация предикатов. W(X)= А (Х) ®В (Х). Множество истинности  установим на основе алгебры логики:  Т=Р®Q = ùPÈQ = D \ P È Q.  Множество истинности  импликация. двух предикатов есть объединение дополнения множества истинности первого предиката с множеством истинности второго предиката.

Импликация предикатов, например, используется при доказательстве теорем, когда устанавливается множество истинности  заключение теоремы (установление класса объектов, для колотых положение доказанное в теореме имеет место)

5. Эквиваленция предикатов. N(X) = А (Х) «В (Х). Множество истинности  установим на основе алгебры логики:

Т=Р«Q =(Р®Q) Ç (Q ®P) = (D \ P È Q) Ç(D \ Q È P)=(ù PÈ Q) Ç(ù QÈ P)=

== =D

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

6. Логическое следование. Высказывательная форма М2(Х) логически следует из высказывательной формы М1(Х), если импликация  М1(Х) ® М2(Х) принимает истинное значении при любых наборах значений переменных, входящих в нее. Обозначается  М1(Х) Þ М2(Х). Очевидно, что множество истинности  логического следования совпадает с множеством истинности высказывательной формы М1(Х). Причем: Т(М1)ÌТ(М2)

В ряде случаев возможно одновременное логическое следование:

М1(Х) Þ М2(Х)   и   М2(Х) Þ М1(Х)

При этом возможна запись М1(Х) Û М2(Х), которая  говорит о равносильности соответствующих высказывательных форм и предикатов.

3. Кванторы.

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

Пусть  на множестве Х простых чисел задан предикат А(х)=Простое число x нечетное

Поставим перед этим предикатом слово всякое, тем самым получим высказывание Всякое число  x нечетное  - ложное, т.к. число 2 относится к четным числам

Поставим перед этим предикатом слово существует, тем самым получим высказывание Существует число  x нечетное  - истинное, т.к., например  число 5 – нечетное число.

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

Различают два вида кванторов:

1. Квантор общности соответствует словам: любой, всякий, каждый и иными словам такого смысла. Обозначается символом .

2. Квантор существования - соответствует словам:  существует, найдется, хотя бы один и иными словам такого смысла. Обозначается символом $.

Предикаты с кванторами можно записать в виде:

(xÎX)A(x)                 ($xÎX)A(x)

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

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

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

Кванторы и $ являются дополнениями и аналогами соответственно логических операций конъюнкции и дизъюнкции. При этом верна формула:

$x A(x)=, которая выражает двойственность

Приведем пример. A(X)=Число x делится на 5

Тогда: $ x A(x)=Найдется число x, которое делится на 5 – верно.

=Неверно, что не найдется число x, которое делится на 5- верно.

Рассмотренная формула позволяет строить отрицания высказываний с кванторами.

Между кванторами и логическими операциями существу­ет тесная связь.

Пусть предикат Р(х) определен на конечном мно­жестве D= 1 а2 , ап}.

Высказывание $aÎD (P(x)) - истинным только в том случае, если истинны одновременно все высказывания Р(а1), Р(а2), , Р(а„), можно сказать, что должна быть истинной конъюнкция этих высказываний.

Высказывание $aÎDР(х) – истинно в том случае, если  истинно хотя бы одно из высказываний Р(а1), Р(а2), , Р(а„), можно сказать, что должна быть истинной дизъюнкция  этих высказываний.

Задание 6-2. Имеются два утверждения:

1. Для лечения любого известного компью­терного вируса имеются программы.

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

Записать их с помощью формул логики предикатов.

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

А(х) - известен компьютерный вирус х;

В(х) - для лечения вируса х существует программа.

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

ù В(х) - против вируса х нет программы;

х(А(х)) любой вирус известен;

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

x(A(x) ®B(x))- если вирус давно известен, то имеется программа для его лечения;

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

Если  оба заданные утверждения рассматривать как их конъюнкцию, то формально такое предложение может выглядеть так:

(x(A(x) ®B(x)) Ç ($х(ù А(х) Ç ù В(х))

Продолжить составление других формул.

Задание 6-3. Образовать из  предиката  В(х)=Число x кратно 5 новые предикаты с кванторами и установить их истинность

Задание 6-4. Установить истинность высказываний и записать их в виде  (xÎX)A(x) или   ($xÎX)A(x). Установить истинность полученных высказываний.

1. Любое натуральное число – четное.

2. Существуют действительные числа большие 1000.

3. Не существует рационального числа, квадрат которого равен 2.

4. Квадратное уравнение имеет два корня.

Задание 6-5. На множестве N  заданы предикаты  Р(Х)=Число x  четное  и  Q(x)=Число x кратно 4 из которых составлены высказывание с помощью кванторов. Перевести их на обычный язык.

1. (xÎN)P(x)             3. ($xÎN) ù Q(x).                     6. (xÎN)(P(x) È Q(x)).

2. ($xÎN)Q(x).                        4. (xÎN)(P(x)Ç Q(x)).           7. ($xÎN)(P(x) È Q(x)).

3. (xÎN)ù P(x).          5. ($xÎN)(P(x)Ç Q(x)).

Задание 6-6. Построить отрицания  высказываний (предикатов с кванторами) используя формулу:  $x A(x)=. Проверить справедливость  формулы x A(x)=.

1. Число x  нечетное.             3. Некоторые прямоугольники квадраты

2. Число x кратно 10              4. Существую правильные пирамиды.

Задание 6-7. Приведите общую словесную формулировку правил построения отрицания высказываний с кванторами на основе выполнения задания 6-5.

4. Понятие о многоместных предикатах

Рассмотри предложение:

Студент x  сдал экзамен на оценку y – это двуместный предикат.

Для его описания надо задать множеств X  фамилии студентов и Y – перечень всех возможных оценок. Область задания этого предиката будет представлять множество пар декартового произведения множеств X и Y. Например: (Иванов; 5), (Сидоров; 3) и др.

Запишем трехместный предикат:

Студент x  сдал экзамен на оценку y преподавателю z Область задания этого предиката будет представлять множество троек декартового произведения множеств X , Y, Z..

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

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

В разделе математики Функции многих переменных находит отражение теория многоместных предикатом, что весьма далеко выходит за пределы данного курса математики.

Задание 6-7. На множестве Х={-3,-2,-1,0,1,2,3,4} заданы предикаты:

А(Х)=Число x кратно 3 и В(Х)=x-1>0

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

1. ù А (Х)                      3. А (Х) Ç В (Х).                  5. А (Х) ®В (Х).

2. ù В (Х)                      4. А (Х) È В (Х).                  6. А (Х) «В (Х).

Для номеров 5и 6 построить словесную формулировку со словами необходимо и достаточно.

Задание 6-8. На множестве Х={1,2,3,4,5,6} задан предикат А(Х)=Если число x кратно 4, то оно четное

1. Укажите вид предиката и найдите  для него множество истинности

2. Привести его словесную формулировку со словами необходимо и достаточно.

3. Дать графическую иллюстрацию

Задание 6-9.Даны предикаты А(Х)=Число х – четное и В(Х)=Число х – делится на 6

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

Контрольные вопросы

1. Привести определение предиката.

2. Указать условия применимости кванторов.

3. Привести правило организации отрицания предиката.

4. Множество истинности составных предикатов.

5. Привести пример 0-местныного предиката.

6. Привести примеры двух, трех, четырех местных предикатов.

Требования к знаниям, умениям и навыкам

Студенты должны знать определение предиката, уметь находить область определения и множество истинности предиката. Знать правила построения предикатов.  Иметь представление о кванторных. Уметь записывать математические предложения с помощью кванторов.