Файл: Учебника по курсу Основы дискретной математики и логики.pdf

Рассмотрим примеры.
Предикат «Для любого х[икс] сумма х[икс] и y[игрек] равна 25» является выполнимым предикатом при y = 25 − х[игрек равном 25 минус икс]. Данный предикат представлен формулой (5.14). Множество истинности предиката (5.14) описывается формулой (5.15). Одновременно этот же предикат является опровержимым при y[игрек], не равном 25 − х[25 минус икс]. Данная ситуация описывается формулой (5.16).
Предикат называется тождественно истинным, если при любой подстановке вместо переменных конкретных элементов из соответствующих множеств он превращается в истинное высказывание.
Предикат (5.17), заданный на множестве действительных чисел, является тождественно истинным, так как высказывание «Для любого числа
х[икс] найдется число y[игрек] такое, что сумма х[икс] и y[игрек] будет равна
25» истинно.
Предикат называется тождественно ложным, если при любой подстановке вместо переменных конкретных элементов из соответствующих множеств он превращается в ложное высказывание.
Предикат (5.18), заданный на множестве действительных чисел, является тождественно ложным, так как высказывание «Существует число

y[игрек] такое, что какое бы число х[икс]мы ни взяли, сумма х[икс] и
y[игрек] будет равна 25» ложно.
Слайд 160
На слайде приведены примеры предикатов, заданных на конечном множестве М[эм], и перечислены их множества истинности. Для пунктов «а – г» запись множества истинности очевидна.
Разберем пункт «д». Дана импликация двух предикатов, импликация принимает ложное значение на наборе (1,0) [один ноль], поэтому из множества М[эм] исключаем четные числа, не являющиеся квадратами натуральных чисел, это 2, 6, 8, 10, 12, 14, 18, 20. Остальные числа из М[эм] образуют множество истинности предиката.

В пункте «е», рассуждая аналогично, исключаем нечетные числа, являющиеся квадратами натуральных чисел. Это 1 и 9. Остальные числа входят во множество истинности предиката.
В пункте «ж» дана конъюнкция двух предикатов. Число, которое одновременно больше пятнадцати и является делителем числа шестнадцать, есть число шестнадцать.
Слайд 161
Два предиката над одними и теми же множествами называются эквивалентными, если один из них обращается в истинное высказывание на тех и только тех наборах значений переменных, на которых в истинное высказывание обращается другой предикат. Такие предикаты называются также равносильными. На слайде данное определение записано с помощью математических символов.
Рассмотрим примеры. Для заданных пар предикатов выясним, будут ли они равносильны над множествами натуральных, целых, рациональных и действительных чисел.
Пункт «а». Предикаты P[пэ]и Q[кю]определяются алгебраическими уравнениями. Корнями первого уравнения являются числа, заданные формулой (5.19); корни второго уравнения представлены формулой (5.20).
Сравнивая множества корней уравнений, мы видим, что данные предикаты равносильны над множествами натуральных и целых чисел и не являются равносильными над множествами рациональных и действительных чисел.
Слайд 162
Продолжим рассмотрение примеров.
Пункт «б». Равенство, определяющее предикат P[пэ], справедливо на множествах натуральных, целых и рациональных чисел. На множестве действительных чисел оно не является верным, так как знаменатель дроби не определен при значении x[икс], равном арифметическому квадратному корню из трех. Неравенство, определяющее предикат Q[кю], справедливо для всех действительных чисел. Отсюда делаем вывод, что заданные предикаты

равносильны над множествами натуральных, целых и рациональных чисел и не являются равносильными над множеством действительных чисел.
Пункт «в». Равенство, определяющее предикат P[пэ], как и неравенство, определяющее предикат Q[кю], справедливо только при x =
0[икс равном нулю]. Поэтому данные предикаты равносильны над всеми четырьмя множествами.
Пункт «г». Поскольку арифметический квадратный корень определен только для неотрицательных чисел, данные предикаты равносильны лишь над множеством натуральных чисел.
Пункт «д». Заданные предикаты равносильны над множеством натуральных чисел, так как в этом случае модуль числа совпадает с самим числом. Над другими тремя множествами равносильности нет, поскольку совпадение абсолютных величин двух чисел допускает их противоположность.
Пункт «е». Данные предикаты не являются равносильными ни над одним из четырех множеств, так как, например, пара (1; 3)[один три] удовлетворяет первому неравенству и не удовлетворяет второму.
Слайд 163
Продолжим рассматривать ту же задачу для новых пар предикатов.
Пункт «ж». Ввиду того что логарифм определен только для положительных чисел, данные предикаты равносильны лишь над множеством натуральных чисел.
Пункт «з». В силу свойства показательной функции уравнения определяющие предикаты являются равносильными на множестве действительных чисел. Поэтому рассматриваемые предикаты равносильны над всеми четырьмя множествами.
Пункт «и». Равенство, определяющее первый предикат, справедливо только для положительных чисел, а равенство, задающее второй предикат, верно для всех действительных чисел. Следовательно, данные предикаты равносильны только над множеством натуральных чисел.

Пункт «к». Равенство, определяющее предикат P[пэ], справедливо на множестве положительных действительных чисел, а равенство, задающее предикат Q[кю], верно для всех неотрицательных действительных чисел.
Поэтому рассматриваемые предикаты равносильны лишь над множеством натуральных чисел.
Пункт «л». Формулы (5.21) и (5.22) представляют множества корней уравнений, определяющих соответственно первый и второй предикаты.
Сравнивая данные множества, мы делаем вывод о том, что данные предикаты равносильны над множествами натуральных и целых чисел и не являются равносильными над множествами рациональных и действительных чисел.
Слайд 164
Пусть P[пэ] и Q[кю]– n[эн]-местные предикаты, заданные над одними и теми же множествами. Предикат Q[кю]называется следствием предиката
P[пэ], если он обращается в истинное высказывание на всех тех наборах значений переменных из соответствующих множеств, на которых в истинное высказывание обращается предикат P[пэ]. На слайде данное определение записано с помощью математических символов.
Рассмотрим следующий пример. Для заданных пар предикатов, рассматриваемых на множестве действительных чисел, выясним, будет ли какой-либо из предикатов являться следствием другого.
Пункт
«а».
Неравенству, определяющему предикат
P[пэ], удовлетворяют все числа из интервала (−3; 3)[от минус трех до трех].
Корнями уравнения, задающего предикат Q[кю], являются числа 1 и 2. Таким образом, множество истинности предиката Q[кю] является строгим подмножеством множества истинности предиката P[пэ]. Отсюда вытекает, что P[пэ]является следствием Q[кю], а Q[кю]не является следствием P[пэ]
Слайд 165
Продолжим рассмотрение нашей задачи.
Пункт «б». Уравнение, определяющее первый предикат, имеет корни
±2[плюс минус два]. Уравнение, задающее второй предикат, не имеет

действительных корней. Поэтому первый предикат является следствием второго, а второй предикат не является следствием первого. Стоит отметить, что из тождественно ложного предиката следует любой предикат.
Пункт
«в».
Неравенству, определяющему предикат
P[пэ], удовлетворяют все числа, большие единицы. Корнями уравнения, задающего предикат Q[кю], являются числа 2 и 5. Отсюда вытекает, что P[пэ]является следствием Q[кю], а Q[кю]не является следствием P[пэ]
Пункт «г». Уравнение, определяющее первый предикат, так же, как и уравнение, задающее второй предикат, не имеет действительных корней.
Поэтому в данном случае каждый из предикатов является следствием другого.
Пункт
«д».
Неравенству, определяющему предикат
P[пэ], удовлетворяют все числа, которые меньше минус шести или больше единицы. Уравнению, задающему предикат Q[кю], удовлетворяют все действительные числа. Отсюда вытекает, что Q[кю]является следствием
P[пэ], а P[пэ]не является следствием Q[кю]. Отметим, что тождественно истинный предикат является следствием любого предиката.
Слайд 166
Продолжим рассматривать ту же задачу для новых пар предикатов.
Пункт
«е».
Неравенству, определяющему предикат
P[пэ], удовлетворяет только число ноль. Оно же является единственным корнем уравнения, задающего предикат Q[кю]. Отсюда вытекает, что каждый из предикатов является следствием другого.
Пункт «ж». Число десять обращает первый предикат в истинное высказывание, а второй – в ложное. Число минус десять, наоборот, обращает первый предикат в ложное высказывание, а второй – в истинное. Таким образом, ни один из предикатов не является следствием другого.
Пункт
«з».
Неравенству, определяющему предикат
P[пэ], удовлетворяют все положительные числа, не превосходящие десяти.
Неравенству, задающему предикат Q[кю], удовлетворяют все числа отрезка

от одного до десяти. Отсюда вытекает, что P[пэ]является следствием Q[кю], а Q[кю]не является следствием P[пэ]
Слайд 167
Продолжим рассмотрение нашей задачи.
Пункт «и». Предикат P[пэ]определяется уравнением, предикат Q[кю] – неравенством. Очевидно, что множество истинности первого предиката у́же, чем множество истинности второго предиката. Поэтому можно утверждать, что второй предикатявляется следствием первого, а первый не является следствием второго.
Пункт «к». Предикаты P[пэ]и Q[кю]задаются с помощью неравенств.
Множество истинности предиката P[пэ], как и в предыдущем случае, у́же множества истинности предиката Q[кю]. Значит, Q[кю]является следствием
P[пэ], а P[пэ]не является следствием Q[кю].
Пункт «л». Корнями уравнения, определяющего первый предикат, являются числа минус два, один и три. Уравнение, задающее второй предикат, имеет корни один и три. Отсюда вытекает, что первый предикат является следствием второго, а второйне является следствием первого
Слайд 168
Понятие формулы алгебры предикатов вводится аналогично понятию формулы алгебры высказываний. Сначала задается алфавит символов, из которых будут составляться формулы. Мы будем использовать символы предметных переменных – малые буквы латинского алфавита, символы предикатных переменных – заглавные буквы латинского алфавита, символы логических операций, кванторы и вспомогательные символы – скобки и запятую.
Определение формулы алгебры предикатов дается индуктивным образом. Оно представлено на слайде.
Формулы, определенные в пунктах 1 и 2, называются атомарными, или элементарными.

Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать.
Подформулой формулы алгебры предикатов называется всякая ее часть, которая сама является формулой. Если формула образована из предикатных переменных F[эф] и G[жэ] с помощью операций дизъюнкции, конъюнкции, импликации, эквиваленции, то F[эф] и G[жэ]являются подформулами этой формулы.
Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, – открытыми.
Слайд 169
Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором выбранном множестве M[эм], то формула превратится в конкретный предикат, заданный над множеством M[эм]. При этом если исходная формула была замкнутой, то полученный конкретный предикат оказывается нульместным, т. е. будет высказыванием. Если же исходная формула была открытой, т. е. содержала свободные вхождения предметных переменных, то в результате подстановки получим предикат, зависящий от некоторых предметных переменных. Если теперь подставить вместо этих предметных переменных конкретные предметы из множества M[эм], то полученный предикат, а следовательно, и исходная формула превратятся в конкретное высказывание.
Превращение формулы логики предикатов в высказывание описанным способом, а также само полученное высказывание называется интерпретацией этой формулы на множестве M[эм]. Итак, если формула логики предикатов замкнутая, т. е. не содержит свободных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов.

Если же формула логики предикатов открытая, т. е. содержит ряд свободных переменных, то ее интерпретация состоит из двух этапов. Во- первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты. В результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле.
Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат и, значит, исходная формула превратится в конкретное высказывание, истинное или ложное.
Рассмотрим пример, формула (5.23). В первом случае формула превратится в следующее, очевидно ложное высказывание «У каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию.
Во второй случае исходная формула превратится в очевидно истинное высказывание «Для каждого натурального числа существует большее по сравнению с ним натуральное число».
Слайд 170
Формула алгебры предикатов называется выполнимой на множестве
М[эм], если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на М[эм], она обращается в выполнимый предикат.
Формула алгебры предикатов называется опровержимой на множестве
М[эм], если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на М[эм], она обращается в опровержимый предикат.
Другими словами, формула выполнима или опровержима на M[эм], если существует истинная или ложная ее интерпретация на M[эм].
Приведем примеры выполнимых и опровержимых формул.

Рассмотрим формулу (5.24). Она является выполнимой на множестве действительных чисел. Действительно, пусть P(x, y)[пэ от икс игрек] –это предикат «x > y»[икс больше игрек]. При такой интерпретации формула превращается в истинное высказывание «Для любого действительного числа
х[икс] найдется такое действительное число у[игрек], что х > у[икс больше игрек]».
В то же время формула (5.24) является опровержимой на множестве натуральных чисел. В самом деле, если P(x, y)[пэ от икс игрек] – это предикат «x > y»[икс больше игрек], то формула превращается в ложное высказывание «Для любого натурального числа х[икс] найдется такое натуральное число у[игрек], что х > у[икс больше игрек]».
Обратимся к формуле (5.25). Она является выполнимой на множестве
М[эм], состоящем из чисел 12, 24, 36. Действительно, пусть предикат P(x)[пэ от икс]выражает свойство числа х[икс]делиться на два, предикат Q(x)[кю от икс] – свойство делимости на три, а предикат R(x)[эр от икс] – свойство делимости на двенадцать. При такой интерпретации формула превращается в истинное высказывание «Всякое число из множества М[эм], делящееся на два и на три, делится и на двенадцать».
В то же время формула (5.25) является опровержимой на множестве натуральных чисел. При подстановке в нее рассмотренных выше предикатов данная формула превращается в ложное высказывание «Всякое натуральное число, делящееся на два и на три, делится и на двенадцать». В самом деле, число восемнадцать, например, делится на два и на три, но при этом оно не делится на двенадцать.
Слайд 171
Формула алгебры предикатов называется тождественно истинной на множестве М[эм], если при всякой подстановке вместо предикатных переменных любых предикатов, заданных на М[эм], она превращается в тождественно истинный предикат.