48070

Математическая логикаи теория алгоритмов. Курс лекций

Конспект

Математика и математический анализ

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

Русский

2013-12-06

125.5 KB

12 чел.

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

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

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

________________________

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

В.В. Гуренко

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

Курс лекций

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

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.

МЛ

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

№ п/п

Наименование

Автор(ы)

Место и год издания

Используется

при изучении разделов

  1.  

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

Гринченков Д.В., Потоцкий С.И.

М.: Изд-во «КноРус», 2010.

МЛ, ТА

  1.  

Задачи и упражнения по дискретной математике: учеб. пособие. – 3-е изд.

Гаврилов Г.П., Сапоженко А.А.

М.: Физматлит, 2005.

ТА

  1.  

Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд.

Лавров И.А., Максимова Л.Л.

М.: Физматлит, 2009.

МЛ, ТА

  1.  

Математическая логика. Пер. с англ. – 4-е изд.

Клини С.К.

М.: ЛКИ, 2008.

МЛ

  1.  

Сложностный метод теории алгоритмов.

Шурыгин В.А.

М.: Либроком, 2009.

ТА

  1.  

Рекурсивные функции.

Марченков С.С.

М.: Физматлит, 2007.

ТА

  1.  

Математическая логика и автоматическое доказательство теорем.

Чень Ч., Ли Р.

М.: Наука, 1983.

МЛ

  1.  

Введение в математическую логику. Пер. с англ.

Мендельсон Э.

М.: Наука, 1984.

МЛ

  1.  

Логика: учеб. пособие. – 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 (правила подстановки).

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


 

А также другие работы, которые могут Вас заинтересовать

59374. РОДИННЕ СВЯТО «НАЙКРАЩИЙ У СВІТІ ДІДУСЬ» 61.5 KB
  Шановні гості цю пісню діти вивчили спеціально для нашого свята. Щебечуть тиснуться кожному хочеться поспілкуватися почути цікаві оповідки яких дідусь Михайло знає так багато.
59375. День здоров’я. Сильні, спритні і сміливі 63 KB
  Вправа ноги на ширину ступні обруч опущений. Вправа видих. Вправа ноги нарізно обруч опущений. Вправа вдих.
59376. У ШЕВЧЕНКОВІЙ СВІТЛИЦІ 40.5 KB
  Святково прибраний клас і портрет Тараса Шевченка, рушники, виставка його творів, ілюстрацій. Біля портрету - слова; що є епіграфом свята:
59377. ТАЄМНИЦІ ВЕСНЯНОГО ЛІСУ 134.5 KB
  Вихователь: Так діти ось і прийшла до нас весна із своїми запашними квітами та зеленими травами. Діти заходять у ліс вдихають повітря Вихователь: Чому так легко дихається в лісі Діти: Тому що багато дерев і вони виробляють кисень.
59381. Cценарій театралізованого свята “В гостях у світової літератури” 55.5 KB
  Ведуча стята повідомляє про початок. Ведуча. Після цього ведуча запрошує їх на сцену і розпочинається дійство. Ведуча: Шановні учні Зарубіжна література надзвичайно цікавий предмет.
59382. Cценарій. Свято букваря 95.5 KB
  Та ще Півника покличу: Мій Півнику мій братику Сюди швидше біжи Азбуці допоможи Півник. Я лисичка я хитренька Букву €œЕЛ віддам тихенько Хвостом пишним поведу Слід з дороги замету. Азбуку дуже шаную Букву ПЕ їй подарую.