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 (правила подстановки).

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


 

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

76960. Формы осуществления публичного управления: понятие, содержание, классификация и характеристика каждой из групп 27.86 KB
  Формы осуществления публичного управления: понятие содержание классификация и характеристика каждой из групп. Форма государственного управления внешнее выражение деятельности органов государственного управления и их должностных лиц осуществляемое в рамках их компетенции по разрешению стоящих задач и вызывающее определенные последствия. Общие черты форм государственного управления: 1.являются способом внешнего выражения деятельности органов государственного управления и их должностных лиц; 2.
76961. Правовые формы государственного управления: понятие, виды, характеристика каждой из форм 29.31 KB
  Правовые формы государственного управления: понятие виды характеристика каждой из форм. Правовая форма государственного управления – это юридически оформленное деяние органа исполнительной власти иного властного субъекта его представителя должностного лица осуществленное в рамках компетенции и влекущее юридические последствия т. Особенности государственного управления: государственное управление имеет ярко выраженный правовой характер направлено на реализацию законов и подзаконных актов; государственное управление осуществляется...
76962. Неправовые формы государственного управления: понятие, сущность, виды, значение. Соотношение с правовыми формами 26.2 KB
  Наряду с этими правовыми формами осуществления исполнительной власти выделяются также неправовые формы в виде организационных действий и материальнотехнических операций информирование инструктирование проведение совещаний консультаций и т. К неправовым формам государственного управления относятся организационные действия и материальнотехнические операции. Материальнотехнические операции разновидность внешнего проявления управленческой деятельности не влекущей юридических последствий направленная на обеспечение реализации правовых...
76963. Правовые акты государственного управления: понятие, признаки и юридическое значение. Классификация правовых актов управления 30.17 KB
  Правовые акты государственного управления: понятие признаки и юридическое значение. Классификация правовых актов управления. Правовой акт управления – вид юридического акта основанное на законе одностороннее юридическивластное волеизъявление органов государственного управления и их должностных лиц принятое в установленном процессуальном порядке и направленное на установление либо возникновение изменение и прекращение административноправовых отношений. Основные черты правового акта управления: 1.
76964. Требования, предъявляемые к правовым актам государственного управления, последствия их несоблюдения 28.36 KB
  Требования предъявляемые к правовым актам государственного управления последствия их несоблюдения. Акт государственного управления это управленческий документ содержащий властное волеизъявление уполномоченного субъекта государственного управления в виде нормативного или индивидуального предписания осуществленное в рамках его компетенции и для целей решения задач управленческой деятельности принятие которого влечет определенные юридические последствия. Являясь подзаконным актом акт государственного управления должен отвечать определенным...
76965. Порядок подготовки, принятия и вступления в действие актов государственного управления 27.03 KB
  Порядок подготовки принятия и вступления в действие актов государственного управления. Порядок подготовки вступления в силу и опубликования правовых актов управления устанавливается различными нормативными правовыми актами в зависимости от вида акта и издающих принимающих их органов федеральной и региональной исполнительной власти а также органов местного самоуправления. Наличие нормативной установленной процедуры издания или принятия актов управления. Подготовка проекта правового акта управления.
76966. Понятие и виды методов публичного управления 29.12 KB
  Понятие и виды методов публичного управления. Методы государственного управления способы приемы воздействия субъекта управления на объект управления в рамках управленческих отношений которые используются для достижения целей и задач управления реализации функций управления. Основные черты методов государственного управления: 1.выражают управленческое воздействие субъекта государственного управления на объект управления; 4.
76967. Убеждение и поощрение как методы государственного управления: понятие, сущность, виды, значение в выполнении задач и функций государственного управления 30.13 KB
  Убеждение и поощрение как методы государственного управления: понятие сущность виды значение в выполнении задач и функций государственного управления. Убеждение – процесс целенаправленного воздействия субъекта управления на управляемый объект в результате которого идеи ценности установки субъекта становятся внутренними идеями личными установками объекта управления. Существуют следующие средства способы убеждения: обучение процесс целенаправленного формирования знаний умений навыков; агитация распространение идей в целях...
76968. Понятие и сущность административно-правовых режимов, их виды и правовые основания введения и использования 28.07 KB
  Понятие и сущность административно-правовых режимов их виды и правовые основания введения и использования. Административно-правовые режимы ставят перед собой цель создание на пути правонарушителей надежных правовых барьеров которые бы затрудняли или же полностью исключали достижение противоправных целей. Ласточкин рассматривает его как совокупность правовых установок и необходимых организационных управленческих мер которые обеспечивали бы порядок реализации отдельными гражданами своих соответствующих прав и обязанностей а также порядок...