Мы определим формальный язык для описания логики высказываний. Это описание чисто синтаксическое и оно не требует, чтобы формулы логики высказывания имели какую-то семантику (смысл).
Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно, пустая). Слово a называется подсловом слова b, если b = b1ab2 для некоторых слов b1 и b2 (мы используем обозначение ab для конкатенации (соединения) двух слов a и b в одно слово).
Алфавит логики высказываний содержит следующие символы: высказывательные переменные X1, X2,…; логические символы &, Ъ, Ш, Й, ~; символы скобок (,).
Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:
1) любая высказывательная переменная - формула;
2) если A и B - формулы, то (ШA), (A&B), (AЪB), (AЙB), (A~B) - формулы.
3) только те слова являются формулами, для которых это следует из 1) и 2).
Подформулой формулы A называется любое подслово A, само являющееся формулой.
Для упрощения записи будем в формуле опускать внешние скобки и те пары скобок, без которых можно восстановить эту формулу, если пользоваться следующим правилом: каждое вхождение знака Ш относится к наикратчайшей подформуле, следующей за ним.
Пример 2.1. Слово (X1&X2)ЙX3ШX1 не является формулой, а слова (ШX1ЙX2)ЪX1, (X1~X2)ЙШX3 - формулы. Слова X1~X2, ШX3, X1, X2, X3 - подформулы последней формулы.
Принцип математической индукции, который будем использовать в рассуждениях, формулируется следующим образом: если какое-то высказывание P(t), зависящее от натурального параметра t, доказано для t = 0 и при произвольном t удается из истинности P(t) обосновать истинность P(t+1), то P(t) истинно для всех t.
Будем применять также и другую формулировку этого принципа: если P(t) истинно при t = 0 и для любого t из истинности P(s) при всех s Ј t следует истинность P(t+1), то P(t) истинно для всех t.
Применительно к высказывательным формулам принцип математической индукции можно сформулировать следующим образом:
если какое-то утверждение P(F), зависящее от параметра F, который пробегает все множество высказывательных формул,
· истинно для всех формул, не содержащих логических символов (т.е. формул вида Xi);
· и при любом натуральном n из того, что P(F) истинно для всех формул F с числом логических символов, меньших n, следует, что P(F) истинно для всех формул с n логическими символами,
то P(F) истинно для всех формул F.
Пример 2.2. Докажем методом математической индукции, что Sn - сумма натуральных чисел от 1 до n - равна 1/2 (n+1)n.
Базис индукции. S1 = 1 = (2Ч1)/2.
Индуктивный переход. Пусть Sn = 1/2 (n+1)n. Тогда Sn+1=Sn + n+1 = =(n+1)n/2 +n+1 = (n2 + n + 2n +2)/2 = (n+1)(n+2)/2, ч. и т. д.
Каждому распределению истинностных значений высказывательных переменных, входящих в ту или иную формулу, соответствует согласно истинностным таблицам для логических связок, некоторое истинностное значение этой формулы логики высказываний.
Таким образом, если {X1, X2,…, Xn} - множество высказывательных переменных, входящих в формулу F, то формула F определяет истинностную функцию {И, Л}n а{И, Л}, которая графически может быть представлена истинностной таблицей для этой формулы.