3.2 Высказывания.

Элементами логических рассуждений являются утверждения, которые либо истинны, либо ложны, но не то и другое вместе. Такие утверждения называются (простыми) высказываниями. Простые высказывания обозначаются пропозициональными переменными, принимающими истинностные значения “И” (истина) и ”Л” (ложь). Из простых высказываний с помощью логических связок могут быть построены составные высказывания.

Обычно рассматривают следующие логические связки:

Название	Прочтение	Обозначение
Отрицание	не	¬
Конъюнкция	и	&
Дизъюнкция	или	V
Импликация	если ... то	→

3.3 Формулы.

Правильно построенные составные высказывания называются (пропозициональными) формулами.

Формулы имеют следующий синтаксис:

Для упрощения записи вводится старшинство связок и лишние скобки опускаются.

Истинностное значение формулы определяется через истинностные значения ее составляющих в соответствии со следующей таблицей:

Л	Л	И	Л	Л	И
Л	И	И	Л	И	И
И	Л	Л	Л	И	Л
И	И	Л	И	И	И

3.4 Интерпретация.

Пусть – пропозициональная формула, где - входящие в нее пропозициональные переменные. Конкретный набор истинностных значений, приписанных переменным , называется интерпретацией формулы А. Формула может быть истинной (иметь значение И) при одной интерпретации и ложной (иметь значение Л) при другой интерпретации. Значение формулы А в интерпретации I будем обозначать I(А). Формула, истинная при некоторой интерпретации, называется выполнимой. Формула, истинная при всех возможных интерпретациях, называется общезначимой (или тавтологией) Формула, ложная при всех возможных интерпретациях, называется невыполнимой (или противоречием).

Пример:

– тавтология, – противоречие,

– выполнимая формула, она истинна при I(A)=Л.

3.5 Формальная теория.

Формальная теория – это:

1. Множество А символов, образующих алфавит;

2. Множество слов в алфавите А, называются формулами;

3. Подмножество В формул, , называются аксиомами;

4. Множество отношений R на множестве формул, ,

называются правилами вывода.

Тема 4. Графы и сети

4.1 История возникновения теории графов.

Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рис. 1). Эта задача была решена Эйлером в 1736 году.

Рис. 1. Иллюстрация к задаче о Кенигсбергских мостах

2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена Куратовским в 1930 году.

Рис. 2. Иллюстрация к задаче о трех домах и трех колодцах