alt text

задан 31 Янв '15 14:51

изменен 31 Янв '15 14:56

EdwardTurJ's gravatar image


5041135

10|600 символов нужно символов осталось
3

Здесь в основе лежит применение законов де Моргана.

Если наша схема является конъюнкцией или дизъюнкцией нескольких схем, то к каждой из них по отдельности применяем описываемую далее процедуру. Пусть схема $%S$% представляет собой отрицание какой-то другой схемы $%S'$%. Если $%S'$% имеет вид отрицания, то двойное отрицание отбрасываем. Если $%S'$% имеет вид конъюнкции или дизъюнкции, то применяем закон де Моргана, переходя к дизъюнкции или конъюнкции отрицаний соответственно, действуя далее по рекурсии.

Легко заметить, что число используемых конъюнкций и дизъюнкций (вместе) не меняется в ходе процесса. Число используемых отрицаний может увеличиваться, но оно не превзойдёт числа элементов исходной схемы $%S$%, то есть размер останется полиномиальным.

ссылка

отвечен 31 Янв '15 18:04

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×939
×216
×87
×13

задан
31 Янв '15 14:51

показан
292 раза

обновлен
31 Янв '15 18:34

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru