По таблице истинности формулы построить СДНФ и СКНФ

Шаг 1: Построение таблицы истинности

Для того чтобы построить таблицу истинности данной формулы, нам нужно учесть следующие логические операции:

• Импликация (→)
• Эквиваленция (~)
• Отрицание (¯)

Формула выглядит так: (x → y) ~ (z → (x ~ \overline{z}))

Количество переменных:

В данной формуле участвуют три переменные: x, y и z. Следовательно, таблица истинности будет иметь \(2^3 = 8\) строк для всех возможных комбинаций истинных значений x, y и z.

Теперь сгенерируем таблицу истинности с вычислениями.

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

СДНФ строится на основе строк таблицы истинности, где результат выражения равен 1. Согласно таблице, единицы находятся в строках:

• 1: x = 0, y = 0, z = 0
• 3: x = 0, y = 1, z = 0
• 5: x = 1, y = 0, z = 0
• 6: x = 1, y = 0, z = 1
• 8: x = 1, y = 1, z = 1

Записи для каждой строки:

1. Для комбинации x = 0, y = 0, z = 0: ¬x ∧ ¬y ∧ ¬z
2. Для комбинации x = 0, y = 1, z = 0: ¬x ∧ y ∧ ¬z
3. Для комбинации x = 1, y = 0, z = 0: x ∧ ¬y ∧ ¬z
4. Для комбинации x = 1, y = 0, z = 1: x ∧ ¬y ∧ z
5. Для комбинации x = 1, y = 1, z = 1: x ∧ y ∧ z

Объединяя все условия по дизъюнкции (по символу ∨), получаем СДНФ:

СДНФ = (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ z)

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

СКНФ строится на основе строк таблицы истинности, где результат выражения равен 0. Согласно таблице, нули находятся в строках:

• 2: x = 0, y = 0, z = 1
• 4: x = 0, y = 1, z = 1
• 7: x = 1, y = 1, z = 0

Записи для каждой строки:

1. Для комбинации x = 0, y = 0, z = 1: (x ∨ y ∨ ¬z)
2. Для комбинации x = 0, y = 1, z = 1: (x ∨ ¬y ∨ ¬z)
3. Для комбинации x = 1, y = 1, z = 0: (¬x ∨ ¬y ∨ z)

Объединяя все условия по конъюнкции (по символу ∧), получаем СКНФ:

Ответ:

• СДНФ: (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ z)
• СКНФ: (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z)

СКНФ = (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z)