Доказать эквивалентность формулы

Автор темы molotov 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеИсследовательские гранты фонда «БАЗИС» 202118.02.2021 17:56
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
10.03.2021 13:09
Доказать эквивалентность формулы
Приветствую!
Доказать, что формула А от переменных P1, P2, ... , Pk эквивалентна некоторой формуле, содержащей лишь &, ∨, → и не содержащей ¬, тогда и только тогда, когда в ее совершенной к.н.ф отсутствуют дизъюнкт (¬P1 ∨ ... ∨ ¬Pk).

к.н.ф - конъюнктивная нормальная форма
10.03.2021 15:04
Подсказка
1) В условии имеется опечатка: отсутствовать должен дизъюнкт, содержащий только отрицания переменных, но не обязательно ВСЕХ переменных.
2) Покажите, что если дизъюнкт содержит хотя бы одну переменную (без отрицания), то его можно преобразовать к виду не содержащему отрицание.
3) Покажите индукцией по сложности формулы, что формулы содержащие только &, ∨, → имеют значение истинности 1 при условии, что все переменные имеют значение 1.
Сделайте вывод о том, что дизъюнкт, не содержащий переменных положительно. не может быть представлен в требуемом виде.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти