КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

“Тобольская государственная социально-педагогическая академия

им. Д.И. Менделеева”

Валицкас А.И.

КОНСПЕКТ ЛЕКЦИЙ ПО

МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Учебно-методическое пособие для студентов

Физико-математических специальностей

Рекомендовано

УМО по математике педвузов Волго-Вятского региона в

качестве учебного пособия для студентов

физико-математических специальностей высших учебных заведений

 

 

Тобольск – 2010

ББК 22.12 я 73 совета Тобольской государственной социально- В 15педагогической академии им. Д.И. Менделеева  

С О Д Е Р Ж А Н И Е

П Р Е Д И С Л О В И Е

Первые две главы “Алгебра высказываний” и “Алгебра предикатов” содержат традиционный материал по неформальному изложению исчислений высказываний и… Большое внимание уделено в третьей главе различным вопросам построения… Автор выражает благодарность всему коллективу кафедры алгебры, геометрии и ТиМОМ ТГСПА им. Д.И. Менделеева за…

Понятие высказывания

Математика, как это ни кажется странным, – наука устная: математики, рассуждая, оперируют высказываниями, именно общение является питательной средой… Определение – это лишь введение синонима, заменяющего некоторое описание… Таким образом, давая очередное определение, мы вынуждены опираться на неопределённые до сих пор понятия и их…

Язык исчисления высказываний

Примеры: 1. “Сейчас температура воздуха на улице от –25 до –30 градусов Цельсия”, “5 – простое число”, “Сегодня скорость ветра в г. Тобольске больше… 2. “Сейчас температура воздуха на улице от –25 до –30 градусов Цельсия” и “5 –… Говоря формально, некоторые из использованных в этих примерах утверждений высказываниями не являются: их невозможно…

Примеры формул и не формул

Формулы	Использованные правила	Не формулы	Нарушенные правила
	a (Ф1) (Ф2) (Ф2)		(a) – не формула (Ф2)
(a Ú b)	a (Ф1) b (Ф1) (a Ú b) (Ф2)	ab	(Ф2)
(® c)	a (Ф1) b (Ф1) c (Ф1) (a Ù b) (Ф2) (Ф2) (® c) (Ф2)	a Ú b Ù c	нет скобок (Ф2)
	a (Ф1) c (Ф1) (Ф2) (с « ) (Ф2) (Ф2)		с « – не формула (Ф2)

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

Несмотря на то, что отсутствие скобок является ошибкой при написании формулы, самые внешние скобки в формуле можно опустить, не нарушая её смысла. Поэтомув дальнейшем для упрощения записи условимся в формулах допускать отсутствие самых внешних скобок (их всегда можно поставить, восстановив status quo). Таким образом, по-прежнему ошибочна запись a Ú b Ù c, но допустимо выражение с « , т.к. оно станет формулой после добавления внешних скобок: (с « ).

Иногда для экономии места применяют следующее правило восстановления скобок по умолчанию:

(С1): скобки в формуле расставляются в несколько проходов, рассматривая входящие в неё символы слева направо.

(С2): на каждом проходе обрабатываются логические связки одного из типов в соответствии с их приоритетами: , Ù , Ú , ® , « (это значит, что двигаясь слева направо, вначале находят первое ещё не обработанное отрицание и обрабатывают его в соответствии с правилом (С3), при отсутствии таковых – первую ещё не обработанную конъюнкцию, затем – дизъюнкцию, далее – импликацию и, наконец, эквивалентность, и.т.д).

(С3): обработка отрицания состоит в расстановке всех скобок в формуле, стоящей под этим отрицанием (в соответствии с правилами (С1)–(С4)).

(С4): обработка остальных логических связок w Î {Ù , Ú , ® , «} состоит в нахождении их минимальных формул-аргументов Ф₁ , Ф₂ и расстановке внешних скобок для получения выражения (Ф₁ w Ф₂).

Проиллюстрируем это правило на нескольких примерах:

Примеры: 1. Для выражения a Ú b Ù c после первого прохода получится выражение a Ú (b Ù c) – конъюнкция обрабатывается раньше дизъюнкции, а при втором проходе – формула (a Ú (b Ù c)).

2. Для выражения a ® b Ù c « c Ù d ® a результаты проходов таковы:

а. a ® (b Ù c) « (c Ù d) ® a (обработано две конъюнкции),

б. (a ® (b Ù c)) « ((c Ù d) ® a) (обработано две импликации),

в. ((a ® (b Ù c)) « ((c Ù d) ® a)) (обработана эквивалентность).

3. Для выражения a ® b Ù (c « c) Ù d ® a результаты будут следующими:

а. a ® ((b Ù (c « c)) Ù d) ® a (обработано две конъюнкции),

б. ((a ® ((b Ù (c « c)) Ù d)) ® a) (обработано две импликации).

4. Для выражения Ú a Ù bÚ результаты проходов таковы:

а. Ú a Ù bÚ

(обработано два отрицания),

б. Ú (a Ù b)Ú

(обработана конъюнкция),

в. ((Ú (a Ù b))Ú )

(обработано две дизъюнкции).

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

 

 

Истинностные значения формул

Истинность или ложность элементарных высказываний оставляется на совести той области знания, к которой они относятся. Логика позволяет по заданным… Прежде, чем переходить к формальным рассуждениям, введём следующие соглашения:… Теперь любой формуле исчисления высказываний A(x1 , … , xn) от пропозициональных переменных x1 , … , xn можно…

Законы логики, противоречия, выполнимые

И равносильные формулы

Примеры предыдущего параграфа показывают, что таблицы истинности формул могут быть разнообразны. Формулы, принимающие при любых наборах значений… Как следует из определений, для того, чтобы проверить к какому именно виду… Пример: Определить вид формулы A = (® a) « (a Ú b).

Совершенные дизъюнктивная и конъюнктивная

Нормальные формы

Пример. Найти формулу со следующей таблицей истинности: Если формула A(x1 , x2 , x3 ) – искомая, то A(x1 , x2 , x3 ) = 1 Û

Булевы функции

После того как каждой формуле A(x1 , … , xn) при любом наборе x1 = e1 , … … , xn = en (ei Î {0, 1}, 1 £ i £ n) значений её… f : ® B может быть задана с помощью таблицы, являющейся (в силу § 5) таблицей… Теорема (о реализации булевых функций формулами).Любая булева функция реализуется формулой исчисления высказываний. …

Логическое следование

Понятие логического следования является одним из важнейших в математической логике и имеет непосредственное отношение к жизни. Нам часто приходится… Пусть А1 , … , An , A – формулы исчисления высказываний от переменных x1 , … ,… Примеры: 1. Будет ли a ® b логическим следствием формул , b ?

Некоторые применения алгебры высказываний

Примеры: 1. Правильно ли следующее логическое рассуждение: “Когда выпадает снег, птицы улетают на юг. Если птицы улетели на юг, то скоро наступит… Обозначим элементарные высказывания буквами: a := “Выпал снег”, b := “Птицы… 2. Оцените правильность логического вывода: “Если a < b, то b – a > 0. Если a ³ b, то a – b ³ 0. Либо…

ГЛАВА II. АЛГЕБРА ПРЕДИКАТОВ

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

Примеры: 1.Высказывание “Волга впадает в Каспийское море” является истинным и говорит об одной конкретной реке Волге. Можно рассмотреть следующее… 2.“3 – простое число” – истинное высказывание об одном числе 3, а “y – простое… Точно так же можно образовывать “высказывания ” и от нескольких переменных. Например, “x > y” – “высказывание” от…

Логические операции над предикатами

Если заданы два предиката P(x₁ , … , x_n ) и Q(x₁ , … , x_n) с одной и той же областью определения Aⁿ и одним и тем же набором переменных, то можно рассмотреть предикаты (x₁ , … , x_n), (P Ù Q)(x₁ , … , x_n), (P Ú Q)(x₁ , … , x_n), (P ® Q)(x₁ , … , x_n), (P « Q)(x₁ , … , x_n), называемые соответственно отрицанием предикатаP, а также конъюнкцией, дизъюнкцией, импликацией и эквивалентностью предикатовP и Q. Эти новые предикаты определяются следующим образом: для любых a₁ , … , a_n Î A полжим (a₁ , … , a_n) = и при w Î {Ù , Ú , ® , « } (P w Q)(a₁ , … , a_n) = (P(a₁ , … , a_n) w Q(a₁ , … , a_n)).

Примеры: 1. Пусть на R заданы два предиката: P(x) = “x > 3” и Q(x) = = “x £ 5”. Тогда для любого a Î Rимеем

(a) = = “a £ 3”, (a) = = “a > 5”,

(PÙQ)(a) = “a > 3” Ù “a £ 5” = “3 < a £ 5”,

(PÚQ)(a) = “a > 3” Ú “a £ 5” = “a Î R” = 1,

(P®Q)(a) = “a > 3” ® “a £ 5” º Ú “a £ 5” = “a £ 3” Ú “a £ 5” = “a £ 5”,

(P«Q)(a) = “a > 3”« “a £ 5” º () Ú (“a > 3” Ù “a £ 5”) =

= (“a £ 3”Ù“a > 5”) Ú “3 < a £ 5” º 0 Ú “3 < a £ 5” º “3 < a £ 5”.

Ясно, что в этом примере верны следующие равенства множеств:

D₁() = D₀(P), D₀() = D₁(P), D₁(PÙQ) = D₁(P) Ç D₁(Q),

D₀(PÙQ) = D₀(P) È D₀(Q), D₁(PÚQ) = D₁(P) È D₁(Q), D₁(P®Q) = D₀(P) È D₁(Q),

D₁(P«Q) = (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)) (проверьте !!).

2. Пусть P(x, y) = “x² < y”, Q(x, y) = “y £ x” – два предиката на Z. Вычислим предикат P ® Q и его область истинности.

По определению для любых a, b Î Z : (P ® Q)(a, b) = (P(a, b) ® Q(a, b)) = = “a² < b” ® “b £ a” º Ú “b £ a” º “a² ³ b” Ú “b £ a”. Когда истинна последняя дизъюнкция ? Она истинна, если b £ a. Но учитывая, что a Î Z, имеем a £ a², так что из b £ a следует b £ a², и (P ® Q)(a, b) º “b £ a ”.

Как и ранее, нетрудно понять, что D₁(P ® Q) = D₀(P) È D₁(Q).

Оказывается, что отмеченные в этих примерах соотношения, связывающие множества D₁(P w Q) и D₁(P), D₁(Q), D₀(P), D₀(Q), справедливы всегда.

Лемма (об областях истинности).Пусть P(x₁ , … , x_n), Q(x₁ , … , x_n) – два предиката на множестве А. Тогда верны равенства множеств:

D₁() = D₀(P) = D(P) \ D₁(P),

D₁(P Ù Q) = D₁(P) Ç D₁(Q),

D₁(P Ú Q) = D₁(P) È D₁(Q),

D₁(P ® Q) = D₀(P) È D₁(Q),

D₁(P « Q) = (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)).

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

D₁() = {(a₁ ; … ; a_n) Î Aⁿ | (a₁ , … , a_n) = 1} =

= {(a₁ ; … ; a_n) Î Aⁿ | P(a₁ , … , a_n) = 0} = D₀(P) = D(P) \ D₁(P) = Aⁿ \ D₁(P),

что и требовалось.

Аналогично доказываются и остальные равенства множеств (в приводимых ниже вычислениях для краткости полагаем a = (a₁ ; … ; a_n), P(a) = P(a₁ ; … ; a_n)):

D₁(P Ù Q) = {(a₁ ; … ; a_n) Î Aⁿ | (PÙQ)(a₁ , … , a_n) = 1} =

= { aÎ Aⁿ | (P(a) Ù Q(a)) = 1} = { aÎ Aⁿ | (P(a) = 1) Ù (Q(a) = 1)} =

= { a Î Aⁿ | P(a) = 1} Ç { a Î Aⁿ | Q(a) = 1} = D₁(P) Ç D₁(Q),

D₁(P « Q) = { a Î Aⁿ | (P « Q)(a) = 1} = { a Î Aⁿ | (P(a) « Q(a)) = 1} =

= {a Î Aⁿ | ((P(a) Ù Q(a)) Ú ()) = 1)} =

= {a Î Aⁿ | (P(a) Ù Q(a) = 1) Ú (= 1)} =

= {a Î Aⁿ | P(a) Ù Q(a) = 1} È {a Î Aⁿ | = 1} =

= ({a Î Aⁿ | P(a) = 1} Ç {a Î Aⁿ | Q(a) = 1}) È

È ({a Î Aⁿ | = 1} Ç {a Î Aⁿ | = 1}) =

= (D₁(P) Ç D₁(Q)) È ({a Î Aⁿ | P(a) = 0} Ç {a Î Aⁿ | Q(a) = 0}

= (D₁(P) Ç D₁(Q)) È (D₀(P) Ç D₀(Q)).

Лемма доказана.

Упражнения: 1.Вычислите области истинности предикатов P, Q , , , P Ù Q , P Ú Q , P ® Q , P « Q , где P(x) = “x² > x ”, Q(x) = “x² – 4×x + 3 < 0”.

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

3.Сформулируйте и докажите лемму об областях ложности.

Рассмотренные логические операции над предикатами позволяют по заданным на множестве А предикатам строить новые предикаты. Другой способ построения новых предикатов дают кванторы. Квантор существования$ и квантор всеобщности" – это специальные математические знаки, служащие для сокращённого обозначения выражений “существует” и “для любого” соответственно.

Примеры: 1. Фразу “квадрат любого действительного числа неотрицателен” математики записывают так: " x Î R x² ³ 0 (читается: для любого действительного числа x выполнено свойство x² ³ 0).

2. Запись " m Î Z ($ n Î Z n < m) (читается: для любого целого числа m существует целое число n со свойством n < m) выражает тот факт, что у любого целого числа есть предшествующие ему целые числа.

В приведённых примерах написанные с помощью кванторов формулы являлись высказываниями. Оба этих высказывания были истинны, но не следует думать, что все высказывания, записанные с помощью кванторов истинны: почувствуйте разницу, прочитав и осмыслив следующие высказывания " x Î Z x ³ 0, " m Î N ($ n Î N n < m), " x Î R ($ y Î R |x – y| < x).

Пусть теперь P(x) – предикат от одной переменной на множестве А. Тогда записи " x Î A P(x) (для любого x Î А выполнено свойство P(x)) и $ x Î A P(x) (существует x Î А со свойством P(x)) являются высказываниями, не зависящими от переменной x. Говорят, что эти высказывания получены связыванием переменнойx с помощью квантора всеобщности " (и квантора существования $) соответственно. При этом высказывание " x Î A P(x) истинно тогда и только тогда, когда любой объектa из множества А принадлежит области истинности предиката P(x), оно ложно тогда и только тогда, когда хотя бы один объект a из множества А принадлежит области ложности предиката P(x). Высказывание $ x Î A P(x) истинно тогда и только тогда, когда хотя бы один объектa из множества А принадлежит области истинности предиката P(x), оно ложно тогда и только тогда, когда все объекты a из множества А принадлежат области ложности предиката P(x).

Примеры: 1. Если P(x) = “x делится нацело на 15” – предикат на Z, то высказывания " x Î Z P(x) и $ x Î Z P(x) ложно и истинно соответственно.

2. Если P(x) = “x² + 6×x + 100 > 0” – предикат на R, то " x Î R P(x) – истинное высказывание. А каковы высказывания $ x Î R P(x) , " x Î R (x) ?

Аналогично предыдущему случаю предикатов от одной переменной можно связывать кванторами и любую переменную в предикате от n переменных, получая при этом предикат от (n–1)-й переменной: если P(x₁ , … , x_n ) – предикат от n переменных на множестве А, то можно, связывая переменную x_i кванторами, образовать предикаты " x_i Î A P(x₁ , … , x_n ) и $ x_i Î A P(x₁ , … , x_n ) от (n–1)-й переменных x₁ , … x_i–1 , x_i+1 , … , x_n . Их области истинности состоят, по определению, из всех наборов (a₁ ; … ; a_i–1 ; a_i+1 ; … ; a_n) Î A^n–1 значений переменных x₁ , … x_i–1 , x_i+1 , … , x_n , для которых при любом (соответственно хотя бы при одном) x_i = a Î A истинно P(a₁ , … , a_i–1 ; a ; a_i+1 ; … ; a_n ) = 1.

Примеры: 1.Если P(x, y) = “x²+y² = 1” – предикат от двух переменных на множестве R, то предикат S(x) = (" y Î R P(x, y)) от одной переменной x принимает значение 0 (ложь) при любом x Î R (т.к., например, при y = 2 равенство x² + y² = 1 не верно, какой бы x Î R ни взять). Предикат T(x) = ($ y Î R P(x, y)) имеет область истинности D₁(T) = [–1; 1] (при любом x = a Î [–1; 1] можно найти y = со свойством x² + y² = 1).

2. Пусть А – множество всех прямых на плоскости, P(x, y, z) =”прямые x, y, z имеют общую точку” – предикат от трёх переменных x, y, z на А. Тогда предикат S(x, z) = (" yÎ A P(x, y, z)) от двух переменных x, z имеет пустую область истинности (?!), а предикат T(x, z) = ($ yÎ A P(x, y, z)) обладает тем свойством, что (T(x, z) = 1)Û (x Ç z ¹ Æ).

Для удобства дальнейших рассмотрений введём следующие сокращения:

1) вместо выражения " x₁ Î A (" x₂ Î A ( … (" x_n Î A P(x₁ , … , x_n))…)) будем писать " x₁ , … , x_n Î A P(x₁ , … , x_n), а $ x₁ , … , x_n Î A P(x₁ , … , x_n) – вместо $ x₁ Î A ($ x₂ Î A ( … ($ x_n Î A P(x₁ , … , x_n))…)). Здесь важно, что кванторы при всех элементах x₁ , … , x_n однотипны, т.е. либо все являются кванторами существования, либо же все – кванторами всеобщности, а также то, что все элементы x₁ , … , x_n выбираются из одного и того же множества А.

2) обозначение $ ! x_i Î A P(x₁ , … , x_i , … , x_n) будет использоваться для сокращения выражения “существует единственный элемент x_i во множестве А со свойством P(x₁ , … , x_i , … , x_n)”. Формально это высказывание записывается так: ($ x_i Î A P(x₁ , … , x_i , … , x_n)) Ù (" y_i Î A (P(x₁ , … , y_i , … , x_n) ® (y_i = x_i ))).

 

 

Равносильные и тождественно истинные предикаты

Два предиката P(x1 , … , xn ) и Q(x1 , … , xn ), определённые на множестве А (т.е. предикаты с условиями An Í D(P) Ç D(Q)), называют… Если An Í D1(P), т.е. " a1 , … , an Î A P(a1 , … , an ) = 1,… Примеры: 1.Равносильны ли предикаты P(x) = “> 1” и Q(x) = “x < 1” на множестве R+ = {r Î R | r > 0} =…

Теорема (об основных равносильностях с кванторами).

(1) " x Î A (" y Î A P(x, y, z)) º " y Î A (" x Î A P(x, y, z)), $ x Î A ($ y Î A P(x, y, z)) º $ y Î A ($ x Î A… (для разноимённых кванторов утверждения не верны),

Язык исчисления предикатов

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

Интерпретации формул исчисления предикатов

Ещё сложнее обстоит дело с формулами исчисления предикатов. Если рассмотреть какую-либо формулу исчисления предикатов, например, ($ x P(x, y)), то… Поэтому так же, как и для формул исчисления высказываний, невозможно говорить… Итак, при выяснении вопроса об истинностных значениях формул исчисления предикатов первостепенную роль играет понятие…

Приведённая и предварённая нормальные формы

По аналогии с исчислением высказываний, найдём некоторую нормальную форму, к которой можно равносильными преобразованиями привести любую формулу… С помощью известных основных равносильностей (A ® B) º (Ú B) и (A… Полученный вид формулы называется приведённым или приведённой формой (ПФ) . Таким образом, доказана следующая

О структуре современных математических теорий

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

Виды математических утверждений

Будем рассматривать высказывания о математических объектах, т.е. произвольные математические утверждения, которым можно приписать значение истина или ложь. Например, “2´2=5”, “2´2=4” и “сумма углов треугольника равна 180⁰” – математические высказывания.

Несколько упрощая и огрубляя действительность, можно сказать, что любое математическое утверждение можно записать в одном из следующих видов: " х Р(х) или $ х Р(х), где х – некоторая переменная, а Р(х) – предикат (на самом деле переменных может быть несколько). В общем виде будем писать Q x P(x), подразумевая под Q один из кванторов (Q Î {", $}). Конечно, сам предикат Р(х) при этом может иметь сколь угодно сложную структуру.

Например, знакомое из анализа утверждение (" e > 0 ($ n Î N (" k, m Î N (k, m ³ n) ® |a_m – a_n| < e))) представляет собой критерий Коши сходимости последовательности {a_n}. Здесь в качестве переменной использован символ e, а предикат Р(e) – это достаточно сложное высказывание с переменной ($ n Î N (" k, m Î N (k, m ³ n) ® |a_m – a_n| < e)) . На самом деле это высказывание правильно записать так: ($ n Î N (" k, m Î N (k ³ n) Ù (m ³ n) ® |a_m – a_n| < e)) . Таким образом, исходное утверждение состоит из кванторной приставки " e > 0 $ n Î N " k, m Î N и условия (k ³ n) Ù (m ³ n) ® |a_m – a_n| < e , имеющего вид импликации двух пре­ди­катов: одного – (k ³ n) Ù (m ³ n) и второго – |a_m – a_n|<e. Эти предикаты сами используют другие предикаты ³ , < и знаки функций – ведь последовательность – это функция, сопоставляющая каждому натуральному числу n значение а_n . Ещё более формально критерий Коши следует писать так:

" e ($ n (" k (" m ((e Î R Ù e > 0) Ù (n Î N) Ù (kÎ N Ù k ³ n) Ù (mÎ N Ù m ³ n)® |a_m – a_n| < e)))).

Здесь " e $ n " k " m – кванторная приставка, а всё остальное – высказывание с переменными, т.е. предикат, образованный с помощью логических связок из более простых предикатов e Î R , e > 0 , n Î N , kÎ N , mÎ N , k ³ n, m ³ n, |a_m – a_n| < e .

Как правило, встречающиеся математические утверждения можно записать в аналогичном виде: (кванторная_приставка) (предикат_1 ® предикат_2). Такая запись называется импликативной формой записи математического утверждения (т.к. в ней используется импликация).

Сразу напрашивается возражение: теорема Пифагора формулируется совсем иначе – ква­драт гипотенузы равен сумме квадратов катетов – где же тут импликация ? Просто при­ве­дённая формулировка не является строгой: например, в ней совсем не упоминается пря­мо­угольный треугольник, не ясно также, что такое его гипотенуза и катеты. Импликативная форма запи­си выглядит, например, так: " D АВС ((Ð АСВ = 90⁰) ® АВ² = АС² + ВС²). Здесь " D АВС – кванторная приставка, Ð АСВ = 90⁰ – предикат_1, АВ² = АС² + ВС² – предикат_2. Если опу­ститься (а может быть, подняться ?!) на ещё более высокую ступень формализма, то сле­дует ввести множество D всех треугольников и функции Ð С(х), АВ(х), ВС(х), АС(х), сопос­та­в­ляющие каждому треугольнику х = D АВС соответственно величину угла С и длины сто­рон АВ, ВС, АС. Тогда теорема Пифагора станет ещё более загадочной: " х Î D ((Ð С(х)=90⁰) ® АВ(х)² = АС(х)² + ВС(х)²). Хотя это и не предел формализации, но, как пра­вило, мы не будем забредать слишком далеко в подобные формалистические дебри.

Другой пример преобразования неимпликативного утверждения в импликативную форму: утверждение “1 является минимальным натуральным числом” может быть записано в импликативной форме так: " n (n Î N ® n ³ 1).

Упражнение: Преобразовать в импликативную форму и записать в виде формул с кванторами и предикатами следующие утверждения:

1) Сумма углов n-угольника равна (n–2)×p,

2) Квадрат действительного числа неотрицателен,

3) Натуральное число m делится на 12 тогда и только тогда, когда оно делится на 3 и на 4 ,

4) Если последовательность сходится, то сходится и её подпоследовательность с чётными номерами,

5) Диагонали параллелограмма делятся в точке пересечения пополам.

В дальнейшем ограничимся рассмотрением только простейших утверждений вида Q x (P(x) ® R(x)). По ним можно образовать следующие утверждения:

Q x (R(x)® P(x)), Q x (), Q x (),

которые называются соответственно обратным, противоположными контрапозиционным утверждениямик исходному. При этом само исходное утверждение Q x (P(x)® R(x)) называют прямым. Легко видеть, что контрапозиционное утверждение является противоположным к обратному, а утверждение обратное к обратному будет прямым, так же как и противоположное к противоположному.

Примеры: 1. Рассмотрим утверждение “если натуральное число n делится на 6, то оно делится на 2 и на 3”. Его импликативная форма:

" n Î N ((n M 6) ® (n M 2) Ù (n M 3))

– это прямое утверждение. Сформулируем другие виды утверждений:

обратное: " n Î N ((n M 2) Ù (n M 3) ® (n M 6)) – “если натуральное число n делится на 2 и на 3, то оно делится на 6”;

противоположное: " n Î N ((n 6) ® (n 2) Ú (n 3)) – “если натуральное число n не делится на 6, то оно не делится на 2 или на 3”;

контрапозиционное: " n Î N ((n 2) Ú (n 3) ® (n 6)) – “если натуральное число n не делится на 2 или на 3, то оно не делится на 6”.

2.Для прямого утверждения “если последовательности {a_n} и {b_n} сходятся, то сходится последовательность {a_n + b_n}” обратное звучит так: “если сходится последовательность {a_n + b_n}, то последовательности {a_n} и {b_n} сходятся”, противоположное – “если одна из последовательностей {a_n} или {b_n} не сходится, то не сходится последовательность {a_n + b_n}” и контрапозиционное – “если не сходится последовательность {a_n + b_n}, то одна из последовательностей {a_n} или {b_n} не сходится”.

Упражнение.Сформулировать все виды утверждений для прямых утверждений из предыдущего упражнения.

Каждое математическое утверждение, будучи высказыванием, является истинным или ложным. Поэтому для проверки истинности утверждения необходимо сопоставить его смысл с “окружающей математической действительностью” в самом широком смысле. Для доказательства истинности утверждения вида $ х Р(х) (не обязательно в импликативной форме) нужно найти хотя бы один объект а Î D(P) со свойством Р(a), т.е. хотя бы один элемент из области истинности предиката Р(х): а Î D₁(P). Для доказательства истинности утверждения вида " х Р(х) нужно проверить, что для любого объекта а Î D(P) выполнено свойство Р(a), т.е. доказать равенство D(P) = D₁(P).

Ложность утверждения вида Q x Р(х) равносильна истинности утверждения , где (см. основные равносильности с кванторами). Поэтому проверка ложности математического утверждения сводится к проверке истинности некоторого другого утверждения аналогичной структуры.

Примеры: 1. Истинно ли утверждение $ х Î Z (" y Î R x×y = 3) ?

Пусть х = х₀ Î Z фиксировано. Рассмотрим высказывание " y Î R x₀×y = 3.

Очевидно, что оно ложно, т.к. при у = 0 условие х₀×у = 3 не выполнено ни при каком х₀ Î Z. Поэтому исходное утверждение ложно.

2.Истинно ли утверждение " х Î N ($ y Î R x×y = 3) ?

Пусть х = х₀ Î N фиксировано. Рассмотрим высказывание $ y Î R x₀×y = 3 . Поскольку х₀ Î N, а значит, х₀ ¹ 0, то это высказывание равносильно утверждению $ y Î R y = , которое, очевидно, истинно (у явно вычислено по х₀). Поэтому исходное утверждение истинно.

3.Истинно ли утверждение " х Î N (" y Î N x×y + 1 > x + y) ?

Для х = х₀ Î N рассмотрим высказывание " y Î N (x₀×y + 1 > x₀ + y) , которое при х₀ = 1 принимает вид " y Î N y + 1 > 1 + y и является ложным. Значит оно истинно не для любого х₀ Î N, т.е. исходное утверждение ложно.

Упражнение.Найдите истинные и ложные утверждения из предыдущего упражнения.

Совершенно не обязательно, что истинность прямого утверждения влечёт истинность и дру­гих – обратного, противоположного и контрапозиционного. Например, утверждение " т, n Î N (m | n ® m £ n) истинно, но обратное к нему: " т, n Î N (m £ n ® m | n) ложно, как и противоположное " т, n Î N (m n ® m > n); контрапозиционное утверждение " т, n Î N (m > n ® m n) снова истинно.

На самом деле контрапозиционное утверждение Q x () и прямое Q x (P(x) ® R(x)) всегда равносильны, т.е. истинны или ложны одновременно. Это следует из известного закона контрапозиции (a ® b) « (® ). Эту равносильность иногда удобно использовать при доказательствах теорем: вместо прямого утверждения иногда удобнее доказывать контрапозиционное к нему.

Если прямое утверждение Q x (P(x) ® R(x)) истинно, то истинна импликация P(x) ® R(x) для некоторой совокупности объектов х (по крайней мере, для одного, если Q = $, и для всех, – если Q ="). Особое внимание уделим случаю Q =". Тогда предикат P(x) ® R(x) тождественно истинен, и вместо записи " x (P(x) ® R(x)) иногда кратко пишут Р(х) Þ R(x). При этом предикат Р(х) называется достаточным условиемдля R(x), а предикат R(x) – необходимым условиемдля Р(х) или логическим следствием предикатаР(х). Смысл названий состоит в том, что для любого объекта а для проверки истинности условия R(а) достаточно проверить истинность условия P(а), а для того, чтобы Р(а) было истинным, необходимо (т.е. обязательно требуется), чтобы истинным было высказывание R(а), истинность которого следует из истинности Р(а).

Если предикаты Р(х) и R(x) равносильны, т.е. " х (P(x) « R(x)), то иногда кратко пишут Р(х) Û R(x). Ввиду равносильности " х (P(x) « R(x)) º º " х ((P(x)® R(x)) Ù (R(x)® P(x))), условие R(x) не только необходимо, но и достаточно для Р(х), а Р(х), в свою очередь, необходимо для R(x) и является логическим следствием предиката R(x). Вот почему вместо Р(х) Û R(x) часто говорят “условие Р(х) необходимо и достаточно для выполнения R(x)”. Ясно, что Р(х) Û R(x) º (Р(х) Þ R(x)) Ù (R(x) Þ Р(х)) поэтому вместе с прямым утверждением в этом случае справедливо и обратное.

Примеры: 1. Условие R(х) º “натуральное число х делится на 2” является необходимым условием для Р(х) º “натуральное число х делится на 6”, т.к. высказывание Р(х) Þ R(x) (º " х (P(x)® R(x))) истинно. Обратное утверждение R(x) Þ Р(х) в данном случае не верно, т.к. например, 2M 2, но 26. Таким образом, условие R(х) необходимо, но не достаточно для Р(х).

2.Очевидно, что необходимым и достаточным условием для Р(х) º “натуральное число х делится на 6” является условие S(х) º “натуральное число х делится на 2 и на 3”. Таким образом, в этом случае справедливо Р(х) Û S(x).

Упражнение: Среди нижеследующих условий выделить необходимые, достаточные и необходимые и достаточные:

1) Р(х) = “два угла треугольника х и две его стороны равны между собой”, R(x) = “треугольник х равносторонний”,

2) Р(х) = “два угла треугольника х равны между собой”,

R(x) = “треугольник х равнобедренный”,

3) Р(х) = “три медианы треугольника х равны между собой”,

R(x) = “треугольник х равносторонний”,

4) Р(х) = “х Î N и х ³ 5”, R(x) º “х Î N и 2^х > 5”,

5) Р(х) º “х Î N и х ³ 5”, R(x) º “х Î N и 2^х > 5×х + 6”,

6) Р(х) º “последовательность {x_n} сходится”,

R(x) º “последовательность {x_2×n} сходится”,

7) Р(х) º “последовательность {x_n} сходится”,

R(x) º “последовательность {2×x_n} сходится”.

Некоторые методы доказательства теорем

Под теоремой обычно понимается математическое утверждение, которое можно доказать. Доказательством теоремыТ называется конечная последовательность… Таким образом, доказательство любой теоремы разбивается на части, каждая из… Аксиомы специфичны для каждой отрасли математического знания. Уже в школе знакомятся с аксиомами евклидовой геометрии,…

ГЛАВА III. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ

ТЕОРИИ

Формальные и неформальные аксиоматические теории

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

Примеры формальных аксиоматических теорий

I. Формальное исчисление высказываний. Алфавитэтой теории – это алфавит исчисления высказываний. Онсостоит из трёх групп символов: пропозициональных переменных: a, b, c, d, … , б₃₄₅ , v₉₆₄ , … , логических связок: , Ù , Ú , ® , « и служебных символов: ( , ).

Правила построения формул исчисления высказыванийизвестны:

(Ф1): любая пропозициональная переменная является формулой.

(Ф2): если A и В – формулы, то (A Ù B), (A Ú B), (A ® B), (A « B), – тоже формулы.

(Ф3): других формул нет.

Аксиомы формального исчисления высказыванийделятся на четыре группы схем аксиом, включающие 11 схем. Это значит, что в нижеследующих псевдоформулах буквы A , B , C – не символы алфавита теории, вместо них можно подставлять любые формулы исчисления высказываний. Таким образом, эти 11 схем аксиом на самом деле представляют бесконечное количество аксиом.

Группа аксиом импликации:

(И1): (A ® (B ® A))

(И2): ((A ® (B ® C)) ® ((A ® B) ® (A ® C)))

Группа аксиом конъюнкции:

(К1): ((A Ù B) ® A)

(К2): ((A Ù B) ® B)

(К3): ((A ® B) ® ((A ® C) ® (A ® (B Ù C))))

Группа аксиом дизъюнкции:

(Д1): (A ® (A Ú B))

(Д2): (B ® (A Ú B))

(Д3): ((A ® C) ® ((B ® C) ® (A Ú B ® C)))

Группа аксиом отрицания:

(О1): (A ® )

(О2): ( ® A)

(О3): ((A ® B) ® ( ® ))

В дальнейшем будем опускать в формулах некоторые скобки, предполагая, что их можно расставить по правилам восстановления скобок § 3 главы I.

В приведённом списке аксиом отсутствует логическая связка « . Это сделано из соображений экономии: известно, что эта связка является производной – она выражается через остальные. Желающие работать с ней, должны ввести ещё следующие две схемы аксиом:

Группа аксиом эквивалентности:

(Э1): ((A « B) ® ((A ® B) Ù (B ® A)))

(Э2): (((A ® B) Ù (B ® A)) ® (A « B))

Единственным правилом выводав формальном исчислении высказываний является уже знакомое правило Modus ponens (MP): .

Доказательством формулы Вв формальной теории исчисления высказываний называется конечная последовательность формул В₁ , … , В_n , где В_n совпадает с В, а каждая формула B_i (1 £ i £ n) либо является аксиомой, либо получена из предыдущих формул В_j и В_k (1 £ < i) по правилу Modus ponens, т.е. В_k = (B_j ® B_i) и применение правила (MP) таково: . Это значит, что из доказуемости формул B_j и B_j ® B_i постулируется возможность сделать вывод о доказуемости формулы B_i . Это далеко не очевидный логический ход, хотя многих птешит иллюзия, что он согласуется со здравым смыслом.

Формула В, для которой существует доказательство, называется доказуемой в формальном исчислении высказываний. В этом случае будем писать В . В частности, всякая аксиома А доказуема, т.к. её доказательством является последовательность формул, состоящая из единственной формулы А.

Примеры доказательств в формальном исчислении высказываний

1.А ® A

2. A Ù B ® B Ù A

3.

II. Формальное исчисление предикатов. Алфавитэтой теории – это алфавит исчисления предикатов. Онсостоит из пропозициональных переменных: a, b, c₉₉ , d₃₄₅ , … , объектных переменных: x, y, z₉₉ , t₃₄₅ , … , логических связок: , Ù , Ú , ® , « , предикатных символов: P⁽¹⁾( _ ), Q⁽¹⁾( _ ), … , P⁽²⁾( _ , _ ), Q⁽²⁾( _ , _ ), … , кванторов: " , $ и служебных символов: , и ( , ) .

Правила построения формул исчисления предикатовизвестны:

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

(Ф2): если P⁽ⁿ⁾( _ , … , _ ) – предикатный символ от n переменных и x₁ , … , x_n – объектные переменные, то P⁽ⁿ⁾( x₁ , … , x_n ) – формула исчисления предикатов, в которой все вхождения объектных переменных x₁ , … , x_n свободны, а вхождений других объектных переменных нет.

(Ф3): если A и В – две формулы, то (A Ù B), (A Ú B), (A ® B), (A « B), – тоже формулы, в которых свободны все вхождения объектных переменных, свободные в А или в В, и связаны все вхождения объектных переменных, связанные в А или в В.

(Ф4): если A(x) – формула хотя бы с одним свободным вхождением объектной переменнойx, то выражения (" x A(x)) и ($ x A(x)) – формулы, в которых связаны вхождения всех объектных переменных, связанных в А, а также все вхождения x, и свободны все вхождения объектных переменных, свободные в А, кроме переменной х. При этом формула A(x) называется областью действия квантора.

(Ф5): других формул нет.

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

Группа аксиом с кванторами:

("): (" x А(x)) ® А(t) , ($): А(t) ® ( $ x А(x))

Здесь t – переменная, отличная от переменной x.

Таким образом, получается 13 схем аксиом, которые на самом деле представляют бесконечное количество аксиом.

Правила выводав формальном исчислении предикатов:

(MP): ,

(В"): (введение квантора " ),

(В$): (введение квантора $ ),

Где С не содержит вхождений переменной x.

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

Примеры доказательств в формальном исчислении предикатов

 

1.(" x P(x)) ® ($ x P(x))

2. Анализ приведённого доказательства показывает, что аналогично можно обосновать правило вывода (правило силлогизма), которое можно использовать в дальнейшем. Обоснование следует доказательству примера 1.

1 · A ® B (дано)

2 · B ® C (дано)

3 · (B ® C) ® (A ® (B ® C)) (И1)

4 · (A ® (B ® C)) MP(2, 3)

5 · (A ® (B ® C)) ® ((A ® B) ® (A ® C)) (И2)

6 · (A ® B) ® (A ® C) МР(4, 5)

7 · A ® C МР(1, 6)

3. (" x P(x)) ® (" y P(y))

1 · (" x P(x)) ® P(y) (")

2 · (" x P(x)) ® (" y P(y)) (В")(1)

4. (" x (" y P(x, y))) ® (" y (" x P(x, y)))

1 · (" x (" y P(x, y))) ® (" y P(u, y)) (")

2 · (" y P(u, y)) ® P(u, v) (")

3· (" x (" y P(x, y))) ® P(u, v) силлогизм(1, 2)

4 · (" x (" y P(x, y))) ® (" u P(u, v)) (В")

5 · (" u P(u, v)) ® (" x P(x, v))(пример 3)

6 · (" x (" y P(x, y))) ® (" x P(x, v))силлогизм(4, 5)

7 · (" x P(x, v)) ® (" v (" x P(x, v)))(В")

8 · (" x (" y P(x, y))) ® (" v (" x P(x, v)))силлогизм(6, 7)

9 · (" v (" x P(x, v))) ® (" y (" x P(x, y)))(пример 3)

10 · (" x (" y P(x, y))) ® (" y (" x P(x, y)))силлогизм(8, 9)

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

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

Более формально, алфавит специальной теориисостоит из нескольких групп символов:

· достаточно большое количество переменных x, y, … , x₁₀₀ , … для обозначения объектов теории,

· символы выделенных элементов c, d, … , c₁₂₉ , … – константы– для обозначения объектов особого назначения,

· функциональные символы f , … , f , …для обозначения специфических операций и функций, используемых в аксиомах специальной теории,

· предикатные символы P, … , P, … для обозначения специфических предикатов, используемых в аксиомах специальной теории,

·Ù , Ú , ® , « , – логические связки,

·", $ – кванторы,

·служебные символы – ( , ) – скобки и , – запятая.

Понятие формулы специальной теории несколько усложняется из-за наличия функциональных символов. Вначале от простого к сложному вводится понятие терма (функционального выражения специальной теории) :

(Т1): любая объектная переменная является термом.

(Т2): любая константа (символ выделенного элемента) является термом.

(Т3): если t₁ , … , t_m – термы, а f ^(m) – один из функциональных символов теории, то f ^(m)(t₁ , … , t_m) – терм.

(Т4): других термов нет.

Теперь от простого к сложному строится понятие формулы специальной теории:

(Ф1): если t₁ , … , t_m – термы, а P ^(m) – один из предикатных символов теории, то P ^(m)(t₁ , … , t_m) – бескванторная формула, зависящая от всех переменных, участвующих в термах t₁ , … , t_m , причём все её переменные свободны.

(Ф2): если A и В – две формулы, то (A Ù B), (A Ú B), (A ® B), (A « B), – тоже формулы, в которых свободны все вхождения объектных переменных, свободные в А или в В, и связаны все вхождения объектных переменных, связанные в А или в В.

(Ф3): если A(x) – формула хотя бы с одним свободным вхождением объектной переменнойx, то выражения (" x A(x)) и ($ x A(x)) – формулы, в которых связаны вхождения всех объектных переменных, связанных в А, а также все вхождения x, и свободны все вхождения объектных переменных, свободные в А, кроме переменной х. При этом формула A(x) называется областью действия квантора.

(Ф4): других формул нет.

Система аксиом специальной теориисостоит из

· аксиом формального исчисления предикатов,

· специальных аксиом теории.

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

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

IV. Пример специальной теории: формальная арифметика. Алфавитсостоит из нескольких групп символов:

·достаточно большое количество переменных x, y, … , x₁₀₀ , … для обозначения натуральных чисел,

·1 – выделенный элемент,

· + , × – знаки бинарных арифметических операций сложения и умножения,

· = – единственный предикатный символ равенства чисел,

·Ù , Ú , ® , « , – логические связки,

·", $ – кванторы,

·( , ) – служебные символы (скобки).

Термы формальной арифметики – это просто арифметические выражения, которые строятся от простого к сложному так:

(АВ1): любая переменная является арифметическим выражением.

(АВ2): 1 – арифметическое выражение.

(АВ2): если A и В – арифметические выражения, то (А + В) и (А×В) – тоже арифметические выражения.

(АВ3): других арифметических выражений нет.

Примеры: 1.1 + x – не арифметическое выражение, т.к. нет скобок.

2. ((x + 1)×(z + t)) – арифметическое выражение.

Формулы арифметикитожеопределяются от простого к сложному:

(Ф1): если А, В – два арифметических выражения, то (А = В) – бескванторная формула, зависящая от всех переменных, участвующих как в А, так и в В, причём все её переменные свободны.

(Ф2): если A и В – две формулы, то (A Ù B), (A Ú B), (A ® B), (A « B), – тоже формулы, в которых свободны все вхождения объектных переменных, свободные в А или в В, и связаны все вхождения объектных переменных, связанные в А или в В.

(Ф3): если A(x) – формула хотя бы с одним свободным вхождением объектной переменнойx, то выражения (" x A(x)) и ($ x A(x)) – формулы, в которых связаны вхождения всех объектных переменных, связанных в А, а также все вхождения x, и свободны все вхождения объектных переменных, свободные в А, кроме переменной х. При этом формула A(x) называется областью действия квантора.

(Ф4): других формул нет.

Примеры: 1. ((x = 1) Ù (y×x+1 = 1)) – бескванторная формула со свободными переменными x и y.

2. ((x + 1)×(z + t) + 1) = (t) – не формула (лишние скобки в правой части).

3. (" t ((x + 1)×(z + t) + 1) = (t + x + 1)) – формула с квантором, связывающим переменную t и свободными переменными x, z.

Аксиомы формальной арифметикикроме аксиом исчисления предикатов включают несколько групп аксиом:

Аксиомы равенства:

Рефлексивность: (" x (x = x))

Симметричность: (" x (" y ((x = y) ® (y = x)))

Транзитивность: (" x (" y (" z (((x = y) Ù (y = z)) ® (x = z))))

Схема подстановки: для любых арифметических выражений А, В, С с выделенным вхождением выражения В в А (символически А = А(В)) следующая формула является аксиомой ((В = С ) ® (А(В) = А(С))), где А(С) – результат замены выделенного вхождения подвыражения В в А на С .

Это – очень сильная форма подстановки, её можно значительно ослабить.

Условимся для арифметических выражений А(x₁ , … , x_n) и В(y₁ , … , y_m) использовать краткую запись А(x₁ , … , x_n) ¹ В(y₁ , … , y_m) вместо отрицания .

Аксиомы операций сложения и умножения:

Существование и единственность следующего: (" x ($ ! y (y = x + 1)))

Единица – наименьший элемент: (" x ((x + 1) ¹ 1))

Равенство следующих: (" x (" y ((x + 1) = (y + 1)) « (x = y)))

Ассоциативность прибавления 1: (" x (" y ((x + (y + 1)) = ((x + y) + 1))))

Единица – нейтральна по умножению: (" x ((x×1) = x))

Связь сложения и умножения: (" x (" y ((x×(y + 1) = ((x×y) + x)))))

Схема формальной индукции

Для любой формулы арифметики А(x) со свободной переменной x следующая формула является аксиомой: ((А(1) Ù (" y (А(y) ® А(y + 1)))) ® (" x А(x))).

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

Примеры теорем формальной арифметики

Введём обычные обозначения: 2 = (1 + 1), 3 = (2 + 1) = ((1 + 1) + 1), 4 = (3 + 1) = (((1 + 1) + 1) + 1) , и.т.д.

1. (4 = (2 + 2))

1 · (" x (" y ((x + (y + 1)) = ((x + y) + 1)))) (аксиома ассоциативности +)

2 · (" y (((1 + 1) + (y + 1)) = (((1 + 1) + y) + 1))) (аксиома"(x = 1+1))

3 · (((1 + 1) + (1 + 1)) = (((1 + 1) + 1) + 1))(аксиома"(y = 1))

4 · (((1 + 1) + 1) + 1) = ((1 + 1) + (1 + 1))) (аксиома симметричности)

5 · ((1 + 1) = 2)(определение)

6 · ((1 + 1) = 2) ® (((1 + 1) + 1) + 1) = (2 + 2)) (подстановка)

7 · (((1 + 1) + 1) + 1) = (2 + 2)) МР(5, 6)

8 ·((((1 + 1) + 1) + 1) = 4) (определение)

9 · ((((1 + 1) + 1) + 1) = 4) ® (4 = (2 + 2)))(подстановка)

10 · (4 = (2 + 2)) МР(8, 9)

2.(2×2 = 4)

1 · (" x (" y ((x×(y + 1)) = ((x×y) + x)))) (аксиома связи + и× )

2 · (" y ((2×(y + 1)) = ((2×y) + 2)))) (аксиома"(x = 2))

3 · ((2×(1 + 1)) = ((2×1) + 2))) (аксиома"(y = 1))

4 · (" x ((x×1) = x)) (аксиома о нейтральности 1)

5 · 2×1 = 2 (аксиома"(5))

6 · ((2×1 = 2) ® ((2×1) + 2) = (2 + 2))) (подстановка)

7 · (((2×1) + 2) = (2 + 2)) МР(5, 6)

8 · ((2 + 2) = 4) доказано

9 ·(((2 + 2) = 4) ® (((2×1) + 2) = 4)) (подстановка)

10 ·(((2×1) + 2) = 4)МР(8, 9)

11 · (2 = (1+ 1)) (определение)

12 · (2 = (1+ 1)) ® ((2×2) = ((2×1) + 2))) (подстановка в 3)

13 ·((2×2) = ((2×1) + 2)) MP(11, 12)

14 · ((2×2) = ((2×1) + 2)) ® (2×2 = 4) (подстановка 10 в 13)

15 · (2×2 = 4)MP(13, 14)

Приведём ещё пример неформального доказательства в формальной ариф­метике, использующий правила вывода и аксиому индукции. Докажем, формулу" x ((x = 1) Ú ($ y ((x = 2×y) Ú (x = 2×y + 1)))), выражающую тот факт, что любое натуральное число либо чётно, либо нечётно.

Пусть А(x) = (x = 1) Ú ($ y (x = 2×y) Ú (x = 2×y + 1)). Тогда ясно, что А(1) доказуемо, т.к. А(1) = ((1 = 1) Ú ($ y (1 = 2×y) Ú (1 = 2×y + 1))) , и первый аргумент этой дизъюнкции является аксиомой (?!). Теперь, чтобы воспользоваться схемой индукции, нужно доказать (" z (А(z) ® А(z + 1))).

Если доказано А(z) = ($ y ((z = 2×y) Ú (z = 2×y + 1))), то А(z+1) означает, что ($ t ((z + 1 = 2×t) Ú (z + 1 = 2×t + 1))). В том случае, когда z = 2×y, имеем z + 1 = 2×y + 1, и в качестве искомого t можно взять t = y. В случае z = 2×y + 1 получаем z + 1 = (2×y + 1) + 1 = 2×y + 2 = 2×(y+1), и в качестве искомого t можно взять t = y + 1.

Таким образом, неформально доказана формула (" z (А(z) ® А(z + 1))) и по схеме индукции, можно заключить, что доказана и формула (" x А(x)).

Упражнения: 1. Что в этом доказательстве неформального ?

2. Формализуйте доказательство.

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

Пусть Г = {Ф₁ , … , Ф_k } – конечное множество формул (возможно пустое). Говорят, что формула В выводима из множества формул Г, если существует конечная цепочка формул В₁ , … , В_n , где В_n совпадает с В, а каждая формула B_i (1 £ i £ n) либо является аксиомой, либо принадлежит Г, либо получена из некоторых предыдущих формул В_j и В_k (1 £ j < i, 1 £ k < i) по правилам вывода теории. Факт выводимости формулы В из совокупности Г обозначается через Г В.

Ясно, что формула В доказуема тогда и только тогда, когда она выводима из пустого множества формул: В. С другой стороны, если все формулы, входящие в Г = {Ф₁ , … , Ф_k }, доказуемы, а В выводима из Г, то В доказуема. Действительно, чтобы получить доказательство формулы В, достаточно к её выводу В₁ , … , В_n из формул Г присоединить доказательства формул Ф₁ , … , Ф_k :

<доказательство Ф₁ >, … , <доказательство Ф_k >, В₁ , … , В_n –

это доказательство формулы В. Таким образом, для доказательства формулы достаточно вывести её из уже доказанных ранее формул.

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

 

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

 

 

Непротиворечивость аксиоматических теорий

Теорема (компактности). Система аксиом специальной теории непротиворечива тогда и только тогда, когда непротиворечива любая её конечная… Доказательство. Ясно, что из непротиворечивости системы аксиом следует… Обратно, пусть непротиворечива каждая конечная подситема системы аксиом, но сама теория противоречива. Тогда из…

Полнота аксиоматических теорий

Для формальной теории истинность теоремы означает, прежде всего, её доказуемость. Для содержательной теории утверждение истинно, если оно истинно в… Интерпретация формальной теории (или модель теории) определяется аналогично… Если фиксирована интерпретация теории, то любая замкнутая формула теории после замены всех участвующих в ней символов…

Разрешимость аксиоматических теорий

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

Независимость системы аксиом теории

Конечно, требование независимости является скорее эстетическим, нежели математически необходимым, но оно побуждает к анализу взаимосвязей аксиом… Если аксиоматика формальной теории состоит из схем аксиом, то, как правило,… Как доказать независимость той или иной системы аксиом ? Основным методом доказательства является метод построения…

Формальное исчисление высказываний

1. Свойства выводимости формул.Докажем некоторые основные свойства выводимости формул. 10. Всякая доказуемая формула выводима из любой совокупности формул. В… Действительно, доказательство формулы является и её выводом из любой совокупности формул, т.к. в нём используются…

A ® A) доказуема

5 · ((A ® B) ® (A ® (A Ù B))) МР(3, 4)

6 · (А Ù В) ® А (К1)

A Ù B) A дедукция

8 · Г, (A Ù B) A расширение посылок

9 · Г, (A Ù B) (В ® С) силлогизм(2, 8)

10 · Г, (A Ù B), В Сдедукция

11 · ((A Ù B) ® B)(К2)

A Ù B) B дедукция

13· Г, (A Ù B) Врасширение посылок

14 ·Г, (A Ù B) Ссиллогизм(10, 13)

15 · Г ((А Ù B) ® C)дедукция

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

1 · Г ((A Ù B) ® C) дано

Г, (А Ù B) C дедукция

Г, А, (А Ù B) C расширение посылок

4 · ((A ® A) ® ((A ® B) ® (A ® (A Ù B)))) (К3)(А := А, В := А, С := В)

А ® A) доказуема

6 · ((A ® B) ® (A ® (A Ù B))) МР(4, 5)

7 · B, A В 2⁰

В (А ® В) дедукция

9 · В (A ® (A Ù B)) МР(6, 8)

B, A (A Ù B) дедукция

12 · Г, А, В C силлогизм(3, 11) 13 · Г, А (В ® C) дедукция 14 · Г (А ® (В ® C)) дедукция

Закон идемпотентности: (А Ù А) ~ A, (А Ú А) ~ A .

1· (A Ù A) ® A (К1)

2· ((А ® A) ® ((A ® A) ® (A ® (A Ù A)))) (К3)

3 ·(A ® A) доказуема

4 · ((A ® A) ® (A ® (A Ù A))) МР(1, 2)

5 · (A ® (A Ù A)) МР(3, 2)

Для дизъюнкции докажите самостоятельно.

Коммутативность: (А Ù B) ~ (В Ù A), (А Ú B) ~ (B Ú A) .

1 · (A ® (A Ú B)) (Д1)

2 · (B ® (A Ú B)) (Д2)

3 · ((B® (A Ú B))® ((A ® (A Ú B)) ® ((B Ú A) ® (A Ú B)))) (Д3)

4 · ((A ® (A Ú B)) ® ((B Ú A) ® (A Ú B)))) МР(2, 3)

5 · ((B Ú A) ® (A Ú B)))) МР(1, 4)

Импликация ((A Ú B) ® (B Ú A)) доказывается аналогично.

Для конъюнкции докажите самостоятельно.

Ассоциативность: ((А Ù B) Ù С) ~ (А Ù (В Ù С)), ((А Ú B) Ú С) ~ (А Ú (B Ú С)).

1 · (((A Ù B) Ù C) ® (A Ù B)) (К1)

A Ù B) Ù C) (A Ù B) дедукция

3 · (((A Ù B) Ù C) ® С) (К2)

4 · ((A Ù B) Ù C) С дедукция

5 · ((A Ù B) ® A) (К1)

A Ù B) A дедукция

7 · ((A Ù B) ® B) (К2)

A Ù B) B дедукция

9 · ((A Ù B) Ù C) A силлогизм(2, 6)

10 · ((A Ù B) Ù C) B силлогизм(2, 8)

11 · ((A Ù B) Ù C) (B Ù C) введениеÙ (4, 10)

12 · ((A Ù B) Ù C) (A Ù (B Ù C)) введение Ù (9, 11)

A Ù B) Ù C) ® (A Ù (B Ù C)) дедукция

Импликация ((A Ù (BÙ C)) ® ((A Ù B) Ù C)) доказывается аналогично.

Для дизъюнкции докажите самостоятельно.

Дистрибутивность: ((А Ù B) Ú С) ~ ((А Ú С) Ù (В Ú С))),

А Ú B) Ù С) ~ ((А Ù С) Ú (В Ù С))).

1 · ((A Ù B) ® A) (К1)

2 · (A Ù B) A дедукция

3 · ((A Ù B) ® B) (К2)

A Ù B) B дедукция

5 · (A ® (A Ú C)) (Д1)

A (A Ú C) дедукция

7 · (A Ù B) (A Ú C) силлогизм (2, 6)

8 · (B ® (B Ú C)) (Д1)

B (B Ú C) дедукция

10 · (A Ù B) (B Ú C) силлогизм (4, 9)

11 · (A Ù B) ((A Ú C) Ù (B Ú C)) введениеÙ (7, 10)

A Ù B) ® ((A Ú C) Ù (B Ú C))) дедукция

14 · С (A Ú C) дедукция 15 · (С ® (B Ú C)) (Д2) 16 · С (B Ú C) дедукция

B, (A Ú C) ((A Ù B) Ú C) дедукция

A Ú C) (В ® ((A Ù B) Ú C)) дедукция

11 · (A Ú C) ((В ® ((A Ù B) Ú C)) ® ((С ® ((A Ù B) Ú C)) ® ® ((B Ú C) ® ((A Ù B) Ú C))))(Д3) 12 · (A Ú C) ((С ® ((A Ù B) Ú C)) ® ((B Ú C) ® ((A Ù B) Ú C))) МР(9, 11) …

A Ú C) Ù (B Ú C) ® ((A Ù B) Ú C)) дедукция

Законы де Моргана: .

1 · (A Ù B) A (почему ?!)

2 · контрапозиция

Дедукция

5 · контрапозиция 6 · дедукция 7 · (() ® (( ) ® ((Ú ) ® ) )) (?!)

A, , (A ® B) Bдедукция

4· A, приведение к противоречию 5 · A (® ) дедукция 6 · (A Ù ) A (?!)

A ® B) (Ú ) силлогизм

20 · (A ® B) (Ú B) силлогизм (18, 19)   1 · , A, A 20

A ® B)) дедукция

9 · ((® (A ® B)) ® ((B ® (A ® B)) ® ((Ú B) ® (A ® B)))) (Д3) 10 · ((B ® (A ® B)) ® ((Ú B) ® (A ® B))) МР(7, 9) 11 · ((Ú B) ® (A ® B)) МР(8, 10)

Правило опровержения

6. Доказуемость и тождественная истинность формул. Теперь уже можно доказать основной результат этого параграфа. Теорема (о доказуемости и тождественной истинности формул ИВ).Формула… Доказательство. То, что доказуемая формула является тождественно истинной, уже отмечалось выше: для этого нужно лишь…

ПРИЛОЖЕНИЕ: ФОРМАЛЬНАЯ ТЕОРИЯ МНОЖЕСТВ

Азы наивной теории множеств

Наиболее употребительны следующие два способа задания множеств: · перечисление элементов(используется в основном для множеств, состоящих из… · выделение множества в другом множестве с помощью характеристического свойства его элементов:если В – множество и…

Основные операции над множествами

I. Если А, В – множества, то существует множество А È В – объединение множествА и В, которое состоит из всех элементов, являющихся элементами либо множества А, либо множества В: x Î A È B « x Î A Ú x Î B.

Примеры: 1.Если A = {1, 2, 5, Æ}, B = {{1}, 2, 5, Æ}, то А È В = {1, 2, 5, Æ, {1}}.

2. Если A = {x Î R | 1 < x £ 5}, B = {x Î R | –1 £ x < 2}, то A È B = [–1; 5], где [–1; 5] = {x Î R | –1 £ x £ 5}.

II. Если А, В – множества, то существует множество А Ç В – пересечение множествА и В, которое состоит из всех элементов, являющихся одновременно элементами и множества А, и множества В: x Î A Ç B « x Î A Ù x Î B.

Примеры: 1. Если A = {1, 2, 5, Æ}, B = {{1}, 2, 5, Æ}, то А Ç В = {2, 5, Æ}.

2. Если A = {x Î R | 1 < x £ 5}, B = {x Î R | –1 £ x < 2}, то A Ç B = (1; 2), где (1; 2) = {x Î R | 1 < x < 2}.

3. A Ç B = {a Î A | a Î B}.

На основе понятий пересечения и объединения двух множеств можно ввести аналогичные операции над несколькими множествами:

A₁ Ç … Ç A_n = (…((A₁ Ç A₂) Ç A₃) Ç …) Ç A_n ,

A₁ È … È A_n = (…((A₁ È A₂) È A₃) È …) È A_n .

III. Если А, В – множества, то существует множество А \ В – разность множествА и В, которое состоит из всех элементов, принадлежащих множеству А, но не принадлежащих множеству В: x Î A \ B « x Î A Ù x Ï B.

Примеры: 1. Если A = {1, 2, 5, Æ}, B = {{1}, 2, 5, Æ}, то А \ В = {1}.

2. Если A = {x Î R | 1 < x £ 5}, B = {x Î R | –1 £ x < 2}, то A \ B = [2; 5].

3. A \ B = {a Î A | a Ï B}.

IV. Если А – множество, то существует множество всех его подмножествB(A), называемое также булеаном множестваА, и состоящее из всех подмножеств множества А: X Î B(A) « X Í A.

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

 

Примеры: 1. Если А = Æ, то B(A) = {Æ}.

2.Если A = {1}, то B(А) = {Æ, {1}}.

3. Если A = {1, 2}, то B(А) = {Æ, {1}, {2}, {1, 2}}.

4. Если A = {1, 2, 3}, то B(А) = {Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

5.Можно доказать, что булеан n-элементного множества А состоит из 2ⁿ элементов. Поэтому булеан часто называют степенью множестваА и обозначают 2^A.

 

V. Если А, В – множества, то существует их прямое (декартово) произведениеА´В, состоящее из всех упорядоченных пар(a; b), где а Î А, b Î B:

А´В = {(a; b) | a Î A Ù b Î B}.

Примеры: 1.Если А = {1}, B = {0, 5}, то А´В = {(1; 0), (1; 5)}.

2. Если А = {0, 2}, B = {0, 5}, то А´В = {(0; 0), (0; 5), (2; 0), (2; 5)}.

3. Если множество А состоит из m элементов, а множество В – из n элементов, то можно доказать, что множество А´В состоит из m´n элементов. По этой причине в названии множества А´В используется термин “произведение”. Если А = B, то множество А´А состоит из m² элементов и называется декартовым квадратом множестваА и обозначается через A².

Вслед за декартовым произведением двух можно ввести и декартово произведение A₁ ´ … ´ A_n = ( … ((A₁ ´ A₂) ´ A₃)´ …)´ A_n n множеств A₁ , … , A_n . Множество называется декартовой степенью множества A и обозначается A ⁿ.

Декартово произведение А´В = {(a; b) | a Î A Ù b Î B} двух множеств А и В иногда условно изображают на плоскости, трактуя компоненты упорядоченной пары (a; b) как координаты: a – координата по оси x, на которой отмечают множество А, а b – координата по оси y, на которой отмечают множество В. Таким образом, элементы (a; b) Î А´B условно изображаются точками на плоскости с “координатами” a и b.

Особенно удобно графическое изображение декартова произведения А´В в случае, когда А и В – числовые множества, т.е. А Í R, B Í R . Тогда изображение принимает не условный характер, а имеет вполне конкретный геометрический смысл: множество А´В представляет из себя множество точек M(a; b) декартовой плоскости, первая координата а которых принадлежит множеству А, а вторая b – принадлежит множеству В.

 

Аксиоматика Цермело-Френкеля теории множеств

В § 1 приложения были даны основные понятия теории множеств. Однако развиваемая на этом основании Г. Кантором наивная теория множеств столкнулась в… Парадокс Рассела: Пусть U – множество всех множеств. Рассмотрим множество M =… Выход из создавшейся ситуации только один – нельзя считать “множество всех множеств” U множеством: если U – не…

Формальная теория множеств: райские

Кущи или адские дебри ?

За краткую (почти столетнюю) историю использования приведённой системы аксиом не было выявлено ни одного противоречия. Это, конечно, не доказывает… Долгое время не было известно достаточно простых примеров недоказуемых, и… Быть может, подобные простые недоказуемые утверждения будут скоро открыты и в арифметике. Само их существование в…

Л И Т Е Р А Т У Р А

1.Глухов М.М., Козлитин О.А., Шапошников В.А., Шишков А.Б. Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов. –… 2.Ершов Ю.Л., Палютин Е.А. Математическая логика. – СПб.: Издательство “Лань”,… 3.Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2004.

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ

Q – множество всех рациональных чисел, R – множество всех действительных чисел, B – множество {0, 1},

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

аксиома объёмности................................................. 150 аксиома (неупорядоченной) пары.............................. 151 аксиома бесконечности.............................................. 154

Алексей Игоревич Валицкас

КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Учебно-методическое пособие

Лицензия на издательскую деятельность

ЛР № 040287 от 25 июля 1997 г.

 

 

Подписано в печать ___. ___. 2010 г.

Формат 6084 1/16. Усл. печ. л. 9 Тираж 300 экз. Заказ № ____________

 

Отпечатано в типографии редакционно-издательского отдела ГОУ ВПО

“Тобольская государственная социально-педагогическая академия им. Д.И. Менделеева”

626150, Тобольск, ул. Знаменского, 58

[1] Любознательный читатель может обратиться к замечательной книге: Смаллиан Р.М. Как же называется эта книга ? – М.: Мир, 1981.

[2] Древние считали, что это правило отделяет “ослов” – не понимающих логики – от нормальных людей: тот, кто освоил это правило уже перешёл по мосту из разряда “ослов” в разряд нормальных людей.

[3] Буду благодарен тому, кто сообщит, что бы это значило (мера терпения ?!).

* При первом чтении можно опустить.

Развернуть

Открыть в широком формате