yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.2. Формализация- предложения естественного языка.

Математическая логика

4.2. Формализация- предложения естественного языка.

Пример. Рассмотрим область определения М =(люди) с заданными на ней предикатами-. J(x) - х судья; L(x) - х юрист; S(x) - х жулик; А(х,у) - x любит у-ка. Формализуем высказывания:

x(J(x) L{x))                                                    каждый судья - юрист x(L(x)&S(x))                                                       некоторые юристы - судьи,

x(S(x)& y(L(y) A(x,y)))                             некоторые жулики любят всех юристов

x(S(x)& y(A(x,y) L(y)))                             некоторые жулики любят только юристов

x(S(x)& y(L(y)&A(x,y)))                                 некоторые жулики любят некоторых юристов

x(S(x) y(J(y) ¬A(x,y)))                         все жулики не любят судей

4.3 Интерпретация  и выполнимость формул алгебры предикатов.

Определение 4.5. Под интерпретацией будем понимать непустую область D, называемую областью интерпретации, а также соответствие, ставящее каждой интерпретацией букве Р1n некоторое отношение на области D, каждой предметной постоянной а1 - некоторый элемент из области D, каждой функциональной букве f1m - некоторую операцию на области D.

При заданной интерпретации все предметные переменные пробегают все значения из области D, а логические связки имеют обычный логический смысл.

Пример: Формула xyP(f(x,y),a) является высказыванием. Предикат P(v,u) - двуместный, переменные х, у - связанные, а - предметная постоянная. Истинность или ложность этого высказывания можно узнать лишь при заданной интерпретации.

Зададим следующую интерпретацию. Область интерпретации D -множество действительных чисел R, константа а=1, функциональный символ f(х,у)=х22, предикат P(u,t): u=t. Тогда формула имеет вид: х22=1 и задает уравнение окружности. Она истинна, т. к. существуют такие x и у , что х2+ у2=1.

Интерпретация может быть частичной, например, x2+y2 =r, Тогда xy(x2+y2=r) - одноместный предикат, который определяет свойство точек на действительной плоскости принадлежать некоторой окружности, которая определяется радиусом r.

Определение 4.6. Формула называется выполнимой, если существует хотя бы одна интерпретация, из которой формула истинна.

Определение 4.7. Формула логически общезначима (ЛОЗ), если она истинна на любой интерпретации для любых значений переменных.

Определение 4.8. Формула, которая ложна на любой интерпретации при любых значениях переменных, называется противоречием.

Логически общезначимые формулы являются выделенными формулами алгебры предикатов.

Так как область определения предиката может быть бесконечной, то очевидно,, таблица истинности не может служить алгоритмом для определения логической общезначимости формул. Однако существуют другие способы, которые в частных случаях позволяют определить ЛОЗ формулы. Можно строить таблицы истинности формул алгебры предикатов для частичных интерпретаций на ограниченных областях. Например, возьмем область интерпретации, состоящую из двух произвольных элементов, которые условно обозначим цифрами: D=(1,2). Построим таблицу истинности формул: Е1= хР(х) и E2=xP(x). Одноместный предикат на области определения из двух элементов может принимать одно из четырех значений, которые определяются таблицами истинности (табл.4.1 ).

Таблица 4.1.

x

 

Р1(.)

 

Р2(.)

 

Р3(.)

 

 

Р4(.)

 

 

1

 

F

 

F

 

Т

 

Т

 

2

 

F

 

Т

 

F

 

Т

 

Формулы Е, и Е, будут принимать на этих интерпретациях следующие значения (табл. 4.2).

Таблица 4.2.

Р(.)

xP(x)

xP(x)

P1

F

F

P2

T

F

P3

T

F

P4

T

T

 

Построим таблицы истинности для следующих формул: E1= x(yP(y) Q(x)) и E2= yP(y)  xQ(x). Дли обеих формул существует 16   интерпретаций,   т.   к.   каждый   из   одноместных   предикатов   Р   и   Q, принимает   по  4   значения.  Истинностные   значения  Е1 и Е2 для   восьми интерпретаций приведенных в табл. 4.3.

Из таблицы видно, что формулы E1 и Е2 эквивалентны.

P(.)

Q(.)

E1

E2

P1

Q1

T

T

P1

Q2

T

T

P1

Q3

T

T

P1

Q4

T

T

P2

Q1

T

T

P2

Q2

T

T

P2

Q3

T

T

P2

Q4

T

T

 

 

 

25