матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009

• Название: Методические указания к выполнению практических работ Омск Издательство Омгту 2009
• Анкор: матлогика_методичка.doc
• Дата: 04.05.2017
• Размер: 0.58 Mb.
• Имя файла: матлогика_методичка.doc
• Тип: Методические указания; #7036
• страница: 8 из 14

2.4. Задания

1. 
   Данную формулу логики предикатов привести к предваренной нормальной форме.
   
2. 
   Данное суждение записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык.
   

Варианты индивидуальных заданий

Вариант № 1

1xP(x)R(x)yQ(x,y)).

2. Не всякое действительное число является рациональным.

Вариант № 2

1xP(x)(R(x)((yQ(x,y)).

2. Каждый студент выполнил хотя бы одну практическую работу.

Вариант № 3

1. xP(x)yP(y))zxR(x, z).

2. Ни одно четное число, большее 2, не является простым.

Вариант № 4

1. xy(P(x)Q(y)) R(y, z)).

2. Некоторые звезды не видны.

Вариант № 5

1. xy(P(x,y)Q(y, z))).

2. Произведение любых двух простых чисел не является простым числом.

Вариант № 6

1. xy(P(x))Q(y)).

2. Всякое положительное число больше всякого отрицательного числа.

Вариант № 7

1. xy(P(x))Q(y, z)).

2. Все ромбы являются параллелограммами.

Вариант № 8

1. xP(x) Q(x, y))yP(y)zQ(y, z).

2. Некоторые четные функции периодические.

Вариант № 9

1xP(x,y) (Q(x) u(P(x,u))).

2. Всякий равносторонний треугольник является равнобедренным.

Вариант № 10

1. xy(zP(x,z)  Q(x, z))  uR(x, y, u).

2. Некоторые змеи ядовиты.

Вариант № 11

1. xP(x) y(Q(x, y)zR(x, y,z))).

2. Некоторые реки не судоходны.

Вариант № 12

1.xP(x) yQ(x, y.

2. Никакое знание не бесполезно.

Вариант № 13

1. (xyP(x, y)(xyzQ(x, y,z))yR(y).

2. Некоторые абитуриенты поступили в институт.

Вариант № 14

1. x(P(x)  (yzQ(x, y,z))).

2. Студент ответил на некоторые вопросы.

Вариант № 15

1. (xP(x))(xQ(x)(R(x) yS(x, y).

2. Автобус останавливается на всех остановках.

Вариант № 16

1.xP(x) xQ(x).

2. Ни одна монотонная функция не явлвется четной.

Вариант № 17

1. (xP(x)xQ(x))(RS(x, y).

2. Ни один лентяй не заслуживает похвалы.

Вариант № 18

1. P(x, y)  (xQ(x, y)uP(u)).

2. Не все металлы твердые.

Вариант № 19

1. xy(Q(xP(x, y)(uR(x,y, u)))).

2. Некоторые студенты получают стипендию.

Вариант № 20

1. P(x, y)xQ(x)(yuR(y,u,y).

2. Некоторые параллелограммы являются ромбами.

Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ

3.1. Построение формализованного исчисления высказываний

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

В качестве аксиом выбраны формулы следующих видов:

(A1)

(А2)

(А3)

где F, G, H – произвольные формулы. Таким образом, каждое из выражений (A1), (A2), (A3) задает лишь форму аксиомы. Они превращаются в аксиомы, если вместо F, G, H подставить конкретные формулы (в частности, пропозициональные переменные). Следовательно, каждое из этих выражений задает бесконечное множество формул. Все они называются аксиомами. Поэтому каждое из выражений (A1), (A2), (A3) называют схемой аксиом. Далее определяется следующее правило получения новых формул из имеющихся. Если имеются формулы F и , то они дают формулу G. Это правило называется modusponensили правилом отделения (сокращенно m. p.) и записывается так:

.

Доказательством или выводом формулы F из множества формул (гипотез) Г называется такая конечная последовательность B₁, B₂ …B_s формул, каждая формула которой является либо аксиомой, либо формулой из Г (гипотезой), либо получена из двух предыдущих по правилу m. p., а последняя формула B_sсовпадает с F. Если имеется вывод формулы F из множества гипотез Г, то говорят, что F выводима из Г, и пишут Г ⊢ F.Если же имеется вывод F из пустого множества гипотез, то говорят, что F выводима из аксиом или что F доказуема. В таком случае F называют теоремой и пишут ⊢ F. Если Г = {F₁,F₂…F_m} ⊢G, можно писать F₁,F₂…F_m⊢ G.

Поскольку в аксиомах не участвуют связки , то они вводятся с помощью следующих определений: обозначает ; обозначает ; обозначает .

Вывод формулы представляет собой последовательность формул, сопровождаемых указаниями, является ли данная формула гипотезой, аксиомой или получена из других формул по некоторому правилу вывода. Принято вначале выписать все гипотезы и слева указывать номер шага вывода.

Пример 3.1.

Построить вывод формулы A⊢ B A.

(1) A – гипотеза;

(2) A (B A) – аксиома (А1);

(3) – из (1) и (2) по m. p.

Любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: . Равносильность A B B  A порождает закон контрапозиции: .

Некоторые правила вывода исчисления высказываний.

1. Введение конъюнкции: .

2. Удаление конъюнкции: и .

3. Отрицание конъюнкции: .

4. Введение дизъюнкции: и .

5. Удаление дизъюнкции: и .

6. Отрицание дизъюнкции: .

7. Введение импликации: .

8. Удаление импликации: (m. p.) и .

9. Отрицание импликации: .

10. Введение эквивалентности: .

11. Удаление эквивалентности: и .

12. Введение отрицания: .

13. Удаление отрицания: .

14. Закон контрапозиции: .

Для построения выводов в исчислении высказываний служит теорема о дедукции:пусть Г – множество формул, A и B – формулы и имеет место вывод: Г, A ⊢B. Тогда имеет место следующий вывод: Г ⊢A B.

Таким образом, если нужно вывести формулу вида A B из множества формул (возможно, пустого), можно ввести дополнительное допущение A.
Важным следствием теоремы дедукции является правило силлогизма:

A B, B  C ⊢ AC.

Рассмотрим примеры построения вывода в исчислении высказываний.

Пример 3.2.

Обосновать вывод A (B C), AB ⊢ C.

1. 
   A  (B C) – гипотеза;
   
2. 
   AB – гипотеза;
   
3. 
   A – из (2) и правила удаления конъюнкции;
   
4. 
   B C – из (1), (3) и m. p.
   
5. 
   B – из (2) и правила удаления конъюнкции;
   
6. 
   C – из (4), (5) и m. p.
   

Пример 3.3.

Обосновать правильность следующего рассуждения, построив вывод.

Если число целое, то оно рациональное. Если число рациональное, то оно действительное. Число целое. Значит, оно действительное.

Сначала формализуем наше рассуждение, введя следующие высказывания:

A = “число целое”.

B = “число рациональное”.

C = “число действительное”.

Нужно построить следующий вывод: A B, B C, A ⊢ C.

Построим этот вывод.

1. 
   A B – гипотеза;
   
2. 
   B C – гипотеза;
   
3. 
   A – гипотеза;
   
4. 
   A C – из (1) и (2) по правилу силлогизма;
   
5. 
   C – из (3) и (4) по m. p.