Логические выражения и нормальные формы

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

Раздел: Логические выражения и нормальные формы

Решение задания №1

Формула:  f = -\left( (\bar{x} \land y \Leftrightarrow \bar{y}) \Rightarrow (x \lor y) \right) 

Шаг 1: Раскрытие эквивалентности

Эквивалентность можно заменить эквивалентным выражением:
 a \Leftrightarrow b = (a \lor \bar{b}) \land (\bar{a} \lor b) 

Применяем к  (\bar{x} \land y \Leftrightarrow \bar{y}) :

 (\bar{x} \land y \Leftrightarrow \bar{y}) = ((\bar{x} \land y) \lor y) \land (\bar{(\bar{x} \land y)} \lor \bar{y}) 

Упрощаем:

 (\bar{x} \land y \lor y) \land ((x \lor \bar{y}) \lor \bar{y}) 

 (y \lor \bar{x}) \land (x \lor \bar{y} \lor \bar{y}) 

 (y \lor \bar{x}) \land (x \lor \bar{y}) 

Шаг 2: Подстановка в исходное выражение

 f = -\left( ((y \lor \bar{x}) \land (x \lor \bar{y})) \Rightarrow (x \lor y) \right) 

Импликация заменяется по правилу  A \Rightarrow B = \bar{A} \lor B :

 f = -\left( \bar{((y \lor \bar{x}) \land (x \lor \bar{y}))} \lor (x \lor y) \right) 

Применяем закон де Моргана:

 f = -\left( (\bar{(y \lor \bar{x})} \lor \bar{(x \lor \bar{y})}) \lor (x \lor y) \right) 

 f = -\left( ((\bar{y} \land x) \lor (\bar{x} \land y)) \lor (x \lor y) \right) 

Шаг 3: Упрощение

Так как  (x \lor y)  уже присутствует, вся скобка становится истинной, а отрицание даёт ложь:
 f = 0 

Следовательно, СКНФ и СДНФ не существуют, так как функция тождественно равна 0.

Решение задания №2

Формула:
 (\neg \exists y P(x, y) \Rightarrow \neg \forall x \forall y Q(x, y)) \Rightarrow R(x) 

Шаг 1: Преобразование к отрицаниям

Используем правило:
 \neg \exists y P(x, y) = \forall y \neg P(x, y) 
 \neg \forall x \forall y Q(x, y) = \exists x \exists y \neg Q(x, y) 

Подставляем:
 (\forall y \neg P(x, y) \Rightarrow \exists x \exists y \neg Q(x, y)) \Rightarrow R(x) 

Шаг 2: Преобразование импликации

 A \Rightarrow B = \neg A \lor B 

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

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

Шаг 3: Упрощение

Используем закон де Моргана:
 (\forall y \neg P(x, y) \land \forall x \forall y Q(x, y)) \lor R(x) 

Это и есть пренексная нормальная форма (ПНФ).