X (S(x) > y(P(y) & R (x,y)).

Классическая по принципам:

1. Двузначность. Каждая формула может принять ровно одно из двух значений – И или Л.

2. Экстенсиональность. Значение сложного выражения зависит только от значения входящих в него частей.

3. Постулат о непустоте предметной области.

Язык логики предикатов:

1)Алфавит

Нелогические символы

Предметные (индивидные) константы – a, b, c,…

Предикаторные константы – Pⁿ,Qⁿ,Rⁿ,… (n – местность предикатора)

Предметно-функциональные константы – fⁿ,gⁿ,hⁿ,… (n – местность функтора)

Предметные переменные – x, y, z,...

Логические символы

Пропозициональные связки – выражают логические функции

& – конъюнкция, – дизъюнкция, – отрицание, – импликация

Кванторы – выражают количественные соотношения

– общности, – существования

Технические символы – () ^,

2)Правила образования

Термы – аналог имен

Всякая предметная переменная является термом

Всякая предметная константа является термом

Если fⁿ – n -местная предметная константа, а t₁,t₂,…,t_n – термы,

то fⁿ(t₁,t₂,…,t_n) – терм

Ни что иное не является термом

Формулы – аналог предложений

Если Pⁿ – n-местная предикаторная константа, а t₁,t₂,…,t_n – термы,

то Pⁿ (t₁,t₂,…,t_n) – формула

Если А – формула, то А – тоже формула

Если А и В формулы, то

(А В) – формула, (А В) – формула, (А&В) – формула

Если А – формула, а х – предметная переменная, то

хА - формула

хА - формула

Ни что иное не является формулой

Понятия:

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 (Пⁿ) Uⁿ

Предметно-функциональные константы – аналоги предметных функторов. Значения – предметно-предметные функции, определенные на множестве U

I: I(Фⁿ) - функция вида Uⁿ → U.

Интерпретация предметных переменных:

Функция φ предметным переменным сопоставляет произвольные объекты множества U того же самого типа, что и константам.

I: φ (α) U

 

Выбрав U и I – задаем модель языка m = <U,I>, где

U – произвольное непустое множество

I – семантическая функция приписывающая значение константам языка.

Модель - возможная реализация языка.

 

Правила приписывания значений термам:

Значения термов – некоторые элементы из универсума.

Три типа термов:

α – предметные переменные

k – предметные константы

Фⁿ (t₁,t₂,…,t_n) – сложные функциональные термы

Значение терма t в модели m при приписывании значений φ:

Краткая запись- |t| _m ^φ или просто |t| ^φ

Для предметных переменных

| α | ^φ = φ (α)

Для предметных констант

| k | ^φ = I (k)

Для сложных термов

| Фⁿ (t₁,t₂,…,t_n) | ^φ = [ I(Ф)] (| t₁| ^φ,| t₂| ^φ,....| t_n | ^φ)

 

4. Классическая логика предикатов: правила приписывания значений формулам, понятия общезначимой и выполнимой формул, определение основных логических отношений между формулами.
Значения, которые могут принимать формулы при интерпретации – истина (И) и ложь (Л)

Значения формул при интерпретации:

Атомарные формулы принимают значение И в том случае, если элементы множества U, знаками которых являются термы t₁,t₂,…,t_n, входящие в формулу, являются и элементами подмножества U, обозначенного предикатором Пⁿ

| Пⁿ (t₁,t₂,…,t_n)| ^φ = И↔ <| t₁| ^φ,| t₂| ^φ,....| t_n | ^φ > I (Пⁿ)

| Пⁿ (t₁,t₂,…,t_n)| ^φ = Л ↔ <| t₁| ^φ,| t₂| ^φ,....| t_n | ^φ > I (Пⁿ)

Значение формулы А противоположно значению формулы А

| А| ^φ = И ↔ |А| ^φ = Л

| А| ^φ = Л ↔ |А| ^φ = И

Значение формулы А & В равно И в том случае, если значение обоих формул, входящих в конъюнкцию, равно И, и равно Л во всех остальных случаях

|А & В| ^φ = И ↔ |А| ^φ = И &˚ |В| ^φ =И

|А & В| ^φ = Л ↔ |А| ^φ = Л ˚ |В| ^φ =Л

Значение формулы А В равно И в том случае, если значение хоть одной из формул, входящих в нее, равно И

|А В|^φ = И ↔ |А|^φ = И ˚ |В|^φ=И

|А В|^φ = Л ↔ |А|^φ = Л &˚ |В|^φ=Л

Значение формулы А В равно И, если значение формулы антецедента равно Л или значение консеквентна равно И

|А В|^φ = И ↔ |А|^φ = Л ˚ |В|^φ=И

|А В| _φ = Л ↔ |А|^φ = И &˚ |В|^φ=Л

Значение формулы α А равно И, если значение ЛЮБОЙ функции ψ, отличающейся от φ не более, чем приписыванием значения переменной α, равно И

| α А|^φ = И ↔ ˚ψ (ψ= _α φ ˚ |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|^φ = И) ˚ |В|^φ = И)

 

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

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

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

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

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