Предикаты и формулы. Интерпретации. Истинность и выполнимость формул. Нормальные формы. - презентация

1 Предикаты и формулы. Интерпретации. Истинность и выполнимость формул. Нормальные формы.

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

3 Субъект предикат Субъект это то, о чем что-то утверждается в высказывании; предикат - это то, что утверждается о субъекте (его свойство; отношение к другому субъекту; действие). Математика – точная наука. Субъект Предикат Субъект Предикат В логике предикатов высказывания также имеют значением или «Истину» или «Ложь».в логике предикатов истинностное значение предиката ставится как функция в соответствие определенному предмету или группе предметов! В логике предикатов, как и в логике высказываний, высказывания также имеют значением или «Истину» или «Ложь». Разница в том, что в логике предикатов истинностное значение предиката ставится как функция в соответствие определенному предмету или группе предметов!

4 Пример Понятие предиката «х - простое число». Рассмотрим высказывание «х - простое число». При одних значениях х (3; 29 ) эта форма дает истинные высказывания, а при других значениях х (9; 12; 28 ) эта форма дает ложные высказывания. Исходное высказывание х, определенной на множестве N, принимающую значения из множества {1; 0}. Исходное высказывание определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1; 0}. функцией Здесь предикат выражает свойство субъекта и является функцией субъекта. Определение. Одноместным предикатом Р(х) произвольная функция переменного х, принимающая значения из множества {1; 0}. Определение. Одноместным предикатом Р(х) называется произвольная функция переменного х, определенная на множестве М и принимающая значения из множества {1; 0}. Множество М, на котором определен предикат P(х), называется областью определения предиката. Определение. множество истинности предиката I р Определение. Множество всех элементов х М, при которых предикат принимает значение «ИСТИНА», называется множеством истинности предиката Р(х), то есть множество истинности предиката Р(х) - это множество I р = {х| х М, Р(х) = 1}. предикат Р(х) «х - простое число» определен на множестве N, I р - есть множество всех простых чисел. Так, предикат Р(х) = «х - простое число» определен на множестве N, а его множество I р - есть множество всех простых чисел.

5 Р(х)="х- простое число" Матрица предикатов Предикат Р(х)="х- простое число" можно задать таблицей, которую называют матрицей предиката или таблицей истинности предиката. Предикат называется тождественно истинным, если его множество истинности совпадает с множеством определения Х, и тождественно-ложным, если его множество истинности пусто. Предикат выполнимый, если в области определения для одних значений истина, а для других ложь.

6 , аргументами которой могут быть ПРОИЗВОЛЬНЫЕ ОБЪЕКТЫ из некоторого множества, значения функции "истина" или "ложь". Формально предикатом называется функция, аргументами которой могут быть ПРОИЗВОЛЬНЫЕ ОБЪЕКТЫ из некоторого множества, а значения функции "истина" или "ложь". Предикат будем рассматривать как расширение понятия высказывания.Пример. Вместо трех высказываний "Маша любит кашу" "Даша любит кашу" "Саша любит кашу" "Икс любит кашу" вместо неизвестного Икс либо Маша, либо Даша, либо Саша. можно написать один предикат - "Икс любит кашу" и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша. Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.

7 Рассмотрим еще примеры предикатов: 1. Q(x) =« sin х = 0 » определен на множестве R, его множество истинности Iq= {x| x = k; k Z}. 1. Предикат Q(x) = « sin х = 0 » определен на множестве R, а его множество истинности Iq= {x| x = k; k Z}. 2. F(x) - «Диагонали параллелограмма х перпендикулярны » определен на множестве всех параллелограммов,его множеством истинности является множество всех ромбов. 2. Предикат F(x) - «Диагонали параллелограмма х перпендикулярны » определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов. 3. Р(х): «х 2 + 1> 0, x R»; область определения предиката М= R область истинности – тоже R для данного предиката М = I p тождественно истинными. 3. Р(х): «х 2 + 1> 0, x R»; область определения предиката М= R и область истинности – тоже R. Таким образом, для данного предиката М = I p. Такие предикаты называются тождественно истинными. 4. В(х): «х 2 + 1< 0, x R»; область истинности Ip =. тождественно ложными. 4. В(х): «х 2 + 1< 0, x R»; область истинности Ip =. Такие предикаты называются тождественно ложными. ЭТО ОДНОМЕСТНЫЕ ПРЕДИКАТЫ (в них 1 субъект)!

8 выражаются отношения между предметами. Введем понятие многоместного предиката, с помощью которого выражаются отношения между предметами. «х < у» Р(х, у), определенной на множестве Z х Zс множеством значений {1; 0}. Примером отношения между двумя предметами является отношение «меньше» («больше»). Пусть отношение «х < у» введено на множестве Z целых чисел, где х, у Z, то есть является функцией двух переменных Р(х, у), определенной на множестве Z х Z с множеством значений {1; 0}. Определение. Двухместным предикатом Р(х, у) х у (субъекты предиката), определенная на множестве М =М 1 М 2 (х М 1, у М 2 ) принимающая значения из множества {1; 0}. Определение. Двухместным предикатом Р(х, у) называется функция двух переменных х и у (субъекты предиката), определенная на множестве М =М 1 М 2 (х М 1, у М 2 ) и принимающая значения из множества {1; 0}. «х < у» для пар (2; 1) (4; 4) и (3; 7). Найдем значения предиката «х < у», где х, у Z для пар (2; 1), (4; 4) и (3; 7). Р(2; 1) = 0; Р(4; 4)=0; Р(3; 7)=1. Областью истинности Р i множество всех пар Областью истинности Р i этого предиката является множество всех пар целых чисел, удовлетворяющих данному неравенству. Многоместные предикаты

9 N–местным предикатом P(x 1, х 2 …х n ) определенная на множестве М= М 1 хМ 2 х…хМ n принимающая значения из множества {1; 0}. N–местным предикатом P(x 1, х 2 …х n ) называется логическая функция от n переменных, определенная на множестве М= М 1 хМ 2 х…хМ n и принимающая значения из множества {1; 0}. местностью или арностью предиката С каждым предикатом связано число, которое называется местностью или арностью предиката (количество переменных). логические операции. Для предикатов справедливы и имеют тот же смысл ранее рассмотренные логические операции. Например: 1. "ЕСЛИ Маша любит кашу, ТО Саша любит кашу". 2. Р(х) – х делится на 2; Q(x) – x делится на 3; P(x)&Q(x) – x делится на 2 и 3, т. е. определен предикат делимости на S(x,y) – x равно y. S(x,y)& S(y,z) S(x,z)

10 НАВЕШИВАНИЯ КВАНТОРОВ (операции связывания кванторами). Но есть и две новые операции, специфические. Они называются операциями НАВЕШИВАНИЯ КВАНТОРОВ (операции связывания кванторами). "для всех" - квантор общности"некоторые" - квантор существования. All Эти операции соответствуют фразам "для всех" - квантор общности и "некоторые" - квантор существования. Квантор общности произошел от английского All и обозначается буквой A, перевернутой вверх ногами -. Exist E Квантор существования произошел от английского Exist и обозначается буквой E, которую вверх ногами переворачивать бесполезно, поэтому ее повернули кругом -.

11 Квантор общности Квантор общности - высказывание истинно для каждого Квантор существования, т. е. это высказывание не зависит от x. Квантор существования - высказывание истинно, если существует, для которого это высказывание истинно. Для конечных множеств операции навешивания кванторов можно выразить через операции ^ и Для конечных множеств операции навешивания кванторов можно выразить через операции ^ и : Если М = {a 1, a 2, …, a m } – конечное множество, то можно считать, что

12 Кванторы можно навешивать также на переменные многоместных предикатов, на одну переменную, несколько или сразу на все. Переменная Х, на которую навешен квантор, называется связанной, в противном случае – свободной. Рассмотрим, например, предикат Здесь x, у – связанные переменные, z, t – свободные переменные.

13 Значение предиката не зависит от связанных переменных, а определяется только значениями свободных переменных. Это означает во-первых, что навешивание квантора на одну переменную уменьшает на 1 местность исходного предиката. Так, предикат является двуместным. Во-вторых, предикат не изменится, если связанные переменные поменять на другие (отличные от свободных). Например

14 Наш предикат из примера после навешивания каждого из кванторов также превращается в высказывание, которое может быть истинно или ложно! ВСЕ "ВСЕ любят кашу" НЕКОТОРЫЕ "НЕКОТОРЫЕ любят кашу" Это, кстати, был (до навешивания кванторов) одноместный предикат (функция 1 переменной). Но ведь предикаты могут быть не только одноместные. "Икс любит игрека" - двухместный предикат. "ВСЕ любят игрека" - одноместный предикат. "ВСЕ любят кофе" - нульместный предикат, то есть высказывание, не зависящее от переменной.

15 Подстановка константы вместо предметной переменной Пусть – n-местный предикат на множестве М, и пусть. Подставим вместо (например) х n константу a. Получим (n-1)-местный предикат Можно сразу подставить одну и ту же или разные константы вместо нескольких переменных. Тогда соответствующим образом уменьшится местность предиката.

16 Интересно посмотреть, как ведут себя кванторы в присутствии операции отрицания. Возьмем отрицание предиката "ВСЕ любят кашу": "НЕ ВЕРНО, что ВСЕ любят кашу". (по закону Де Моргана: отрицание высказывания «А и В» эквивалентно высказыванию «не-А или не-В», т.е. А & B = A B Это равносильно (по закону Де Моргана: отрицание высказывания «А и В» эквивалентно высказыванию «не-А или не-В», т.е. А & B = A B) заявлению: "НЕКОТОРЫЕ НЕ любят кашу". отрицание "задвинули" за квантор в результате чего квантор сменился на противоположный. То есть отрицание "задвинули" за квантор, в результате чего квантор сменился на противоположный.

17

18 В последних четырех тождествах предикат Q, вообще говоря, может иметь предметные переменные, но отличные от x

19 ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ – САМЫЙ БЛИЗКИЙ К ЕСТЕСТВЕННОМУ. А теперь сделаем одно из самых важных заявлений: ИЗ ФОРМАЛИЗОВАННЫХ ЯЗЫКОВ МАТЕМАТИКИ ЯЗЫК ПРЕДИКАТОВ – САМЫЙ БЛИЗКИЙ К ЕСТЕСТВЕННОМУ. Поэтому работы по искусственному интеллекту тяготеют к использованию этого языка. В сравнении с естественным это очень (во многих смыслах) ограниченный язык. Но лучшего за 100 лет не придумано. программирования ПРОЛОГ - ПРОграммирование на ЛОГике. В хорошо формализованных системах даже наоборот - дополнительно ограничивают этот язык для удобной реализации на компьютерах. Примером тому язык (логического) программирования ПРОЛОГ - ПРОграммирование на ЛОГике.

20 На языке предикатов можно описать далеко не все, хотя и многое. Но даже в этом ограниченном пространстве подчас приходится применять хитрости и уловки, вот их "классические примеры". "Все студенты умники" Если мы желаем сказать на языке предикатов "Все студенты умники", то рекомендуется конструкция "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс студент, ТО икс умник«. "Некоторые студенты умники", Но если хотим сказать "Некоторые студенты умники", то это следует записать так: "ДЛЯ НЕКОТОРЫХ иксов справедливо: икс студент И икс умник«. "ДЛЯ НЕКОТОРЫХ иксов справедливо: икс студент И икс умник«.

21 и И еще высказывание "Собакам и кошкам вход воспрещен". Что имеется в виду под союзом «и»? вариант 1 "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака И икс - кошка, ТО иксу вход запрещен". "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака И икс - кошка, ТО иксу вход запрещен". Ясно что таких иксов (и таких игреков), которые бы были одновременно собакой и кошкой не существует! Поэтому вариант 2 "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака ИЛИ икс - кошка, ТО иксу вход запрещен"

22 Формула логики предикатов, в которой из операций логики высказываний имеются только конъюнкция, дизъюнкция и отрицание, причем отрицание относится только к элементарным предикатам, называется приведенной формой предиката. Теорема. Для всякого предиката существует равносильная ему приведенная нормальная форма. Доказательство. Действительно, все операции в данной предикатной формуле можно выразить через конъюнкцию, дизъюнкцию и отрицание (например, в виде ДНФ). Если после этого некоторые отрицания будут относиться к частям формулы, содержащим кванторы, то отрицания можно снять с кванторов согласно равносильностям 1 и 2, а снять отрицания с конъюнкций и дизъюнкций можно, следуя законам де Моргана. После всех описанных преобразований предикат, очевидно, будет представлен в приведенной форме.

23 Предикатная формула вида Предикатная формула вида где К i – кванторы, где К i – кванторы, x i – различные связанные переменные, F – предикатная формула без кванторов, находящаяся в приведенной форме, называется предваренной нормальной формой предиката. Для всякого предиката существует равносильная ему предваренная нормальная форма. Теорема. Для всякого предиката существует равносильная ему предваренная нормальная форма.

24 Формулы Предикаты могут быть выражены с помощью так называемых предикатных формул. Внимание! Формула будет предикатом, когда все переменные определены на некотором множестве, и определены все предикаты, входящие в формулу. Предикаты могут быть выражены с помощью так называемых предикатных формул. Внимание! Формула будет предикатом, когда все переменные определены на некотором множестве, и определены все предикаты, входящие в формулу. А(х, у); В(х) - элементарные формулы. Если A, B – предикатные формулы, то формулами являются также выражения ¬A, A B, yA. А(х, у); В(х) - элементарные формулы. Если A, B – предикатные формулы, то формулами являются также выражения ¬A, A B, yA.

25 С помощью предикатов можно записывать различные математические утверждения. Рассмотрим, как можно записать утверждение: Числовая последовательность {x n } имеет пределом число a. Математическая запись: Запишем данное утверждение с помощью кванторов и обозначим его A: