239
ПРИЛОЖЕНИЯ
Варианты типового задания
1.Запишите приведенное высказывание в виде формулы логики высказываний. Для полученной формулы составьте таблицу истинности.
2.Упростите формулу логики высказываний, используя основные равносильности между формулами.
3.Составьте программу нахождения совершенной конъюнктивной нормальной формы (с.к.н.ф.) на любом известном вам алгоритмическом языке и найдите с.к.н.ф. для заданной булевой функции. Проверьте полученный результат, построив с.к.н.ф. равносильными преобразованиям.
4.Методом резолюций выясните, истинно ли приведённое утверждение. Решите эту задачу, используя два метода из следующих: метод исчерпания уровня, стратегия вычёркивания, лок-резолюция и табличный метод (последний для случая, если заданное множество является множеством хорновских дизъюнктов).
5.Запишите предложение в виде формулы логики предикатов.
6.Привести пример интерпретации, для которой данная формула истинна.
7.Получить предваренные нормальные формы и скулемовские стандартные формы для данных формул.
8.Записать предложения в виде соотношений формул логики предикатов. Методом резолюций выяснить будет ли заключение логическим следствием из посылок. Продемонстрировать результат с помощью диаграмм Эйлера-Венна.
9.Построить нормальный алгоритм для преобразования слова Р в слово
Q, при условии что в каждой подстановке Рi→(•)Qi алгоритма число букв удовлетворяет неравенству: Рi ≤ n, Qi ≤ n, где n=2+[N](mod
3), здесь N - ваш номер в списке группы, а [N](mod 3) означает число N по модулю три.
10.Построить машину Тьюринга для преобразования слова Р в слово Q. 11.Построить машину Тьюринга, которая будет считать записанные подряд (без пропусков) единицы (их число не превосходит n) и запишет их число в системе счисления с основанием n +1, здесь n=3+[N](mod 13) и N =(ваш номер в списке группы)+(номер вашей
группы).
12.Доказать, что приведенная функция является примитивно рекурсивной.
13.Доказать методами исчисления высказываний, что данная формула является теоремой исчисления высказываний.
240
14.Выяснить, равносильны ли приведенные формулы в трёхзначной логике Лукасевича. Желательно сделать это с помощью разработанной вами программы на любом известном вам алгоритмическом языке.
15.Пусть нечеткие множества А*, В* и С* определены на универсальном множестве U={x: 0 ≤ x ≤ 10} функциями принадлежности:
|
|
1 |
|
1 1 / 2 |
|
1 |
2 |
||
µА*( х) = |
|
|
, µВ*( х) = |
|
|
, µС*( х) = |
|
|
, |
1 |
+nх |
|
|
||||||
|
|
1 +nх |
|
1 +nх |
|
||||
здесь n=1+[N](mod 25) и N =(ваш номер в списке группы)+(номер вашей группы). Построить (в аналитическом виде и графическом) функции принадлежности для нечетких подмножеств, указанных для вашего варианта.
Вариант 1
1.А достаточно для В, а В необходимо для С или А, но А не эквивалентно
С.
2.A&C A&D& C A& C D&B& D B&A& C&D B B B&B&A& B.
3.A&C A&В& C.
4.А (В С), В С A╞ (A С) B.
5.Все А суть не В, а некоторые В суть С, кроме того, существуют А, такие что С.
6.x yP(x,y) xP(x,x).
7.А= x yP(x,y) xP(x,x), В= x yP(x,y) y xP(y,x).
8.Ни одно С не есть D. Все А суть D. Все В суть С. Следовательно, все В
|
не есть А. |
|
|
|
|
9. |
P=aabcc, Q=aabccdabcdd. |
10. P=aabc, Q=aabccdab. |
|||
11. |
Смотри условия задачи. |
12. |
х−1, |
если |
х >0 |
δ(х)= |
если |
х =0. |
|||
|
|
|
0, |
||
13. |
( В А) (А В). |
14. |
((Nx) (Ny))&z, (y x)&z. |
||
15.A*∩B*, A* C*, А* ∩(B* C*).
Вариант 2
1.А необходимо для В, а В достаточно для С и А, но А не эквивалентно С или В.
2.A& (C D)&( А В C D)&( А C D С& B) B&A& B.
3.A C A&В& C.
4.P Q R, P Q S, P,Q╞ S.
5.Некоторые В суть не А, но ни одно В не есть С, тогда некоторые не А суть не С.
6.xP(x,а) y xP(x,у).
7.А= х yP(x,y) xP(x,x), В= x y zP(x,y,z) y zQ(y,z).
8.Все С не есть D. Все А суть не D. Все В суть С. Следовательно, все В
|
есть А. |
|
9. |
P=bbcab, Q=bbcabccdabcdd. |
10. P=abab, Q=abababcdab. |
|
|
241 |
|
|
11. |
Смотри условия задачи. |
12. x-y= х− у, |
если |
х ≥ у |
|
|
0, |
если |
х < y. |
13. |
(А В) ( В А). |
14. (N((Nx)&y))&z, (y x)&z. |
||
15.A* B*, A*∩C*, А* (B*∩ C*).
Вариант 3
1.А когда В или С, а В необходимо для А или С, но из С следует А и В.
2.(A C)&(D ( A& C)) ( D& A) (A C)&( C D) B&A& A.
3.А (В С).
4.P Q, P Q, P Q╞ P&Q.
5.Все А суть не В, а некоторые С суть В или некоторые С суть не А и В.
6.x yP(x,y) xP(x,x).
7.А= y xP(x,y) xP(а,x), В= x yP(x,y) z y xQ(y,x,z).
8.Некоторые С не есть D. Все А суть не D. Все В суть С. Следовательно,
|
все В суть А. |
|
|
|
9. |
P=ссaab, Q=ссaabccabcdd. |
10. P=сabc, Q=сabccdab. |
||
11. |
Смотри условия задачи. |
12. х-у = х− у, |
если |
х ≥ у |
|
|
у- х, |
если |
х < y. |
13. |
А ( В (А В)). |
14. ((Nx) (Ny))&z, (N(y&x))&z. |
||
15.А* ∩B*, A* C*, А*∩(B* C*).
Вариант 4
1.Если А то В, а В достаточно для С или А, но А не эквивалентно не С.
2.(A C)&( A&D B&D A& D B& D)&(A C) B&A& B.
3.(A≡C) A&В& C.
4.P Q R, P R, Q R ╞ R.
5.Ни одно С не есть D, но все А суть D, а все В суть С или А.
6.( xP(x)) xQ(x)≡x(P(x) Q(x)).
7.А= x yP(x,f(x,y)) xP(x,x), В= x yQ(x,a,y) y xP(y,x).
8.Все А суть не В, а некоторые В суть С, следовательно, не существует А, таких что В или С.
9. |
P=ddaab, Q=ddaabbbabcdd. |
10. P=ddccc, Q=ddcccbccab. |
||
11. |
Смотри условия задачи. |
12. sg*(х)= 1, |
если |
х =0 |
|
|
0, |
если |
х ≠0. |
13. |
(А В) (( A B) В). |
14. ((Nx)≡(Ny))&z, ((Ny) (Nx))&z. |
||
15.A*∩C*, B* C*, А* (B*∩C*).
Вариант 5
1.А тогда, когда В, а В только тогда когда С или А, но А не достаточно для С.
2.(A D)&(B& C B&D C&B B&D)&( D A) B&A& B.
3.A&C (A В)& C.
242
4.P Q, R Q, R S, R P, S Q╞ R&Q.
5.Все D суть В, ни одно А не есть не С, также ни одно В не есть С.
6.( xP(x)) xQ(x)≡x y(P(x) Q(y)).
7.А= x yP(x,y) xQ(a,f(x,y)), В= x yP(x,y) y xP(y,x).
8.Некоторые С не есть D. Все А суть D. Все В суть не С. Следовательно, все В есть А.
9. |
P=ccdda, Q=ccdddacdabcdd. |
10. P=acacb, Q=acacbccdab. |
11. |
Смотри условия задачи. |
12. x! |
13. |
A (А В). |
14. (Nx) ((Ny)&z), x ((Ny)&z). |
15.C*∩ А* , A* C*, A*∩(B* C*).
Вариант 6
1.А при условии, что для В, а В влечёт С и А, но А не эквивалентно С.
2.( A B C D)&( A C D C&B)&A& ( C D) B&C& B.
3.A C A&В& C.
4.P, Q P, R P Q╞ R&P.
5.Не все А суть не В, а некоторые В суть С, кроме того, не существует А, таких что В.
6.( xP(x))& xQ(x)≡x(P(x)&Q(x)).
7.А= x yQ(a,x,y) xP(x,x), В= y xP(x,f(y)) y xP(y,x).
8.Ни одно С не есть D. Все А суть не D. Некоторые В суть не С.
|
Следовательно, все В суть А. |
|
9. |
P=abca, Q=abcacdaaad. |
10. P=abc, Q=abccbaa. |
11. |
Смотри условия задачи. |
12. min(x,y). |
13. |
( А А) (А А). |
14. ((Nx)≡y)&z, (х у)&(у (Nx))&z. |
15.A*∩В* , A* C*, A*∩(B* C*).
Вариант 7
1.А необходимо для В, а В когда С и А, но А не эквивалентно С и В.
2.(A&C D)&( А C) D&А ( A C)&(C D) B& A& B.
3.A C A&В C.
4.P Q R, P Q S, P,Q╞ S.
5.Некоторые В суть не А и ни одно В не есть С, но некоторые А суть С.
6.( xP(x))& xQ(x)≡ x y(P(x)&Q(y)).
7.А= х yQ(a,b,x,y) xP(x,x), В= x y zR(x,y,z) y zP(y,z).
8.Все не В суть А. Ни одно А не суть D. Все В суть С. Следовательно, все D суть С.
9. |
P=badb, Q=badbdabcdd. |
10. P=abab, Q=abababd. |
11. |
Смотри условия задачи. |
12. min(x1,x2,…xn). |
13. |
(А A) ( A А). |
14. N((Nx) y)&z, (N(x y))&z. |
15.С* B*, A*∩C*, A* (B*∩C*).
Вариант 8
1.А когда В и С, а В при условии, что С, но из С не следует А и В.
243
2.A& C (( A D)&(B D)& A& D&(B D))A&C C& C&D.
3.А В&С.
4.P Q R, P R, P, Q, R S, R T╞ S& T.
5.Все А суть не В, а некоторые С суть В, но некоторые С суть А или не В.
6.x yP(x,y) xP(x,x).
7.А= y xP(x,y) xP(а,x), В= x yP(x,y) z y xQ(y,x,z).
8.Все D суть Е. Все С суть А. Ни одно В не есть не D. Все Е суть не А. Следовательно, некоторые А суть D.
9. |
P=dссaa, Q=dссaabccabcdd. |
10. P=ddbc, Q=ddbсccdab. |
11. |
Смотри условия задачи. |
12. max(x,y). |
13. |
А ( А (А А)). |
14. ((Nx) & (Ny)) z, N(y&x) z. |
15.А* B*, A*∩C*, А*∩(B* C*).
Вариант 9
1.А необходимо для В, а В достаточно для С или А, но А не эквивалентно
С.
2.A&B& C&D A (C&D) ( A& C&& D&(C B) A&B&A
3.(A≡C) A≡В.
4.A B, C D, A C, A D, C B ╞ (A B) A&B.
5.Все С суть D, а все А суть не D, но некоторые В суть С.
6.x(P(x) Q(x)) (( x(P(x))& xQ(x)).
7.А= xP(x,x) x yP(x,f(x,y)), В= x yQ(x,a,y) y xP(y,x).
8.Все А суть В, а некоторые В суть С, следовательно, существует А,
|
такое что В и С. |
|
9. |
P=dadab, Q=dadabbabcdd. |
10. P=dadc, Q=dadccbccab. |
11. |
Смотри условия задачи. |
12. max(x1,x2,…xn). |
13. |
(А А) (( A А) А). |
14. (Nx≡Ny) z, ((Ny) (Nx)) z. |
15.A*∩C*, А* C*, А* (B*∩C*).
Вариант 10
1.А необходимо для В, а В только тогда когда С или А, но А не достаточно для С.
2.A&D (B C)&(B D)&(C B)&( B D) D&A B&A& A.
3.A C (A В)&C.
4.A B, A В, B (C D), A D╞ (A&C).
5.Все D суть не В, но ни одно А не есть С, а некоторые В не есть С.
6.( xP(x)) xQ(x)≡x y(P(x) Q(y)).
7.А= x yP(x,y) xQ(a,f(x,y)), В= x yP(x,y) y xP(y,x).
8.Некоторые С суть D. Все А суть D. Все В суть не С. Следовательно, все В есть А.
9. |
P=ccaad, Q=ccaaddacdcdd. |
10. P=cacab, Q=cacabcdc. |
11. |
Смотри условия задачи. |
12. rm(x,у)=остатку от деления у на х. |
13. |
(A А) А. |
14. (Nx) ((Ny)&z), x ((Ny)&z). |
244
15.C* А* , A* C*, A* (B*∩ C*).
Вариант 11
1.А необходимо для В, а В достаточно для С или А, но А не эквивалентно
С.
2.B&D (C A)&( A B)&(A C)&(A B) B& D B&A& B.
3.A&C ((A В) C).
4.B C, A≡B, C≡D╞ (C B) (D A).
5.Если все А суть В, а некоторые В суть С, тогда существуют А, такие что С.
6.P(x) yP(y).
7.А= x yQ(x,a,y) xP(x,f(x)), В= x yP(x,y) y xQ(a,y,x).
8.Ни одно С не есть D. Все А суть D. Все В суть С. Следовательно, все В не есть А.
9. |
P=aabcc, Q=aabccdabcdd. |
10. P=aabc, Q=aabccdab. |
11. |
Смотри условия задачи. |
12. qt(х,y)=частному от деления у на х. |
13. |
( А А) (А А). |
14. (Nx Ny) z, (y x) z. |
15.A*∩ C*, A* B*, C*∩(B* А* ).
Вариант 12
1.А необходимо для В, а В достаточно для С и А, но А не эквивалентно С или В.
2.(A (C B&C))& (C&D)&C& D&(C С& D D) B&A& A.
3.A C A&В& C.
4.P Q R, P, Q, R S╞ S.
5.Если некоторые В суть не А, но ни одно В не есть С, то некоторые А суть не С.
6.xP(x) xP(x).
7.А= х yP(x,y) xQ(a,x,x), В= x y zS(x,f(y),z) y zQ(y,z).
8.Все С не есть D. Все А суть не D. Все В суть С. Следовательно, все В есть А.
9. |
P=bcab, Q=bcabccdabcda. |
10. P=aba, Q=ababcdab. |
||
11. |
Смотри условия задачи. |
12. x+y×z. |
||
13. |
(А A) ( A А). |
14. N((Nx) y)&z, N((y x) z). |
||
15 |
A* B*, |
|
* ∩C*, A* (B*∩ C*). |
|
А |
|
|||
Вариант 13
1.А достаточно для В или С, а В необходимо для А и С, но из С следует А либо В.
2.B D&(C& A A& B A&C A& B)&(B D) A&A& B.
3.А≡ (В≡С).
4.P Q, P R, Q╞ R.
5.Если все А суть В, а некоторые С суть В, то некоторые С суть не А.
245
6.x y(P(x)≡ P(у)).
7.А= z y xQ(x,y,z) xP(а,x), В= x yP(x,y) z y xQ(y,f(a,x),z).
8.Некоторые С не есть D. Все А суть не D. Все В суть С. Следовательно, все В суть А.
9. |
P=dсaab, Q=dсaabccabcdd. |
10. P=dabc, Q=dabccdab. |
11. |
Смотри условия задачи. |
12. x×(y+z). |
13. |
А ( A (А A)). |
14. ((Nx) (Ny)) z, N(y&x) z. |
15.А* ∩В* , A* C*, А* B* C*.
Вариант 14
1.Если А то В либо С, а В достаточно для С, но А не эквивалентно С.
2.(C D) A&C&(B C) C D C&( C D)&D D&A& D.
3.(A≡C) (A В).
4.P Q R, P R, Q R ╞ R.
5.Когда ни одно С не есть D, а все А суть D, то все В суть С.
6.x(P(x) Q(x)) (( xP(x))& xQ(x)).
7.А= x yQ(x,f(x,y,a)) xP(x,x), В= x yQ(x,a,y) y xP(y,x).
8.Все А суть не В. Некоторые В суть С. Следовательно, не существует А, таких что В или С.
9. |
P=dсdaa, Q=dсdaabссabcd. |
10. P=dсdcа, Q=dсdcаcbаca. |
11. |
Смотри условия задачи. |
12. (х+y)z. |
13. |
(А A) (( A A) A). |
14. (Nx Ny) z, (y x) z. |
15.А* ∩C*, B* C*, А* ∩ B*∩C*.
Вариант 15
1.А только тогда, когда В, а В необходимо для С или А, но А не достаточно для С.
2.A&B&C A&B& A&C (A B)&(C D)&(A B) D&B C&A& C.
3.(A≡C) (A В).
4.A (C B), D A, C╞ D B.
5.Когда все D суть В, а некоторые А есть С или не В, то ни одно В не есть
С.
6.( xP(x)) xQ(x)≡x y(P(x) Q(y)).
7.А= y xQ(a,f(x,y)) x yP(x,y), В= x yP(x,а(y)) y xP(y,x).
8.Некоторые С не есть D. Все А суть D. Все В суть не С. Следовательно,
|
все В суть А. |
|
|
9. |
P=ccda, Q=ccdacdaаcdd. |
10. P=acсb, Q=acсbccаab. |
|
11. |
Смотри условия задачи. |
12. |
(x+у)! |
13. |
( A А) ( А А). |
14. |
(Nx) ((Ny) z), x ((Ny) z). |
15.C*∩ А* , A* В* , A*∩(B* C*).
Вариант 16
1.А достаточно для В, а В влечёт С либо А, но А не эквивалентно С.
|
247 |
13. А A (А А)). |
14.((Nx)&(Ny)) (Nz), N(y x) (Nz). |
15.А* В* , A*∩C*, А*∩B*∩ C*.
Вариант 19
1.А эквивалентно не В, а В необходимо для С или А, но из А не следует С
иВ.
2.(C&D) A& C& D (C B)&A A&B&A A&B& C&D A.
3.(A≡C) A В.
4.A (B C), A B, B A, B D ╞ C D.
5.Если некоторые А суть В, но все В суть С, то существует А, такое что В
иС.
6.( xP(x) хQ(x))≡ х у(P(x) Q(у)).
7.А= x yQ(x,a,y) x yP(x,f(x,y)), В= xP(x,x) y xP(y,x).
8.Не все С суть D. Все А суть D. Все В суть не С. Следовательно,
|
некоторые В есть А. |
|
9. |
P=ddab, Q=ddabbabcdd. |
10. P=ddc, Q=ddccbccab. |
11. |
Смотри условия задачи. |
12. x×y+x×z. |
13. |
(А А) ((A А) B). |
14. (Nx) (y z), (z (y (Nx)). |
15.A*∩C*, А* C*, А* В* C*).
Вариант 20
1.А только тогда, когда В, а В достаточно для С или А, но А не эквивалентно С.
2.(B C)&(B D)&(C B)&( B D) D&A B&A& A A&D.
3.A C (A В).
4.A B, A В, B (C D), A D╞ (A&C).
5.Когда не все D суть В, а ни одно А не есть С, тогда некоторые В не есть
С.
6.( xP(x) xQ(x))≡x y(P(x) Q(y)).
7.А= xQ(a,f(x,y)) x yP(x,y), В= x yP(x,y) y xP(y,x).
8.Все С суть D. Некоторые А суть D. Все не В суть С. Следовательно, все
|
В есть А. |
|
9. |
P=ccad, Q=ccaadсacdabcdd. |
10. P=cab, Q=cabccdcс. |
11. |
Смотри условия задачи. |
12. max(x1,x2,x3). |
13. |
(A А) (А А). |
14. (Nx) (y&z), x (y&z). |
15.C* А* , А* ∩В*, A*∩B*∩ C*.
Вариант 21
1.Как А так и В, а В необходимо для С или А, но А не эквивалентно С.
2.(A B A& B)&(B C B&D)& (A D)&B& A B&A& B.
3.A&C A&В C.
4.А (В С), D E A, C F╞ B (F D).
248
5.Если все А суть не В, а некоторые В суть С, то существуют не А, такие что С.
6.x(P(x)& y(P(y) Q(x,y))).
7.А= xP(x,a) y xP(y,x), В= x yP(f(x,y),y) y xP(y,x).
8.Ни одно С не есть D. Все А суть D. Некоторые В суть С.
|
Следовательно, все В не есть А. |
|
9. |
P=aabbc, Q=aabbccdabcdd. |
10. P=aabd, Q=aabdcdab. |
11. |
Смотри условия задачи. |
12. (x+y)×z. |
13. |
(A (A A)) ( (А A) A). |
14. ((Nx) y)&z, ((Ny) x)&z. |
15.A*∩B*, A* C*, А* ∩(B* C*).
Вариант 22
1.А необходимо для В, а В достаточно для С и А, но А не эквивалентно С либо В.
2.( А C D С& B)& A& (C D)&( А В C D) B&A& B.
3.A C В C.
4.(A B) (C D), (D E) F╞ A F.
5.Когда некоторые В суть не А, а ни одно В не есть С, тогда некоторые не А суть С.
6.х у(P(x) Q(x,у)).
7.А= х yR(a,f(x,b),y) xP(x,x), В= x yQ(x,y) y xP(y,x).
8.Все С есть не D. Все А суть D. Все В суть С. Следовательно, некоторые В есть не А.
9. |
P=bca, Q=bcacdaсcdd. |
10. P=abс, Q=abсbcсab. |
11. |
Смотри условия задачи. |
12. (x+y)+z. |
13. |
(А A) ( (A A) B). |
14. N((Nx) y) z, (y (Nx)) z. |
15.A* C*, А* ∩B*, А* (B*∩ C*).
Вариант 23
1.А когда В либо С, а В необходимо для А и С, но из С не следует А.
2.(A C)&(D ( A& C)) ( D& A) (A C)&( C D) B&A& A.
3.А (В≡С).
4.A, B C, D C, B (A D)╞ C.
5.Если все А суть не В. Некоторые С суть В, тогда некоторые С суть А.
6.x yP(x,y) y xP(x,у).
7.А= y xR(x,b,y) xP(а,x), В= z y xQ(y,x,z) x yP(x,y).
8.Некоторые С есть D. Все А суть не D. Все В суть С. Следовательно, все
|
В суть А. |
|
||||
9. |
P=aab, Q=aabccabcdd. |
10. P=abc, Q=abccdab. |
||||
11. |
Смотри условия задачи. |
12. x×(y+z). |
||||
13. |
(А (A B)) ( (A В) А). |
14. ((Nx) (Ny)) z, N(y&x) z. |
||||
15. |
|
|
* ∩B*, |
|
* C*, А*∩(B* C*). |
|
|
А |
А |
|
|||
249
Вариант 24
1.Если А то В либо С, а В достаточно для С, но А не эквивалентно С.
2.( A& D B& D)&(A C) B&A& B (A C)&( A&D B&D).
3.(A≡C) A&В&C.
4.A B, A C, B D, D C ╞ A&C.
5.Когда все А суть В, а некоторые В суть не С, тогда не существует А, таких что В или С.
6.x yP(x,y)) y xP(x,y).
7.А= x yP(x,f(x,y)) xP(a,x), В= x yQ(f(x,a),y) y xP(y,x).
8.Ни одно С не есть D. Все А суть D. Все В суть С. Следовательно, некоторые В есть А.
9. |
P=ddab, Q=ddabbbacdd. |
10. P=ddc, Q=ddcbccab. |
11. |
Смотри условия задачи. |
12. х×(у+2). |
13. |
А ( (A A) (A (A A)). |
14.(Nx)≡((Ny)&z), (Ny) ((Nx)&z). |
15.A*∩C*, B* C*, А* B* C*).
Вариант 25
1.А только тогда, когда В, а В когда С или А, но А не достаточно для С.
2.(A D)&(B& C B& D C&B B& D)&(D A) B&A& B.
3.A C (A В)& C.
4.С (B A), B D, C╞ A D C.
5.Если некоторые D суть В, а ни одно А не есть не С, то все А суть D.
6.x y(P(x)&P(y)&Q(x,y)).
7.А= x yP(x,b) xQ(a,f(x,y)), В= x yP(x,y) y xR(f(x,a),y,x).
8.Некоторые С суть D. Все А суть D. Все В суть не С. Следовательно, все
|
В есть А. |
|
9. |
P=cda, Q=cdacdabcdd. |
10. P=accb, Q=accbccdab. |
11. |
Смотри условия задачи. |
12. x! |
13. |
A (А А). |
14. (Nx) (y&z), x (y&z). |
15.C*∩ А* , A* C* В*, A*∩(B* C*).