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


Вариант 1

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

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

 

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

и  ;

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

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

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

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

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

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

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

 

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

 

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

 

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

 

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

 

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

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

 

  1. Построить композицию машины Т1Т2 по паре состояний (q10,q21) и найти результат применения композиции к слову Р=1401 (q20 – заключительное состояние машины T2)
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

 

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