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

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

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

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

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

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