Преобразовать формулу в совершенную конъюнктивную нормальную форму (СКНФ)

Предмет: Математическая логика (логика высказываний).
Задача 1.3: Преобразовать формулу \((xy¯)(xy)\) в совершенную конъюнктивную нормальную форму (СКНФ).
Шаг 1: Преобразуем импликацию в эквивалентную форму через дизъюнкцию

Импликация \(xy¯\) равносильна \(x¯y¯\). Теперь формула приобретает следующий вид:

\[(x¯y¯)(xy)\]

Шаг 2: Применяем законы ассоциативности и коммутативности

Объединяем дизъюнкции:

\[x¯y¯xy\]

Шаг 3: Приведение к СКНФ (совершенной конъюнктивной нормальной форме)

Нам нужно привести формулу в конъюнкцию дизъюнкций всех возможных переменных в различных комбинациях их значений. Дизъюнкция \(x¯y¯xy\) равносильна булевой константе 1, так как хотя бы один из членов всегда истинный. Формула в результате этого упрощения равна 1.

Ответ: СКНФ — это просто 1 (тождественно истинная формула).


Задача 1.4: Преобразовать формулу \(xy(xy)x\) в совершенную дизъюнктивную нормальную форму (СДНФ).
Шаг 1. Преобразуем импликацию

Импликация \(xy\) равносильна \(x¯y\). Теперь формула приобретает вид:

\[xy(x¯y)x\]

Шаг 2: Применяем дистрибутивность

Сначала раскроем скобки:

\[x(x¯y)\]

Применяя дистрибутивность логического умножения относительно сложения:

\[(xx¯)(xy)\]

Так как \(xx¯=0\), остаётся:

\[xy\]

Шаг 3: Финальная формула

Теперь объединяем с первой частью исходной формулы \(xy\):

\[xyxy\]

Так как обе части одинаковы, окончательно формула равна:

\[xy\]


Заключение:
  • В задаче 1.3 формула привелась к константе 1 (тождественно истинная формула).
  • В задаче 1.4 получилось \(xy\) в форме СДНФ.

Ответ: СДНФ — это \(xy\).

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

Узнайте стоимость работы онлайн

  • 22423 авторов готовы помочь тебе.
  • 2402 онлайн
Напишем БЕСПЛАТНО любую работу за 30 минут