Назовём формулу импликативной, если она состоит только из отрицаний и импликаций. Скажем, что формула имеет тесные отрицания, если отрицания стоят только перед переменными. Верно ли, что любую функцию можно представить импликативной формулой с тесными отрицаниями?

задан 15 Окт 22:11

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

Тождественно нулевую функцию в таком виде не представить. Более того, функция должна принимать значение 1 как минимум на половине всех наборов. Поэтому not(a->b) тоже непредставима.

Индукцией по сложности формулы (числу логических связок) доказываем, что существует переменная, которой можно придать одно из значений 0 или 1, и этого будет достаточно, чтобы вся функция была равна 1.

Если связок нет, и перед нами переменная a, то полагаем её равной 1. Если формула имеет вид отрицания, то это отрицание переменной not(a), и полагаем a равной 0. Если формула имеет вид импликации p->q, то q есть импликативная формула с тесными отрицаниями и меньшим числом связок. Для неё есть требуемая переменная, одно из значений которой гарантирует |q|=1. Но тогда вся импликация тоже истинна.

ссылка

отвечен 15 Окт 23:31

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

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

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

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

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

отмечен:

×915

задан
15 Окт 22:11

показан
36 раз

обновлен
15 Окт 23:31

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

по почте:

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

по RSS:

Ответы

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

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