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

A i kB~^ ( \A\ / ^B ) . (1.4) Легко видеть, нто имеем: & l S ) . (1.5) Из соотношения (1.2) заменой ааА получаем, что AvB~^A=>B. (1.6) Имеют место следующие теоремы. Теорема 1.4. Для каждой пропозициональной формы Л сущест-! вует равносильная ей форма, содержащая только связки 1 , &, v, причем связка 1 относится только к пропозициональным буквам. I Доказательство. Связки =i> и s можно исключить согласно соотношениям (1.2) и (1-3). При этом останутся только связки 1, V. Если пропозициональная связка 1 стоит перед некото­ рой скобкой, например, 1 (.^&jSvCvl 5), то на основании законов де Моргана можно внести 1 под скобки, при этом связка & меняется на V, а V на &, а связки и S нигде не появляются. Внеся 1 под скобки, перед которыми они стоят, добьемся, чтобы 1 относилась только к пропозициональным буквам. Теорема доказана. Теорема 1.5. Для каждой пропозициональной формы А сущест­ вует равносильная ей форма, содержащая либо только связки 1, &, либо только 1, V, либо только 1, =>. Доказательство. Покажем, что можно оставить только связки 1 и &. Связки ^ и = можно исключить (если они есть) на основании соотношений (1.2) и (1.3), а затем по (1.5) исключим v. В результате останутся только 1 и &, Остальные случаи доказывают­ ся аналогичным образом на основании соотношений (1.1) - (1.6). Будем рассматривать пропозициональные формы, содержащие только связки 1, V. Как уже установлено, всякая пропозициональ­ 29