X (S(x) > y(P(y) & R (x,y)).
Классическая по принципам:
1. Двузначность. Каждая формула может принять ровно одно из двух значений – И или Л.
2. Экстенсиональность. Значение сложного выражения зависит только от значения входящих в него частей.
3. Постулат о непустоте предметной области.
Язык логики предикатов:
1)Алфавит
Нелогические символы
Предметные (индивидные) константы – a, b, c,…
Предикаторные константы – Pn,Qn,Rn,… (n – местность предикатора)
Предметно-функциональные константы – fn,gn,hn,… (n – местность функтора)
Предметные переменные – x, y, z,...
Логические символы
Пропозициональные связки – выражают логические функции
&– конъюнкция, – дизъюнкция, – отрицание, – импликация
Кванторы – выражают количественные соотношения
– общности, – существования
Технические символы – ( ) ,
2)Правила образования
Термы – аналог имен
Всякая предметная переменная является термом
Всякая предметная константа является термом
Если fn – n-местная предметная константа, а t1,t2,…,tn – термы,
то fn(t1,t2,…,tn) – терм
Ни что иное не является термом
Формулы – аналог предложений
Если Pn– n-местная предикаторная константа, а t1,t2,…,tn – термы,
то Pn (t1,t2,…,tn) – формула
Если А – формула, то А – тоже формула
Если А и В формулы, то
(А В) – формула, (А В) – формула, (А&В) – формула
Если А – формула, а х – предметная переменная, то
хА - формула
хА - формула
Ни что иное не является формулой
Понятия:
1. Вхождение α в формулу А.
xP(x,y,x) – 3 вхождения переменной хв формулу, одно вхождение переменной у
2. Область действия квантора.
αA, αA – А находится в области действия квантора
3. Связанное/свободное вхождение.
Вхождение α называется связанным, если и только если это вхождение α непосредственно следует за квантором или находится в области действия квантора по переменной α.
Вхождение α называется свободным, если и только если это вхождение не следует за квантором и не находится в области действия никакого квантора по переменной α.
4. Свободная/связанная переменная
Переменная свободна в формуле А, если и только если существует свободное вхождение α в А.
Переменная связана в формуле А, если и только если существует связанное вхождение α в А.
Пример: x( yP(x,y,z) R(x,y,z) )
х- связанная, y- связанная и свободная, z- свободная
5. Правильная подстановка терма. А (α /t)
Подстановка терма t в формулу А называется правильной если и только если:
Замещаются все свободные вхождения α в А.
Ни одно из замещаемых вхождений не находится в формуле А в
области действия какого-нибудь квантора по переменной входящей в терм t.
Замкнутый терм – не содержит переменных
Замкнутая формула – не содержит свободных переменных
Интерпретация нелогических символов:
U (универсум рассмотрения) – непустое множество предметов, которые могут обозначаться нелогическими символами. Интерпретация нелогических символов будет связываться (релятивизироваться) с выбранным универсумом. U=
Классы нелогических символов:
- константы (предметные, предикаторные, предметно-функциональные)
- предметные переменные (равны типу значений предметным константам)
I (интерпретационная функция) – функция приписывания значения константе с учетом выбранного U < U, I > -модель языка
Интерпретация констант:
Предметные константы – аналоги имен. Значение имени – отдельный предмет, взятый из U. Функция Iкаждой предметной константе сопоставляет элемент множества U
I: I (k) U
Предикаторные константы – аналоги предикаторов, которые в качестве значений имеют свойства или отношения, либо являются знаками множеств предметов, обладающих этими свойствами или кортежей предметов, находящихся в этих отношениях. Таким образом, значением предикаторной константы является некоторое подмножество U
I: I (Пn) Un
Предметно-функциональные константы – аналоги предметных функторов. Значения – предметно-предметные функции, определенные на множестве U
I: I(Фn) - функция вида Un → U.
Интерпретация предметных переменных:
Функция φ предметным переменным сопоставляет произвольные объекты множества U того же самого типа, что и константам.
I: φ (α) U
Выбрав U и I – задаем модель языка m = <U,I>, где
U – произвольное непустое множество
I – семантическая функция приписывающая значение константам языка.
Модель - возможная реализация языка.
Правила приписывания значений термам:
Значения термов – некоторые элементы из универсума.
Три типа термов:
α – предметные переменные
k – предметные константы
Фn (t1,t2,…,tn) – сложные функциональные термы
Значение терма t в модели m при приписывании значений φ:
Краткая запись- |t|mφ или просто |t|φ
Для предметных переменных
| α | φ = φ (α)
Для предметных констант
| k | φ = I (k)
Для сложных термов
| Фn (t1,t2,…,tn) | φ = [ I(Ф)] ( | t1| φ,| t2| φ, ....| tn | φ)
4. Классическая логика предикатов: правила приписывания значений формулам, понятия общезначимой и выполнимой формул, определение основных логических отношений между формулами.
Значения, которые могут принимать формулы при интерпретации – истина (И) и ложь (Л)
Значения формул при интерпретации:
Атомарные формулы принимают значение Ив том случае, если элементы множества U, знаками которых являются термы t1,t2,…,tn, входящие в формулу, являются и элементами подмножества U, обозначенного предикатором Пn
| Пn (t1,t2,…,tn)| φ = И↔ <| t1| φ,| t2| φ, ....| tn | φ > I (Пn)
| Пn (t1,t2,…,tn)| φ = Л ↔ <| t1| φ,| t2| φ, ....| tn | φ > I (Пn )
Значение формулы Апротивоположно значению формулы А
| А| φ = И ↔ |А| φ = Л
| А| φ = Л ↔ |А| φ = И
Значение формулы А & В равно И в том случае, если значение обоих формул, входящих в конъюнкцию, равно И, и равно Л во всех остальных случаях
|А & В| φ = И ↔ |А| φ = И &˚ |В| φ =И
|А & В| φ = Л ↔ |А| φ = Л ˚ |В| φ =Л
Значение формулы А В равно И в том случае, если значение хоть одной из формул, входящих в нее, равно И
|А В|φ = И ↔ |А|φ = И ˚ |В|φ=И
|А В|φ = Л ↔ |А|φ = Л &˚ |В|φ=Л
Значение формулы А В равно И, если значение формулы антецедента равно Л или значение консеквентна равно И
|А В|φ = И ↔ |А|φ = Л ˚ |В|φ=И
|А В|φ= Л ↔ |А|φ = И &˚ |В|φ=Л
Значение формулы α А равно И, если значение ЛЮБОЙ функции ψ,отличающейся от φ не более, чем приписыванием значения переменной α,равноИ
| α А|φ = И ↔ ˚ψ (ψ=αφ ˚ |A|ψ = И) ψ=αφ – приписывание ψ значения
| α А|φ = Л ↔ ˚ψ (ψ=αφ &˚ |A|ψ = Л)отличного от φ не более, чем на α
Значение формулы Е α А, если значение ХОТЬ ОДНОЙ функции ψ,отличающейся от φ не более, чем приписыванием значения переменной α,равноИ
| α А|φ = И ↔ ˚ψ (ψ=αφ &˚ |A|ψ = И) ψ=αφ – приписывание ψ значения
| α А|φ = Л ↔ ˚ψ (ψ=αφ ˚ |A|ψ = Л)отличного от φ не более, чем на α
Виды формул:
Закон (общезначимая формула) – это формула, принимающая значение И во всех моделях и при любых приписываемых значениях предметным переменным
╞ A ≡Df ˚U ˚I ˚φ |A|φ<U,I>= И
Выполнимая формула – принимающая значение И в некоторых моделях и при некоторых приписываниях значений предметным переменным
Формула А выполнима ≡Df ˚U ˚I ˚φ |A|φ<U,I>= И
Невыполнимая формула – это формула, принимающая значение Л во всех моделях и при любых приписываемых значениях предметным переменным
Формула А невыполнима ≡Df ˚U ˚I ˚φ |A|φ<U,I>= Л
Опровержимая формула - принимающая значение Л в некоторых моделях и при некоторых приписываниях значений предметным переменным
Формула А опровержима ≡Df ˚U ˚I ˚φ |A|φ<U,I>= Л
Формула А значима (истинна) в модели <U,I> ≡Df ˚φ |A|φ<U,I> = И
Формула Аобщезначима на множестве U (U общезначима) ≡Df ˚I ˚φ |A|φ<U,I> = И
Логические отношения
Совместимость по истинности.
Формулы из Г совместимы по истинности в том случае, если существует такая модель и такое приписывание значений переменным, при котором каждая формула из Г примет значение И.
˚A (A Г ˚ ˚U ˚I ˚φ |A|φ = И )
Совместимость по ложности
Формулы из Г совместимы по ложности в том случае, если существует такая модель и такое приписывание значений переменным, при котором каждая формула из Г примет значение Л.
˚A (A Г ˚ ˚U ˚I ˚φ |A|φ = Л)
Логическое следование.
Имеется в том случае, если для всякой модели и для всякого приписывания значений переменным, при котором каждое значение из Г примет значение И, формула В тоже примет значение И.
Г ╞ B ↔ ˚U ˚I ˚φ ( ˚A (A Г ˚ |A|φ = И ) ˚ |В|φ = И)
Задачи, решаемые в логике предикатов перебором моделей
-обоснование выполнимости
- обоснование опровержимости
-соместимость по истинности и по ложности
Обосновать общезначимости, невыполнимость, несовместимость по И и Л или отношение логического следования невозможно.