Рис. Достижимость в графе: а –граф; б – матрица смежности; в – матрица достижимости; г- матрица контрдостижимости.
1. Каким образом определяется граф?
2. Что является путем в графе?
3. Как определяется такой вид графа, как дерево?
4. Какими способами можно задать граф?
Все компьютерные программы, демонстрирующиеинтеллектуальное поведение, основаны на использовании определенного математического аппарата, опирающегося на законы математической логики. Без понимания этих законов невозможно понимание принципов работы вычислительных машин вообще и систем искусственного интеллекта в частности.
Суждения могут быть истинными или ложными. Истинность или ложность суждений проверяется их соответствием действительности. Пример истинного суждения - «снег белый». Пример ложного суждения - «генетика - лженаука».
Суждение истинно, если оно отражает действительное положение вещей. Примеры истинных суждений: «снег белый», «2´2 = 4», «театр - это искусство».
Суждение ложно, если оно противоречит истинному положению вещей. Примеры ложных утверждений - «2´2 = 5», «снег - черный», «Земля плоская».
Однако существуют суждения, об истинности или ложности которых нельзя судить однозначно. Пример таких суждений: «есть жизнь на Марсе», «машина может думать», «астрология - наука».
Математическая логика - это дисциплина, изучающая технику математических доказательств. Отличие математических суждений от обычных разговорных высказываний состоит в том, что математические суждения всегда предполагают однозначную интерпретацию, в то время как наши обычные высказывания зачастую допускают многозначную трактовку.
Математика - наука, признающая исключительно только однозначные суждения, утверждения и допускающая только строгие доказательства. В то время как люди в своих рассуждениях и высказываниях допускают различного рода неточности и двусмысленности.
Работа ЭВМ как автоматических устройств основана исключительно на математически строгих правилах выполнения команд, программ и интерпретации данных. Тем самым работа компьютеров допускает строгую однозначную проверку правильности своей работы в плане заложенных в них процедур и алгоритмов обработки информации.
Фундаментом науки о вычислительных машинах является конструктивная математика, в основе которой лежит математическая логика и теория алгоритмов с их однозначностью в оценке суждений и процедур вывода. Математическая логика с самого начала использовалась для описания элементов и узлов ЭВМ, а теория алгоритмов - для описания компьютерных программ.
Основными объектами в математической логике являются- высказывания и предикаты. Первые изучаются в исчислении высказываний, а вторые - в исчислении предикатов.
Высказывания - это суждения, о которых может быть известно - что они истины или ложны. В исчислении высказываний не исследуется - о чем утверждается в этих суждениях.
Высказывания обычно обозначаются отдельными буквами или буквами с возможными индексами. Примеры простых высказываний и их обозначений:
А = «снег белый»
В1 = «вода теплая»
В2 = «земля твердая»
С математической точки зрения высказывания - это переменные, принимающие значения«истина» или«ложь». Эти два истинностных значения иногда заменяются словами «да», «нет», либо цифрами 1 и 0.
В отличии от высказыванийпредикаты - это суждения о некоторых переменных объектах или их свойствах. Примеры предикатов:
А(х) = «цвет яблока -х»
В(х, у) = «х < у»
где х, у - это некоторые переменные (объекты).
Значениями переменных в предикатах могут быть числа, слова, вектора, списки, функции, процедуры, алгоритмы или даже программы. Для математической логики существенно, чтобы эти переменные объекты имели конструктивную форму и были бы строго определены.
С математической точки зренияпредикаты - это функции, имеющие одну или несколько переменных и принимающие логические значения «истина» или «ложь». Обозначения предикатов в математической логике схожи с обозначениями обычных математических функций:Р(х), Q(x,y)и т. д.
вида:
, 
, 
:
, 
, 
.
