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

Пропозициональную букву с отрицанием либо без отрицания, называют литерой или литералом (литерал) логики высказываний. Дизъюнкт, не содержащий ни одну литеру, называется пустым дизъюнктом и обозначается символом . Литеры L и —iL называются контрарными. Например, в дизъюнктах Dj=Pv -4Q и Z)2= —J^vQvS литеры Р и —Р контрарные. Также контрарны литеры Q и -б- Пусть для дизъюнктов dj и d2 существует литера Lj в dj, которая контрарна литере L2 в Z)^. Удалив Lj и L2 из Dj и D2 соответственно, построим дизъюнкцию оставшихся частей Dj и Z)^. Полученный таким образом дизъюнкт называется бинарной резольвентой Dj и Z)^, его часто обозначают через R. Примеры. 1. Пусть dj =PvQ, d2 = —РvТ, тогда r =QvТ. 2. Пусть di =P, d 2= —P v Q (D2~P^>Q), тогда r =Q, или из и P^Q получаем Q. 3. Пусть di= -^vq (di=p^), d2= -^ qvt ( d2=q ^ t ) , тогда r= -^vt (r =P^T). Таким образом, из P^>Q и Q^T получаем Р^Т. Теорема 3.5. Пусть для дизъюнктов Z); и Z)^ существует резольвента r. Тогда r есть логическое следствие из dj и Z)^. Доказательство. Пусть Dj=PvDj^, D2= —PvD2^, где Z)/* - оставшаяся часть дизъюнкта Z)/, i=l,2. Тогда/? =Dj^ vD2^ является бинарной резольвентой для Dj И D2. Докажем, что D „ D2 h R. Выпишем всевозможные наборы истинностных значений букв, входящих в Dj и D2. Выберем набор, положим к- ый, на котором dj=m и В2=И. Допустим, что на этом ^-ом наборе Р принимает значение И, тогда —Р=Л, поэтому должно быть В2*=И, следовательно, D i ^ v D2^=M. Таким образом, из истинности Dj и D2 получили истинность Dj^v D2'' В случае, если на ^-ом наборе Р=Л, то Dj^=H и вновь получаем, что из истинности Dj И D2 следует истинность Dj^^v D2^\ В силу произвольности выбранного набора получаем, что из истинности Dj и Z)^ следует истинность для r =di^vd2^, ЧТО И требовалось. Рассмотрим задачу выяснения, будет ли в логическим следствием из Ai^2i---Am, ТО есть истинна ли следующая запись: В § 1 данной главы показано, что эта задача сводится к выяснению невыполнимости формы c=aj&a2&.. .&ат& —в. Пайдем для формулы С ее к.н.ф., то есть получим конъюнкцию дизъюнктов: c=dj&d2&...&dk. Множество дизъюнктов {Di,D2,...,Dk} считается невыполнимым тогда и только тогда, когда формула С невыполнима. 62