Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними

Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

рис.17

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности).
Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

Ориентированные графы в экономике активно используются в сетевом планировании, в математике — в теории игр, теории множеств; при решении многих задач, в частности, комбинаторных.

Тема 5. Логические элементы компьютера

Определение

LOGOS (греч.) - слово, понятие, рассуждение, разум.

Слово «логика» обозначает совокупность правил, которым подчиняется процесс мышления.

Основными формами абстрактного мышления являются: понятия, суждения, умозаключения.

Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов (трапеция, дом).

Суждение - мысль, в которой что-либо утверждается или отрицается о предметах (весна наступила, и грачи прилетели).

Умозаключение - прием мышления, посредством которого из исходного знания получается новое знание (все металлы - простые вещества).

Логика (формальная) - наука о законах и формах правильного мышления.

Математическая логика - изучает логические связи и отношения, лежащие в основе логического (дедуктивного) вывода.

Этапы развития логики

I. АРИСТОТЕЛЬ (384-322 гг. до н.э., древнегреческий философ) - основоположник логики.

Написал книги «Категории», «Первая аналитика», «Вторая аналитика».

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

Например:

1.Все млекопитающие имеют скелет. Все киты - млекопитающие. Следовательно, все киты имеют скелет.

2. Все квадраты - ромбы. Все ромбы - параллелограммы. Следовательно, все квадраты - параллелограммы.

Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: «Все А суть В»; «Некоторые А суть В»; «Все А не суть В»; «Некоторые А не суть В».

Логика, основанная на теории силлогизмов называется классической.

II. Декарт Рене(1596-1650, французский философ, математик).Рекомендовал в логике использовать математические методы.

III. Лейбниц Г.В. (1646-1716, немецкий философ и математик) - предложил использовать в логике математическую символику и впервые высказал мысль о возможности применения в ней двоичной системы счисления. Ему принадлежит идея логического исчисления, то есть четко сформулированные правила действий со словами и предложениями, сродни арифметическим правилам действий с числами. В соответствии с этими правилами простые элементы логических рассуждений (понятия) обозначаются буквами, сложные элементы (предложения) – формулами, а умозаключения – уравнениями. «Единственное средство улучшить наши умозаключения – сделать их, как у математиков, наглядными, и если среди людей возникнет спор, нужно сказать «Посчитаем!»; тогда без особых формальностей можно будет увидеть, кто прав», - писал Лейбниц.

Лейбниц заложил идейный фундамент математической логики, а над практической реализацией этих идей работали и работают многие учёные.

IV.Джордж Буль (1815-1864, ирландский математик и логик) - основоположник математической логики. В 1847 г. Джордж Буль в работе «Математический анализ логики» изложил основы булевой алгебры. Разработал алфавит, орфографию и грамматику.

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

Развитие идей Буля привело к созданию современной математической логики, которая включает в себя алгебру множеств, алгебру высказываний, алгебру релейных схем (реле – это переключатель в электрических схемах), без которых было бы невозможным проектирование и программирование вычислительных машин. Именно булева алгебра лежит в основе работы компьютера.

V. Вклад в становление и развитие математической логики внесли также:

§ Аугустус де Морган (1806 - 1871);

§ Уильям Стенли Джевонс (1835 – 1882, английский экономист, статистик и философ-логик);

§ Платон Сергеевич Порецкий (1846-1907 – русский математик);

§ Чарлз Сандерс Пирс (1839-1914, американский философ, логик, математик и естествоиспытатель, «Исследования по логике» (1883)) и др.