NsmuBase

Учебные материалы и ответы на тесты

Математическая логика: Лекция “Теория предикатов”

Математическая логика: Лекция "Теория предикатов"

Математическая логика и теория алгоритмов. Лекция №2. Теория предикатов.

1.     Теория предикатов

1.1.  Предикаты

Рассмотрим предложение «n – четное число», где n – натуральная переменная. Это предложение не является высказыванием, т.к. нельзя сказать, истинно оно или ложно. Но если вместо n подставить какое-либо допустимое значение (некоторое натуральное число), то получается высказывание. Например, при n=3получится ложное высказывание, а при n=6 – истинное. Предложения такого вида называются предикатами. Определение. Предложения с переменными, дающие высказывания в результате замены свободных переменных их допустимыми значениями называются предикатами.

Пример: Пусть x, y, z – целочисленные переменные. 1)     x > 10; 2) x + y = 7; 3) x2 + y2 = z2 – предикаты. По числу свободных переменных, входящих в предикат, различают предикаты одноместные,двухместные, трехместные и т.д. (соответствуют примеры 1)-3)). Высказывания будем считать 0-местными предикатами. Предикаты можно задавать различными способами. В алгебре предикаты задаются с помощью уравнений, неравенств, систем уравнений и неравенств и т.д. Например: 1)     x+1=0, xR – одноместный предикат. 2)    x+y=5, 2x-y>3, x,yR – двухместные предикаты. Обозначение предикатов:A(x), B(x, y), C(x, y, z).

Определение. Истинностное значение предикатана том или ином наборе входящих в его состав свободных переменных – это истинностное значение высказывания, которое получается в результате замены свободных переменных соответствующими значениями из рассматриваемого набора. Пример: истинностное значение предиката A(x): x>2, xR, дляx=5 – истина, дляx=1 – ложь. Истинностное значение предиката B(x, y): x2+y2=25, x, yZ, дляx=5, y=0 – истина, дляx=y=1 – ложь.

1.2.  Область истинности предиката Пусть A(x)– одноместный предикат на множестве M (xM).

Определение. Областью истинности одноместного предиката называется совокупность всех значений свободной переменной x, при которых предикат обращается в истинное высказывание. Будем обозначать это множество T(A(x)).Пример 1: Область истинности одноместного предиката A(x): x20, xR –все действительные числа (это неравенство будет верно при подстановке любого действительного числа), т.е. T(A(x))=R. Пример 2: Область истинности предиката A(x): x-5=0, xR – число 5. T(A(x))=5. ПустьA(x, y) – двухместный предикат (xM1, yM2).

Определение. Областью истинности двухместного предиката называется совокупность всех пар значений свободных переменных x и y, при которых предикат обращается в истинное высказывание. Пример 3: областью истинности двухместного предиката x-y=0, x, yR является прямая на плоскости x=y, т.е все пары действительных чисел (x, y), для которых верно x=y. Пример 4: областью истинности двухместного предиката x2+y2=1, x, yRявляется окружность на плоскости с центром в точке (0, 0), радиуса 1, т.е все пары действительных чисел (x, y), для которых соответствующие точки лежат на этой окружности. Аналогично определяется область истинности для трехместного предиката и т.д. (n-местного предиката). Для предикатов можно определить следующие понятия: —       тождественно истинный предикат (превращается в истинное высказывание при всех значениях свободных переменных), множество истинности такого предиката совпадает с множеством, на котором определен предикат; —        тождественно ложный предикат(превращается в ложное высказывание при всех значениях свободных переменных), множество истинности такого предиката пусто; —       выполнимый предикат (существует набор значений свободных переменных, при котором предикат превращается в истинное высказывание); —        опровержимый предикат (существует набор значений свободных переменных, при котором предикат превращается в ложное высказывание). Т.о. предикат из примера 1 является тождественно истинным и выполнимым, предикаты из примеров 2-4 – выполнимыми и опровержимыми.

1.3.   Логические операции (связки) над предикатами Связки, анало­гичные связкам для высказываний, соответствуют логическим операциям над предикатами. Операции над n-местными предикатами вводятся аналогично одноместным. Пусть, например, Р(х) и Q(x) – предикаты, которые определены на множестве D причем Т(Р) и T(Q) – их множе­ства истинности.

Определение. Отрицанием предиката Р(х) называется предикат, также определенный на множестве D и истинный при тех значениях переменной х, при которых Р(х) ложен,
т.е. Т() = D\T(P) .
Пример: предикат Р(х): «х – простое число» определен на множестве D=Z целых чисел, а его областью истинности являют­ся только простые числа, т. е. числа, имеющие два делителя: х и 1. Тогда предикат «х – составное (целое) число», также определен­ный на Z, будет отрицанием предиката Р(х), т.е., а его обла­стью истинности будет множество всех целых составных чисел (имеющих три и более делителей): Т() = D\T(P(x)). Рис. Множество истинности предиката
Аналогично вводятся и остальные операции.

Определение.Конъюнкция предикатов Р(х) и Q(x) есть новый преди­кат Р(х)Q(x), определенный на множестве D и истинный при тех значениях переменной х, при которых истинны одновременно оба предиката Р(х) и Q(x),
поэтому Т(Р(х)Q(x)) = T(P)T(Q). Рис. Множество истинности конъюнкции предикатов
Рассмотрим примеры. 1. Для предикатов Р(х): «х – четное число» и Q(x): «x кратно 7» конъюнкцией Р(х)Q(x) служит предикат «х – четное и кратное 7 число» или «х – число, кратное 14». 2. Решить систему неравенств  означает: решить первое неравенство, т.е. определить Т(Р1), решить второе неравен­ство – определить Т(Р2). Определить, при каких х верны и первое, и второе неравенства. В данном случае система означает конъюнкцию высказываний (х8)(х>5) <=> 5<х8, а ответ является пересечением Т(Р1) и Т(Р2). Рис. Графическое решение системы неравенств

Определение. Дизъюнкцией предикатов Р(х) и Q(x) называется пре­дикат Р(х)vQ(x), определенный на множестве D и истинный при тех значениях переменной х, при которых истинен хотя бы один из предикатов Р(х) или Q(x). Поэтому T(PvQ) = T(P)T(Q). Рис. Множество ис­тинности дизъюнкции предикатов
Например, для предикатов Р(х): «х – число, кратное 3» и Q(x): «х – число, оканчивающееся на 3», определенных на N, дизъюнк­цией Р(х)vQ(x) служит предикат: «х – число или кратное 3, или оканчивающееся цифрой 3». Так, при решении уравнений (неравенств), левая часть кото­рых есть произведение нескольких множителей, а правая – нуль, они разбиваются на совокупность уравнений (неравенств). На­пример, х2 — 8х — 20 = 0 <=> (х — 10)(х +2) = 0<=>х-10=0 (P1) или х+2=0 (Р2). Таким образом, нужно найти Т(Р1)={10}, Т(Р2)={-2} и их объединение:
Т(Р)={-2,10}.

Определение. Импликацией предиката Р(х) в Q(x) называется преди­кат Р(х)Q(x), определенный на множестве D и ложный только при тех значениях переменной х, при которой предикат Р(х) истинен, а предикат Q(x) ложен. В полном соответствии с формулой логики имеем: РQ=vQ, T(РQ) = (D\T(P))T(Q). Рис. Множество истинности импли­кации предикатов
Например, импликацией предикатов Р(х): «х – нечетное число» и Q(x): «x кратно 5», определенных на NU{0}, служит предикат Р(х) Q(x): «Если х – нечетное число, то х кратно 5».
Здесь Т(Р) = {у| (y mod 2) = 1} = {1, 3, 5, …}; T(Q) ={y|(y mod 5) = 0} = {0, 5, 10, …}. Тогда D/ Т(Р) = {у | (y mod 2) = 0}={0,2,4, …}; T(РQ) = (D\T(P))T(Q) = {v|(v mod 2) = 0 или (v mod 5) = 0} = {0, 2, 4, 5, 6, …}. Импликация верна, если число кратно двум или пяти.

Определение. Эквиваленцией предикатов Р(х) и Q(x) называется пре­дикат Р(х)Q(x), определенный на множестве D и истинный при тех значениях переменной х, при которых либо оба предиката истинны, либо оба предиката ложны. Например, эквивалентны преди­каты Р(х): «х – натуральное число, кратное 3» и Q(x): «x – нату­ральное число, сумма цифр которого делится на 3».

1.4.  Следование и эквиваленция

Предикат Q2 следу­ет из предиката Q1 если импликация Q1Q2 об­ращается в истинное высказывание при любых наборах значений переменных, входящих в нее. Для операции логического следова­ния принято обозначение Q1Q2. Пусть даны два предиката, определенные на одном множестве. Предикаты Q1 и Q2 назовем равносильными, если при любом наборе значений переменных, входящих в них, предикаты принимают одинаковые значения истин­ности: Q1Q2. Очевидно, что если Q1Q2 a Q2Q1, то Q1Q2. Тогда T(Q1) = T(Q2), т.е. множества истинности равносильных предикатов также совпадают. Например, пусть предикаты заданы на множестве действительных чисел R. (х2 – 5х + 6)/(x-2)= 0 и х2-5х+6 = 0 не являются равносильными. (3x+8)/(x2+1)= 0 и 3х+8=0 являются равносильными. В математике нарушение цепочки тождественных преобразова­ний при решении уравнений или неравенств влечет за собой по­терю имеющихся или приобретение посторонних корней, т.е. из­менение множества истинности исследуемого предиката. Эти свойства предиката используются при решении уравне­ний и неравенств, которые тоже являются некоторыми предикатами. Так, решение любого уравнения или неравенства предусматривает установление множества его истин­ности, т. е. множества истинности соответствующего ему преди­ката. В процессе поиска множества истинности производят замену одного предиката другим, равносильным данному, с целью упро­щения имеющихся предикатов.

1.5.  Кванторы

Для количественных характеристик обычно исполь­зуют понятия «все», «некоторые», «существуют» и др., кото­рые называют кванторами (от лат. quantum – сколько). Символы  и, заменяют слова «любой» и существует». Покажем действие этих кванторов в предикатах. Определение. Часть предиката, на которую распространяется действие квантора, называется областью действия этого кван­тора. Вхождение переменной в формулу может бытьсвязанным, если переменная расположена либо непосредственно после знака квантора, либо в области действий квантора, после которого стоит переменная. Все прочие вхождения – свободные. Напри­мер, в выражении хР(х) переменная х связывает свойство пре­диката и квантор общности. Грубо говоря, от этой переменной, ее конкретного вида и имени, ничего не зависит, т.е. хР(х) и уР(у) суть одно и то же. Так, можно произвольно называть индекс суммирования в рядах и переменную интегрирования в определенных интегралах. В частности, в определении множества как совокупности всех объектов, удовлетворяющих характери­стическому свойству, использовалась запись G={х|Р(х)}. Оче­видно, что в предикате со связанной переменной ее так же легко можно заменить на любую другую. При этом множество все рав­но будет совокупностью тех же элементов, удовлетворяющих свой­ству Р. Переменная, не являющаяся связанной, называется сво­бодной, если после подстановки вместо нее имени некоторых конкретных объектов предикат превращается в осмысленное пред­ложение. Например, запишем с помощью формул логики предикатов следующее утверждение: «Для лечения любого известного компью­терного вируса имеются программы. Существуют новые (неизвест­ные) компьютерные вирусы, для лечения которых программы еще не разработаны». Введем обозначения элементарных формул: А(х) – известен компьютерный вирус х; В(х) – для лечения вируса х существует программа. Тогда с помощью логических связок и кванторов получим фор­мулы: В(х) – против вируса х нет программы; x(A(x)) – любой вирус известен; х((х)) – существуют новые (неизвестные) вирусы; х(А(х) В(х)) – если вирус давно известен, то имеется программа для его лечения; х((х)(х)) – существуют (появились) новые вирусы, для лечения которых программы еще не разработаны. Тогда формализованное исходное утверждение примет вид (х(А(х) В(х)))  (х((х)(х))). В эту формулу входит лишь связанная переменная х, а, напри­мер, в формуле А(х1, х2)В(х1) первое включение перемен­ной х1 свободное, а второе – связанное. Отношения следования и равносильности между предикатами связаны с тождественно-истинными импли­кацией и эквиваленцией, следовательно, их можно записать с по­мощью квантора общности: Q1Q2тождественно x(Q1Q2); Q1Q2 тождественно x(Q1Q2). Например, запись х2-5х=0  х(х-5)=0 является не форму­лой, а истинным высказыванием о равносильности двух формул, представленных в виде уравнений. Поэтому логическое следование можно определить через имп­ликацию, а равносильность через эквиваленцию. При «навешивании» кванторов на двухместный предикат Q(x, у) можно получить одну из восьми комбинаций: 1) xy(Q(x, у)) – «для любого х и любого у Q(x, у)»; 2) yx(Q(x, у)) – «для любого у и любого х Q(x, у)»; 3) xy(Q(x, у)) – «существует х и существует у, такие, что Q(x, у)»; 4) yx(Q(x, у)) – «существует у и существует х, такие, что Q(x, у)»; 5) xy(Q(x, у)) – «существует х, такой, что для любого у Q(x, у)»; 6) xy(Q(x, у)) – «для всякого х существует у, такой, что Q(x, у)»; 7) yx(Q(x, у)) – «существует у, такой, что для любого х Q(x, у»; 8) yx(Q(x, у)) – «для всякого у существует х, такой, что Q(x, у)». Очевидно, что первое и второе высказывания, а также третье и четвертое тождественны между собой, их значения истинности совпадают. Между остальными полученными высказываниями нельзя установить тождественности: если истинно высказывание 5, то истинным будет и высказывание 8, причем обратное неверно. Аналогично, если истинно высказывание 7, то истинно и выска­зывание 6, но не наоборот. То есть, если кванторы одноименны (1–4), то их порядок не играет роли и полученные высказывания эквивалентны. Если кванторы разноименные (5 – 8), то их поря­док в полученном высказывании принципиально важен. Например, для двухместного предиката «Город х находится в стране у» высказывание ухР(х, у) имеет вид 0-местного пре­диката и читается «В каждой стране у есть некоторый город х». Оно будет истинным, в то время как высказывание хуР(х, у) чита­ется «Существует город х, находящийся во всех странах у» будет ложным.

Математическая логика: Лекция "Теория предикатов"

Next Post

Previous Post

© 2020 NsmuBase

Проект winterweb.pro