Математическая логика и теория алгоритмов

Пропозициональные формы часто называют формулами логики высказываний. Жирные заглавные буквы латинского алфавита {А,В,С ,...) или те же буквы с числовыми индексами упот­ ребляются для обозначения произвольных пропозициональных форм, тогда как обычное написание этих букв применяется лишь для пропо­ зициональных букв. Истинностной функцией от п аргументов называется и-аргументная функция, принимающая одно из двух значений: И либо Л, когда ее аргументы пробегают те же значения. Составное (сложное) высказывание, образованное с помощью введенных операций 1 , &, v , =:i>,=, будет истинным либо ложным в зависимости от значений исходных высказываний; Следовательно, полученное составное высказывание порождает некоторую истинно­ стную функцию. Как определено, каждая пропозициональная буква может при­ нимать значения И либо Л. Будем считать, что пропозициональные формы (]А), (А&В), (A V B), (A=i>B) и (А =В) имеют те же таблицы ис­ тинности, что и обозначаемые таким образом высказывания (см.§1). Тогда каждому распределению (истинностных) значений И п Л про­ позициональных букв, входящих в пропозициональную форму, соот­ ветствуют некоторые истинностные значения этой пропозициональ­ ной формы. Таким образом, каждая пропозициональная форма порождает некоторую функцию, принимающую значение Л или И в зависимости от истинностных значений пропозициональных букв, в нее входящих, следовательно, каждая пропозициональная форма порождает некото­ рую истинностную функцию. Заметим, что пропозициональная форма не является высказыва­ нием. По определению пропозициональная форма - это вырамсение, построенное из пропозициональных букв, т.е. букв А, В, С,..., А], Аг,..., В\, Вг С], Сг,... с помощью пропозициональных связок согласно пра­ вилам 1), 2), 3) и ничего более. В частном случае пропозициональные буквы могут обозначать высказывания, пропозициональные связки ~ логические операции, тогда пропозициональная форма будет обозна­ 18