Методические указания к выполнению расчетно-графической работы по математической логике и теории алгоритмов

22 {А) все S суть Р - Vx(S(x) =^Р(х)); (Е) ни одно S не есть Р - Vx(S(x) 7Р(Х)); (Т) некоторые S суть Р - 3c(S(x)&P(x))-, (О) некоторые S не есть Р - 3c(S(x)& ]Р(х)). Выполнение задания № 6 требует, чтобы в первую очередь было выбрано (задано) множество - область интерпретации, а затем подобрать предикаты так, чтобы формула на выбранном множестве оказалась истинной. Задание № 7, как правило, не вызывает затруднений, важно только помнить, что прежде, чем выносить кванторы за скобки нужно, при необходимости, провести переименования переменных. Квантор из посылки выносится меняясь на двойственный, а из заключения - без изменений. Восьмое задание, фактически аналогично заданиям № 5 и № 4, см. указания по этим задачам. Сначала нужно записать посылки и заключение в виде формул логики предикатов. Для этого см. пояснение к задаче 5. Далее нужно доказать, что из записанных посылок логически следует заключение. Отметим следующее. Проблема дедукции логики предикатов состоит, как и в логике высказываний, в выяснении: будет ли формула В логическим следствием формул А2, ..., An. Для выяснения будет ли формула В логическим следствием формул А i, А2, ..., An проводится следующая последовательность действий А). Строим конъюнкцию С = А1&А2& ...& Ап.&1 В. Отметим, что требуемое следствие (заключение) взято с отрицанием. Б) Находим (сколемовскую) стандартную форму Cs для формулы С Положим, что форма С, = (QiXiQ2X2...QnXn)'Ci&C2&...&Cm, где =(QiXiQ2X2...QnXn) - префикс формулы без кванторов существования, а С],С2,... ,Ст - ДИЗЪЮНКТЫ, В которых ПО необходимости введены сколемовские функции.