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

Истинностной функцией от п аргументов называется и-аргументная функ­ ция, принимающая одно из двух значений: И либо Л, когда ее аргументы про­ бегают те же значения. Составное (сложное) высказывание, образованное с помощью введенных операций —i, &, v, =^, = будет истинным либо ложным в зависимости от значе­ ний исходных высказываний. Следовательно, составное высказывание порож­ дает некоторую истинностную функцию. Также отметим, что приведенные контрпримеры (для конъюнкции и им­ пликации) показывают, что логика высказываний позволяет моделировать не все возможные предложения языка, а только часть. Но эта часть достаточно объемна и важна. § 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности Символы —1, &, V, =^, = называются пропозициональными связками. Заглавные буквы алфавита {А,В,С,...) и те же буквы с числовыми индекса­ ми { Ai , A2,...,Bi , B2,...,Ci , C2,...) называются пропозициональными буквами или атомами. Считается, что каждая пропозициональная буква может принимать значение И либо Л. Приписывание значений И либо Л атомам считается озна­ чиванием. Множество всех пропозициональных букв обозначим через Р. Отметим, что Р является счетным множеством. Определение пропозициональной формы: 1) все пропозициональные буквы суть пропозициональные формы, 2) еслиЛ и в пропозициональные формы, то ( ^ ) , {А&В), {А vB), (А^В), {А=В) тоже пропозициональные формы, 3) только те выражения являются пропозициональными формами, для ко­ торых это следует из пп.1), 2). Пропозициональные формы часто называют формулами логики высказы­ ваний или формулами. Используя нормальные формы Бэкуса, приведенное выше определение формулы можно записать следующим образом. формула : = А для любого ^ из Р формула : = {—^формула) \ ( формула& формула) \ ( формула v формула) I ( формула ^ формула) \ ( формула = формула) Примеры пропозициональных форм: А, (—^В), (A&( —iB)), (( А&В)^( —iQ), (((^A)vB)^C). Жирные заглавные буквы латинского алфавита {А,В,С,...) или те же буквы с числовыми индексами {Ai,A2,...,Bi,B2,...,Ci,C2,...) употребляются для обозна­ 8