Prolog — задача 76 кто украл перец

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 месяца назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6773
      @admin
      StudLance.ru

      Задача:

      Подозрения Короля пали на Мартовского Зайца, Болванщика и Соню. Солдаты были отправлены к их домику,
      но при обыске перца не обнаружили. Поскольку трое подозреваемых могли спрятать перец в каком-нибудь тайнике,
      их арестовали из общих соображений.

      На суде Мартовский Заяц заявил, что Болванщик невиновен,
      а Болванщик утверждал, что Соня невиновна. Соня
      когда ей предоставили слово, пробормотала что-то неразборчивое себе под нос, но так и не проснулась,
      и ее показания не были внесены в протокол.
      Выяснилось, что ни один невиновный не высказал ложного утверждения (Напомним, что те, кто крадет перец,
      никогда не говорят правды). Кроме того, установлено, что перец украл кто-то один.
      Кто из трех обитателей домика виновен (если кто-нибудь из трех вообще виновен)?

      Приведенные тут варианты решения очень легко читаются — я думаю, к ним не нужны дополнительные пояснения. Если что-то не понятно — спрашивайте. Наиболее сложные предикаты — входит_в, без_повторов и убрать_повторы подробно разобраны тут. Там же, объясняется как понять findall. Также, понять решение может помочь статья «Решение логических задач на Prolog«.

      Тут приводится несколько решений, чаще всего каждое следующее решение получено незначительной доработкой предыдущего. Например, первая программа может выводить множество повторяющихся вариантов решений, а следующая — убирает повторы. Наиболее правильным всегда является последний варианты, однако первые варианты обычно проще (их проще понять, изучение кода стоит начать с них).

      Решение 1

      DOMAINS 
      	подозреваемый = заяц; болванщик; соня
      	гипотеза = вор(подозреваемый)
      	подозреваемые = подозреваемый*
      	
      	высказывание = не_вор(подозреваемый)
      	высказывания = высказывание*
      PREDICATES      
             nondeterm возможный_вор(подозреваемый)
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(подозреваемый, высказывания)
             nondeterm высказывание_истино(высказывание, гипотеза)
             nondeterm все_высказывания_ложны(подозреваемый, гипотеза)
             nondeterm все_высказывания_истины(подозреваемый, гипотеза)
            
             nondeterm не_вор(гипотеза, подозреваемый)
            
      CLAUSES 
      	возможный_вор(заяц).
      	возможный_вор(болванщик).
      	возможный_вор(соня).
      	
      	генерация_гипотезы(вор(Вор)):-
      		возможный_вор(Вор).
      		
      	% заяц сказал что болванщик невиновен
      	сказал(заяц, [не_вор(болванщик)]).
      	% болванщик сказал что соня невиновна
      	сказал(болванщик, [не_вор(соня)]).
      	% соня ничего внятного не сказала
      	сказал(соня, []).
      	
      	высказывание_истино(не_вор(Кто), вор(Вор)):-
      		NOT(Кто = Вор).
      	
      	все_высказывания_ложны(Кто, Гипотеза):-
      		сказал(Кто, []);
      		сказал(Кто, [Высказывание]),
      		NOT(высказывание_истино(Высказывание, Гипотеза)).
      		
      	все_высказывания_истины(Кто, Гипотеза):-
      		сказал(Кто, []);
      		сказал(Кто, [Высказывание]),
      		высказывание_истино(Высказывание, Гипотеза).
      		
      	проверка_гипотезы(Гипотеза):-
      		Гипотеза = вор(Вор),
      		все_высказывания_ложны(Вор, Гипотеза),
      		
      		findall(НеВор, не_вор(вор(Вор), НеВор), НеВоры),
      		НеВоры = [Первый,Второй],
      		все_высказывания_истины(Первый, Гипотеза),
      		все_высказывания_истины(Второй, Гипотеза).
      		
      	не_вор(вор(Вор), НеВор):-
      		возможный_вор(НеВор),
      		NOT(Вор = НеВор).
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
              
              /*генерация_гипотезы(Гипотеза),
              findall(НеВор, не_вор(Гипотеза, НеВор), НеВоры).*/
      

      Решение 2

      DOMAINS 
      	имя = заяц; болванщик; соня
      	роль = виновен; невиновен
      	истинность = истина;ложь
      	
      	структура = имя_роль(имя, роль)
      	гипотеза = структура*
      	высказывания = структура*
      	
      PREDICATES      
             nondeterm возможное_имя(имя)
             nondeterm возможная_роль(роль)
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm проверка_гипотезы(гипотеза)
             nondeterm только_один_вор(гипотеза)
             nondeterm сказал(имя, высказывания)
             nondeterm проверка_высказываний(высказывания, гипотеза, истинность)
             
             nondeterm один_из(структура, гипотеза)
      CLAUSES 
      	возможное_имя(заяц).
      	возможное_имя(болванщик).
      	возможное_имя(соня).
      	
      	возможная_роль(виновен).
      	возможная_роль(невиновен).
      	
      	генерация_гипотезы([
      		имя_роль(заяц, РольЗайца), 
      		имя_роль(болванщик, РольБолванщика), 
      		имя_роль(соня, РольСони)
      	]):-
      		возможная_роль(РольЗайца),
      		возможная_роль(РольБолванщика),
      		возможная_роль(РольСони).
      	
      	только_один_вор([имя_роль(_, виновен),  имя_роль(_, невиновен),  имя_роль(_, невиновен)]).
      	только_один_вор([имя_роль(_, невиновен),  имя_роль(_, виновен),  имя_роль(_, невиновен)]).
      	только_один_вор([имя_роль(_, невиновен),  имя_роль(_, невиновен),  имя_роль(_, виновен)]).
      	
        	один_из(Name,[Name|_]). % предикат взят из примера "Кто украл муку с дублированием"
      	один_из(Name,[_|Хвост]):-
         		один_из(Name,Хвост).
      		
      	% невиновный говорит правду - а виновный - неправду
      	% (ни один невиновный не высказал ложного утверждения)
      	% (те, кто крадет перец, никогда не говорят правды)
      	проверка_гипотезы(Гипотеза):-
      		только_один_вор(Гипотеза),
      		
      		один_из(имя_роль(Вор, виновен), Гипотеза),
      		сказал(Вор, ВысказыванияВора),
      		
      		один_из(имя_роль(А, невиновен), Гипотеза),
      		один_из(имя_роль(Б, невиновен), Гипотеза),
      		NOT(А=Б),
      		сказал(А, ВысказыванияА), сказал(Б, ВысказыванияБ),
      		
      		проверка_высказываний(ВысказыванияВора, Гипотеза, ложь),
      		проверка_высказываний(ВысказыванияА, Гипотеза, истина),
      		проверка_высказываний(ВысказыванияБ, Гипотеза, истина).
      		
      	проверка_высказываний([], _Гипотеза, _Истинность).
      	проверка_высказываний([ПервоеВысказывание|Остальные], Гипотеза, истина):-
      		один_из(ПервоеВысказывание, Гипотеза),
      		проверка_высказываний(Остальные, Гипотеза, истина).
      	проверка_высказываний([ПервоеВысказывание|Остальные], Гипотеза, ложь):-
      		NOT(один_из(ПервоеВысказывание, Гипотеза)),
      		проверка_высказываний(Остальные, Гипотеза, ложь).
      		
      	% заяц сказал что болванщик невиновен
      	сказал(заяц, [имя_роль(болванщик, невиновен)]).
      	% болванщик сказал что соня невиновна
      	сказал(болванщик, [имя_роль(соня, невиновен)]).
      	% соня ничего внятного не сказала
      	сказал(соня, []).
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 3

      DOMAINS 
      	имя = заяц; болванщик; соня
      	роль = виновен; невиновен
      	истинность = истина;ложь
      	
      	структура = имя_роль(имя, роль)
      	гипотеза = структура*
      	высказывания = структура*
      	
      	список_решений = гипотеза*
      	
      PREDICATES      
             nondeterm возможное_имя(имя)
             nondeterm возможная_роль(роль)
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm проверка_гипотезы(гипотеза)
             nondeterm только_один_вор(гипотеза)
             nondeterm сказал(имя, высказывания)
             nondeterm проверка_высказываний(высказывания, гипотеза, истинность)
             
             nondeterm один_из(структура, гипотеза)
             
             nondeterm поиск_решения(гипотеза)
      CLAUSES 
      	возможное_имя(заяц).
      	возможное_имя(болванщик).
      	возможное_имя(соня).
      	
      	возможная_роль(виновен).
      	возможная_роль(невиновен).
      	
      	генерация_гипотезы([
      		имя_роль(заяц, РольЗайца), 
      		имя_роль(болванщик, РольБолванщика), 
      		имя_роль(соня, РольСони)
      	]):-
      		возможная_роль(РольЗайца),
      		возможная_роль(РольБолванщика),
      		возможная_роль(РольСони).
      	
      	только_один_вор([имя_роль(_, виновен),  имя_роль(_, невиновен),  имя_роль(_, невиновен)]).
      	только_один_вор([имя_роль(_, невиновен),  имя_роль(_, виновен),  имя_роль(_, невиновен)]).
      	только_один_вор([имя_роль(_, невиновен),  имя_роль(_, невиновен),  имя_роль(_, виновен)]).
      	
        	один_из(Name,[Name|_]). % предикат взят из примера "Кто украл муку с дублированием"
      	один_из(Name,[_|Хвост]):-
         		один_из(Name,Хвост).
      		
      	% невиновный говорит правду - а виновный - неправду
      	% (ни один невиновный не высказал ложного утверждения)
      	% (те, кто крадет перец, никогда не говорят правды)
      	проверка_гипотезы(Гипотеза):-
      		только_один_вор(Гипотеза),
      		
      		один_из(имя_роль(Вор, виновен), Гипотеза),
      		сказал(Вор, ВысказыванияВора),
      		
      		один_из(имя_роль(А, невиновен), Гипотеза),
      		один_из(имя_роль(Б, невиновен), Гипотеза),
      		NOT(А=Б),
      		сказал(А, ВысказыванияА), сказал(Б, ВысказыванияБ),
      		
      		проверка_высказываний(ВысказыванияВора, Гипотеза, ложь),
      		проверка_высказываний(ВысказыванияА, Гипотеза, истина),
      		проверка_высказываний(ВысказыванияБ, Гипотеза, истина).
      		
      	проверка_высказываний([], _Гипотеза, _Истинность).
      	проверка_высказываний([ПервоеВысказывание|Остальные], Гипотеза, истина):-
      		один_из(ПервоеВысказывание, Гипотеза),
      		проверка_высказываний(Остальные, Гипотеза, истина).
      	проверка_высказываний([ПервоеВысказывание|Остальные], Гипотеза, ложь):-
      		NOT(один_из(ПервоеВысказывание, Гипотеза)),
      		проверка_высказываний(Остальные, Гипотеза, ложь).
      		
      	% заяц сказал что болванщик невиновен
      	сказал(заяц, [имя_роль(болванщик, невиновен)]).
      	% болванщик сказал что соня невиновна
      	сказал(болванщик, [имя_роль(соня, невиновен)]).
      	% соня ничего внятного не сказала
      	сказал(соня, []).
      	
      	поиск_решения(Гипотеза):-
      		генерация_гипотезы(Гипотеза),
             	 	проверка_гипотезы(Гипотеза).
      GOAL    
              findall(Гипотеза, поиск_решения(Гипотеза), Решения),
              NOT(Решения = []), write("Решения: "), write(Решения);
              write("никто из подозреваемых не крал муку").
      

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×