Нормальна форма формули у логіці предикатів

Нормальна форма формули у логіці предикатів — це формула, яка містить лише операції кон'юнкції, диз'юнкції та кванторні операції, а операція заперечення відноситься до елементарних формул.

З допомогою рівностей алгебри висловлень й логіки предикатів кожну формулу логіки предикатів можна привести до нормальної формули.^[1]

Теорема про нормальну форму

Теорема: Кожна формула логіки предикатів має нормальну форму.

Доведення: Перш ніж доводити теорему, встановимо 4 равносильності, які необхідні нам надалі. В них передбачається, що формула Н не містить вільної змінної х:

$\forall x W (x) \lor H = \forall x (W (x) \lor H)$
$\exists x W (x) \lor H = \exists x (W (x) \lor H)$
$\forall x W (x) \land H = \forall x (W (x) \land H)$
$\exists x W (x) \land H = \exists x (W (x) \land H)$

Встановимо першу з цих рівносильностей. Решта - аналогічно.

Нехай $\forall x W (x) \lor H$ істинна для деякої області М. Тоді на М істинно чи $\forall x W (x)$ , чи $H$ . В першому випадку $W (x)$ тотожно істинний на М предикат і через те, що $H$ не містить х, $W (x) \lor H$ теж тотожно істинний на М предикат, і тоді $\forall x W (x) \lor H$ - істинно. У другому випадку, якщо істинно $H$ , то істинно і $W (x) \lor H$ незалежно від х, а значить $\forall x$ з М.

Нехай тепер $\forall x W (x) \lor H$ хибно. Тоді $\forall x W (x)$ і $H$ хибні. Тобто існує $x_{0} \in M$ , такий що $W (x_{0})$ хибно. Але тоді $W (x) \lor H$ хибно, бо $\forall x W (x) \lor H$ хибно.

Доведемо тепер теорему методом індукції. Для елементарних формул наше твердження істинне, бо вони самі є нормальними формами. Будь-яку формулу можна записати, використовуючи операції $\land, \lor, \neg,$ , тому достатньо показати, що якщо $W_{1}$ і $W_{2}$ мають нормальні форми, то і $\neg W_{1}$ , $W_{1} \land W_{2}$ , $W_{1} \lor W_{2}$ теж мають нормальні форми. Нехай $W_{1}$ і $W_{2}$ мають нормальні форми $\tilde{W_{1}}$ і $\tilde{W_{2}}$ , де

$\tilde{W_{1}} = \forall x_{1} . . . \forall x_{i} \exists x_{i + 1} . . . \exists x_{n} V_{1} (x_{1} . . . x_{n})$

$\tilde{W_{1}} = \exists y_{1} . . . \exists y_{i} \forall y_{i + 1} . . . y_{m} V_{2} (y_{1} . . . y_{m})$

Тоді формулі $W_{1} \lor W_{2}$ рівносильна формула $\tilde{W_{1}} \lor \tilde{W_{2}}$ , яка може завжди бути приведена до нормальної форми з використанням рівностей 1 – 2:

$\tilde{W_{1}} \lor \tilde{W_{2}} = \forall x_{1} [\forall x_{2} . . . \forall x_{i} \exists x_{i + 1} . . . \exists x_{n} V_{1} (x_{1} . . . x_{n}) \lor \exists y_{1} . . . \exists y_{i} \forall y_{i + 1} . . . y_{m} V_{2} (y_{1} . . . y_{m})] = \forall x_{1} . . . \forall x_{i} \exists x_{i + 1} . . . \exists x_{n} \exists y_{1} . . . \exists y_{i} \forall y_{i + 1} . . . y_{m} [V_{1} (x_{1} . . . x_{n}) \lor V_{2} (y_{1} . . . y_{m})]$

Таким чином, отримана нормальна форма формули $W_{1} \lor W_{2}$ . Аналогічно, з рівностей 3,4 отримаємо, що можна побудувати нормальну форму і для $W_{1} \land W_{2}$ . Нарешті, якщо відома нормальна форма $\tilde{W_{1}}$ формули $W_{1}$ , то нормальна форма $\overline{W_{1}}$ має вигляд:

$\overline{W_{1}} = \overline{\forall x_{1} . . . \forall x_{i} \exists x_{i + 1} . . . \exists x_{n} V_{1} (x_{1} . . . x_{n})} = \exists x_{1} . . . \exists x_{i} \forall x_{i + 1} . . . \forall x_{n} \overline{V_{1} (x_{1} . . . x_{n})}$

Таким чином встановлено, що будь-яка формула логіки предикатів має нормальну форму.

Алгоритм приведення формули до нормальної форми

Для приведення формули до нормальної форми потрібно виконати наступні операції:

виключити операції $\to$ , ~, якщо вони є;
зменшити область знаків заперечення;
перейменувати змінні так, щоб можна було винести квантори в початок формули.

Приклад

$\neg (\forall x P (x) \to \exists x Q (x)) = \neg (\neg (\forall x P (x)) \lor \exists x Q (x)) = \forall x P (x) \land \forall x \neg Q (x) = \forall x P (x) \land \forall y \neg Q (y) = \forall x \forall y P (x) \neg Q (y)$

Примітки

Шаблон:Примітки

Посилання

↑ Шаблон:Cite web

[1] Шаблон:Cite web

[1]

Нормальна форма формули у логіці предикатів

Зміст

Теорема про нормальну форму

Алгоритм приведення формули до нормальної форми

Приклад

Примітки

Посилання

Навігаційне меню

Нормальна форма формули у логіці предикатів

Теорема про нормальну форму

Алгоритм приведення формули до нормальної форми

Приклад

Примітки

Посилання

Навігаційне меню

Пошук