Презентация на тему "ЛОГИКА ПРЕДИКАТОВ"

Содержание

• 
  Слайд 1

  ЛОГИКА ПРЕДИКАТОВ

• 
  Слайд 2
  

  Определение. Предикатом P(x1, x2, ... , xn) называется функция, аргументы которой определены на некотором множестве М, x1, x2, ... , xn∈ M, а сама она принимает два значения: И (истина) и Л (ложь). Таким образом, предикат осуществляет отображение М → {И, Л}. Переменные x1, x2, ... , xnназываются предметнымипеременными, а множество M – предметной областью. Предикат от n переменных называется n-местным предикатом. Высказывание есть 0-местный предикат. Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом, можно говорить об алгебре предикатов.

• 
  Слайд 3
  

  Квантор общности. Пусть P(x) – некоторый предикат, определенный для каждого x М. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно для всякогоx М и ложным в противном случае. Символ x называется квантором общности. Выражение xP(x) читается: “Для всех x имеет место P(x)”. В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности: ØxP(x): “Не для всех x имеет место P(x)”. Пример . Пусть P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Всякое x – четное число" = «Все числа – четные». Отрицание ØxP(x) есть высказывание «Не всякое x – четное число» = «Не все числа – четные».

• 
  Слайд 4
  

  Квантор существования. Пусть P(x) – некоторый предикат, xМ. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно хотя бы для одногоxМ и ложным в противном случае. Символ x называется квантором существования. Выражение xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования: ØxP(x): “Не существует x, для которого имеет место P(x)”. Пример. Пусть, P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Некоторые x – четные числа” = “Существуют четные числа” . Высказывание ØxP(x) = “Неверно, что некоторые x – четные числа” = “Не существует четных чисел”.

• 
  Слайд 5
  

  Кванторы существования и общности называются двойственными кванторами. Буква x, стоящая справа от квантора, называется кванторной переменной и должна присутствовать обязательно. Переменная, стоящая под знаком квантора, называется также связанной переменной. Несвязанная переменная называется свободной.

• 
  Слайд 6
  

  Формулы логики предикатов. Равносильность формул   Определение.Формула логики предикатовопределяется индуктивно следующим образом: 1. Любая формула логики высказываний есть формула логики предикатов. К новым формулам логики предикатов относятся следующие выражения: 2. Предметные переменные x, y, z, ... есть формулы. 3. Предикаты P(x), Q(x, y), ... , а также выражения с кванторами xP(x), xR(x), xyQ(x, y),... есть формулы. 4. Если A и B – формулы, то ØA, AVB, A&B, AÞB, AB есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными. 5. Ничто, кроме указанного в пунктах 1 – 4, не есть формула.

• 
  Слайд 7
  

  Пример. 1. Следующие выражения являются формулами логики предикатов: а) A & BÞC, где A, B, C – высказывания. б) xyQ(x, y, z) & xyP(x, y, u). Проанализируем последовательно это выражение. Предикат Q(x, y, z) – формула; Выражение xyQ(x, y, z) – формула; переменные x, y – связанные, переменная z – свободная. Предикат P(x, y, u) – формула. Выражение xyP(x, y, u) – формула; переменные x, y – связанные, переменная u – свободная. Выражение xyQ(x, y, z) & xyP(x, y, u) – формула; переменные x, y – связанные, переменные z, u – свободные. 2. Выражение xyP(x, y, z) ÞQ(x, y, z) формулой не является. Действительно, выражение xyP(x, y, z) есть формула, в которой переменные x и y связанные, а переменная z свободная. Выражение Q(x, y, z) также формула, но в ней все переменные x, y, z свободные.

• 
  Слайд 8
  

  Определение. Формулы F и G, определенные на некотором множестве М, называютсяравносильнымина этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения. Определение. Формулы, равносильные на любых множествах, будем называть просто равносильными.  Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по следующим правилам: 1.Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов. 2. Перенос квантора через отрицание. Пусть A – формула, содержащая свободную переменную x. Тогда Ø(xA(x)ºx(ØA(x)). (2.1) Ø(xA(x))ºxØ(A(x)). (2.2)

• 
  Слайд 9
  

  3. Вынос квантора за скобки. Пусть формула A(x) содержит переменную x, а формула B не содержит переменной x, и все переменные, связанные в одной формуле, связаны в другой. Тогда   xA(x)VBºx(A(x)VB). xA(x)&Bºx(A(x)&B). xA(x)VBºx(A(x)VB). xA(x)&Bºx(A(x)&B). 4.Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции. Пусть формула B, так же, как и формула A, зависит от х. Тогда xA(x) & xB(x)ºx(A(x) & B(x)). xA(x) VxB(x)ºx(A(x) V B(x)).

• 
  Слайд 10
  

  5.Перестановка одноименных кванторов. xyA(x,y)ºyxA(x,y). xyA(x,y)ºyxA(x,y). Разноименные кванторы переставлять, вообще говоря, нельзя!   6. Переименование связанных переменных. Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора, получим формулу, равносильную A.   Пример2.11. A = xF(x) ÞxG(x). Заменяя связанную переменную x на y в первом члене импликации и на z во втором, получим равносильную формулу: B = yF(y) ÞzG(z). AºB.

• 
  Слайд 11
  

  Приведенные и нормальные формулы   Определение. Формулы, в которых из логических символов имеются только символы &, V и Ø,причем символ Ø встречается лишь перед символами предикатов, называются приведенными формулами. Пример. A(x)&B(x, y). xA(x) V xØB(x, y). Ø(A(x)&B(x, y)). xA(x) ÞxØB(x, y). Ø(xA(x) ÞxØB(x, y)). Теорема. Для каждой формулы существует равносильная ей приведеннаяформула, причем множества свободных и связанных переменных этих формул совпадают.

• 
  Слайд 12
  

  Выражение суждения в виде формулы логики предикатов  Существуют две задачи, определяющие связь между суждениями и формулами логики предикатов: 1) выражение суждения в виде формулы логики предикатов; 2) интерпретация формулы логики предикатов. Суждение – это мысль, в которой утверждается наличие или отсутствие свойств предметов, отношений между предметами. Простым суждением назовем суждение, в котором нельзя выделить часть, в свою очередь являющуюся суждением. Среди простых суждений выделяют атрибутивные суждения и суждения об отношениях. Все атрибутивные суждения можно разделить на следующие типы: "a есть P", "Все S есть P", "Ни один S не есть P", "Некоторые S есть P", "Некоторые S не есть P". Эти суждения следующим образом переводятся на язык логики предикатов: "a есть P" – P(a); "Все Sесть P" – x(S(x) ÞP(x)); "Ни один S не есть P" – x(S(x) ÞØP(x)); "Некоторые S есть P" – x(S(x) & P(x)); "Некоторые S не есть P" – x(S(x) & ØP(x)).

• 
  Слайд 13
  

  Если кванторная переменная связана квантором общности (), то в формуле используется знак импликации (Þ), а если кванторная переменная связана квантором существования (), то в формуле используется знак конъюнкции (&).   Пример2.17. Перевести на язык логики предикатов следующие суждения: а) Веста – собака. Заменим имя "Веста" символом "в" и введем предикат P(x) = "x – собака". Наше суждение можно выразить формулой: P(в).  б) Всякая логическая функция может быть задана таблицей. Введем предикаты S(x) = "x – логическая функция"; P(x) = "x может быть задана таблицей". Искомая формула: x(S(x) ÞP(x)). в) Ни один народ не хочет войны. Введем предикаты S(x) = "x – народ"; P(x) = "x хочет войны". Наше суждение можно выразить формулой: x(S(x) ÞØP(x)). г) Некоторые журналисты были в космосе. Введем предикаты S(x) = "x – журналист"; P(x) = "x был в космосе". Наше суждение можно выразить формулой: x(S(x) & P(x)). д) Некоторые современники динозавров не вымерли. Введем предикаты S(x) = "x – современник динозавров"; P(x) = "x вымер". Наше суждение можно выразить формулой: x(A(x) & ØP(x)).

• 
  Слайд 14
  

  Язык логики предикатов удобен для записи математических предложений: определений, теорем, необходимых и достаточных условий. Пример. «Для любого целого n > 2 не существует натуральных чисел x, y,z, удовлетворяющих равенству: xn+yn= zn». Введем предикаты: N(x) = "x – натуральное число"; M(x) = "x > 2"; P(x, y, z, n) = "xn + yn = zn". Для любых чисел x, y, z, n условие (посылка) теоремы Ферма есть конъюнкция N(x)&N(y)&N(z)&N(n)&M(n), а заключение есть ØP(x, y, z, n). Поэтому теорема Ферма формулируется следующим образом:   xyzn(N(x)&N(y)&N(z)&N(n)&M(n) ÞØP(x, y, z, n)).

• 
  Слайд 15
  

  Если теорема имеет вид x(P(x) ÞQ(x)), то предикат Q(x) является следствием предиката P(x). При этом предикат Q(x) называется необходимым условием предиката P(x), а предикат P(x) – достаточным условием предиката Q(x).   Пример. Запишем в виде формулы логики предикатов утверждение: "Если число делится на 6, то оно делится на 3". Введем предикаты P(x) = "x делится на 6"; Q(x) = "x делится на 3". Наше утверждение формулируется следующим образом: x(P(x) ÞQ(x)). Предикат P(x) (делимость на 6) является достаточным условием предиката Q(x) (делимость на 3). Предикат Q(x) (делимость на 3) является необходимым условием предиката P(x) (делимость на 6).