Элементы математической логики icon

Элементы математической логики




Скачать 318.06 Kb.
НазваниеЭлементы математической логики
Дата конвертации11.11.2012
Размер318.06 Kb.
ТипДокументы
1. /.doc
2. /Глава1.DOC
3. /Глава2.doc
4. /Глава3.doc
5. /Глава4.doc
6. /Глава5.doc
7. /Глава6.doc
8. /Глава7.doc
9. /Глава8.doc
10. /Глава9.doc
11. /Литерат.doc
12. /Матан.doc
13. /Оглавление.doc
14. /матанализ.doc
Билет №1. Интегральная сумма. Определенный интеграл, его геометрический смысл. Градиент скалярного поля (определения 1 и 2), свойства градиента.; (): y=2+sin X, y=0, x=0, x=2 z=sin, где x=et, y=t2; Билет №2
Элементы математической логики
Множества объектов, одно из фундаментальных в математике. В специальной литературе можно встретить различные толкования это понятия.
. Иногда бывает удобно наряду с обычными точками числового множества 
 и будем последовательно сопоставлять каждому элементу из 
Теория пределов функций
Теория пределов функций
 между прямой и положительным направлением оси ох. Если Р
Определение области задания функции
Определение Пусть функции f (X) и h (X) заданы на одном и том же множестве Х. Если функции f (X) и h (X) удовлетворяют соотношению h‘
К главе Математическая числовая система
1. Значения определенного инт не зависят от обозначения пределов интегрирования 2
Математический анализ
1. Значения определенного инт не зависят от обозначения пределов интегрирования 2



ГЛАВА 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ




§ 1.1 Простые высказывания и умозаключения


Если в повседневной жизни случается так, что нам недостает сведений о каком-то интересующем нас предмете, мы можем обратиться к справочникам, специалистам, т.е. использовать знания, добытые другими людьми. Но иногда мы пытаемся необходимые нам сведения получить самостоятельно, без использования чьих-либо знаний. Тогда можно прийти к нужному результату либо путем опыта, либо при помощи правильного рассуждения. К сожалению не все сомнения можно разрешить при помощи опыта. Рассмотрим следующую ситуацию. Вы находитесь в незнакомой местности и желаете добраться до ближайшего города и из него вылететь, допустим, в Санкт-Петербург. Единственное, что вам известно – между этими городами существует ежедневное авиасообщение, но вы не знаете, в котором часу вылетает самолет, а выяснить это не удалось. Тогда вместо поездки в аэропорт для выяснения времени отлета можно провести следующее рассуждение. « Поскольку ночью видимость плохая, то полет ночью более труден и менее безопасен, нежели днем. Кроме того, я знаю, что полет продолжается не более часа. Следовательно, если я прилечу ночью, то у меня возникнут трудности с транспортом или ночлегом. Поскольку транспорт устроен так, чтобы обеспечить пассажирам наибольшую безопасность и удобства ( sic ! ), то наиболее вероятным оказывается то, что самолет должен отлетать утром и уж во всяком случае днем, но не ночью»

Мы провели определенное рассуждение конкретного вида, называемое умозаключением. Присмотримся к тому, что мы делали. Сначала констатировали многие данные, рассматриваемые как несомненные даже до того, как начать рассуждение, например: «ночью видимость плохая», «полет продолжается не более часа», «пассажиры обеспечиваются безопасностью и удобствами», «я прилечу ночью», «у меня возникнут трудности с транспортом или ночлегом». Кроме того, мы располагаем некоторыми сведениями, которыми связываем предыдущие и которые получены как раз путем рассуждения, например: «поскольку ночью видимость плохая, то полет ночью более труден и менее безопасен, нежели днем», «если я прилечу ночью, то у меня возникнут трудности с транспортом или ночлегом», «наиболее вероятным оказывается то, что самолет должен отлетать утром». Сведения этой группы выведены нами из информации предыдущей группы. Поэтому можно сказать, что в рассуждениях такого рода, которые можно назвать умозаключениями, мы всегда имеем дело с двумя группами сведений (информации):

  1. Сведения, которыми мы располагаем до начала рассуждений.

  2. Сведения, которые выводятся из первой группы сведений путем рассуждения.

В математической логике сведения первого рода называют простыми высказываниями, т.е. это предложение, утверждающее что-то о чем-то. Рассматривая простое высказывание в определенных условиях времени и места, мы можем сказать, истинно оно или ложно, другими словами, что его логическое значение есть «истина» или «ложь». В нашем примере высказывание «ночью видимость плохая» в определенных условиях времени и места может быть как истинно, так и ложно. Высказывание «Петербург стоит на Неве» будет всегда истинным, а высказывание «число 2 больше числа 5» - всегда ложным.

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

«если я прилечу ночью, то у меня возникнут трудности с транспортом или ночлегом».

В математической логике для образования составных высказываний используются следующие основные грамматические связки: «не», «и», «или», «если.., то», «тогда и только тогда». Построение из данных простых высказываний нового составного высказывания называется логической операцией над высказываниями. Действия над высказываниями с применением логических операций называют алгеброй высказываний.

В алгебре высказываний все высказывания рассматриваются только с точки зрения их логического значения, а от содержания их отвлекаются. Считается, что каждое высказывание либо истинно, либо ложно и что ни одно высказывание не может быть одновременно истинным и ложным.

Высказывание обозначаются прописными латинскими буквами A, B, C,….подобно тому, как в алгебре числа обозначаются буквами a, b, cОсновные логические операции над высказываниями называются

  • Отрицание

  • Конъюнкция

  • Дизъюнкция

  • Импликация

  • Эквивалентность

Первая из них, отрицание, является унитарной операцией (от лат. unitas – единство), т.е. эта операция применима только к одному простому высказыванию. Все остальные операции являются бинарными (от лат. binarius – двойной), т. е. применимые к двум простым высказываниям.


Попытайтесь выделить простые высказывания из следующего составного высказывания:

« Если две стороны и угол между ними одного треугольника равны двум сторонам и углу между ними другого треугольника, то эти треугольники равны»

Если вы получите только два простых высказывания, то значит не совсем ясно представляете структуру составного высказывания (хотя этот ответ и будет верным); если получите пять простых высказываний, то слишком детализируете процесс.

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


§ 1.2 Логические операции над высказываниями

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



Определение 1. Отрицанием высказывания A называется новое высказывание, обозначаемое символом  A (читается: «неверно, что A» или, короче, «не A»), которое считается истинным, если A ложно, и ложным, если A истинно.

Например, для истинного высказывания « 2 больше 1» отрицанием будет ложное высказывание: « неверно, что 2 больше 1 » или короче « 2 не больше 1 ».

Зависимость логического значения отрицания  A от логического значения высказывания А можно выразить наглядно с помощью следующей таблицы, называемой таблицей истинности отрицания:


Таблица 1а. Таблица 1б.




А  A А  A




и л 1 0




л и 0 1


В таблице 1а символами “и” и “л” обозначены истинное и ложное высказывания. В таблице 1б вместо символов “и”, “л” стоят часто употребляемые в ряде прикладных дисциплин ( в том числе – информатики ) символы “1” ( истина) и “0” ( ложь ). Выбор применения того или типа символов оставляем на усмотрение читателя. Мы будем использовать обозначения таблицы 1а.

В строках первого столбца таблиц указаны два возможных логических значения высказывания А: “и” и “л” ; в строках второго столбца таблиц - соответствующие логические значения отрицания  A : “ л ” в первом случае и “и” - во втором.


Определение 2. Конъюнкцией двух высказываний A, B называется новое высказывание, образованное символом A  B ( читается: « A и B » ), которое считается истинным, если оба высказывания A, B истинны, и ложным, если хотя бы одно из них ложно. Высказывания A, B называются членами конъюнкции.

Например, для двух простых высказываний: А= “ 2 > 1 “ , В = “ 275 делится на 5 ” конъюнкция A  B = “ 2 > 1 и 275 делится на 5 ” будет истинным высказыванием. Если обозначить A = “ 2 > 1 “ – “и”, B = “ 275 делится на 2 ” – “л”, то A  B = “л”, т.к. одно из высказываний ложное.

Зависимость логического значения конъюнкции A  B от логических значений ее членов A и B можно выразить следующей таблицей, называемой таблицей истинности конъюнкции:



A B A  B A B A  B




и и и 1 1 1

и л л 1 0 0

л и л 0 1 0

л л л 0 0 0


В строках двух первых ее столбцов указаны всевозможные комбинации логических значений высказываний A и B, в строках третьего столбца - соответствующие логические значения конъюнкции A  B.

Из определения 2 видно, что союз “и” в алгебре высказываний употребляется в том же смысле, что и в повседневной речи. Но в обычной речи не принято соединять союзом “и” два высказывания, далекие друг от друга по содержанию. Например, употребленное на бытовом уровне высказывание:

Летом мы поедем на Канарские острова” и “ у меня украли шляпу”, скорее вызовет сочуствие в Вашем здоровье, чем восхищение познаниями в логике.

В авгебре высказываний рассматривается конъюнкция двух любых высказываний.


Определение 3 Дизъюнкцией двух высказываний A, B называется новое высказывание, обозначаемое символом A  B ( читается: “ A или B ” ), которое считается истинным, если хотя бы одно из высказываний A, B истинно, и ложным, если оба они ложны. Высказывания A, B называются членами дизъюнкции.

Например, для двух высказываний « 3 + 5 = 4 », « снег белый » дизъюнкция « 3 + 5 = 4 или снег белый » по определению будет истинным высказыванием.

Таблица истинности дизъюнкции, наглядно выражающая зависимость логического значения дизъюнкции от логического значения ее членов, имеет вид:





A B A  B A B A  B




и и и 1 1 1

и л и 1 0 1

л и и 0 1 1

л л л 0 0 0


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


Определение 4. Импликацией двух высказываний A, B называется новое высказывание, обозначаемое символически A  B ( читается :” если A, то B” ), которое считается ложным, если A истинно и B ложно, и истинным при всех других логических значений высказываний A, B . Высказывание A называется условием или посылкой, высказывание B заключением или следствием импликации.

Импликация читается также A  B читается также следующим образом: “ А влечет В“, или “ из А следует В “, или “ А имплицирует В “.

Таблица истинности импликации имеет вид:



A B A  B A B A  B




и и и 1 1 1

и л л 1 0 0

л и и 0 1 1

л л и 0 0 1


Согласно определению 4, можно рассматривать импликацию любых двух высказываний, даже если они не связаны между собой по содержанию, и истинность импликации определяется только логическими знаниями ее посылки и заключения.


Значение импликации для математических доказательств ( этот вопрос будет подробно рассматриваться ниже ) состоит в том, что из истинности импликации A  B и ее посылки А мы заключаем об истинности ее следствия В.


Определение 5. Эквивалентностью двух высказываний A, B называется новое высказывание, обозначаемое символически A  B ( читается :” A тогда и только тогда, когда B” или короче “А эквивалентно В “ ), которое считается истинным, когда оба высказывания A , B либо истинны, либо ложны, и ложным – в остальных случаях. Высказывания A, В называются членами эквивалентности.

Эквивалентность A  B читается также следующим образом: “ для того, чтобы А, необходимо и достаточно, чтобы В”, или “А, если и только если В“, или “если А, то В, и обратно“, или “А равносильно В“. Таблица истинности эквивалентности имеет вид:




A B A B A B A B




и и и 1 1 1

и л л 1 0 0

л и л 0 1 0

л л и 0 0 1


Например, эквивалентность: « треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда угол P равен углу Q » - истина, так как ее члены либо одновременно истинны, либо одновременно ложны.

Значение эквивалентности для математических доказательств состоит в том, что из истинности эквивалентности и истинности либо ложности одного из ее членов мы заключаем соответственно об истинности либо ложности другого ее члена.

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



Определение 6 Исключающей дизъюнкцией двух высказываний A, B называется новое высказывание, обозначаемое символом A B (читается: “ либо A, либо B”), которое считается истинным, когда одно и только одно из данных высказываний A, B истинно, и ложным в остальных случаях. Высказывания A, B называются членами исключающей дизъюнкции.

Например, для двух истинных высказываний « огонь красный », « трава зеленая » исключающая дизъюнкция « либо огонь красный, либо трава зеленая» будет ложным высказыванием. А высказывание « Либо утром восходит солнце, либо солнце не восходит никогда » будет истинным.

Таблица истинности исключающей дизъюнкции, имеет вид:



A B A B A B A B




и и л 1 1 0

и л и 1 0 1

л и и 0 1 1

л л л 0 0 0


Определение 7 Штрихом Шеффера двух высказываний A, B называется новое высказывание, обозначаемое символом A  B (читается: “ A не совместимо с B”), которое ложно только тогда, когда оба данных высказывания A, B истинны, и истинно в остальных случаях. Высказывания A, B называются членами штриха Шеффера.

Например, для двух ложных высказываний « горячий лед », « холодный огонь » штрих Шеффера « горячий лед не совместим с холодным огнем » будет истинным высказыванием. А высказывание « Холодный лед не совместим с горячим огнем » будет ложным.

Таблица истинности исключающей дизъюнкции, имеет вид:




A B A B A B A B




и и л 1 1 0

и л и 1 0 1

л и и 0 1 1

л л и 0 0 1


Определение 8. Штрихом Лукашевича двух высказываний A, B называется новое высказывание, обозначаемое символом A  B (читается: “ ни A, ни B”), которое истинно в том и только в том случае, когда оба данных высказывания A, B ложны, и ложно в остальных случаях. Высказывания A, B называются членами штриха Лукашевича.

Постарайтесь сами построить примеры, когда штрих Лукашевича будет истинным и ложным. Таблица истинности штриха Лукашевича вид:



A B A B A B A B




и и л 1 1 0

и л и 1 0 1

л и и 0 1 1

л л и 0 0 1


В следующем параграфе мы построим примеры, показывающие, что основные логические операции ( отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность ) выражаются через штрихи Шеффера и Лукасевича.


Примеры.

  1. Вернемся к предыдущему примеру. Надо выделить все логические операции,

использованные в составном высказывании:

« Если две стороны и угол между ними одного треугольника равны двум сторонам

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

Если вы обнаружите только одну логическую операцию, то совсем не поняли

параграфа; если вы получите три логических операции, то смело читайте

следующий параграф.

  1. Примените к двум высказываниям введенные логические операции (кроме отрицания) и оцените истинность составного высказывания:

А: « Число а меньше b »

В: « Число в представимо в виде b = a + с »

§ 1.3 Формулы исчислений и тавтологии



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

-  ( А  В ) читается как « отрицание конъюнкции » ;

- ( А С )  ( С  А ) читается, как « импликация дизъюнкции и эквивалентности»

-  ( А  В )  С читается, как « дизъюнкция отрицания конъюнкции высказываний

А , В и высказывания С» и т.д. ( Поупражняйтесь ! )


Чтобы уменьшить число скобок в составном высказывании, согласимся отрицание высказывания в скобки не заключать.

Логическое значение составного высказывания зависит только от логических значений образующих его элементарных высказываний. Оно может быть найдено на основании определений логических операций над высказываниями. Например, если высказывания А,. В - истинные, а С – ложное высказывание, то дизъюнкция


( А  В )  С


будет ложна, т.к. если конъюнкция ( А  В ) истинное высказывание ( таблица 2), отрицание  ( А  В ) - ложное ( таблица 1 ), то дизъюнкция двух ложных высказываний - ложное высказывание ( таблица 3 ).

Введем особые символы Р1, Р2,…,Рn , которые будем называть пропозиционными буквами. Из пропозиционных букв, логических символов и скобок можно составлять различные выражения, некоторые из них называются формулами.

Определение 1. Формулами исчисления высказываний являются:

а) каждая пропозиционная буква;

б) выражения  ( Ф ), (Ф)  (Е), (Ф)  (Е), (Ф)  (Е), (Ф)  (Е) в которых Ф и Е

сами являются некоторыми формулами исчисления.


Выражение  ( Ф ) называется отрицанием формулы Ф, выражения (Ф)  (Е) ,

(Ф)  (Е), (Ф)  (Е), (Ф)  (Е) - соответственно конъюнкцией, дизъюнкцией, импликацией и эквивалентностью формул Ф и Е.

Согласно определению 1, каждая формула исчисления высказываний является пропозиционной буквой, либо может быть получена из конечного числа пропозиционных букв путем многократного применения пункта б) сначала к исходным пропозиционным буквам, а затем к уже полученным перед этим формулам. Как и договаривались, для уменьшения числа скобок в формулах согласимся пропозиционную букву и отрицание формулы в скобки не включать. Например, выражение


( Р1  Р2 )  ( Р3  (Р2  Р1 ) )


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

1 Р2 ),  Р1  Р2 , (Р1  Р2 )  .


Формулы исчисления высказываний, образованные из пропозиционных букв Р1, Р2,…,Рn , логических символов и скобок, будем обозначать Ф (Р1, Р2,…,Рn ). Если в формуле Ф (Р1, Р2,…,Рn ).пропозиционные буквы заменить какими-либо высказываниями А1, А2, …., Аn, соответственно, то получим некоторое, вообще говоря составное высказывание, которое будем обозначать Ф (А1, А2, …., Аn ).


Определение 2. Пусть Ф (Р1, Р2,…,Рn ) формула исчисления высказываний, образованная из пропозиционных букв Р1, Р2,…,Рn , и пусть А1, А2, …., Аn - некоторые высказывания. Значением формулы Ф (Р1, Р2,…,Рn ) для высказываний А1, А2, …., Аn называется логическое значение высказывания Ф (А1, А2, …., Аn ), которое получается из данной формулы при замене пропозиционных букв Р1, Р2,…,Рn высказываниями А1, А2, …., Аn

Согласно этому определению, значение формулы Ф (Р1, Р2,…,Рn ) зависит только от данных высказываний А1, А2, …., Аn . Эту зависимость можно выразить наглядно с помощью таблицы из 2n строк и (n +1)-ого столбца. Число строк таблицы равно числу возможных комбинаций логических значений высказываний А1, А2, …., Аn , которые и отмечаются в строках первых n ее столбцов. В строках (n+1)-ого столбца указываются соответствующие значения данной формулы.

Например, для формулы  ( Р1 Р2)  Р2 таблица значений будет иметь вид:





А1 А2  ( Р1 Р2)  Р2




и и и

и л и

л и и

л л и


При определении значений последнего столбца были использованы определения операций отрицание, конъюнкции и дизъюнкции. К примеру, для второй строки такое значение было получено следующим образом: ( Р1  Р2) ложно, т.к. А1 –истина, А2 – ложно; тогда  ( Р1 Р2) – истина; следовательно  ( Р1 Р2)  Р2 – истина.


Определение 3. Формула исчисления высказываний Ф (Р1, Р2,…,Рn ), образованная из пропозиционных букв Р1, Р2,…,Рn называется тавтологией исчисления высказываний или тождественно истинной формулой, если ее значение для любых высказываний есть всегда “истина”.

Нахождение тавтологий является одной из основных задач исчислений высказываний, т.к. они выражают законы логического мышления, на которые мы опираемся при проведении логических доказательств.

Для каждой формулы исчислений высказываний легко проверить, является ли она тавтологией или нет. С этой целью можно составить таблицу ее значений, которая покажет какие значения ( и в каком случае ) имеет данная формула. В приведенном выше примере значения формулы  ( Р1  Р2)  Р2 было истинными для всех возможных значений пропозиционных букв. Следовательно, согласно определению 2, формула

 ( Р1  Р2)  Р2 является тавтологией. Однако, если число пропозиционных букв достаточно велико, то доказательство тавтологий через таблицы представляет существенную трудность. В таких случаях необходимо использовать принцип доказательства от противного. Его логическим обоснованием и реализацией в доказательствах тавтологий мы займемся в следующем параграфе.


В качестве упражнений решите следующие примеры:


1. Пусть А и В есть, соответственно, высказывания : « Этот треугольник равнобедренный» и « Этот треугольник правильный». Если мы образуем составное высказывание ( формулу исчисления )  А   В, то оно причитается : « этот треугольник не равнобедренный и не правильный». Теперь сами прочитайте следующие выражения:

а)  ( А В) б)  А   В в) (А  В)  А г)  ( А  В)   В


2. Следующее составное высказывание Р можно расчленить на простые и используя логические символы записать для него формулу исчисления.

Р =” если F делится на 2 и не делится на 3, то оно не делится на 6 . Результатом будет: А = «F делится на 2», В = «F не делится на 3», и С = «F не делится на 6». Формула исчислений примет вид: P = ( А  В )  С.


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

а) Р = «Произведение трех чисел равно нулю тогда и только тогда, когда одно из них равно нулю».

б) P = «Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний».


3. Из двух высказываний А и В можно построить составное высказывание с помощью операций отрицания и конъюнкции, которое было бы ложно тогда и только тогда, когда оба данных высказывания истинны. Формулой будет:  ( А  В )

Это действительно так, т.к. ( А  В ) истина, тогда и только тогда, когда оба данных высказывания истинны, а отрицание истинного высказывания – ложное высказывание.

Теперь сами постройте составное высказывание с помощью операций отрицания и конъюнкции, которое было бы

а) истинно тогда и только тогда, когда оба данных высказывания ложны.

б) ложно тогда и только тогда, когда А – истинно, а В - ложно.


4. Вычислим формулу  ( Р1  Р2 )  Р3 . В соответствии с рекомендациями параграфа составляем таблицу истинности и используя определения логических операций получаем результат




Р1 Р2 Р3  ( Р1  Р2 )  Р3




и и и и

и л и и

л и и и

л л и и

и и л л

и л л и

л и л и

л л л и


Теперь самостоятельно вычислить формулы


а)  ( Р1   Р2 )  ( Р3  Р2 ) б ) Р1  ( Р3  Р2 )   Р2


5. Доказать, что основные операции над высказываниями можно выразить через штрих Шеффера.

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

( А  А)   А ; ( А  В)   ( А  В ); ( (А В)  ( А  В) )  ( А  В )


( (А А)  ( В  В) )  ( А  В ); ( А  В )  ( А  ( В В))


(для проверки можно воспользоваться соответствующими таблицами истинности)


Доказать, что все основные операции над высказываниями можно выразить через штрих Лукашевича ( для доказательства потребуется составить только три формулы ).


§ 1.4 Основные тавтологии и равносильные формулы


Каждое логическое доказательства опирается на законы исчисления высказываний. Выясним логические основания наиболее распространенных в математике методов доказательств.


Теорема 1. Нижеприведенные формулы являются тавтологиями:

1.1 Р2 )  (  Р2  Р1 ) ( закон контрапозиции )

  1. [ (Р1 Р2 )  ( Р2  Р3 )]  ( Р1  Р 3 ) ( правило цепного заключения )

  2. 1  Р2 )  (  Р1   Р2 ) ( закон противоположности )

Доказательство. 1. Пусть А, В – некоторые высказывания. По определению импликация А  В ложна в том и только в том случае, когда А истинно, а В ложно, т.е. когда  В истинно, а  А ложно. Последнее, в свою очередь , возможно в том и только в том случае, когда импликация  В  А ложна. Таким образом, для любых двух высказываний члены эквивалентности имеют одинаковые значения, то по определению эквивалентности она истина и, следовательно сама формула исчисления (Р1 Р2 )  (  Р2  Р1 ) является тавтологией.

Данная формула дает логическое обоснование введению в математике принципа доказательства от противного. Этот принцип ( метод ) используется для доказательства теорем, выраженных в форме импликации “ А  В “. Для доказательства предполагают, что заключение теоремы В ложно и выводят отсюда, что условие теоремы А тоже ложно, т.е. доказывают истинность обратнопротивоположной импликации “  В  А ” . Отсюда делают заключение о справедливости данной теоремы. Последний вывод и опирается на доказанный нами факт. Мы дали теоретическое обоснование возможности использовать при доказательстве теорем принципа доказательство от противного.

Заметим, чтом метод от противного уже был использован нами при доказательстве в главе 1 факта существования несоизмеримых отрезков. Теперь мы установили, что база для проведения такого метода доказательства логически корректна.

  1. Пусть А, В, С - три высказывания. Допустим, что импликация А  С ложна ( мы

уже имеем право использовать принцип от противного ! ). Тогда по определению импликации высказывание А истинно, а С – ложно. Высказывание В может быть либо

истинным либо ложным. В первом случае будет ложна импликация В  С, а во втором случае будет ложна импликация А  В. Следовательно, независимо от логического значения высказывания В, конъюнкция (А  В)  (В  С) ложна. Таким образом, для любых трех высказываний значение формулы [ (Р1 Р2 )  ( Р2  Р3 )]  ( Р1  Р3 ) не может быть ложью, т.е. это тавтология.

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


А  А1 , А1  А2, А2  А3, ….., A n-1  Аn, A n  В,


где А1 , А2, А3, ….., A n-1, Аn - некоторые вспомогательные высказывания. Отсюда делают заключения о справедливости данной теоремы А  В. Этот вывод опирается на доказанную выше формулу.

3. Пусть А, В – некоторые высказывания. По определению эквивалентность А  В истинна в том и только в том случае, когда высказывания А и В оба истинны или оба ложны, что по определению отрицания равносильно тому, что  А и  В или оба ложны, или оба истинны. Последнее возможно в том и только в том случае, когда эквивалентность  А   В истинна. Таким образом для любых двух высказываний значения членов эквивалентности формулы (Р1  Р2 )  (  Р1   Р2 ) совпадают, следовательно, это тавтология.

В математике часто встречаются теоремы вида « Условие А равносильно условию В», что выражается также словами: « Для того чтобы имело место условие А, необходимо и достаточно , чтобы выполнялось условие В». Доказательство такой теоремы ( мы будем с ними очень часто иметь дело ) обычно сводится к доказательству двух утверждений

а) если имеет место условие А, то выполняется и условие В ( В необходимо для А ).

б) если выполняется условие В, то имеет место и условие А ( В достаточно для А )

Первое из них называется также прямой, второе – обратной теоремами. В большинстве случаев одновременно доказывается и необходимость и достаточность условия В для А. Для этого находится последовательность истинных эквивалентностей вида

А  А1 , А1  А2, А2  А3, ….., A n-1  Аn, A n  В,

где А1 , А2, А3, ….., A n-1, Аn - некоторые вспомогательные высказывания. Отсюда делают заключения о справедливости данной теоремы А  В.

Достаточно часто для доказательства того факта, что формула является тавтологией, используют так называемые “основные тавтологии”. Разбивая исходную формулу на “основные тавтологии” мы существенно упрощаем процесс таких доказательств.

Теорема 2 Приведенные ниже формулы исчисления высказываний являются

тавтологиями:


1. Р   Р - закон исключения третьего

  1.  ( Р   Р ) - закон отрицания противоречия

  1. 3.   Р  Р - закон двойного отрицания

  2. 4. Р  Р - закон тождества

5. ( Р  Р )  Р ( Р  Р )  Р законы идемпотентности

  1. 6. ( Р 1 Р2 )  (Р2  Р1 ) и ( Р1 Р2 )  (Р2  Р1 )

  2. законы коммутативности

  3. 7. [(Р 1 Р2 )  Р3 ] [Р1  (Р2  Р3 )] и [ (Р1 Р2 ) P3 ][(Р1  (P2  Р1)]

  4. законы ассоциативности

  5. 8. [(Р1 Р2 )  Р3][(Р1Р3)(Р2  Р3)] и [(Р1  Р2 )  Р3][(Р1Р3) (Р2 Р3)]

  6. законы дистрибутивности



Доказательство. Доказательства указанных законом достаточно просты. Для примера докажем закон 2. По определению отрицания, для любого высказывания А либо оно, либо его отрицание ложно и, следовательно, конъюнкция А   А ложна, а ее отрицание  ( А   А ) истинно. Т.о. значение формулы 2 для любого высказывания есть истина, что и доказывает 2-е утверждение теоремы.

Доказательство остальных законов предоставляем читателю в качестве упражнения

Если потребуется доказать, является ли тавтологией некоторая формула исчисления, например,


F = ( Р   Р )   ( Р   Р )  (   Р  Р )  ( Р  Р )  Р ,


то ответ следует незамедлительно - перед нами конъюнкция 1, 2, 3 и 4 законов, являющихся тавтологиями и, следовательно, она сама является тавтологией (конъюнкция истинных высказываний является истинной ).

Мы привели самые очевидные и простые законы логики. Материалы курса не позволяют охватить ряд других важные тавтологий ( законы де-Моргана и т.д. ) Тех, кто серьезно заинтересуется законами логики, отсылаем в список литературы для данной главы, помещенный в конце книги.

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

Определение 1. Две формулы исчисления высказываний Ф1 ( Р1, Р2, …, Рn ) и Ф2 ( Р1, Р2,…, Рn ), образованные из одних и тех же пропозиционных букв Р1, Р2,…, Рn называются равносильными, если значения их для любых высказываний совпадают.


Каждые две равносильные формулы будут иметь одну и туже таблицу значений и, наоборот, формулы, таблицы значений которых совпадают, равносильны. Этим замечанием можно пользоваться для установления равносильности данных формул.

Используя определение равносильности и результат Теоремы 1 (п.3 – закон противоположности) можно легко показать

Теорема 3. Две формулы исчисления высказываний Ф1 ( Р1, Р2, …, Рn ) и Ф2 ( Р1, Р2,…, Рn ), образованные из одних и тех же пропозиционных букв Р1, Р2,…, Рn, равносильны тогда и только тогда, когда их эквивалентность

. Ф1 ( Р1, Р2, …, Рn )  Ф2 ( Р1, Р2,…, Рn )


является тавтологией.


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

Необходимость.( в дальнейшем вместо этого слово будем применять символ  ).

Пусть формулы Ф1, Ф2 равносильны. Тогда они либо обе истинные, либо обе ложные. В обоих случаях эквивалентность является истинной а, следовательно, Ф 1  Ф2 является тавтологией.

Достаточность .( в дальнейшем вместо этого слово будем применять символ  )

Если Ф 1  Ф2 является тавтологией, то Ф 1 , Ф2 одновременно обе либо истинны либо ложны, а, следовательно, равносильны. Теорема доказана. 


На основании теорема 3 и введенных ранее определений можно указать большое число равносильных формул. В частности, равносильными являются следующие пары:


а) Р1  Р2 и  (  Р1   Р2 )

б) Р1  Р2 и  (  Р1   Р2 )

в) Р1  Р2 и  ( Р1   Р2 )

г) Р1  Р2 и  Р1  Р2

д) Р1  Р2 и ( Р1  Р2 )  ( Р2  Р1 )

е) Р1  Р2 и  ( Р1   Р2 )

Имея это в виду, говорят, что : а) операция конъюнкции может быть выражена через дизъюнкцию и отрицание; б) операция дизъюнкции может быть выражена через конъюнкцию и отрицание; …. , д) операцию эквивалентности можно выразить через конъюнкцию и импликацию и так далее. Для примера докажем, что пара б) является равносильной или, что то же самое (согласно теоремы 3.),

Р1  Р2   (  Р1   Р2 ). ( 1 )


Дизъюнкция Р1  Р2 истинна, кроме случая, когда Р1, Р2 ложны. Если они обе ложны, то  Р1 и  Р2 истинны, то  Р1   Р2 истина, и, следовательно,  (  Р1   Р2 ) – ложна. А эквивалентность ложных высказываний – истина. Если одна из Р1, Р2 ложна, то  Р1   Р2 – ложна и, следовательно, правая часть формулы (1) истинна. Если обе пропозиционные буквы истинны, то  Р1   Р2 является ложной и, следовательно, ( Р1  Р2) истинной. А эквивалентность истинных высказываний – истина. Следовательно, формула (1) является тавтологией.

Таким образом приходим к выводу, что все основные логические операции можно выразить через одну из следующих пар: конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание.

  1. Используя «технику доказательств» тавтологий ( на основе этой техники нами были доказаны все теоремы параграфа ), докажите следующие тавтологии:


а) ( P1  Р2 )  ( Р1  Р3 )  ( Р2  Р3 )

б) ( P1  Р2 )  [ ( Р1  Р3 )  ( Р2  Р3 ) ]

в) ( P1  Р2 )  ( Р2  Р3 )  ( Р1  Р3 )



  1. Какие из следующих формул являются тавтологиями


а) [ ( P1  Р2 )  ( Р1  Р3 ) ] [P1  ( Р2  Р3 )]

б) P1  [ ( Р1  Р3 )  ( Р2  Р3 )]

в)  ( P1  Р2 )   [ ( Р1  Р3 )  ( Р2  Р3 )]


§ 1.6 Предикаты и кванторы

В математике и других науках наряду с высказываниями мы встречаемся с выражениями, грамматически имеющими форму высказываний, но содержащими предметные переменные, т.е символы, замена которых в выражении на те или иные количественные ( качественные ) характеристики приводит к истинному или ложному высказыванию. Например, в выражении : « n – целое число:», символ n – является предметной переменной. Если вместо символа n поставим некоторое его значение, к примеру n = 2, то получим истинное высказывание « 2 – целое число ». Если выбрать более сложное выражение, типа « расстояние от точки А до точки М равно Х метров », то заменяя две предметные переменные М и Х соответственно на А и число 0, получим истинное высказывание: « расстояние от точки А до точки А равно 0 метров », а заменяя М и Х соответственно на А и 1 получим ложное высказывание « расстояние от точки А до точки А равно 1 метр ». Все подобные выражения называются предикатами. Предикаты могут содержать неограниченное число предметных переменных, однако мы будем рассматривать только так называемые одномерные предикаты ( т.е. содержащие одну переменную ).

Определение 1 Одномерным предикатом называется выражение, содержащее одну предметную переменную и обращающееся в высказывание при замене ее любой количественной или качественной характеристикой.

Например, в выражении « А - цвет из спектра» при замене А на качественную характеристику «черный цвет» получим ложное высказывание.


Одноместный предикат, содержащий предметную переменную х, обозначают А ( х ). Высказывание, в которое обращается предикат А ( х ) при замене переменной х на некоторое значение х0 , обозначают А ( х0 )


Определение 2. Значением предиката А(х) для переменной х0 называется логическое значение высказывания А ( х0 ), в которое обращается данный предикат при замене предметной переменной х на х0 ; если значение предиката А ( х ) для х0 есть «истина», то говорят что переменная удовлетворяет данному предикату, в противном случае говорят, что переменная не удовлетворяет данному предикату.

Например, относительно предиката « х > 2 » можно сказать, что значение его для чисел 3 и 1 есть, соответственно, «истина» и «ложь», и, следовательно, число 3 удовлетворяет, а число 1 не удовлетворяет этому предикату.


Определение 3. Два предиката называются равносильными, если значения их для переменных совпадают, другими словами, если они удовлетворяются одними и теми же переменными.

Например, если х – переменная, принимающая значение из поля вещественных чисел, то предикаты « x > 2 » и « х – 2 > 0 » равносильны.


Определение 4. Пусть А ( х ) и В ( х ) - предикаты, то если В ( х ) удовлетворяется любыми переменными, удовлетворяющими предикат А( х ), то предикат В ( х ) называется следствием предиката А ( х ).

Например, предикат “ n делится на 3 ”, где n принимает значения из поля вещественных чисел, есть следствие предиката « n делится на 6 » .

Сопоставляя определения 3 и 4, приходим к следующей теореме



Теорема 1. Два предиката равносильны тогда и только тогда, когда каждый из них является следствием другого.

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

 Пусть два предиката равносильны, то они удовлетворяются одними и теми же переменными. Следовательно, каждый из них является следствием другого.

 Доказательство обратного утверждения оставляем читателю.


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

а) тождественно истинным, если значение его для любых переменных есть “истина”

б) тождественно ложным, если значение его для любых переменных есть “ложь”

в) выполнимым, если существует по крайней мере одна переменная, для которой значение предиката есть “истина”.

Например, предикат “ х + 1 = х ” будет тождественно ложным, “ х = х ” - тождественно истинным, а “ х + 1 = 2 ” выполнимым для х = 1.

Очевидно, что каждый тождественно истинный предикат является выполнимым, но обратно неверно. Каждый выполнимый предикат будет не тождественно ложным и обратно, каждый не тождественно ложный предикат будет выполнимым.

Простейшими логическими операциями над предикатами, так же как и для высказываний, являются : отрицание, конъюнкция дизъюнкция, импликация и эквивалентность, которые обозначаются с помощью тех же символов, что и для высказываний. При этом от содержания предикатов отвлекаются, они рассматриваются только с точки зрения их значений, другими словами, равносильные предикаты не различаются. Мы не будем повторятся в определениях ( в качестве упражнения читатель без труда сможет их сформулировать на основе введенных ранее понятий ), однако приведем несколько примеров, комментирующих логические операции над предикатами.

Для предиката “ х больше 2” отрицанием будет предикат “ х не больше 2”. Число 1 данному предикату не удовлетворяет, а его отрицанию удовлетворяет.

Для предикатов “х  6” и ” x  8 ” конъюнкцией будет предикат “х  6 и x  8”. При этом конъюнкция будет иметь значение “истина” только для тех х, которые заключены в отрезке [ 6, 8 ] .

Для предикатов “х  6” и ” x  8 ” дизъюнкцией будет предикат “х  6 или x  8”. При этом дизъюнкция будет иметь значение “истина” для всех х из поля вещественных чисел ( данный предикат будет тождественно истинным )

Для предикатов “ целое число n делится на 6 ” и “ целое число n делится на 3 ”, импликацией будет тождественно истинный предикат “ Если целое число n делится на 6 , то целое число n делится на 3 “.

Эквивалентностью указанных предикатов будет предикат Целое число n делится на 6 тогда и только тогда, когда целое число n делится на 3 “. Для n = 12 данный предикат является истинным, а для n = 9 - ложным.

Предикаты широко используется в языках программирования ( наиболее часто в операторах «условие» ). Желающих более подробно ознакомится с теорией алгебры предикатов ( в том числе и многомерных предикатов ) отсылаем в список рекомендуемой литературы.

* * *


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


Определение 6. Пусть А (х) предикат со значениями переменной из некоторой совокупности элементов М. Универсальным высказыванием, соответствующим предикату А(х) называется высказывание « каждый элемент из М удовлетворяет предикату А (х) », которое обозначается символом (х) А(х) и считается истинным, если данный предикат тождественно истинный, и ложным – в противном случае.

Символ ( х) ( перевернутая первая буква английского слова Anu («любой»)) называется квантором общности по переменной х, его читают: « для всех х» или « для каждого х». Универсальное высказывание (х) А(х) читают кратко : « для всех х, А(х)». Говорят, что высказывание ( х) А(х) есть результат применения квантора общности к предикату А(х). Например, для предикатов « х = х » и « х больше 2 », определенных на поле вещественных чисел, соответствующие универсальные высказывания будут соответственно: ( х) ( х = х ) - читается « каждое вещественное число равно себе» (истинное ) и ( х) ( х > 2 ) – « каждое вещественное число больше 2 » ( ложное ).


Определение 7. Пусть А(х) предикат, определенный на совокупности элементов М. Экзистенциональным высказыванием, соответствующим А(х), называется высказывание: « существует элемент из М, удовлетворяющий предикату А(х) », которое обозначается символом ( х ) А(х), и считается истинным, если предикат А(х) тождественно истинный, и ложным – в противном случае.

Символ (х) (перевернутая первая буква английского слова Existence - «существование») называется квантором существования по переменному х , его читают:” существует х такой, что …” или “ для некоторого х …”

Экзистенциональное высказывание ( х ) А(х) читают кратко: « существует х такой, что А(х)» или « для некоторого х, А(х) ». Говорят, что высказывание ( х ) А(х) есть результат применения квантора существования к предикату А(х).

Например, для предикатов « x > 2 » и « х = х + 1 », определенных в поле вещественных чисел, соответствующие им экзистенциональные высказывания будут соответствовать

( х ) (x > 2 ) « существует вещественное число, большее 2 » (истинное) и

( х ) (x = х + 1) «существует вещественное число, равное себе плюс единица» (ложное).

С помощью кванторов общности и существования можно построить новые кванторы. Среди них важным является квантор существования и единственности, который обозначается символом (  х ) ( читается « существует один и только один х, такой , что …» или « существует точно один ( единственный ) х, такой, что …». Если применить к предикату А(х) квантор существования и единственности по переменному х, получим высказывание (  х ) А(х) (« существует единственный х, такой, что А(х)»). Это высказывание будет истинным тогда и только тогда, когда истинны два высказывания:

1) экзистенциональное высказывание (х ) А(х), соответствующее данному предикату (« существует, по крайней мере, один элемент из совокупности М, удовлетворяющий предикату А(х)»)

2) отрицание экзистенционального высказывания  (  х, х1) [ А(х)  А(х1)  х  х 1) ( «не существует двух разных элементов, удовлетворяющих данному предикату А(х) »).


* * *


Пользуясь введенными логическими символами каждое математическое высказывание можно записать формулой. Например, теорема арифметики

« Каждое целое число, делящееся на 4, делится на 2 » запишется формулой

(  n) ( 4/n 2/n ),

а теорему

« Каждое положительное вещественное число является квадратом некоторого вещественного числа» можно записать формулой


«( n) [ x > 0  ( у) ( x = y 2 )]»


При доказательстве теорем каждой математической науки используются тавтологии исчисления предикатов. Каждая формула, полученная из какой-либо тавтологии при замене входящих в нее предикатных букв определенными предикатами данной науки, является теоремой этой науки. В последующих главах мы будем широко использовать полученные результаты.

Добавить документ в свой блог или на сайт



Похожие:

Элементы математической логики iconВнеклассное мероприятие по математике на тему: "В мире логики Льюиса Кэрролла". (Для учащихся 8-х классов)
...

Элементы математической логики iconКонтрольная работа «Элементы математической статистики»
Для успешного выполнения контрольной работы по статистике необходимо ознакомится с рабочей программой курса, также необходимо пользоваться...

Элементы математической логики iconТема : Основные понятия математической логики
Автор, к своему стыду, до сих пор иногда путает  и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком...

Элементы математической логики iconАндрей николаевич колмогоров
Колмогоров сделал в мгу, был посвящен вовсе не математике: на семинаре С. В. Бахрушина он выступил с сообщением о Новгородском землевладении....

Элементы математической логики iconМуниципальное общеобразовательное учреждение «Средняя общеобразовательная школа с. Петропавловка Дергачёвского района Саратовской области»
«Алгебра», «Функции», «Уравнения и неравенства», «Геометрия», «Элементы комбинаторики, теории вероятностей, статистики и логики»,...

Элементы математической логики iconМоу игнатовская средняя общеобразовательная школа антикоррупционное образование
Основные элементы Государственного стандарта среднего ( полного) общего образования по истории и обществознанию ( базовый уровень)...

Элементы математической логики iconУчебно-методическое пособие по дисциплине «Логика» Троицк-2012 Предмет логики и этапы ее развития. Логика
Ее основателем является великий Аристотель (384-322 гг до н э.), хотя теория понятия начала развиваться уже учителем Аристотеля Платоном...

Элементы математической логики iconДокументи
1. /алгебра логики/Алгебра логики.doc
2. /алгебра...

Элементы математической логики iconПрограмма «Джордж Буль и его алгебра логики» Учебный курс предпрофильной подготовки для учащихся 9-х классов*
Элективный курс «Джордж Буль и его алгебра логики» ориентирован на учащихся, которые хотели бы связать свое будущее с точными науками,...

Элементы математической логики iconМетодические указания по выполнению выпускной квалификационной работы для студентов специальности
Охватывает элементы только данной системы (не имманентные – охватывают также элементы, выходящие за рамки данной системы (например,...

Элементы математической логики iconИонова Светлана Георгиевна, учитель информатики и икт г. Биробиджан, 2011 год Ионова С. Г. Основы логики на урок
Ионова С. Г. Основы логики на уроках информатики. Брошюра, в помощь учителю информатики, г. Биробиджан, 2011, 18 с

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы