Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Логика предикатов

Читайте также:
  1. Билет 6. Логика имеет особое значение также в деятельности юристов.
  2. Билет №74.Логика вопроса. Виды. Правила построения.
  3. Вопрос 4. Логика межвременного выбора индивида.
  4. Вопрос. Специфика структуры религии, логика и обусловленность ее внутренних уровней.
  5. ДИАЛЕКТИЧЕСКАЯ ЛОГИКА
  6. Индуктивная логика
  7. ИНТУИЦИОНИСТСКАЯ ЛОГИКА
  8. История и логика развития естествознания
  9. История и логика развития курса «Основы безопасности жизнедеятельности» в школе
  10. Логика 1 лекция
  1. Пусть f1, g2, h3 Î F. Являются ли термами следующие слова:

a. f1(g2(v0, v1));

b. g2(f1(v2), h3(v0, v1, v2));

c. f1(g2(v0), h3(v0, v1, v2))?

2. Пусть f, g, h, ÎF – одноместный, двуместный и трехместный функциональные символы соответственно. P, Q ÎR – одноместный и трехместный предикатные символы соответственно. Являются ли формулами следующие слова:

a. Q(v0, f(v1), h(v1, v2, v2));

b. P(v0)®"v1(Q (v0, v1, v2) & P (g(v0, v1)));

c. Q (P(v0), f(v1), f(v2));

d. f (h(v0, v1, v1))?

3. Показать, что слово $v0"v1 … "v0 (P(v1) & … &P(v0)), где PÎR, не является формулой.

4. Выписать все подформулы формул:

a. Q(f(v0), g(v0, v1));

b.

5. Описать множество термов от одной переменной v0 и

a. Функционального символа f1;

b. Функционального символа g2.

6. Какие вхождения переменных являются свободными, а какие связанными в следующих формулах:

a. "xP(x,y)®"yQ(y);

b. "xP(x,y)®"yR(x,y);

c.

7. Является ли терм t свободным для переменной v в формуле U?

a. t=f(x,z), v=y, U="x P(x,y);

b. t=f(y,z), v=y, U=((P(y,z) ® $z q(z)).

c. T=y2-y; U=$y (v+y<0), если предметной областью является множество действительных чисел?

8. Доказать, что

a. постоянный терм свободен для любой переменной в любой формуле;

b. переменная x свободна для x в любой формуле;

c. если формула U не содержит свободных вхождений переменной x, то любой терм свободен для x в этой формуле.

9. Используя предикат <, записать следующие утверждения в системе (N; <, =, +, -):

a. Существует число х, меньшее 5 и большее, чем 7;

b. Для любого числа х существует у, меньшее х;

c. Для любого числа х существует число у, большее, чем х;

d. Для любых чисел х и у существует такое число у, что для любого z, если разность z-5<y, то разность x-7<3.

10. Пусть математическая модель сигнатуры имеет вид M=(N; S3, P3), где S(x,y,z) истинна тогда и только тогда, когда x+y=z, и P(x,y,z) истинна тогда и только тогда, когда x*y=z. Записать формулу с одной свободной переменной х, истинную в М тогда и только тогда, когда

a. x=0;

b. x=1;

c. x=2;

d. x – четно;

e. x – нечетно;

f. x – простое число.

11. Выполнимы ли следующие формулы:

a. $xP(x);

b. "xP(x);

c. $x"y(Q(x,x)&ØQ(x,y);

d. $x$y(P(x)&ØP(y);

e. $x"y(Q(x,y)®"zR(x,y,z));

f. (P(x)®"yP(y).

15. Являются ли тождественно истинными следующие формулы:

a. ($xP(x)®"xP(x));

b. Ø($xP(x)®"xP(x);

c. ($x"yQ(x,y)®"y$xQ(x,y));

d. ("x$yQ(x,y)®$y"xQ(x,y))?

16. Привести к пренексной нормальной форме, считая U и B бескванторными формулами:

a. Ø$x"y$z"uU;

b. ($x"yU(x,y)&$x"yB(x,y));

c. ($x"yU(x,y)®$x"yB(x,y));

d. ($x"yU(x,y)®$x"yB(x,y)).

17. Для формулы "x$z"y$u ((y>z ® y>x) & (u<z) & Ø(u<x)) построить сколемовскую формулу. Для системы (N,<) найти требуемое обогащение.

18. Для формулы "x"y$z$t (P(x,t) & ØP(y,z)) построить сколемовскую формулу. Для любой системы ((М, P), где М={0,1}, найти подходящее обогащение.

19. Для формулы "x"y$z$v"t (ØS(x,y,y) ® (S(a,v,x) & P(v,t,t))) и системы (N, S3, P3) построить сколемовские функции, если S(x,y,z)=t Û x+y=z; P(x,y,z)=t Û x*y=z.

20. Привести к СНФ:

a. ($x"yQ(x,y) ®"x$yQ(x,y));

b. $x"y$z"v R(x,y,z,v);

c. "x$y"v$z R(x,y,z,v).

6. Пусть ({a,b}, P2) – модель сигнатуры языка логики предикатов и задана функция интерпретации I такая, что (a,a), (b,b) Î I(P), а (a,b), (b,a) ÏI(P). Определить, являются ли следующие формулы истинными в данной интерпретации:

a. "x$yP(x,y);

b. Ex"yP(x,y);

c. "x$y(P(x,y) ® P(Y,x);

d. "x"yP(x,y);

e. $y

f. "xP(x,x).

8. Пусть дано предложение U: $xP(x)®"xP(x).

a. Докажите, что предложение U всегда истинно в интерпретации, область которой состоит из одного элемента.

b. Найдите интерпретацию с предметной областью, состоящей из двух элементов, в которой предложение U ложно.

9. Найдите интерпретацию с D={a,b}, в которой предложение $x$yP(x,y) было бы истинным, а предложение "x$yP(x,y) – ложным.

10. Пусть задана алгебраическая система сигнатуры, имеющая вид ({1,2,3,4,5,6,7,8,9}; | c1, c2, …, c9) и функция интерпретации I такая, что каждой константе ciÎС, i= она сопоставляет один из элементов предметной области, т.е. "i I[ci]=i, I[|]– отношение делимости: x|yÛy делится на x (иначе «х делитель у»). Какие из следующих выражений истинны в данной интерпретации. Ответ аргументируйте.

a. "y |(c1,y),

b. "x [|(x,c5)«(x=c1)Ú(x=c5)];

c. $x"y |(x,y);

d. $x"y |y,x).

11. Приведите к предваренной нормальной форме следующие предложения:

a.

b.

c.

12. Определить теоретико-множественную форму следующих предложений:

a. A1:

b. A2:

c. A3:

13. Пусть S1 и S2 – два множества дизъюнктов:

S1={{P(a)}, {P(x), P(f(x))}};

S2={{P(x), Q(x)}, {R(z)}, {T(y), ØW(y)}}.

Определите эрбрановские множества H3 для S1 и H1, …, H10 для S2.

14. Определите эрбрановские множества H0 и H1 для множества дизъюнктов

S={{P(f(x), a, g(f(x), b))}}. Определите все основные примеры для S на множествах H0 и H1.

15. Докажите с помощью замкнутых семантических таблиц общезначимость следующих предложений:

17. Докажите средствами замкнутых семантических таблиц, что следующие предложения недоказуемы по Бету:

a. A1:

b. A2:

Найдите две интерпретации этих формул, в которых А1 и А2 соответственно ложны.

18. Найдите опровержения приведенных ниже множеств методом семантических деревьев:

19. Постройте семантические деревья и определите невыполнимые основные примеры, соответствующие следующим формулам:

a. :

b. j:

c. t:

20. Определите, является ли предложение s: логически истинным или нет. Постройте соответствующее доказательство или контр пример.

21. Найдите невыполнимые основные примеры для следующих множеств дизъюнктов:


Дата добавления: 2014-11-24; просмотров: 23 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2021 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав