Задачи.

1. Доказать, что на одноэлементных множествах М кванто-ры $ и " совпадают.

2. Построить на множествах М с произвольными числами элементов примеры предикатов, для которых действие кванторов $ и " совпадает.

3. Построить на двухэлементном множестве М пример двухместного предиката, у которого действие кванторов $ и " не совпадает.

4. Перевести на язык формул следующие предложения , предварительно введя предметные множества и необхо-димые предикаты:

а) “ не все змеи ядовиты”,

б) “ можно обмануть кого-то, но нельзя обмануть всех”,

в) “некоторые остроумны только тогда, когда это не каса-ется их самих”,

г) “ ночью все кошки серы”,

д) “ любой, кто может плавать и летать - либо рыба либо птица”.

е) “ не существует самого большого простого числа”,

ж)“не каждое вещественное число является рациональным”,

з) “ любой четырехугольник является ромбом тогда и толь-ко тогда, когда длины его сторон равны”,

и) “ каждый ромб с четырьмя равными углами является квадратом”,

к) “ число х является простым, если оно делится нацело только на себя и на единицу”.

5. Представить в виде а) формулы ЛП, б) формулы ИВ пословицу “ У семерых нянек дитя без глазу”.

6. Выразить в виде формулы ЛП:

а) дистрибутивность сложения относительно умножения для вещественных чисел,

б) ассоциативность сложения для вещественных чисел,

в) коммутативность умножения целых чисел.

7. Пусть Р¹, Q², R³ - одно-, двух- и трехместные предикаты. Будут ли термами следующие выражения:

а) Р¹(х₀ ,а₁), б) Р¹(а₃), в) R³(х₁,а₁), г) R³(х₁, Р¹(х₀ ,а₁), Q²(х₁,а₁)), д) Q²(R³(х,х₁,Р¹(х₀ )),а₁,Q²(х₁, а₁ )), е) R³(Q²(х₀ , а₁),Q²(х₁ ,а₁ )).

8. Определить область истинности предикатов при х Î N, у Î N:

а) ”х-у = 10”, б) “ху = 16”, в) “х/у = 2”.

9. Будут ли формулами ЛП следующие выражения:

а) Ø"х Р(х,у), б) S(z)Ø А(х,у)® $хВ(х,у),

в) Ø А(х,у)& "х В(х,у), г) "х Р(х,у) ®" f Q(f(х),у).

10. Указать свободные и связанные переменные в форму-лах:

а) Ø Q(х)& "х В(х,у), б) $ хS(х,у) Ú "u А(z,u)® В(х,у),

в) Ø"х $ у А(х,у)& В(х,у), г) "х Р(х,у) ®"z Q(х,у,z,u),

д) $ х "у Р(х,у) & Ø R(х,у,z).

11. Привести пример высказывания, которое можно пред-ставить в виде формулы в ЛП, но нельзя – в алгебре логики.