Контрольная
Математическая логика, Вариант 6
Дата сдачи: Ноябрь 2011
1. Записать с использованием пропозициональных переменных и символов заданные &V¬→↔ высказывания:
Вар. 6. «Штурм» сегодня выиграет приз, если «Счастливчики» не выиграют.
2. Упростить выражение при помощи эквивалентных преобразований: XY(X↔Y)
3. Доказать тождественную истинность формулы при помощи эквивалентных преобразований, результат проверить по таблице истинности: (P→Q)→((P→Q)→P)
4. Привести формулу к дизъюнктивной нормальной форме: (X↔Y)(Y↔Z)
5. Привести формулу к конъюнктивной нормальной форме: ((((A→B)→A)→B)→C)→C
6. Найти СДНФ, эквивалентную данной формуле, при помощи эквивалентных преобразований, результат проверить по таблице истинности: (X→Y)(Y→Z)(Z→X)
7. Найти СКНФ эквивалентную данной формуле, при помощи эквивалентных преобразований, результат проверить по таблице истинности: X v Y → (Y→Z)
9. Исследовать заданную систему функций на функциональную полноту: {x v y; x → y;x ¤ y}
10. Предоставить заданное утверждение в виде формулы логики предикатов: любой ученик который сдает все экзамены и выигрывает в лотерею - счастлив
12. найти предваренную нормальную форму: ¥x(A(x) → Зy(B(y)))(A(x) → B(x)) → B(x)
13 Используя метод резолюций в логике предикатов, докажите логичность следующих рассуждений: к уголовной ответственности привлекаются лица, совершившие тайное похищение личного имущества граждан. Обвиняемый Х не совершая тайного похищения личного имущества граждан. Следовательно, обвиняемый Х не может быть привлечен к уголовной ответственности.
14. Определить в какое слово перерабатывает машина Тьюринга с программой заданное слово, если она находится в начальном состоянии q1 и обозревает указанную ячейку (обозреваемые ячейки необходимо считать слева). Изобразить схематически последовательность конфигураций, возникающих на ленте на каждом такте работы машины: a0 l l l a0 l l l (ячейка 1)