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

формулам (семантика языка).

Чтобы определить интерпретацию для формулы логики предикатов следует задать:

n общую область определения D для всех предметных переменных, входящих в формулу;

n значения констант;

n истинностные значения предикатов, входящих в формулу;

n значения функций, входящих в формулу

При этом:

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

2) каждому n-местному функциональному символу ставится в соответствие отображение из Dⁿ в D (заметим, что Dⁿ=

3) каждому n-местному предикатному символу ставится в соответствие отображение Dⁿ в множество {И,Л}.

Для каждой интерпретации формулы из области D формула может получать истинностное значение И или Л согласно следующим правилам:

1. если заданы значения формул G и H, то истинностные значения формул ùG,() получаются по табл. 2 логики высказываний.

2. G получает значение И, если G получает значение И для каждого x из D; в противном случае она получает значение Л.

3. получает значение И, если g получает значение И хотя бы для одного x из D;в противном случае она получает значение Л.

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

Пример: Оценим формулы

а)

b)

c)

в следующей интерпретации I:

Л, И, И,

И, Л, И.

Для формулы а): если , то

ИИ = И;

если , то

ЛЛ = Л.

Так как в области D существует элемент, а именно , такой, что истинна, то а) истинна при интерпретации I.

Для формулы b):

если , то

ЛИЛ;

если x=2, то

ИЛЛ.

Т. к. в D не существует такого элемента, что истинна, что формула b),будет ложной при интерпретации I.

Для формулы c):

если , то Л. Следовательно, = Л для и для . Так как существует , а именно , такой, что ложно, то формула с) ложна при интерпретации I, т.е. эта формула опровергается интерпретацией I.

Определим ряд важнейших понятий для логики предикатов.

Непротиворечивая (выполнимая) формула - формула G выполнима (непротиворечива) тогда и только тогда, когда существует такая интерпретация I, что G имеет значение И в I. Если формула G есть И в интерпретации I, то I есть модель формулы G и I удовлетворяет G.

Противоречивая формула – когда не существует никакой интер-претации, которая удовлетворяет G.

Общезначимая формула – когда не существует никакой интер-претации I, которая не удовлетворяет G.

Логическое следствие – формула G есть логическое следствие формул тогда и только тогда, когда для каждой интерпретации I, если истинна в I, то G также истинна в I.

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

Дата добавления: 2014-01-04