А) основная литература:
Глухов М.М., Козлитин О.А., Шапошников В.А., Шишков А.Б. Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов. – С.-Пб.: Издательство “Лань”, 2008.
Ершов Ю.Л., Палютин Е.А. Математическая логика. – СПб.: Издательство “Лань”, 2004.
Игошин В.И. Математическая логика и теория алгоритмов. – М.: Издательский центр “Академия”, 2004.
Игошин В.И. Задачник-практикум по математической логике. – М.: Издательский центр “Академия”, 2005.
Лавров И.А. Математическая логика. – М.: Издательский центр “Академия”, 2008.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Издательский центр “Академия”, 2007.
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – С.-Пб.: Издательство “Лань”, 2008.
Б) дополнительная литература:
Клини С. Введение в метаматематику / Пер. с англ. – М.: ИЛ, 1961.
Клини С. Математическая логика / Пер. с англ. – М.: Мир, 1973.
Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. – М.: Изд-во МГУ, 1984.
Кондаков Н.И. Логический словарь-справочник. – М.: , 1975.
Коэн П. Дж. Теория множеств и континуум-гипотеза. – М.: Мир, 1969.
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.
Математическая логика (Под общей редакцией А.А. Столяра и др.) – Минск: Вышейшая школа, 1991.
Мендельсон Э. Введение в математическую логику. – М.: Наука, 1976.
Новиков П.С. Элементы математической логики. – М.: Наука, 1973.
Смаллиан Р.М. Как же называется эта книга ? – М.: Мир, 1981.
Смаллиан Р.М. Принцесса или тигр ? – М.: Мир, 1985.
Чёрч А. Введение в математическую логику. – М: Мир, 1960.
Эдельман С.Л. Математическая логика. – М., 1975.
Список основных обозначений
N – множество всех натуральных чисел,
Q – множество всех рациональных чисел,
R – множество всех действительных чисел,
B – множество {0, 1},
f : X Y – функция из множества X со значениями во множестве Y,
f : ? ? – функция с неопределёнными областями определения и значений,
{ai}iI – последовательность элементов, индексированных элементами множества I,
D(f) – область определения функции f,
DA(f) – область определения функции f с неопределёнными областями определения и значений на множестве А,
Im(f) – область значений функции f,
ImA(f) – область значений функции f с неопределёнными областями определения и значений на множестве А,
Р : An B – предикат на множестве А,
D1(P), D0(P) – области истинности и ложности предиката Р,
f : X1 … Xn Y – функция от n аргументов x1 X1 , … , xn Xn со значениями во множестве Y,
> , – знаки “больше”, a > b, a b – а больше b,
< , – знаки “меньше”, a < b, a b – a меньше b,
–логическая
связка отрицание,
– отрицание формулы A,
– логическая связка конъюнкция, (A B) – конъюнкция двух формул,
– логическая связка дизъюнкция, (A B) – конъюнкция двух формул,
– логическая связка импликация, (A B) – импликация двух формул,
– логическая связка эквивалентность, (A B) – эквивалентность двух формул,
– знак равносильности формул, A B – формулы А и В равносильны, т.е. имеют одинаковые значения при любых интерпретациях,
~ – знак равносильности формул в формальных теориях, A ~ B – формулы А и В равносильны, т.е. доказуемы теоремы A B и B A,
– сложение по модулю 2 (исключающее или) a b = a + b (mod 2),
|
– штрих Шеффера,
x
| y
= (
),
– стрелка
Пирса, x
y
= (
),
– делимость нацело целых чисел, x y – x делится нацело на y,
Г
А, А1
, … , An
A,
А –
обозначение логического следования
формулы А из множества формул Г, формул
А1
, … , An
, из пустого множества формул,
–схема правил
логического следования,
A(x1 , … , xn) 1, A(x1 , … , xn) 0 – формула A тождественно истинна (закон логики), соответственно тождественно ложная (противоречие),
P(x1 , … , xn ) А 1, P(x1 , … , xn ) А 0 – тождественно истинный и тождественно ложный предикаты на множестве А,
P(x1 , … , xn ) 1, P(x1 , … , xn ) 0 – тождественно истинный и тождественно ложный предикаты на множестве D(P),
P(x1 , … , xn ) А Q(x1 , … , xn ) – равносильные на множестве А предикаты,
P(x1 , … , xn ) Q(x1 , … , xn ) – равносильные на множестве D(P) = D(Q) предикаты,
– знак логического следования для предикатов, Р(х) Q(x) – предикат Q(x) является логическим следствием предиката P(x) (т.е. x P(x) Q(x)),
– знак логической равносильности предикатов, Р(х) Q(x) – предикаты P(x) и Q(x) с одинаковыми областями определения равносильны (т.е. x D(P) P(x) Q(x)),
P(s)( _ , … , _ ) – предикатный символ от s переменных,
J
= (M,
a1
= 1
, … , am
= m
, x1
= o1
, … , xn
= on
,
)
– интерпретация множества формул
исчисления предикатов,
–дизъюнктивная
форма,
–конъюнктивная
форма,
–полином
(многочлен) Жегалкина,
–двоичное
число с двоичными цифрами 1
, … , n
,
{a1 ; … an} – конечное множество из n элементов,
{ x A | P(x) = 1} – множество всех элементов множества А, удовлетворяющих характеристическому свойству Р,
– знак принадлежности элемента множеству, a A, a A – элемент a принадлежит (не принадлежит) множеству A,
– знак пересечения множеств, A1 … An – пересечение множеств A1 , … , An ,
– знак объединения, A1 … An – объединение множеств A1 , … , An ,
{C
| C
A},
– пересеченение по множеству A,
{C
| C
A},
– объединение по множеству A,
\ – знак разности множеств, A \ B – разность множеств A и B,
– знак включения, A B – A является подмножеством в B (A содержится в В),
– пустое множество,
B(A) – булеан множества А (множество всех подмножеств множества А),
(a ; b) – упорядоченная пара, (a1 ; … ; an) – упорядоченная n-ка,
– знак прямого произведения множеств, A1 … An – прямое (декартово) произведение мжеств A1 , … , An ,
, – кванторы всеобщности и существования,
! – знак существования и единственности,
A
– формула A
доказуема в ИВ или ИП,
ИВ – исчисление высказываний,
ИП – исчисление предикатов,
ДФ – дизъюнктивная форма,
КФ – конъюнктивная форма,
РКС – релейно контактная схема,
СБИС – сверхбольшая интегральная схема,
ПФ – приведённая форма формулы ИП,
ПНФ – предварённая нормальная форма формулы ИП,
ППНФ – предварённая приведённая нормальная форма формулы ИП,
MP – правило вывода modus ponens,
ч. у. м. – частично упорядоченное множество,
в. у. м. – вполне упорядоченное множество.