24. Язык исчисления предикатов.

Предикаты. Предикатомназывается функция, где М — произвольное множество, а В —двоичное множество.Иначе говоря, n-местный предикат, определенный на М, — это двузначная функция от п аргументов, принимающих значе­ния в произвольном множестве М. М называется предмет­ной областью предиката, а .— предметными пере­менными.

Для любых М и п существует взаимно однозначное со­ответствие между n-местными отношениями и n-местными предикатами на М:

а) каждому n-местному отношению R соответствует предикат Р, такой, чтоесли и только если;

б) всякий предикат определяет отношение R, такое, что,если и только если.

При этом R задает область истинности предиката Р.

Выражение(и другие, более сложные выражения логики предикатов), где , будем понимать как высказывание или в соответствии с логической интерпретацией как «истинно», а выражение, где— переменные, как переменное высказывание, истинность которого определяется подстановкой элементов М вместо. При этом— это логическая (двоичная) переменная, — нелогические переменные. Поскольку предика­ты принимают два значения и интерпретируются как высказывания, из них можно образовывать выражения логики высказываний, т. е. формулы вида .

Кванторы. Пусть — предикат, определенный на М. Высказывание «для всех х изистинно» обозначается (множество М не входит в обозначение и должно быть ясно из контекста). Знак называетсяквантором общности; другое его обозначение (х). Высказывание «су­ществует такой х из М, чтоистинно» обозначается . Знак называетсяквантором существования; другое его обозначение. Переход от к или кназывается связыванием переменной х, а также навешиванием квантора на переменную х (или на предикат Р), иногда — квантификацией переменной х. Пере­менная, на которую навешен квантор, называется связан­ной; несвязанная переменная называется свободной.

Выражение, на которое навешивается квантор или, называется областью действия квантора; все вхождения переменной х в это выра­жение являются связанными.

Истинные формулы и эквивалентные соотношения. При логической (истинностной) интерпретации формул логики предикатов возможны три основные ситуации.

1. Если в области М для формулы F существует такая подстановка констант вместо всех переменных, что F ста­новится истинным высказыванием, то формула F называ­ется выполнимой в области М. Если существует область M, где F выполнима, то F называется просто выполнимой. 2. Если формула F выполнима в М при любых подста­новках констант, то она называется тождественно истинной в М. Формула, тождественно истинная в любых М, называ­ется тождественно истинной или общезначимой.

3. Если формула F невыполнима в М, она называется тождественно ложной в М. Если F невыполнима ни в ка­ких М, она называется тождественно ложной, или противоречивой.

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

Множество истинных формул логики предикатов:

25. Представление формальных теорий на языке семантических сетей.

Вопросы 21 и 26