Мат анализ. Мат анализ 9. Контрольная работа 1 Задание 1 Построим таблицу истинности для формулы алгебры высказываний и приведём её к сднф и скнф двумя способами
 Скачать 84.4 Kb.
|
1 2
|
| ( | X | ∨ | Y | → | Z | ) | | ( | ¬ | Z | → | ¬ | ( | X | ∧ | Y | ) | ) |
|
|
|
|
|
|
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Способ 1
Для нахождения СКНФ нужно из таблицы истинности выделить лишь те строки, результат которых равен 0. Для даннойфункции набор строк будет следующим:
|
|
|
|
|
|
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
Далее, для каждой строки выписываем дизъюнкцию всех переменных по следующему алгоритму: если значение переменной в данной строке равно 0, то в дизъюнкцию записываем саму переменную, а если равно 1, то - отрицание этой переменной. После этого все дизъюнкции связываем в конъюнкцию.
В результате, совершенная конъюнктивно-нормальная форма (СКНФ) нашей функции равна:
| ( | X | ∨ | ¬ | Y | ∨ | Z | ) | ∧ | ( | ¬ | X | ∨ | Y | ∨ | Z | ) |
| | | | | | | | | | | | | | | | | |
Способ 2
Для того чтобы найти КНФ ставим два отрицания над ДНФ и, оставляя временно верхнее отрицание без изменения, приводим оставшееся выражение к ДНФ. Затем по правилу де Моргана получаем КНФ.
| ¬ | ( | ¬ | ( | Z | ∨ | X | ∧ | Y | ∨ | ¬ | X | ∧ | ¬ | Y | ) | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | ( | X | ∧ | Y | ) | ∧ | ¬ | ( | ¬ | X | ∧ | ¬ | Y | ) | ) |
| ¬ | ( | ¬ | Z | ∧ | ( | ¬ | X | ∨ | ¬ | Y | ) | ∧ | ¬ | ( | ¬ | X | ∧ | ¬ | Y | ) | ) |
| ¬ | ( | ( | ¬ | Z | ∧ | ¬ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ) | ∧ | ¬ | ( | ¬ | X | ∧ | ¬ | Y | ) | ) |
| ¬ | ( | ( | ¬ | Z | ∧ | ¬ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ) | ∧ | ( | ¬ | ( | ¬ | X | ) | ∨ | ¬ | ( | ¬ | Y | ) | ) | ) |
| ¬ | ( | ( | ¬ | Z | ∧ | ¬ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ) | ∧ | ( | ¬ | ( | ¬ | X | ) | ∨ | Y | ) | ) |
| ¬ | ( | ( | ¬ | Z | ∧ | ¬ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ) | ∧ | ( | X | ∨ | Y | ) | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | X | ∨ | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | Y | ) |
| ¬ | ( | ¬ | Z | ∧ | 0 | ∨ | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | Y | ) |
| ¬ | ( | 0 | ∨ | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | Y | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | Y | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | ¬ | Z | ∧ | 0 | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ∨ | 0 | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ∨ | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ) |
| ¬ | ( | ¬ | Z | ∧ | ¬ | X | ∧ | Y | ) | ∧ | ¬ | ( | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ) |
| ( | ¬ | ( | ¬ | Z | ) | ∨ | ¬ | ( | ¬ | X | ) | ∨ | ¬ | Y | ) | ∧ | ¬ | ( | ¬ | Z | ∧ | ¬ | Y | ∧ | X | ) |
| ( | ¬ | ( | ¬ | Z | ) | ∨ | ¬ | ( | ¬ | X | ) | ∨ | ¬ | Y | ) | ∧ | ( | ¬ | ( | ¬ | Z | ) | ∨ | ¬ | ( | ¬ | Y | ) | ∨ | ¬ | X | ) |
| ( | ¬ | ( | ¬ | Z | ) | ∨ | ¬ | ( | ¬ | X | ) | ∨ | ¬ | Y | ) | ∧ | ( | ¬ | ( | ¬ | Z | ) | ∨ | Y | ∨ | ¬ | X | ) |
| ( | ¬ | ( | ¬ | Z | ) | ∨ | ¬ | ( | ¬ | X | ) | ∨ | ¬ | Y | ) | ∧ | ( | Z | ∨ | Y | ∨ | ¬ | X | ) |
| ( | ¬ | ( | ¬ | Z | ) | ∨ | X | ∨ | ¬ | Y | ) | ∧ | ( | Z | ∨ | Y | ∨ | ¬ | X | ) |
| ( | Z | ∨ | X | ∨ | ¬ | Y | ) | ∧ | ( | Z | ∨ | Y | ∨ | ¬ | X | ) |
Находим СКНФ.
| ( | Z | ∨ | X | ∨ | ¬ | Y | ) | ∧ | ( | Z | ∨ | Y | ∨ | ¬ | X | ) |
1 2