Матлогика зачет

Вариант 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. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков.Постройте функцио­нальную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т. е. пересчитывала бы набор единиц.

Матлогика зачет

Вариант 2

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

Если Антон ляжет сегодня поздно, то утром он будет в нерабочем состоянии. Если он ляжет не поздно, то ему будет казаться, что он много времени теряет бесполезно. Следовательно, или Антон завтра будет в нерабочем состоянии, или ему будет казаться, что он много времени теряет напрасно.

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

и;

3. Логическая задача: Один из четырех мальчиков испортил выключатель. На вопрос: «Кто это сделал?» — были получены такие отве­ты: 1) «Это сделал или Миша, или Коля»; 2) «Это сделал или Витя, или Коля»; 3) «Это не могли сделать ни Толя, ни Миша»; 4) «Это сделал или Витя, или Миша». Можно ли по этим дан­ным установить, кто виновен в поломке выключателя, если из четырех высказываний три высказывания истинны?

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

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

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

7. Проверить на противоречивость множество хорновских дизъюнктов: