RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Летняя школа «Современная математика», 2015
27 июля 2015 г. 09:30, г. Дубна, дом отдыха «Ратмино»
 


Сложность доказательств. Занятие 2

А. А. Разборов
Видеозаписи:
Flash Video 472.6 Mb
Flash Video 2,831.7 Mb
MP4 472.6 Mb

Количество просмотров:
Эта страница:167
Видеофайлы:44

А. А. Разборов


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Аннотация: 1. Имеется выражение, состоящее из булевых переменных $p_1,…,p_n$ и логических связок $\neg$,$\lor$,$\land$,$\Rightarrow$. Как доказать, что оно выполнимо, т. е. что вместо $p_1,…,p_n$ можно подставить TRUE или FALSE так, что значение всего выражения окажется равным TRUE? Ответ очевиден: предъявить подстановку и проверить её прямым вычислением.

2. А как быстро доказать, что данное булево выражение невыполнимо? Короткого доказательства, скорее всего, не существует. Однако можно попытаться вывести противоречие из имеющихся аксиом с помощью хорошо известных в математической логике правил вывода.

3. А как доказать, что компьютерный чип или программа удовлетворяют требуемым спецификациям? Ответ: закодировать этот факт в виде булевого выражения, после чего воспользоваться алгоритмами, разработанными для предыдущей задачи.

4. Наконец, пусть имеется система полиномиальных уравнений или неравенств. Как доказать, что она несовместна? Ответ: воспользоваться теоремой Гильберта о нулях или её вещественным аналогом, известным как Positivestellensatz. Короткими при этом будут считаться доказательства, использующие исключительно полиномы малой степени.

Общим для всех этих ситуаций является то, что нас интересует не только наличие доказательства верных фактов (скажем, теорем), но и то, насколько «простым» оно может или не может быть. Несмотря на кажущуюся разнородность всех этих вопросов, их изучение в рамках одной дисциплины оказывается весьма продуктивным, и именно об этом мы и поговорим.
Специальных знаний для понимания курса не требуется, хотя самое общее представление о пропозициональной (булевой) логике было бы полезно.

Website: http://www.mccme.ru/dubna/2015/courses/razborov.html
Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017