Булева алгебра и нормальные формы логических выражений

Условие:

Реши задания

Условие: Реши задания

Решение:

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

Раздел: Булева алгебра и нормальные формы логических выражений

Задание №1

Упростим формулу и приведем её к СКНФ (совершенной конъюнктивной нормальной форме) и СДНФ (совершенной дизъюнктивной нормальной форме).

Задана формула:
 f = \neg \left( (\neg x \land y \Leftrightarrow \neg y) \Rightarrow (x \lor y) \right) 

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

Эквивалентность  A \Leftrightarrow B  можно заменить на
 (A \lor \neg B) \land (\neg A \lor B) .

Подставляем:
 (\neg x \land y \Leftrightarrow \neg y) = ((\neg x \land y) \lor y) \land (\neg(\neg x \land y) \lor \neg y) .

Упрощаем:
 ((\neg x \land y) \lor y) \land ((x \lor \neg y) \lor \neg y) .

Так как  (\neg x \land y) \lor y = y  и  (x \lor \neg y) \lor \neg y = x \lor \neg y , получаем:
 y \land (x \lor \neg y) .

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

Импликация  A \Rightarrow B  эквивалентна  \neg A \lor B .

Значит,
 (y \land (x \lor \neg y)) \Rightarrow (x \lor y) 
эквивалентно
 \neg (y \land (x \lor \neg y)) \lor (x \lor y) .

Шаг 3: Применяем закон Де Моргана

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

Так как  \neg (x \lor \neg y) = \neg x \land y , получаем:
 (\neg y \lor (\neg x \land y)) \lor (x \lor y) .

Упрощаем:
 (\neg y \lor \neg x \lor y) \lor (x \lor y) .

Так как  \neg y \lor y = 1 , остается:
 1 \lor (x \lor y) = 1 .

Таким образом,  f = \neg 1 = 0 .

Поскольку функция тождественно равна нулю, её СКНФ:
 x \land \neg x ,
а СДНФ отсутствует (так как нет единичных наборов).


Задание №2

Раздел: Логика предикатов
Требуется привести формулу логики предикатов к ПНФ (пренексной нормальной форме).

Формула отсутствует на изображении. Пожалуйста, уточните её, чтобы я мог выполнить преобразование.

Не нашли нужного вам решения? Оставьте заявку и наши авторы быстро и качественно помогут вам с решением.
Оставить заявку
Работа вам нужна срочно. Не волнуйтесь, уложимся!
  • 22423 авторов готовы помочь тебе.
  • 2402 онлайн