| МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ
УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Контрольная работа №2
По дисциплине «Математическая логика и теория алгоритмов»
Вариант 1
2003г
Южно-Сахалинск.
1) Записать составные высказывания в виде формул
. употребляя высказывательные переменные для обозначения простых высказываний: «Для того, чтобы x
было нечётным, достаточно, чтобы х
было простым»;
Решение: Обозначим А = «х - не чётное число»
В = «х - простое число»
А
Þ
В (импликация «для А достаточно В»).
2) При каких значениях переменных x
, y
, z
формула
ложна?
Решение: Составим таблицу истинности:
| x
|
y
|
z
|
Øx
|
Øy
|
ydz
|
x É(ydx)
|
Øy ÉØx
|
(xÉ(ydz)) É(Øy ÉØx)
|
(xÉ(ydz)) É(Øy ÉØx) ÉØy
|
| 0
|
0
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
| 0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
| 0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
| 0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
| 1
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
| 1
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
| 1
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
0
|
| 1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
Т.о. данная формула ложна при: 1)
х = 0; y = 1; z = 0; 2)
x = 0; y = 1; z = 1;
3)
x = 1; y = 1; z = 1;. где 1 - «истина», 0 - «ложь».
3) Является ли тавтологией формула
?
Решение: Тавтологий является формула, которая истинна независима от значений входящих в нее переменных. Составим таблицу истинности -
| p
|
|
r
|
t
|
Øq
|
Ør
|
Øt
|
pÉq
|
ØrÉØq
|
tÉØr
|
(pÉq)&(ØrÉØq)&(tÉØr)
|
pÉØt
|
((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt)
|
| 0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
| 0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
| 0
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
| 0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
| 0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
| 0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
| 0
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
1
|
| 0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
| 1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
| 1
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
| 1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
| 1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
0
|
0
|
1
|
| 1
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
| 1
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
| 1
|
1
|
1 1
|
0 1
|
0 0
|
0 0
|
1 0
|
1 1
|
1 1
|
1 1
|
1 1
|
1 0
|
1 0
|
| 1
|
1
|
|
|
|
|
|
|
|
|
|
|
|
Т.о. данная формула не является тавтологией.
4) Доказать выполнимость формулы. Ø(p
ÉØp
)
Решение: Составим таблицу истинности:
| p
|
Øp
|
p
ÉØp
|
Ø(p
ÉØp
)
|
| 1
|
0
|
0
|
1
|
| 0
|
1
|
1
|
0
|
Формула выполняется, если на некотором наборе распределения истинностных значений переменных она принимает истинное значение.
т.е. формула истинна при истинном значении p
и ложна при ложном значении p
, следовательно она выполнима.
5)Пусть даны предикаты на множестве натуральных чисел D
(x
,y
) º “y
делится на x
”; E
(x
) º “x
- чётное число”. Переведите на обычный язык формулу. $x(E(x)ÚD(6,x)). Решение: «некоторые числа являются чётными или делятся на 6).
6) Пусть даны предикаты на множестве натуральных чисел D
(x
, y
) º “y
делится на x
”; G(x, y, z) º “z - наибольший общий делитель x
и y
”. Запишите утверждение на языке логики предикатов: «если x
делится на y
и y
делится на z
, то x
делится на z
».
Решение: "x
"y
"z
((D
(y
, x
)&
D
(z
, y
))ÞD
(z
, x
))
7) Пользуясь знаками арифметических операций (+, ´) и отношений (Ð, =) запишите на языке логики предикатов следующее высказывание о действительных числах: «система уравнений
не имеет решения»
Решение:
- ложно.
|