матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009
![]()
|
2.4. Задания
Варианты индивидуальных заданий Вариант № 1 1xP(x)R(x)yQ(x,y)). 2. Не всякое действительное число является рациональным. Вариант № 2 1xP(x)(R(x)((yQ(x,y)). 2. Каждый студент выполнил хотя бы одну практическую работу. Вариант № 3 1. xP(x)yP(y))zxR(x, z). 2. Ни одно четное число, большее 2, не является простым. Вариант № 41. xy(P(x)Q(y)) R(y, z)). 2. Некоторые звезды не видны. Вариант № 51. xy(P(x,y)Q(y, z))). 2. Произведение любых двух простых чисел не является простым числом. Вариант № 61. xy(P(x))Q(y)). 2. Всякое положительное число больше всякого отрицательного числа. Вариант № 71. xy(P(x))Q(y, z)). 2. Все ромбы являются параллелограммами. Вариант № 81. xP(x) Q(x, y))yP(y)zQ(y, z). 2. Некоторые четные функции периодические. Вариант № 91xP(x,y) (Q(x) u(P(x,u))). 2. Всякий равносторонний треугольник является равнобедренным. Вариант № 101. xy(zP(x,z) Q(x, z)) uR(x, y, u). 2. Некоторые змеи ядовиты. Вариант № 111. xP(x) y(Q(x, y)zR(x, y,z))). 2. Некоторые реки не судоходны. Вариант № 121.xP(x) yQ(x, y. 2. Никакое знание не бесполезно. Вариант № 131. (xyP(x, y)(xyzQ(x, y,z))yR(y). 2. Некоторые абитуриенты поступили в институт. Вариант № 141. x(P(x) (yzQ(x, y,z))). 2. Студент ответил на некоторые вопросы. Вариант № 151. (xP(x))(xQ(x)(R(x) yS(x, y). 2. Автобус останавливается на всех остановках. Вариант № 161.xP(x) xQ(x). 2. Ни одна монотонная функция не явлвется четной. Вариант № 171. (xP(x)xQ(x))(RS(x, y). 2. Ни один лентяй не заслуживает похвалы. Вариант № 181. P(x, y) (xQ(x, y)uP(u)). 2. Не все металлы твердые. Вариант № 191. xy(Q(xP(x, y)(uR(x,y, u)))). 2. Некоторые студенты получают стипендию. Вариант № 201. P(x, y)xQ(x)(yuR(y,u,y). 2. Некоторые параллелограммы являются ромбами. Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ3.1. Построение формализованного исчисления высказыванийСпособ построения научной теории в виде системы аксиом и правил вывода, позволяющих формальным логическим путем получать утверждения (теоремы) данной теории, называется аксиоматическим методом. Аксиомы (утверждения, принимаемые без доказательств) выделяются, а правила вывода определяются так, что по ним из аксиом могут быть получены все тавтологии алгебры высказываний и только они. В качестве аксиом выбраны формулы следующих видов: (A1) ![]() (А2) ![]() (А3) ![]() где F, G, H – произвольные формулы. Таким образом, каждое из выражений (A1), (A2), (A3) задает лишь форму аксиомы. Они превращаются в аксиомы, если вместо F, G, H подставить конкретные формулы (в частности, пропозициональные переменные). Следовательно, каждое из этих выражений задает бесконечное множество формул. Все они называются аксиомами. Поэтому каждое из выражений (A1), (A2), (A3) называют схемой аксиом. Далее определяется следующее правило получения новых формул из имеющихся. Если имеются формулы F и ![]() ![]() Доказательством или выводом формулы F из множества формул (гипотез) Г называется такая конечная последовательность B1, B2 …Bs формул, каждая формула которой является либо аксиомой, либо формулой из Г (гипотезой), либо получена из двух предыдущих по правилу m. p., а последняя формула Bsсовпадает с F. Если имеется вывод формулы F из множества гипотез Г, то говорят, что F выводима из Г, и пишут Г ⊢ F.Если же имеется вывод F из пустого множества гипотез, то говорят, что F выводима из аксиом или что F доказуема. В таком случае F называют теоремой и пишут ⊢ F. Если Г = {F1,F2…Fm} ⊢G, можно писать F1,F2…Fm⊢ G. Поскольку в аксиомах не участвуют связки ![]() ![]() ![]() ![]() ![]() ![]() ![]() Вывод формулы представляет собой последовательность формул, сопровождаемых указаниями, является ли данная формула гипотезой, аксиомой или получена из других формул по некоторому правилу вывода. Принято вначале выписать все гипотезы и слева указывать номер шага вывода. Пример 3.1. Построить вывод формулы A⊢ B A. (1) A – гипотеза; (2) A (B A) – аксиома (А1); (3) ![]() Любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: ![]() ![]() Некоторые правила вывода исчисления высказываний. 1. Введение конъюнкции: ![]() 2. Удаление конъюнкции: ![]() ![]() 3. Отрицание конъюнкции: ![]() 4. Введение дизъюнкции: ![]() ![]() 5. Удаление дизъюнкции: ![]() ![]() 6. Отрицание дизъюнкции: ![]() 7. Введение импликации: ![]() 8. Удаление импликации: ![]() ![]() 9. Отрицание импликации: ![]() 10. Введение эквивалентности: ![]() 11. Удаление эквивалентности: ![]() ![]() 12. Введение отрицания: ![]() 13. Удаление отрицания: ![]() 14. Закон контрапозиции: ![]() Для построения выводов в исчислении высказываний служит теорема о дедукции:пусть Г – множество формул, A и B – формулы и имеет место вывод: Г, A ⊢B. Тогда имеет место следующий вывод: Г ⊢A B. Таким образом, если нужно вывести формулу вида A B из множества формул (возможно, пустого), можно ввести дополнительное допущение A. Важным следствием теоремы дедукции является правило силлогизма: A B, B C ⊢ AC. Рассмотрим примеры построения вывода в исчислении высказываний. Пример 3.2. Обосновать вывод A (B C), AB ⊢ C.
Пример 3.3. Обосновать правильность следующего рассуждения, построив вывод. Если число целое, то оно рациональное. Если число рациональное, то оно действительное. Число целое. Значит, оно действительное. Сначала формализуем наше рассуждение, введя следующие высказывания: A = “число целое”. B = “число рациональное”. C = “число действительное”. Нужно построить следующий вывод: A B, B C, A ⊢ C. Построим этот вывод.
|