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

и А=>В. Требуется найти все логические следствия этих форм. Для этого составляем конъюнкцию данных форм; А £ ( А = > В ) и находим равносильную ей с.к.н.ф.: (^v5)&(^v1 5)&(1 AvB). Искомые следст­ вия суть; A v B - AW ] B -, 1 ^ v 5 ; { A - ^ B ) 8 L { A V ] B ) ~А-, {A\/B)8C(\AVB)~B-, (^v1 5 )&(1 A-^B) ~ ASB; (^v S )&(^v1 S)&("UvS) ~ A&B. 6. Найти все следствия для следующих форм: а) А&В, 1 В; б) А=>В, 1 А; в) 5=>~| А,А; г) А=>В, ~| А; д) BvC, А,B=z>C; е) ] А'^В,В=>С, 1 С=>А. Логическое следствие называется простые следствием, если оно является элементарной суммой, не содержащей повторяющихся сла­ гаемых, а таклсе не является тавтологией и является минимальной, т.е. после отбрасывания какого-нибудь из ее членов перестает быть логи­ ческим следствием из данных форм. Так, в разобранном примере про­ стыми следствиями из ^ и А=>В являются следствие А и следствие В. Конъюнкция всех простых следствий данной формы А оказывается сокращенной к.н.ф. 7. Найти все простые следствия для пропозициональных форм задачи 6. 8. Для заданных посылок найти все их простые следствия. (Ука­ зание: найти сначала сокращенные к.н.ф. для конъюнкции посылок): а) A=>^ В,AvC, 1 (S&C); б) (Л&В)=:>1 С,В, С; в) (AvB)&C, С; г) А=В. A=>Cv^ S; д)А=>В, ~]в=>С, В. Рассмотрим пример использования сокращенных к.н.ф. В со­ вершении некоторого поступка подозревается только одно из четырех лиц; Л1, Л2, ЛЪ и ЛА. Л\ утверждает, что поступок совершил Л2; Л2 утверждает, что поступок совершил Л4; ЛЗ говорит, что он не совер­ шал этого поступка, и Л4 тоже говорит, что он этого поступка не со­ вершал. Кто же совершил поступок, если известно, что только одно из этих утверясдений истинно? 131