Логика предикатов
методическая разработка по математике на тему

Урок 25. Основные понятия логики связанные с предикатами.

Опр1: предикатом P(х1,х2,…,хn) называется повествовательное предложение, содержащее __________________ переменные (х или х1, х2,…,хn), если вместо предметных переменных подставить конкретные значения, то получится выказывание – истинное или ложное.

( х-четное число ____________________и 4 – четное число_________________________)

Опр2: Количество предметных переменных определяет __________________________ предиката. В зависимости от количества предметных переменных предикаты бывают: одно-, двух-, трех-, …n-местные (сумма х и у четна________________________________)

Опр3: Множество значений предметных переменных, на котором предикат имеет смысл, называется _____________________________________________________________

Напр.______________________________________________________________________

Опр4: Множество значений предметных переменных, на котором предикат принимает значение «истина» называется _________________________________________ _______________________________предиката. Обозначается: _______________

Пример 1: На  множестве N чисел определен одноместный предикат
Р(х) : «х делится на 2».

Его множеством истинности является___________________________________________

Пример 2 : На множестве Z – целых чисел зададим двухместный предикат  
F(x;y) : «x > у».  Его множество истинности:

Кванторы.

Кроме операций логики высказываний, в логике предикатов рассматриваются операции квантификации. Для их обозначения используются символы:

-___________________________________________________________________________________

 -___________________________________________________________________________________

 Рассмотрим эти операции вначале для одноместных предикатов.

Пусть Р(x) - одноместный предикат, определенный на множестве M.

Опр5: Под выражением xP(x) будем понимать высказывание, которое принимает значение истина тогда и только тогда, когда ______________________________________

___________________________________________________________________________

Это высказывание уже не зависит от х.

Опр6: Переменную х в предикате  Р(х) называют ___________________________________,

a в высказывании xP(x) ______________________________________________________

Опр7: Под выражением  х Р(х) понимают высказывание, которое является  истинным, если ______________________________________________________________________

___________________________________________________________________________

______________________________________________________________________________Высказывание хР(х) не зависит от х в нем переменная х связана квантором существования.

Замечание 1: Операции квантификации являются обобщением  операций конъюнкции и дизъюнкции на случай бесконечного множества М предметной переменной.

Замечание 2: Операции квантификации понижают порядок (местность) предиката, а одноместный предикат превращается в высказывание (0-местный предикат).
Применение одной кванторной операции к двухместному предикату превращает его в одноместный предикат.

Пример 3 : у Т(х,у) – __________________________________________________________.

Пример 4 :  у Т(х,у) – _______________________________________________________

Применение двух  кванторных  операций к двухместному предикату превращает его в ____________________________________.

Замечание 3: Если на двухместный предикат навешать два одинаковых квантора, то их можно менять местами, если же кванторы разноименные, то этого делать нельзя.

Пример 5 :Пусть предикат Р(х,у) выражает свойство:

 «покупателю х подходит по размеру пара ботинок у»

Тогда высказывания:

1).  –_________________________________________________________

_____________________________________________________________________

2). –________________________________________________________

_____________________________________________________________________

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

Пример 6 :

Пусть задана формула F = . Рассмотрим 2 ее интерпретации:

1). М=N   P(x,y):  “xy”

 :____________________________________________________________

2).M=Z    P(x,y):  “xy”

 :____________________________________________________________.

Что можно сказать об истинности формулы F в 1-ом и 2-ом случаях?

Практические задания:

1. Запишите формулу логики предикатов для приведенного утверждения: «Некоторые люди хотят пить, если на улице жарко ».

Пусть даны предикаты: Р(х): «х – число  простое» и Q(x): «х – делится на 2», определенные на множестве R чисел.  Найти область истинности предиката:

2. Изобразите на координатной плоскости область истинности предиката
   ,  если  ,  и .
3. Определите вид предиката  на множестве действительных чисел?
4.  Определите значение истинности высказывания и его отрицания:

5. Даны предикаты:  Р(х):  х – простое число, В(х):  х – четное число, N(x):  х – натуральное число. Сформулировать на русском языке записанное ниже в символах логики предикатов высказывание, построить отрицание и определить  значение истинности:  

Урок 26.  Кванторные операции над предикатами.

Опр 1. Предикатной формулой называется выражение, составленное из переменных предикатов с помощью логических операций и кванторов, и обращающееся в конкретный предикат при подстановке вместо переменных конкретных предикатов.

______________________________________________________________

Предикатная формула должна удовлетворять следующим правилам:

1. Формула логики предикатов наз-ся атомарной, если _____________________

________________________________________________________________.

2. Пусть А – формула, тогда  - тоже формула.

_____________________________________________________________________________________________________________________________________

3. Пусть А и В – формулы, причем нет таких предметных переменных, которые были бы связаны в одной формуле и свободны в другой.
   Тогда ____________________________________________________________ формулы, в которых свободные переменные формул А и В остаются свободными, а связанные – связанными.
4. Пусть А – формула, содержащая свободную переменную х. тогда________________– тоже формулы, в которых переменная х – связана, а остальные переменные входящие в А, остаются свободными.

Пример 1:  Определите, какие из выражений являются формулами:

Равносильные преобразования формул.

Опр 2. Переход от формулы к равносильной ей формуле называется __________________________________________ исходной формулы.

Опр 3. Две формулы логики предикатов называются равносильными, ______________________________________________________________________________________________________________________________________. Все равносильности логики высказываний справедливы в логике предикатов.  

Теорема 1: Формулы логики предикатов F и Н равносильны тогда и только тогда, когда_________________________________________________________.

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

Основные равносильности логики предикатов.

Как и в логике высказываний, в логике предикатов сущ-ют эквивалентные нормальные формы представления любых предикатных формул, в том числе: приведенная нормальная, предваренная нормальная.

Опр 4. Формула А наз-ся приведенной, если ___________________________________________________________________

__________________________________________________________________________

___________________________________________________________________

__________________________________________________________________________

Для любой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных совпадают.

Опр 5. Предваренная нормальная форма (ПНФ) формулы – это форма:

1. Содержит только лог.операции: ________________________
2. Все отрицания ___________________________________________________
3. Все кванторы __________________________________________________

Пример 2.

Записать в ПНФ формулу логики предикатов: