1. Запишете в подходящ език следните изречения и проверете дали са тавтологии; ако не са, покажете структура, в която не са верни и структура, в която са тъждествено верни:
    • "Ако: всеки бръснар в Джонсвил бръсне тези и само тези хора, които не бръснат сами себе си, то: в Джонсвил няма нито един бръснар"
    • "Ако: двама души са родственици на трети, то първият е родственик на втория и всеки е родственик на някого, то: ако Джон е родственик на Уилям, а Уилям - на Едит, тогава Джон е родственик на Едит"
    • "Ако: двама души са родственици на трети, то първият е родственик на втория и всеки е родственик на някого, то: всеки е родственик на някого"
    • "Ако всеки обича себе си, то някой някого обича"
    • "Ако всички обичат Джейн, то всички са обичани"
    • "Ако конете са животни, то главите на конете са глави на животни"
  2. Нека M е непразно множество. Докажете, че следните мноожества са определими в структурата S = (2M;$$\subseteq$$) (навсякъде A,B,C са подмножества на M):
    • {$$\emptyset$$} (внимание, не $$\emptyset$$, a {$$\emptyset$$}!)
    • {M}
    • {(A,B) | A = B}
    • {(A,B) | A $$\neq$$ B}
    • {(A,B,C) | C = A U B }
    • {(A,B,C) | C = A $$\cap$$ B}
    • {(A,B) | A = $$\overline{B}$$}
    • { A | A се състои от точно един елемент (A е синглетон)}
  3. Да се изкаже постулатът на Евклид в език със три предикатни символа: point/1, line/1, lies/2:
    • За всяка права и точка, която не лежи на нея съществува единствена права, успоредна на нея
  4. Определимо ли е в структурата S = (<o;s;=>,N,I) за I(o) = 0, I(s)(x) = x+1, множеството
    • A = { n; в десетичния запис на $$\pi$$ има блок от поне n седмици }
    • Упътване: не се иска множеството да се определи, а да се докаже, че е определимо, т.е. че винаги може да се намери формула, която го определя.
Последно модифициране: събота, 12 ноември 2011, 17:38