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

Предмет: Математическая логика (логика высказываний).

Задача 1.3: Преобразовать формулу \((x \rightarrow \overline{y}) \vee (x \vee y)\) в совершенную конъюнктивную нормальную форму (СКНФ).

Шаг 1: Преобразуем импликацию в эквивалентную форму через дизъюнкцию

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

\[ (\overline{x} \vee \overline{y}) \vee (x \vee y) \]

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

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

\[\overline{x} \vee \overline{y} \vee x \vee y\]

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

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

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

Задача 1.4: Преобразовать формулу \(x \land y \vee (x \rightarrow y) \land x\) в совершенную дизъюнктивную нормальную форму (СДНФ).

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

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

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

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

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

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

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

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

Так как \(x \land \overline{x} = 0\), остаётся:

\[x \land y\]

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

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

\[x \land y \vee x \land y\]

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

\[x \land y\]

Заключение:

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

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