- •2. Сочетания, размещения, перестановки, булеаны.
- •3. Понятие атрибута, кортежа и схемы отношения. Представление атрибутов, кортежей и схем отношений на языке семантических сетей.
- •5. Бинарные отношения, свойства бинарных отношений и их представление на языке семантических сетей.
- •6. Соответствия и их типология. Представление соответствий на языке семантических сетей.
- •11. Отношение гомоморфизма на алгебраических системах. Представление отношения гомоморфизма на языке семантических сетей.
- •12. Отношение изоморфизма и автоморфизм алгебраических систем. Представление отношения изоморфизма и автоморфизма на языке семантических сетей.
- •13. Понятие реляционной структуры. Типология элементов реляционной структуры. Представление реляционных структур на языке семантических сетей.
- •15. Понятие формального языка. Типология формальных языков. Графовые формальные языки.
- •16. Алфавит и синтаксис формального фактографического языка семантических сетей.
- •17 .Понятие логического формального языка. Примеры логических формальных языков
- •18 Логические операции. Понятие высказывания. Типология высказываний.
- •20 Понятие совершенной конъюнктивной нормальной формы и совершенной дизъюнктивной нормальной формы. Способы построения.
- •24. Язык исчисления предикатов.
- •26. Алфавит, синтаксис и ключевые узлы графового логического языка.
- •27. Понятие формальной модели обработки информации. Понятие абстрактной машины. Машина Тьюринга.
- •28. Абстрактные машины логического вывода.
- •29. Типология и представление целей в машинах логического вывода.
- •30.Средства описания динамических предметных областей.
24. Язык исчисления предикатов.
Предикаты. Предикатомназывается функция, где М — произвольное множество, а В —двоичное множество.Иначе говоря, n-местный предикат, определенный на М, — это двузначная функция от п аргументов, принимающих значения в произвольном множестве М. М называется предметной областью предиката, а .— предметными переменными.
Для любых М и п существует взаимно однозначное соответствие между n-местными отношениями и n-местными предикатами на М:
а) каждому n-местному отношению R соответствует предикат Р, такой, чтоесли и только если;
б) всякий предикат определяет отношение R, такое, что,если и только если.
При этом R задает область истинности предиката Р.
Выражение(и другие, более сложные выражения логики предикатов), где , будем понимать как высказывание или в соответствии с логической интерпретацией как «истинно», а выражение, где— переменные, как переменное высказывание, истинность которого определяется подстановкой элементов М вместо. При этом— это логическая (двоичная) переменная, — нелогические переменные. Поскольку предикаты принимают два значения и интерпретируются как высказывания, из них можно образовывать выражения логики высказываний, т. е. формулы вида .
Кванторы. Пусть — предикат, определенный на М. Высказывание «для всех х изистинно» обозначается (множество М не входит в обозначение и должно быть ясно из контекста). Знак называетсяквантором общности; другое его обозначение (х). Высказывание «существует такой х из М, чтоистинно» обозначается . Знак называетсяквантором существования; другое его обозначение. Переход от к или кназывается связыванием переменной х, а также навешиванием квантора на переменную х (или на предикат Р), иногда — квантификацией переменной х. Переменная, на которую навешен квантор, называется связанной; несвязанная переменная называется свободной.
Выражение, на которое навешивается квантор или, называется областью действия квантора; все вхождения переменной х в это выражение являются связанными.
Истинные формулы и эквивалентные соотношения. При логической (истинностной) интерпретации формул логики предикатов возможны три основные ситуации.
1. Если в области М для формулы F существует такая подстановка констант вместо всех переменных, что F становится истинным высказыванием, то формула F называется выполнимой в области М. Если существует область M, где F выполнима, то F называется просто выполнимой. 2. Если формула F выполнима в М при любых подстановках констант, то она называется тождественно истинной в М. Формула, тождественно истинная в любых М, называется тождественно истинной или общезначимой.
3. Если формула F невыполнима в М, она называется тождественно ложной в М. Если F невыполнима ни в каких М, она называется тождественно ложной, или противоречивой.
Формулы называются эквивалентными, если при любых подстановках констант они принимают одинаковые значения.
Множество истинных формул логики предикатов:
Представление формальных теорий на языке семантических сетей.
Вопросы 21 и 26