Булева алгебра и логические выражения

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

Раздел: Булева алгебра и логические выражения

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

Найти СДНФ (совершенную дизъюнктивную нормальную форму) и СКНФ (совершенную конъюнктивную нормальную форму) для выражения:

(\neg (x \land y) \Rightarrow \neg y) \land \neg (x \land y \Rightarrow \neg x)

Шаг 1: Упрощение выражения

1. Раскрываем импликации по правилу (A \Rightarrow B) \equiv \neg A \lor B:

   (\neg (x \land y) \lor \neg y) \land \neg (\neg (x \land y) \lor \neg x)

2. Упрощаем \neg (x \land y) по закону де Моргана:

   ((\neg x \lor \neg y) \lor \neg y) \land \neg ((\neg x \lor \neg y) \lor \neg x)

3. Убираем лишние повторения:

   (\neg x \lor \neg y) \land \neg (\neg x \lor \neg y \lor \neg x)

4. Упрощаем вторую часть:

   (\neg x \lor \neg y) \land (x \land y)

Шаг 2: Построение СДНФ

СДНФ — это дизъюнкция конъюнкций, в которых переменные принимают конкретные значения, при которых выражение истинно.

Таблица истинности показывает, что выражение истинно только при (x = 0, y = 1) или (x = 1, y = 0), значит:

\neg x y \lor x \neg y

Шаг 3: Построение СКНФ

СКНФ — это конъюнкция дизъюнкций, в которых выражение ложно.

Выражение ложно только при (x = 1, y = 1) и (x = 0, y = 0), значит:

(x \lor y) \land (\neg x \lor \neg y)

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

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

\exists x P(x,y) \lor \exists x \forall y Q(x,y) \Rightarrow \forall y \exists x S(x,y)

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

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

\neg (\exists x P(x,y) \lor \exists x \forall y Q(x,y)) \lor \forall y \exists x S(x,y)

Шаг 2: Применение законов де Моргана

1. \neg (A \lor B) \equiv \neg A \land \neg B:

   (\neg \exists x P(x,y) \land \neg \exists x \forall y Q(x,y)) \lor \forall y \exists x S(x,y)

2. Преобразуем отрицания кванторов:

   (\forall x \neg P(x,y) \land \forall x \exists y \neg Q(x,y)) \lor \forall y \exists x S(x,y)

Шаг 3: Приведение к пренексной форме

Выносим кванторы наружу:

\forall x \forall x' \forall y (\neg P(x,y) \land \exists y' \neg Q(x',y')) \lor (\forall y \exists x S(x,y))

Применяем дистрибутивность и приводим к стандартному виду:

\forall x \forall x' \forall y \forall y' \exists x'' ((\neg P(x,y) \land \neg Q(x',y')) \lor S(x'',y))

Это и есть ПНФ.

Решение задания 3:

Анализируем логическое рассуждение:

1. Переведем в логическую форму:

   • A: "Я опоздаю на поезд"
   • B: "Я не попаду на концерт"
   • C: "Я буду огорчаться"
   • D: "Мне нужно будет развеяться"
   • E: "Я буду долго собираться"

2. Даны условия:

   1. A \Rightarrow B
   2. B \Rightarrow (C \land D)
   3. E \Rightarrow A

3. Нужно доказать: (C \land D) \land E.

4. Проверим логическую цепочку:

   • Из E \Rightarrow A следует, что если E истинно, то A тоже истинно.
   • Из A \Rightarrow B следует, что если A истинно, то B тоже истинно.
   • Из B \Rightarrow (C \land D) следует, что если B истинно, то C и D тоже истинны.

5. Таким образом, если E истинно, то (C \land D) \land E тоже истинно.

Вывод: Рассуждение логически верно.