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

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

Логика предикатов Алгебра логики, рассматривая простые высказывания как целые, неделимые, без учета их внутренней структуры, оказывается недостаточной в анализе многих рассуждений. Есть необходимость в расширении логики высказываний, в построении такой логической системы, средствами которой можно было бы исследовать и структуру тех высказываний, которые в рамках логики высказываний рассматриваются как элементарные. Такой логической системой является логика предикатов, содержащая всю логику высказываний в качестве своей части. Логика предикатов расчленяет элементарное высказывание на субъект (буквально — подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально - сказуемое, хотя оно может играть и роль определения).

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

Пример Пример

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

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

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

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

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

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

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

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

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

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

Равносильные формулы логики предикатов

Равносильные формулы логики предикатов

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

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

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

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

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

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

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