Логическо програмиране 2004/05 - упражнения

Работим в сигнатурата $$\Sigma = (\{c,f\},\{p,q\},\rho)$$, като $$\rho(c) = 0, \rho(f) = \rho(q) = 1, \rho(p) = 2$$.

1. Кои от следните формули са предикатни тавтологии? Докажете или дайте контрапример:
   • q(x) v not(q(x)).
   • not(q(x) & not(q(x))).
   • (p(x,y) -> q(x)) <-> (not(q(x)) -> not(p(x,y))).
   • $$\forall$$x not(q(x)) <-> not($$\exists$$x q(x)).
   • $$\exists$$x not(q(x)) <-> not($$\forall$$x q(x)).
   • $$\forall x\exists y$$ p(x,y) <-> $$\exists y\forall x$$ p(x,y).
2. Изберете подходяща сигнатура и изкажете следните изречения с формула от първи ред. Кои от тях са предикатни тавтологии?
   • Всички плодове в кошницата са лоши
   • Ако всеки предшествени на предшественика на даден човек е също предшесвеник на този човек и никой не е предшественик сам на себе си, то съществува човек, който няма предшественици
   • Всеки бръснар в Джонсвил бръсне тези и само тези хора, които не бръснат сами себе си. Следователно в Джонсвил няма нито един бръснар
   • Ако двама души са родственици на трети, то първият е родственик на втория. Всеки е родственик на някого. Следователно ако Джон е родственик на Уилям, а Уилям - на Едит, тогава Джон е родственик на Едит
   • Ако всеки обича себе си, то поне някой някого обича
   • Щом всички обичат Джейн, то всички са обичани