Формулы логики высказываний. Мы определим формальный язык для описания логики высказываний

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

Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно, пустая). Слово a называется подсловом слова b, если b = b₁ab₂ для некоторых слов b₁ и b₂ (мы используем обозначение ab для конкатенации (соединения) двух слов a и b в одно слово).

Алфавит логики высказываний содержит следующие символы: высказывательные переменные X₁, X₂,…; логические символы &, Ъ, Ш, Й, ~; символы скобок (,).

Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

любая высказывательная переменная - формула;

если A и B - формулы, то (ШA), (A&B), (AЪB), (AЙB), (A~B) - формулы.

только те слова являются формулами, для которых это следует из 1) и 2).

Подформулой формулы A называется любое подслово A, само являющееся формулой.

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

Пример 2.1. Слово (X₁&X₂)ЙX₃ШX₁ не является формулой, а слова (ШX₁ЙX₂)ЪX₁, (X₁~X₂)ЙШX₃ - формулы. Слова X₁~X₂, ШX₃, X₁, X₂, X₃ - подформулы последней формулы.

Принцип математической индукции, который будем использовать в рассуждениях, формулируется следующим образом: если какое-то высказывание 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, который пробегает все множество высказывательных формул,

истинно для всех формул, не содержащих логических символов (т.е. формул вида X_i);

и при любом натуральном n из того, что P(F) истинно для всех формул F с числом логических символов, меньших n, следует, что P(F) истинно для всех формул с n логическими символами,

то P(F) истинно для всех формул F.

Пример 2.2. Докажем методом математической индукции, что S_n - сумма натуральных чисел от 1 до n - равна 1/2 (n+1)n.

Базис индукции. S₁ = 1 = (2Ч1)/2.

Индуктивный переход. Пусть S_n = 1/2 (n+1)n. Тогда S_n+1=S_n + n+1 = =(n+1)n/2 +n+1 = (n² + n + 2n +2)/2 = (n+1)(n+2)/2, ч. и т. д.

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

Таким образом, если {X₁, X₂,…, X_n} - множество высказывательных переменных, входящих в формулу F, то формула F определяет истинностную функцию {И, Л}ⁿ а{И, Л}, которая графически может быть представлена истинностной таблицей для этой формулы.