Контрольная работа по математической логике. 16 задач.

16 задач по матлогике. ...

1) Максимально упростить выражение, воспользовавшись законами логики Буля. С помощью таблиц истинности сравните упрощенное выражение с исходным.
2) Четыре друга – Антонов (А), Вехов (В), Сомов (С), Деев (Д) решили провести каникулы в четырех разных городах – Москве, Одессе, Киеве и Ташкенте. Определите, в какой город должен поехать каждый из них, если имеются следующие ограничения:
 Если А не едет в Москву то С не едет в Одессу
 Если В не едет ни в Москву ни в Ташкент, то А едет в Москву
 Если С не едет в Ташкент, то В едет в Киев
 Если Д не едет в Москву, то В не едет в Москву
 Если Д не едет в Одессу, то В не едет в Москву
3) Доказать при помощи метода резолюций, что формула G является логическим следствием формул F1…Fn
4) Изобразить на диаграмме Эйлера – Венна область истинности для следующего предиката
5) Построить машину Тьюринга:
Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток. Каретка слева.
И другие

1) Максимально упростить выражение, воспользовавшись законами логики Буля. С помощью таблиц истинности сравните упрощенное выражение с исходным.
2) Четыре друга – Антонов (А), Вехов (В), Сомов (С), Деев (Д) решили провести каникулы в четырех разных городах – Москве, Одессе, Киеве и Ташкенте. Определите, в какой город должен поехать каждый из них, если имеются следующие ограничения:
 Если А не едет в Москву то С не едет в Одессу
 Если В не едет ни в Москву ни в Ташкент, то А едет в Москву
 Если С не едет в Ташкент, то В едет в Киев
 Если Д не едет в Москву, то В не едет в Москву
 Если Д не едет в Одессу, то В не едет в Москву
3) Доказать при помощи метода резолюций, что формула G является логическим следствием формул F1…Fn
4) Изобразить на диаграмме Эйлера – Венна область истинности дл я следующего предиката
5) Построить машину Тьюринга:
Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток. Каретка слева.
И другие

К&ПВ
В
Следствие:
КП
3) Проверим, следует ли заключение из конъюнкции посылок.
(К&ПВ)&(В)=(КПВ)&В=КП
Вывод: рассуждение правильное.
Задача 4.
Запишите с использованием 4–6 различных букв, логические формулы, отвечающие тексту или контексты вашей легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное, другое ложное.
Если усложнить схему устройства, то возрастёт его производительность, а если использовать новую элементную базу, то увеличится период эксплуатации. Устройства начнут хорошо раскупать только при одновременном росте его производительности и периода эксплуатации. Но устройства не пользуются спросом.
Решение:
1)Введем обозначения:
У – усложнение схемы устройства;
П – производительность;
Н – новая элементная база;
Э – периодэксплуатации;
С – спрос;
2)Посылки:
;
;
.
3)Следствие:
.
4)Произведем преобразования:
;
;
;
.
5)Отрицание следствия:
.
6)Необходимо доказать что множество формул
F1&F2&F3&F4&F5, где
F1=;
F2=;
F3=;
F4=
F5= противоречиво.
Докажем, что &&&()&() является противоречием методом резолюций.
&&&()&()
рез (1,5) =
рез (,2) =
рез (,3) =
рез (,4) =  (false)
Отсюда следует, что является логическим следствием из формул F1…F5
7)Сформируем ложное следствие, из которого будет следовать, что производилось усложнение схемы устройства без использования новой элементной базы:
Добавим его отрицание к имеющимся посылкам.
Докажем, что &&&()&() является противоречием методом резолюций.
&&&()&()
рез (2,5) =
рез (,3) =
рез (,4) =
рез (,1) =
Отсюда следует, что не является логическим следствием из формул F1…F5
Задача 4.
Доказать при помощи метода резолюций, что формула G является логическим следствием формул F1…Fn

Решение:
1)Произведем преобразования:
Отрицание следствия:
2)Необходимо доказать что множество формул
F1&F2&F3&F4&F5, где
F1=
F2=
F3=
F4=
F5= противоречиво.
Докажем, что ()&()&()&()&() является противоречием методом резолюций.
()&()&()&()&()
рез (1,5) =
рез (,2) =
рез (,3) =
рез (,4) =  (false)
Отсюда следует, что G является логическим следствием из формул F1…F5.
Задача 5.
Найти отрицание формулы:
.
Решение:
1) Опустим отрицание на формулу:
Ответ:
Задача 6.
На множестве М={1,2,3…,20} заданы предикаты:
A(x):”Число X не делится на 5”
B(x):”Число X делится на 2”
C(x):”Число X-простое”
D(x):”Число X делится на 3”
Найти множество истинности предиката:
Решение:
1)Множество истинности A(x) = {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19}
2)Множество истинности В(x) = {2,4,6,8,10,12,14,16,18,20}
3)Множество истинности С(x) = {1,2,3,5,7,11,13,17,19}
4)Множество истинности D(x) = {3,6,9,12,15,18}
5)Множество истинности =
{1,2,3,4,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Ответ: {1,2,3,4,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}.
Задача 7.
Изобразить на диаграмме Эйлера – Венна область истинности для следующего предиката: .
Решение:
1) Произведем преобразования:
Диаграмма Эйлера-Венна:

Задача 8.
какие из формул являются рбщезначемыми.докажите

Решение:
Задача 9.
Привести к предваренной нормальной форме:
Решение:
Ответ:
Задача 10.
Привести к скулемовской нормальной форме:
Решение:
Ответ:
Задача 11.
Будут ли равносильны следующие формулы:
и
Решение:
1) Упростим первую формулу:
=
2) Упростим вторую формулу:
=
Ответ: формулы равносильны.
Задача 12.
Определить унифицируемы ли следующие множества атомарных формул. Если унифицируемо, найти НОУ.
Решение :
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
Ответ: следовательно множество унифицируемо. НОУ для это
Задача 13.
Используя метод резолюций в логике предикатов, докажите логичность следующего рассуждения:
Каждый из первокурсников знаком с кем – либо из спортсменов. Некоторые из первокурсников не знакомы ни с одним любителем подледного лова. Следовательно, ни один спортсмен не является любителем подледного лова.
Решение:
1) Выделим предикаты:
P(x): «x-первокурсник»
S(x): «x-спортсмен»
L(x): «x-любитель подледного лова»
Z(x,y): «x знает у»
2) Выделим формулы предикатов:
3) Отрицание заключения:
4) Опустим знак квантора предполагая, что доказательство будет проведено для некоторого фиксированного x, но так как x любое, оно будет справедливо для всех случаев.
5) Произведем преобразования:
6) Выделим дизъюнкты:
7) Для доказательства возьмем отрицание следствия, добавим его к посылкам и докажем противоречие:
рез(5,3)=
рез(,1)=
рез(,4)=
рез(,2)= (false)
Вывод: таким образом логическое рассуждение является правильным.
Задача 14.
Построить машину Поста:
На ленте машины Поста расположен массив из N меток. Составить программу действуя по которой машина выяснит, делится ли число на 3.Если да то, после массива через одну пустую секцию поставить метку V.
Решение:
v
v
v
v
v
v
v
v
v

1 2
1 нет
2
3 да
3 4
5 нет
4
6 да
5 Stop 5
6 7
5 нет
7
8 да
8 9
10 нет
9
3 да
10 11

11 М 12
12 5
Задача15.
Построить машину Тьюринга:
На информационной ленте машины Тьюринга в трех секциях в произвольном порядке записаны три цифры: 1, 2, 3. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.
Решение:
Внешний алфавит включает
Задание 16
Построить машину Тьюринга:
Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток. Каретка слева.
Решение:
A={a0, v ,0,1,2,3,4,5,6,7,8,9};
Q={q0,q1,q2,q3,q4}
 
а0
v
1
2
3
4
5
6
7
8
9
q1
a0 п q1
1 п q2
 
 
 
 
 
 
 
 
 
 
q2
a0 л q3