1
Министерство образования Российской федерации
Воронежский государственный университет
конспекты лекций и упражнения по курсу
МАТЕМАТИЧЕСКАЯ ЛОГИКА
/Логика высказываний/
пособие для студентов специальностей 01.03.01, 01.05.01, 02.03.01
Воронеж
2015
Стр.1
3
Оглавление
1. Логика высказываний .............................................................................................................. 4
1.1. Определение логического следствия.................................................................................... 4
1.1.1. Определение высказывания и предиката. ................................................................. 4
1.1.2. Определение умозаключения, посылок и заключения. ........................................... 4
1.1.3. Определение интерпретации и контрпримера. ........................................................ 4
1.1.4. Определение логического следствия и следствия в теории. ................................... 5
1.1.5. Упражнение. ................................................................................................................ 6
1.2. Язык логики высказываний ................................................................................................... 6
1.2.1. Логические связки. ...................................................................................................... 6
1.2.2. Формулы логики высказываний. ............................................................................... 7
1.2.3. Упражнение. ................................................................................................................ 7
1.2.4. Формализация в логике высказываний. .................................................................... 8
1.2.5. Упражнение. ................................................................................................................ 8
1.2.6. Формализация необходимых и достаточных условий............................................. 9
1.2.7. Упражнение. ................................................................................................................ 9
1.3. Следствие в логике высказываний ..................................................................................... 10
1.3.1. Стандартные интерпретации. ................................................................................... 10
1.3.2. Таблицы истинности. ................................................................................................ 10
1.3.3. Упражнение. .............................................................................................................. 11
1.3.4. Таблицы истинности и логическое следствие. ....................................................... 11
1.3.5. Направленная табличная процедура. ...................................................................... 11
1.3.6. Примеры доказательств направленной процедурой. ............................................ 12
1.3.7. Примеры доказательств с разветвлением. .............................................................. 12
1.3.8. Упражнение. .............................................................................................................. 13
1.3.9. Упражнение. .............................................................................................................. 13
1.3.10. Определение логической эквивалентности, тавтологии и противоречия. ........ 14
1.3.11. Упражнение. ............................................................................................................ 15
1.3.12. Упражнение. ............................................................................................................ 15
1.3.13. Упражнение. ............................................................................................................ 15
1.3.14. Свойства логического следствия, эквивалентности, тавтологии и
противоречия. ...................................................................................................................... 15
1.3.15. Упражнение. ............................................................................................................ 16
1.4. Основные теоремы логики высказываний ......................................................................... 16
1.4.1. Теорема об отрицании, конъюнкции и дизъюнкции. ............................................ 16
1.4.2. Теорема об импликации и двойной импликации. .................................................. 17
1.4.3. Упражнение. .............................................................................................................. 17
1.4.4. Замечания об истории, терминологии и обозначениях. ........................................ 17
1.4.5. Нормальные формы................................................................................................... 18
1.4.6. Упражнение. .............................................................................................................. 19
1.4.7. Анализ и синтез контактных схем. .......................................................................... 19
1.4.8. Упражнение. .............................................................................................................. 21
1.4.9. Упражнение. .............................................................................................................. 21
1.4.10. Полные системы булевых функций....................................................................... 21
1.4.11. Упражнение. ............................................................................................................ 22
Литература ................................................................................................................................... 22
Стр.3
6
дует неравенство 2
контрпример:ab
Например, в теории действительных чисел из неравенства ab
a ab , как показывает согласованный с этой теорией
.
2, 1
Из этого примера, кстати, видно, что для построения согласованных с
данной теорией T интерпретаций предикатов этой теории не так уж много
возможностей: можно только придавать именам неопределенных объектов
допустимые конкретные значения.
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 , которое удовлетворяет неравенству
a
3 . Следовательно, для любого числа a из A справедливо неравенство
a 3 .
6. Существует рациональное число, которое больше 0, и рациональное число,
которое меньше 1. Следовательно, существует рациональное число, которое
больше 0 и меньше 1.
7. Для любой фигуры из данного списка верно, что она является треугольником
или квадратом. Следовательно, любая фигура из этого списка есть
треугольник или все фигуры в данном списке являются квадратами.
8. Для любого числа a из множества A существует натуральное N , такое,
что aN
a из A выполнено неравенство aN
1.2.1. Логические связки.
Как сказано выше, логическая форма предложения определяется семью перечисленными
в 1.1.3 выражениями. Первые пять из них называются логическими
связками; они изучаются в логике высказываний. Последние два -
квантором общности и квантором существования; их изучением занимается
логика предикатов. Логические связки и кванторы рассматриваются в
логике как операции, с помощью которых из данных предикатов, называемых
операндами, строятся более сложные предикаты. Для логических связок
. Следовательно, существует такое натуральное N , что для любого
.
1.2. Язык логики высказываний
не сле
Стр.6
7
вводятся следующие обозначения и названия: «неверно, что A» – A ( A) –
отрицание; «A и B» – AB
AB
– дизъюнкция; «если A, то B» – AB
только если B» – AB
(A ,B AB) – конъюнкция; «A или B» –
– импликация; «A, если и
– двойная импликация. Формальные определения
логических связок задаются в виде таблиц истинности, определяющих истинностные
значения сложных предикатов через истинностные значения
операндов:
A B A AB AB AB AB
и и л
и л
л и и
л л
и
л
л
л
и
и
и
л
1.2.2. Формулы логики высказываний.
В результате последовательного применения логических связок к простым
предикатам, обозначенным буквами, получаются формулы логики высказываний.
Порядок действий в них, как и в алгебраических формулах, задаётся с
помощью скобок. Например, для формулы ((( )A B A B B
))
) (
действия в порядке их выполнения можно пронумеровать следующим образом:
(((
))
1
A)
2
B)
4
(A B
3
5
Словами данную формулу можно прочесть так: если отрицание A влечёт B
и A влечёт B, то справедливо B. Как и в алгебре, в логике принято соглашение
о порядке действий, в соответствии с которым при отсутствии скобок
операции выполняются в следующем порядке:
, , , { , }
A B A B B
) (
)
(импликация
и двойная импликация считаются действиями одной ступени, то есть при отсутствии
скобок они выполняются в порядке слева направо). Например,
рассмотренную выше формулу можно записать в виде
(
порядок действий и смысл формулы будет иной:
1
2
4
1.2.3. Упражнение.
Записать формулу на обычном языке. Найти интерпретации предложений
A,,
1. A B C
(
2. ( .
(A B C)
B C, в которых она истинна и ложна.
.
A B C))
A
7. .
А В С
С А
8. А С В В С А В
.
. Если же опустить и оставшиеся четыре скобки, то
A B A B B
3
5
B
и
л
и
и
и
л
л
и
Стр.7
8
3. A B .
A B C)
(A B)
4. ( .
5. A A.
( B A)
6. А В С В С А
( B C)
.
9. А С А В С В С
10. .
11. А В С С В
А С В
А В А В С
.
12. .
С
1.2.4. Формализация в логике высказываний.
Сложности записи утверждения, сформулированного на обычном языке
общения, в виде логической формулы аналогичны проблемам перевода с одного
языка на другой. Правда, следует заметить, что язык формальной логики
существенно беднее любого языка общения, что значительно облегчает задачу
перевода, которую можно осуществлять, придерживаясь следующего алгоритма.
В предложении следует выделить основную его форму ( “не верно,
что ...”, “... и ...” , “... или ...”, “если …, то ...”, “ …, тогда и только тогда, когда
...” и т.п.) и заменить её на соответствующую логическую формулу
( ,,,A A B A B
A B A B ). Затем с каждой частью предложения, обо,
значенной
в полученной формуле буквами А и В и представляющей собой
самостоятельное утверждение, проделать ту же процедуру, если только
утверждение не оказывается простым высказыванием. После этого буквы А
и В в первоначальной формуле заменяются на полученные вместо них формулы.
Повторяем процесс формализации до тех пор, пока все буквы формулы
не будут соответствовать простым высказываниям. В процессе формализации
необходимо следить за тем, чтобы разные вхождения одного и того же
высказывания обозначались одной буквой, а разные высказывания были обозначены
разными буквами.
Например, формализуем утверждение “Произведение ab положительно в
том и только том случае, когда a и b оба положительны или оба отрицательны”.
Основная форма этого предложения – “ … в том и только том случае,
когда ...”, аналогичная форме “ …, тогда и только тогда, когда...”. Заменим
её на формулу AX
“a и b – оба положительны или оба отрицательны ”. A является простым
высказыванием, а X имеет форму “... или ...”, заменяем её на YZ
начальной формуле: A Y Z . Высказывания Y – “a и b – оба положительны
” и Z – “a и b – оба отрицательны ” имеют одну и ту же форму, которую
легче определить, переформулировав эти предложения без изменения смысла
следующим образом. Y – “a положительно и b положительно ”, Z – “a отрицательно
и b отрицательно ”. Форму “... и ...” этих предложений заменим
на формулы BC
и DE
Z , получим окончательно: A B C D E
. Подставляя их в основную формулу вместо Y и
. B – “a – положительно”,C – “b
– положительно ”, D – “a – отрицательно”, E – “b – отрицательно ” – простые
высказывания.
1.2.5. Упражнение.
Записать следующие утверждения в виде формул логики высказываний.
А В
.
, где A – “ Произведение ab положительно ” и X –
в перво
Стр.8