Лекция «Аксиоматическая теория Гильберта-Аккермана» по Дискретной математике (Сабуров М. А.)

Кирилл Николоев вт, 22.03.2016 20:30

М.А. Сабуров 1 Аксиоматическая система Гильберта-Аккермана Аксиоматическая система Гильберта-Аккермана (Hilbert-Ackermann) состоит из трех частей: 1) алфавит; 2) правила образования формул; 3) правила преобразования формул (правила образования тезисов).

1. Алфавит – список первичных понятий: a) Прописные латинские буквы (возможно, с индексами) A, B, C, … , A1, A2, … будут называться простыми высказываниями. Иногда их также называют пропозициональными буквами. При этом о значениях истинности этих

высказываний речи не идет. b) Знаки Ú и` , которые мы будем называть дизъюнкцией и отрицанием, соответственно, или операциями. Никакого содержательного смысла этим знакам мы не придаем. c) Скобки ( , ) – знаки пунктуации.

2. Правила образования формул. Для удобства речи формулы будем обозначать прописными готическими буквами: A, B, C, D и т.д. Готические буквы не входят в алфавит исчисления высказываний. Формулы исчисления высказываний составляют предметный язык, т.е. предмет нашего изучения.

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

должны различаться. В нашем случае метаязык состоит из естественного языка и условных обозначений. Готические буквы суть символы метаязыка. Они вводятся для удобства, их можно заменить словами. a) Все простые высказывания суть формулы.

b) Если A и B – формулы, то (AÚB) – формула. c) Если A – формула, то A – формула. Примеры формул: A , A , (A Ú B) , (A Ú B) Для сокращения записи формул введем новые символы операций: (A&B) есть сокращенная запись для (AÚB) . Назовем эту операцию

конъюнкцией. (A⇒B) есть сокращенная запись для (AÚB) . Назовем эту операцию импликацией. (AÛB) есть сокращенная запись для (A⇒B)&(B⇒A) (эквивалентность). Для сокращения же условимся опускать скобки. Во-первых, опускаем внешние

скобки: вместо (AÚB) пишем AÚB, а также считаем, что знак отрицания заменяет скобки: вместо (AÚB) ÚC пишем AÚBÚC. Во-вторых, введем понятие приоритета операций. Будем считать, что конъюнкция связывает сильнее, чем дизъюнкция, а

дизъюнкция, в свою очередь, сильнее, чем импликация и эквивалентность. Здесь мы несколько отступаем от Гильберта-Аккермана: у них дизъюнкция сильнее конъюнкции, Аксиоматическая система Гильберта-Аккермана

© М.А. Сабуров, 2007 2 а импликация сильнее эквивалентности; кроме того, в их книге знак дизъюнкции опускается, т.е. AB означает AÚB. Введенные нами правила использования скобок в большей степени согласуются с принятыми в современной математике и потому более

привычны для нас. Итак, формула A& B Ú C & D ⇒ E представляет собой сокращенную запись формулы (((A Ú B) Ú (C Ú D)) Ú E) Для удобства восприятия разрешим использовать скобки разного вида (квадратные, фигурные).

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

будем называть тезисами. Правила преобразования формул, или правила образования тезисов, включают в себя список первичных тезисов, или аксиом, и правила вывода. Следующие формулы суть аксиомы: A1: A Ú A⇒ A

A2: A⇒ A Ú B A3: A Ú B ⇒ B Ú A A4: (A⇒ B)⇒ (C Ú A⇒C Ú B) Правил вывода два. Первое из них – правило подстановки: α: в тезисе можно заменить любое простое высказывание, всюду, где оно встречается в нем, любой формулой.

Например, в тезисе A⇒ A Ú B заменим B на A и получим новый тезис: A⇒ A Ú A . (Правило подстановки позволяет рассматривать формулы A1 – A4 как схемы аксиом. Так, мы могли бы включить в список аксиом формулы B Ú B ⇒ B , C Ú C ⇒C

Скачать файлы

Похожие документы