Математическая логика и теория алгоритмов 3 МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) Контрольная работа №2 По дисциплине «Математическая логика и теория алгоритмов» Вариант 1 2003г Южно-Сахалинск. 1) Записать составные высказывания в виде формул . употребляя высказывательные переменные для обозначения простых высказываний: «Для того, чтобы x было нечётным, достаточно, чтобы х было простым»; Решение: Обозначим А = «х - не чётное число» В = «х - простое число» А Þ В (импликация «для А достаточно В»). 2) При каких значениях переменных x , y , z формула ложна? Решение: Составим таблицу истинности: x y z Øx Øy ydz x É(ydx) Øy ÉØx (xÉ(ydz)) É(Øy ÉØx) (xÉ(ydz)) É(Øy ÉØx) ÉØy 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 Т.о. данная формула ложна при: 1) х = 0; y = 1; z = 0; 2) x = 0; y = 1; z = 1; 3) x = 1; y = 1; z = 1;. где 1 - «истина», 0 - «ложь». 3) Является ли тавтологией формула ? Решение: Тавтологий является формула, которая истинна независима от значений входящих в нее переменных. Составим таблицу истинности - p r t Øq Ør Øt pÉq ØrÉØq tÉØr (pÉq)&(ØrÉØq)&(tÉØr) pÉØt ((pÉq)&(ØrÉØq)&(tÉØr))É(pÉØt) 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1