Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

чения произвольных пропозициональных форм, тогда как обычное написание этих букв применяется лишь для пропозициональных букв. Как определено, каждая пропозициональная буква может принимать зна­ чения И либо Л. Будем считать, что пропозициональные формы (—i А), {А&В), {AWB), {А^В) и (А =В) имеют те же таблицы истинности, что и обозначаемые таким образом высказывания (см. § 1). Тогда каждому распределению (истин­ ностных) значений И И Л пропозициональных букв, входящих в пропозицио­ нальную форму (означиванию атомов), соответствует некоторое истинностное значение этой пропозициональной формы; эта процедура считается означива­ нием формы. В результате, каждая пропозициональная форма порождает неко­ торую истинностную функцию. Заметим, что пропозициональная форма не является высказыванием. По определению формула - это выражение, построенное из пропозициональных букв, с помощью пропозициональных связок согласно правилам 1), 2), 3) и ни­ чего более. В частном случае пропозициональные буквы могут обозначать вы­ сказывания, пропозициональные связки - логические операции, тогда пропози­ циональная форма будет обозначать некоторое высказывание. Так как добавление каждой новой пропозициональной буквы увеличивает количество строк в таблице истинности вдвое, то форма, содержащая п различ­ ных букв, имеет таблицу истинности с 2" строками. Например, для формы {{{A8LB)WC)^A) имеем следующую таблицу истинности: А в с (А&В) {{А&В)иС) {ЦА&В )иС )^А) Л л л л л и Л л и л и л Л и л л л и л и и л и л и л л л л и и л и л и и и и л и и и и и и и и и Составление таблицы истинности можно сократить, выписывая шаг за ша­ гом под каждой пропозициональной связкой истинностные значения той со­ ставляющей формулы, для которой применяется эта связка. Например, для той же формулы (((А&В) VCJ^A) получаем таблицу: А в с (((А &В) vC) ^А) л л л л л и л л и л и л л и л л л и л и и л и л и л л л л и и л и л и и и и л и и и и и и и и и 9