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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\text{[}x\wedge y\vee (\overline{x}\vee y)\wedge x\text{]}$

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

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

$\text{[}x\wedge (\overline{x}\vee y)\text{]}$

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

$\text{[}(x\wedge \overline{x})\vee (x\wedge y)\text{]}$

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

$\text{[}x\wedge y\text{]}$

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

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

$\text{[}x\wedge y\vee x\wedge y\text{]}$

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

$\text{[}x\wedge y\text{]}$

Заключение:

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

Ответ: СДНФ — это $\text{(}x\wedge y\text{)}$.