Вариант 1

1. Выяснить, является ли рассуждение правильным:

Если цех II не будет участвовать в выпуске нового образца продукции, то не будет участвовать и цех I. Если же II будет участвовать в выпуске нового образца, то в этой работе непременно должны быть задействованы цеха I и III. Необходимо ли участие цеха III, если в выпуске нового образца будет участвовать цех I.

 

2. Найдите все неравносильные между собой и не тож­дественно истинные формулы алгебры высказываний, являю­щиеся логическими следствиями следующих формул (посы­лок):

и  ;

3. Логическая задача: Один из трех братьев поставил на скатерть кляксу.

— Витя не ставил кляксу, — сказал Алеша. — Это сде­лал Боря.

— Ну, а ты что скажешь? — спросила бабушка Борю.

— Это Витя поставил кляксу, — сказал Боря. — А Але­ша не пачкал скатерть.

— Я знаю, что Боря не мог это сделать. А я сегодня не готовил уроки, — сказал Витя.

Оказалось, что двое мальчиков в каждом из двух случаев сказали правду, а один оба раза сказал неправду. Кто по­ставил на скатерть кляксу?

Указание. Образуйте сначала всевозможные попарные дизъюнк­ции из высказываний братьев. Все они будут истинны. Затем рассмотрите конъюнкцию всех этих истинных дизъюнкций. Она также будет истинна. Преобразовав ее к конъюнкции элементарных высказываний, установите виновного.

 

4. Доказать Утверждение 3: ├ØØАÞА

 

5. Введите одноместные предикаты на соответствующих областях и запишите при их помощи следующие высказыва­ния в виде формул алгебры предикатов: Всякое натуральное число, делящееся на 20, делится на 5, 4 и 10.

 

6. Для следующих формул алгебры предикатов найди­те равносильную им приведенную форму, т. е. такую форму, в которой из операций алгебры высказываний имеются толь­ко операции ¬, & и Ú, а знаки отрицания относятся только к предикатным переменным и к высказываниям:

 

7. Методом резолюций проверить следующее соотношение:

 

8. Проанализировать рассуждение:

Если бы кто-нибудь мог решить эту задачу, то и какой-нибудь математик мог бы. Иванов – математик, а не может ее решить. Значит, задача неразрешима.

 

9. Построить композицию машины Т₁Т₂ по паре состояний (q₁₀,q₂₁) и найти результат применения композиции к слову Р=1⁴01 (q₂₀ – заключительное состояние машины T₂)

		q11	q12			q21	q22
T1	0	q12 0 R	q10 1 L	T2	0	q22 1 R	q22 1 R
	1	q12 1 R	q11 0 R		1	q21 0 L	q20 1 S

 

10. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков. Постройте функцио­нальную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т. е. пересчитывала бы набор единиц.