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|φ = И ) ˚ |В|φ = И)

Задачи, решаемые в логике предикатов перебором моделей

-обоснование выполнимости

- обоснование опровержимости

-соместимость по истинности и по ложности

Обосновать общезначимости, невыполнимость, несовместимость по И и Л или отношение логического следования невозможно.

Наши рекомендации