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

Таким образом, связку = можно выразить через —i, и v : A=B-(^AvB) &(^BvA). (1.3) Так как А равносильно — i f — т о А&В равносильно ^(^А)& —i (^В), а последнее согласно закону де Моргана равносильно ^(^А v ^В), следовательно: А&В-^(^А v^B). (1.4) Легко видеть, что имеем: AvB- ^ ( ^A&^B) . (1.5) Из соотношения (1.2) заменой —^А на^ получаем, что A v B - ^ A ^ B . (1.6) Имеют место следующие теоремы. Теорема 1.8. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая только связки —i, с&, v, причем связка —i относится только к пропозициональным буквам. Доказательство. Связки^ и = можно исключить согласно соотношениям (1.2) и (1.3). При этом останутся только связки v. Если связка —i стоит перед скобкой, например, —i(A&BvCv - пВ), то на основании законов де Моргана можно внести —i под скобки, при этом связка & меняется на v, а v на &, а связки ^ и = нигде не появляются. Внеся —i под скобки, перед которыми они стоят, добьемся, чтобы —i относилась только к буквам. Теорема доказана. Теорема 1.9. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая либо только связки —i, &, либо только —1, v, либо только —1, Доказательство. Покажем, что можно оставить только связки —i и &. Связки ^ и = можно исключить (если они есть) на основании соотношений (1.2) и (1.3), а затем по (1.5) исключим v. В результате останутся только —i и cfe. Остальные случаи доказываются аналогичным образом на основании соотношений (1.1)-(1.6). Будем рассматривать формы, содержащие только связки -п, &, v. Как уже установлено, всякая форма может быть приведена преобразованиями равносильности к такому виду. Считается, что связка & двойственна связке v и наоборот. Пропозициональные формы Л и Л * называются двойственными, если одна получается из другой заменой каждой связки cfe и v на двойственную. Например, если Л ={А\/^В)&С, то Л* ={А cfe —i5)vC. Отношение двойственности взаимно: если А двойственно Л*, то Л* двойственной. Следующую теорему счшдйотзаконом двойственности. 15