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

Условие:

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

Решение:

Предмет: Математическая логика. Раздел: Логика предикатов. Задание: Привести формулу логики предикатов к предварённой нормальной форме (ПНФ). Для начала давайте уточним, что формула логики предикатов приведена к предварённой нормальной форме (ПНФ), если все кванторы вынесены максимально наружу, сохраняя порядок их следования. Дана формула: \[ \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) \]