ИДПО. Задание на семестровую КР. 2014


Оглавление TOC \o "1-3" \h \z \u ИДПО. Задание на КР по Матлогике PAGEREF _Toc402478781 \h 1Исчисление высказываний PAGEREF _Toc402478782 \h 1Логика предикатов PAGEREF _Toc402478783 \h 2Основные понятия PAGEREF _Toc402478784 \h 2Подстановки PAGEREF _Toc402478785 \h 4Унификация. Метод резолюции. PAGEREF _Toc402478786 \h 7Алгоритмическая модель «Машина Тьюринга» PAGEREF _Toc402478787 \h 8
ИДПО. Задание на КР по МатлогикеИсчисление высказыванийИспользуя замкнутые семантические таблицы, доказать, что следующие выражения являются тавтологиями.














Используя метод резолюций, доказать следования:
a∨b,a∨c,b∨d⊢c∨d;
a→b,a→c,b∨c⊢a;
a→c,b→d,c∨d⊢a∨b;
p→q,q→r⊢p→r;
a→b∨c, b→d,c→d⊢d.
Исчисление секвенций
Доказать, что следующие правила являются допустимыми (Правило Σ1,Σ2,…,ΣKΣ называется допустимым в ИС, если из выводимости секвенций Σ1,Σ2,…,ΣK следует выводимость секвенции Σ):
(Сечение): Γ1⊢U, Γ2,U⊢BΓ1,Γ2⊢B;
(Объединение посылок): Γ,U,B⊢CΓ,U&B⊢C;(Расщепление посылок): Γ,(U&B)⊢CΓ,U,B,⊢C;
(Разбор случаев): Γ,U⊢C; Γ,B⊢CΓ,U∨B⊢C;
(Контрапозиция): Γ,U⊢BΓ,B⊢U; (Доказательство от противного): Γ,U⊢BΓ,B⊢U.Вывести следующие секвенции:
U→B,B→C⊢U→C; U→B→C⊢B→U→C;
U→B→C⊢U&B→C;U&B→C⊢U→B→C; U→B⊢B→C→U→C; U→B⊢C→U→C→B; U→B⊢C&U→C&B; U→B⊢U&C→B&C;
U→B⊢U∨C→B∨C;
U→B⊢C∨U→C∨B;
U⊢U→B;
U⊢U→B;B⊢U→B;
U→B⊢B→U;
U→B⊢B→U;U→B⊢B→U;U→B⊢B→U.Логика предикатовОсновные понятияПусть f1, g2, h3 F. Являются ли термами следующие слова:
f1(g2(v0, v1));
g2(f1(v2), h3(v0, v1, v2));
f1(g2(v0), h3(v0, v1, v2))?
Пусть f, g, h, F – одноместный, двуместный и трехместный функциональные символы соответственно. P, Q R – одноместный и трехместный предикатные символы соответственно. Являются ли формулами следующие слова:
Q(v0, f(v1), h(v1, v2, v2));
P(v0)v1(Q (v0, v1, v2) & P (g(v0, v1)));
Q (P(v0), f(v1), f(v2));
f (h(v0, v1, v1))?
Показать, что слово v0v1 … v0 (P(v1) & … &P(v0)), где PR, не является формулой.
Выписать все подформулы формул:
Q(f(v0), g(v0, v1));

Описать множество термов от одной переменной v0 и
5.1. Функционального символа f1;
5.2. Функционального символа g2.
Какие вхождения переменных являются свободными, а какие связанными в следующих формулах:
xP(x,y)yQ(y);
xP(x,y)yR(x,y);
6.3.
7.Используя предикат <, записать следующие утверждения в системе (N; <, =, +, -):
7.1. Существует число х, меньшее 5 и большее, чем 7;
7.2.Для любого числа х существует у, меньшее х;
7.3. Для любого числа х существует число у, большее, чем х;
7.4. Для любых чисел х и у существует такое число у, что для любого z, если разность z-5<y, то разность x-7<3.
Пусть математическая модель сигнатуры имеет вид M=(N; S3, P3), где S(x,y,z) истинна тогда и только тогда, когда x+y=z, и P(x,y,z) истинна тогда и только тогда, когда x*y=z. Записать формулу с одной свободной переменной х, истинную в М тогда и только тогда, когда
x=0;
x=1;
x=2;
x-четно;
x− нечетно
Рассмотрим модели с одним двуместным предикатом R(x,y). Записать, что данный предикат
Рефлексивен;
Симметричен;
Транзитивен;
Иррефлексивен;
Асимметричен;
Антисимметричен;
R(x,y) – эквивалентность.
Выполнимы ли следующие формулы:
xP(x);
xP(x);
xy(Q(x,x)&Q(x,y)
xy(P(x)&P(y);
xy(Q(x,y)zR(x,y,z));
(P(x)yP(y)Являются ли тождественно истинными следующие формулы:
(xP(x)xP(x));
(xP(x)xP(x);
(xyQ(x,y)yxQ(x,y));
(xyQ(x,y)yxQ(x,y))?
Привести к пренексной нормальной форме, считая U и B бескванторными формулами:
xyzuU;
(xyU(x,y)&xyB(x,y));
(xyU(x,y)xyB(x,y));
(xyU(x,y)xyB(x,y)).
Для формулы xzyu ((y>z y>x) & (u<z) & (u<x)) построить сколемовскую формулу. Для системы (N,<) найти требуемое обогащение.
Для формулы xyzt (P(x,t) & P(y,z)) построить сколемовскую формулу. Для любой системы ((М, P), где М={0,1}, найти подходящее обогащение.Для формулы xyzvt (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.
Привести к СНФ:
(xyQ(x,y) xyQ(x,y));
xyzv R(x,y,z,v);
xyvz R(x,y,z,v).
ПодстановкиПусть - подстановки, Е – тождественная подстановка, - атомарная формула. Докажите, что



Определить, какие из следующих пар формул являются вариантами:
P(f(x,y), g(z), a) и P(f(y,x), g(u), a);
P(x,x) и P(x,y).
Докажите, что
Если free (x,t,A), то ├ (A{x/t} x A(x));
Если free (x,t,A), то ├ (x A(x) A{x/t});
├ (A(x) xA(x));
├ (x A(x) x A(x));
├ xy (x=y);
├ xy (x=y);
├ xy (x=y y=x);
├ xyz [x=y & y=z) x=z].
Предположим, что драконы существуют, и мы поймали одного из них. Запишите следующие предложения в виде хорновских дизъюнктов:
Всякий дракон, живущий в зоопарке, несчастен;
Всякое животное, встречающееся с вежливыми людьми, счастливо;
Все люди, посещающие зоопарк, вежливы;
Животные, живущие в зоопарке, встречаются с людьми, посещающими зоопарк.
Сформулируйте следующие высказывания, данные на обыденном языке, в виде хорновских дизъюнктов:
х – мать у, если х – женщина и родитель у.
х – отец у, если х – мужчина и родитель у;
х – человек, если его родитель человек;
х – человек, если родитель х – человек;
никто не родитель самому себе.
Пусть есть два сосуда вместимостью 5 и 7 литров. Найти последовательность действий, которая приведет к тому, что в семилитровом сосуде будет ровно 4 литра воды. Разрешены только два действия:
наполнить сосуд;
переливать воду из одного сосуда в другой, пока один из них не будет полон или пуст.
Сформулируйте задачу и разрешенные действия с помощью хорновских дизъюнктов.
Пусть ({a,b}, P2) – модель сигнатуры языка логики предикатов и задана функция интерпретации I такая, что (a,a), (b,b) I(P), а (a,b), (b,a) I(P). Определить, являются ли следующие формулы истинными в данной интерпретации:
xyP(x,y);
ExyP(x,y);
xy(P(x,y) P(Y,x);
xyP(x,y);
y
xP(x,x).
Пусть дано предложение U: xP(x)xP(x).
Докажите, что предложение U всегда истинно в интерпретации, область которой состоит из одного элемента.
Найдите интерпретацию с предметной областью, состоящей из двух элементов, в которой предложение U ложно.
Найдите интерпретацию с D={a,b}, в которой предложение xyP(x,y) было бы истинным, а предложение xyP(x,y) – ложным.
Пусть задана алгебраическая система сигнатуры, имеющая вид ({1,2,3,4,5,6,7,8,9}; | c1, c2, …, c9) и функция интерпретации I такая, что каждой константе ciС, i= она сопоставляет один из элементов предметной области, т.е. i I[ci]=i, I[|]– отношение делимости: x|yy делится на x (иначе «х делитель у»). Какие из следующих выражений истинны в данной интерпретации. Ответ аргументируйте.
y |(c1,y),
x [|(x,c5)(x=c1)(x=c5)];
xy |(x,y);
xy |y,x).
Приведите к предваренной нормальной форме следующие предложения:



Определить теоретико-множественную форму следующих предложений:
A1:
A2:
A3:
Пусть 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.
Определите эрбрановские множества H0 и H1 для множества дизъюнктов
S={{P(f(x), a, g(f(x), b))}}. Определите все основные примеры для S на множествах H0 и H1.
Докажите с помощью замкнутых семантических таблиц общезначимость следующих предложений:





Докажите средствами замкнутых семантических таблиц, что следующие предложения недоказуемы по Бету:
A1:
A2:
Найдите две интерпретации этих формул, в которых А1 и А2 соответственно ложны.
Найдите опровержения приведенных ниже множеств методом семантических деревьев:
18.1.
18.2.
Постройте семантические деревья и определите невыполнимые основные примеры, соответствующие следующим формулам:
:
:
:
Определите, является ли предложение : логически истинным или нет. Постройте соответствующее доказательство или контр пример.
Найдите невыполнимые основные примеры для следующих множеств дизъюнктов:



Унификация. Метод резолюции.Определить, какие из следующих множеств предложений унифицируемы. Если они унифицируемы, найдите наиболее общий унификатор (НОУ).
S={{P(f(a),g(x)}, {P(y,y)}};
S={{P(a, x, h (g(z)))}, {P(z, h(y), h(y))}};
S={{Q(f(w), a, z)}, {Q(w,b,f(z))}};
S={{любит (w, f(y))}, {любит (Джордж, футбол)}};
S={{R(w,y), Q(w, f(z), z),R(w,w)}, {R(w,z), Q(f(w),w,z)}};
S={{P(f(x),a)}, {P(y,f(w))}};
S={{P(f(x),z)}, {P(y,a)}}.
Определите, какие из следующих предложений унифицируемы, найдите НОУ:
S={{Q(x)}, {Q(b)}};
S={{Q(a,x)}, {Q(a,a)}};
S={{Q(a,x,f(x))}, {Q(a,y,y)}};
S={{Q(x,y,z)}, {Q(u,h(v,v)u)}};
S={{P(x,g(x),y,h(x,y),z,f(x,y,z))}, {P(u,v,e(v),w,k(v,w),s)}}.
Полагаем, что a,b – константы, f,g,h,e,kF.
Определите невыполнимый основной пример для следующего множества дизъюнктов:
S={{P(x,a,g(x,b))}, {P(f(y),z,g(f(a),b)}}.
Известны истинные утверждения: «Воробей имеет крылья», «Воробей несет яйца» и «Если животное имеет крылья и несет яйца, то это птица». Требуется доказать утверждение «Воробей является птицей». Для этого выполните следующее;
a) переведите эти утверждения на язык логики предикатов первого порядка, выделив все необходимые группы формул, включая целевую;
b) сделайте опровержение целевой формулы;
c) переведите все формулы в клаузальную форму;
d) используя резолюцию, докажите (выведите) истинность целевой формулы.
Предположим, что верны утверждения, представленные ниже:
Существует хотя бы один дракон.
Дракон либо спит в своей пещере, либо охотится в лесу.
Если дракон голоден, он не может спать.
Если дракон устал, он не может охотиться.
Применить метод резолюции, чтобы ответить на следующие вопросы:
Что делает дракон, когда он голоден?
Что делает дракон, когда он устал?
Что делает дракон, когда он голоден и устал?
Пусть следующие предикаты интерпретируются так:
T(x,y,u,v) – “x,y,u,v – это трапеция»;
P(x,y,u,v) – «отрезки xy и vu – параллельны»;
E(x,y,z,u,v,w) – ”угол (xyz) равен углу (uvw)”.
И пусть даны предложения:
A1: xyuv[T(x,y,u,v)P(x,y,v,u)] – определение трапеции;
A2: xyuv [P(x,y,u,v)E(x,y,v,u,v,y)] – если xy параллельно vu, то угол (xyv) равен углу (uvy);
A3: T(a,b,c,d) (abcd – трапеция).
Алгоритмическая модель «Машина Тьюринга»Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что q1 * начальное состояние, q0 * заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте.
a) Р=10[01]21.b) P = 130212, c) P = 13013.

a) P=13012,b) P = 16,c) P= 1401.
По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию (q0 * заключительное состояние).
2.1.
T: q1 q2
0 q01S q10R
1 q20R q21L
а) К1 = 12q11301,b)K1 = 1q114.

a) K1= 1q115, b) K1 = q11301, c) K1 = 10q114.
Построить композицию Т1Т2 машин Тьюринга Т1 и Т2 (по паре состояний (q10, q21)) и найти результат применения композиции T1T2 к слову P (q20 - заключительное состояние машины Т2), если
3.1. программы машин Т1 и Т2 заданы таблицами:
T1: q11 q12 q13 T2: q21 q22
0 q100L q130R q110R 0 q221Ll q200R
1 q121R q131R q110R 1 q221L q210L
Найти композицию машин T1, T2:
a)P = 140213012,b) P = 1201013.
3.2.
a) P = 12013012,b) P = 120120212.
Построить машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления, т.е. машину Т, удовлетворяющую условию: Т((m)унарн.+(n)унарн.) = (m+n)унарн. Привести пример сложения.
Построить машину Тьюринга, удваивающую числа, записанные в унарной системе счисления.
Построить машину Тьюринга, переводящую числа, записанные в унарной системе счисления, в двоичную систему счисления. Привести пример перевода для слова ||||.
Построить машину Тьюринга, переводящую числа, записанные в унарной системе счисления, в троичную систему счисления.

Приложенные файлы

  • docx 14806888
    Размер файла: 123 kB Загрузок: 0

Добавить комментарий