🗊Презентация Lektsia_5_6_red

Лекция 5 Исчисление предикатов

Понятие предиката В математике и других науках наряду с высказываниями встречаются выражения, имеющие форму высказывания, но содержащие переменные, принадлежащие некоторому множеству V. Множество называется предметной областью, а переменные – предметными переменными.      Например, “2 – простое число” - высказывание;      “3>1” - высказывание. Но, заменив числа в этих высказываниях предметной переменной x из множества натуральных чисел N, получим выражения: “x - простое число”,      “x1>x2”, являющиеся не высказываниями, а предикатами. Предикаты отражают свойства и отношения между предметами из предметной области.

Понятие предиката (2)      Обозначим P1(x) - свойство “быть простым числом”, а      P2(x1,x2) отношение “x1 больше x2”. В общем случае мы ничего не можем сказать о значении предиката, но подставив, например, в P1 и P2 значения x=2, x1=3, x2=1, получим P1(2) - “2-простое число”,      P2(3,1) - “3 больше 1” - истинные высказывания, а подставив значения x=4, x1=1, x2=3. получим P1(4) - “4 – простое число”,      P2(1,3) - “1 больше 3” – ложные высказывания, т.е. предикат при подстановки конкретных констант из предметной области, может принимать значение И или Л.

ОПРЕДЕЛЕНИЕ Предикат – это переменное высказывание о предметах из заданной области. Предикат Р(х) не конкретен, пока не определён х. При конкретном значении х предикат принимает значение Истина или Ложь {И, Л}. Таким образом, предикат на множестве V есть логическая функция, принимающая значения {И, Л}, если аргументы фиксированы: P(x) V  {И, Л} В общем случае предикат зависит от n переменных: P(x1, x2, … , xn ) – n – местный предикат. Одноместные предикаты обычно выражают свойства предметов, Двуместные – отношения между предметами.

Кванторы. Двойственность. Введём связки: - квантор всеобщности;          Если P(x) - одноместный предикат, то запись xP(x) означает, что свойство P выполняется для всех предметов из предметной области. Связка  - квантор существования.  xP(x) означает, что существует по крайней мере один предмет, обладающий свойством P.     Самое распространенное и часто применяемое свойство кванторов — это закон двойственности, который формулируется так: 1) x F(x) = x (F(x)), 2) x F(x) = x (F(x)).

Кванторы. Двойственность Действительно, утверждение x F(x) означает, что не для всех х из области определения F(x) - истинно. Равносильное высказывание – «Существует хотя бы один предмет х, для которого F(x) ложно». Правило: знак отрицания можно продвинуть за квантор, при этом квантор меняется на противоположный. Пример. Пусть Р(х) означает «х есть птица», L(x) – «х умеет летать». Тогда утверждение x (Р(x)  L(x) ) получит смысл «Не все птицы летают». Применим правило двойственности кванторов: x (Р(x)  L(x) ) = x (Р(x)  L(x) ) = x  (Р(x)  L(x) ) = = x (Р(х) &  L(x)) Получено утверждение «Существуют птицы, которые не летают»

ЗАПИСЬ УТВЕРЖДЕНИЙ НА ЯЗЫКЕ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ Рассмотрим два правила, которые основаны на силлогизмах Аристотеля. Общеутвердительное суждение: «Все примеры, обладающие свойством Р, обладают также свойством S». x (Р(x)  S(x) ) 2. Частноутвердительное суждение: «Некоторые предметы, обладающие свойством Р, обладают также свойством S». x (Р(х) & S(x)) Пример 1. Всякое положительное целое число есть натуральное число. 5- положительное целое. Следовательно, 5- натуральное число. Обозначим Р(х) - «х –положительное целое число», N(x) – «х –натуральное число». Тогда x (Р(x)  N(x) ) P(5)___________ N(5)

ПРИМЕРЫ ЗАПИСИ УТВЕРЖДЕНИЙ НА ЯЗЫКЕ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ Пример 2. Рассмотрим рассуждение: Каждый студент – молод. Некоторые молодые люди занимаются спортом. Следовательно, существуют студенты – спортсмены. Введём предикаты С(х) «х – студент», М(х) «х – молод», S(x) «х- занимается спортом» . Формальная запись рассуждения: Тогда x (С(x)  М(x) ) x (М(х) & S(x)) -------------------- x (C(х) & S(x))

Пример 3 Все люди – животные: y (S(y)  C(y)). Следовательно, голова человека является головой животного: x (y (S(y) & V(x, y))  z (C(z) & V(x, z))). Здесь S(x) – «х – человек»; C(x) – «х – животное»; V(x, y) – «х является головой у». Если перевод первого высказывания довольно прост, то с переводом второго возникают сложности, связанные с определением его семантики.

СВОБОДНЫЕ И СВЯЗАННЫЕ ВХОЖДЕНИЯ ПЕРЕМЕННЫХ Переход от P(x) к  xP(x) или к  xP(x) называется связыванием переменной или навешиванием квантора на переменную x. Переменная, на которую навесили квантор, называется связанной, несвязанная переменная называется свободной.      Смысл связанных и свободных переменных различен. Свободная переменная – это переменная, которая может принимать любые значения из V . При этом P(x) зависит от значения x . Выражение  x)P(x) от x не зависит и при заданных P и V имеет вполне определенное значение.      Например, если P(x) - “быть четным числом”, то xP(x) принимает значение Л, если V - множество натуральных чисел и xP(x) принимает значение И, если V={2,4,6,…}.

Формулы исчисления предикатов Для логики предикатов определим понятия терма, атома и формулы. Здесь мы имеем: х1, х2, …, хn, … – предметные переменные; a1, a2, …ak, … – предметные константы; P11 , P12 , …, Pij , …, … – предикатные буквы; f11 , f12, …, fkm, … – функциональные буквы. Верхний индекс предикатной или функциональной буквы указывает число аргументов, а нижний служит для различения букв с одним и тем же числом аргументов. В дальнейшем верхний индекс будем опускать.

ТЕРМЫ. Функциональные символы задают функции над предметами. Если функциональный символ зависит от п аргументов, это функция, отображающая п – ку предметов в предмет: fnk Vn  V Правила конструирования термов: всякая предметная переменная или предметная константа есть терм; если fi – функциональная буква и t1, t2, …, tn – термы, то fi(t1, t2, …, tn) – терм; других правил образования термов нет. Например, х, у и 1 – термы, mult и plus – двухместные функциональные символы, тогда plus(y, 1) и mult(x, plus(y, 1)) – также термы.

Формулы исчисления предикатов. Правила образования атомов (атомарных формул): всякое переменное высказывание Х есть атом; если Pi – предикатная буква, а t1, t2, …, tn – термы, то Pi(t1, t2, …, tn) есть атом; других правил образования атомов нет. Формулы логики предикатов конструируются по следующим правилам: всякий атом есть формула; если А и В – формулы и х – предметная переменная, то каждое из выражений А, А & В, А  В, А  В, хА и хА есть формула; других правил образования формул нет.

Формулы исчисления предикатов Для того чтобы сократить количество скобок в формуле, используем правила силы операций: связка  сильнее связок &, , , ; связка & сильнее связок , , ; связка  сильнее связок , ; связка  сильнее связки . Внешние скобки всегда будем опускать и вообще везде, где не возникает двусмысленностей, будем пользоваться минимумом скобок. Кроме того, всегда предполагаем, что свободные и связанные переменные обозначены разными буквами, и если один квантор находится в области действия другого, то переменные, связанные этими кванторами, также обозначены разными буквами.

ИНТЕРПРЕТАЦИЯ Пусть имеется непустое множество V - область интерпретации. Сопоставим каждому предикатному символу п – местный предикат на V . Каждому функциональному символу сопоставим предметную функцию в V . Каждой константе сопоставим предмет из V . Тогда любая формула без свободных переменных превратится в высказывание, истинное или ложное. Всякая формула со свободными переменными станет отношением на области интерпретации, истинным для одних значений переменных и ложным для других. Очевидно, что формула, истинная в одной интерпретации, может быть ложной в других интерпретациях.

ПРИМЕР ИНТЕРПРЕТАЦИИ Пусть V содержит два предмета: {a, b} На этой области заданы: функция f f(a)=b, f(b)=a, предикаты А(х), принимающий значения (А(а)=И, А(b)=Л) Задан предикат В(x, y) (В(a, a) =И , В(a, b) = Л, В(b, a) = Л, В(b, b) =И). Рассмотрим формулы: 1. x (А(х)  А(f (x))) 2. x (В(x, х)) Проверим истинность (ложность) формулы 1. Возможны только два случая: при х=а А(а)  А(f (а)) = И  А(b) = И  Л=Л при х=b А(b)  А(f (b)) = Л  А(a) = Л  И = И Вывод: при х= b формула А(х)  А(f (x)) стала истинной, значит формула 1 верна. Самостоятельно проверьте истинность (ложность) формулы 2.

ОПРЕДЕЛЕНИЯ Определение 1. Формула исчисления предикатов А, истинная во всех интерпретациях, называется общезначимой (тавтологией). Определение 2. Формула исчисления предикатов А, ложная во всех интерпретациях, называется противоречием. Определение 3. Формула исчисления предикатов А, истинная хотя бы в одной интерпретации, называется выполнимой (непротиворечивой). Определение 4. Формула исчисления предикатов А, ложная хотя бы в одной интерпретации, называется опровержимой. (Если А выполнима, А – опровержима). Часто область интерпретации бесконечна, тогда перебор при доказательстве истинности (ложности) формулы невозможен. Необходим логический вывод.

ПРИМЕРЫ Пример 1. Покажем, что формула xР(x)  Р(y) общезначима. Рассуждаем от противного. Предположим, что в некоторой области интерпретации V эта формула стала ложной. Импликация ложна только если верно ИЛ. В этом случае xР(x) =И и Р(y) = Л. Но, поскольку Р(х) верно для всех х (квантор всеобщности), Р(y) не может быть ложным. Мы пришли к противоречию, следовательно, исходная формула общезначима. Пример 2. Аналогично можно показать, что формула Р(y)  xР(x) также общезначима. Проведите рассуждение самостоятельно. Пример 3. Покажем, что формула xР(x)  xР(x) не является общезначимой. Для доказательства придумаем интерпретацию, на которой формула будет ложной. Вариант: V ={a, b} P(a)=И, P(b)=Л. xР(x) = P(a) P(b)=И Л = И xР(x) =P(a)& P(b)=И&Л = Л Получим И Л=Л.

Лекция 6. Исчисление предикатов как формальная система

Исчисление предикатов как формальная система 1. Исходными элементами ФС2 являются: счетное множество предметных переменных x1, х2,, … , хn, . . .; конечное (может быть и пустое) или счетное множество предметных констант a1, a2, …; конечное (может быть и пустое) или счетное множество функциональных букв ; непустое конечное или счетное множество предикатных букв ; символы исчисления высказываний: ¬, &, , →; скобки ( ) и запятая; символы , ; других исходных элементов нет.

2. Правила образования ППФ: всякий атом есть ППФ; если А и В – ППФ и х – предметная переменная, то каждое из выражений ¬А, А → В, А & В, А  B, х А и х A есть ППФ; других правил образования ППФ нет. Таким образом, форма записи ППФ совпадает с записью фор­мул исчисления предикатов. 3. Система аксиом. К системе аксиом исчисления высказываний добавляются еще две аксиомы: a12. x A(x)) → A(t), где A(x) есть ППФ и t – терм, свобод­ный для x в A(x). а13. A(t) → x A(x), где A(x) есть ППФ и t – терм, свобод­ный для x в A(x).

Правила вывода Правило 1. Все аксиомы выводимы. Правило 2. Правило подстановки. Это правило аналогично правилу подстановки, которое имело место для исчисления высказываний. Только для ФС2 мы будем иметь дело с такой подстановкой термов t1, t2, …, tk вместо х в A[х], что A[х] свободна для t1, t2, …, tk . Несоблюдение этого условия может привести к неприятным последствиям. Например, пусть в аксиоме 12 терм t не свободен для x в А[x] и пусть А[x] есть ППФ вида ¬x2A(x1, x2) и t есть x2. Тогда терм t не свободен для x1 в ¬x2A(x1, x2). Рассмотрим а12: x1(¬x2 A(x1, x2)) → ¬2A(x2, x2). Возьмем в качестве интерпретации любую область, содержащую не менее двух элементов, а в качестве A – отношение тождества. Тогда посылка x1(¬x2A(x1,x2)) в а12 истинна, а заключение ¬x2 A(x2, x2) ложно.

Правила вывода Правило 3. Правило modus ponens (МР). Если ├ A и ├ A → В, то ├ B. Правило 4. Правило обобщения (или правило связывания квантором общности). Если ППФ B → A(x) при условии, что В не содержит свобод­ных вхождении x, выводима, то выводима будет и ППФ B → x A(x). В дальнейшем это правило будем обозначать че­рез Gen. Правило 5. Правило конкретизации (или правило связывания кван­тором существования). Если A(x) → В – выводимая ППФ (теорема) и В не содержит свободных вхождений x, то x A(x) → В также теорема. Обоз­начим это правило через Еx. Правило 6. Если A – теорема, имеющая квантор общности и/или кван­тор существования, то одна связанная переменная в A может быть заменена другой связанной переменной, отличной от всех свобод­ных переменных, одновременно во всех областях действия кванто­ра и в самом кванторе. Полученная ППФ также является теоремой. Правило 7. Других правил вывода нет.

Свойства ИП как ФС. Остановимся теперь на свойствах исчисления предикатов: не­противоречивости и полноте. Как и раньше, будем считать непроти­воречивым такое исчисление, в котором не выводимы никакие две ППФ, из которых одна является отрицанием другой. Теорема 4. Исчисление предикатов первого порядка непротиворечиво. Так как аксиомам исчисления предикатов соответствуют выводи­мые ППФ исчисления высказываний, то, очевидно, что всякой вы­водимой ППФ исчисления предикатов соответствует выводимая ППФ исчисления высказываний. Из полноты исчисления высказы­ваний и непротиворечивости исчисления предикатов вытекает, что всякая ППФ исчисления высказываний, выводимая в исчислении предикатов, является выводимой ППФ исчисления высказываний.

Свойства ИП как ФС. Теорема 5. Во всяком исчислении предикатов первого поряд­ка всякая теорема является общезначимой ППФ. Обратное утверждение носит название проблемы полноты исчис­ления предикатов в широком смысле, которая решается положи­тельным образом. Впервые проблему полноты в широком смысле в 1930 г. доказал выдающийся немецкий математик и логик К. Гедель. Теорема 6. (Геделя о полноте). Во всяком исчислении преди­катов первого порядка всякая общезначимая ППФ является тео­ремой. Что касается проблемы полноты в узком смысле, то для исчис­ления предикатов первого порядка она решается отрицательно. На­помним, что система аксиом называется полной в узком смысле, если нельзя без противоречия присоединить к данной системе никакую другую не выводимую ППФ. Исчисление предикатов оказы­вается неполным в узком смысле, так как к его аксиомам можно присоединить без противоречия недоказуемую в нем следующую ППФ х А(х) →x A(x).

Свойства ИП как ФС. При определении формальной системы мы требовали существования разрешающей процедуры для понятия вывода, но для понятия выводимости или доказуемости ППФ этого требования не выставляли. Мы отмечали, что формальная система, для которой существует эффективная разрешающая процедура, позволяющая узнать по данной ППФ, является ли она теоремой или нет, называется разрешимой, в противном случае такая формальная система неразрешима. Примером разрешимой формальной системы является исчисление высказываний. Для него мы имеем эффективную процедуру разрешения, выраженную в виде истинностных таблиц, по которым можно легко судить, является ли ППФ теоремой (общезначимой ППФ) или нет. Исчисление предикатов первого порядка – пример неразрешимой формальной системы.

Доказательство логического следствия в исчислении высказываний

Понятие логического следствия Применяя правила вывода к аксиомам, либо к аксиомам и посылкам (гипотезам), мы чисто механически выводим новые утверждения, теоремы. В логической системе заключительному утверждению приписывается значение «истина», если каждой посылке также приписано значение «истина». Аксиомы общезначимы – им приписано значение «истина» в любой интерпретации. Вывод из посылок будет корректным, если для всех интерпретаций, в которых истинны посылки, будет истинным также заключение.

Определения Определение 1. Пусть даны формулы F1, F2, …, Fn и G. Скажем, что формула G является логическим следствием F1, F2, …, Fn (или G логически следует из F1, F2, …, Fn) тогда и только тогда, когда для любой интерпретации I, в которой F1 & F2 & … & Fn истинна, G также истинна. Для обозначения логического следования формулы G из посылок F1, F2, …, Fn будем писать F1, F2, …, Fn ╞ G. Символ ╞ есть некоторое отношение между формулами, причем, если посылки соединены знаком &, то имеет место двуместное отношение: F1 & F2 & … & Fn ╞ G. Логически правильные утверждения важны для образования новых истинных рассуждений из истинных посылок.

Две теоремы о логическом следствии Теперь приведем две простые, но важные теоремы, связывающие понятия логического следования с понятиями общезначимости и противоречивости. Теорема1. Даны формулы F1, F2, …, Fn и G. Формула G является логическим следствием формул F1, F2, …, Fn тогда и только тогда, когда формула F1 & F2 & … & Fn  G общезначима, т.е. ╞ F1 & F2 & … & Fn  G. Формула F1 & F2 & … & Fn  G называется теоремой, а G называется заключением теоремы. Теорема 2. Даны формулы F1, F2, …, Fn и G. Формула G является логическим следствием формул F1, F2, …, Fn тогда и только тогда, когда формула F1 & F2 & … & Fn & G противоречива. Таким образом, факт, что данная формула является логическим следствием конечной последовательности формул, сводится к доказательству общезначимости или противоречивости некоторой формулы. Следовательно, имеется полная аналогия при выводе заключения теоремы из множества аксиом или посылок в формальной системе, и многие проблемы в математике могут быть сформулированы как проблемы доказательства теорем. Обозначим общезначимую формулу через , а противоречивую – через .

Нормальные формы. При разработке методов автоматического доказательства теорем необходимо все формулы, как логики высказываний, так и логики предикатов первого порядка, представить в некотором стандартном виде. В дальнейшем слова «первого порядка» будут опускаться, а логика предикатов считаться расширением логики высказываний за счет введения предикатов и кванторов общности  и кванторов существования . Простые высказывания в логике высказываний будем называть атомами, принимающими два значения: истина (И) или ложь (Л). Символы И и Л называются истинностными значениями.

Пример 1 Дано: Если капиталовложения останутся постоянными (К), то возрастут правительственные расходы (R) или возникнет безработица (В). Если правительственные расходы не возрастут, то налоги будут снижены (N). Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возникнет. Капиталовложения останутся постоянными. Следовательно, правительственные расходы возрастут. Запишем формальное представление утверждения. F1: KRB F2: R N F3: N&K  B F4: K -------------------------- G: R

Доказательство логического следствия по Теореме 1 Построим формулу F1&F2&F3&F4 G и преобразуем ее к виду: F1&F2&F3&F4 G = (F1&F2&F3&F4)G = F1F2F3F4 G Докажем общезначимость выражения (KRB)(R N)(N&K  B)К R Приведём формулу к нормальной форме: ( KRB)(R N)((N&K)  B)К R = = K&R &B   R& N  N&K &B К R = = R &B   R& N  N&K &B К R = = R &B  R& N  N& B К R = BR&N  N&BКR = = BN  N&BКR = BN  BКR = И N КR = И (к подчеркнутым частям формулы многократно применяем тождество XX&Y= XY, В B=И).

Доказательство логического следствия по Теореме 2 Построим по Теореме 2 формулу F1&F2&F3&F4 &G : (KRB)&(R N)&(N&K  B)& К & R= = ( K RB)&(R N)&(N  K B)& К & R= = ( K & К  R & К B & К)&(R &R  N&R) &(N  K B)= =(R & К B & К)& N&R &(N  K B)= =(R & К &R B & К &R)& (N & N  K & N  B & N)= = B & К &R& (K & N  B & N)= (B & К &R& K & N  B & К &R& B & N)=Л Л=Л (сомножители, выделенные цветом, обращают логическое произведение в Ложь) Легко заметить, что доказательство противоречивости выполняется гораздо легче, чем доказательство общезначимости.

Нормальные формы в исчислении высказываний Любую формулу логики высказываний удобно представить в виде так называемой нормальной формы. Атом или его отрицание будем называть литерой. Говорят, что формула логики высказываний В представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет форму B = B1 & B2 & … & Bm, где каждая из Bi (i =  ) есть дизъюнкция литер. Например, В = (Х1  Х2) & (Х1  Х2  Х3) & Х3 представлена в КНФ. Аналогично говорят, что формула логики высказываний В представлена в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет форму B = B1  B2  …  Bm, где каждая из Bi (i =  ) есть конъюнкция литер. Например, В = (Х1 & Х2 & Х3)  (Х1 & Х2)  Х3 представлена в ДНФ.

Алгоритм приведения к ДНФ, КНФ Любая формула исчисления высказываний может быть преобразована в нормальную форму с помощью следующего алгоритма. Шаг 1. А  В = (А  В) & (В  А). А  В = А  В. Шаг 2. А = А. законы Де-Моргана. Шаг 3. А  (В & С) = (А  В) & (А  С) (для КНФ). А & (В  С) = А & В  А & С (для ДНФ).   Пример 1. Получим КНФ для формулы (A  (B  C))  D. (A  (B  C))  D = (A  B  C)  D = (A  B  C)  D = (A & B & C)  D = (A  D) & (B  D) & (C  D).   Пример 2. Получим ДНФ для формулы (A & B) & (A  B). (A & B) & (A  B) = (A  B) & (A  B) = ((A  B) & A)  ((A  B) & B) = (A & B)  (B & A).