Файл: Логика высказываний 1.pdf

13 

Оглавление

План курса 

(4) 

Литература 

(5)

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

(5)

1.1. Определение логического следствия 

(5) 

1.1.1.

 Определение высказывания и предиката (5). 

1.1.2.

 Определение умозаключения, посы-

лок и заключения (5). 

1.1.3.

 Определение интерпретации и контрпримера (6). 

1.1.4.

 Опреде-

ление логического следствия и следствия в теории (6). 

1.1.5.

 Упражнение (7).  

1.2. Язык логики высказываний 

(7)

1.2.1.

 Логические связки (7). 

1.2.2.

 Формулы логики высказываний (8).

1.2.3.

 Упражнение (8).  

1.3. Cледствие в логике высказываний 

(9)

1.3.1.

 Стандартные интерпретации (9). 

1.3.2.

 Таблицы истинности (9). 

1.3.3.

 Упражнение (9). 

1.3.4.

 Таблицы истинности и логическое следствие (9). 

1.3.5.

 Направленная табличная проце-

дура (10). 

1.3.6.

 Примеры доказательств направленной  процедурой (10). 

1.3.7.

 Примеры до-

казательств  с  разветвлением  (11)

.  1.3.8.

  Упражнение  (11). 

1.3.9.

    Упражнение  (12). 

1.3.10.

Определение  логической  эквивалентности,  тавтологии  и  противоречия  (12). 

1.3.11.

  Упраж-

нение  (13). 

1.3.12.

  Упражнение  (13). 

1.3.13.

  Упражнение  (13). 

1.3.14.

  Свойства  логического 

следствия, эквивалентности, тавтологии и противоречия (13). 

1.3.15.

 Упражнение (14). 

1.4. Основные теоремы логики высказываний 

(14)

1.4.1.

 Теорема об отрицании, конъюнкции и дизъюнкции (14). 

1.4.2.

 Теорема об импликации 

и двойной импликации (14). 

1.4.3.

 Упражнение (15). 

1.4.4.

 Замечания об истории, терминоло-

гии и обозначениях (15). 

1.4.5.

 Нормальные формы (16). 

1.4.6.

 Упражнение (17). 

1.4.7.

  Ана-

лиз  и  синтез  контактных  схем  (17). 

1.4.8.

  Упражнение  (18). 

1.4.9.

  Упражнение  (18). 

1.4.10.

Полные системы булевых функций (19). 

1.4.11.

 Упражнение (19). 

2. Логика предикатов 

(19)

2.1. Язык прикладной логики предикатов 

(19)

2.1.1.

  Элементы  языка  прикладной  логики  предикатов  (19). 

2.1.2.

  Кванторы.  Свободные  и 

связанные  переменные  (20). 

2.1.3.

  Основные  свойства  кванторов  (21). 

2.1.4.

  Ограниченные 

кванторы (21). 

2.1.5.

 Упражнение (22). 

2.1.6.

 Пример формализации в языке прикладной ло-

гики предикатов (22). 

2.1.7.

 Правило обобщения (23). 

2.1.8.

 Упражнение (24). 

2.1.9.

 О форма-

лизации определений (24). 

2.1.10.

 Упражнение (25).

2.2. Следствие в прикладной логике предикатов 

(25)

2.2.1.

  Применение  правил  общности  (26). 

2.2.2.

  Обозначения  сложных  выражений.  Ограни-

ченные  кванторы  (26).

  2.2.3.

  Пример  с    подстроками  (27). 

2.2.4.

  Применение  правил  суще-

ствования (27). 

2.2.5.

 Обратное применение правил общности (27). 

2.2.6.

 Равенство как логи-

ческий предикат (28). 

2.2.7.

  Квантор существования  и  единственности  (28). 

2.2.8.

  Упражне-

ние (29). 

2.2.9.

 Упражнение (29). 

2.3. Основные теоремы логики предикатов 

(29)

2.3.1.

  Теорема  о  кванторах,  отрицании,  конъюнкции  и  дизъюнкции  (29). 

2.3.2.

  Теорема  о 

кванторах  и  импликации  (31). 

2.3.3.

  Упражнение  (32). 

2.3.4.

  ЕА-формализация  (32). 

2.3.5.

Упражнение (33). 

2.3.6.

 О силлогизмах Аристотеля (33). 

2.3.7.

 Упражнение (34). 

14 

3. Аксиоматические теории 

(34)

3.1. Аксиоматическая арифметика 

(35)

3.1.1.

 Аксиомы Пеано (35). 

3.1.2.

 Утверждение о существовании и единственности непосред-

ственно  следующего  элемента  (35). 

3.1.3.

  Непротиворечивость  (36).   

3.1.4.

  Утверждение  о 

существовании  предшественника  (36). 

3.1.5.

  Независимость  (37). 

3.1.6.

  Из  истории  геомет-

рии: независимость пятого постулата Евклида (37).  

3.1.7.

  Аксиомы  сложения  и  умножения 

(38). 

3.1.8.

  Утверждение: 



2 2

4

 

  (38)

.  3.1.9.

  Упражнение  (39). 

3.1.10.

  Доказательство 

утверждения 5 из 3.1.9 (39). 

3.2. Логические исчисления и формальная арифметика 

(39)

3.2.1.

 Формальные аксиоматические теории (39). 

3.2.2.

 Исчисление высказываний (40). 

3.2.3.

Пример доказательства в исчислении высказываний (41). 

3.2.4.

 Основные теоремы об исчис-

лении высказываний (41). 

3.2.5.

  Исчисление  предикатов  с  равенством  и  теории  первого  по-

рядка (42). 

3.2.6.

 Основные теоремы об исчислении предикатов (43). 

3.2.7.

 Основные теоре-

мы о формальной арифметике (44). 

4. Материалы к экзамену 

(45)

4.1. Логика высказываний 

(45)

4.1.1.

 Теоретические вопросы (45). 

4.1.2.

 Примерные задачи (45).  

4.2. Логика предикатов и аксиоматические теории 

(46) 

4.2.1.

 Теоретические вопросы (46). 

4.2.2.

 Примерные задачи (46).  

План курса  

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

(3 лекции + 6 лабораторных занятий). 

2.  Логика предикатов    

(3 лекции + 8 лабораторных занятий). 

3.  Аксиоматические теории   

(2 лекции + 3 лабораторных занятия). 

Коллоквиум

  письменный  на  лабораторных  занятиях  в  подгруппах  в  конце 

марта.  

Экзамен

  письменный  в  июне.  Сначала  работа  по  второй  части  курса,  потом  – 

для желающих повысить оценку за коллоквиум – по первой.    

Структура работы

 на коллоквиуме и на экзамене : 2 формулировки определе-

ний или теорем (по 10 баллов), 1 теорема с доказательством (15 баллов), 1 зада-
ча (15 баллов). 

Критерии оценки: 

отл

 – 

45

-

50

, 

хор – 35-44, уд – 25-34. Общая оценка ставится 

по сумме баллов за первую и вторую части курса: отл – 90-100, хор – 70-89, уд 
– 50-69. По аттестации преподавателя, ведущего лабораторные занятия, сумма  
может быть изменена на 1-2 балла.  

15 

Литература 

1.

Лавров  И.А.,  Максимова  Л.Л.  Задачи  по  теории  множеств,  математической 
логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова.  – М.: Физмат-
лит, 2001. – 255 с. 

2.

Лексаченко  В.А. Логика. Множества. Вероятность /  В.А. Лексаченко.  – М.: 
Вузовская книга, 2001. – 128 с.   

3.

Лихтарников Л.М., Сукачева Т.Г. Математическая логика: Курс лекций: За-
дачник – практикум и решения: Учеб. пособие / Л.М. Лихтарников, Т.Г. Су-
качева. – СПб.: Лань, 1999. – 285 с.   

4.

Гладкий  А.В.  Математическая  логика:  Учеб.  пособие  /  А.В.  Гладкий.  –  М., 
1998. – 479 с. 

5.

Петрова Л.П., Садовский Б.Н. Логика высказываний / Л.П. Петрова, Б.Н. Са-
довский. – Воронеж: ВГУ, 1989. – 24 с. 

6.

Петрова  Л.П.,  Садовский  Б.Н.  Логика  предикатов  /  Л.П.  Петрова,  Б.Н.  Са-
довский. – Воронеж: ВГУ, 1989. – 18 с. 

7.

Ершов  Ю.Л.,  Палютин  Е.А.  Математическая  логика  /  Ю.Л.  Ершов, 
Е.А.Палютин. – М.: Наука, 1979. – 320 с. 

8.

Мендельсон  Э.  Введение  в  математическую  логику  /  Э.  Мендельсон.  –  М.: 
Наука, 1976 – 320 с. 

9.

Шенфилд Дж. Математическая логика / Дж. Шенфилд. – М.: Наука, 1975. – 
528 с. 

10.

Клини С. Математическая логика / С. Клини. – М.: Мир, 1973. – 480 c. 

11.

Столл Р.Р. Множества. Логика. Аксиоматические теории / Р.Р. Столл. – М.: 
Просвещение, 1968. – 230 c. 

12.

Новиков  П.С.  Элементы  математической  логики  /  П.С.  Новиков.  –  М.: 
ГИФМЛ, 1959. – 400 c. 

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

1.1. Определение логического следствия 

1.1.1. Определение высказывания и предиката. 



Высказывание 

- это предложение, относительно которого имеет смысл утвер-

ждать,  что  оно 

истинно

  или 

ложно

. 



Например,  “5 3



”,  “

5

3



”,  “Дюма-сын 

есть сын Дюма-отца”, “

7

5

5

7



”. 



Предикат

 - предложение, относящееся к од-

ному  или  нескольким  неопределенным  объектам,  которое  превращается  в  вы-
сказывание всякий раз, когда все входящие в него неопределенные объекты за-
менены их конкретными представителями. 



Например, “

3

x



 ”, “прямая 

l

 па-

раллельна  прямой 

m

”. 



Имена  неопределенных  объектов  называются 

пере-

менными

  данного  предиката.  Каждая  переменная  имеет  свою 

область измене-

ния,

 которая должна явно или неявно указываться при задании предиката. 



Ес-

ли область изменения каждой переменной данного предиката состоит из един-
ственного элемента, то предикат по существу является высказыванием; поэтому 
мы 

будем считать высказывание частным случаем предиката

.

16 

1.1.2. Определение умозаключения, посылок и заключения.  



Пусть 

1

2

,

,

n

A A

A

 и 

B

 –предикаты. Утверждение типа “Из 

1

2

,

,

n

A A

A

следует 

B

” независимо от того, на чем оно основано,  называют  

умозаключением

, пре-

дикаты 

1

2

,

,

n

A A

A

-  его 

посылками

,  предикат 

B

  –

заключением

. 



Например, 

“Из   

x

y



, 

y

z



  следует,  что 

x

z



”. 



В  курсе  математической  логики,  в  ос-

новном,  изучаются 

логические  умозаключения

,  выражаемые  словами  “Из 

1

2

,

,

n

A A

A

логически  следует 

B

”  или  формулой 

1

2

,

,...,

|

n

A A

A

B



.  В  приведен-

ном выше примере, как мы вскоре увидим, заключение не является 

логическим

следствием посылок, но является 

следствием в теории 

вещественных чисел. 

1.1.3. Определение интерпретации и контрпримера.  



Интерпретацией 

 списка предикатов будем называть придание всем его сло-

вам 

произвольных

 смысловых значений, при котором 

форма 

предикатов не ме-

няется, а сами предикаты становятся высказываниями, т.е. определенно истин-
ными или ложными предложениями. 



Форма

 предложения с точки зрения ло-

гики  определяется  следующими  семью  словами  и  словосочетаниями  или  их 
языковыми эквивалентами:  

“не”, “и”, “или”,  “если...то”, “если и только если”, 

“для любого”, “существует”

 –  этим  выражениям  во  всех  интерпретациях  должны  придаваться  обычные 
смысловые  значения. 



Контрпримером

  к  умозаключению 

1

2

,

,...,

|

n

A A

A

B



называется такая его интерпретация, в которой все посылки истинны, а заклю-
чение  ложно. 



Например,  к  умозаключению 

,

|

x

y y

z

x

z



  

  можно  приве-

сти  следующий  контрпример:  Дюма-сын  –  сын  Дюма-отца,  Дюма-отец  –  сын 
Дюма-деда,  следовательно  (?!),  Дюма-сын  –  сын  Дюма-деда.  “Словарь”  этой 
интерпретации таков: 

x

  –  Дюма-сын, 

y

– Дюма-отец, 

z

– Дюма-дед, 



  –  явля-

ется сыном.  

1.1.4. Определение логического следствия и следствия в теории. 



Будем говорить, что заключение 

B  логически следует 

из посылок 

1

2

,

,...,

n

A A

A

, 

и  писать 

1

2

,

,...,

|

n

A A

A

B



,  если  к  данному  умозаключению  не  существует 

контрпримера. 



Например, 

,

x

y y

z





|

x

z

 

  ,  что  показывает  построенный 

выше контрпример. 



Пусть 

T – 

некоторая теория. Говорят, что в 

этой

теории

из  посылок 

1

2

,

,...,

n

A A

A

, 

следует

B

  (и  пишут 

1

2

,

,...,

n

A A

A

B



T

,  или 

1

2

,

,...,

n

A A

A

B



),  если  список  посылок  можно  дополнить 

истинными  в 

T

утверждениями 

1

2

, ,

m

T T

T

,  так,  что  из  расширенного  списка  посылок  предло-

жение 

B

следует 

логически: 

1

2

1

2

,

,...,

, , ,

|

n

m

A A

A T T

T

B



.  Для  аксиоматической 

теории 

T

истинность 

того  или  иного  предложения  означает,  что  его  можно 

доказать строго логически, т.е. в конечном счёте установить, что оно 

логически 

следует 

из  аксиом  и  определений  данной  теории.  Для  иных  теорий  критерии 

истинности могут быть иными. Для констатации истинности  иногда  использу- 

17 

ется  обозначение  «

B



T

»  или  «

B



». 



В  арифметике  вещественных  чисел 

,

x

y y

z





x

z

 

.  Действительно,  эта  теория  включает  в  качестве  аксиомы 

или  теоремы  (это  зависит  от  конкретного  способа  её  построения)  следующее 
свойство  транзитивности  неравенств:  “Если 

x

y



  и 

y

z



,  то 

x

z



”.  Добавив 

его  к  двум  посылкам  рассматриваемого  умозаключения,  мы  уже  не  сможем  к 
полученному  рассуждению  найти  контрпример,  потому  что  добавленная  по-
сылка как раз означает, что в случае истинности первых двух посылок заклю-
чение  не  может  быть  ложно.  (Напомним,  что  выражениям  “если…то”,  “и”,  
входящим  в  добавленную  посылку,  должны  придаваться  их  обычные  смысло-
вые значения). 

1.1.5.  Упражнение.   

Доказать,  что  заключение  не  является  логическим  след-

ствием посылок. Определить, является ли оно следствием в теории. 

1.

Неверно, что  7  делится на 2 и на 3. Следовательно, 7 не делится на 2 и не 

делится на 3. 

2.

Если число 9 делится на 4, то оно делится на 2. Следовательно, если 9 не де-

лится на 4, то 9 не делится на 2. 

3.

Число 

n

 не делится на 2 или не делится на 3. Следовательно, неверно, что 

n

делится на 2 или на 3. 

4.

Если число 

n

  делится  на  2  и  на  5,  то 

n

  делится  на  10. 

n

  не  делится  на  10. 

Следовательно, 

n

 не делится на 2 и не делится на 5. 

5.

В множестве 

A

 не существует числа 

a

, которое удовлетворяет неравенству 

3

a



. Следовательно, для любого числа 

a

 из 

A

 справедливо неравенство 

3

a



. 

6.

Существует рациональное число, которое больше 0, и рациональное число, 

которое  меньше  1.  Следовательно,  существует  рациональное  число,  которое 
больше 0 и меньше 1. 

7.

Для любой  фигуры из данного списка верно, что она является треугольни-

ком  или  квадратом.  Следовательно,  любая  фигура  из  этого  списка  есть  тре-
угольник или все фигуры в данном списке являются квадратами. 

8.

Для любого числа 

a

 из множества 

A

 существует натуральное 

N

, такое, что 

a

N



. Следовательно, существует такое натуральное 

N

, что для любого 

a

 из 

A

 выполнено неравенство 

a

N



. 

1.2. Язык логики высказываний 

1.2.1. Логические связки.  



Как сказано выше, логическая 

форма

 предложения определяется семью пере-

численными  в  1.1.3  выражениями. 



  Первые  пять  из  них  называются 

логиче-

скими связками

; они изучаются в 

логике высказываний

. Последние два  - 

кван-

тором общности 

и 

квантором

существования

; их изучением занимается 

логи-

ка предикатов

. 



Логические связки и кванторы рассматриваются в логике как 

операции

, с помощью которых из данных предикатов, называемых 

операндами,

строятся более сложные предикаты. 



Для логических связок вводятся следую-

щие обозначения и названия: «неверно, что 

A

» –  

A



 (

A

) – 

отрицание

; «

A

  и