Elementy_mat_logiki_Teoria

свободной в другой. В этом случае полагают, что переменная является и связанной, и свободной одновременно.

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

Пример.

( x)( z)Q(x, y, z) не является высказыванием, так как переменная y не связана никаким квантором.

Формулы имеют смысл только тогда, когда существует какая-либо интерпретация символов, входящих в эти формулы.

Определение.

Интерпретация формулы F логики предикатов состоит из элементов непустой предметной области D , значений всех констант, функциональных символов и предикатов, встречающихся в F . Указанные значения задаются следующим образом:

1.Каждой константе ставится в соответствие некоторый элемент из D .

2.Каждому n -местному функциональному символу ставится в соответствие

отображение из Dn	в D . Здесь Dn (x , x ,...,x ) , где		x , x		,...,x	n	D .
	1 2	n	1	2
3. Каждому n -местному предикату ставится в соответствие отображение из
Dn в {И, Л}.
Для каждой	интерпретации на	области	D	формула может получать

истинностное значение И или Л согласно следующим правилам:

1.Если заданы значения формул F и G , то истинностные значения формул

( F ), ( F G ), ( F G ),( F G ),( F ~ G ) получаются с помощью таблиц истинности соответствующих логических операций.

2.Формула ( x)F получает значение И, если F получает значение И для

каждого x из D , в противном случае она получает значение Л.
3.	Формула ( x)F получает значение И, если F получает значение И хотя
бы для одного x из D , в противном случае она получает значение Л.
4.	Формула,	содержащая свободные переменные, не	может получать
истинностные значения.
Пример.
Пусть задан		предикат P(x) x2 5. Формула xP(x)	не истинна, если

универсом (предметной областью) является множество целых чисел, однако она была бы истинной, если в качестве предметной области взять множество целых чисел, больших чем 2.

Квантифицированный предикат xP(x) , где P(x) : 3 x 5 , не является

истинным, если предметная область − множество целых чисел, потому что имеются значения x из этой области (например, x 4 ) такие, что P(x) ложно. Для

истинности xP(x) P(x) должно быть истинным для каждого значения x из

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

Пример.

Предикат xP(x) , где P(x) : x2 4 , является истинным, если предметной областью есть множество действительных чисел, т.к. x2 4 истинно для x 2

Предикат xP(x) , где P(x) : x2 5, также истинен, если предметной областью

есть множество действительных чисел, однако, он не является истинным, если предметная область есть множество целых чисел, т.к. не существует целого числа, квадрат которого равен 5.

При логической (истинностной) интерпретации формул логики предикатов так же, как и в логике высказываний определяются общезначимые,

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

Законы и тождества логики предикатов

Все законы и тождества, которые справедливы в логике высказываний, остаются справедливыми и в логике предикатов.

Для эквивалентных преобразований предикатных высказываний с кванторами дополнительно необходимо использовать приведенные ниже законы.

1. Замена связанной переменной: ( x)F(x) ( y)F( y) ;

( x)F(x) ( y)F( y) ,

F (x) − одноместный предикат.

Введение нового обозначения связанной переменной (т.е. переименование связанной переменной) не изменяет смысл формулы логики предикатов, если выполняется следующее условие: никакая свободная переменная в любой части формулы не должна после переименования оказаться связанной.

Пример.

Для нового обозначения связанной переменной следует выбирать букву, которая отсутствует в формуле, например, ( x)( y)P(x, y) ( x)( z)P(x, z) . Здесь

осуществлена операция переименования связанной переменной y .

2. Коммутативные свойства кванторов:

( x)( y)P(x, y) ( y)( x)P(x, y) ; ( x)( y)P(x, y) ( y)( x)P(x, y) .

Менять местами можно только одноименные кванторы.

( x)( y)P(x, y) ( y)( x)P(x, y) .

3. Дистрибутивные свойства кванторов

( x)F(x) G ( x)(F(x) G) ; ( x)F(x) G ( x)(F(x) G) ; ( x)F(x) G ( x)(F(x) G) ; ( x)F(x) G ( x)(F(x) G) ,

где G − формула логики предикатов, которая не содержит x ; ( x)F(x) ( x)H (x) ( x)(F(x) H (x)) ;

(x)F(x) (x)H (x) (x)(F(x) H (x)) .

Сформулированный дистрибутивный закон справедлив только для квантора всеобщности при конъюнкции и квантора существования при дизъюнкции

, т.к. другие комбинации приводят к неравенствам:

(x)F(x) (x)H (x) (x)(F(x) H (x)) ; (x)F(x) (x)H (x) (x)(F(x) H (x)) .

Для преодоления данного ограничения дистрибутивного закона, следует

использовать замену связанной переменной:

(x)F(x) (x)H (x) (x)F(x) (y)H ( y) (x)(y)(F(x) H ( y)) ; (x)F(x) (x)H (x) (x)F(x) (y)H ( y) (x)(y)(F(x) H ( y)) .

Таким образом, в общем случае дистрибутивные свойства кванторов можно записать следующей схемой:

(Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ; (Q1 x)F(x) (Q2 y)H ( y) (Q1 x)(Q2 y)(F(x) H ( y)) ,

где (Q1 x), (Q2 x) − любой из кванторов или .

4. Закон де Моргана для кванторов:

((x)F(x) (x) F(x) ; ((x)F(x) (x) F(x) .

Предваренные нормальные формы

Определение.

Формула F в логике первого порядка находится в предваренной нормальной

форме (ПНФ) тогда и только тогда, когда она может быть представлена в виде (Q1 x1 )...(Qn xn )(A) , где каждое (Qi xi ) , i 1,...,n , есть или (x) , или (x) , а A −

формула, не содержащая кванторов. Причем (Q1 x1 )...(Qn xn ) называется префиксом, а

A − матрицей формулы F .

Для преобразования выражений произвольной формы в ПНФ необходимо поочередно выполнить следующие этапы преобразования:

1. Исключить логические связки эквиваленции и импликации, выразив их

через операции дизъюнкции, конъюнкции и отрицания с помощью следующих законов: F G F G ; F ~ G (F G) (G F) .

2. Опустить знаки операций отрицания непосредственно на предикаты,

используя закон двойного отрицания (F) F		и законы де	Моргана
(F G) F G) ,	(F G) F G) , в том	числе для	кванторов:
((xF(x)) (x)(F(x)) ; ((xF(x)) (x)(F(x)) .

3.Если необходимо, переименовать связанные переменные.

4.Вынести кванторы в начало формулы, используя соответствующие законы, для получения предваренной нормальной формы

Пример.

Приведем формулу ( x)F(x) ( x)Q(x) к предваренной нормальной форме.

Сначала исключим импликацию, затем опустим знак операции отрицания непосредственно на предикат и вынесем квантор в начало:

( x)F(x) ( x)H (x) (( xF(x)) ( x)H (x) ( x)( F(x)) ( x)H (x)( x)( F(x) H (x)).

Выводимость в логике предикатов

Для дедуктивного вывода в логике предикатов можно использовать правила, которые применяются для подобных выводов в логике высказываний. Однако в логике предикатов для проведения дедуктивных умозаключений используются также и специфические правила, учитывающие наличие кванторных операций. К таким правилом относятся следующие правила:

а) Правило удаления квантора всеобщности xP(x)

P(c) для произвольного с D

используется для доказательства истинности P(с) , где c − произвольно выбранный элемент предметной области D , в которой справедливо xP(x) .

Пример.

Из посылки «Все студенты любят получать хорошие оценки» делаем вывод: «Студент Петров любит получать хорошие оценки».

б) Правило введения квантора всеобщности P(c) для произвольного с D

xP(x)

утверждает истинность xP(x) , если доказана истинность P(с) для любого c , то есть для всех элементов c из рассматриваемой предметной области D .

xP(x)

в) Правило удаления квантора существования P(c) для некоторого с D в

истинной формуле xP(x) заключается в указании имени элемента c (конкретного или гипотетического), для которого P(с) истинно.

г) Правило введения квантора существования P(c) для некоторого с D

xP(x)

позволяет заключить, что xP(x) является истинным, когда известен некоторый элемент c , для которого истинно P(с) .

Исчисление предикатов

В логике предикатов, в отличие от логики высказываний, нет эффективного способа для распознавания общезначимости формул. Поэтому аксиоматический метод становится существенным при изучении формул, содержащих кванторы.

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

Определение.

Исчисление предикатов − это аксиоматическая теория, символами которой являются:

1)символы предметных переменных: x1 , x2 ,...,xn ,...;

2) символы предикатов: P(t ) , P(t ) ,...,P(t ) ,..., где t 0,1, 2,...;
1 2	n

3)логические символы: , ;

4)символы кванторов: , ;

5)скобки и запятую: ),( .

Аксиомами исчисления предикатов являются следующие аксиомы:

а) A (B A) ;

б) (A (B C)) ((A B) (A C)) ;

в) ( B A) (( B A) B) ;

г) xP(x) P( y) ; д) P( y) xP(x) .

В исчислении предикатов используются следующие правила вывода:

1. Правило отделения, которое формулируется так же, как и в исчислении

высказываний: P, P Q ;

Q

2. Правило связывания квантором общности (правило обобщения, правило

	-введения)	P Q(x)	, где Q(x) содержит свободные вхождения	x , а P их не
		P Q(x)

содержит.

3. Правило связывания квантором существования (правило -введения)

Q(x) P , где Q(x) содержит свободные вхождения x , а P их не содержит.

Q(x) P

4. Правило переименования связанной переменной. Связанную переменную формулы P можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в P .

Пример.

Докажем правило переименования связанных переменных для квантора общности:

1.xF (x) (по условию).

2.xF(x) F( y) (аксиома а) ).

3.xF (x) yF( y) (правило обобщения).

4. yF ( y) .

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

Теорема (ослабленная теорема о дедукции)

Пусть G − множество формул, A, B − формулы и G, A B , и существует

вывод в исчислении предикатов, построенный с применением только правила отделения, то G A B .

Утверждение 1. Аксиомы исчисления предикатов − общезначимые формулы. Утверждение 2. формула, получающаяся из общезначимой формулы по

любому из правил 1 − 4, является общезначимой.