Формальные логические выражения и их преобразования (нормальная форма)

Предмет: Математическая логика, раздел: Формальные логические выражения и их преобразования (нормальная форма)

Мы можем начать с того, что преобразуем данную формулу, используя логические законы и упрощения, чтобы привести её к совершенной конъюнктивной нормальной форме (СКНФ).

Формула:

\[((x \rightarrow y) \sim (y \rightarrow \overline{x})) \land z\]

Где:

• \(x \rightarrow y\) — импликация, эквивалентная \( \overline{x} \lor y\);
• \( \sim \) — эквивалентность;
• \( \overline{x} \) — отрицание \(x\);
• \(\land z\) — конъюнкция с \(z\).

Шаги:

1. Раскрытие импликаций:
   По определению импликации:

   \[ x \rightarrow y \equiv \overline{x} \lor y \]

   \[ y \rightarrow \overline{x} \equiv \overline{y} \lor \overline{x} \]

   Подставляем в исходное выражение:

   \[ ((\overline{x} \lor y) \sim (\overline{y} \lor \overline{x})) \land z \]

2. Раскрытие эквивалентности:
   Эквивалентность \(\sim\) можно заменить конъюнкцией двух импликаций:

   \[ A \sim B \equiv (A \rightarrow B) \land (B \rightarrow A) \]

   где \(A = \overline{x} \lor y\), \(B = \overline{y} \lor \overline{x}\). Раскроем конструкцию:

   \[ (\overline{x} \lor y) \sim (\overline{y} \lor \overline{x}) \equiv ((\overline{x} \lor y) \rightarrow (\overline{y} \lor \overline{x})) \land ((\overline{y} \lor \overline{x}) \rightarrow (\overline{x} \lor y)) \]

3. Раскрытие импликаций:
   Применяем правило импликации:

   \[ A \rightarrow B \equiv \overline{A} \lor B \]

   Для первой части:

   \[ (\overline{x} \lor y) \rightarrow (\overline{y} \lor \overline{x}) \equiv \overline{(\overline{x} \lor y)} \lor (\overline{y} \lor \overline{x}) \]

   Исправим первую часть выражения:

   \[ \overline{(\overline{x} \lor y)} \equiv \overline{\overline{x}} \land \overline{y} \equiv x \land \overline{y} \]

   Таким образом:

   \[ (x \land \overline{y}) \lor (\overline{y} \lor \overline{x}) \]

   Для второй импликации:

   \[ (\overline{y} \lor \overline{x}) \rightarrow (\overline{x} \lor y) \equiv \overline{(\overline{y} \lor \overline{x})} \lor (\overline{x} \lor y) \]

   \[ \overline{(\overline{y} \lor \overline{x})} \equiv \overline{\overline{y}} \land \overline{\overline{x}} \equiv y \land x \]

   Таким образом:

   \[ (y \land x) \lor (\overline{x} \lor y) \]

4. Формула упрощается:
   Подставим все обратно:

   \[ (((x \land \overline{y}) \lor (\overline{y} \lor \overline{x})) \land ((y \land x) \lor (\overline{x} \lor y))) \land z \]

5. Приведение к СКНФ:
   По правилам приведения к конъюнктивной нормальной форме необходимо использовать законы де Моргана и распространить конъюнкции на дизъюнкции. Но прежде всего, попробуем упростить, чтобы минимизировать количество операций. После нескольких преобразований можно прийти к следующему выражению (оно будет в конъюнктивной нормальной форме):

Ответ:

Формула в СКНФ:

\[ (x \lor y) \land (\overline{x} \lor \overline{y}) \land z \]