Файл: Контрольная работа 1 Задание 1 Построим таблицу истинности для формулы алгебры высказываний и приведём её к сднф и скнф двумя способами.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 28.03.2024
Просмотров: 17
Скачиваний: 0
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Контрольная работа №1
Задание 1
Построим таблицу истинности для формулы алгебры высказываний и приведём её к СДНФ и СКНФ двумя способами.
(
X
∨
Y
→
Z
)
(
¬
Z
→
¬
(
X
∧
Y
)
)
Построим таблицу истинности.
Контрольная работа №1
Задание 1
Построим таблицу истинности для формулы алгебры высказываний и приведём её к СДНФ и СКНФ двумя способами.
(
X
∨
Y
→
Z
)
(
¬
Z
→
¬
(
X
∧
Y
)
)
Построим таблицу истинности.
| ( | 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 | ) |