Презентация Логика высказываний и булевы алгебры (Boolean Algebra and Logic) онлайн

Содержание слайда: Логика высказываний и булевы алгебры (Boolean Algebra and Logic) Автор курса: Гринченков Дмитрий Валерьевич, доцент, к.т.н., заведующий кафедрой ПОВТ

Содержание слайда: Лекции – 18 часов Практические занятия – 18 часов Лабораторные работы – 18 часов Экзамен

Содержание слайда: ВВЕДЕНИЕ

Содержание слайда: Математическая логика (ее называют также формальной логикой, теорией доказательств) изучает законы и формы корректных человеческих рассуждений. Этот раздел математики имеет особое значение в изучении математических наук.

Содержание слайда: С одной стороны, предметом изучения математической логики является конкретная область знаний, связанная с расширением, развитием и формализацией положений и законов Булевой алгебры. Положения этой теории лежат в основе таких направлений исследований, как дискретная математика, функциональное и логическое программирование, системы искусственного интеллекта и др.

Содержание слайда: С другой стороны, положения математической логики носят всеобщий характер, так как они определяют понятия и правила строгого выполнения логических доказательств. Строгое доказательство правильности тех или иных утверждений – это центральное звено любой математической теории.

Содержание слайда: Главная цель математической логики  дать точное и адекватное определение понятия "математическое доказательство". Поскольку математика является наукой, в которой все утверждения доказываются с помощью умозаключений, математическая логика может представляться как инструмент (как совокупность средств) для описания правил построения множества других математических теорий.

Содержание слайда: С точки зрения построения математической теории весь комплекс знаний в некоторой предметной области удобно разделить на две части: Содержательная часть теории (семантика). Формальная часть теории (синтаксис).

Содержание слайда: Содержательная часть теории (семантика), которая непосредственно связана с изучаемым объектом и позволяет описывать его поведение и свойства в терминах соответствующей области знания; все утверждения такого описания имеют содержательный смысл. Содержательная часть теории (семантика), которая непосредственно связана с изучаемым объектом и позволяет описывать его поведение и свойства в терминах соответствующей области знания; все утверждения такого описания имеют содержательный смысл.

Содержание слайда: Формальная часть теории (синтаксис), основу которой составляет набор правил, позволяющих осуществлять преобразования и формировать новые истинные утверждения на основе ранее доказанных. Эта часть теории носит абстрактный характер и не связывается с конкретным реальным объектом. Более того, полученные в формальной теории результаты могут относиться к большому количеству различных объектов реальной жизни.

Содержание слайда: Пример. Рассмотрим цепочку логических рассуждений: - из А следует В; - из С следует А. Вывод: из С следует В. Эта цепочка рассуждений может иметь практически любое содержание.

Содержание слайда: Например: Все люди смертны. Сократ  человек. Следовательно, Сократ смертен. Все студенты сдали сессию. Петров  студент. Следовательно, Петров сдал сессию.

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

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

Содержание слайда: Другим примером построения математической теории является теория предикатов. Другим примером построения математической теории является теория предикатов. Семантическая часть этой теории – логика предикатов, она представляет расширение логики высказываний в части описания множества отношений и двоичных функций (в том числе функций непрерывных переменных).

Содержание слайда: Синтаксической частью этой теории является исчисление предикатов,  это формальная система, которая дает инструмент для доказательства истинных в данной теории утверждений (теорем).

Содержание слайда: История развития Интерес к логике возник еще в VI  IV вв. до н.э. Оформление же ее как самостоятельной науки произошло в трудах греческого философа Аристотеля (384  322 гг. до н.э.), который в своих "Аналитиках" систематизи-ровал известные до него сведения, и эта система стала впоследствии называться формальной логикой.

Содержание слайда: Формальная логика в ее первоначальном виде, просуществовала без особых изменений двадцать столетий. Сравнительно рано возникла идея и о том, что, записав исходные посылки формулами, похожими на математические, удастся заменить все рассуждения формальными "вычислениями". Уже в средние века делались попытки даже создания таких "логических" машин.

Содержание слайда: Развитие математики выявило недостатки логики, разработанной Аристотилем, и потребовало дальнейшего ее развития. Идеи о построении логики на математической основе были высказаны немецким математиком Г. Лейбницем (1646  1716) в конце XVII века.

Содержание слайда: Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением. Лейбниц говорил: «Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, что­бы облегчить сам процесс нашего мышления».

Содержание слайда: Первая реализация идей Лейбница, положившая начало современному аппарату математической логики (точнее, алгебре логики), принадлежит английскому ученому Дж. Булю (1815  1864). Он создал алгебру, в которой буквами обозначены высказывания, и это привело к алгебре высказываний.

Содержание слайда: Введение символических обозначений в логику имело огромное значение, именно благодаря введению символов в логику была получена основа для создания новой науки  математической логики. Применение математики к логике позволило представить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, ранее практически недоступных человеческому мышлению, что существенно расширило область логических исследований. Ставшие в конце XIX века актуальными вопросы обоснования основных математических понятий также имели логическую природу, что привело к дальнейшему активному развитию математической логики.

Содержание слайда: Особенности математического мышления объясняются особенностями математических абстракций и многообразием их взаимосвязей, которые отражаются в логической систематизации математики, в доказательстве математических теорем. Именно поэтому современную математическую логику определяют как раздел математики, посвященный изучению математических доказательств и вопросов оснований математики.

Содержание слайда: Существенное развитие математическая логика получила в работах Г.Фреге (1848  1925), посвященных теории формальных языков, и Д.Пеано (1858  1932), который применил математическую логику для обоснования арифметики и теории множеств.

Содержание слайда: Однако особое значение этот раздел математики приобрел после инициативы Д.Гильберта (1862  1943), выступившего в 20-х годах прошлого века с программой обоснования математики на базе математической логики, именно с этого момента и начинается активное развитие современной математической логики.

Содержание слайда: Теории Д. Гильберта и его школа основывались на построении математических теорий как синтаксических теорий, в которых все утверждения записываются формулами в некотором алфавите и точно указываются правила вывода одних формул из других. В теорию как составная часть входит математическая логика. Таким образом, математическая теория, непротиворечивость которой требовалось доказать, стала предметом другой математической теории, которую Гильберт назвал метаматематикой, или теорией доказательств.

Содержание слайда: В связи с этим решается задача построения синтаксической, то есть формализованной аксиоматической теории самой математической логики. Выбирая по-разному системы аксиом и правила вывода одних формул из других, получают различные синтаксические логические теории. Каждую из них называют логическим исчислением.

Содержание слайда: Для математиков это открытие логических парадоксов, затронувших основы теории множеств. Распространение аксиоматического метода в построении различных математических теорий, в первую очередь геометрии, а затем арифметики, теории групп и т.д. В аксиоматическом построении математической теории предварительно выбираются некоторая система базовых понятий и отношения между ними. Эти понятия и отношения часто называются основными. Далее без доказательства принимаются основные положения рассматриваемой теории  аксиомы. Все дальнейшее содержание теории выводится логически из аксиом.

Содержание слайда: Впервые аксиоматическое построение математической теории было предпринято Евклидом в построении геометрии.

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

Содержание слайда: Непротиворечивость аксиоматической теории является одним из основных требований, предъявляемых к системе аксиом данной теории. Она означает, что из данной системы аксиом нельзя логическим путем вывести два противоречащих друг другу утверждения. Интерес инженеров связан с тем, что в рамках математической логики уже создан аппарат для расчета действия самых различных вычислительных и управляющих дискретных устройств и систем.

Содержание слайда: Первым идею применимости математической логики для формального описания сложных цепей, состоящих из технических объектов, вступающих в дискретные отношения, высказал в 1910 г. профессор С.-Петербургского университета П.Эренфест. Он предложил описывать релейные схемы, имевшие уже в то время большое значение для техники связи, с помощью аппарата логики. Но поскольку эти цепи были довольно примитивны и не требовали для своей разработки теоретической базы, идеи Эренфеста были надолго забыты.

Содержание слайда: И лишь в 1938 г. американский инженер К.Шеннон использовал на практике алгебру логики Дж. Буля для анализа и расчета релейных схем. В дальнейшем достижения математической логики стали использоваться при создании технических средств для информационных и вычислительных систем. Кроме того, результаты, полученные в логической теории языков, применяются при создании формальных языков программирования и элементов искусственного интеллекта.

Содержание слайда: Рекомендуемая литература по курсу

Содержание слайда: