Логика Предиктов Первого Порядка 1

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Свободные и связанные переменные

Пример Рассмотрим формулу

1	2	3
x	x	x
F = t(	) ^(8y)[s(	; y) ! (9x)(r( ; y) _t(y))]:

В формулу x входит три раза (вхождение под знаком квантора (9x) не учитывается).

Первое вхождение x свободно

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Свободные и связанные переменные

Пример Рассмотрим формулу

1	2	3
x	x	x
F = t(	) ^(8y)[s(	; y) ! (9x)(r( ; y) _t(y))]:

В формулу x входит три раза (вхождение под знаком квантора (9x) не учитывается).

Первое вхождение x свободно

Второе хотя и входит в область действия квантора (8y), но тоже свободно (квантор от y, à íå îò x)

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Свободные и связанные переменные

Пример Рассмотрим формулу

1	2	3
x	x	x
F = t(	) ^(8y)[s(	; y) ! (9x)(r( ; y) _t(y))]:

В формулу x входит три раза (вхождение под знаком квантора (9x) не учитывается).

Первое вхождение x свободно

Второе хотя и входит в область действия квантора (8y), но тоже свободно (квантор от y, à íå îò x)

Третье вхождение x является связанным

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Свободные и связанные переменные

Пример Рассмотрим формулу

1	2	3
x	x	x
F = t(	) ^(8y)[s(	; y) ! (9x)(r( ; y) _t(y))]:

В формулу x входит три раза (вхождение под знаком квантора (9x) не учитывается).

Первое вхождение x свободно

Второе хотя и входит в область действия квантора (8y), но тоже свободно (квантор от y, à íå îò x)

Третье вхождение x является связанным

Все вхождения y связанные

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус,

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус, что может доставить неудобства при преобразовании формулы

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус, что может доставить неудобства при преобразовании формулы

Однако нетрудно понять, что если переменную в кванторе обозначить другой буквой и заменить ее вхождения в области квантора на эту букву

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус, что может доставить неудобства при преобразовании формулы

Однако нетрудно понять, что если переменную в кванторе обозначить другой буквой и заменить ее вхождения в области квантора на эту букву , то формула не изменится

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус, что может доставить неудобства при преобразовании формулы

Однако нетрудно понять, что если переменную в кванторе обозначить другой буквой и заменить ее вхождения в области квантора на эту букву , то формула не изменится

Например, если в

F= t(x) ^(8y)[s(x; y) ! (9x)(r(x; y) _t(y))]: x â (9x) заменить на x1,

Расин О.В.	Логика предикатов первого порядка

Понятие предиката Новые операции над предикатами

Равносильность формул и законы логики первого порядка

Переименование связанных переменных

Связанные и свободные переменные имеют разный статус, что может доставить неудобства при преобразовании формулы

Однако нетрудно понять, что если переменную в кванторе обозначить другой буквой и заменить ее вхождения в области квантора на эту букву , то формула не изменится

Например, если в

F= t(x) ^(8y)[s(x; y) ! (9x)(r(x; y) _t(y))]: x â (9x) заменить на x1,

то получим формулу

F = t(x) ^(8y)[s(x; y) ! (9x1)(r(x1; y) _t(y))];

которая по сути имеет тот же смысл

Расин О.В.	Логика предикатов первого порядка