Задачи к экзамену по математической логике и теории алгоритмов. Задачи к экзамену по дисциплине Математическая логика и теория алгоритмов

• Название: Задачи к экзамену по дисциплине Математическая логика и теория алгоритмов
• Дата: 16.06.2021
• Размер: 408.88 Kb.
• Имя файла: Задачи к экзамену по математической логике и теории алгоритмов.pdf
• Тип: Документы; #217956

1
Задачи к экзамену
по дисциплине «Математическая логика и теория алгоритмов»
1. Составив таблицу истинности, проверьте, является ли следующая формула тавтологией:






P
Q
P
Q
P




2. Докажите, что: если

G
F

,

H
G

, то

H
F

3. Пользуясь определением понятия логического следования, выясните, справедливо ли следующее логическое следование:
Q
Q
P
Q
P



,
4. Применяя равносильные преобразования, приведите формулу к возможно более простой формуле:




Q
R
Q
P



5. Найти CКНФ и СДНФ булевой функции, результат проверить таблицей истинности
)
(
)
(
y
z
y
x



6. Минимизировать булеву функцию алгебраическими преобразованиями:


c
b
d
a
d
c
a
f



7. Минимизировать булеву функцию методом Квайна Мак-
Класки:


1101
,
1011
,
0111
,
0101
,
0100
,
0010

f
8. Минимизировать булеву функцию методом карт Карно:






b
d
ab
ce
d
f





9. Минимизировать булеву функцию и построить её РКС:
)
(
)
(
t
y
x
z
y
x



10. Представить булеву функцию в виде многочлена Жегалкина
1) с помощью СДНФ;
2) методом неопределённых коэффициентов;
3) методом треугольника Паскаля;
4) с помощью непосредственных преобразований:




3 1
2 1
x
x
x
x
f




11. Выясните, является ли булева функция линейной:

 

z
y
x
z
xy
f





12. Отыскав для булевой функции представляющий её многочлен
Жегалкина, установите, является ли функция тождественно равной 1 или тождественно равной 0:


x
y
x
y
x
f




13.
Определить принадлежность функции к классу
S
(самодвойственных функций):




z
x
y
x
z
y
x
f




)
,
,
(

2 14. Определить принадлежность функции к классу M (монотонных функций):



y
x
y
x
y
x
f



)
,
(
15. Определить принадлежность функции к классу L (линейных функций):



y
x
y
x
y
x
f



)
,
(
16. Проверить на полноту систему булевых функций:




xy
y
x
x





,
1 17.
Изобразите на координатной плоскости множества истинности следующих двухместных предикатов, заданных на множестве действительных чисел R:
y
x


2 2
18. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого:
x
y

,
0 2
2


y
x
19.
Привести формулу


))
,
(
)
,
(
(
)
(
3 2
3 3
1 2
3 1
1 2
1
x
x
P
x
x
P
x
x
P
x
x
F






к предваренной нормальной форме и сколемовской стандартной форме.
20. Составьте отрицание к фразе: в каждой группе есть студент, который каждый день опаздывает на занятия.
21. Применима ли машина Тьюринга с внешним алфавитом А =
{0,1}, алфавитом внутренних состояний Q = {
2 1
,
0
, q
q
q
} и следующей функциональной схемой:







1 1
;
1 1
;
1 0
;
0 0
2 2
1 1
0 2
2 1
q
q
q
q
q
q
q
q

к слову 0011000011110000?
22. Пусть A = {a, b, c}. Слово Р содержит не менее трех символов.
Удалить из слова Р третий символ. Описать системой команд, функциональной таблицей и диаграммой переходов работу машины Тьюринга, реализующую данный алгоритм. Начальная и конечная конфигурации стандартны.
23. Реализовать нормальный алгоритм Маркова, выполняющий замену в слове

в алфавите
}
,
,
{
c
d
a
A

каждого символа
a
на символ
c