Исчисление высказываний как формальную теорию можно определить с помощью аксиоматического метода.

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

1) задано некоторое счетное множество, т.е. множество, элементы которого могут быть взаимно однозначно сопоставлены элементам натурального ряда 1, 2, ... символов ≈ символов теории T. Конечные последовательности символов теории называются выражениями теории T;

2)  имеется подмножество выражений теории T, называемых формулами теории T (формулами теории часто называют правильно построенные формулы). Чтобы определить, является ли выражение формулой в теории, существует эффективная процедура;

3) выделено некоторое множество формул, называемых аксиомами теорииT;

4) имеется конечное множество R₁, R₂, ..., R_n отношений между формулами, называемых правилами вывода. Для каждого R_i существует натуральное j такое, что для всякого множества, состоящего из j формул, и для всякой формулы F эффективно решается вопрос о том, находятся ли данные j формул в отношении R_i с формулой F и если ╚ да╩ , то F называется непосредственным следствием данных j формул по правилу R_i.

Выводом в T называется всякая последовательность F₁, F₂, ..., F_m формул такая, что для любого i формула F_i есть либо аксиома теории T, либо непосредственное следствие каких-либо предыдущих формул.

Формула F теории T называется теоремой теории T, если существует такой вывод в T, в котором последней формулой является F; этот вывод называется выводом формулы F. В общем случае может не существовать эффективной процедуры, с помощью которой можно определить по данной формуле, существует ли ее вывод в теории T.

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

Используя понятие аксиоматической теории T, определим исчисление высказываний в дизъюнктивном базисе Буля.

1. Символами T являются Ъ , Ш , (,) и буквы m_i с целыми положительными числами в качестве индексов: m₁, m₂, ... . Символы Ъ , Ш называются связками, а буквы m_i ≈ пропозициональными буквами.

2. а) Все пропозициональные буквы являются формулами;

б) если A и B ≈ формулы, то (A Ъ B) и (ШA) также формулы;

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

Таким образом, всякая формула исчисления высказываний есть некая пропозициональная форма, построенная из пропозициональных букв с помощью связок Ъ и Ш .

3) Каковы бы ни были формулы A, B и C теории T, следующие формулы есть аксиомы T:

A Ъ A ╝ A, A Ъ B ╝ B Ъ A,

A ╝ A Ъ B, (B ╝ C) ╝  (A Ъ B ╝ A Ъ C),

где запись a ╝ b эквивалентна записи Ш a Ъ  b .

4. Правилами вывода исчисления высказываний являются:

правило подстановки (если a  ≈ выводимая формула и вместо любой переменной в этой формуле всюду произвести подстановку любой формулы, то новая формула также является выводимой);

правило заключения (если a ╝ b и a  ≈ выводимые формулы, то b также выводимая формула) ≈ правило modus ponens. Символически это правило записывается так: (a ,a╝b )/b .

Например, если высказывания A и A╝ (q ╝A) истинны, то высказывание q╝ A также является истинным согласно правилу заключения.

Аналогично можно определить и другие булевы алгебры:

алгебру Вебба A = бM, oс ;

алгебру Шеффера A = бM, ╫с ;

импликативную алгебру A = бM ,╝ , 0с ;

коимпликативную алгебру A = бM ,╝ , 1с ;

алгебру Жегалкина A = бM, &, Е, 1с .

Обобщением двузначных логик являются конечнозначные логики.

Функция , отображающая n-мерный k-значный кортеж , в множество {0, 1, ..., k √ 1}, называется функцией k-значной логики. Будем задавать функцию k-значной логики с помощью таблицы истинности (одно-мерной таблицы), число строк которой равно kⁿ, или двумерной таблицы, число клеток которой равно k².

Рассмотрим трехзначную функцию ≈ функцию Вебба, заданную таблицами:
 
 

Функция Вебба

является полной в конечнозначной логике. Таким образом, конечнозначная алгебра Вебба
 
 

определяет соответствующую k-значную логику.

Другими часто встречающимися k-значными логиками являются логики, определяемые:

алгеброй Поста

где ≈ дизъюнкция; ≈ цикл;

алгеброй Россера≈Тьюкетта;

где ≈ конъюнкция,

≈ характеристические функции, .

Алгебраическая система (алгебра) определяется как , где A ≈ непустое множество, O ≈ семейство операций, R ≈ семейство отношений на множестве A. При этом A называется носителем или основным множеством; операции из O и отношения из R называются основными или главными.

Множество W  = O  И R называется сигнатурой алгебры S.

Система S называется собственно алгеброй или универсальной алгеброй, если множество R основных отношений пусто и называется реляционной системой или моделью, если множество O основных операций пусто.

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

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

Сигнатура непротиворечива, если не найдется формулы F, которая одновременно справедлива с формулой Ш F .

Конечнозначные логики являются обобщением двузначных логик. Например, логика Поста бM, Ъ, ~ с обобщает логику Буля б M,Ъ , Шс .

При минимизации логических функций конечнозначных логик можно использовать результаты двузначной логики ≈ теорию ДНФ булевых функций. Для этого введем булеву переменную , равную 1 при xa   = i и 0 в противном случае, xa ╧ i. Будем называть i √й фазой переменной xa  , xa  = {0, 1, ..., k √ 1}:

.

Отрицание i √й фазы равно дизъюнкции остальных фаз этой переменной

.

Очевидно, что .

Действительно, .
 
 

Предикат (от позднелат. рraedicatum ≈ сказанное) ≈ высказывательная функция, определенная на некотором множестве M, т.е. такая n-местная функция P, которая каждому упорядоченному набору элементов множества M сопоставляет некоторое высказывание, обозначаемое ; Pназывается n-местным предикатом на M. Под 0-местным предикатом понимается произвольное высказывание.

В математической логике высказывание обычно отождествляется с его истинностным значением 1 (╚ истина╩ ) или 0 (╚ ложь╩ ). При этом понятие предиката получает следующее, наиболее общее определение: n-местным предикатом на множестве M называется произвольная n-местная функция, определенная на M и принимающая значения 0 и 1. Если на наборе значений аргументов предикат P принимает значение 1, то есть , то говорят, что этот набор значений аргументов удовлетворяет предикату P, а предикат P выполняется для набора . Предикат называется тождественно истинным, если он выполняется для любого набора значений своих аргументов, и тождественно ложным, если никакой набор не удовлетворяет этому предикату. Предикат называется выполнимым, если он выполняется хотя бы для одного набора значений аргументов.

Множество тех наборов значений аргументов, которые удовлетворяют данному предикату, называется областью истинности этого предиката. Если P есть n-местный предикат на множестве M, то его область истинности является n-местным отношением на M. И наоборот, каждому n-местному отношению на множестве M однозначно соответствует n-местный предикат на M. Поэтому изучение предикатов и отношений тесно связано между собой.

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

Применение квантора всеобщностик предикату , где дает (n √ 1)-местный предикат , который набору сопоставляет высказывание, истинное тогда и только тогда, когда для любого значения a переменной x_i истинно высказывание .

Квантор существованияв применении к предикату при дает (n √ 1)-местный предикат , который набору сопоставляет высказывание, истинное тогда и только тогда, когда хотя бы для одного значения a переменной x_i истинно высказывание .

Исследованием связей между предикатами, определяемых их логической структурой, занимается логика предикатов.

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

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

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

1) предикатные переменные ≈ выражения вида , где m и n ≈ неотрицательные целые числа;

2) предметные переменные ;

3) логические символы & (или Щ ≈ конъюнкция), Ъ (дизъюнкция), ╝ (импликация), ~ (эквивалентность), ╛ (отрицание), $ (квантор существования), " (квантор всеобщности);

4) вспомогательные символы (,) (скобки) и , (запятая).

Выражение называется m-местной предикатной переменной; 0-местные предикатные переменные называются пропозициональными переменными.

Элементарной формулой называется всякая пропозициональная переменная, а также любое выражение вида , где P ≈ какая-либо m-местная предикатная переменная (m > 0), а ≈ произвольные предметные переменные. Из элементарных формул следующим образом строятся предикатные формулы:

1) все элементарные формулы суть формулы;

2) если А и В ≈ формулы, то выражения (А  & В ), (А  Ъ В ), (А  ╝ В ), (А  ~ В ),╛ А считаются формулами;

3) если А ≈ формула, x ≈ предметная переменная, то " x Аи $x А суть формулы.

Например, предикатными формулами являются .

Часть формулы А  , которая сама является формулой, называется подформулой формулы А .

Областью действия квантора "y или $y в формуле А называется такая ее подформула В , что " yВ или $yВявляется подформулой формулы А .

Вхождение переменной y в формулу А называется связанным, если оно есть вхождение в квантор "y или $y, или в область действия одного из этих кванторов.

Всякое вхождение переменной y, не являющееся связанным, называется свободным. Например, в формуле первые два вхождения переменной x₁ ≈ связанные, а третье ≈ свободное.

Переменная y называется свободной переменной формулы А , если она имеет свободные вхождения в А .

Говорят, что задана интерпретация формулы А на непустом множестве M, если каждой свободной переменной формулы А сопоставлен некоторый элемент из M, а каждой m-местной предикатной переменной из А ≈ некоторый m-местный предикат на M. Истинностное значение ╫ А╫ формулы А в данной интерпретации определяется индукцией по построению формулы А . Если А имеет вид , то ее значением является значение предиката, сопоставленного предикатной переменной P, на наборе значений переменных . Если А имеет вид ╛ В , то ╫ А ╫ = И тогда и только тогда, когда ╫ В╫ = Л. Аналогично, в соответствии с истинностными таблицами для логических операций &, Ъ,╝ , ~ определяются значения формул вида (А & В ), (А  Ъ В ), (А  ╝ В ), (А  ~ В ) через значения формул А  и В . Например, ╫А & В╫ = И, тогда и только тогда, когда ╫ А╫ = И и ╫В ╫ = И. Значение формулы " yАесть Л в том и только том случае, когда ╫А ╫= Л в некоторой интерпретации, полученной из данной приписыванием значения переменной y. Значение формулы $ yАесть И, если ╫А ╫ = И в некоторой интерпретации, полученной из данной приписыванием значения переменной y. Если ╫А╫ = И, то говорят, что формула А истинна в данной интерпретации.

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

общезначима на любом множестве, содержащем ровно один элемент, и не будет общезначимой на M, если в M есть хотя бы два элемента. Формула называется общезначимой или тавтологией, или тождественно истинной, если она общезначима на любом непустом множестве. Тот факт, что формула А общезначима, обычно обозначают так: ╫=А

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

Обычно классическое исчисление предикатов строится на основе того или иного варианта исчисления высказываний: аксиомы классического исчисления высказываний считаются схемами аксиом исчисления предикатов, то есть любая предикатная формула, полученная из некоторой аксиомы исчисления высказываний подстановкой в нее каких-либо предикатных формул вместо пропозициональных переменных, объявляется аксиомой исчисления предикатов. Например, из аксиомы исчисления высказываний таким образом получается аксиома исчисления предикатов
 
 

К этим аксиомам добавляются две новые схемы аксиом:
 
 

где А (x) ≈ произвольная предикатная формула, в которой переменная x не находится в области действия кванторов " y и $y, а формула А (y) получена заменой в А (x) каждого свободного вхождения переменной x на y.

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

• ≈ " -правило, позволяющее из формулы (В  ╝ А ) получить формулу (В  ╝ " x А ) , где В   и  А ≈ произвольные предикатные формулы, причем В не содержит свободную переменную x;
• ≈ $ -правило, позволяющее при тех же предположениях относительно формул А , В и переменной x перейти от формулы (А ╝ В ) к формуле ($ x А ╝ В ) .

Выводом формулы А в исчислении предикатов называется конечная последовательность формул А₁, . . ., А _m такая, что каждая из формул А _i либо есть аксиома, либо получается из некоторых предшествующих ей формул по одному из перечисленных правил вывода, и А_m совпадает с А . Формула А выводима в исчислении предикатов, или является теоремой, если можно построить вывод этой формулы. Согласно теореме Геделя о полноте, все общезначимые предикатные формулы и только они выводимы в классическом исчислении предикатов.

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