При этом исчисление высказываний
представлено достаточно полно, для исчисления предикатов
рассмотрены вопросы интерпретации, непротиворечивости
и неразрешимости, теория алгоритмов представлена материалами по вычислимым функциям, разрешимым и перечислимым множествам, рассмотрены неразрешимые алгоритмические проблемы. <...> Раздел формальной арифметики
включает теорему Гјделя о неполноте. <...> Арифметические множества и функции
Глава
117
Теорема Райса. <...> Математическая логика и опирающийся на неј аксиоматический метод оказали большое влияние на развитие всех разделов
математики, в частности, и потому, что классическое исчисление
предикатов является той логической системой, на базе которой
можно, в принципе, формализовать всю математику. <...> Формальные теории
сложные высказывания, используя для этого логические связки,
например которые были определены ранее (или другие подобные):
если A, то B , или из A следует B ;
¬ не A, неверно, что A;
или A или B (или оба);
и A и B. <...> Формальные теории
11
множестве формул задано некоторое конечное множество отношений, называемых
Отметим, что, по данному определению, формальная аксиоматическая теория есть язык, в котором определены аксиомы и
правила вывода. <...> Формулы
f1 , f2 , . . . fn называют
, или
, формулу fn+1
.
Последовательность формул g1 , g2 , . . . gn называется
, если каждая формула в
этой последовательности является или аксиомой, или непосредственным следствием некоторых предыдущих формул. <...> Говорят, что формула h выводится из набора условий G, и это обозначается так: G ` h, если существует конечная
последовательность формул h1 , h2 , . . . hn , такая, что каждая hk
является или аксиомой, или одним из условий из набора G, или
непосредственным следствием предыдущих формул по одному
из правил вывода и hn = h.
правилами вывода.
непосредственным следствием
условиями посылками
заключением
Определение.
формальным доказательством
мой
доказуемой
формальной теоре-
вывода из условий,
Определение. <...> Цель изучения <...>
Лекции_по_математической_логике_и_теории_алгоритмов_учебное_пособие.pdf
F FF
FF
F F
E
D
PHIQ
Стр.1
SIHFPQXSIHFT@HUSFVA
IPUQ
RQ
E
F PHIQ
X
F F D D Y
F F F
D FF
RQ X GFF D
F FY F F E F FF F
" X D PHIQF " IRH F
sfx WUVESEVQWUEHWHVEW
F
D
D
D E
D E
D E
F
F
D E
HIHQHHFTP E
@ E
D AD F
SIHFPQXSIHFT@HUSFVA
IPUQ
sfx WUVESEVQWUEHWHVEW
- D PHIQ
Стр.2
F F F F F F F F F F F F F F F F F F F F F F F F F F F F S
IF
IF F F F F F F F F F F F F F F V
PF F F F F F F F F F F IQ
QF F F F F F F IT
RF D D F F F F PR
SF
F F F F F F F F F F F F F F F F F F F F F F F F F PT
TF F F F F QI
s F F F F F F F F F F F F F F F F F F F QR
UF F
F F F F F F F F F F F F F F F F F F F F F F F QV
VF
F F F F F F F F F F F F F F F F F F F F F F RQ
WF SR
IHF
F F F F F F F F F F F F F F F F F F F F F F F F F F F SW
IIF
F F F F F F F F F F F F F F F F F F F F F F F F F F F TR
ss F F F F F F F F F F F F F F F F F F TW
D D F F F F F F F F F F F F F F F F UI
Q
U
Стр.3
R
PF
UW
IPF F VH
IQF F F F F F F F F F F F F F F VR
IRF E F F F F F VV
ISF WP
ITF wE
E F F F F F F F F F F F F F WS
ITFIF F F F F F F F F F F F F F F F F F F WS
ITFPF F F F F F F F F F F F WU
ITFQF F F F F F F F F F F F F F WU
ITFRF F F F F F F F F F F F WV
ITFSF F F F F F F F F F F F F F F F F F F F WW
IUF F F F F IHI
IVF F F F F F F F F F IHR
IWF F IHT
PHF
F F F F F F F F F F F F F F F F F F F F F F F F F F F IHV
PIF
F F F F F F F F F F F F F F F F F F F F F F F F F F F F IIU
PPF F
F F F F F F F F F F F F F F IPH
PQF F
F F F F F F F F IPS
PRF
F F
F F F F F F F F F F F F F F F F F F F F F F F F F F IQQ
F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F IQV
Стр.4
E
D
F
E
D D D
D
D D F
E E
D D
D E
F
F
E
D E
F D D
F
D
F E
E
F
" E
F D
D
D F
@ AD
@ E
AD F
Стр.5