Задания

Задание 1. Даны высказывания A и B. Выясните, являются истинными или ложными высказывания а) ; б) ; в) A→B.

A = «Волга впадает в Каспийское море», B = «Все граждане США – индейцы». A = «БелАЗ-540 – легковая машина», B = «Солнце вращается вокруг Земли». A = «Реактивный самолет движется быстрее, чем воздушный шар», B = «Камчатка расположена восточнее Таймыра». A = «Дважды два – пять», B = «Столица России – Москва». A = «Пушкин учился в Лицее», B = «У Тараса Бульбы было двое сыновей». A = «Джон фон Нейман придумал архитектуру ЭВМ», B = «Первые компьютеры были переносными». A = «Наполеон Бонапарт был королем Англии», B = «Солнце восходит на западе». A = «Вода кипит при атмосферном давлении и нулевой температуре», B = «22 сентября – день осеннего равноденствия». A = «Монета не всегда падает орлом вверх», B = «Скрипка – самый большой струнный музыкальный инструмент». A = «Свинец плавится при нагревании», B = «Наташа Ростова – не персонаж ».

Задание 2. Дана булева функция f трех переменных.

составьте для нее таблицу истинности; приведите ее к ДНФ и КНФ; приведите ее к СДНФ и СКНФ двумя способами:

используя уже известные ДНФ и КНФ; используя теорему Шеннона о суперпозиции (по таблице истинности);

получите для данной функции полином Жегалкина двумя способами:

методом неопределенных коэффициентов; с помощью законов де Моргана и заменяя отрицание сложением с 1.

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.

Задание 3. Дан вектор значений булевой функции. Найдите ее минимальную ДНФ.

1. (α)f = (10001100)	2. (α)f = (11100011)
3. (α)f = (01010100)	4. (α)f = (00101011)
5. (α)f = (10011001)	6. (α)f = (11101110)
7. (α)f = (11001101)	8. (α)f = (01110110)
9. (α)f = (01011010)	10. (α)f = (11011001)

Задание 4. Проверьте систему булевых функций B на полноту.

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.

Задание 5. Запишите высказывание с помощью кванторов и предикатов. Расшифруйте веденные вами обозначения.

Не все то золото, что блестит. Редкая птица долетит до середины Днепра. Не говорят ни рыбы, ни коты. Если где-то нет кого-то, значит, кто-то где-то есть. Рожденный ползать – летать не может. Не все йогурты одинаково полезны. Все троллейбусы подходящего маршрута идут в депо. Некоторые бутерброды не падают маслом вниз. Если объект зеленый, то его изучает биология, а если он не работает – то физика. Ни один трамвай не может свернуть с рельсов.

Задание 6. Доказать выводимость формулы в исчислении высказываний.

1.	2.
3.	4.
5.	6.
7.	8.
9.	10.

Задание 7. Вывести секвенции:

1. (A→B), (B→A) ў (A↔B)	2. (A↔B), (B↔C) ў (A↔C)
3. (A↔B) ў (A→B)	4. (A↔B) ў ((A∧C)↔(B∧C))
5. (A↔B), A ў B	6. (A↔B) ў ((A∨C)↔(B∨C))
7. (A↔B) ў ((A→C)↔(B→C))	8. (A↔B) ў (B→A)
9. (A→B) ў ((A∨C)→(B∨C))	10. (A→B) ў ((C→A)→(C→B))

Задание 8. Опишите алгоритм указанных действий. Укажите входные данные, последовательность шагов алгоритма, условие останова. Составьте блок-схему алгоритма.

Сложение многозначных натуральных чисел «столбиком». Поиск словарной статьи в словаре (название может состоять из нескольких слов). Умножение многозначного натурального числа на однозначное. Открытие двери подбором ключа из связки. Вычитание многозначных натуральных чисел «столбиком». Пришивание оторвавшейся пуговицы. Замена перегоревшей лампочки. Умножение многочлена на линейный двучлен. Запись информации на DVD-диск с помощью одной из компьютерных программ. Передвижение из дома на занятия в университет (другой район города).

Задание 9. Построить машину Тьюринга, вычисляющую функции натуральных x, y:

1. f(x, y) = x+y	2. f(x) = x/2
3. f(x) = x+1	4. f(x, y) = x–y
5. f(x) = 2x	6. f(x) = x–1
7. f(x) = [x/2]	8. f(x) = x+4
9. f(x) = sign(x–y)	10. f(x, y) = x mod y