Исчисление высказываний и исчисление предикатов;
Исчисление высказываний, исчисление суждений, раздел математической логики, в котором формально-аксиоматическим методом изучаются сложные (составные) высказывания, составленные из простых (элементарных, не анализируемых) высказываний с помощью логических связок "и", "или", "если..., то" и "неверно, что". При этом ставится цель охарактеризовать общезначимые в том или ином смыслевысказывательные формы, т. е. те формулы, которые при любой подстановке высказываний вместо переменных дают высказывания, верные в соответствующем смысле.
Будем говорить, что ФАТ (формально-аксиоматическая теория) задана, если:
1. задан алфавит;
2. заданы формулы (слова в заданном алфавите);
3. определены аксиомы (выделенные формулы);
4.определены правила вывода 
(n-местное отношение на множестве формул Ф: 
).
Если формулы 
,следовательно, 
, то формула 
есть непосредственное следствие из предыдущих формул по правилу 
.
Последовательность 
— есть вывод формулы А, если любая формула Аi есть либо аксиома, непосредственное следствие предыдущих формул.
Пусть Г – множество формул.
, если 
, где любая из 
- аксиома, -следствие, -либо формула из Г. Если 
, тогда 
– теорема.
Элементарные свойства выводимости.
Пусть 
– формулы, 
– множество формул.
1. 
.
2.Если 
, то 
.
3.Если , то 
.
4.Если 
, тогда 
.
5.Если 
, то 
.
Исчисление высказываний:
1. Алфавит исчисления высказываний состоит из переменных высказываний: х,…, 
, логических связок 
и скобок 
.
- Формулы:
а) все переменные являются формулами;
б) если 
и 
– формулы, то 
и 
– формулы;
в) других нет.
3. Аксиомы.
I. 
;
II. 
;
III. 
;
4. Правило вывода:
Modus Ponens. Если и 
– выводимые формулы, то выводима: 
.
Формула В есть непосредственное следствие формул А и .
Предикатом Р( 
) называется функция, переменные которой принимают значения из некоторого множества М, а само значение функции принимает значения: 1 или 0.
Предикат от n-переменных, называют n-местным предикатом.
Исчисление предикатов:
1) Алфавит:
1. Предметные переменные х1, х2…;
2. Предикатные константы а1, а2….;
3. Функциональные буквы 
, где i – количество аргументов;
4. Предикатные буквы 
;
5. Логические связки 
;
6. Кванторы существования 
2) Формулы (слова в алфавите):
1. Термы.
1. предметные переменные и константы являются термами;
2. если fn – функциональная буква, а t1, … , tn – термы, то fn(t1, … , tn) – терм.
2. Формулы.
1. если Аn – предикатная буква, а t1, … , tn – термы, тогда Аn (t1,…, tn) формула. Такая формула называется атомарной (элементарной). Все переменные в атомарной формуле являются свободными. Определение: переменная х является связанной, если х входит в квантор или находится в области действия квантора.
2. Если А формула, тогда - формула, причем все связанные переменные в А, являются связанными в .
3. Пусть А и В формулы, причем нет переменных которые были бы связаны в одной и свободны в другой, тогда - формула.
4. пусть А – формула и переменная х свободная, тогда 
и 
- формулы.
3) Аксиомы:
1. А1, А2, А3
2. А4 
, если А(х) не содержит переменной у;
3. А5 
4) Правило вывода:
1. m.p.
2. 
3. 
, В не содержит х.
Под интерпретацией понимают систему М= 
, где М - непустое множество, а f – соответствие, сопоставляющего каждому предметному символу (букве) определенный предикат.
Формула называется общезначимой, если она принимает истинные значения на любом множестве
Теорема о полноте И Пр.
Ф-ла А выводима в И Пр Û когда она логически общезначима