Предмет: Математическая логика
Задание 1.1: Приведение формулы (x \to y) \land (y \to z) \to (x \to z) к конъюнктивной нормальной форме (КНФ).
Шаг 1. Развернем импликации:
Формула имеет три импликации (
\(\to\)), которые мы можем развернуть через эквивалентное выражение:
p \to q \equiv \neg p \lor q.
- x \to y \equiv \neg x \lor y,
- y \to z \equiv \neg y \lor z,
- x \to z \equiv \neg x \lor z.
Заменяя все импликации в формуле:
[(\neg x \lor y) \land (\neg y \lor z) \to (\neg x \lor z)].
Шаг 2. Преобразуем импликацию (A \to B):
Используем правило:
A \to B \equiv \neg A \lor B.
[\neg ((\neg x \lor y) \land (\neg y \lor z)) \lor (\neg x \lor z)].
Шаг 3. Раскроем отрицание с помощью закона де Моргана:
[((x \land \neg y) \lor (y \land \neg z)) \lor (\neg x \lor z)].
Шаг 4. Приведем формулу к конъюнктивной нормальной форме:
Заметим, что эту формулу можно переписать как дизъюнкцию элементарных дизъюнктов, что делает её КНФ:
[(x \lor \neg x \lor z) \land (\neg y \lor \neg z \lor z)].
Удаляем тождественные переменные (например,
z \lor \neg z):
[(x \lor z) \land (\neg y \lor \neg z)].
Это и есть КНФ:
(x \lor z) \land (\neg y \lor \neg z).
Задание 1.2: Приведение формулы \neg x \land y \to x \land \neg y к дизъюнктивной нормальной форме (ДНФ).
Шаг 1. Развернем импликацию:
Используем эквивалентное выражение для импликации:
p \to q \equiv \neg p \lor q.
[\neg (\neg x \land y) \lor (x \land \neg y)].
Шаг 2. Раскроем отрицание:
Используем закон де Моргана:
[(x \lor \neg y) \lor (x \land \neg y)].
Шаг 3. Приведем к ДНФ:
Используем распределительный закон, чтобы привести формулу к ДНФ. В данном случае распределения не требуется, так как дизъюнкция уже состоит из элементарных дизъюнктов:
[(x \lor \neg y) \lor (x \land \neg y)].
Это и есть ДНФ:
(x \lor \neg y) \lor (x \land \neg y).
Ответы:
1.1.
(x \lor z) \land (\neg y \lor \neg z) — КНФ формулы.
1.2.
(x \lor \neg y) \lor (x \land \neg y) — ДНФ формулы.