Привести формулу логики предикатов к предваренной нормальной форме

Предмет: Математическая логика.

Раздел: Логика предикатов.

Задание: Привести формулу логики предикатов к предварённой нормальной форме (ПНФ).

Для начала давайте уточним, что формула логики предикатов приведена к предварённой нормальной форме (ПНФ), если все кванторы вынесены максимально наружу, сохраняя порядок их следования. Дана формула: \[ \exists y F(x, y, z) \lor G(x, y) \supset \forall x H(z, x) \]

Шаг 1: Приведение импликации к эквивалентной форме.

Мы знаем, что \( A \supset B \) эквивалентно \( ¬A ∨ B \). То есть, \[ A \supset B \equiv ¬A ∨ B \] так что наша формула становится: \[ ¬(\exists y F(x, y, z) \lor G(x, y)) \lor \forall x H(z, x) \]

Шаг 2: Использование правил де Моргана для отрицания.

Мы выносим отрицание внутрь скобок: \[ \neg (\exists y F(x, y, z) \lor G(x, y)) \equiv (\neg \exists y F(x, y, z)) \land \neg G(x, y) \] Используя правила де Моргана и закон двойственного квантора, получаем: \[ \neg (\exists y F(x, y, z)) \equiv \forall y \neg F(x, y, z) \] Тогда формула становится: \[ (\forall y \neg F(x, y, z)) \land \neg G(x, y) \]

Шаг 3: Вынесение кванторов наружу.

Текущая формула: \[ (\forall y \neg F(x, y, z)) \land \neg G(x, y) \lor \forall x H(z, x) \]

Шаг 4: Упрощение логического выражения.

Формула уже представлена в предваренной нормальной форме (ПНФ), где все кванторы вынесены максимально наружу. Окончательная формула в ПНФ: \[ \forall y (\neg F(x, y, z)) \land \neg G(x, y) \lor \forall x H(z, x) \]