Дискретная математика: привести предикат в приведённую форму
привести предикат в приведённую форму
(∃x ∀y P(y, z, t) | R(x, y, z)) ∨ ∃y T(x, y, t)
привести предикат в приведённую нормальную форму
(∀x ∀y T(x, y, t) ↓ ∃x P(x, y)) | R(x, y, z)

Предыдущий
вопрос Следующий
вопрос

Для приведения предикатов к приведённой нормальной форме (ПНФ) мы будем использовать правила логики предикатов и свойства кванторов.

Первый предикат: [
(∃x ∀y P(y, z, t) \lor R(x, y, z)) \lor ∃y T(x, y, t)
]

Для приведения данной формулы в приведённую форму воспользуемся следующими шагами:

Объединим кванторы. Перепишем, как:
[
∃x (∀y P(y, z, t) \lor R(x, y, z)) \lor ∃y T(x, y, t)
]Применим стандартные правила вывода и обработки
[
∃x ∃y (∀y P(y, z, t) \lor R(x, y, z) \lor T(x, y, t))
]Выразим через все кванторы, если это возможно.

Получаем:
[
∃x ∀y (P(y, z, t) \lor R(x, y, z) \lor T(x, y, t))
]

Это предикат в приведённой нормальной форме.

Второй предикат: [
(∀x ∀y T(x, y, t) \downarrow ∃x P(x, y)) \lor R(x, y, z)
]

Для этого предиката начнем с преобразования. Поскольку "↓" обозначает "не" (логическое отрицание), мы можем переписать формулу:
[
\neg (∀x ∀y T(x, y, t) \lor ∃x P(x, y)) \lor R(x, y, z)
]

Затем применим закон де Моргана:
[
(\neg ∀x ∀y T(x, y, t) \land \neg ∃x P(x, y)) \lor R(x, y, z)
]
Теперь преобразуем кванторы:
[
(∃x ∃y \neg T(x, y, t) \land ∀x \neg P(x, y)) \lor R(x, y, z)
]

Тем самым мы можем привести к:
[
∃x ∃y (¬T(x, y, t) \land ∀x ¬P(x, y)) \lor R(x, y, z)
]

В приведенной нормальной форме это будет:
[
∀x (P(x, y) \lor ¬T(x, y, t)) \lor R(x, y, z)
]

Эти преобразования обеспечивают, что предикаты находятся в удобной для логического вывода форме. Если нужно, можно проверить каждую логическую операцию на корректность, чтобы убедиться, что все преобразования были выполнены верно.