Найти преденексную нормальную форму (ПНФ) для данной логической формулы

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

Раздел: Преденексная нормальная форма (ПНФ)

Нам нужно найти преденексную нормальную форму (ПНФ) для данной логической формулы:

 \neg (\forall x P(x, y) \Rightarrow (\forall y \exists z Q(y, z) \Rightarrow \neg \forall z R(y, z))) 

Шаг 1: Раскроем импликации

Используем эквивалентность импликации:
 A \Rightarrow B \equiv \neg A \vee B 

Применяем к первой импликации:  \forall x P(x, y) \Rightarrow (\forall y \exists z Q(y, z) \Rightarrow \neg \forall z R(y, z))  Эквивалентно:  \neg \forall x P(x, y) \vee (\neg (\forall y \exists z Q(y, z)) \vee \neg \forall z R(y, z)) 

Теперь применим эквивалентность к \forall x P(x, y):  \neg \forall x P(x, y) \equiv \exists x \neg P(x, y) 

Аналогично:  \neg (\forall y \exists z Q(y, z)) \equiv \exists y \forall z \neg Q(y, z) 

И:  \neg \forall z R(y, z) \equiv \exists z \neg R(y, z) 

Шаг 2: Подставляем преобразования

Формула теперь принимает вид:  \exists x \neg P(x, y) \vee (\exists y \forall z \neg Q(y, z) \vee \exists z \neg R(y, z)) 

Шаг 3: Приведение к ПНФ

В преденексной нормальной форме (ПНФ) все кванторы должны быть вынесены в начало. У нас есть три квантора:
 \exists x, \exists y, \forall z, \exists z 

Перепишем формулу, вынеся кванторы:  \exists x \exists y \forall z \exists w (\neg P(x, y) \vee \neg Q(y, z) \vee \neg R(y, w)) 

Ответ:

Преденексная нормальная форма (ПНФ) данной формулы:  \exists x \exists y \forall z \exists w (\neg P(x, y) \vee \neg Q(y, z) \vee \neg R(y, w))