1. Как превратить предикат «В городе N живёт более 2 миллионов человек» в логическое высказывание? Предложите несколько способов.
Ввести переменную, обозначающую численность населения города N, например, P(N), и записать: P(N) > 2. Использовать логическое утверждение, например, Q, означающее, что «число жителей города N больше 2 миллионов», и записать Q = истина. Сформулировать через предикат R(x), где x — численность жителей, и записать: R(x): x > 2, где x — численность населения города N.
2. Сравните логические высказывания ∀х∃уР(х, у) и ∃у∀хР(х, у), где Р(х, у) — предикат от х и у.
∀x∃yP(x, y) означает, что для каждого x найдётся хотя бы одно y, такое что предикат P(x, y) истинно. Это утверждение требует, чтобы для всех возможных значений x существовало значение y, при котором P(x, y) истинно.
∃y∀xP(x, y) означает, что существует хотя бы одно значение y, такое что для всех x предикат P(x, y) истинно. Здесь утверждается, что можно найти одно универсальное y, которое удовлетворяет предикату для всех x.
Разница в порядке кванторов: первый случай (∀x∃y) гарантирует существование y для каждого x, тогда как второй (∃y∀x) утверждает существование одного универсального y, подходящего для всех x. Эти высказывания в общем случае неэквивалентны.
3. Какие из этих выражений — предикаты, а какие — логические высказывания?
а) ∀хР(х, у); б) ∃уР(х, у);
в) ∀x∃yP(x, у); г) ∃y∀xP(x, у).
а) ∀xP(x, y) — предикат, так как содержит свободную переменную y. б) ∃yP(x, y) — предикат, так как содержит свободную переменную x. в) ∀x∃yP(x, y) — логическое высказывание, так как не содержит свободных переменных (все переменные связаны кванторами). г) ∃y∀xP(x, y) — логическое высказывание, так как не содержит свободных переменных (все переменные связаны кванторами)