Упражнения

26. Какие из следующих формул являются общезначимыми (логическими законами):

1. $x(P(x)É"yP(y))

2. "x (P (x) Ú Q (x)) ≡ ("x P (x) Ú "x Q (x))

3. "x (P (x) & Q (x)) ≡ ("x P (x) & "x Q (x))

4. $x (P (x) Ú Q (x)) ≡ ($x P (x) Ú $x Q (x))

5. $x (P (x) & Q (x)) ≡ ($x P (x) & $x Q (x))

6. R(a,c)&R(a,c)

7. R(a,c,a)R(a,c,a)

Ответы

Гл.4 Упр.3

1) Неосмысленная запись: ни терм, ни формула. Раз нет предикатных знаков, значит это либо терм, либо неправильная (неосмысленная) запись. Две переменные, записанные подряд не являются осмысленной записью.

2) Неосмысленная запись: ни терм, ни формула. Раз нет предикатных знаков, значит это либо терм, либо неправильная (неосмысленная) запись. Две переменные, записанные через запятую и взятые в скобки, не являются термом.

3) Неосмысленная запись: ни терм, ни формула. Раз в состав записи входит предикатный символ, то она является либо формулой, либо неправильно построена. Ошибка в данной записи: два терма (xиy) соединены пропозициональной связкой &, которая может связывать, согласно определениям терма и формулы, только формулы.

4) Неосмысленная запись: ни терм, ни формула. Ошибка: нельзя отрицать термы (индивидная константа а – терм).

5) Терм.

6) Формула. Ее нагруженное дерево:

Гл.4 Упр.5(г)

Область действия квантора "x(подчеркнута):

"x (P(x,y₁)yQ(y,x))  "z(R(x,y)R₁(y, x))

Область действия квантора у (подчеркнута):

"x(P(x,y₁)yQ(y,x))"z(R(x,y)R₁(y, x))

Область действия квантора "z(подчеркнута):

"x(P(x,y₁)yQ(y,x))"z(R(x,y)R₁(y, x))

Гл.4 Упр.6

Свободные вхождения выделены жирным шрифтом и подчеркнуты, остальные вхождения переменных – связанные.

д."x(P(x,y)Q(y,x))"z(R(x,y)R₁(y,x))

е. x(P(x)Q(y))

ж. свободных вхождений переменных нет

Гл.4 Упр.7(j)Не предложение, формула содержит свободные вхождения переменных (они подчеркнуты):

zx(R²(x,z)Q²(x,x))Q³(x,z,z)

Гл.4 Упр.8

(1)вариант з)

(2)вариант в)

(3)вариант д)

(4)вариант д)

(5)вариант в)

(6) вариант б)

(7)вариант з)

Чтение некоторых неправильных вариантов:

если Р(х) – быть ребенком, а Q(x) – любить мороженое, тогда вариант а)"xP(x)É"xQ(x) прочитываетсяЕсли все дети, то все любят мороженое;

вариант б) содержит свободное вхождение переменной - у: "x(P(x)ÉQ(y)), - и поэтому не задает структуру предложения (а задает структуру одноместного предиката);

в) "x (P(x)Q (y)) –Все являются детьми и любят мороженое;

г) $x(P(x)Q(х)) –Существует ребенок, который любит мороженое;

д) "xP(x)Q(х) – второе вхождение переменной х свободное.

и) "xP(x)"xQ(x) –Все дети и все любят мороженое.

(8)Утверждение предполагает, что все рукописи не горят, поэтому правильный вариант б).

(9)варианты б) и г).

(10)вариант в).

Вариант б) "x((P(x)Q(x)R(x))S(x)) прочитывается: все являются политиками, а также честолюбивыми, неискренними и недальновидными людьми.

(11)вариант а)

Предложение (11) не содержит кванторных слов, поэтому все варианты, содержащие кванторы, не соответствуют его структуре.

(12)вариант а).

Гл.4 Упр.10

1. х(P(х)Q(x))

2. х(Q(x) &y(R(x,y)Р(у)));

можно также хy(Q(x) & (R(x,y)Р(у)))

3. х(Q(x)Р(х))

4. х(S(х)R(a,x));

или так (учитывая, что Джонс - судья): х(S(х)(R(a,x)Р(а))

5. х(Q(x) &R(x,а))х(S(x) &R(x,а)); или так (включая информацию, что объект а из класса Р):

х(Q(x)&R(x,а)Р(а))х(S(x)&R(x,а)Р(а))

6. ху((Q(x) &R(x,y))Q(у)); или так:х (Q(x)у(R(x,y)Q(у)))

7. ху((Q(x) &R(у,х))Q(у)); или так:х (Q(x)у(R(у,х)Q(у)))

Гл.5 Упр.20

(5)Q(a)&Q(c)Q(b)

Данная структура говорит, что некоторые фиксированные объекты а и с обладают свойством Q, а объектbэтим свойством не обладает.

Модель для формулы (5)(одна из возможных):

I:

U = N

|Q¹|_I – четное число (из записи формулы следует, что предикатQ- одноместный)

|a |_I - 2

|b|_I - 5

|c|_I - 4

В данной интерпретации рассматриваемая структура прочитывается: 2 и 4 – четные числа, а 5 – нет.

Имеем: |Q(a)|_I=и, |Q(c)|_I= и, |Q(b)|_I= л.

Тогда |Q(b)|_I=и (отрицание меняет значение высказывания на противоположное).

Конъюнктивное высказывание истинно, е.т.е. оба конъюнкта истинны. Последовательно вычисляя значение конъюнкций (неважно, в каком порядке: конъюнкция ассоциативна), получаем |Q(a)&Q(c)  Q(b)|_I=и.

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

I₁:

U = N

|Q¹|_I1 – четное число

|a |_I1 - 1

|b|_I1 - 5

|c|_I1 - 4

В данной интерпретации рассматриваемая структура прочитывается: 1 – четное число, и 4 – четное, а 5 – нет. Имеем три высказывания, соединенных конъюнкцией. Первое из высказываний ложно, значит, по определению конъюнкции ложно и все высказывание в целом.

I₂:

U = N

|Q¹|_I2 – нечетное число

|a |_I2 - 2

|b|_I2 - 5

|c|_I2 - 4

В данной интерпретации рассматриваемая структура прочитывается: 1 – нечетное число, и 4 – нечетное, а 5 – нет. Имеем три высказывания, соединенных конъюнкцией. Каждое из этих высказываний ложно, значит, по определению конъюнкции ложно и все высказывание в целом.

(7) P(b, а)P(a,b)

Данная формула прочитывается: объект а находятся в отношении Р с объектом bв том и только в том случае, если объектbнаходится в этом отношении с объектом а.

Примеры моделей данной формулы

Эквиваленция истинна в двух случаях (табличное определение ): (1) обе части эквиваленции истинны; (2) обе части ложны. Построим модели, соответствующие каждому из этих вариантов.

I₁:

U = {Аристотель, Платон}

|Р²|_I1 – быть лично знакомым (из записи формулы следует, что предикат Р - двухместный)

|a |_I1 - Аристотель

|b|_I1 - Платон

В данной интерпретации и левая часть эквиваленции истинна (Платон современник Аристотеля), и правая (Аристотель современник Платона), и, значит, все высказывание истинно.

I₂:

U = {Аристотель, Гоголь}

|Р|_I2 – быть лично знакомым

|a |_I2 - Аристотель

|b|_I2 - Гоголь

В данной интерпретации и левая, и правая части эквиваленции ложны, и, в соответствии с определением условий истинности этой связки, все высказывание истинно.

Пример контрмодели для формулы (7)

I:

U = {Аристотель, Платон}

|Р|_I – быть учеником кого-либо

|a |_I - Аристотель

|b|_I - Платон

Имеем: |P(b, а)|_I= л (Платон не ученик Аристотеля), |P(a,b)|_I=и. Раз левая и правая части эквиваленции оценены по-разному, вся эквиваленция ложна (по определению этой связки), поэтому наша интерпретацияI– контрмодель для формулы (7).

(9) $x(S(x) & (P(а,x)P(b,x)))

Структура прочитывается: существует такой объект, который обладает свойством Sи объект а не находится с ним в отношении Р или объектb.

При задании интерпретации (хоть модели, хоть контрмодели) некоторой формулы, необходимо установить значения всех нелогических констант, входящих в ее состав (и только их). В нашей формулы нелогические константы – это символы S¹(из записиS(x) следует, что предикатS- одноместный),P², а,b.

Для того, чтобы построить модель для формулы вида $хА, надо на некотором множестве объектов найти такой, который превращает условие после квантора – А - в истинное. В нашем случае надо на некотором множествеUтак проинтерпретировать символыS¹,P², а иb, чтобы вUнашелся объект х, для которого верно (S(x) & (P(а,x)P(b,x)). Раз найдется, значит верно будет ввести квантор существования -$х. Рассмотрим, в каком случае для некоторого х верно условие в скобках

Поскольку формула утверждает, что существует объект, удовлетворяющий условию (S(x) & (P(а,x)P(b,x)), то нужно найти интерпретациюIсимволовS¹,P², а,bи такую функцию оценки(такое понимание) х, что |S(x) & (P(а,x)P(b,x)|^_I= и. В последней формуле главный знак –. Конъюнктивная формула истинна, е.т.е. оба конъюнкта истинны, т.е. в искомой моделиI|S(x)|^_I=и, |P(а,x)P(b,x)|^_I= и. ФормулаP(а,x)P(b,x) – составная (содержит логические символы), для дизъюнктивной формулы имеем: она истинна, е.т.е. хотя бы один из дизъюнктов истинен: |P(а,x)P(b,x)|^_I= и, е.т.е. |P(а,x)|^_I=и или |P(b,x)|^_I= и. Отрицание формулы истинно, если сама формула (при заданныхIи) ложна, поэтому |P(а,x)|^_I=и, е.т.е. |P(а,x)|^_I= л, |P(b,x)|^_I= и, е.т.е. |P(b,x)|^_I= л.

Таким образом, надо найти такое множество Uи такие значения значенияS¹,P², а иbна нем, что хотя бы для одного объекта изUбудет верно:

(1) |S(x)|^_I=ии

(2) |P(а,x)|^_I=л или |P(b,x)|^_I=л

Примером интерпретации, для которой выполнены эти условия, будет, например, такая.

Модель для формулы (9)

I:

U = {x| х родившихся до н.э.} (множество всех людей, родившихся до н.э.)

|S¹|_I – быть философом

|Р²|_I – родиться раньше

|a |_I - Сократ

|b|_I - Платон

В данной интерпретации структуре 9 соответствует предложение Есть человек, живший до н.э., который является философом и Сократ и Платон родились раньше его. В нашемUмы найдем такое значение х, при котором структураS(x) & (P(а,x)P(b,x)) будет истинна. Например, если(х)=Аристотель. Значит, утверждение о существовании -$x(S(x)&(P(а,x)P(b,x))) - в этой интерпретации верно.

Пример контрмодели для формулы (9)

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

I:

U = множество всех городов-миллионеров

|S¹|_I – быть расположенным в Антарктиде

|Р²|_I – быть построенным раньше

|a |_I – Москва

|b|_I – Нью-Йорк

В данной интерпретации для структуры 9 получаем предложение: Существует город-миллионер, расположенный в Антарктиде такой, что Москва была построена не раньше его или Нью-Йорк не раньше.

(10) "x"y(R(x, y)R(y, x))

Модель для формулы (10)

I:U = множество всех людей (когда-либо живших)

|R²|_I – современник

Контрмодель для формулы (10)

I:U = N

|R²|_I – «  »

1Граф набран Т.В.Сальниковой; задание, взятое из книги Р.Столл «Множества. Логика. Аксиоматические теории» М., 1968, помечено [Ст], а из учебника Н.Н.Непейводы «Прикладная логика» - [Н].

2Выражения с постоянным значением бессмысленно квантифицировать (ставить перед ними кванторные слова:все,любой,некоторый,существует, есть, какой-нибудьи т.д.). Ср., например, выражениядля любой РФ верно, что… илиесть такие Соединенные Штаты Америки, в которых… Очевидно, что употребление словлюбойиестьв этих фразах бессмысленно.

3Считайте, что это глубокомысленное предложение утверждает, что все орлы и мухи такие. Правильный вариант – из предложенных – предполагает это

4В данном случае совершенно не важно какую переменную использовать, поэтому, например, следующие формулы также очевидно правильно воспроизводят структуру разбираемого предложения:∃х₁(P(x₁)&Q(x₁)),∃y(P(y)&Q(y)),∃z(P(z)&Q(z)) (все эти формулы логически эквивалентны).

5Вместо одноместного предиката «знать английский» можно также рассмотреть двухместный предикат «знать какой-либо язык», идя по этому пути, мы подробнее выявим структуру предложения.

6Если рассматривать двухместный предикат «знать какой-либо язык», тогда исходному предложению соответствует такая формула: ∃х(P(x)&Q(x,а))&∃х(P(x)&¬Q(x,а)), где константе «а», естественно, сопоставлено значение «английский язык».

7По поводу «обычно»: является ли, например, словосочетаниедревние люди, которые были современниками мамонтов осмысленным? грамотным?

8Разумеется, предикатиметь пломбынельзя рассматривать как отрицание предикатабеззубый, так же какносить парикне есть отрицание предикатабыть лысым (к вопросу о символизации).

9Кстати, справедливо для многих студентов, пытающихся что-то произносить на зачете по логике (вообще-то, не только по логике, и не только на зачетах, да и не только для студентов).

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