ID: 48070

Название работы: Математическая логикаи теория алгоритмов. Курс лекций

Категория: Конспект

Предметная область: Математика и математический анализ

Описание: Формула логики высказываний: пропозициональные буквы переменные: B C простые высказывания пропозициональные связки логические связки скобки = пропозициональная формула ПФ формула proposition заявление утверждение; от лат. Формула F называется выполнимой если F истинна в некоторой интерпретации: существует k такое что FIk = И. Формула F называется общезначимой или тавтологией если F истинна во всех возможных интерпретациях: для всех возможных k: FIk = И. Формула F называется противоречием если F ложна во всех...

Язык: Русский

Дата добавления: 2013-12-06

Размер файла: 125.5 KB

Работу скачали: 14 чел.

Федеральное агентство железнодорожного транспорта

Московский государственный университет путей сообщения (МИИТ)

Институт управления и информационных технологий

________________________

Кафедра «Автоматизированные системы управления»

В.В. Гуренко

Математическая логика
и теория алгоритмов

Курс лекций

Направление, профиль:

1) Информатика и вычислительная техника, АСОИУ (230100.62),

2) Информационные системы и технологии, ИСТ (230400.62).

Квалификация: бакалавр.

Семестр: 3. Форма контроля: экзамен.

Объемы (ч.):

АСОИУ (УВА): всего – 72, ауд. – 36 (лк. – 18, пр. занятия – 18), СРС – 9.   ЗЕТ = 2;

ИВТ (УИС): всего – 108, ауд. – 39 (лк. – 18, пр. занятия – 18, КСР – 3), СРС – 42.   ЗЕТ = 3.

Москва   2012

Литература

Основная.

№ п/п	Наименование	Автор(ы)	Место и год издания	Исп. при изучении разделов
1.	Дискретная математика для инженера. – 5-е изд. (Серия: Учебники для вузов. Специальная литература).	Кузнецов О.П.	СПб.: Изд-во «Лань», 2009.	МЛ, ТА
2.	Математическая логика и теория алгоритмов. Учебник. (Серия «Высшее образование»).	Судоплатов С.В., Овчинникова Е.В.	М.: Инфра-М, 2008.	МЛ, ТА
3.	Дискретная математика: Учеб. пособие. – 3-е изд., испр. и доп.	Плотников А.Д.	М.: Новое знание, 2008.	МЛ, ТА
4.	Дискретная математика для программистов. Учебник для вузов. – 2-е изд.	Новиков Ф.А.	СПб.: Питер, 2007.	МЛ
5.	Математическая логика: учеб. пособие.	Ершов Ю.Л., Палюгин Е.А.	СПб.: Изд-во «Лань», 2006.	МЛ

Дополнительная.

№ п/п	Наименование	Автор(ы)	Место и год издания	Используется при изучении разделов
	Математическая логика и теория алгоритмов для программистов.	Гринченков Д.В., Потоцкий С.И.	М.: Изд-во «КноРус», 2010.	МЛ, ТА
	Задачи и упражнения по дискретной математике: учеб. пособие. – 3-е изд.	Гаврилов Г.П., Сапоженко А.А.	М.: Физматлит, 2005.	ТА
	Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд.	Лавров И.А., Максимова Л.Л.	М.: Физматлит, 2009.	МЛ, ТА
	Математическая логика. Пер. с англ. – 4-е изд.	Клини С.К.	М.: ЛКИ, 2008.	МЛ
	Сложностный метод теории алгоритмов.	Шурыгин В.А.	М.: Либроком, 2009.	ТА
	Рекурсивные функции.	Марченков С.С.	М.: Физматлит, 2007.	ТА
	Математическая логика и автоматическое доказательство теорем.	Чень Ч., Ли Р.	М.: Наука, 1983.	МЛ
	Введение в математическую логику. Пер. с англ.	Мендельсон Э.	М.: Наука, 1984.	МЛ
	Логика: учеб. пособие. – 2-е изд.	Фатиев Н.И.	СПб.: СПбГУП, 2002.	МЛ

Раздел 1. Математическая логика

Предмет МЛ: логические исчисления в наиболее общем виде.

Часть 1. Логика высказываний

§ 1. Основные понятия.

Высказывание – повествовательное предложение, которое либо истинно (И), либо ложно (Л), но не то и другое вместе.

Отрицание		«НЕ»
Конъюнкция	&  	«И»
Дизъюнкция		«ИЛИ»
Импликация		«Если…, то…»
Эквивалентность		«… тогда и только тогда…»

Простые высказывания. Обозначение: A, B, C,…

Примеры. A: «Идет дождь», B: «Книга раскрыта», C: «Солнце светит».

Составные высказывания.   A & C, B, C  A.

Задача логики высказываний: изучение зависимостей между истинностными значениями простых и составных высказываний.

Формула логики высказываний:

пропозициональные буквы (переменные): A, B, C,… (простые высказывания)

+

пропозициональные связки (логические связки)

+

скобки

=

пропозициональная формула (ПФ, формула)

proposition – заявление, утверждение; от лат. propositio – основное положение, предпосылка.

Каждой ПФ можно поставить в соответствие таблицу истинности.

Таблица истинности показывает зависимость значения формулы от значений входящих в нее пропозициональных переменных.

Пример. F = (A & B)  B.

A	B	A & B	F
Л	Л	Л	И
Л	И	И	Л
И	Л	Л	И
И	И	Л	И

§ 2. Интерпретации.

Пусть F(x1, x2, … xn) – ПФ, где x1, x2, … xn – входящие в F пропозициональные переменные.

Интерпретация I формулы F – конкретный набор истинностных значений переменных x1, x2, … xn.

F(I) – значение формулы F в интерпретации I.

В приведенном выше примере, где  F = (A & B)  B,  можно указать:

I1: A = «Л», B = «И» либо кратко: I1 = (Л, И). F(I1) = «Л».

I2: A = «И», B = «Л», кратко: I2 = (И, Л). F(I2) = «И».

В построении для ПФ таблицы истинности, включающей все возможные интерпретации, заключается исчисление высказываний методом таблиц истинности.

§ 3. Тавтологии и противоречия.

Формула F называется выполнимой, если F истинна в некоторой интерпретации,:

существует k такое, что F(Ik) = «И».

Формула F называется общезначимой или тавтологией, если F истинна во всех возможных интерпретациях,:

для всех возможных k: F(Ik) = «И».

Формула F называется противоречием, если F ложна во всех возможных интерпретациях (т.е. формула невыполнима):

для всех возможных k: F(Ik) = «Л».

Пример. F1 = А  А – тавтология:

I1 = «И», F1(I1) = «И»;   I2 = «Л», F1(I2) = «И».   Других интерпретаций нет.

F2 = А & А – противоречие:

I1 = «И», F2(I1) = «Л»;   I2 = «Л», F2(I2) = «Л».   Других интерпретаций нет.

F3 = (A & B)  B – выполнимая формула.

Две теоремы о тавтологиях.

Th. 1.

1.  Если F – тавтология, то F – противоречие, и наоборот.
2.  Если F – противоречие, то F – тавтология, и наоборот.
3.  Если F – тавтология, то неверно, что F – противоречие, и наоборот.
4.  Если F – выполнимая формула, то неверно, что F – тавтология.
5.  Если F – выполнимая формула, то неверно, что F – противоречие.

Доказательства 1) … 5) следуют из определений и предшествующих утверждений для последующих. ■

Th. 2. Если формулы P и P  Q – тавтологии, то формула Q – тавтология.

Доказательство. От противного. Предположим: Q(Ij) = «Л». Из условия имеем:

P(Ij) = «И». Но тогда [P  Q] (Ij) = «Л» по определению импликации. Получили противоречие с условием в том, что P  Q – тавтология.

 Предположение неверно, и Q – тавтология. ■

§ 4. Логическое следование и логическая эквивалентность.

Пусть P и Q – формулы. Говорят, что:

Q логически следует из P (обозначение P  Q), если Q истинна в тех же интерпретациях, в которых истинна P;

P и Q логически эквивалентны (обозначение P  Q), если они являются логическим следствием друг друга, т.е. (P  Q) & (Q  P).

Свойство 1. Истинностные значения логически эквивалентных формул одинаковы в каждой из всех возможных интерпретаций.

Пример. (A  B)  (A & B).

Теоремы о логической эквивалентности.

Th. 3. Если формулы P и Q логически эквивалентны, то формула P  Q – тавтология.

Доказательство. На основании свойства 1, формулы P и Q одновременно принимают значение либо «И», либо «Л». И в том, и в другом случае значение формулы P  Q равно «И» по определению эквивалентности, т.е. [P  Q](Ij) = «И» для всех возможных j.    P  Q – тавтология. ■

Th. 4. Формула  P  Q  логически эквивалентна формуле P  Q:   (P  Q)  (P  Q).

Доказательство: методом таблиц истинности для всех возможных интерпретаций. ■

Th. 4 позволяет заменять дизъюнкцию импликацией.

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

•  обозначения множеств – формулами,
•  операции над множествами – логическими связками,

то имеют место соответствующие логические эквивалентности:

Свойство операций над множествами		Логическая эквивалентность
Коммутативность	A  B = B  A A  B = B  A	A & B  B & A A  B  B  A
Ассоциативность	A  (B  С) = (A  B)  C A  (B  С) = (A  B)  C	A & (B & C)  (A & B) & C A  (B  C)  (A  B)  C
Дистрибутивность	A  (B  С) = (A  B)  (A  C) A  (B  С) = (A  B)  (A  C)	A & (B  C)  (A & B)  (A & C) A  (B & C)  (A  B) & (A  C)
и т.д.	…	…

Доказательство: методом таблиц истинности для всех возможных интерпретаций. ■

Теоремы о логическом следовании.

Th. 6*. Если P1, P2, … Pn, Q – формулы, то (P1 & P2 & … & Pn)  Q тогда и только тогда, когда (P1 & P2 & … & Pn)  Q – тавтология.

Th. 7*. Если P1, P2, … Pn, Q – формулы, то (P1 & P2 & … & Pn)  Q тогда и только тогда, когда P1 & P2 & … & Pn & Q – противоречие.

Доказательство: см. рекомендованную литературу.

Примечание.  A  B: формулировка «В логически следует из А» эквивалентна формулировке «А логически влечет В».

Введенные понятия логики высказываний позволяют сформулировать возможности метода таблиц истинности. Используя его, можно выяснить:

•  является ли формула выполнимой, тавтологией или противоречием;
•  имеет ли место логическое следование одной формулы из другой;
•  являются ли две формулы логически эквивалентными.

§ 5. Подстановка и замена.

Пусть F – формула, в которую входит переменная х:  F(…х…)

или подформула Q: F(…Q…).

Пусть P – формула. Тогда F(…х…) {P // х}

обозначает формулу, полученную из F подстановкой P вместо всех вхождений х в F;

F(…Q…) {P / Q}

обозначает формулу, полученную из F заменой некоторых (одного или нескольких) вхождений подформулы Q на формулу P.

Пример. Дано: F = (A & B  B  A)  A & B. Пусть x = B,  P = B  A,  Q = A & B.

Тогда  подстановка F(…х…) {P // х}  =  F(…B…) {(B  A) // B}  =

=  (A & (B  A)   (B  A)  A)  A & (B  A);

однократная замена F(…Q…) {P / Q}  =  F(…(A & B)…) {(B  A) / (A & B )} =

=  ((B  A)  B  A)  A & B.

Th. 8 (правило подстановки). Если F(…х…) – тавтология и Р – любая формула,
то F(…х…) {P // х} – тавтология.

Th. 9 (правило замены). Если F(…Q…),  Q  S  и  D = F(…Q…) {S / Q},  то  F  D.

NB: Q и S – эквивалентные, но разные формулы!

Правила Th. 8 и Th. 9 используются при построении логического вывода в формальных теориях.

Частный случай формулы.

Формула В, полученная из формулы А подстановкой подформул В1, В2, …, Вn вместо переменных х1, х2, …, хn, называется частным случаем формулы А:

Набор подстановок  называется унификатором, т.к. в указанной подстановке формулы А и В унифицируются на основании Th. 8 (правила подстановки).

При этом если А – тавтология, то и В – тавтология  (подстановка в тавтологию порождает тавтологию).